BZOJ 1079 着色

发表于 2017-03-17 | 更新于 2018-06-18

Link

Solution 1

脑洞超大首先考虑最最暴力的做法，把每种颜色的剩余个数压起来的状压DP肯定是可以做的， $f[i][S]$ 表示序列中的颜色的个数的状态为 $S$ ，第一个位置颜色是 $i$ 的方案数目，转移就枚举就好了只是状态有 $15\times 5^{15}$ 个(233)。（PS：排队题？）然后考虑做了什么无用功：个数相同的颜色是本质相同的，一种方案的颜色置换一下就是另一个方案。因此，要开一个相当大的脑洞： $f[i][S]$ 分别记录剩余 $1\sim 5$ 个可用块的颜色数， $i$ 表示上一位放的颜色的剩余的个数。 DFS，枚举当前要放的色块的可用个数，然后相应加减，进入下一层DFS，累计返回的答案。具体做法是，现在要放的一种剩下 $c$ 个可用块的颜色，那么计算。假如说，那么答案累加 $res*S[c]$ ，否则累加 $res*(S[c]-1)$ 。仔细想想是非常妙的，把本质相同的状态一起计算，通过乘法原理累计答案。

Code 1

#include "lucida"
const int P=1000000007;
struct Five {
	int a[6];
	Five(int n[]) {
		for(int i=0;i<=5;++i)
			a[i]=n[i];
	}
	int &operator [](int x) {
		return a[x];
	}
};
int64 f[6][16*16*16*16*16];
int Hash(Five s) {
	int res=0;
	for(int i=1;i<=5;++i)
		(res*=16)+=s[i];
	return res;
}
int64 DP(int last,Five s) {
	int code=Hash(s);
	if(~f[last][code]) return f[last][code];
	int64 res=0;
	for(int i=1;i<=5;++i) if(s[i]) {
		--s[i],++s[i-1];
		(res+=((s[i]+1)-(last==i+1))*DP(i,s))%=P;
		++s[i],--s[i-1];
	}
	return f[last][code]=res;
}
int main() {
	freopen("input","r",stdin);
	int num[6];memset(num,0,sizeof(num));
	int k;is>>k;
	for(int i=1;i<=k;++i) {
		int c;is>>c;
		num[c]++;
	}
	memset(f,-1,sizeof(f));
	for(int i=0;i<=5;++i) f[i][0]=1;
	int64 Ans=DP(0,Five(num));
	os<<Ans<<'\n';
	return 0;
}

Solution 2

发现有大神给出了更科学的清真做法，其实和那个排队神似 $f[i][j]$ 表示构造了含有所有前 $i$ 种颜色的色块的序列，有 $j$ 对同色相邻那么答案就是 $f[K][0]$ 考虑转移现在有 $cnt[i+1]$ 个第 $i+1$ 种颜色的色块，要把它们分到已经有的长度为 $pref[i] (pref[i]=\sum\limits_{j=1}^i cnt[i])$ 的序列中。大体可以用这些色块搞这三件事： ~~1. 确立社会主义市场经济~~

放到一起，组成新的相邻同色对
塞到已经有的相邻同色对中，无情地拆散
老老实实地分到一些相邻不同色的对的中间

然后这个过程看起来是很复杂的，其实经过一番抽象可以看成这样的东西：把 $cnt[i+1]$ 个色块，分成 $dc$ 个组，把这些组的前 $div$ 个塞到已有的相邻同色对中间，后 $dc-div$ 个塞到相邻的不同色对中间。那么这样的话，新的序列就会多出 $(cnt[i+1]-dc)-div$ 对相邻同色对那么这样构造的方案数目呢？把 $cnt[i+1]$ 个分 $dc$ 组，插板法， $C_{cnt[i+1]-1}^{dc-1}$ 塞前 $div$ 组，有 $C_j^{div}$ 种方法剩下的，有 $C_{pref[i]+1-j}^{dc-div}$ 种方法

Code 2

#include "lucida"
const int MAXN=80,P=1e9+7;
int64 f[MAXN][MAXN],C[MAXN][MAXN];
int cnt[MAXN],pref[MAXN];
struct PREP{PREP() {
	C[0][0]=1;
	for(int i=1;i<MAXN;++i) {
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	}
}}srO_Orz;
int main() {
	freopen("input","r",stdin);
	int K;is>>K;
	for(int i=1;i<=K;++i) {
		is>>cnt[i];
		pref[i]=pref[i-1]+cnt[i];
	}
	f[0][0]=1;
	for(int i=0;i<K;++i)
		for(int j=0;j<=pref[i];++j)
			for(int dc=1;dc<=cnt[i+1];++dc)
				for(int div=0,g;div<=dc;++div)
					if((g=j+(cnt[i+1]-dc)-div)>=0)
						(f[i+1][g]+=f[i][j]*C[cnt[i+1]-1][dc-1]%P*C[j][div]%P*C[pref[i]+1-j][dc-div])%=P;
					else 
						break;
	int64 Ans=f[K][0];
	os<<Ans<<'\n';
	return 0;
}

不得不说，

一道题的两种做法都这么巧妙优美凝练，这真＊＊是个好题！

BZOJ 4710 分特产

发表于 2017-03-17 | 更新于 2018-06-18

Link

容斥唉。。

Solution

加限制的记数就应该考虑一下容斥？ $f[i][j]$ 表示前 $i$ 中特产随便分给 $j$ 个人的方案数目，然后每个特产用插板法计算分法。。然后枚举得不到特产的人数容斥。。

Tips

万用的插板法。。

Code

#include "lucida"
const int P=1000000007,MAXN=1000+11;
int64 C[MAXN<<1][MAXN<<1];
struct _{_(){
	C[0][0]=1;
	for(int i=1;i<=2000;++i) {//2000上界...
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	}
}}Auto;
int main() {
	freopen("input","r",stdin);
	static int f[MAXN][MAXN],c[MAXN];
	int n,co;
	is>>n>>co;
	//f[i][j] 表示把前i个物品随便分给j个人的方案数
	for(int i=1;i<=co;++i)
		is>>c[i];
	for(int i=1;i<=n;++i)
		f[0][i]=1;
	for(int i=1;i<=co;++i)
		for(int j=1;j<=n;++j)
			f[i][j]=f[i-1][j]*C[c[i]+j-1][j-1]%P;//[][j]..
	//f[n][i] 分给i个人的方案数目
	int64 Ans=0;
	for(int i=0;i<=n;++i)//i个人分不到的方案数目
		(Ans+=f[co][n-i]*C[n][i]*(i&1?-1:1))%=P;//没%
	(Ans+=P)%=P;
	os<<Ans<<'\n';
	return 0;
}

BZOJ 4321

发表于 2017-03-17 | 更新于 2018-06-17

Link

状态状态。。

Solution

心路历程

一开始，觉得必须需要知道最后一个数字的位置，就可以推合法状态了。写完之后忽然发现自己zz了：不合法状态也可以转化成合法状态。然后发现，并不需要知道最后一个数字的位置，因为仅仅从合法状态来说，最后一个数字不管在哪，都是少了两个可以放的位置。然后发现必须要知道有了多少对不合法的，然后想转移。然后发现，最后一个数字和其它的数字不能一起算，然而又已经删掉了最后一个数字的位置那个状态，所以就无力了。。。其实就按照这个思路接着想，只差一步了

最后

$f[i][j][0/1]$ 表示前 $i$ 个数字，在 $1\sim i-1$ 中有 $j$ 对不合法的， $i-1$ 与 $i$ 相邻/不相邻的方案数目。转移需要花点脑筋，而且还有一个~~我觉得很容易漏掉的~~好吧就是我漏掉的部分 $\downarrow$

f[i][j][1]+=f[i-1][j][1] $\uparrow$

Why Can't

没有继续大力分析，没有继续把问题抽象下去

Code

#include "lucida"
using std::max;
const int P=7777777,MAXN=1000+11;
int64 f[MAXN][MAXN][2];
int main() {
	freopen("input","r",stdin);
	int n;is>>n;
	//f[i][j] 前i个人的排列 最后一个人为j
	//只要知道最后一个数字的位置??
	//并不需要知道 只需要知道少了两个可以待的位置就行了!
	//f[i][j]表示前i个数字，j对不合法
	f[1][0][0]=1;
	for(int i=2;i<=n;++i)
		for(int j=0;j<=i;++j) {
			(f[i][j][0]+=(f[i-1][j][0]*max(i-j-2,0)+f[i-1][j-1][1]*max(i-j-1,0)))%=P;
			(f[i][j][1]+=(f[i-1][j][0]*2+f[i-1][j-1][1]+f[i-1][j][1]))%=P;//f[i-1][j][1]....
			(f[i][j][0]+=(f[i-1][j+1][0]*(j+1)+f[i-1][j][1]*j))%=P;
		}
	os<<f[n][0][0]<<'\n';
	return 0;
}

打表(2333)

#include<cstdio>
const int Ans[]={0,1,0,0,2,14,90,646,5242,47622,479306,5296790,1556818,6839196,2618495,979672,2780742,6351756,1622080,2317213,2571415,7589087,5658722,7608399,6636261,4668421,7151323,3463698,4156794,4264499,5635853,6694840,2815244,6087105,2410849,138105,6232687,4045091,5426290,443641,2132596,7300720,3837755,683117,6707322,4505086,6965880,4427426,4624186,1633284,5054300,3707705,280807,7350611,6884553,3601801,2427241,4950492,1686306,6296813,4597759,5133390,5889499,3818810,666987,1669662,5049011,2299852,4731598,3071649,7354002,6093291,4043220,1517871,2203318,2339158,2233651,6915925,5535396,569059,6518458,1643343,621793,649215,5700623,268360,2406235,1576587,6770258,5337622,4162333,1050359,1253251,4101392,7401333,1827870,2681459,3743523,767947,2646862,3207770,517802,2948811,2480880,6880517,6183333,6979293,2934653,87516,6316788,2579861,1413692,2938668,3198980,7690710,162125,5876967,7050837,4544169,2517853,2984897,3852570,4068038,3755810,336753,5648517,5964467,7579328,1314739,4905010,4341055,5881025,5615323,1813051,5787382,1140427,6724244,4113573,6909270,9863,4911548,5192356,2816477,370921,5745668,1055932,4968796,6466084,2348198,7041350,2985873,3279516,6465764,2591925,3393346,3641471,1461389,950381,846340,2553519,1746115,3881145,1358265,2790180,5474331,2029449,6639168,1269072,3724565,3750419,4938996,5057232,7292220,1879531,5663210,6177075,5875876,2328453,5066616,4617531,6466296,5290250,2692625,3618119,6072464,4404510,3069673,7253998,5204843,3508227,4711097,7126610,6893147,5853766,890320,5559204,6971508,1003094,2774848,1158190,5604562,4161951,1328313,3024947,4528131,7115669,837972,4659265,4950229,1073009,1734654,7312166,6810327,4622343,5561337,2255844,232841,5930773,3738510,4039897,4343355,4877777,4282219,2043160,7373280,5959493,2364466,2345138,6021713,5408420,2138843,2578676,3491914,5491991,2938693,2343511,3835038,918729,3506445,7255536,4830895,584295,6602573,677442,4971995,4163084,4054588,5432974,1891297,5678780,4514570,6885081,446143,7468721,5312285,4974429,2888443,3987105,432075,776113,3374867,6819492,4062998,484283,6198973,4110260,6414532,4706486,4842032,2831757,5202818,4559439,5282403,1989577,1572353,289031,7713127,4452303,3527710,7513065,4843165,386289,5234326,4148807,2818226,1888967,2812397,1802929,873242,6212207,6248566,3194263,4409318,3206462,1353966,1969724,1347366,2232725,5499730,7045825,5609856,1573336,2239754,3766001,2586180,5716216,425471,3659229,2834648,6287737,3636051,3399590,2466721,2128276,4461870,5344761,6785267,6957056,2179774,2733593,3772234,7289702,4035666,3851765,4477899,3768252,4038221,7054071,5834549,5453121,287174,4048255,5253243,4392271,7179323,76811,146102,1578424,3268670,4207173,5855407,3773962,5003425,2235067,2802967,2729084,3455188,1119785,4035420,1732297,778944,824139,1100826,95541,5544432,1566498,1567440,551322,5215629,3604182,7771269,7685155,2216764,1285347,918300,2396983,7217825,3369371,3315093,5588110,1245062,6643695,7636138,1633962,5819872,3776537,3646486,2724022,7351566,2831116,6313418,890839,3227467,1511926,1427979,3772960,756685,3873451,531407,6240922,1128705,4731741,4193026,1297066,4906586,3934726,7375604,47022,1998717,760307,46192,207187,665821,4981461,5687210,1772596,128959,2076733,5990543,7355955,565388,2833764,5905004,5258304,4921608,6612810,2044310,1662838,5450645,452424,3389090,2672699,5626837,2839961,2737467,5020305,5290691,829642,4138448,6228139,4044098,619733,2027519,4508749,3669755,282920,1162580,3158377,4593034,2850970,5237736,976495,2895815,2072645,6870551,4647442,2358136,6248207,6739395,5526095,2209892,6636481,1031973,6618286,1749713,642721,7545831,2940204,288010,3862217,2559113,2611315,1232348,3650431,4818813,4964874,4839700,7154843,110432,6379298,3883053,6804568,6186042,6011504,4339115,738101,7690765,4756501,2851057,5569429,3025083,2393387,7449036,2562002,6323519,4969574,6272051,1479081,6100574,7398146,5877758,2186920,5000148,6374576,7473408,6703105,1402345,2454328,6075061,822690,3304548,1830264,927490,3950401,518453,5888471,5975619,3786585,6959356,2883030,4177684,6996222,170505,6207097,3076089,351689,4133294,5417104,5800191,6859231,1820398,3467903,4516377,2527248,64141,1494383,2632433,6170088,3650845,3295182,91270,644098,7445051,4119851,4422809,1527804,5888734,4496684,2567950,6292344,2458833,2797649,934173,4120160,5905876,345065,6425137,1074914,4446231,5024353,1717161,6469011,28938,663007,2219111,4383681,7453210,4971584,1450341,6822158,149651,3827195,7260301,6879381,6668639,917444,5072550,6159666,3935994,2674036,1598837,2814919,1680480,4448983,5955549,1166964,1842861,200415,5878388,7083814,1635564,4702126,4493978,6915490,20372,7003691,2470234,5461484,244711,4479056,3846877,472750,5611779,4681183,3740975,375391,2063816,5658871,1791960,211570,631089,2515436,787022,4246012,3143993,5882721,6783110,325594,3667643,6446197,5730052,6427100,1900131,5808434,5153698,635677,335417,3106118,369333,7031386,488430,113753,6070827,5165792,4356386,94872,7490282,1718061,4268625,7463106,4475973,2415085,4483149,4799443,2880120,102945,1186696,1019853,3992925,5600183,7216631,5725995,7333253,1047571,6906450,1896805,6601118,2557770,685200,3607313,6624422,3884197,4602597,3614038,6845519,7057766,3851131,3731735,2409601,5397267,6871766,427033,4123782,3163443,2346631,5381854,6787766,1240247,2524041,3323077,7512481,4944828,6597820,1519652,4814711,6626191,2574038,166890,2660609,7300204,6408366,7135493,1279091,2671524,2306980,5673220,4950377,6999042,2964380,6184505,564828,402027,353822,4236759,5224729,3291863,7175471,7654677,3083840,6959540,4086899,3118886,4329779,3070338,4342742,3918694,5865160,4989350,6770721,2822331,4405249,4502038,1724209,2852395,5346122,3106538,7120126,1247076,3930582,1932255,24815,7506389,5470310,7359948,4973782,4046296,3594889,5490926,4626900,645030,5696256,5475461,5986265,5353722,5391729,987177,5492661,5339818,625172,4352056,1266220,6247290,2603935,6359011,5753936,5157479,6626884,5160095,5931051,774874,4848857,4480435,7318152,1734742,4347529,1144304,7089766,5413689,3183788,925951,6510586,4902852,2825396,6230163,4192383,7534388,6073643,7110847,932250,3779335,1030097,7064639,4830699,6653407,810094,4256577,1367898,3055481,1775101,2598646,4483964,689593,7225887,1610196,1476354,6033455,3397015,692508,4410411,1590599,5925290,3627045,3280493,2052058,2846069,1441414,7281229,3077753,7294138,633074,2695832,1699570,4879180,6690505,3048283,4151177,2511732,4447409,1748420,1354964,7400180,3727612,1862768,4707914,5846252,3208882,230263,2645786,4878853,66355,6495502,6956034,73348,2846433,2719546,334670,5976339,6744844,2100853,3210793,3265449,88371,4015788,1342077,7605058,4743621,5455585,7184641,276707,4597992,1069325,947640,2042795,4484170,3322842,2933913,3656863,6447793,538817,189022,5140739,6875710,3817769,466865,387721,3321522,241555,2383708,188326,1613097,2901710,5193960,4042639,2881012,7414269,3856960,7412934,5139610,3728786,1131684,2583839,5060599,3552890,5903369,5746580,4413313,4469499,1098014,6419366,2470995,5287125,1931104,6943872,1682493,5027742,453206,7743608,4758981,3712779,4903026,2975342,1667807,1862408,2788571,3963719,4772467,1407243,1913192,1451995,3162171,6325912,5795674,159852,5665844,4960871,5456921,7553758,849683,645040,585795,2481141,4085719,3004140,2779992,6984381,6413557,3270169,1433700,559789,1742490,1190072,3712424,3839553,1431458,2813431,23213,5220550,5215873,2315052,5590378,6596849,3616685,2144302,7264216,7541529,1240675,4149772,7416864,6251663,123803,2673040,7214877,4169450,5824318,252812,3959174,1791558,4762941,7289998,4696827,1390029,7170415,3191676,32334,2929646,7404143,6245335,3897624,3388602,5565156,833755,3952026,3655801,108075,7545682,2888942,1801203,6528425,1170175,6440642,2967214,4498665,5912977,6195947,5592971,3864428,1720959,7098352,1578490,5075406,138073,569507,5628034,2607001,2401852,5992794,799848,1795341,5182918,3154775,5586723,3174187,6588194,3257212,4831174,585719,5954346,1458070,371341,6845212,496636};
int main() {
	int n;scanf("%d",&n);
	printf("%d\n",Ans[n]);
	return 0;
}

BZOJ 3416 Take-out

发表于 2017-03-16 | 更新于 2018-06-18

Link

非常妙的做法啊。。

Solution

需要方案满足每次消除都不跨过已经消除的块，换句话说，就是消除的时候两块要么没有间隔，要么间隔 $>k+1$ ，中间的 $k+1$ 块必须自行消除掉。注意到保证有解，那就只要贪心地构造解，然后反向地输出，就可以得到答案啦

Tips

考虑构造的过程，如果正着走顾虑太多，就倒着来，使得每次的决策都是不得不做出的决策。尝试这样的思路，可能有奇效。

Code

#include "lucida"
using std::vector;
const int MAXN=1000000+11;
int main() {
	freopen("input","r",stdin);
	static char s[MAXN];
	static int pref[MAXN],stack[MAXN],top;
	vector<int> Ans[MAXN];int ac=0;
	int n,K;is>>n>>K>>(s+1);
	for(int i=1;i<=n;++i) {
		pref[i]=pref[i-1]+(s[i]=='b'?1:-K);
		stack[++top]=i;
		if(top>=K+1 && pref[stack[top-K-1]]==pref[i]) {
			++ac;
			for(int j=1;j<=K+1;++j)
				Ans[ac].push_back(stack[top--]);
		}
	}
	for(int x=ac;x;--x) 
		for(int i=Ans[x].size()-1;~i;--i)
			os<<Ans[x][i]<<(i==0?'\n':' ');
	return 0;
}

BZOJ 3426 Tower Defense Game

发表于 2017-03-16 | 更新于 2018-06-18

Link

好吧我不刷POI了。。

Solution

我真的没有意识到

突然XYW的男人看到了他的电脑屏幕：我只要用k座塔就可以了。（保证存在仅用k座塔就可以保卫所有城市的情况）

是题目条件然后想了很久DP种种

然而因为这个条件，每次只要随便选一个没有被覆盖的就行了。。

在原方案中能覆盖这个点的所有塔的攻击范围的并集一定小于等于这个攻击距离为2的塔的攻击范围——commonc

Tips

好吧改刷省选\UR题

Code

#include "lucida"
const int MAXN=500000+11,MAXM=1000000+11;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXM<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
bool covered[MAXN];
void Cover(int pos,int d=2,int from=0) {
	covered[pos]=1;
	if(d)
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=from)
				Cover(e->to,d-1,pos);
}
int main() {
	freopen("input","r",stdin);
	static int Ans[MAXN],ac;
	int n,m,K;is>>n>>m>>K;
	for(int i=1;i<=m;++i) {
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	for(int i=1;i<=n;++i)
		if(!covered[i]) {
			Ans[++ac]=i;
			Cover(i);
		}
	os<<ac<<'\n';
	for(int i=1;i<=ac;++i)
		os<<Ans[i]<<(i==ac?'\n':' ');
	return 0;
}

BZOJ 3780 数字统计

发表于 2017-03-16 | 更新于 2018-06-17

Link

Solution

从低位到高位DP。。现在感觉这种边DP边卡的做法很舒服啊。。 $f[i][0/1][0/1]$ 表示第 $i$ 位，是否卡到了上界(卡上界的情况需要包含超上界的情况，因为是从低到高DP的)，删之后剩下了 $0/1$ 的方案数目。转移的时候和从高到低的判断条件不太一样，不要手滑写错。

Code

#include "lucida"
using std::reverse;
using std::max;
const int MAXB=200+11;
IO::Ost &operator <<(IO::Ost &,struct BinNum &); 
struct BinNum {
	short a[MAXB];int n;
	short &operator [](int x) {
		return a[x];
	}
	BinNum(int x=0) {
		memset(a,0,sizeof(a));
		for(n=0;x;x>>=1)
			a[++n]=x&1;
	}
	friend BinNum operator +(BinNum a,BinNum b) {
		int &n=a.n=max(a.n,b.n);
		for(int i=1;i<=n;++i) {
			a[i]+=b[i];
		}
		for(int i=1;i<=n;++i) {
			a[i+1]+=a[i]>>1;
			a[i]&=1;
			if(a[i+1]) 
				chkmx(n,i+1);
		}
		return a;
	}
	friend BinNum operator -(BinNum a,BinNum b) {
		int &n=a.n=max(a.n,b.n);
		for(int i=1;i<=n;++i)
			a[i]-=b[i];
		for(int i=1;i<=n;++i)
			if(a[i]<0) {
				a[i]+=2;
				a[i+1]--;
			}
		while(n && !a[n]) --n;//n..
		return a;
	}
	#define template template <class T>
	template BinNum &operator +=(T a) {
		return *this=*this+a;
	}
	template BinNum &operator -=(T a) {
		return *this=*this-a;
	}
	#undef template
};
IO::Ist &operator >>(IO::Ist &is,BinNum &x) {
	int &n=x.n=0;
	char ch;
	while(ch=getchar(),(ch!='0' && ch!='1'));
	do	x[++n]=ch-'0';
	while(ch=getchar(),(ch=='0' || ch=='1'));	
	reverse(x.a+1,x.a+1+n);
	return is;
}
IO::Ost &operator <<(IO::Ost &os,BinNum &x) {
	int p=x.n;
	while(p && !x[p]) p--;
	if(p) do 
		putchar(x[p--]+'0');
	while(p);
	else putchar('0');
	return os;
}
BinNum f[MAXB][2][2];//定义成了int64????2333..
BinNum Calc(BinNum x,int Y) {
	#define merge(x,y) ((x)==0 && (y)==0)
	memset(f,0,sizeof(f));
	//f[i][(f)0/1][(s)0/1] 表示后i位,</>= x,删出来的结果为0/1
	//答案就是f[len][0][Y]
	for(int i=0;i<2;++i)
		f[1][i>=x[1]][i]=1;
	for(int i=2;i<=x.n;++i) {
		for(int dt=0;dt<2;++dt)
			for(int ff=0;ff<2;++ff)
				for(int fs=0;fs<2;++fs) {
					f[i][dt>x[i] || (dt==x[i] && ff)][merge(dt,fs)]+=f[i-1][ff][fs];	
				}
	}
	return f[x.n][0][Y];
}
void Work() {
	int M,Y;is>>M>>Y;
	BinNum l,r;is>>l>>r;
	BinNum Ans=Calc(r+1,Y)-Calc(l,Y);
	os<<Ans<<'\n';
}
int main() {
//	freopen("input","r",stdin);
	int T;is>>T;
	while(T--)
		Work();
	return 0;
}

BZOJ 3427 Bytecomputer

发表于 2017-03-16 | 更新于 2018-06-17

Link

Solution

直观的感受就是最后答案一定是 $-1,-1,-1,...,0,0,0,...,1,1,1$ 因为如果答案中存在了 $\{-1,0,1\}$ 之外的数字，那么那一串数字一定可以少加一个 $1$ 或者少减一个 $1$ 。这样之后一定不会破坏非降性质，而且可以减小答案。

Code

#include "lucida"
using std::min;
int min(const int &x,const int &y,const int &z) {
	return min(x,min(y,z));
}
const int MAXN=1000000+11,INF=0x1f1f1f1f;
int main() {
	static int a[MAXN],f[3][MAXN];
	#define f(x) f[(x)+1]
	memset(f,31,sizeof(f));
	freopen("input","r",stdin);
	int n;is>>n;
	is>>a[1];
	f(a[1])[1]=0;
	for(int i=2;i<=n;++i) {
		is>>a[i];
		f(-1)[i]=f(-1)[i-1]+a[i]+1;
		if(a[i]!=-1)
			f(0)[i]=f(-1)[i-1]+a[i];
		if(a[i]==0)
			chkmn(f(0)[i],min(f(-1)[i-1],f(0)[i-1]));
		f(1)[i]=f(1)[i-1]+1-a[i];
		if(a[i]==1)
			chkmn(f(1)[i],min(f(-1)[i-1],f(0)[i-1],f(1)[i-1]));
	}
	int Ans=min(f(-1)[n],f(0)[n],f(1)[n]);
	if(Ans==INF)
		os<<"BRAK"<<'\n';
	else
		os<<Ans<<'\n';
	return 0;
}

BZOJ 3417 Tales of seafaring

发表于 2017-03-16 | 更新于 2018-06-18

Link

Solution

一开始发现需要求奇偶长度的SP，觉得并不能 $O(n)$ BFS，然后就抱着试试看的心态写了 $O(ke)$ 的SPFA，被细节卡了一会儿，改完居然过了。。然后搜题解，发现就是个BFS，相当于一个点拆两个，每个点最早入队列的时候肯定是最短路。。。

Code

#include "lucida"
using std::queue;
using std::swap;
using std::vector;
const int MAXN=5000+11,MAXK=1000000+11;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
int sp[MAXN][2];
void SP(int s) {
	static bool inq[MAXN];
	queue<int> Q;
	memset(inq,0,sizeof(inq));
	Q.push(s);inq[s]=1;sp[s][0]=0;
	while(!Q.empty()) {
		int cur=Q.front();Q.pop();
		inq[cur]=0;
		for(Edge *e=G[cur];e;e=e->pre) {
			int u=e->to;
			if((chkmn(sp[u][0],sp[cur][1]+1) | chkmn(sp[u][1],sp[cur][0]+1)) && !inq[u]) {//||..
				Q.push(u);
				inq[u]=1;
			}
		}
	}
}
struct QNode {
	int t,d,id;
	QNode(int t,int d,int id):t(t),d(d),id(id){}
};
vector<QNode> query[MAXN];
int main() {
	//freopen("input","r",stdin);
	static bool Ans[MAXK];
	int n,m,K;is>>n>>m>>K;
	//需要一条奇数长度的sp 一条偶数长度的sp
	for(int i=1;i<=m;++i) {
		int a,b;is>>a>>b;
		Adde(a,b);
	}
	for(int i=1;i<=K;++i) {
		int s,t,d;is>>s>>t>>d;
		if(s==t && d && !G[s])
			Ans[i]=0;
		else {
			if(s>t) swap(s,t);
			query[s].push_back(QNode(t,d,i));
		}
	}
	for(int i=1;i<=n;++i) if(query[i].size()) {
		memset(sp,126,sizeof(sp));
		SP(i);
		for(int v=0,ev=query[i].size();v<ev;++v)
			Ans[query[i][v].id]=sp[query[i][v].t][query[i][v].d&1]<=query[i][v].d;
	}
	for(int i=1;i<=K;++i)
		os<<(Ans[i]?"TAK":"NIE")<<'\n';
	return 0;
}

CF404 Div.2

发表于 2017-03-16 | 更新于 2018-06-18

Link

D

比赛直到还剩十分钟的时候才考虑到要化组合数的式子，之前一直觉得组合数的方法不可想因为涉及到组合数就需要长度就需要枚举，然后一直在想怎么可以不看长度算贡献。。。这就是思维漏洞。。

范德蒙恒等式

$\sum C_{n}^{k-i}C_{m}^i=C_{n+m}^k$

证明

考虑二项式展开: $(a+b)^n=\sum\limits_{i=0}^nC_n^ia^ib^{n-i}$ 带入得到 $(a+b)^n(a+b)^m=\sum\limits_{i=0}^nC_n^ia^ib^{n-i}\sum\limits_{j=0}^mC_m^ja^jb^{m-j}$ $=(a+b)^{n+m}=\sum\limits_{i=0}^{n+m}C_{n+m}^ia^ib^{n+m-i}$ 令 $b=1$ ，就可以得到 $a^i$ 的系数为 $\sum_{n+m}^i=\sum C_n^jC_m^{i-j}$ 然后， $\sum C_{a-1}^{i-1}C_b^i=\sum C_{a-1}^{a-i}C_b^i=C_{a+b-1}^a$

E

现在看写这个比刚D题性价比更高。。树状数组套线段树，时空 $O(q\log^2n)$

SGU 390 BZOJ 2063 我爸是李刚

发表于 2017-03-15 | 更新于 2018-06-17

Link

Solution

不能用区间减法做了。。因为最后总能剩下那么一点，就不满足区间减法了。。没办法，只好在计算的时候同时卡上界和下界了。先不考虑卡上界和下界，现在找一下独立的子问题：通用的 $f[len][i]$ 表示有 $len$ 位，最高位为 $i$ 的方案数还可行吗？似乎不行了，原因还是一样：最后剩下的那么一点点，导致子问题不是独立的了。那就加一维 $f[len][i][rem]$ 表示统计完了前两维 $< len,< i$ 的情况，剩下了一些数字数位和为 $rem$ ，能分的组数。然后似乎还不行：这个状态没有记录已经有的数位和，所以没法转移。那好说，注意到第二维表示成最高位的数字是意义不明(也许也可以做，但做法确实不显然)的，那就把第二维改成已经有的数位和。这样 $f[len][sum][rem]$ 表示前 $len$ 位的数位和为 $sum$ ，之前剩下的数位和为 $rem$ 能分出的组数，就可以计算了。注意要记录是否需要卡上下界，而且需要卡上下界的每种状态都是至多计算一次，不需要记忆化，如果记忆化了在BZOJ上就MLE了。因为两个界都卡的只会有第一层DFS计算，剩下的都是卡一边的。而卡一边的只能从 $len+1$ 的卡一边的转移过来。附 $l=1,r=10^{18}$ 的需要卡上下界的状态计数

c[1][0][0]<1,0>=1
c[2][0][0]<1,0>=1
c[3][0][0]<1,0>=1
c[4][0][0]<1,0>=1
c[5][0][0]<1,0>=1
c[6][0][0]<1,0>=1
c[7][0][0]<1,0>=1
c[8][0][0]<1,0>=1
c[9][0][0]<1,0>=1
c[10][0][0]<1,0>=1
c[11][0][0]<1,0>=1
c[12][0][0]<1,0>=1
c[13][0][0]<1,0>=1
c[14][0][0]<1,0>=1
c[15][0][0]<1,0>=1
c[16][0][0]<1,0>=1
c[17][0][0]<1,0>=1
c[18][0][0]<1,0>=1
c[1][1][483]<0,1>=1
c[2][1][483]<0,1>=1
c[3][1][483]<0,1>=1
c[4][1][483]<0,1>=1
c[5][1][483]<0,1>=1
c[6][1][483]<0,1>=1
c[7][1][483]<0,1>=1
c[8][1][483]<0,1>=1
c[9][1][483]<0,1>=1
c[10][1][483]<0,1>=1
c[11][1][483]<0,1>=1
c[12][1][483]<0,1>=1
c[13][1][483]<0,1>=1
c[14][1][483]<0,1>=1
c[15][1][483]<0,1>=1
c[16][1][483]<0,1>=1
c[17][1][483]<0,1>=1
c[18][1][483]<0,1>=1
c[19][0][0]<1,1>=1
126628280529273434

Tips

数位DP不只有区间减法，有可能需要一次算两边。

Code

#include "lucida"
int lbit[20],rbit[20];
int Convert(int64 x,int bit[]) {
	int len=0;
	for(;x;x/=10)
		bit[++len]=x%10;
	return len;
}
struct Node {
	int64 cnt,rem;
	Node():cnt(-1),rem(0){}
	Node(int64 cnt,int rem):cnt(cnt),rem(rem){}
	Node &operator +=(const Node &a) {
		cnt+=a.cnt;
		rem=a.rem;
		return *this;
	}
}f[21][171][1011];
int64 l,r,M;
Node DFS(int len,int sum,int rem,bool lm,bool rm) {
	//sum是数位之和9*18=162
	if(len==0)
		return (sum+rem>=M)?Node(1,0):Node(0,sum+rem);
	if(!lm && !rm && f[len][sum][rem].cnt!=-1)
		return f[len][sum][rem];
	Node res(0,rem);
	for(int i=(lm?lbit[len]:0),ei=(rm?rbit[len]:9);i<=ei;++i) 
		res+=DFS(len-1,sum+i,res.rem,lm && i==lbit[len],rm && i==rbit[len]);
	if(!lm && !rm) f[len][sum][rem]=res;
	return res;
}
int main() {
	freopen("input","r",stdin);
	is>>l>>r>>M;
	Convert(l,lbit);
	int len=Convert(r,rbit);
	int64 Ans=DFS(len,0,0,1,1).cnt;
	os<<Ans<<'\n';
	return 0;
}

Lucida

It's been a while.

222 日志

127 标签