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