【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;
}

【AtCoder】[Regular Contest 075 F] Mirrored

相关链接

题目传送门:http://arc075.contest.atcoder.jp/tasks/arc075_d

解题报告

之前PKUSC的时候考过$n + rev(n) = d$的版本
所以这一次把暴搜重新打一次就过了

Code

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

int *mth, *spj, a2[100], a1[100]; 

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;
}

LL DFS(LL res, LL l, LL r) {
	if (l <= r) {
		if (res == 0) {
			return l == r? 10: 1;
		} else {
			return 0;
		}
	} else {
		LL ret = 0, cur = l - r;
		l /= 10; r *= 10;
		for (int i = -9; i <= 9; i++) {
			if (abs(res - i * cur) < l * 11) {
				ret += mth[i] * DFS(res - i * cur, l, r);				
			}
		}
		return ret;
	}
}

int main() {
	mth = a1 + 50;
	spj = a2 + 50;
	for (int i = 0; i <= 9; i++) {
		for (int j = -9; j <= 0; j++) {
			mth[i + j]++;
		}
	}
	for (int i = 1; i <= 9; i++) {
		for (int j = -9; j <= 0; j++) {
			spj[i + j]++;
		}
	}
	LL ans = 0, D = -read();
	for (LL mx = 1e18; mx >= 10; mx /= 10) {
		LL delta = mx - 1;
		for (int i = -8; i <= 9; i++) {
			ans += spj[i] * DFS(D - i * delta, mx / 10, 10);
		}
	}
	cout<<ans<<endl;
	return 0;
}

【Codeforces 812E】Sagheer and Apple Tree

相关链接

题目传送门:http://codeforces.com/contest/812/problem/E
官方题解:http://codeforces.com/blog/entry/52318

解题报告

我们发现,如果操作同叶子结点的深度奇偶性不同的结点
那么对手总可以操作刚刚你操作的那些苹果

所以结果只与深度同叶子结点奇偶性相同的点有关
更进一步观察发现,实质上就是这些点组成的$NIM$游戏
于是乘一乘、加一加就好了

Code

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

const int N = 100009;
const int M = 10000009;

int n, prt, tot, dep[N], v[N], in[N];
int head[N], nxt[N], to[N], cnt[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;
}

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

void DFS(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		dep[to[i]] = dep[w] + 1;
		DFS(to[i]);
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i <= n; i++) {
		v[i] = read();
	}
	for (int i = 2; i <= n; i++) {
		AddEdge(read(), i);
	}
	DFS(1);
	for (int i = 2; i <= n; ++i) {
		if (in[i] == 1) {
			prt = (dep[i] & 1);
			break;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			ans ^= v[i];
		}
	}
	LL vout = 0;
	tot = n;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			cnt[v[i]]++;
			--tot;
		}
	}
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) != prt) {
			int tt = ans ^ v[i];
			if (tt < M) {
				vout += cnt[tt];
			}
		}
	}
	if (!ans) {
		vout += tot * (tot - 1ll) / 2;
		vout += (n - tot) * (n - tot - 1ll) / 2;
	}
	cout<<vout<<endl;
	return 0;
}

【Codeforces 802L】Send the Fool Further! (hard)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf

解题报告

这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$

Code

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

const int N = 100009;
const int M = 200009;
const int MOD = 1000000007;

int n, head[N], nxt[M], to[M], cost[M];
int a[N], b[N], fa[N], d[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 void AddEdge(int u, int v, int c) {
	static int E = 1; 
	d[u]++; d[v]++;
	cost[E + 1] = cost[E + 2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int REV(int x) {
	int ret = 1, t = MOD - 2;
	for (; t; x = (LL)x * x % MOD, t >>= 1) {
		if (t & 1) {
			ret = (LL)ret * x % MOD;
		}
	}
	return ret;
}

void solve(int w, int f) {
	if (d[w] > 1) {
		a[w] = -1;
		for (int i = head[w]; i; i = nxt[i]) {
			b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD;
			if (to[i] != f) {
				solve(to[i], w);
			}
		}
		if (w != f) {
			b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD;
			a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD;
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		AddEdge(u + 1, v + 1, read());
	}
	solve(1, 1);
	int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
	ans = (ans + MOD) % MOD;
	cout<<ans<<endl;
	return 0;
}

【Codeforces 802C】Heidi and Library (hard)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/C
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
消圈定理:https://blog.sengxian.com/algorithms/clearcircle

解题报告

被这题强制解锁了两个新姿势qwq

  1. 上下界最小费用流:
    直接按照上下界网络流一样建图,然后正常跑费用流
  2. 带负环的费用流
    应用消圈定理,强行将负环满流

然后考完之后发现脑残了
换一种建图方法就没有负环了_(:з」∠)_

Code

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

const int N = 5000000;
const int M = 200;
const int INF = 1e9;

int n,k,S,T,tot,SS,TT,ans,a[M],np[M],cc[M];
int head[N],nxt[N],to[N],flow[N],cost[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 int AddEdge(int u, int v, int c, int f) {
	static int E = 1;
    to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N],vis[N]; 
    queue<int> que; 
    public:
        inline void MaxFlow() {
        	while (clearCircle()); 
            for (int ff; ff = INF, SPFA();) {
            	for (int w = TT; w != SS; w = to[sur[w]^1]) {
					ff = min(ff, flow[sur[w]]);
				}
                for (int w = TT; w != SS; w = to[sur[w]^1]) {
					flow[sur[w]] -= ff;
					flow[sur[w]^1] += ff;
				}
				ans += dis[TT] * ff;
            }
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(SS); dis[SS] = 0;
               
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) {
							inq[to[i]] = 1;
							que.push(to[i]);
						}
                    }
                }
            }
            return dis[TT] < INF;
        }
        bool clearCircle() {
        	memset(dis, 0, sizeof(dis));
        	memset(vis, 0, sizeof(vis));
			for (int i = 1; i <= tot; ++i) { 
   	    		if (!vis[i] && DFS(i)) {
					return 1;   
				}
			}
			return 0;
    	}
    	bool DFS(int w) {
    		vis[w] = 1;
    		if (inq[w]) {
    			int cur = w;
    			do {
					flow[sur[cur]]--;
					flow[sur[cur]^1]++;
					ans += cost[sur[cur]];
					cur = to[sur[cur]];
				} while (cur != w);
				return 1;
			} else {
    			inq[w] = 1;
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
						dis[to[i]] = dis[w] + cost[i];
						sur[w] = i;
						if (DFS(to[i])) {
							inq[w] = 0;
							return 1;
						}
					}
				}
				inq[w] = 0;
				return 0;
			}
			
		}
}MCMF;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif 
	n = read(); k = read();
	S = tot = n + 4; T = n + 1;
	SS = n + 2; TT = n + 3; 
	AddEdge(T, S, 0, k); 
	AddEdge(S, 1, 0, INF);
	for (int i = 1; i <= n; i++) {
		np[i] = ++tot;
		AddEdge(np[i], i + 1, 0, INF);
		AddEdge(i, np[i], 0, INF);
		AddEdge(i, TT, 0, 1);
		AddEdge(SS, np[i], 0, 1);
		a[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		cc[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		ans += cc[a[i]];
		for (int j = i + 1; j <= n; j++) {
			if (a[i] == a[j]) {
				AddEdge(np[i], j, -cc[a[i]], 1);
				break;
			} 
		}
	}
	MCMF.MaxFlow();
	cout<<ans<<endl; 
	return 0;
}

【BZOJ 4881】[Lydsy2017年5月月赛] 线段游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4881
神犇题解:http://krydom.com/bzoj4881/

解题报告

不难发现,这就是一个二分图染色问题
那么我们首先需要判无解
分析题目我们可以发现,如果存在长度为$x+2$的奇环,那么一定存在长度为$x$的奇环
于是我们只需要判有没有长度为$3$的奇环,然后我们发现这就是三个递减的数,于是随便搞一搞就好
至于输出方案数,就是$2$的连通块个数次方

Code

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

const int N = 100009;
const int MOD = 998244353;

int n, p[N], mx[N], mn[N];
stack<int> stk; 

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();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	mx[1] = p[1];
	for (int i = 2; i <= n; i++) {
		mx[i] = max(mx[i - 1], p[i]);
	}
	mn[n] = p[n];
	for (int i = n - 1; i; i--) {
		mn[i] = min(mn[i + 1], p[i]);
	}
	for (int i = 2; i < n; i++) {
		if (mx[i - 1] > p[i] && p[i] > mn[i + 1]) {
			puts("0");
			exit(0);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (stk.empty() || stk.top() < p[i]) {
			stk.push(p[i]);
		} else {
			int tt = stk.top();
			for (; !stk.empty() && stk.top() > p[i]; stk.pop());
			stk.push(tt);
		}
	}
	int ans = 1;
	for (int i = 1; i <= (int)stk.size(); i++) {
		ans = (ans << 1) % MOD;
	}
	cout<<ans<<endl;
	return 0;
}

【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4886
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

我们把权值看做点,矩形看作边
不难发现一个大小为$n$连通块如果是树,那么最多选$n-1$个点
否则可以选完$n$个点

所以用并查集维护一下连通性之后
直接贪心即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 500009;
  
int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N]; 
LL 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 find(int x) {
    return x == fa[x]? x: fa[x] = find(fa[x]);
}
  
int main() {
    n = read();
    for (int i=1;i<=n;i++) {
        u[i] = val[++tot] = read(); 
        v[i] = val[++tot] = read();
        ans += u[i];
        ans += v[i];
    }
    sort(val+1, val+1+tot);
    tot = unique(val+1, val+1+tot) - val - 1;
    for (int i=1;i<=tot;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
    for (int i=1;i<=n;i++) {
        int x = lower_bound(val+1, val+1+tot, u[i]) - val;
        int y = lower_bound(val+1, val+1+tot, v[i]) - val;
        if (find(x) != find(y)) {
            sz[fa[y]] += sz[fa[x]];
            if (cir[fa[x]]) {
                cir[fa[y]] = 1;
            }
            fa[fa[x]] = fa[y];
        } else {
            cir[fa[x]] = 1;
        }
    } 
    for (int i=1;i<=tot;i++) {
        if (find(i) == i) {
            sz[i] -= (cir[i] ^ 1);
        }
    }
    for (int i=1,w=1;i<=n;i++,w++) {
        while (sz[find(w)] == 0) ++w;
        ans -= val[w]; 
        sz[fa[w]]--;
    }
    printf("%lld\n",ans);
    return 0;
}

【BZOJ 4883】[Lydsy2017年5月月赛] 棋盘上的守卫

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4883
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

把行和列看成点,格子看成边
那么一个$n$个点的连通块需要$n$条边
于是用$Kruskal$做一个基环树森林就可以了
时间复杂度:$O(nm \log nm)$

Code

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

const int N = 300000;

struct Edge{
	int u, v, c;
	bool operator < (const Edge &ee) const {
		return c < ee.c;
	}
}e[N];
int n, m, tot, cir[N], fa[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 find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			e[++tot].c = read();
			e[tot].u = i;
			e[tot].v = n + j;
		}
	}
	sort(e + 1, e + 1 + tot);
	for (int i = 1; i <= n + m; i++) {
		fa[i] = i;
	}
	LL ans = 0;
	for (int i = 1; i <= tot; i++) {
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (cir[fu] && cir[fv]) {
			continue;
		} else if (fu != fv) {
			fa[fv] = fu;
			cir[fu] |= cir[fv];
		} else if (!cir[fu]) {
			cir[fu] = 1;
		}
		ans += e[i].c;
	}
	printf("%lld\n", ans);
	return 0;
}

【BZOJ 4878】[Lydsy2017年5月月赛] 挑战NP-Hard

相关链接

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

解题报告

我们搞出$DFS$生成树
如果树高大于$k$,那么显然可以找出长度为$k$的简单路径
如果树高$\le k$的话,因为非树边一定是返祖边,所以把深度作为颜色就可以$k$染色了

Code

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

const int N = 1009;
const int M = 20009;

int n,m,k,E,head[N],nxt[M],to[M];
int DONE,fa[N],dep[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 void AddEdge(int u, int v) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f) {
	dep[w] = dep[f] + 1;
	fa[w] = f;
	if (dep[w] > k) {
		DONE = 1;
		printf("path ");
		for (; 1; w = fa[w]) {
			printf("%d ", w);
			if (w == fa[w]) {
				break;
			}
		}
		cout<<endl;
	} else {
		for (int i = head[w]; i && !DONE; i = nxt[i]) {
			if (!dep[to[i]]) {
				DFS(to[i], w);
			}
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		n = read(); m = read(); 
		k = read(); E = DONE = 0;
		for (int i = 1; i <= m; i++) {
			AddEdge(read(), read());
		}
		memset(dep, 0, sizeof(dep));
		for (int i = 1; i <= n && !DONE; ++i) {
			if (!dep[i]) {
				DFS(i, i);
			}
		}
		if (!DONE) {
			printf("color ");
			for (int i = 1; i <= n; ++i) {
				printf("%d ", dep[i]);
			}
			cout<<endl;
		}
	} 
	return 0;
}

【POJ 3922】A simple stone game

相关链接

题目传送门:http://poj.org/problem?id=3922
神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2012/12/19/2825539.html

解题报告

根据$k = 1$的情况,我们发现在二进制下,我们取走最低位的$1$,对手取不走较高位的$1$
所以如果不是二的整次幂,那么先手必胜

再来看看$k = 2$的情况
根据$HINT$我们把每个整数拆成若干个不同、不相邻的斐波那契数之和,表示成二进制状态
之后跟据$k = 1$时的推论,我们取走最低位的$1$,对手不能直接取走较高位的$1$

先在我们看我们依赖拆分数列的哪些性质:

存在一种拆分使得选中的项的任意相邻两项超过$k$倍

于是我们尝试构造拆分数列$a_i$
我们设$b_i$为$a_1 \to a_i$能拼出的极长的前缀长度
不难发现$a_i = b_{i-1}+1, b_i=a_i+b_j$,其中$j$尽可能大,且$a_j k < a_i$

于是这题就做完啦
似乎这个问题还是博弈论里的一个经典问题,叫”$k$倍动态减法问题”
似乎某年国家集训队论文里还提出了另外的算法,对于某些数据会更优

Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[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() {
	for (int t = 1, T = read(); t <= T; ++t) {
		n = read(); k = read();
		a[0] = b[0] = x = y = 0;
		while (a[x] < n) {
			a[x + 1] = b[x] + 1;
			for (++x; (LL)a[y + 1] * k < a[x]; ++y);
			b[x] = y? b[y] + a[x]: a[x];
		}
		if (a[x] == n) {
			printf("Case %d: lose\n", t);
		} else {
			int ans = 0;
			for (; n && x; --x) {
				if (n >= a[x]) {
					n -= a[x];
					ans = a[x];
				}
			}
			printf("Case %d: %d\n", t, ans);
		}
	}
	return 0;
}

【TopCoder SRM714】NAddOdd

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14408&rd=16883
神犇题解:http://codeforces.com/blog/entry/50602?#comment-358475

解题报告

设$f(x)=\sum\limits_{i=1}^{x}{g(k+i)}$
那么奇偶讨论,可以得到递推式$f(x)=(f(\frac{x-k}{2})+\frac{x}{2})+(f(\frac{x}{2})+x)$
于是递归算$f(\frac{x-k}{2})$,$\sum\limits_{i=\frac{x-k}{2}+1}^{\frac{x}{2}}{g(i)}$暴力算
时间复杂度:$O(k \log^2 n)$

Code

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

class NAddOdd {
    public:
    	long long solve(long long L, long long R, int K) {
			return Cal(R - K, K) - Cal(L - 1 - K, K);
   		}
   	private:
   		inline LL Cal(LL n, int k) {
			if (n <= 0) {
				return 0;
			} else {
				LL ret = Cal((n - k) >> 1, k) << 1;
				ret += n + (n >> 1);
				for (LL i=((n-k)>>1)+1;i*2<=n;i++) {
					ret += g(i + k, k);
				}
				return ret;
			}
		}
		inline int g(LL x, int k) {
			LL ret = 0, w = x;
			while (w > k) {
				++ret;
				w = (((w&1)? (w+k): (w>>1)));
			} 
			return ret;
		} 
};

【TopCoder SRM714】Salesman

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14120&rd=16883
神犇题解:http://codeforces.com/blog/entry/50602?#comment-358439

解题报告

设最终移动的范围为$[l,r]$
那么如果存在$r’ < r$且$sum_{l \to r’} \ge 0$,则$r’$优于$r$
所以我们可以枚举左端点,然后找到其对应的最优右端点

接下来就是区间内的路径规划问题
我们可以假设先走到左端点,那么剩下的东西的分配一定是尽量往左分配
这样就可以贪心了

Code

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

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

int pfx[N],delta[N],pos[N],nxt[N];

class Salesman {
    public:
    	int minMoves(vector<int> ppos, vector<int> ddelta) {
    	    int n = ppos.size();
    	    for (int i=1;i<=n;i++) {
				pos[i] = ppos[i - 1];
				delta[i] = ddelta[i - 1];
			}
			int ans = INF;
			ans = min(ans, solve(n));
			for (int l=1,r=n;l<r;l++,r--) {
				swap(pos[l], pos[r]);
				swap(delta[l], delta[r]);
			}
			for (int i=1;i<=n;i++) {
				pos[i] = -pos[i];
			}
			ans = min(ans, solve(n));
			return ans;
   		}
   	private:
   		inline int solve(int n) {
			int mn = INF, mx = -INF, ret = INF;
			for (int i=1;i<=n;i++) {
				pfx[i] = pfx[i-1] + delta[i];
				if (delta[i] < 0) {
					mx = max(mx, i);
					mn = min(mn, i);
				}
			}   
			for (int i=n,j=n;i;i--) {
				if (delta[i] < 0) {
					j = i;
				}
				nxt[i] = j;
			}
			if (mn == INF) {
				return 0;
			}
			for (int l=1;l<=mn;l++) {
				for (int r=mx;r<=n;r++) {
					if (pfx[r] - pfx[l - 1] >= 0) {
						ret = min(ret, cal(l, r));	
						break;
					}
				}
			}
			return ret;
		}
		inline int cal(int l, int r) {
			int ret = pos[r] - pos[l] + abs(pos[l]), ans = INF;
			int cry = 0, ned = 0, ptn = 0;
			for (int i=l;i<=r;i++) {
				if (delta[i] >= 0) {
					cry += delta[i];
					if (cry >= ned && ned) {
						cry -= ned;
						ret += max(0, pos[i] - ptn) << 1;
						ned = 0;
					}
				} else if (delta[i] < 0) {
					if (!ned && cry >= -delta[i]) {
						cry += delta[i];
					} else {
						if (!ned) {
							ptn = max(ptn, pos[i]);
						} 
						ned -= delta[i];
					}
				}
				
				ans = min(ans, ret + max(0, pos[r] - (ned? ptn: pos[nxt[i+1]])));
			}
			return ans;
		}
};

【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 4829】[HNOI2017] 队长快跑

相关链接

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

解题报告

首先我们可以把每一条射线等价为一条垂直于$x$轴的射线
此时问题变成了$Flappy \ Bird$那样

然后我们发现问题就是上下两个凸包互相卡
然后用两个队列瞎搞搞就好了

另外这题精度巨坑
之前用$long double$各种判$EPS$还是挂成狗
所以建议安心用$long long$

Code

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

const int N = 1000009;
const int LEN = 1e4;
const double PI = acos(-1);

int n,tot,st[N],head[2],tail[2];
struct Point{
	LL x,y; Point *nxt; int pt;
	inline Point() {}
	inline Point(LL a, LL b):x(a),y(b) {}
	inline Point operator + (const Point &P) {return Point(x + P.x, y + P.y);}
	inline Point operator - (const Point &P) {return Point(x - P.x, y - P.y);}
	inline Point operator * (double t) {return Point(x * t, y * t);}
	inline LL operator ^ (const Point &P) {return x * P.x + y * P.y;}
	inline LL operator * (const Point &P) {return x * P.y - y * P.x;}
	inline bool operator < (const Point &P) const {return x < P.x;}
	inline bool operator != (const Point &P) const {return x != P.x || y != P.y;}
	inline double len() {return sqrt(x * x + y * y);}
}ss,tt,p[N],vout[N],*que[2][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 NotInRange(double div, double a, double b) {
	if (div >= -PI / 2 && div <= PI / 2) return (a < div || a > PI / 2) && (b < div || b > PI / 2);
	else if (div < 0) return a > div && a < PI / 2 && b > div && b < PI / 2;
	else return (a > div || a < PI / 2) && (b > div || b < PI / 2);
}

int main() {
	n = read(); tt.x = read(); tt.y = read();
	for (int i=1;i<=n;i++) {
		p[i].x = read(); p[i].y = read();
		double r1,r2,r3; scanf("%lf",&r1);
		r2 = atan2((ss-p[i]).y, (ss-p[i]).x);
		r3 = atan2((tt-p[i]).y, (tt-p[i]).x);
		if (NotInRange(r1, r2, r3)) p[i].pt = 1; //射线朝上 
		else p[i].pt = 0; //射线朝下 
	}
	sort(p+1, p+1+n);
	int lim = n; n = 0;
	for (int i=1;i<=lim;i++) {
		if (p[i].x < ss.x || tt.x < p[i].x) continue;
		p[++n] = p[i];
	} 
	p[++n] = tt; 
	que[0][tail[0] = head[0] = 1] = &ss; 
	que[1][tail[1] = head[1] = 1] = &ss;
	for (int i=1;i<=n;i++) {
		int &h1 = head[p[i].pt], &h2 = head[p[i].pt ^ 1], &t1 = tail[p[i].pt], &t2 = tail[p[i].pt ^ 1];
		Point **a1 = que[p[i].pt], **a2 = que[p[i].pt ^ 1];
		if (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
			while (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
				++h2;
			}
			p[i].nxt = a2[h2];
			a1[h1 = t1 = t1 + 1] = a2[h2];
		} else {
			while (h1 < t1 && ((p[i] - *a1[t1 - 1]) * (*a1[t1] - *a1[t1 - 1])) * (p[i].pt==1? 1: -1) >= 0) {
				--t1;
			}
			p[i].nxt = a1[t1];
		}
		a1[++t1] = &p[i];
	} 
	double ans = 0; 
	for (Point *cur=&p[n],*last;*cur!=ss;) {
		last = cur; cur = cur->nxt;
		ans += (*cur - *last).len(); 
	} 
	printf("%.10lf\n",ans);
	return 0;
}

【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 3622】已经没有什么好害怕的了

相关链接

解题报告:http://www.lydsy.com/JudgeOnline/problem.php?id=3622

解题报告

恰好有$k$个条件满足,这不就是广义容斥原理吗?
不知道广义容斥原理的同学可以去找$sengxian$要他的$PDF$看哦!

知道广义容斥原理的同学,这题难点就是求$\alpha(i)$
设$f_{i,j}$表示考虑了前$i$个糖果,至少有$j$个糖果符合条件的方案数
那么$\alpha(i)=f_{n,i} \cdot (n-i)!$

于是先$O(n^2)$DP出$\alpha(i)$
然后根据广义容斥原理$O(n)$推出$\beta(k)$就可以了
总时间复杂度:$O(n^2)$

Code

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

const int N = 2009;
const int MOD = 1000000009;

int n,K,a[N],b[N],sum[N],fac[N],alpha[N],f[N][N],C[N][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(); K = read();
	if ((n + K) & 1) {
		puts("0");
		exit(0);
	} 
	K = n + K >> 1; 
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	sort(a+1, a+1+n);
	for (int i=1;i<=n;i++) {
		b[i] = read();
	} 
	sort(b+1, b+1+n);
	for (int i=1,j=0;i<=n;i++) {
		for (;j < n && b[j+1] < a[i];++j);
		sum[i] = j;
	}
	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] + C[i-1][j-1]) % MOD;
		}
	}
	fac[0] = 1;
	for (int i=1;i<=n;i++) {
		fac[i] = fac[i-1] * (LL)i % MOD; 
	}
	f[0][0] = 1;
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=i;j++) {
			f[i][j] = (f[i-1][j] + (j?f[i-1][j-1] * max(0ll, (sum[i] - j + 1ll)):0ll)) % MOD;
		}
	}
	for (int i=0;i<=n;i++) {
		alpha[i] = (LL)f[n][i] * fac[n - i] % MOD;
	}
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		ans = (ans + (LL)alpha[i] * C[i][K] * t) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}