1
12
2017
0

新写作环境体验

简单来说就是换了一个暂不能当博客的JB玩意儿做博客。

反正是Markdown,里面的Mathjax什么的配备还算完全。

一个同样是手写的主页

 

Category: HDU | Tags:
11
20
2016
1

[NOIP2016]爆零游记

Category: 游记 | Tags:
11
8
2016
1

NOIP泛做

 

 

NOIP泛做

联赛前没心情做BZOJ跑来写联赛题解23333
点击题目名称前往题目页面查看题目

年份我选择倒序= =

发现数学公式显示[Math Processing Error]的选手请右键任一公式,点击 
Math Settings->Math Renderer->重新选择HTML-CSS即可正常显示公式

觉得阅读难受的不妨试试标导航栏上的同名链接

Category: HDU | Tags:
9
7
2016
0

【抄袭】多项式初步

逛了一圈pls博客,让我来冷静地学一波多项式。

Category: HDU | Tags:
8
17
2016
6

【普及组】DP练习

不会数数,来切51nod普及组dp。老司机莫喷QAQ。感觉51nod题目真友好

妈呀切不动51nod了,再回BZOJ看看。

听说ljx帮我放广告,那我也只能放回去了w【DP大师传送门

Category: 51nod | Tags: DP 51nod
8
11
2016
3

【Cool's Life欢乐赛暨洛谷8月月赛】题解

参赛者
总成绩
A
B
C
D
400 (3038ms)
100
100
100
100
400 (3102ms)
100
100
100
100
400 (10684ms)
100
100
100
100
400 (13208ms)
100
100
100
100
#5
wyxorz
400 (13910ms)
100
100
100
100
350 (8906ms)
100
100
100
50
#7
YYMHL
350 (14935ms)
100
100
100
50
340 (9434ms)
100
100
100
40
320 (15164ms)
100
100
100
20
#10
ahwhGQY
305 (3050ms)
100
45
100
60

 

大家纷纷AK,出题人受到打击;大家来月再战思考难度大战!

Category: HDU | Tags:
5
8
2016
14

【CTSC&APIO2016】蒟蒻滚粗记

滚粗辣
 

Category: 罗干 | Tags: CTSC APIO
5
7
2016
0

【洛谷5月月赛】题解

省选滚粗来出一套题冷静一下233333

恭喜前6名获奖,以及cyxhahaha成功AK!

400 (9433ms)100
100
100
100
380 (7429ms)
100
100
80
100
344 (1968ms)
100
100
80
64
328 (5625ms)
100
100
80
48
304 (5607ms)
100
100
80
24
#6
Riolu
292 (1552ms)
100
100
80
12

 

Category: HDU | Tags:
4
30
2016
0

专题:状态压缩动态规划

再不切题就要退役辣,学习老板娘板切专题。

BZOJ 1087 1076 2064 1725 1231 1688 1072 1097 2734 1226 2595 2073 2004 2669
CODEVS 1050 2800 1358 1480 2009 2017 2125 2743 2818 2889 2941 3122 3196  
hdu 3001 3681 4114 4892 4284 1074 3182 4568 4336 1565 2167 4539    

BZOJ:

1087:在N*N的棋盘上放K个互不攻击的王的方案数。

正确姿势:打表233

f[i][j][S]表示第i行状态为S时还剩下j个王可放。位运算预处理一下转移什么的轻易AC了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 10
#define maxk 82
#define maxS 512
using namespace std;
int n,k,S;
long long f[maxn][maxk][maxS],cnt[maxS],ans;
int main()
{
	scanf("%d%d",&n,&k);S=1<<n;
	for(int i=0;i<S;i++)if(!(i&(i<<1)))
		for(int x=i;x;x>>=1)cnt[i]+=(x&1);	
	f[0][k][0]=1;
	for(int i=1;i<=n;i++)
		for(int x=1;x<=k;x++)
			for(int s=0;s<S;s++)
				for(int t=0;t<S;t++)
					if(!(s&t)&&!(s&(s<<1))&&!(t&(t<<1))&&!(s&(t<<1))&&!(t&(s<<1))&&cnt[t]<=x)
						f[i][x-cnt[t]][t]+=f[i-1][x][s];	
	for(int i=1;i<=n;i++)
		for(int s=0;s<S;s++)
			ans+=f[i][0][s];
	printf("%lld",ans);
}

1725:

棋盘的给定位置上放置不相邻旗子的方案数。

比上一题还要斯波,f[i][S]表示第i行状态为j的方案数。

#include<cstdio>
#include<cstring> 
#define MO 100000000
using namespace std;
int n,m,s[13],f[13][4096],x,ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)scanf("%d",&x),s[i]=(s[i]<<1)+x;
	int S=1<<m;
	for(int i=0;i<S;i++)if(!(i&(i<<1))&&(i|s[1])==s[1])
		f[1][i]=1;
	for(int i=2;i<=n;i++)
		for (int l=0;l<S;l++)if(f[i-1][l])
			for(int r=0;r<S;r++)
				if(!(l&r)&&!(r&(r<<1))&&(r|s[i])==s[i])
					f[i][r]=(f[i][r]+f[i-1][l])%MO;
	for(int i=0;i<S;i++)
		ans=(ans+f[n][i])%MO;
	printf("%d",ans);
}

CODEVS:

1050:轮廓线状压DP,详见http://scarlet.is-programmer.com/posts/181697.html

hdu:

3001:

每个点经过不超过两次的TSP。f[i][S]表示经过点的状态S时,最后一个点为i的最小费用。这里S三进制状压,表示每个点已经遍历的次数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 11
#define maxS 59049
#define AE(u,v,w) E[Si]=(Ed){v,w},nxt[Si]=idx[u],idx[u]=Si++
#define mi(a,b) a=min(a,b)
using namespace std;
struct Ed{int v,w;}E[maxS];
int f[maxn][maxS],n,m,idx[maxn],nxt[maxS],trn[maxn],Si,u,v,w,S,tri[maxS][maxn],c[maxS];
int main()
{
	trn[0]=1;for(int i=1;i<=10;i++)trn[i]=trn[i-1]*3;
	for(int i=0;i<maxS;i++)for(int j=0,x=i;j<=10;j++,x/=3)tri[i][j]=x%3,c[i]+=((x%3)!=0);
	while(scanf("%d%d",&n,&m)==2)
	{
		Si=0;S=trn[n];
		memset(idx,-1,sizeof(idx));
		memset(f,0x7f7f7f7f,sizeof(f));
		int ans=f[0][0],INF=f[0][0];
		for(int i=1;i<=m;i++)scanf("%d%d%d",&u,&v,&w),u--,v--,AE(u,v,w),AE(v,u,w);
		for(int i=0;i<n;i++)f[i][trn[i]]=0;
		for(int s=0;s<S;s++)
			for(int u=0;u<n;u++)if(tri[s][u]!=0) 
				for(int i=idx[u];i+1;i=nxt[i])if(tri[s][E[i].v]<2)
					mi(f[E[i].v][s+trn[E[i].v]],f[u][s]+E[i].w);
		for(int s=0;s<S;s++)if(c[s]==n)
			for(int i=0;i<n;i++)
				ans=min(ans,f[i][s]);
		if(ans!=INF)printf("%d\n",ans);
		else puts("-1");
	}
}
Category: 罗干 | Tags: 动态规划
2
15
2016
0

【SDOI2013】校测

颓不完作业来颓竞赛QAQ

BZOJ:3122-3124

校内:60+10+100(T1被map卡20分表示不服)

Category: 魔泥赛 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com