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