over 6 years ago
嘟噜噜... 还有一个月就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];
}
};
