Tag: 基础知识

相关链接

题目传送门：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;
}

相关链接

解题报告：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;
}

相关链接

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

题目大意

给定$n(n \le 10^9)$，问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$，我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话，贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小，所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4710
神犇题解：http://www.cnblogs.com/candy99/p/6616858.html

解题报告

先不考虑每个人至少一个的限制条件
那么我们可以将每一类物品分别考虑，用一个插板法就可以解决问题

现在考虑每一个人至少一个的限制
我们可以大力容斥一波！

于是总的时间复杂度就是：$O(nm)$

Code

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

const int N = 2009;
const int MOD = 1000000007;

int n,m,ans,a[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;
}

inline int cal(int x) {
	int ret = C[x][n];
	for (int i=1;i<=m;i++) {
		ret = (LL)ret * C[n-x-1][a[i]+n-x-1] % MOD;
	}
	return ret;
}

int main() {
	n = read(); m = read(); 
	C[0][0] = 1;
	for (int i=1;i<N;i++) {
		C[0][i] = 1;
		for (int j=1;j<N;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	}
	for (int i=1;i<=m;i++) a[i] = read();
	for (int i=0;i<n;i++) {
		if (i&1) ans = (ans - cal(i)) % MOD;
		else ans = (ans + cal(i)) % MOD;
	} 
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

相关链接

题目传送门：https://www.codechef.com/problems/DINING
官方题解：https://discuss.codechef.com/questions/70332/dining-editorial

解题报告

这题套路啊，神™套路啊！

关键问题是它的概率是乘起来的，不是加起来
于是很多东西都不能用啊！
于是题解说我们可以取对数，因为$\log(a \cdot b) = \log (a) + \log (b)$
于是就变成了加法，于是就可以跑一个费用流了

把乘法换搞成加法，在模意义下还有一种做法，参见：
http://oi.cyo.ng/?p=2702

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2118
神犇题解：https://blog.sengxian.com/solutions/bzoj-2118

解题报告

先来看一道简单的题目：

给定$a,b,c(a,b,c \le 10^5)$，规定$x,y,z \in \mathbb{N}$
问$ax+by+cz$不能表示出的正整数中，最大的那一个是多少

我们不妨在$\bmod c$的意义下做，这样就可以只考虑$0 \sim c-1$
于是暴力用$a,b$连边，跑一边最短路
这样就可以求出在$\bmod c$的剩余系中，每一个等价类最早出现的位置
于是扫一遍，取一个$\max$就可以了

然后再看看这个题，也就是多连几条边的事吧？

Code

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

const int N = 500009;
const int M = N * 12;
const LL INF = 1e17;

int n,a[N],done[N];
int nxt[M],to[M],cost[M],head[N];
LL dis[N],bmn,bmx,mn=INF;
priority_queue<pair<LL,int> > que;

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

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 Dijkstra() {
	for (int i=0;i<mn;i++) dis[i] = INF;
	dis[0] = 0; que.push(make_pair(0, 0));
	while (!que.empty()) {
		int w = que.top().second; que.pop();
		if (done[w]) continue; else done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

inline LL cal(LL lim) {
	LL ret = 0, tmp;
	for (int i=0;i<mn;i++) {
		if (lim < dis[i]) continue;
		ret += (lim - dis[i]) / mn + 1;
	}
	return ret;
}

int main() {
	n = read(); cin>>bmn>>bmx;
	for (int i=1;i<=n;i++) {
		a[i] = read();
		if (a[i]) mn = min(mn, (LL)a[i]);
	}
	for (int i=1;i<=n;i++) {
		if (a[i] == mn) continue;
		for (int j=0;j<mn;j++) {
			AddEdge(j, (j+a[i])%mn, a[i]);
		}
	}
	Dijkstra();
	printf("%lld\n",cal(bmx)-cal(bmn-1));
	return 0;
}

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4810
神犇题解：http://blog.csdn.net/qzh_1430586275/article/details/69400458

解题报告

看一看似乎一脸懵逼啊
询问两数相加、相减为特殊值不是只能$FFT$吗？
你这™还带区间限制，那怎么做啊……

但仔细看看值域范围，发现这货只有$10^{10}$
配上$30s$的限制，刚好是$bitset$的数据范围啊！
于是仔细想一想，加法可以直接减法可以直接左移然后$and$起来
至于减法，我们可以记一下负数就可以转化为减法了
至于相乘嘛，我们可以暴力枚举因数！
于是再配上区间的莫队，时间复杂度：$O(n \sqrt{n} + \frac{mc}{64})$

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2618
神犇题解：http://hzwer.com/4713.html

解题报告

把每一个凸多边形看成一堆半平面
于是原题变成求半平面交

Code

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

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
	double x,y;
	inline Point() {}
	inline Point(double a, double b):x(a),y(b) {}
	inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
	inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
	inline Point operator * (double d) const {return Point(x*d, y*d);}
	inline Point operator / (double d) const {return Point(x/d, y/d);}
	inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
	inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;} 
}p[N],cvx[N];

struct Line{
	Point a,b; double slp;
	inline Line() {}
	inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
	inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
	inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
	inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
	inline double len() {return sqrt((b - a) * (b - a));}
	inline Point ins(const Line &L) {
		double s1 = (b - L.b) ^ (L.a - L.b);
		double s2 = (a - L.a) ^ (L.b - L.a);
		return a + (((b - a) * s2) / (s1 + s2));
	}
}l[N],que[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 HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
	sort(a+1, a+1+tot); cnt = tot; tot = 1; 
	for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i]; 
	b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
	for (int i=3;i<=tot;i++) {
		while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
		while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
		b[++r] = a[i];
	} 
	while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
	while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
	cnt = 0; b[0] = b[r];
	for (int i=l;i<=r;i++) b[++cnt] = b[i];
	for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]); 
}

int main() {
	n = read(); int tot=0,cnt=0;
	for (int i=1;i<=n;i++) {
		m = read();
		for (int j=1;j<=m;j++) p[j].x = read(), p[j].y = read();
		p[m+1] = p[1];
		for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
	}
	HalfPlaneIntersection(tot, l, cnt, que, cvx);
	double vout = 0;
	for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
	printf("%.3lf\n",vout/2);
	return 0;
}

相关链接

题目传送门：https://www.codechef.com/problems/GRAPHCNT
数据生成器：http://paste.ubuntu.com/24319212/
神犇题解Ⅰ：http://blog.csdn.net/a710128/article/details/49913553
神犇题解Ⅱ：http://www.cnblogs.com/meowww/p/6475952.html

解题报告

就是支配树的板题？

我们可以用Lengauer Tarjan算法在$O(n \alpha (n))$的时间复杂度内解决这个问题
也可以求出所有的半支配点，然后用灭绝树来搞，时间复杂度：$O(n \log n)$
另外之前我还看到一种非常鬼畜地LCT+灭绝树地做法，时间复杂度跑起来像：$O(n \log n)$

Code

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

const int N = 100009;
const int M = 1500009;

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

class Dominator_Tree{
	int dom[N],pre[N],head[N],nxt[M],to[M],que[N],anc[N];
	int dfs_cnt,dfn[N],idom[N],semi[N],bst[N],ufs[N],sz[N];
	public: 
		inline void AddEdge(int u, int v) {
			AddEdge(head, u, v);
			AddEdge(pre, v, u);	
		}
		inline void build() {
			DFS(1);
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) {
				for (int j=pre[w];j;j=nxt[j]) {
					if (dfn[to[j]]) {
						update(to[j]);
						if (dfn[semi[bst[to[j]]]] < dfn[semi[w]])
							semi[w] = semi[bst[to[j]]];
					}
				}
				AddEdge(dom, semi[w], w);
				ufs[w] = anc[w]; w = que[i-1];
				for (int j=dom[w];j;j=nxt[j]) {
					update(to[j]);
					if (semi[bst[to[j]]] == w) idom[to[j]] = w;
					else idom[to[j]] = bst[to[j]];
				}
			}
			for (int i=2,w;w=que[i],i<=dfs_cnt;i++)
				idom[w] = ((idom[w] == semi[w])? idom[w]: idom[idom[w]]);
		}
		inline LL solve() {
			LL ret = dfs_cnt * (dfs_cnt - 1ll) / 2ll; 
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) { 
				if (++sz[w], idom[w] != 1) sz[idom[w]] += sz[w];
				else ret -= (sz[w] - 1ll) * sz[w] / 2ll;
			} return ret;
		}
	private:
		inline void AddEdge(int *arr, int u, int v) {
			static int E = 1; 
			to[++E] = v; nxt[E] = arr[u]; arr[u] = E;
		}	
		void DFS(int w) {
			dfn[w] = ++dfs_cnt; que[dfs_cnt] = w;
			bst[w] = semi[w] = ufs[w] = w;
			for (int i=head[w];i;i=nxt[i]) 
				if (!dfn[to[i]]) anc[to[i]] = w, DFS(to[i]);
		}
		int update(int w) {
			if (ufs[w] == w) return w;
			int tmp = update(ufs[w]);
			if (dfn[semi[bst[ufs[w]]]] < dfn[semi[bst[w]]])
				bst[w] = bst[ufs[w]];
			return ufs[w] = tmp;
		}
}DMT;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		DMT.AddEdge(u, v);
	}
	DMT.build();
	cout<<DMT.solve();
	return 0;
}