NOIP模拟赛总结Ⅱ | Aniciry = Meteorshower

# Trees

# 题目描述

在长度为 $n$ 的序列里选出 $k$ 个数，这些数的贡献为最大的数的数值。为可选择的所有方案的权值和。

# 解题思路

不方便去快速求出子序列的最大值，我们可以枚举这个最大值，然后乘上选剩下 $k-1$ 个数的方案数就能求出一个最大值的贡献了。把所有数作为最大值的贡献加起来就是答案。至于选数的的方案数，组合数学求下就好。

	#include<algorithm>
	#include<iostream>
	#include<cstdio>
	using namespace std;
	#define long long long
	const int MAXN = 100010;
	const int p = 1e9+7;
	int n, k; long ans;
	long a[MAXN], fact[MAXN], finv[MAXN];
	auto prework(int n) -> void;
	auto C(int n, int m) -> long;
	auto ksm(long a, int b) -> long;
	int main()
	{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i += 1)
	scanf("%lld", &a[i]);
	sort(a+1, a+n+1);
	prework(n);
	for(int i = k; i <= n; i += 1)
	(ans += a[i]*C(i-1, k-1)%p) %= p;
	printf("%lld", ans);
	return 0;
	}
	auto prework(int n) -> void
	{
	fact[0] = finv[0] = 1;
	for(int i = 1; i <= n; i += 1) fact[i] = fact[i-1] * i % p;
	for(int i = 1; i <= n; i += 1) finv[i] = ksm(fact[i], p-2);
	}
	auto C(int n, int m) -> long
	{
	if(n < m) return 0;
	return fact[n] * finv[m]%p * finv[n-m]%p;
	}
	auto ksm(long a, int b) -> long
	{
	long ans = 1;
	for(; b; (a *= a) % p, b >>= 1)
	if(b&1) (ans *= a) %= p; return ans;
	}

# bridge

# 题目描述

在一个一位数轴上的一个点开始走，走 $n$ 步，可以往左也可以往右，最后回到这个点，每两次经过这个点的时间间隔不能超过 $m$ 。询问可以行走的路线方案数。

# 解题思路

考虑 DP 转移求方案数。
首先我们设计一个比较简单的状态，用 $f_i$ 表示走 $i$ 步回到起点且满足题目时间限制的方案数。因为左右两个方向对称，所以我们算出来一种就行，另一边乘 $2$ 即可。
接下来我们要算的就是走 $x$ ( $x$ 为偶数) 步的之后回到起点的方案数，因为保证不重复计算方案数，所以不能让他中途经过起点。为了满足这个性质，我们可以让他先迈出一步，在这个点及外边反复横跳，最后留一步回到起点。
我们记 $d_x$ 为走 $x$ 步再回到起点的方案数， $f_i$ 的转移方程就是 $f_i = \sum\limits_{j = 2}^{m} f_{i-j} \ast 2 \cdot d_{j-2}$ 。
常系数转移方程的优化交给矩阵就好，由 $O(nm)$ 的时间复杂度降为 $O(m^3 \log n)$ , 可以接受。

	#include<iostream>
	#include<cstdio>
	using namespace std;
	#define long long long
	const long MAXN = 110 ;
	const long p = 100000007 ;

	int m, n;
	long f[MAXN][MAXN];
	long ans[MAXN][MAXN];
	long d[MAXN][MAXN] ;

	struct node
	{
	long v[MAXN][MAXN];
	node(){
	for(int i = 1; i <= m; i += 1)
	for(int j = 1; j <= m; j += 1)
	v[i][j] = 0;
	}
	friend node operator*(node a, node b){
	node c;
	for(int i = 1; i <= m; i += 1)
	for(int j = 1; j <= m; j += 1)
	for(int k = 1; k <= m; k += 1)
	(c.v[i][k] += a.v[i][j]*b.v[j][k]%p) %= p;
	return c;
	}
	}A, B;

	auto ksm(node a, int b, node &ans) -> void;

	int main()
	{
	scanf("%d%d", &n, &m) ;
	int t = m >> 1 ;
	d[0][0] = 1;
	for(int i = 1; i <= m; i += 1)
	for(int j = 0; j <= i; j += 1)
	{
	if(j != 0) (d[i][j] += d[i-1][j-1]) %= p;
	if(j != i) (d[i][j] += d[i-1][j+1]) %= p;
	}
	for(int i = 1; i < m; i += 1) B.v[i+1][i] = 1;
	for(int i = 1; i < m; i += 1) B.v[i][m] = 2*d[m-i-1][0]%p;
	A.v[1][m] = 1;
	ksm(B, n, A);
	printf("%lld", A.v[1][m]);
	return 0;
	}
	auto ksm(node a, int b, node &ans) -> void
	{
	for(; b; a = a*a, b >>= 1)
	if(b&1) ans = ans*a;
	}

# flowers

# 题目描述

地上一开始有 $A$ 片樱花，接下来每秒掉落 $B$ 片，从第一秒开始，过 $n$ 秒，地上每秒的樱花数的二进制下 $1$ 的数量总和。

# 解题思路

这是一道需要找规律的题，每一位上的 01 都有循环节，第 $i$ 位的循环节为 $2_{i+1}$ 。而且总所周知的一点是，在一个循环节里，一位上的 01 数量对半分。
所以对于循环的部分，直接算就好，反正是 $O(1)$ 的。
那么对于不是整个循环节的剩下部分，要没事低位剩下的少，高位进位不频繁，都允许我们去暴力算。对于每一位，每次计算连续的 0 和 1 的个数会比较方便（只要算出还有多少才进位就行）。

	#include<iostream>
	#include<cstring>
	#include<cstdio>
	#include<cmath>
	using namespace std;
	#define long long long
	int T, n; long A, B, m, ans;
	auto work() -> void;
	int main()
	{
	scanf("%d", &T);
	while(T--) work();
	return 0;
	}
	auto calc(long x, long t) -> void
	{
	static long now, pos;
	for(long i = 1; i <= x; i += 1)
	{
	now = (B + A * i)%t;
	if(now >= (t>>1))
	{
	pos = min(x, i + (t-1 - now)/A);
	ans += pos-i+1; i = pos;
	}
	else i = min(x, i + ((t>>1)-1 - now)/A);
	}
	}
	auto work() -> void
	{
	ans = 0;
	scanf("%lld%lld%lld", &A, &B, &n);
	while((!(A&1)) and A)
	ans += n*(B&1), A >>= 1, B >>= 1;
	m = B + A * n;
	for(long i = 2; i < (m<<1); i <<= 1)
	ans += (n/i)*(i/2), calc(n%i,i);
	printf("%lld\n", ans);
	}

# robo

# 题目描述

小文给这个小机器人布置了 $n*m$ 的场地（场地外用障碍围住），在场地上设置了障碍、水池和靶子。其中，障碍是不可以通过并且无法用水晶弹打掉的，靶子无法通过、但是可以被水晶弹打掉，水池也无法通过、但是水晶弹可以通过水池。小文检查了一下小机器人，发现它的指令系统很简单。该系统中一共有 $6$ 种指令，指令的使用说明如下：

“FT x” ：该指令表示炮台的 $90°$ 转动，其中 $x∈[0，1]，x∈Z$ ，并且 $0、1$ 分别表示逆时针和顺时针。

“FF i” ：该指令表示填弹，填弹后弹仓剩余弹量减一，弹夹剩余弹量加一，其中 $i∈[0，1]$ 且 $i∈Z$ ， $i$ 为 $1$ 表示所填水晶弹为大弹丸，为 $0$ 表示所填水晶弹为小弹丸。

“FE” ：该指令表示发射水晶弹，水晶弹的发射方向同炮台的朝向，发射的水晶弹为最后一个填入弹夹的水晶弹，指令执行后弹夹容量减一。

“WT x” ：该指令表示机器人的 $90°$ 转动，其中 $x∈[0，1]，x∈Z$ ，并且 $0, 1$ 分别表示逆时针和顺时针，注意机器人转动时炮台不会转动。

“WG y” ：该指令表示机器人前进 $y$ 步，其中 $y∈[0，max(m，n))，y∈Z$ 。

“END” ：该指令将返回 “Complete” 并停机，不同于编译器先编译后运行， END （及其他将造成停机的情况）后的指令均被无视。

现在小文将要开始测试，但是为了避免自己的指令集让小机器人出现错误，小文给了你场地、小机器人的初始状态和指令集并拜托你帮他计算出小机器人的返回内容、停下的位置、打掉的靶子数量以及小机器人的状态。

注意：

（一）弹夹无弹的情况下将跳过 FE 指令，弹仓无相应弹丸的情况下将跳过 FF 指令；

（二）大水晶弹一发打掉靶子，小水晶弹需两发打掉靶子，靶子打掉后变成空地可通过；

（三）小机器人将在以下情况下返回 “ERROR” 并停机：

（1）在弹夹已满的情况下继续填弹；

（2）撞上障碍（包括未被打掉的靶子）或者撞进水池；

（3）指令后的参数不满足要求（例： “FE 10” ）;

（4）无 “END” 指令；

# 做题思路

此代模拟一道，细节还是不少。

每次要把所有指令读完。而不是到了 END 和 ERROR 就直接 break 开始下个数据。
不合法的指令参数只会出现在有参数的指令里，所以并不需要全部判断，可以减少一部分码量。
注意不合法的参里有小数。
发生 ERROR 后，输出的数据是发生 ERROR 前的那条指令执行完的数据。
言有尽而意无穷......

	#include<iostream>
	#include<climits>
	#include<cstring>
	#include<cstdio>
	#include<string>
	using namespace std;
	const int inf = 11451419;
	struct node{
	int magezine[35], rest, lightrest, heavyrest;
	int robodir, gundir, x, y, kill, state;
	}data;
	int T, n, m, k, mp[210][210], Hp[210][210];
	int magezine[35], rest, limit, lightrest, heavyrest;
	int robodir, gundir, x, y, kill, state;
	int dx[4] = {-1, 0, 1, 0};
	int dy[4] = {0, -1, 0, 1};
	auto init() -> void;
	auto work() -> void;
	auto record() -> void;
	auto FT(int x) -> int;
	auto FF(int i) -> int;
	auto FE() -> int;
	auto WT(int x) -> int;
	auto WG(int y) -> int;
	auto END() -> int;
	int main()
	{
	cin >> T;
	while(T--) work();
	return 0;
	}
	auto work() -> void
	{
	string ch;
	int opt, len, num; init();
	cin >> n >> m;
	for(int i = 1; i <= n; i += 1)
	for(int j = 1; j <= m; j += 1)
	cin >> mp[i][j];
	cin >> x >> y >> limit; x += 1, y += 1;
	cin >> heavyrest >> lightrest >> k;
	for(int i = 1; i <= n; i += 1)
	for(int j = 1; j <= m; j += 1)
	if(mp[i][j] == 1) Hp[i][j] = inf;
	else if(mp[i][j] == 2) Hp[i][j] = 2;
	else if(mp[i][j] == 3) Hp[i][j] = -1;
	else if(mp[i][j] == 0) Hp[i][j] = 0;
	getline(cin, ch);int flag = false;
	for(int i = 1; i <= k; i += 1)
	{
	getline(cin, ch); len = ch.size(); num = 0;
	if(flag or state == -1) continue; record();
	if(ch[0] == 'F' and ch[1] == 'T')
	{
	int pos = 3;
	if(len < 3) {state = -1;continue;};
	for( ; pos < len; pos += 1)
	{
	if(ch[pos] <= '9' and ch[pos] >= '0')
	num = num*10+ch[pos]-'0';
	else break;
	}
	if(len > pos) {state = -1;continue;};
	if(FT(num) == -1) {state = -1;continue;};
	}
	else if(ch[0] == 'F' and ch[1] == 'F')
	{
	int pos = 3;
	if(len < 3) {state = -1;continue;};
	for( ; pos < len; pos += 1)
	{
	if(ch[pos] <= '9' and ch[pos] >= '0')
	num = num*10+ch[pos]-'0';
	else break;
	}
	if(len > pos) {state = -1;continue;};
	if(FF(num) == -1) {state = -1;continue;};
	}
	else if(ch[0] == 'F' and ch[1] == 'E')
	{
	if(FE() == -1) {state = -1;continue;};
	}
	else if(ch[0] == 'W' and ch[1] == 'T')
	{
	int pos = 3;
	if(len < 3) {state = -1;continue;};
	for( ; pos < len; pos += 1)
	{
	if(ch[pos] <= '9' and ch[pos] >= '0')
	num = num*10+ch[pos]-'0';
	else break;
	}
	if(len > pos) {state = -1;continue;};
	if(WT(num) == -1) {state = -1;continue;};
	}
	else if(ch[0] == 'W' and ch[1] == 'G')
	{
	int pos = 3;
	if(len < 3) {state = -1;continue;};
	for( ; pos < len; pos += 1)
	{
	if(ch[pos] <= '9' and ch[pos] >= '0')
	num = num*10+ch[pos]-'0';
	else break;
	}
	if(len > pos) {state = -1;continue;};
	if(WG(num) == -1) {state = -1;continue;};
	}
	else if(ch[0] == 'E' and ch[1] == 'N' and ch[2] == 'D')
	{
	flag = true; continue;
	}
	}
	if(!flag and state != -1)
	{
	cout << "ERROR\n";
	cout << x-1 << ' ' << y-1 << '\n';
	cout << kill << '\n';
	cout << gundir << ' ' << robodir << ' '
	<< heavyrest << ' ' << lightrest << '\n';
	}
	else if(state == -1)
	{
	cout << "ERROR\n";
	cout << data.x-1 << ' ' << data.y-1 << '\n';
	cout << data.kill << '\n';
	cout << data.gundir << ' ' << data.robodir << ' '
	<< data.heavyrest << ' ' << data.lightrest << '\n';
	}
	else
	{
	cout << "Complete\n";
	cout << x-1 << ' ' << y-1 << '\n';
	cout << kill << '\n';
	cout << gundir << ' ' << robodir << ' '
	<< heavyrest << ' ' << lightrest << '\n';
	}
	}
	string ch;
	auto init() -> void
	{
	rest = lightrest = heavyrest = 0;
	robodir = gundir = kill = 0;
	state = 1;
	memset(Hp, 0, sizeof(Hp));
	memset(magezine, 0, sizeof(magezine));
	}
	auto FT(int x) -> int
	{
	if(x != 0 and x != 1) return -1;
	if(x == 0) (gundir += 1) %= 4;
	if(x == 1) (gundir += 3) %= 4;
	return 1;
	}
	auto FF(int i) -> int
	{
	if(i != 0 and i != 1) return -1;
	if(rest == limit) return -1;
	if(i == 0)
	{
	if(lightrest == 0) return 1;
	lightrest -= 1;
	magezine[++rest] = 0;
	}
	if(i == 1)
	{
	if(heavyrest == 0) return 1;
	heavyrest -= 1;
	magezine[++rest] = 1;
	}
	return 1;
	}
	auto FE() -> int
	{
	if(rest == 0) return 1;
	int nx = x, ny = y, type = magezine[rest--]+1;
	while(1)
	{
	nx += dx[gundir];
	ny += dy[gundir];
	if(nx < 1 or nx > n) return 1;
	if(ny < 1 or ny > m) return 1;
	if(Hp[nx][ny] == 1)
	{
	kill += 1;
	Hp[nx][ny] = 0;
	return 1;
	}
	else if(Hp[nx][ny] == 2)
	{
	Hp[nx][ny] -= type;
	if(Hp[nx][ny] == 0) kill += 1;
	return 1;
	}
	else if(Hp[nx][ny] > 3)
	return 1;
	}
	return 1;
	}
	auto WT(int x) -> int
	{
	if(x != 0 and x != 1) return -1;
	if(x == 0) (robodir += 1) %= 4;
	if(x == 1) (robodir += 3) %= 4;
	return 1;
	}
	auto WG(int t) -> int
	{
	for(int i = 1; i <= t; i += 1)
	{
	x += dx[robodir];
	y += dy[robodir];
	if(Hp[x][y] != 0 or x < 1 or x > n or y < 1 or y > m)
	return -1;
	}
	return 1;
	}
	auto END() -> int
	{
	return 1145141919;
	}
	auto record() -> void
	{
	for(int i = 1; i <= rest; i += 1)
	data.magezine[i] = magezine[i];
	data.rest = rest;
	data.lightrest = lightrest;
	data.heavyrest = heavyrest;
	data.robodir = robodir;
	data.gundir = gundir;
	data.x = x;
	data.y = y;
	data.kill = kill;
	data.state = state;
	}

# Or Plus Max

# 题目描述

有一个长度位 $2^n$ 的数列 $A$ , 编号为 $0, 1, 2...2^{n}-1$ 。对于每一个 $k(0 < k < 2^n)$ , 求 $\max(a_i, a_j),(i \,or\, j，\le k , i \not= j )$ , or 为按位或运算。

# 解题思路

我们在枚举 $k$ 时已经知道了小于 $k$ 的所有答案，这是我们只需要枚举按位或等于 $k$ 的两个数，和与之前答案取较大值即可。
由于按位或的性质，我们可以通过枚举子集的方式找到两个数，在枚举子集时记录下最大值次大值，答案的候选值即为最大值与次大相加。
当然直接枚举子集的时间复杂度是我们所不能接受的，所以我们不需要枚举所有子集，因为有的子集被其他子集所包含，所有一次只扣掉一个 $1$ 也是个不错的选择。

	#include<iostream>
	#include<cstdio>
	#define lowbit(i) (i&(-i))
	using namespace std;
	const int MAXN = 525010;
	int n, a[MAXN], ans;
	int smax[MAXN], kmax[MAXN], cnt[MAXN], id[MAXN];
	auto prework() -> void;
	auto calc(int k) -> int;
	auto solve(int x) -> void;
	int main()
	{
	scanf("%d", &n); n = (1<<n)-1;
	for(int i = 0; i <= n; i += 1)
	scanf("%d", &a[i]); prework();
	for(int i = 1; i <= n; i += 1)
	{
	ans = max(ans, calc(i));
	printf("%d\n", ans);
	}
	return 0;
	}
	auto prework() -> void
	{
	smax[0] = a[0]; ans = a[0];
	for(int i = 1; i <= n; i += 1)
	{
	smax[i] = a[i]; id[i] = i;
	cnt[i] = 1; solve(i);
	}
	}
	auto solve(int x) -> void
	{
	int k = x, p, now;
	while(k)
	{
	p = x-lowbit(k); now = smax[p];
	if(now > smax[x])
	{
	kmax[x] = smax[x]; smax[x] = now;
	cnt[x] = cnt[p]; id[x] = id[p];
	}
	else if(now == smax[x]){
	if(id[p] != id[x]) cnt[x] += 1;
	}
	else kmax[x] = max(kmax[x], now);
	k -= lowbit(k);
	}
	}
	auto calc(int x) -> int
	{
	if(cnt[x] >= 2) return smax[x]*2;
	return smax[x] + kmax[x];
	}

# LEGOndary Grandmaster

# 题目描述

对于两个长度为 $n$ 的 01 串 $s,t$ ，你可以对 $s$ 进行两种操作：把相邻两个 $0$ 变成 $1$ 或把相邻两个 $1$ 变成 $0$ ，定义 $s$ 到 $t$ 的距离为最少操作次数使得 $s$ 变成 $t$ ，如过没法变则距离为 $0$ 。

现在你有两个不完整的字符串，可以把其中的 ? 变成 $0$ 或 $1$ ，求所有情况所得到的两个 01 串的距离之和。

# 解题思路

对 00 和 11 操作有点不好搞，我们转化一下，对于所有奇数位（偶数位也可以）的数字进行翻转，我们的操作就变成把 01 变成 10 和把 10 变成 01 ，可以看作交换两个数字。由此一来就好搞多了。
对于交换两个相同的数，显然是浪费操作的不优解，因此并不会有这种情况。
首先，两个串 $0$ 和 $1$ 的个数不相同肯定无解。
我们的新目标是，求所有第 $k$ 个 $1$ 的位置的差的和。
因为有 ? 的存在，我们考虑每一个 $1$ 的贡献，用 DP 转移，记 $pre_{i, j}$ 为串的前缀 $1$ ~ $i$ 中， $1$ 的个数差为 $j$ 的方案数， $f_{i, j}$ 为方案之和。
通过下一位的 $0$ 或 $1$ 的取值，我们可以将 $pre_{i, j}$ 转移到 $pre_{i+1,j+1}, pre{i+1,j}, pre{i+1,j-1}$ ，将方案数求和存在 $f$ 里。
因为 $j$ 可能为负数，我们可以整体加上一个数变成非负的就方便转移了。

	#include<iostream>
	#include<cstring>
	#include<cstdio>
	#define _(x) (x+N)
	#define abs(x) (x<0?-x:x)
	using namespace std;
	const int p = 1e9+7;
	const int N = 2e3+0;
	const int MAXN = 2e3+10;
	const int MAXA = MAXN<<1;
	int T, n, a[MAXN], b[MAXN];
	int pre[MAXN][MAXA], f[MAXN][MAXA];
	char s[MAXN];
	auto work() -> void;
	int main()
	{
	scanf("%d", &T);
	while(T--) work();
	return 0;
	}
	auto prework(int *A) -> void
	{
	for(int i = 1; i <= n; i += 1)
	{
	if(s[i] == '?') A[i] = -1;
	else A[i] = s[i]-'0';
	}
	for(int i = 1; i <= n; i += 2)
	if(A[i] != -1) A[i] = !A[i];
	}
	inline auto check(int a, int x) -> bool
	{
	return (a == -1) or (a == x);
	}
	auto work() -> void
	{
	scanf("%d", &n);
	scanf("%s", s+1), prework(a);
	scanf("%s", s+1), prework(b);
	pre[0][N] = 1;
	for(int i = 1; i <= n; i += 1)
	for(int j = -n; j <= n; j += 1)
	for(int x = 0; x < 2; x += 1)
	for(int y = 0; y < 2; y += 1)
	if(check(a[i], x) and check(b[i], y))
	(pre[i][_(j+x-y)] += pre[i-1][_(j)]) %= p;
	for(int i = 1; i <= n; i += 1)
	for(int j = -n; j <= n; j += 1)
	for(int x = 0; x < 2; x += 1)
	for(int y = 0; y < 2; y += 1)
	if(check(a[i], x) and check(b[i], y))
	(f[i][_(j+x-y)] += ((long long)abs(j)*pre[i-1][_(j)]+f[i-1][_(j)])%p) %= p;
	printf("%d\n", f[n][N]);
	for(int i = 1; i <= n; i += 1)
	for(int j = -n; j <= n; j += 1)
	f[i][_(j)] = pre[i][_(j)] = 0;
	}

总结

# Trees

# 题目描述

# 解题思路

# bridge

# 题目描述

# 解题思路

# flowers

# 题目描述

# 解题思路

# robo

# 题目描述

# 做题思路

# Or Plus Max

# 题目描述

# 解题思路

# LEGOndary Grandmaster

# 题目描述

# 解题思路

NOIP模拟赛总结Ⅰ

NOIP模拟赛总结Ⅲ