NOIP模拟好题题解(一)

PERMUTATION

对于两个长度同为N的排列A和B, 定义它们的权值value为:
$$ value(A, B) = \sum^N_{i=1} max(A_i, B_i) $$
给定N和K, 求有多少种长度为N的排列A和B使得[latex]value(A, B) \le K[/latex], 答案对[latex]10^9+7[/latex]取模。
[latex]N \le 50[/latex]

解题报告

假想我们有两个并排的插槽, 每个插槽一开始有N个空位。
考虑从大到小把元素N到1插入到两个插槽里(一次插入两个相同数字, 每次分别插入一个数字i)。
那么我们每次插入数字所带来的的贡献不是0, 就是i或者2×i了。
然后设计DP状态[latex]dp_{full, half, sum}[/latex]。
其中, full代表目前两个插槽内对应位置已经插满两个数字的位置数量;
half代表目前两个插槽内对应位置只插入了一个数字的位置数量除以二(其实不除也可以, 反正这种空位数量一定是二的倍数)
sum代表当前贡献和。
接下来对于四种情况分类讨论转移:
1.插入的两个数字刚好消掉一个half, 增加两个full, 贡献为0。
2.插入的两个数字其中一个消掉半个half, 另外一个增加了半个half, half不变而full增加了1,贡献为i。
3.插入的两个数字一共增加了一整个half, 贡献为2×i。
4.插入的两个数字刚好填补满同一位置的一个full, 贡献为i。
方案数计算就不多说了, 组合一下搞搞就出来了。

TPS

给你一颗树, 你要在上面安放X个无线基站, 一个节点的坐标用一个长度为X的有序数列A表示, A中元素依次为该节点到第i个基站的距离。
问至少放置多少个无线基站才能保证没有两个节点的序列A相同。
[latex]N \le 5000 [/latex]

解题报告

首先必须在一个叶子节点放一个基站。
枚举这个叶子节点, 然后树就被分成了很多层, 对于每个节点我们必须区分出不同子树。
首先如果子树中有一个子树是一条链那么可以不在那里放基站, 然后从其他儿子节点的DP值累和即可。
真的比较迷啊…具体看看代码吧:

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int MAXN = 5010;
char g[MAXN][MAXN];
struct Node {
	int v, nxt;
} d[MAXN*2];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
	etot ++;
	d[etot].v = b;
	d[etot].nxt = head[a];
	head[a] = etot;
}

int dp[MAXN];
bool chain[MAXN];
int dfs (int u, int f) {
	chain[u] = false;
	int cnt = 0,num=0;
	dp[u] = 0;
	for(int e = head[u]; e; e = d[e].nxt) {
		if(f == d[e].v) continue ;
		dp[u] += dfs(d[e].v, u);
		if(chain[d[e].v])num=1;
		cnt ++;
	}
	if((cnt <= 1 && num) || cnt == 0) chain[u] = true;
	if(num)--dp[u];
	dp[u] = max(dp[u],1);
	return dp[u];
}
int rd[MAXN];
int main () {
	int N;
	scanf("%d", &N);
	for(int i = 1; i<=N; i++) {
		scanf("%s", g[i]+1);
		for(int j = 1; j<=N; j++)
			if(g[i][j] == 'Y') addEdge(i, j), rd[i]++, rd[j]++;
	}
	int ans = 0x3f3f3f3f;
	for(int i = 1; i<=N; i++)
		if(rd[i] == 2) ans = min(ans, dfs(i, 0)+1);
	printf("%d\n", ans);
}

SIMILAR

输入N个无编号不重复字符串, 和M个限制条件, 限制条件形如(a, b)表示字符串a为字符串b的前缀。
问有多少种编号方案使得所有限制条件被满足。
[latex] N \le 50, M \le 8, len(str) \le 50 [/latex]

解题报告

题面没有说过字符串不能重复…害的考试想了好久…
首先把所有字符串的关系搞出来, 发现这一定是一个有向无环图。
接着发现如果字符串a是b的前缀, b是c的前缀, 那么a一定是c的前缀, 从而整个有向无环图(也可能是多个)形成了一种类似于树的结构:只是每个子树的根节点到子树内所有节点都会有一条直接的边。
然后鉴于数据那么水可以大力把这个树搞出来, 在树上进行状态压缩后做背包之类的操作即可, 虽然状压点可能达到16个, 但是合法状态数还是比较少的, 可以过。
处理森林的情况, 直接新建虚拟节点出来然后把它向所有树根连边, 并且限定这个节点不能放置’特殊点’, 一波dp即可。
说的模糊看代码:

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
const int MAXN = 55;
char str[MAXN][MAXN];
int len[MAXN], N, M;
int req[10][2];
int rin[MAXN];
struct Node {
	int v, nxt;
} d[MAXN*4];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
	//printf("edge:%d->%d\n", a, b);
	etot ++;
	d[etot].v = b;
	d[etot].nxt = head[a];
	head[a] = etot;
}

int dp[52][1<<16];
int tmp[1<<16];
int itot;
vector<int> pre[16], vald;
vector<int> child[1<<16];
int sz[MAXN];
void tdp (int u, bool b = false) {
	dp[u][0] = 1;
	sz[u] = 1;
	for(int e = head[u]; e; e = d[e].nxt) {
		tdp(d[e].v);
		for(int x = 0; x<(int)vald.size(); x++) {
			int s = vald[x];
			tmp[s] = 0;
			for(int t = 0; t<(int)child[s].size(); t++)
				(tmp[s] += (LL)dp[u][child[s][t]]*dp[d[e].v][s^child[s][t]]%MOD) %= MOD;
		}
		for(int x = 0; x<(int)vald.size(); x++) {
			int s = vald[x];
			dp[u][s] = tmp[s];
		}
		sz[u] += sz[d[e].v];
	}
	memcpy(tmp, dp[u], sizeof tmp);
	if(b) return ;
	for(int i = 0; i<itot; i++)
		for(int t = 0; t<(int)vald.size(); t++) {
			int s = vald[t];
			if(s&(1<<i)) continue ;
			(dp[u][s|(1<<i)] += tmp[s]) %= MOD;
		}
}
int rid[MAXN];
inline void makeImg (int u) {
	if(rid[u]) return ;
	else rid[u] = ++itot;
}
int main () {
	freopen("similar.in", "r", stdin);
	freopen("similar.out", "w", stdout);
	scanf("%d", &N);
	for(int i = 1; i<=N; i++)
		scanf("%s", str[i]), len[i] = strlen(str[i]);
	scanf("%d", &M);
	for(int i = 1; i<=M; i++)
		scanf("%d", &req[i][0]);
	for(int i = 1; i<=M; i++)
		scanf("%d", &req[i][1]);
	for(int i = 1; i<=M; i++) {
		if(req[i][0] == req[i][1]) continue ;
		makeImg(req[i][0]), makeImg(req[i][1]);
	}
	for(int i = 1; i<=M; i++) {
		if(req[i][0] == req[i][1]) continue ;
		pre[rid[req[i][0]]-1].push_back(rid[req[i][1]]-1);
	}
	
	for(int s = 0; s<(1<<itot); s++) {
		bool flg = true;
		for(int i = 0; i<itot; i++)
			if(s&(1<<i)) for(int t = 0; t<(int)pre[i].size(); t++)
				if(!(s&(1<<pre[i][t]))) {flg = false; break;}
		if(!flg) continue ;
		vald.push_back(s);
	}
	for(int t = 0; t<(int)vald.size(); t++) {
		int s = vald[t];
		for(int s1 = s; s1; s1=(s1-1)&s) {
			if(*lower_bound(vald.begin(), vald.end(), s1) != s1 || *lower_bound(vald.begin(), vald.end(), s^s1) != (s^s1)) continue ;
			child[s].push_back(s1);
		}
		child[s].push_back(0);
	}
	
	for(int i = 1; i<=N; i++)
		for(int j = 1; j<=N; j++) {
			if(i == j) continue ;
			int k;
			for(k = 0; k<len[i]; k++)
				if(str[j][k] != str[i][k]) break ;
			rin[j] += (k == len[i]);
		}
	int p = N+1;
	for(int i = 1; i<=N; i++)
		if(rin[i] == 0) addEdge(p, i);
	for(int i = 1; i<=N; i++) {
		char stemp[55];
		int flg = 0;
		for(int e = len[i]-1; e; e--) {
			memcpy(stemp, str[i], e+1);
			stemp[e] = '\0';
			for(int j = 1; j<=N; j++)
				if(strcmp(stemp, str[j]) == 0) {flg = j; break;}
			if(flg) break ;
		}
		if(flg) addEdge(flg, i);
	}
	tdp(p, true);
	int fc = 1;
	for(int i = 1; i<=N-itot; i++)
		fc = (LL)fc*i%MOD;
	printf("%lld\n", (LL)dp[p][(1<<itot)-1]*fc%MOD);
}

GEAR

给你N个齿轮, 被染成RGB三种颜色, 同种颜色齿轮旋转方向必须相同, 齿轮之间有一些咬合关系, 相互咬合的齿轮旋转方向必须相反, 你能选择齿轮旋转方向, 问至少移除多少齿轮才能让方案合法。
保证通种颜色齿轮之间没有咬合关系。
[latex] N \le 50 [/latex]

解题报告

首先三种颜色的齿轮不可能方向完全一样, 这显然。
然后枚举哪两种齿轮旋转方向相同, 另外一种齿轮很明显就不用管了, 然后这两种颜色形成了一个二分图, 接下来就是二分图最大独立集问题了。
转化成二分图最大匹配, 用最大流求解(主要因为不是很会写匈牙利QAQ)

COOL

给出整数N, 则集合S包含整数1, 2, 3, … , N。考虑S的某个非空子集T,把子集T的所有元素都写下来, 如果使用0-9中每个数字的次数都没有超过1次(允许是0次),则把子集T称为酷子集。
给出N, 问有多少酷子集, 答案对[latex]10^9+7[/latex]取模。

解题报告

首先发现0-9这10个数字只可能出现一次, 那么给定N, 我们可以一波大力(10!)或者数位DP求出所有满足条件的数字, 设[latex]cnt_S[/latex]为用S集内的数字组成的合法数字数量, 那么有如下方程:
$$ f_{i,S} = f_{i-1,S_1}\times cnt_{S_2} | S_1 xor S_2 = S $$
这样就可以算出一个’酷排列’的方案数, 由于’酷子集’是无序的, 并且模数是一个素数, 直接利用逆元除去排列数即可。

PAINT

给一个 2 × M 的表格,现在你要将其中的 R 个格子涂成红色, G 个格子涂成蓝色, B 个格子涂成蓝色, 并且要求同时满足以下条件:
1.任意两个相邻格子的颜色不同;
2.每种颜色在任意一个 2 × 2 矩阵中都至少出现一次。
求方案数, 对[latex]10^9+7[/latex]取模。

解题报告

好题啊! 还没有超纲
首先考虑用一列上没有出现过的颜色的字符表示这一列, 那么2×M的矩阵就转换成了一个字符串。
然后根据狗眼观察法就可以发现相同字符不可能相邻, 同时对于一个这样的字符串有两种把它还原为原串的方法。
重新定义R为M-R(不含R的列数), G = M-G, B = M-B。
接下来问题就转化成了统计有多少个满足相同字符不能相邻的序列。
尝试把序列看成由G分隔开的若干段非空子串, 考虑G是否填充在左边界或者右边界, 子串数量一共可能有G-1, G(两种情况)或者G+1个, 分别计算方案后累加即可, 设当前子串数量为N。
而子串一共有以下三种可能:
1.R比B多一个, 交错填充(RBRB…RBR), 设这样的子串数量为X
2.R和B交错填充(可表示为RBRB…或BRBR…, 导致答案需要乘以[latex]2^Y[/latex]), 设这样的子串数量为Y
3.B比R多一个, 交错填充(BRBR…BRB), 设这样的子串数量为Z
那么就可以列个方程组:
[latex]X+Y+Z=N[/latex]
[latex]X-Y = R-B[/latex]
解得:[latex] X = \frac{N-Y+R-B}{2}, Z = \frac{N-Y+B-R}{2} [/latex]
当X或Z不是整数或小于0时忽略即可。
确定了XYZ, 继续考虑如何计算序列数量。
首先我们确定三种序列相对位置关系(三种元素的排列数, 阶乘+除逆元即可)
然后考虑想序列中填充元素, 为了保证每个子序列非空, 先向每个X类里加入一个R, 每个Y类里加入一对RB, 每个Z类里加入一个B。
接下来无论向哪一个子串内塞元素, 都只能一对一对地塞R和B了
我们现在应该还剩下[latex]\frac{M-G-X-Z}{2}-Y[/latex]对R和B可以塞, 考虑隔板法, 方案数乘以[latex]C(N-1, N-1+\frac{M-G-X-Z}{2}-Y)[/latex]即可。
答案记得乘上2(序列转换回去有两种方法)。

代码

由于我可能没说清一些东西就附上代码吧.

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
LL ans = 0;
int M, R, G, B;
inline LL advPow (LL a, int b) {
	LL ret = 1;
	while(b) {
		if(b & 1) ret = (LL)ret*a%MOD;
		a = (LL)a*a%MOD;
		b >>= 1;
	}
	return ret;
}
LL fac[2000100];
inline LL C (int M, int N) {
	return (LL)fac[N]*advPow((LL)fac[M]*fac[N-M]%MOD, MOD-2)%MOD;
}
void solve (int N, int mul) {
	if(N == 0) return;
	for(int x0 = 0; x0<=N; x0++) {
		int xn1 = (N-x0+R-B);
		int xp1 = (N-x0+B-R);
		if(xn1 < 0 || xp1 < 0) continue ;
		if(xn1 & 1) continue ;
		else xn1 >>= 1;
		if(xp1 & 1) continue ;
		else xp1 >>= 1;
		if(((M-G-xn1-xp1) & 1) || (M-G-xn1-xp1)/2-x0+N-1 < N-1) continue ;
		LL tmp = (LL)fac[N]*advPow((LL)fac[xn1]*fac[x0]%MOD*fac[xp1]%MOD, MOD-2)%MOD*advPow(2, x0)%MOD*C(N-1, (M-G-xn1-xp1)/2-x0+N-1)%MOD;
		ans = (ans+tmp*mul)%MOD;
	}
}
int main () {
	freopen("paint.in", "r", stdin);
	freopen("paint.out", "w", stdout);
	fac[0] = 1;
	for(int i = 1; i<=2000000; i++)
		fac[i] = (LL)fac[i-1]*i%MOD;
	scanf("%d%d%d%d", &M, &R, &G, &B);
	R = M-R, G = M-G, B = M-B;
	solve(G-1, 1);
	solve(G, 2);
	solve(G+1, 1);
	printf("%lld\n", ans*2%MOD);
}

BUILDING

一条宽阔的河中有N根柱子, 他们从河的此岸到彼岸,排成一条直线。
选择一组柱子,把它们的顶部连接起来形成桥, 选出的柱子必须包括第一根和最后一根柱子。
不被选中的柱子必须移除, 移除第i根柱子的费用为[latex]w_i[/latex](可能为负), 在柱子i和j之间建造一段桥的费用是[latex](h_i-h_j)^2[/latex]
问建造连接第一根和最后一根柱子的桥的最小费用。
[latex]N \le 10^5[/latex]

解题报告

我死也不信NOIP第一题这种姿势…
首先这个很明显就是斜率优化, 让f[i]表示选中第i根柱子并且处理了前i根柱子的最小费用。
然后推一波式子:$$ f_i = min\{ f_j+sumW(j+1, i-1)+(h_i-h_j)^2\} | j < i $$
$$ = min\{f_j+sumW(j+1, i-1)+{h_j}^2 – 2 h_i h_j + {h_i}^2\} $$
如果把h[i]看成坐标x, 那么这个就是一个一次函数的形式, 我们需要维护一个右上凸壳进行转移。
但是非常恶心的是, h是没有单调性的, 要强行维护这个凸壳必须写动态凸包, 所以尝试使用CDQ。
分治姿势大约是:
1.处理左半边
2.处理出左半边的凸壳, 用左半边更新右半边
3.处理右半边
CDQ分治比动态凸包好多了, 复杂度也可以达到[latex]N log(N)[/latex], 但是比较懒就写成[latex]N log^2(N)[/latex]了。

SWAP

给定一个长度为N的整数序列A, 每个元素属于区间[0, 9]。
接下随机交换位置X和位置Y上的数字(X 解题报告

解法由Ender原创。
首先考虑DP, 设f[i][j]为第i个位置在第j次交换后的期望值, 那么每次转移为:
$$ x = \frac{2}{N\times (N-1)}, y = \frac{2}{N} $$
$$ f_{i,j} = ((\sum_{k=1}^N f_{k, j-1})-f_{i,j-1})x + (f_{i,j-1})(1-y)$$
设S为A序列之和, 很显然对于任何j, 都有[latex] \sum_{i=1}^N f_{i,j} = S[/latex]
把递推式变形, 常数移到一起:
$$ f_{i,j} = S\times x + (1-y-x)f_{i,j-1} $$
就是一个线性关系式了, 矩乘计算, 或者 使用张老师教授的技巧 推一波通项。
如果选择推通项会发现[latex]f_{i,j}=(1-y-x)^j(f_{i,0}+\frac{S\times x}{-(x+y)})-\frac{S\times x}{-(x+y)}[/latex]
反正都得快速幂0.0。

CONSTELLATION

给你平面上N个点, 第i个点出现的概率是posb[i], 问凸包期望面积。
[latex] N \le 5000 [/latex]

解题报告

题目简单粗暴不会做啊QAQ
看完题解觉得自己是傻瓜啊QAQ
考虑边(u, v)在凸包上的贡献, 它对凸包的贡献就是它和原点形成的有向面积, 它出现的概率就是它左边(有向)以外的点全部不出现的概率乘以它两个点出现的概率, 然后加速这个过程用极角序加扫描线就可以搞了, 主要是代码的一些细节。

GAME

A和B在一棵树上玩一个游戏, A有一枚硬币在节点1.每个回合, B会选择树上的一个节点进行标记, 然后A会标记硬币所在节点, 接着选择硬币相邻的一个未标记节点, 把硬币移动到那个节点。
给你这棵树和整数K, 问B能不能在K次操作内让A无路可走。
[latex] N,K \le 400 [/latex]

解题报告

考试的时候冥思苦想想不出来啊…于是来骗分吧!
然后写了两个贪心+一个随机化搜索(一定概率放弃贪心最优选择次优)+判断是否超时, 拿了84分…
好了来说正经的。
首先, 我们来发掘题目中的一些规律:
1.如果一个节点的深度大于K, 那么这个节点对答案无关紧要, 因为当硬币能够抵达这个节点前, 游戏就已经结束了。
2.如果一个 叶子 节点深度小于K, 那么这个节点对答案也无关紧要, 因为如果A选择走向这个节点的话, 他就输定了。
3.如果一个节点的所有儿子都是对答案无关紧要的, 那么这个节点对答案也是无关紧要的, 这显然。
我们可以删除所有’对答案无关紧要的节点’, 方便接下来的讨论。
删除完毕后, 把剩余节点按照深度分层, 那么最优策略一定是从深度为1, 2, …, K-1, K的K层节点中每层选出一个进行删除, 这也很显然(放弃深度小的节点以求得删除两个以上的深度较大的同层节点必然不会更优)。
B一共只有K次删除机会, 我们来看看他至少能够删除多少节点。
这里删除u定义为删除u到根节点路径上所有节点和子树节点, 因为如果B采取删除u的策略, A一定不可能让硬币待在那些节点。
假定删除策略为删除第i层中没有被删除节点中直接儿子数量最多的节点:
设 cnt[i] 为深度为i的第i层的节点中拥有大于等于2个儿子的节点数量。
设[latex]b[/latex]满足[latex]cnt[1, 2, …, b-1] \le 1[/latex]并且[latex]cnt[b] \ge 2[/latex]
那么从第一层删除到第b层, 一共就删除了至少[latex]2 \times b(2K-b)[/latex]个节点
删除的节点到根节点的路径会不会与之前删除的节点重复呢?答案是否定的, 应为所有深度小于i的’分岔’节点都被删除了, 这意味着树上未被删除的通向根的路径中没有’合并’节点。
接下来考虑b层以下至少会删除多少节点, 是[latex](K-b)(K-b)[/latex]
相加答案, 发现包含b的项恰好消去, 答案为至少删除K平方个节点!

<(QAQ ) !

这意味着如果树的大小小于等于K平方, B是必胜的! 他可以直接把整颗树删完!
那么就只用考虑K小于根号N的情况了, 暴力状压DP即可。
好神啊!

代码

还没写…