嘟噜噜... 还有一个月就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;
}
};
