2020 5月月赛题解
花絮
- csf: 从参赛人数来看，我很满意
- 中途为啥oj崩了，原因还在找= -=
1001. 社会热点题
送分题，不解释，直接输出7即可，注意需要添加文件IO操作。 不会的同学，请看这个链接https://turingjudge.com/problem/1001
1002. 功能实现题
读入字符串，将每个字符传换成大写字母即可。
for(int i = 0;s[i];++i) {
if(s[i] >= 'a' && s[i] <= 'z') {
s[i] = ('A' - 'a') + s[i];
}
}
1003. 数学计算题
根据题目中的提示，面积的比值等于线比值的平方倍。
。
注意精度问题，也就是说表示的越精确越好。
1004. 朴素模拟题
这道题是错误率最高的一道题，其中有一个原因是是出题人的问题，第一个样例弄错了，还好修正及时，十分抱歉。
需要特别注意的是，左上角坐标是，右下角坐标是，也就是说可以看成是行号，可以看成是列号。
指令相当于行在上下移动，相当于列在左右移动。
然后如果越界了，那么就重置为边界处就可以了。
参考代码：
int len = st.size() >> 1;
for (int i = 0; i < len; i++){
char dir = st[i<<1];
int step = st[i<<1^1] - '0';
if (dir == 'L'){
y -= step;
y = max(1, y);
}else if (dir == 'R'){
y += step;
y = min(m, y);
}else if (dir == 'U'){
x -= step;
x = max(1, x);
}else{ // D
x += step;
x = min(n, x);
}
}
printf("%d %d\n", x, y);
1005. 递归分解题
这是一道非常明显的，考察递归的题目，如果分解出来的数字大于9，则需要继续进一步分解。
我们可以设计函数dfs(int n)表示对进行分解。
那么代码就可以写成：
int _sum(int x) {
int ans = 0;
while(x) {
ans += x % 10;
x /= 10;
}
return ans;
}
void dfs(int x) {
if(x < 10) {
cout << x;
return ;
}
int sum = _sum(x);
cout << "[";
dfs(sum);
cout << "](";
dfs(sum+1);
cout << ")";
}
1006. 动态规划题
这道题改编自“石子合并”问题，只不过石子合并是2堆相邻的石子进行合并，而这道题则是3个相邻的物体进行合并，但思路是一样的。
2堆石子合并的时候，是2个区间在合并；而3个相邻物体进行合并，则是3个区间在合并。
设表示把这段区间内的宠物合并成变异宠物的最大概率。
枚举两个分界点，将区间分解成3个相邻的区间，,那么我们就可以得到转移方程。
不妨设。
考虑所有的8种情况
情况1：三个区间都合成了变异宠物，这种情况的概率是，那么合并3个变异宠物得到变异宠物的概率是。
情况2：第一个区间普通宠物，第二、三区间变异宠物，这种情况的概率是，那么合并得到新的变异宠物概率是。
情况3：第一、二个区间普通宠物，第三区间变异宠物，这种情况的概率是，那么合并得到新的变异宠物概率是。
以下省略剩余5种情况。最后把所有情况的概率求和即得到本次分割的最大概率。
参考代码：
double dfs(int l, int r) {
if (l == r) return a[l];
if (vis[l][r]) return dp[l][r];
vis[l][r] = true;
for (int i = l; i < r; i += 2) {
for (int j = r; j > i; j -= 2) {
double x1 = dfs(l, i);
double x2 = dfs(i + 1, j - 1);
double x3 = dfs(j, r);
double ans = x1 * x2 * x3;
ans += p1 * (1 - x1) * x2 * x3;
ans += p1 * x1 * (1 - x2) * x3;
ans += p1 * x1 * x2 * (1 - x3);
ans += p2 * (1 - x1) * (1 - x2) * x3;
ans += p2 * (1 - x1) * x2 * (1 - x3);
ans += p2 * x1 * (1 - x2) * (1 - x3);
dp[l][r] = std::max(dp[l][r], ans);
}
}
return dp[l][r];
}
// ans = dfs(0, n - 1)
1007. 图论扩展题
本题是出题人的失误，出的数据太弱了，放掉了一些看起来正确的“假算法”，过题的同学再仔细审视一下自己的算法，有没有问题。
考虑u是v的真祖先，我们就在图上连接一条从u到v的有向边。
按照拓扑排序的思想，所有v的祖先都会排在v的前面，进一步思考，我们发现v的父节点一定是v最靠后的那个祖先。
所以我们就有了思路，当节点u从队列中弹出的时候，根据拓扑排序的思想，我们需要把u指向的所有节点v的入度-1，此时，我们顺便把这个节点v的父节点覆盖为u即可，fa[v] = u;。 这样的话，一定是v的真正的父节点最后覆盖了fa[v]。
时间复杂度。
参考代码：
cin >> n >> m;
for(int i = 1;i <= m;++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
indeg[v] ++;
}
queue<int> Q;
for(int i = 1;i <= n;++i) {
if(indeg[i] == 0) {
Q.push(i);
}
}
while(!Q.empty()) {
int u = Q.front();Q.pop();
for(int i = 0;i < G[u].size();++i) {
int v = G[u][i];
fa[v] = u;
if(--indeg[v] == 0) {
Q.push(v);
}
}
}
for(int i = 1;i <= n;++i) {
cout << fa[i] << " ";
}
cout << endl;
csl: 被我bitset直接草了
前排