这清华集训打得有点萎，这几天就来更一下题解好了。感想就不写了 代码写的比较惨，就不贴了
Alice和Bob又在玩游戏
关键词：SG函数，Trie的合并
题目描述
有个节点，条边（），构成若干棵有根树，每棵树的根节点是该连通块内编号最小的点。
Alice和Bob轮流操作（Alice先手），每回合选择一个没有被删除的节点，将及其所有祖先全部删除，不能操作的人输。
需要注意的是，树的形态是在一开始就确定好的，删除节点不会影响剩余节点父亲和儿子的关系。
比如： 这样一条链，号点是根节点，删除号点之后，号点还是号点的父节点。
假设Alice和Bob都足够聪明，问Alice有没有必胜策略。
对于的数据，，输入数据保证不会形成环，且每棵树的大小。
算法简述
这个题其实今年集训队作业里是有的，只是这里的数据范围大了一些。考虑用SG函数，表示以为根的子树的SG值。 这样直接搞的复杂度是，可以用来维护sg值和求mex操作，合并子树的时候可以用的合并。复杂度或
魔法小程序
关键词：高维前缀和
题目描述
有这样一段魔法的程序：（其中所有的数组下标从 开始，所有的除法的结果为整数，且向 取整）
定义数组 a[], b[], c[]
定义函数 魔法(x, y, z):
{
如果 a 的长度 == z:
返回 x >= y
如果 x % a[z] < y % a[z]:
返回 假
返回 魔法(x / a[z], y / a[z], z + 1)
}
定义函数 主程序():
{
读入 a[], b[]
令 c[] 的长度与 b[] 的长度相同，且 c[] 的每个元素均为 0
令 变量 i 从 0 循环至 b 的长度 - 1:
令 变量 j 从 0 循环至 i:
如果 魔法(i, j, 0):
c[i] += b[j]
输出 a[], c[]
}
这个程序目前十分低效（显然时间复杂度至少是平方量级的），无法快速完成百万级别的计算，但我们现在的任务不仅是优化它。
现在我们给出这段程序的输出，你需要完成一个“非确定机”的工作，给出一个可能的输入。
的长度不会超过 。 的每一个元素不会超过 。
的长度不会超过 。对 的元素的范围没有直接的保证，但是保证存在一个解 ，使得 的每一个元素的绝对值都不超过 。
和 都至少拥有一个元素。
算法简述
这个题第一眼看起来，解应该只有一个，因为可以解个方程算出来。再看一看，发现这个东西和的比较像，这其实就是一个高维的前缀和。就可以反过来搞，对每一维分开来求差分，最后就能还原出来了。要注意细节问题。
数据交互
关键词：树链剖分
题目描述
一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。每个数据交互请求都有一个非负的重要度，越重要的请求显然需要得到越高的优先处理权。此外，如果在某一个时刻存在一条非常重要（可以看作重要度无穷大）、且数据量巨大的交互请求，则所有被该交互经过的服务器都会优先处理这条交互并阻塞，从而导致其他通过这些服务器的交互出现延迟。
现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也很简单，在每一个时刻，只有可能出现下列二种事件中的一种：
- 在某两个服务器之间出现一条新的数据交互请求；
- 某个数据交互请求结束。 我们假设这些事件中的交互请求的数据量都足够小。
你的任务是在每一个时刻的事件结束后，求出：如果突然出现一条非常重要、且数据量巨大的交互请求，那么因其造成延迟的数据交互请求的重要度之和最大可能是多少？
算法简述
这个题的idea我感觉还是挺不错的。首先把每个边都拆出点来。每一次添加数据交互请求就相当于给路径上所有边点都减去权值，点点都加上权值。每次要求的答案就相当于这个树的直径。这样就变成了，链修改，求直径的问题，可以套用Qtree7的做法，搞链剖，维护最高点在每一条重链上的最长的路径。这个题稍稍有点繁琐的地方在于，一条路径上的点有两种，点点和边点交替出现，每次修改的时候，边点和点点的加的值正好相反。那么就可以在线段树上多维护一些信息，把起点终点是点点和边点的分开来维护，就可以了。
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
ArcadeManao
关键词：并查集
题目简述
很久很久以前，有一个的网格，其中有一些格子上是可以停留的，有一些是悬空的。
这是一个有重力存在的世界。
有一个可爱的小朋友，他现在在网格的底部（保证底部的每一个格子都是可以停留的），需要到达一个特定的可停留的格子。
现在有两种移动方式：左右移动和上下移动。
左右移动：左右紧挨的两个格子，如果都可以停留，就可以在这两个格子之间自由移动。
上下移动：同一条竖直线上的两个可停留的格子（可以不紧挨）可以互相移动，不过你需要拥有一
把长度至少为两个格子纵坐标之差的绝对值的梯子。
梯子可以重复使用，问从网格底部到达目标点，需要的梯子的最短长度。
算法简述
可以暴力枚举答案，然后用并查集判断
一点点小代码
const int N = 60;
int n, m;
int id[N][N], a[N][N];
int f[N * N];
int x, y;
int get(int a) {
if (a == f[a]) return a;
return f[a] = get(f[a]);
}
int join(int a, int b) {
f[get(a)] = get(b);
}
bool check(int H) {//判断梯子的长度不超过H的时候是否有解
REP(i, 1, n * m) f[i] = i;
REP(i, 1, n) REP(j, 1, m - 1) if (a[i][j] && a[i][j + 1]) join(id[i][j], id[i][j + 1]);
REP(i, 1, n) REP(j, 1, m) REP(k, 1, min(n - i, H))
if (a[i][j] && a[i + k][j]) join(id[i][j], id[i + k][j]);//用并查集判断
return get(id[n][1]) == get(id[x][y]);//如果起点和终点在一个连通块里就可以
}
class ArcadeManao {
public:
int shortestLadder(vector<string> level, int X, int Y) {
x = X, y = Y;
n = level.size(); m = level[0].size();
int tot = 0;
REP(i, 1, n) REP(j, 1, m) id[i][j] = ++tot;
REP(i, 1, n) REP(j, 1, m) a[i][j] = (level[i - 1][j - 1] == 'X');
REP(i, 0, n) if (check(i)) return i;//从小到大枚举答案
}
};
CountPlacements
关键词：动态规划
算法简述
显然，每个海绵能够接到的水滴一定是连续的一段，所以的思路是从左往右把这些水龙头切成一段又一段，分给各个脸盆（当然也可以落到地面上）。
我们考虑怎样的切割方法是合法的。
首先，以被浪费的水龙头为界，将没有被浪费的水龙头分成了若干块（每一块是连续的一段没有被浪费的水龙头），各块互相独立。每一块被该块内部接水区间紧挨的若干个脸盆瓜分。每一块内部一定存在一个高度最高的脸盆（废话），它不被任何其他脸盆所阻挡，于是正好能够接住个水龙头的。这一块内部的其他脸盆，接到的部分长度都小于等于（废话，总共也就那么长）。而且只要满足以上条件，方案一定能够实现，因为只要确定了那么正好接住个水龙头的最高的脸盆，其余脸盆都可以以阶梯状从中心向两边排出任何你想要的区间。
于是。区间切割分配的方案(也就是要求的方案)合法当且仅当每一个联通块(紧挨即联通)内部都至少存在一个区间长度正好为，且其他的长度均小于等于。
一点点小代码
const int N = 610;
int f[N][N][3];
int s[N];
int a[N], n, m;
int A, B, L;
class TheExperiment {
public:
int countPlacements(vector<string> intensity, int M, int L, int A, int B) {
n = 0, m = M;
REP(i, 0, intensity.size() - 1) REP(j, 0, intensity[i].size() - 1) a[++n] = intensity[i][j] - '0';
::A = A, ::B = B;
::L = L;
REP(i, 1, n) s[i] = s[i - 1] + a[i];
CL(f, 0);
f[0][0][0] = 1;
REP(i, 1, n) {
REP(j, 0, m) {
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][2]) % mo; // 要么是前面也是空的，要么是前面是组好的一段
if (j) {
PER(k, i - 1, max(0, i - L + 1)) if (s[i] - s[k] <= B && s[i] - s[k] >= A) // 枚举这一段的长度
f[i][j][1] = ((f[i][j][1] + f[k][j - 1][1]) % mo + f[k][j - 1][0]) % mo;//有可能是新的一个连续段
PER(k, i - 1, max(0, i - L + 1)) if (s[i] - s[k] <= B && s[i] - s[k] >= A) // 枚举这一段的长度
f[i][j][2] = (f[i][j][2] + f[k][j - 1][2]) % mo;//有可能是新的一个连续段
if (i >= L && s[i] - s[i - L] >= A && s[i] - s[i - L] <= B) { // 这一段长度为L
f[i][j][2] = (f[i][j][2] + f[i - L][j - 1][2]) % mo;
f[i][j][2] = (f[i][j][2] + f[i - L][j - 1][1]) % mo;
f[i][j][2] = (f[i][j][2] + f[i - L][j - 1][0]) % mo;
}
}
}
}
int ans = 0;
REP(i, 1, n) ans = (ans + f[i][m][2]) % mo;
return ans;
}
};
CharacterBoard
关键词：数学
题目简述
很久很久以前，有一个活泼可爱的小朋友，他拥有一个棋盘，行从上至下以编号，列从左至右以编号。
后来，有一个长者给了他一个长度为的字符串，并让小朋友以以下伪代码去填充这个棋盘。
int cursor = 0;
for (int i = 0; i < 1000000000; i++)
for (int j = 0; j < W; j++) {
a[i][j] = s[cursor];
cursor = (cursor + 1) % L;
}
接着，小朋友在大棋盘中取出一个以为左上角，行数为，列数为的子矩阵。
现在已知取出的子矩阵，而对于那个用于循环节的字符串，连长度都不知道，更别提内容了，只知道只含有小写字母。小朋友想要猜出这个字符串究竟是啥。
于是问你有多少种可能的字符串
算法简述
首先可以考虑枚举字符串长度，然后判一下长度为的时候是否合法并且有多少种不同的方案。发现大多数时候，字符并不会循环出现，那么方案就是.什么时候会在矩阵中出现重复的位置呢，当且仅当两个位置的差正好是的倍数的时候。这样只要暴力枚举会重复的位置，去分解一下，就可以计算出所有可能导致重复的, 因为棋盘的大小有限所以两两位置的差最多只有种。
一点小代码
int w;
LL id(int x, int y) {
return 1LL * w * x + y; //计算一个元素的位置
}
map<LL, char> S;
set<LL> A;
vector<LL> v[255]; //把所有相同的字符放在一起
int n, m;
void frac(LL x) { //寻找x的所有因子
if (A.find(x) != A.end()) return; //总共不同的差的数量不会超过100
for (LL i = 1; i * i <= x; ++i) if (x % i == 0) {
A.insert(i);
if (i * i != x) A.insert(x / i);
}
}
int check(LL x) {//计算S长度为x的时候的合法的S的数量
static map<LL, char> C; C.clear();
for (map<LL, char> ::iterator it = S.begin(); it != S.end(); ++it) {
if (C.find(it -> FR % x) == C.end()) C[it -> FR % x] = it -> SC;
else if (C[it -> FR % x] != it -> SC) return 0;
}
return pow(26, (int)x - (int)C.size());
}
class CharacterBoard {
public:
int countGenerators(vector<string> fragment, int W, int i0, int j0) {
S.clear();
A.clear();
w = W;
n = fragment.size(), m = fragment[0].size();
REP(i, 0, n - 1) REP(j, 0, m - 1)
S[id(i + i0, j + j0)] = fragment[i][j];
int ans = 0;
if (W >= n * m)
ans = 1LL * (pow(26, W - n * m + 1) - 1 + mo) % mo * pow(25, mo - 2) % mo; //先计算不会产生重叠部分的答案
for (map<LL, char> ::iterator it = S.begin(); it != S.end(); ++it)
for (map<LL, char> ::iterator it2 = it; it2 != S.end(); ++it2) {//枚举所有两两重叠的时候可能的S的长度
if ((*it) == (*it2)) continue;
frac(it2 -> FR - it -> FR);
}
for (set<LL> ::iterator it = A.begin(); it != A.end(); ++it) {
if (*it > W) break;
int tmp = check(*it);
ans = (ans + tmp) % mo;
if ((*it) >= n * m) ans = (ans - pow(26LL, (*it) - n * m) + mo) %mo; //如果长度大于n * m那么就要把之前的计算给减去
}
return ans;
}
};
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
EelAndRabbit
关键词：离散化，暴力
算法简述
实际上, 我们只需要考虑所有形如 以及 的时刻 就可以了. 如果我们抓鱼的时间不能表示成这两种形式之一的话, 我们可以通过改变时间 调整到这两种形式.
因此我们不妨枚举两次抓鱼的时刻 和 , 然后统计有多少条鱼能被抓上来, 并求出鱼的数量的最大值.
一点点小代码
vector<int> v;
bitset<51> flag[101]; //表示在第i个关键点抓能抓到的集合
class EelAndRabbit {
public:
int getmax(vector<int> l, vector<int> t) {
int n = l.size();
v.clear();
REP(i, 0, n - 1) v.PB(t[i]), v.PB(t[i] + l[i]); //先离散化 找出关键点
int ans = 0;
REP(i, 0, v.size() - 1) {
flag[i].reset();
REP(k, 0, n - 1)
if (t[k] <= v[i] && v[i] <= t[k] + l[k]) flag[i][k] = 1; // 找到能抓到的集合
}
REP(i, 0, v.size() - 1)
REP(j, i, v.size() - 1) get_max(&ans, (int)(flag[i] | flag[j]).count()); //枚举两个时间点
return ans;
}
};
ShoutterDiv1
关键词：贪心， 图论
算法简述
设 为 最小的元素, 为 最大的元素, 那么 的消息被看到当且仅当这则消息被 和 都看到了.
这样的话我们可以从 开始 BFS, 找到 到 和 的最短传播距离, 然后用 来更新 .
注意, 这里有一种特殊情况: 到 的路径与 到 的路径可能有交. 但是我们可以发现, 这种情况一定是先由 传到 (), 再由 传到 和 , 也就是说传播路径可能是 Y 字形. 因此我们还要枚举所有可能的 , 并用 更新 .
一点点小代码
const int N = 2600;
int f[N];
PII a[N];
int l[N], r[N];
bool el[N], er[N];
int n;
bool cmp(const PII &A, const PII &B) {
return A.SC - A.FR > B.SC - B.FR;
}
bool intersect(int x, int y) {
return a[x].SC <= a[y].SC && a[x].SC >= a[y].FR;
}
int calcL(int x) {
int res = 0;
while (!el[x]) {
if (x == l[x]) return -1;
x = l[x]; ++res;
}
return res;
}
int calcR(int x) {
int res = 0;
while (!er[x]) {
if (x == r[x]) return -1;
x = r[x]; ++res;
}
return res;
}
class ShoutterDiv1 {
public:
int count(vector<string> s1000, vector<string> s100, vector<string> s10, vector<string> s1, vector<string> t1000, vector<string> t100, vector<string> t10, vector<string> t1) {
CL(el, 1); CL(er, 1);
CL(l, 0); CL(r, 0);
REP(i, 1, s1.size() - 1) s1000[0] += s1000[i], s100[0] += s100[i], s10[0] += s10[i], s1[0] += s1[i];
REP(i, 1, s1.size() - 1) t1000[0] += t1000[i], t100[0] += t100[i], t10[0] += t10[i], t1[0] += t1[i];
n = s1[0].size();
REP(i, 1, n) a[i].FR = (s1000[0][i - 1] - 0) * 1000 + (s100[0][i - 1] - '0') * 100 + (s10[0][i - 1] - '0') * 10
+ s1[0][i - 1] - '0';
REP(i, 1, n) a[i].SC = (t1000[0][i - 1] - 0) * 1000 + (t100[0][i - 1] - '0') * 100 + (t10[0][i - 1] - '0') * 10
+ t1[0][i - 1] - '0';
sort(a + 1, a + n + 1, cmp);
REP(i, 1, n)
REP(j, 1, n) {
if (a[j].FR > a[i].SC) er[i] = 0;
if (a[j].SC < a[i].FR) el[i] = 0;
}
REP(i, 1, n) {
l[i] = r[i] = i;
REP(j, 1, n) if (a[j].FR <= a[i].SC && a[j].SC > a[r[i]].SC) r[i] = j;
REP(j, 1, n) if (a[j].SC >= a[i].FR && a[j].FR < a[l[i]].FR) l[i] = j;
}
int ans = 0;
REP(i, 1, n) {
f[i] = 1e9;
REP(j, 1, i - 1) if (a[j].FR <= a[i].FR && a[j].SC >= a[i].SC) getmin(&f[i], f[j] + 1);
int fl = calcL(i), fr = calcR(i);
if (fl == -1 || fr == -1) return -1;
getmin(&f[i], fl + fr);
ans += f[i];
}
return ans;
}
};
WallGameDiv1
关键词：博弈, 动态规划, 记忆化搜索
题目简述
Rabbit 和 Eel 在玩一个游戏. 游戏在一个 的棋盘上进行, 在这个游戏中, 玩家需要操作一个棋子, 将它从第一行移动到最后一行(当棋子被移动到最后一行时, 游戏立刻结束). 在第 行第 列有一个数字 , 表示经过这个格子的代价.
游戏由若干轮组成. 每一轮由 Rabbit 先操作. 在第一轮, Rabbit 会把一个棋子放在第一行的某一列上, 并付出相应的费用. 在接下来的每一轮中, Rabbit 先把棋子向左, 向右, 或向下移动一步, 然后付出相应的费用. 然后由 Eel 操作. Eel 可以选取一对 , 其中 并且 , 然后在 和 之间修建一堵墙. Eel 每次操作可以修建任意多的墙, 但是在任意时刻, Eel 修建的墙都不能够使游戏无法结束(也就是说, Eel 修建的墙不能阻止棋子从当前的位置移动到最后一行).
Rabbit 的目标是最小化花费, 而 Eel 的目标是最大化 Rabbit 的花费. 现在假设双方都绝顶聪明, 你需要求出最后的花费.
注意: 多次经过同一个位置的花费算多次.
算法简述
首先注意到两个结论:
- Eel 一定是等 Rabbit 走到某个位置下面, 再决定是否放墙;
- 如果 Eel 没有在 Rabbit 的下面放墙, 那么 Rabbit 一定要走下去.
于是我们可以得到一个推论: 每一行的墙的位置一定是连续的.
接下来我们可以设 表示当前在第 行, 表示有墙的列的编号为, 当前棋子的位置是 ; 表示有墙的列的编号为, 当前棋子的位置是 .
转移时只需要枚举 Eel 是否要在当前位置下面修墙, 如果修墙的话 Rabbit 是从当前位置走到 更好还是走到 更好, 就可以了.
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
TheTree
关键词：数学
算法简述
枚举一下直径的两个端点的深度，然后判一下就可以了
一点点小代码
int a[100];
class TheTree {
public:
int maximumDiameter(vector<int> cnt) {
int ans = 0;
int n = cnt.size();
REP(i, 0, n - 1) a[i + 1] = cnt[i];
a[0] =1;
REP(i, 0, n ) {
int r = i;
PER(j, i, 0) if (a[j] == 1) {
r = j;
break;
}
if (a[i] > 1) getmax(&ans, 2 * i - 2 * r);
REP(j, i + 1, n) getmax(&ans, j + i - 2 * r);
}
return ans;
}
};
PyramidSequences
关键词：数学
算法简述
这题其实挺恶心的，好多部分是否重复根本想不清楚，不过代码还是很好写的。式子也就一行
一点点小代码
class PyramidSequences {
public:
long long distinctPairs(int N, int M) {
LL d = __gcd((LL)N - 1, (LL)M - 1);
return 1LL * (d-1) * ((N-1)/d) * ((M-1)/d) + 1LL * ((1+(N-1)/d)*(1+(M-1)/d)+1)/2; //只要一行式子就可以了
}
};
StringPath
关键词：dp
题目简述
给你 的方阵，你要给每个格子都填上一个小写字母，使得从左上角到右下角存在两条不走弯路的路径恰好为字符串A和字符串B.
算法简述
这种题一看就无脑状压DP一波.. 表示一下轮廓线上每个位置的状态，要么是不合法的，要么是能作为A的结尾，要么是能作为B的结尾。稍微优化一下就能过了。
一点小代码
const int N = 10;
struct node { //dp状态
int x, y; //目前已经dp到了(x, y)
string s; //目前上面一列的状态 0 代表都不行 1代表可以作为A的结尾 2代表可以作为B的结尾
node() {}
node (int _x, int _y, string _s): x(_x) , y(_y), s(_s) {}
};
bool operator < (const node &A, const node &B) {
if (MP(A.x, A.y) == MP(B.x, B.y)) return A.s < B.s;
return MP(A.x, A.y) < MP(B.x, B.y);
}
map<node, int> S; //用map来记录所有状态
void add(char &x, int a) { //把这个位置打上标记 说明可以放a
if (x == '3') return;
if (x - '0' == a) return;
x += a;
}
bool check(string &x, int k, int a) { //检查位置k是否能作为a的结尾
if (k < 0) return false;
if (x[k] == '3') return true;
return x[k] - '0' == a;
}
queue<node> q;
class StringPath {
public:
int countBoards(int n, int m, string A, string B) {
if (A[0] != B[0]) return 0;
int ans = 0;
while (!q.empty()) q.pop();
S.clear();
string s,zero;
REP(i, 0, m - 1) s.PB('0'), zero.PB('0');
s[0] = '3';
q.push(node(0, 0, s));
S[node(0, 0, s)] = 1; //初始状态
while (!q.empty()) {
node now = q.front(); q.pop();
int i = now.x, j = now.y;
++j; if (j >= m) ++i, j = 0;
int tmp = S[now];
if (i >= n) { //已经dp完了
if (now.s[m - 1] == '3')
ans = (ans + tmp) % mo;
continue;
}
int zz = 0;
REP(c, 'A', 'Z') { //枚举这个位置所填的字母
if (c != A[i + j] && c != B[i + j]) { //如果发现这个字符一定不行 就留到最后一起处理
++zz;
continue;
}
string s = now.s;
char r = '0'; //r代表这个位置可以是哪些串的结尾
if (c == A[i + j] && (check(s, j - 1, 1) || check(s, j, 1))) add(r, 1);
if (c == B[i + j] && (check(s, j - 1, 2) || check(s, j, 2))) add(r, 2);
s[j] = r;
node nxt(i, j, s);
if (S.find(nxt) == S.end()) //如果还没有这个状态就加进去
q.push(nxt);
S[nxt] = (S[nxt] + tmp) % mo;
}
string s = now.s;
s[j] = '0';
node nxt(i, j, s);
if (S.find(nxt) == S.end())
q.push(nxt);
S[nxt] = (S[nxt] + 1LL * tmp * zz % mo) % mo; //最后处理那些这个位置填0的串，优化常数
}
return ans;
}
};
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
TomekPhone
关键词：贪心
算法简述
可以把所有键的权给搞出来，然后排个序，贪心就可以了。
一点点小代码
class TomekPhone {
public:
int minKeystrokes(vector<int> A, vector<int> B) {
vector<int> C;
C.clear();
sort(A.begin(), A.end(), greater<int>());
REP(i, 0, B.size() - 1) REP(j, 1, B[i]) C.PB(j);
sort(C.begin(), C.end());
int ans = 0;
REP(i, 0, A.size() - 1) {
if (i >= C.size()) return -1;
ans += A[i] * C[i];
}
return ans;
}
};
DrawingPointsDivOne
关键词：DP，数学
算法简述
这个题目还是有点妙的。会发现，每个点都放在中间和每个点都放在左下角的情况是一样的，因为点与点之间的相对位置是一样的。那么问题就转化成，填一些点，让每个点作为一个k*k的正方形的左下角，且不存在其他点满足这个条件。那么就可以枚举k或者二分，然后用dp验证了。
一点点小代码
const int N = 400;
int f[N * 2][N * 2];
int a[N * 2][N * 2];
int n, x[N], y[N];
int dp(int l) { //dp 判断步数为l是否可行
CL(a, 0);
CL(f, 0);
REP(i, 1, n) {
REP(j, x[i] - l, x[i])
REP(k, y[i], y[i] + l) { //把每个点都摆在一个大小为k * k的正方形的左下角
a[j][k] = 1;
}
}
int cnt = 0;
REP(i, 0, 600)
REP(j, 0, 600) if (a[i][j]) {
f[i][j] = min(min(f[i - 1][j - 1], f[i][j - 1]), f[i - 1][j]) + 1; //计算总共有多少点是一个大小为k * k的正方形的一个角
cnt += (f[i][j] > l);
}
return cnt;
}
class DrawingPointsDivOne {
public:
int maxSteps(vector<int> X, vector<int> Y) {
n = X.size();
REP(i, 1, n) x[i] = X[i - 1] + 300, y[i] = Y[i - 1] + 300; //把坐标平移到正的地方
int l = 0, r = 141, res = 0;
while (l <= r) { //二分答案
int mid = (l + r) >> 1;
if (dp(mid) == n) res = mid, l = mid + 1;
else r = mid - 1;
}
if (res == 141) return -1; //如果答案超过了140就说明肯定存在无限大小的步数
return res;
}
};
BoundedOptimization
关键词：数学
题目简述
给定一个多项式，且每一项都是两个变量的乘积。给定每个变量共同的取值范围[l, r]， 这个多项式的最大值。
变量数不超过13
算法简述
这题非常有意思。可以把这个变量看成点，两个变量的乘积就是一条边，现在要给点确定值，让边权和最大。因为n比较小，枚举有哪些点是取到最大值或最小值的。根据调整法可得，如果两个点不相邻且他们都没取到最值，那么把其中一个调成最值一定不会更劣，所以没取到最值的点就成了一个团。那么这个团里的值要怎么取呢，可以求个导看看，具体可以看代码的注释。
一点小代码
const int N = 20;
bool G[N][N]; //邻接矩阵
int M, a[N], n;//a[i]代表未被分配到极值的点i 与其相邻的极值点的点权和 M为非极值点的点权和
double f[N];
/*
* f[i]为每个点所分配的值
* 现在要最大化：sigma f[i] * (a[i] + M / 2 - f[i] / 2)
* 其中sigma f[i] * M / 2的值已经固定
* f[i] * a[i] - f[i] ^ 2 / 2 的导数是 a[i] - f[i]
* 根据拉格朗日乘数法可知一定存在一个数C, 满足
* a[i] - f[i] + c = 0
* 由于f[i]的和是M，这样就可以计算得到C的值了
*/
bool isClique(int S) {//判断一个集合是否构成了一个clique
REP(i, 0, n - 1) if (S & (1 << i))
REP(j, i + 1, n - 1) if (S & (1 << j))
if (!G[i][j]) return false;
return true;
}
class BoundedOptimization {
public:
double maxValue(vector<string> expr, vector<int> lowerBound, vector<int> upperBound, int maxSum) {
n = lowerBound.size();
REP(i, 1, expr.size() - 1) expr[0] += expr[i];
CL(G, 0);
for (int i = 0; i < expr[0].size(); i += 3)
G[expr[0][i] - 'a'][expr[0][i + 1] - 'a'] =
G[expr[0][i + 1] - 'a'][expr[0][i] - 'a'] = 1; //把相邻的点连边
double ans = 0;
REP(S, 0, (1 << n) - 1) { //枚举取到极值的点的集合
if (!isClique((1 << n) - 1 - S)) continue; //所有没取到极值的点要在一个团里面
for (int T = S; ; T = (T - 1) & S) { //枚举取到lowerbound的点
M = maxSum;
double tmp = 0;
int k = __builtin_popcount((1 << n) - 1 - S); //计算未被分配到值的点的个数
int sa = 0;
REP(i, 0, n - 1) if (S & (1 << i)) {
if (T & (1 << i)) f[i] = lowerBound[i];
else f[i] = upperBound[i];
M -= f[i];
}
if (M < 0) goto LOOP; //第一步分配不能超过上限
REP(i, 0, n - 1) {
if (S & (1 << i)) continue;
a[i] = 0;
REP(j, 0, n - 1) if (S & (1 << j)) if (G[i][j]) a[i] += f[j]; //a[i]代表与点i相邻的已经分配的点的权值和
sa += a[i]; //a[i]的和
}
REP(i, 0, n - 1) {
if (S & (1 << i)) continue;
f[i] = 1.0 * a[i] + 1.0 * M / k - 1.0 * sa / k; //根据导数计算每点应该分配的值
if (f[i] < 1.0 * lowerBound[i] || f[i] > 1.0 * upperBound[i]) goto LOOP;
}
REP(i, 0, n - 1)
REP(j, i + 1, n - 1) if (G[i][j]) tmp += f[i] * f[j];
getmax(&ans, tmp);
LOOP: if (!T) break;
}
}
return ans;
}
};
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
GooseInZooDivOne
关键词：并查集、图论
算法简述
这个题一看就是一个比较套路的题目，先把两之间距离小于dist的用并查集缩起来，然后数一下奇数集合的数量和偶数集合的数量，然后判一下就可以了。
一点点小代码
const int N = 51;
int id[N][N];
int f[N * N], cnt[N * N];
int get(int u) { //并查集
if (u == f[u]) return u;
return f[u] = get(f[u]);
}
void join(int u, int v) {
f[get(u)] = get(v);
}
class GooseInZooDivOne {
public:
int count(vector<string> field, int dist) {
int n = field.size(), m = field[0].size();
int tot = 0;
REP(i, 0, n - 1) REP(j, 0, m - 1) id[i][j] = ++tot;
REP(i, 1, tot) f[i] = i, cnt[i] = 0;
REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v')
REP(k1, 0, n - 1 ) REP(k2, 0, m - 1) if (k1 != i || k2 != j)
if (field[k1][k2] == 'v') if (abs(i - k1) + abs(j - k2) <= dist) join(id[i][j], id[k1][k2]);
//把两两之间距离小于dist的那些给放到一个集合中去
REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v') cnt[get(id[i][j])]++;
int ans1 = 0, ans2 = 0;
REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v' && f[id[i][j]] == id[i][j]) {
if (cnt[id[i][j]] & 1) ++ans1; //集合大小为奇数的集合个数
else ++ans2; //集合大小为偶数的集合个数
}
int ans = pow(2, ans1 + ans2 - (ans1 > 0)); //因为要满足goose的数目为偶数，所以奇数的那些集合只能选偶数个
return (ans - 1 + mo) % mo;//至少要有一个goose
}
};
WolfInZooDivOne
关键词：动态规划
算法简述
这个题目还是比较有意思的。首先考虑如果限制不是最多放两个而是最多放一个。那么就可以写一个这样的dp. 代表现在dp到第i个位置，这个区间里不放东西的方案数。具体的转移可以根据区间的左右端点来确定。那么受到这个思路的启发,可以写出一个这样的dp,, 其中k表示这个区间最多放一个东西。
一点点小代码
const int N = 310;
int f[2][N][N];// f[i][j][k]代表目前放了前i个位置，i到j位置都不能放wolf了， (j + 1)到k位置可以放一个wolf的方案数
PII a[N]; //所有的区间
int n, m, tmp;
stringstream fin;
class WolfInZooDivOne {
public:
int count(int N, vector<string> L, vector<string> R) {
fin.clear();
n = N;
REP(i, 1, L.size() - 1) L[0] += L[i];
REP(i, 1, R.size() - 1) R[0] += R[i];
fin << L[0];
m = 0;
while (fin >> tmp) a[++m].FR = tmp + 1;
fin.clear();
fin << R[0];
m = 0;
while (fin >> tmp) a[++m].SC = tmp + 1; //处理一下格式
sort(a + 1, a + m + 1);
CL(f, 0);
f[0][0][0] = 1;
int j = 1, c = 0, ans = 0, l = 0;
REP(i, 0, n - 1) {
c ^= 1; CL(f[c], 0); //滚动数组
while (j <= m && a[j].FR <= i + 1) getmax(&l, a[j].SC), ++j;//目前包含i + 1这个位置的最远的区间
REP(k1, 0, n)
REP(k2, k1, n) {
f[c][k1][k2] = (f[c][k1][k2] + f[c ^ 1][k1][k2]) % mo; //这个位置不放wolf
if (k1 < i + 1) f[c][k2][l] = (f[c][k2][l] + f[c ^ 1][k1][k2]) % mo; //这个位置放wolf
}
}
REP(i, 0, n)
REP(j, i, n) ans = (ans + f[c][i][j]) % mo;
return ans;
}
};
DeerInZooDivOne
关键词：动态规划，费用流，KM
题目简述
给出一个个点的树，让你从中选出两个连通子图，使得这两个子图同构。
算法简述
这个题看起来挺熟悉的，不知道哪里见到过。感觉这种题也没啥好做法，就是暴力搞，复杂度反正就是玄学。
首先要先枚举一条断边，把整个树分成两部分，然后枚举这两部分中选择的点（也就是枚举两个根）。然后开始搞dp，这个dp的过程中由于需要对儿子进行配对，所以还要搞一个KM，或者费用流也可以。在dp的过程中可以瞎jb记忆化来加速。大致就是代表两个点为根的最大值。
一点小代码
class ZKW { //ZKW费用流板子
public:
#define INF 1000000000
#define MAXN 100000
#define MAXM 100000
struct edge_node
{
int p,next;
int w,c;
}edge[MAXM];
int vis[MAXN],instack[MAXN];
int head[MAXN],slk[MAXN];
int d[MAXN];
int cur[MAXM];
int cnt,S,T,index,tot;
LL ans,flow;
void ae(int a,int b,int weight,int cost)
{
edge[++cnt].p=b; edge[cnt].w=weight;
edge[cnt].c=cost; edge[cnt].next=head[a]; head[a]=cnt;
edge[++cnt].p=a; edge[cnt].w=0;
edge[cnt].c=-cost; edge[cnt].next=head[b]; head[b]=cnt;
}
int aug(int u,int now)
{
if (u==T)
{
ans+=(LL)now*d[T];
flow+=now;
return now;
}
int res=0,tmp;
vis[u]=instack[u]=index;
for (int &k=cur[u];k;k=edge[k].next)
{
int v=edge[k].p;
int t=d[u]+edge[k].c-d[v];
if (edge[k].w)
{
slk[v]=min(slk[v],t);
if (!t&&instack[v]!=index)
{
tmp=aug(v,min(now,edge[k].w));
res+=tmp;
edge[k].w-=tmp;
edge[k^1].w+=tmp;
if ((now-=tmp)==0) break;
}
}
}
instack[u]=false;
return res;
}
bool modlabel()
{
int del=INF;
for (int i=1;i<=T;++i) if (vis[i]!=index)
del=min(del,slk[i]);
if (del==INF) return false;
for (int i=1;i<=T;++i) if (vis[i]!=index)
d[i]+=del;
return true;
}
LL MCMF(int _S, int _T, int returnflow = 0)
{
S = _S, T = _T;
flow=ans=0;
for (int i=1;i<=T;++i) d[i]=0;
do
do{
for (int i=1;i<=T;++i) slk[i]=INF,cur[i]=head[i];
++index;
}
while (aug(S,INF));while (modlabel());
if (returnflow) return flow;
return ans;
}
void init(int n) {
index = cnt = 1;
REP(i, 1, n + 2) head[i] = 0, vis[i] = -1;
}
}solver;
const int N = 53;
int n;
struct node {
int p, next;
bool flag;
}edge[N * 2];
int head[N], cnt;
void ae(int a, int b) {
edge[++cnt].p = b;
edge[cnt].next = head[a];
head[a] = cnt;
edge[cnt].flag = 1;
}
int f[N][N][N][N];
vector<int> X, Y;
void dfs(vector<int> &V, int u, int fa) {
V.PB(u);
RED(k, u) if (edge[k].flag){
int v = edge[k].p;
if (v != fa) dfs(V, v, u);
}
}
int dp(int a, int fa, int b, int fb) { //记忆化搜索
if (f[a][fa][b][fb] != -1) return f[a][fa][b][fb];
vector<int> X, Y;
RED(k, a) if (edge[k].flag && edge[k].p != fa)
X.PB(edge[k].p);
RED(k, b) if (edge[k].flag && edge[k].p != fb)
Y.PB(edge[k].p);
for (int i = 0; i < X.size(); ++ i)
for (int j = 0; j < Y.size(); ++j) dp(X[i], a, Y[j], b);
solver.init(X.size() + Y.size()); //费用流初始化
int S = X.size() + Y.size() + 1, T = S + 1;
for (int i = 0; i < X.size(); ++ i) solver.ae(S, i + 1, 1, 0); //最大权匹配
for (int i = 0; i < Y.size(); ++ i) solver.ae(i + 1 + X.size(), T, 1, 0);
for (int i = 0; i < X.size(); ++ i)
for (int j = 0; j < Y.size(); ++j) {
solver.ae(i + 1, j + X.size() + 1, 1, -f[X[i]][a][Y[j]][b]);
}
f[a][fa][b][fb] = -solver.MCMF(S, T) + 1; //最大费用流
return f[a][fa][b][fb];
}
int solve(int a, int b) {
CL(f, 0xff);
X.clear(); Y.clear();
dfs(X, a, 0);
dfs(Y, b, 0);
int ans = 0;
REP(i, 0, X.size() - 1)
REP(j, 0, Y.size() - 1) { //枚举两边树的根
getmax(&ans, dp(X[i], 0, Y[j], 0));
}
return ans;
}
class DeerInZooDivOne {
public:
int getmax(vector<int> a, vector<int> b) {
n = a.size() + 1;
cnt = 1;
CL(head, 0);
REP(i, 0, a.size() - 1) ae(a[i] + 1, b[i] + 1), ae(b[i] + 1, a[i] + 1); //连边
int ans = 0;
REP(i, 1, n) RED(k, i) { //枚举断掉的边
int j = edge[k].p;
if (i > j) continue;
edge[k].flag = 0;
edge[k ^ 1].flag = 0;
ans = max(ans, solve(i, j));
edge[k].flag = 1;
edge[k ^ 1].flag = 1;
}
return ans;
}
};
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
GooseTattarrattatDiv1
关键词：并查集、字符串
算法简述
因为每次替换都是以字母为单位的，所以可以先用并查集处理出哪些字母需要被变成一样的。然后在每个需要变成一样的集合中找到一个目前数量最多的字母，把其他字母都变成它就可以了。
一点点小代码
const int N = 100000;
int f[N], size[N];
int get(int u) {
if (u == f[u]) return u;
return f[u] = get(f[u]);
}
void join(int a, int b) {//并查集操作
if (size[get(a)] > size[get(b)]) swap(a, b);
f[get(a)] = get(b);
}
class GooseTattarrattatDiv1 {
public:
int getmin(string S) {
int n = S.size();
CL(size, 0);
REP(i, 'a', 'z') f[i] = i;
REP(i, 0, n - 1) size[S[i]]++;
REP(i, 0, n / 2) join(S[i], S[n - i - 1]);//把需要相同的字母集合找出来
int ans = 0;
REP(i, 'a', 'z') if (i != f[i]) ans += size[i];//答案就是每个集合的总数去掉其中最多的一种字母
return ans;
}
};
GearsDiv1
关键词：二分图匹配
算法简述
这题有两个条件，一个是要求让最终的图变成一个二分图。第二个条件是，原先所有相同颜色的节点必须要在一个集合里面。这样的话就simple了，只需要枚举哪两种颜色被分在一个集合里，然后计算一下这个集合的最小点覆盖，只要把最小点覆盖里的点都给删掉了就可以保证这个集合内没有边了。
一点点小代码
const int N = 60;
int a[N][N], vis[N], link[N];
char c[N];
char X, Y;
int n;
int find(int u) {// 匈牙利算法
REP(i, 0, n - 1) if (c[i] == Y && a[u][i] && !vis[i]) {
vis[i] = 1;
if (link[i] == -1 || find(link[i])) {
link[i] = u;
return true;
}
}
return false;
}
int match() {
CL(link, 0xff);
int ans = 0;
REP(i, 0, n - 1) if (c[i] == X) {
CL(vis, 0);
ans += find(i);
}
return ans;
}
int solve(char X, char Y) {//计算X和Y的最大独立集
::Y = Y;
::X = X;
return match();
}
class GearsDiv1 {
public:
int getmin(string color, vector<string> graph) {
CL(a, 0);
n = color.size();
REP(i, 0, n - 1) c[i] = color[i];
REP(i, 0, n - 1)
REP(j, 0, n - 1) a[i][j] = (graph[i][j] == 'Y');
return min(min(solve('R', 'G'), solve('G', 'B')), solve('R', 'B'));//枚举两种颜色作为二分图的一部 计算独立集
}
};
FlippingBitsDiv1
关键词：字符串，分类讨论，动态规划
题目简述
给定一个长度为的01串和一个正整数，定义它是一个循环串当且仅当的前个字符和后个字符匹配。现在可以进行两种操作：
- 将的一个位置反转
- 将的前个位置反转，其中是一个任意的正整数
你需要把给变成 一个循环串，求你需要的最少操作步数。
算法简述
首先考虑这个循环串是怎么一回事，其实这个条件就等价于将每隔置分组，除去最后一组外每组都相同。这样我们先考虑一个算法：枚举每一组的答案，然后用DP去计算要让每组变成这样所需要的代价。这个状态数是
那么再来看一个算法：枚举每一组是否反转，然后通过贪心的方法来得到最后的答案。这样枚举的状态数就是
现在发现这两个算法正好能互补起来，只需要判断一下的大小，采取合适的算法就可以了。
一点小代码
const int N = 310;
string b[N];
string T;
int n, m;
int tmp[N], sum[N], len[N];
int f[N];
int trans(int x) {
int res = 0;
REP(i, 0, b[x].size() - 1) res += (b[x][i] != T[i]);
return res;
}
int solve1() {
T = b[0];
int ans = 1e9;
REP(i, 0, (1 << m) - 1) {
REP(j, 0, m - 1) if (i & (1 << j)) T[j] = '1'; else T[j] = '0';
REP(j, 0, n - 1) tmp[j] = trans(j);
sum[0] = tmp[0]; len[0] = b[0].size();
REP(j, 1, n - 1) sum[j] = sum[j - 1] + tmp[j], len[j] = len[j - 1] + b[j].size();
REP(j, 0, n - 1) {
f[j] = min(sum[j], len[j] - sum[j] + 1);
if (j) getmin(&f[j], f[j - 1] + tmp[j]);
REP(k, 1, j) getmin(&f[j], f[k - 1] + len[j] - len[k - 1] - sum[j] + sum[k - 1] + 2);
}
getmin(&ans, f[n - 1]);
}
return ans;
}
int calc(int s) {
int ans = 0;
int last = -2;
REP(i, 0, n - 1) if (s & (1 << i)) {
if (i != last + 1) ++ans;
last = i;
}
ans *= 2;
if (s & 1) ans --;
return ans;
}
int solve2() {
int ans = 1e9;
int num[2][N];
REP(i, 0, (1 << n) - 1) {
int tmp = 0;
CL(num, 0);
REP(j, 0, n - 1)
REP(k, 0, b[j].size() - 1) if (i & (1 << j)) num[b[j][k] == '0'][k]++;
else num[b[j][k] == '1'][k]++;
REP(j, 0, m - 1) tmp += min(num[0][j], num[1][j]);
getmin(&ans, tmp + calc(i));
}
return ans;
}
class FlippingBitsDiv1 {
public:
int getmin(vector<string> S, int M) {
for (int i = 1; i < S.size(); ++i) S[0] += S[i];
m = M;
REP(i, 0, 300) b[i].clear();
REP(i, 0, S[0].size() - 1) {
b[i / M] += S[0][i];
}
n = (S[0].size() - 1) / M + 1;
int ans = 0;
if (M <= 17) ans = solve1();
else ans = solve2();
return ans;
}
};
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
LittleElephantAndString
关键词: 字符串
算法简述
这个idea还是比较简单的，只要看是否存在一段连续的位置是递增的就可以了。
一点点小代码
int n;
string A, B;
bool check(int x) {//贪心判断使用x操作是否可行
int last = -1;
bool flag;
REP(i, x, n - 1) { //看看A中是否存在B[x] .. B[n - 1]这个子序列
flag = 0;
REP(j, last + 1, n - 1) {
if (A[j] == B[i]) {
last = j;
flag = 1;
break;
}
}
if (!flag) return false;
}
return true;
}
class LittleElephantAndString {
public:
int getNumber(string A, string B) {
::A = A, ::B = B;
n = A.size();
sort(A.begin(), A.end());
sort(B.begin(), B.end());
if (A != B) return -1; //若AB中的字符不同则无解
int ans = 0;
REP(i, 0, n - 1) if (check(i)) return i;
return -1;
}
};
ConvexPolygonGame
关键词：计算几何
算法简述
这个题目就是给你一个凸包，问你这个凸包内是否存在一个坐标为整数的三角形。坐标范围是。由于坐标的范围比较小，我们发现，如果合法的点数大于那么些点里面一定存在一个三角形。所以只要把所有的点都找出来就可以了。至于怎么把所有的点都给找出来，可以枚举每个X，直接算出合法区间。
一点点小代码
int n;
LL area(int x1, int y1, int x2, int y2) { //计算叉积
return 1LL * x1 * y2 - 1LL * x2 * y1;
}
int gcd(int a, int b) { // 计算gcd
if (!b) return a;
return gcd(b,a % b);
}
double eval(int x1, int y1, int x2, int y2, int x) { //计算x在直线上的y坐标
return 1.0 * y1 + 1.0 * (y2 - y1) / (x2 - x1) * (x - x1);
}
PII t[210000];
vector<PII> P;
class ConvexPolygonGame {
public:
string winner(vector<int> X, vector<int> Y) {
n = X.size();
P.clear();
CL(t, 0);
LL side = 0, s = 0;
int x1 = 1e9, x2 = -1e9;
X.PB(X[0]); Y.PB(Y[0]);
REP(i, 0, n - 1) side += gcd(abs(X[i + 1] - X[i]), abs(Y[i + 1] - Y[i])),
s += area(X[i], Y[i], X[i + 1], Y[i + 1]);
s = abs(s);
LL num = side + (s + 2 - side) / 2 - n; //计算所有合法点的个数 Pick定理
if (num > 200001) return "Masha"; //如果点大于这个数的话 那么一定就会存在三点共线
if (num < 3) return "Petya";
REP(i, 0, n - 1) getmin(&x1, X[i]), getmax(&x2, X[i]);
PII *v = t + 101000;
REP(i, 0, n - 1) { //把每个x合法的y区间给求出来
int x1 = X[i], x2 = X[i + 1];
int y1 = Y[i], y2 = Y[i + 1];
if (x1 == x2)
v[x1] = MP(min(y1, y2) + 1, max(y1, y2) - 1);
else if (x1 < x2) {
REP(j, x1 + 1, x2 - 1) {
v[j].FR = ceil(eval(x1, y1, x2, y2, j));
}
v[x1].FR = y1 + 1;
v[x2].FR = y2 + 1;
} else {
REP(j, x2 + 1, x1 - 1) v[j].SC = floor(eval(x2, y2, x1, y1, j));
v[x1].SC = y1 - 1;
v[x2].SC = y2 - 1;
}
}
REP(i, x1, x2){ //把每个合法的点都存下来
REP(j, v[i].FR, v[i].SC) P.PB(MP(i, j));
}
REP(i, 2, P.size() - 1) if (area(P[i].FR - P[0].FR, P[i].SC - P[0].SC, P[1].FR - P[0].FR, P[1].SC - P[0].SC) != 0)
return "Masha";
return "Petya";
}
};
LittleElephantAndBoard
关键词：组合数学
题目简述
有个大小为的网格，你要给每个格子染R, G, B三种颜色中的一种。一种染色是合法的当且仅当：
- 任意两个相邻的格子都是不同的颜色
- 任意一个的格子都有3种不同的颜色
现在给出每种颜色的数量，求总共有多少种合法方案。
算法简述
这个题我感觉还是比较有意思的。首先要对条件进行转化。我们可以一列一列去考虑，每一列要往里面填两种不同的颜色，其中一种是上一列中没有出现过的颜色。现在考虑能不能用这个颜色来作为每一列的代表颜色。假定已知每一列新出现的颜色，那么能还原出整个染色方案呢？
答案是可以的。可以由下一列的代表颜色来确定出这一列的颜色组成，这样就能换原出整个网格了。具体的方法可以参考：SOL
一点小代码
const int N = 2100000;
int f[N], inv[N];
int C(int a, int b) {
return 1LL * f[a] * inv[b] % mo * inv[a - b] % mo;
}
int calc(int X, int Y, int Z) {//计算有X个R Y个G Z个B情况且相邻颜色不同的方案数
if (X <= 0) return 0;
int res = 0;
REP(g, X - 1, X) //组数
for (int ev = 0, xp = 1; ev <= g; ev++, xp = (xp + xp) % mo) { //枚举数量为偶数的组数
if ( (g - ev + Y - Z) % 2 != 0) continue;
int oy = (g - ev + Y - Z) / 2; // G多的
int oz = g - ev - oy; //B多的
if (oy >= 0 && oz >= 0 && Y - oy >= 0) {
int r = Y - oy - ev;
if (r < 0) continue;
int p = C(r+g-1, r);
p = 1LL * p * C(g,ev) % mo;
p = 1LL * p * C(g - ev, oy) % mo;
p = 1LL * p * xp % mo;
res = (res + p) % mo;
}
}
return res;
}
class LittleElephantAndBoard {
public:
int getNumber(int M, int R, int G, int B) {
f[0] = 1;
REP(i, 1, 2 * M) f[i] = 1LL * f[i - 1] * i % mo;
inv[2 * M] = pow(f[2 * M], mo - 2);
PER(i, 2 * M - 1, 0) inv[i] = 1LL * inv[i + 1] * (i + 1) % mo;
int ans = 2LL * calc(M - R, M - G, M - B) % mo;
ans = (ans + 2LL * calc(M - G, M - R, M - B) % mo) % mo;
ans = (ans + 2LL * calc(M - B, M - R, M - G) % mo) % mo;
return ans;
}
};
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
HexagonalBoard
关键词：二分图判定
算法简述
首先可以观察出题目所给的这个图的色数一定不超过3。这样只要知道这个图的色数是不是2就可以了，一个floodfill之类的就行了。
一点点小代码
int c[100][100];
int g[100][100];
int n;
int dirx[] = {0, 0, 1, 1, -1, -1};
int diry[] = {-1, 1, -1, 0, 0, 1};
bool pd(int x, int y) { //判断(x, y)是否是一个合法的位置
return x < n && x >= 0 && y < n && y >= 0 && g[x][y];
}
bool floodfill(int x, int y, int d) { // floodfill判断是否二分图
c[x][y] = d;
REP(i, 0, 5) {
int xx = x + dirx[i], yy = y + diry[i];
if (!pd(xx, yy)) continue;
if (!c[xx][yy] && !floodfill(xx, yy, 3 - d)) return false;
else if (c[xx][yy] == d) return false;
}
return true;
}
class HexagonalBoard {
public:
int minColors(vector<string> board) {
CL(c, 0);
n = board.size();
REP(i, 0, n - 1) REP(j, 0, n - 1) g[i][j] = (board[i][j] == 'X');
REP(i, 0, n - 1) REP(j, 0, n - 1) if (pd(i, j) && !c[i][j] && !floodfill(i, j, 1)) return 3; //如果不是二分图说明答案3
int mx = 0;
REP(i, 0, n - 1) REP(j, 0, n - 1) getmax(&mx, c[i][j]); //判断答案是否为0 1 2
return mx;
}
};
MayTheBestPetWin
关键词：背包、简单数学
算法简述
首先把式子变换一下，我们要最小化的是, 其中是选择出的第一队的A与B的和。整理一下就是, 其中是常数，因此只要知道就行了。那么就把这个看成一个整体，来做一个可行性背包，最后枚举一下就可以算出答案了。
一点点小代码
const int M = 1000001;
bitset<M> f; //代表sigma A[i] + B[i] = x 是否可行
int n;
class MayTheBestPetWin {
public:
int calc(vector<int> A, vector<int> B) {
n = A.size();
f.reset(); f[0] = 1; //最开始的时候 只有f[0] = 1
REP(i, 0, n - 1) f |= (f << (A[i] + B[i]));
int ans = 1e9;
int sa = 0, sb = 0; //A的和 与 B的和
REP(i, 0, n - 1) sa += A[i], sb += B[i];
REP(i, 0, sa + sb) if (f[i]) getmin(&ans, max(sb - i, i - sa)); //计算最优的Max{sb - A - B, A + B - sa}
return ans;
}
};
WolfDelaymasterHard
关键词：动态规划
题目简述
定义一个串是合法的：
- 对于一个正整数,串
ww..woo..o(个w后面接上个o) 是合法的 - 两个合法串的拼接是合法的
现在给出一个串,其中包含有字符w,o,?，现在要把所有?的地方填上w或o，使得串合法。
问有多少种不同的填法。
算法简述
这个题可以一眼看出一个十分naive的暴力DP，大概就是 ，其中的意思就是这个子串可以被填成ww..woo..o这样的形式。
考虑来优化这个DP，我们发现对于一个，所以合法的的位置组成了不超过段连续区间。这个还是比较好说明的，可以脑补一下发现是对的。
有了这个结论就可以很方便地来做这个题了。只要维护一下每一段区间，同时记录一下DP的前缀和就可以了。
一点小代码
const int N = 2100000;
char s[N];
int f[N];
int sum1[N], sum2[N]; //奇数下标的前缀和以及偶数下标的前缀和
int sw[N], so[N]; //'w'的前缀和 'o'的前缀和 用于判断子串合法
vector<PII> v; //储存合法的转移区间 不超过O(log(n))
bool check(int i, int j) { //判断[i, j]是否合法 (w^n + o^n)
if (i <= 0 || i > j || (i - j) % 2 == 0) return false;
int m = (i + j) / 2;
return (so[m] - so[i - 1] == 0) && (sw[j] - sw[m] == 0);
}
class WolfDelaymasterHard {
public:
int countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd) {
//先生成字符串
//
REP(i, 1, N) s[i] = '?';
LL x = w0;
REP(i, 0, wlen - 1) {
s[x + 1] = 'w';
x = (x * wmul + wadd) % N;
}
x = o0;
REP(i, 0, olen - 1) {
s[x + 1] = 'o';
x = (x * omul + oadd) % N;
}
sw[0] = so[0] = 0;
REP(i, 1, N) sw[i] = sw[i - 1] + (s[i] == 'w'), so[i] = so[i - 1] + (s[i] == 'o');
f[0] = 1;
f[1] = 0;
sum2[0] = 1;
sum1[1] = 0;
v.clear();
REP(i, 2, N) {
vector<PII> t;
bool flag = false;
for (int j = 0; j < v.size(); ++j) { //维护合法的转移区间
PII &A = v[j];
if (!check(i - 2 * A.SC - 1, i)) --A.SC;
A.SC++, A.FR++;
if (A.FR <= A.SC) {
if (A.FR == 2 && check(i - 1, i)) A.FR = 1, flag = 1;
if (s[i] != 'w')
t.PB(A);
}
}
if (!flag && check(i - 1, i)) t.PB(MP(1, 1));
v = t;
int *s;
if (i & 1) s = sum1;
else s = sum2;
f[i] = 0;
for (int j = 0; j < v.size(); ++j) {
PII &A = v[j];
f[i] = (f[i] + s[i - 2 * A.FR] - s[i - 2 * A.SC]) % mo; //通过前缀和来计算
f[i] = (f[i] + f[i - 2 * A.SC]) % mo;
if (f[i] < 0) f[i] += mo;
}
s[i] = (s[i - 2] + f[i]) % mo;
}
return f[N];
}
};
