【Codeforces 814E】An unavoidable detour for home

相关链接

题目传送门:http://codeforces.com/contest/814/problem/E
官方题解:http://codeforces.com/blog/entry/52449
神犇题解Ⅰ:https://loj.ac/article/37
神犇题解Ⅱ:http://kczno1.blog.uoj.ac/blog/2660

解题报告

我们考虑分层图的话
那每一层的一个点一定会与上一层的某个点相连,剩下的度数只能层内消化
又因为这题对祖先有严格的限制,所以每一层都是原序列中连续的一段
于是$O(n^5)$的暴力$DP$就可以写了

至于$O(n^3)$的$DP$,就是$DP$套$DP$
预处理出转移的$buf$,然后转移的时候直接乘就好了
但这个预处理的时候要讨论很多情况啊,反正我自己考场上是想不出来的_(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 52;
const int MOD = 1000000007;
const int REV2 = 500000004;

int n, f[N][N], s2[N], s3[N], buf[N][N][N], C[N][N], prm[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read();
	f[read() + 1][1] = 1;
	for (int i = 2; i <= n; i++) {
		s2[i] = s2[i - 1];
		s3[i] = s3[i - 1];
		if (read() == 2) {
			s2[i]++;
		} else {
			s3[i]++;
		}
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	prm[2] = 1;
	for (int i = 3; i <= n; i++) {
		prm[i] = REV2;
		for (int j = 2; j < i; j++) {
			prm[i] = (LL)prm[i] * j % MOD;
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (i == 0 && j == 0 && k == 0) {
					buf[i][j][k] = 1;
				} else if (i == 0 && j == 0) {
					for (int l = 2; l < k; l++) {
						(buf[i][j][k] += ((LL)buf[i][j][k - 1 - l] * C[k - 1][l] % MOD) * prm[l + 1] % MOD) %= MOD;
					}
				} else if (i == 0) {
					buf[i][j][k] = j > 1? (LL)(j - 1) * buf[i][j - 2][k] % MOD: 0;
					(buf[i][j][k] += k? (LL)k * buf[i][j][k - 1] % MOD: 0) %= MOD;
				} else {
					buf[i][j][k] = j? (LL)j * buf[i - 1][j - 1][k] % MOD: 0;
					(buf[i][j][k] += k? (LL)k * buf[i - 1][j + 1][k - 1] % MOD: 0) % MOD;
				} 
			}
		}
	} 
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			if (f[i][j]) {
				int t2 = s2[i] - s2[j];
				int t3 = s3[i] - s3[j];
				for (int k = i + 1; k <= n; k++) {
					f[k][i] = (f[k][i] + (LL)f[i][j] * buf[k - i][t2][t3]) % MOD;
				}
			}
		}
	} 
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = (ans + (LL)f[n][i] * buf[0][s2[n] - s2[i]][s3[n] - s3[i]]) % MOD;
	}
	cout<<ans<<endl;
	return 0;
}

【Codeforces 799D】Field expansion

相关链接

题目传送门:http://codeforces.com/contest/799/problem/D

解题报告

不难发现,至多只会使用$O(2 \log 10^5)$个物品
于是定义$f_i$表示长为$i$时,宽最多为多少
暴力转移即可,时间复杂度:$O(10^5 \log 10^5)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int INF = 1e9;

int n,v[N],f[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline bool cmp(int a, int b) {
	return a > b;
}

inline int solve(int a, int b, int h, int w) {
	memset(f, 0, sizeof(f));
	f[min(h, a)] = min(b, w);
	int ans = 1;
	for (int j=1;j<=n;j++,ans++) {
		for (int i=a;i;i--) {
			if (f[i]) {
				int tt = min((LL)a, (LL)i * v[j]);
				f[tt] = max(f[tt], f[i]);
				if (tt == a && f[i] == b) {
					return ans;
				}
				tt = min((LL)b, (LL)f[i] * v[j]);
				f[i] = tt;
				if (i == a && tt == b) {
					return ans;
				}
			}
		}
	}
	return INF;
}

int main() {
	int a = read(), b = read();
	int h = read(), w = read();
	n = read();
	for (int i=1;i<=n;i++) {
		v[i] = read();
	}
	sort(v+1, v+1+n, cmp);
	n = min(n, 34);
	if ((h >= a && w >= b) || (h >= b && w >= a)) {
		puts("0");
		exit(0);
	}
	int ans1 = solve(a, b, h, w);
	int ans2 = solve(a, b, w, h);
	if (ans1 >= INF && ans2 >= INF) {
		puts("-1");
	} else {
		printf("%d\n",min(ans1, ans2));
	}
	return 0;
}

【TopCoder SRM713】CoinsQuery

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14572&rd=16882

题目大意

给$n(n \le 100)$类物品,第$i$类物品重量为$w_i(w_i \le 100)$,价值为$v_i(v_i \le 10^9)$,数量无限
给定$m(m \le 100)$个询问,第$i$询问请你回答总重量恰好为$q_i(q_i \le 10^9)$的物品,价值和最大为多少
你还需要求出使价值最大的方案数是多少(同类物品视作一样,摆放顺序不同算不同)

解题报告

规定每个物品重量不超过$100$那么我们就可以矩乘
但有一个问题:我们不仅要让价值最大,还要求方案数

但类比倍增Floyd:在一定条件,矩乘重载运算符之后仍然满足结合律
比如说这个题,我们可以:

重载加法为:两种方案取最优
重载乘法为:将两种方案拼起来(方案数相乘,价值相加)

然后直接做是$O(m n^3 \log n)$的,会在第$21$个点$TLE$
于是我们预处理转移矩阵的幂次,然后对于每个询问就是向量与矩阵相乘,单次复杂度是$O(n^2)$的
于是总的时间复杂度优化到:$O(m n^2 \log n + n^3 \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 101;

struct Data{
	LL val,chs;
	inline Data() {val = chs = -1;}
	inline Data(LL a, LL b):val(a),chs(b) {}
	inline Data operator + (const Data &D) {
		if (chs == -1 || D.chs == -1) {
			return chs != -1? *this: D;
		} else {
			Data ret(max(val, D.val), 0);
			(ret.chs += (val == ret.val? chs: 0)) %= MOD;
			(ret.chs += (D.val == ret.val? D.chs: 0)) %= MOD;
			return ret;
		}
	}
	inline Data operator * (const Data &D) {
		if (!~chs || !~D.chs) return Data(-1, -1);
		return Data(val + D.val, chs * D.chs % MOD);
	}
}e(0,1);
struct Matrix{
	Data a[N][N]; int x,y;
	inline Matrix() {x = y = 0;}
	inline Matrix(int X, int Y):x(X),y(Y) {}
	inline Matrix operator * (const Matrix &M) {
		Matrix ret(M.x, y);
		for (int i=1;i<=M.x;i++) {
			for (int k=1;k<=x;k++) {
				for (int j=1;j<=y;j++) {
					ret.a[i][j] = ret.a[i][j] + (a[k][j] * M.a[i][k]);
				}
			}
		}
		return ret;
	}
}tra[32];

class CoinsQuery {
    public:
    	vector<LL> query(vector<int> w, vector<int> v, vector<int> query) {
    	    int m = query.size(), n = w.size();
			tra[0].x = tra[0].y = 100;
    	    for (int i=0;i<n;i++) {
				tra[0].a[w[i]][1] = tra[0].a[w[i]][1] + Data(v[i], 1);
			}
			for (int i=2;i<=100;i++) {
				tra[0].a[i-1][i] = e;
			}
			for (int i=1;i<=30;i++) {
				tra[i] = tra[i-1] * tra[i-1];
			}
    	    
			vector<LL> ret;
    	    for (int tt=0;tt<m;tt++) {
				Matrix ans(100, 1);
				ans.a[1][1] = e;
				int cur = query[tt];
				for (int i=0;cur;cur>>=1,++i) {
					if (cur & 1) {
						ans = ans * tra[i];
					}
				}
				ret.push_back(ans.a[1][1].val);
				ret.push_back(ans.a[1][1].chs);
			}
    	    return ret;
   		}
   	private:
};

【BZOJ 4828】[HNOI2017] 大佬

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4828

解题报告

先$DP$出最多可以有多少天不做题
然后我们发现两次$D$人其实是独立的
于是我们再$DP$出攻击达到$x$的最小天数

最后回答每个询问的时候
用个双指针扫一扫

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 109;
const int M = 930000;

int n,m,mc,tot,MX,ispri[N],w[N],a[N],f[N][N];
pair<int,int> itm[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void DFS(int t, LL sum) {
	if (t > MX) return;
	else {
		DFS(t + 1, sum);
		if (ispri[t]) {
			for (;sum*=t,sum<=1e8;) {
				itm[++tot].first = sum;
				DFS(t + 1, sum);
			}
		}
	}
}

inline int cal(int x) {
	int ret = x + 1;
	for (int i=min(MX,x-1),cnt,tmp;i;i--) {
		if (x % i) continue;
		cnt = i + 1; tmp = x;
		for (int j=i;j>1&&tmp>1;j--) {
			while (tmp % j == 0) {
				tmp /= j;
				++cnt;
			}
		}
		if (tmp == 1) {
			ret = min(ret, cnt);
		} else {
			break;
		}
	}
	return ret;
}

int main() {
	n = read(); m = read(); mc = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	for (int j=1;j<=n;j++) {
		w[j] = read();
	}
	//DP最多空出来的天数 
	memset(f, -1, sizeof(f));
	f[1][mc] = 0;
	for (int i=1;i<=n;i++) {
		for (int j=a[i];j<=mc;j++) {
			if (f[i][j] == -1) continue;
			int t1 = min(j - a[i] + w[i], mc), t2 = j - a[i];
			if (t1 >= 0) {
				f[i + 1][t1] = max(f[i + 1][t1], f[i][j]);
			}
			if (t2 >= 0) {
				f[i + 1][t2] = max(f[i + 1][t2], f[i][j] + 1);
			}
		}
	}
	MX = -1; 
	for (int j=2;j<=n+1;j++) {
		for (int i=0;i<=mc;i++) {
			MX = max(MX, f[j][i]);
		}
	} 
	//搞出每一个物品的最小花费 
	for (int j=2;j<=100;j++) {
		ispri[j] = 1;
		for (int i=2;i*i<=j;i++) {
			if (j % i == 0) {
				ispri[j] = 0;
			}
		}
	}
	DFS(1, 1); 
	for (int i=1;i<=tot;i++) {
		itm[i].second = cal(itm[i].first);
	}
	itm[++tot] = make_pair(0, 0);
	sort(itm+1, itm+1+tot);
	//对于每个询问用一个双端队列
	for (int tt=1;tt<=m;tt++) {
		int C = read(), ans = 0;
		for (int i=tot,pfx=1,cur=-1e9;i;i--) {
			while (pfx <= tot && itm[pfx].first <= C - itm[i].first) {
				cur = max(cur, itm[pfx].first - itm[pfx].second);
				pfx++;
			}
			if (cur + itm[i].first - itm[i].second >= C - MX) {
				ans = 1; 
				break;
			}
		}
		printf("%d\n",ans);
	} 
	return 0;
}

【BZOJ 4861】[BeiJing2017] 魔法咒语

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4861

解题报告

对于$L \le 100$的情况,我们定义$f_{i,j}$表示长度为$i$,在$ac$自动机上匹配到点$j$的答案
然后暴力转移就可以了,时间复杂度:$O(10^4L)$

对于其他的点,我们构造转移矩阵,用矩阵快速幂来优化
至于如何把长度为$2$的和为$1$的给统一起来?我们可以加一个点缓存一下
时间复杂度:$O(200^3 \log L)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;

int n,m,L,len[109];
char s1[109][109],s2[109][109];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class AC_Automaton{
	int cnt,ch[109][26],vis[109],fail[109];
	vector<int> G[109];
	queue<int> que;
	public:
		inline AC_Automaton() {
			cnt=1;
		}
		inline void insert(char *s) {
			int l = strlen(s + 1), w = 1;
			for (int i=1;i<=l;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			}
			vis[w] = 1;
		}
		inline void build() {
			for (int i=0;i<26;i++) {
				if (!ch[1][i]) ch[1][i] = 1;
				else fail[ch[1][i]] = 1, que.push(ch[1][i]);
			}
			while (!que.empty()) { 
				int w = que.front(); que.pop(); 
				G[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i] && ch[w][i] != 1) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else {
						ch[w][i] = ch[fail[w]][i];
					}
				}
			} 
			DFS(1, 0);
		}
		inline int size() {
			return cnt;
		}
		inline int MOVE(int w, int j) {
			if (vis[j]) return -1;
			for (int i=1;i<=len[w];i++) {
				j = ch[j][s1[w][i]-'a'];
				if (vis[j]) return -1;
			}
			return j;
		}
	private:
		void DFS(int w, int t) {
			t |= vis[w];
			if (t) vis[w] = 1; 
			for (int i=G[w].size()-1;~i;i--) {
				if (G[w][i] != i) { 
					DFS(G[w][i], t);
				}
			}
		}
}ac;

namespace SUBTASK_ONE{
	int f[109][109],tot,ans;
	int tra[109][109];
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); 
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=ac.size();j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		f[0][1] = 1;
		for (int i=0;i<L;i++) {
			for (int j=1;j<=ac.size();j++) {
				if (f[i][j]) {
					for (int k=1,t1,t2;k<=n;k++) {
						if ((t1=tra[j][k]) != -1 && (t2=i + len[k]) <= L) {
							f[t2][t1] = (f[t2][t1] + f[i][j]) % MOD; 
						}
					}
				}
			}
		}
		for (int i=1;i<=ac.size();i++) {
			ans = (ans + f[L][i]) % MOD;
		}
		printf("%d\n",ans);
	} 
};

namespace SUBTASK_TWO{
	int sz,tot,tra[109][109*109+109];
	struct Matrix{
		int a[209][209];
		inline Matrix() {
			memset(a,0,sizeof(a));
		}
		inline Matrix(int x) {
			memset(a,0,sizeof(a));
			for (int i=1;i<=sz;i++) a[i][i] = x;
		}
		inline Matrix operator * (const Matrix &M) {
			Matrix ret;
			for (int i=1;i<=sz;i++) {
				for (int j=1;j<=sz;j++) {
					for (int k=1;k<=sz;k++) {
						ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * M.a[i][k]) % MOD;	
					}
				}
			}
			return ret;
		}
		inline Matrix operator ^ (int t) {
			Matrix ret(1),tmp;
			for (int i=1;i<=sz;i++) {
				memcpy(tmp.a[i],a[i],sizeof(a[i]));
			}
			for (;t;t>>=1,tmp=tmp*tmp) {
				if (t&1) ret = ret * tmp;
			}
			return ret;
		}
		inline void init() {
			memset(a,0,sizeof(a));
		}
	}ans,trans;
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); sz = ac.size();
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=sz;j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		ans.a[1][1] = 1; int ori = sz; 
		for (int i=1;i<=ori;i++) trans.a[i][++sz]++;
		for (int i=1;i<=ori;i++) {
			for (int j=1;j<=n;j++) {
				if (!tra[i][j]) continue;
				if (len[j] == 1) ++trans.a[tra[i][j]][i];
				else trans.a[tra[i][j]+ori][i]++;
			}
		}
		trans = trans ^ L;
		ans = ans * trans;
		int vout = 0;
		for (int i=1;i<=ori;i++) vout = (vout + ans.a[i][1]) % MOD;
		cout<<vout<<endl;
	}
};

int main() {
	n = read(); m = read(); L = read();
	if (L <= 100) {
		SUBTASK_ONE::solve();
	} else {
		SUBTASK_TWO::solve();
	}
	return 0;
}

【BZOJ 3612】[HEOI2014] 平衡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3612
神犇题解:http://blog.csdn.net/Vmurder/article/details/42551603

解题报告

读题后我们发现需要求解这么一个问题:

用$k$个不同的数,来凑成$n$的方案数

这个看起来只能$O(kn^2)$来做$DP$
但我们可以将其优化到$O(nk)$
具体来说,考虑所有$k$个数,一起加或一起减
这样的话,我们就可以不用枚举新加入答案集合的数是哪一个了

回到原题,我们枚举左右两边取出来的重量,和左边用了几块橡皮
然后总的复杂度主要还是在$DP$那一块,复杂度是:$O(k^2n)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 11;

int n,K,MOD,f[N][M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read(),ans;ans=0,T;T--) {
		n = read(); K = read(); MOD = read();
		memset(f,0,sizeof(f)); f[0][0] = 1;
		for (int i=1,lim=n*K;i<=lim;i++) {
			for (int k=1,LIM=min(i,K);k<=LIM;k++) {
				f[i][k] = (f[i-k][k] + f[i-k][k-1]) % MOD;
				if (i > n) f[i][k] = (f[i][k] - f[i-(n+1)][k-1]) % MOD;
			}
		}
		for (int i=0,lim=n*K;i<=lim;i++) {
			for (int k=0;k<K;k++) {
				ans = (ans + (LL)f[i][k] * f[i][K-k]) % MOD;
				ans = (ans + (LL)f[i][k] * f[i][K-k-1]) % MOD;
			}
		}
		printf("%d\n",(ans+MOD)%MOD);
	}
	return 0;
}

【Codeforces 800C】Vulnerable Kerbals

相关链接

题目传送门:http://codeforces.com/contest/800/problem/C

解题报告

写一写发现前缀积与$m$的$\gcd$是一个递增的关系,依次为倍数
于是我们将$0 \sim m-1$按照与$m$的$\gcd$分类
然后就是在拓扑图上搞一搞$DP$,输出的时候用拓展欧几里得求一发逆元
总的时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000;
const int M = 10000;

int n,m,tot,ans,vis[N],id[N],in[M],num[M];
int head[M],nxt[N],to[N],f[M],itr[M];
vector<int> que[M],vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int gcd(int a, int b) {
	return b? gcd(b, a%b): a;
}

inline void AddEdge(int u, int v) {
	static int E = 1; in[u]++; 
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void solve(int w) { 
	f[w] = que[w].size() + (itr[w]?f[itr[w]]:0);
	ans = max(ans, f[w]); 
	for (int i=head[w];i;i=nxt[i]) {
		if (f[w] > f[itr[to[i]]]) itr[to[i]] = w;
		if (--in[to[i]] == 0) solve(to[i]);
	}
}

void exgcd(int a, int b, LL &x, LL &y) {
	if (b) {exgcd(b, a%b, y, x); y -= a / b * x;}
	else {x = 1; y = 0;}
}

inline int REV(int a, int z) {
	int tmp = gcd(a, m), b; LL x, y; 
	a /= tmp; z /= tmp; b = m / tmp;
	exgcd(a, b, x, y);
	return x * z % m;
}

void print(int w, int v) {
	for (int i=0;i<=que[w].size()-1;i++) {
		int nv = que[w][i], rev = REV(v, nv);
		vout.push_back((rev+m)%m); v = nv;
	}
	if (itr[w]) print(itr[w], v);
}

int main() {
	n = read(); m = read();
	for (int i=1;i<=n;i++) vis[read()] = 1;
	for (int i=1;i<m;i++) if (!vis[i]) {
		int tmp = gcd(m, i); 
		if (!id[tmp]) id[tmp] = ++tot, num[tot] = tmp;
		que[id[tmp]].push_back(i);
	}
	for (int i=1;i<=tot;i++) {
		for (int j=1;j<=tot;j++) {
			if (num[j] > num[i] && num[j] % num[i] == 0) {
				AddEdge(i, j); 
			}
		}
	}
	for (int i=1;i<=tot;i++) if (!in[i]) solve(i);
	for (int i=1;i<=tot;i++) if (f[i] == ans) {print(i, 1); break;}
	if (!vis[0]) vout.push_back(0); cout<<vout.size()<<endl;
	for (int i=0;i<=vout.size()-1;i++) printf("%d ",vout[i]); 
	return 0;
}

【HDU 4624】Endless Spin

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4624
神犇题解Ⅰ:http://www.cnblogs.com/chanme/p/4869377.html
神犇题解Ⅱ:http://blog.csdn.net/beginendzrq/article/details/51331954

解题报告

我们设$f_i$为染色$i$次后还有球没有被染色的概率
那么我们的答案$ans$为: $\sum\limits_{i = 0}^\infty {{f_i}} $

现在考虑如何求$f_i$,我们先来$O(2^n)$暴力容斥
具体来讲,我们枚举染色$i$次后还剩下哪些球为白色
设还有$k$个球为白色,这$k$个球位置分别为$v_1 \sim v_k$
那么单次染色的区间不能包含这$k$个位置,设合法的方案数为$A$
那么单次染色符合条件的概率$P=\frac{A}{\frac{n(n-1)}{2}}$
那么$i$次都符合要求的概率就是$P^i$
于是对于$f_i$来讲,贡献为$P^i \cdot (-1)^{k-1}$
这种情况对于答案$ans$的贡献为$(-1)^{k-1}\sum\limits_{i=0}^{\infty}{P^i}=\frac{(-1)^{k-1}}{1-P}$

现在考虑优化容斥的过程
我们发现每一种具体的方案对于答案的贡献只与剩余球的数量的奇偶性和$A$有关
于是我们可以搞一个状态为$O(n^4)$,转移为$O(1)$的DP来优化容斥

Code

这份代码在我本地跑出来是对的,但交上去就wa
于是只能打了一份表交上去:http://paste.ubuntu.com/24448347/

#include<bits/stdc++.h>
#define LL long long
#define LDB __float128
using namespace std;

const int N = 51;
const int M = N * N;

int n,ww,pp;
LL f[2][N][M][2]; 
LDB ans;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read();T;T--) {
		ans = ww = 0; pp = 1;
		memset(f,0,sizeof(f));
		f[pp][0][0][0] = 1;
		n = read();
		for (int i=0;i<n;i++,ww^=1,pp^=1) { 
			memset(f[ww],0,sizeof(f[ww]));
			for (int j=0;j<=i;j++) {
				for (int k=i*i;~k;k--) {
					for (int p=0;p<=1;p++) {
						if (f[pp][j][k][p]) {
							f[ww][0][k+j*(j+1)/2][p^(j&1)] += f[pp][j][k][p];
							f[ww][j+1][k][p] += f[pp][j][k][p]; 
						}
					}
				}
			}
		}
		for (int j=0;j<=n;j++) {
			for (int k=n*n;~k;k--) {
				for (int p=0;p<=1;p++) {
					if (!f[pp][j][k][p]) continue;
					int v = k + j * (j + 1) / 2, t = p ^ (j & 1);
					LDB tmp = ((v < n * (n + 1) / 2)? ((LDB)v / (n * (n + 1) / 2 - v)): 0);
					if ((n-t)&1) ans += tmp * f[pp][j][k][p];
					else ans -= tmp * f[pp][j][k][p];
				}
			}
		}
		ans += 1; 
		printf("%.15Lf\n",(long double)ans);
	}
	return 0;
}

相关拓展

当然这题还可以改成:如果染到$k$个球都为黑色了就停止,询问停止时的期望步数
例题可以参考:凯旋三兵

【BZOJ 3711】[PA2014] Druzyny

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3711
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/4654215.html
神犇题解Ⅱ:http://blog.csdn.net/u010600261/article/details/54917569

解题报告

去膜了题解,好神啊!
本题一个区间要同时受$c_i,d_i$的限制

于是我们先只考虑$d_i$的限制
那么对于某一个区间的右端点$i$来讲,设合法的左端点$\in [g_i,i)$
至于$g_i$怎么求?搞一个队列就可以了?或者二分也是可以的
另外还需要注意一点:$g_i$是单调递增的

现在我们再来考虑$c_i$的限制,我们使用分治来解决
在$solve(l,r)$的时候,我们找出$c_i$最大的那个点$k$,然后递归下去
在合并上来的时候,我们就只需要考虑$[l,k-1]$对于$[k,r]$的贡献了
更进一步:因为$c_k$是$[l,r]$中最大的那个,所以对于此时所有的转移,$c_i$的限制均只需要考虑$c_k$
那么此时对于$i \in [k,r]$来讲,其合法的左端点$j \in [max(l,g_i),min(k-1,i-c_k)]$
因为$g_i$单调递增,所以我们对于$[k,r]$从左到右分四段考虑:

  1. $g_i \le l$且$i-c_k \le k-1$
    我们的首先我们肯定可以使用线段树来更新
    但更进一步,对于这一类点,我们只需要在查询第一个点时使用线段树就可以了
    因为这是一个前缀,之后$i$每向右移一位,合法的$j$也最多增加$1$
    不难发现,总的暴力操作次数不大于左右区间中较小的一段
    时间复杂度:$O(\log + \min(r-k+1,k-l))$
  2. $g_i \le l$且$k-1 < i-c_k$
    对于这些点,我们查询的是整个左区间
    我们整体查一次,然后一起更新就可以了
    时间复杂度:$O(\log n)$
  3. $l < g_i < k$
    对于这些点,我们查询的是左区间的一个后缀,我们直接在线段树上查就好
    考虑所有会影响到$i$的$solve$,它们的左区间一定没有交集
    也就是说只会有一个$solve$的左区间包含$g_i$
    于是对于每一个$i$,在整个算法中只会被查询一次
    所以这部分复杂度是$O(n \log n)$的,且不需要考虑到分治的复杂度中去
  4. $g_i \le k$
    直接不管就好

现在我们来分析分治的复杂度:$T(a+b)=T(a)+T(b)+min(a,b)+\log n$
我们发现这和启发式合并一样,于是复杂度是$O(n \log n)$的
在算上第三类更新的复杂度,总时间复杂度仍然为$O(n \log n)$

值得一提的是,这种与最值相关的问题使用分治来解决已经多次出现
比如HDU 5575,一定要引起重视啊

【BZOJ 3482】[COCI2013] hiperprostor

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解:http://www.cnblogs.com/clrs97/p/4675155.html

解题报告

我们发现一条路径的长度为$ax+b$,是一条直线的形式
那么我们如果求出所有直线的凸包,那么就可以$O(n)$计算答案了

现在考虑如何搞出凸包:

若两条直线的斜率相等,那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点,斜率为$j$,的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来,之后我们显然可以$O(n)$构造出凸包了

有了凸包后,每一条线段的贡献就是一个等差数列,这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$