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