CSDN 第三十七期竞赛题解

很少有时间来玩玩题目，上一次因为环境极为嘈杂的原因在时间上没有进入前十，挺遗憾的。
在 CSDN 参加的第一次没出锅的比赛。

大概只有最后一题值得好好讲讲。

---

T1：幼稚班作业

幼稚园终于又有新的作业了。 老师安排同学用发给同学的4根木棒拼接成一个三角形。 当然按照正常的逻辑，如果不能拼接成三角形。 必然要折断某个木棍来拼接三角形。 可是懒惰的小艺当然不会费力了！ 如果拼接不成三角形，小艺就会把它拼接成类似边长 1 1 2的伪三角形（两边之和等于第3边）。 如果伪三角形都拼接不成那就不交作业！

分析

排序 + 三角形判断，注意四根木棍不需要全用。

#include<bits/stdc++.h>
int a[5];
using namespace std;
int main(){scanf("%d%d%d%d",a+1,a+2,a+3,a+4);sort(a+1,a+5);if(a[1]+a[2]>a[3]||a[2]+a[3]>a[4]) return puts("1"),0;else if(a[1]+a[2]==a[3]||a[2]+a[3]==a[4]) return puts("0"),0;puts("-1");
}

---

T2：异或和

小张找到了一个整数 N，他想问问你从 1 到 N 的所有不同整数的异或和是多少， 请你回答他的问题。（$1\le N\le 10^5$）

分析

本来以为需要奇偶数分类，没想到是个模拟。
题目限制变成 $1\le N\le 10^{10^5}$ 应该更好。

#include<bits/stdc++.h>
int n,ans;
using namespace std;int main(){scanf("%d",&n);for(int i=1;i<=n;i++) ans^=i;printf("%d",ans);
}

---

T3：大整数替换数位

以字符串的形式给你一个长度为 $M$ 的整数 $N$，请你计算出对这个数进行一次操作后模 $9$ 的值为 $1$ 的所有可能的不同操作方式。

在一次操作中， 我们可以选择 $N$ 的一个数位 $N_i$，并把它替换成另一个不同的 $0$ 到 $9$ 范围之内的数 $B$，当且仅当它们选择的 $i$ 或 $B$ 不同时两种操作方式不同。

分析

首先知道 $9$ 的倍数其满足数位和仍为 $9$ 的倍数。
那么问题变成

求对于一个由 $n$ 个一位数组成的序列 $N$，试求改变一个 $N_i$，使得 $\sum _{1\le i\le n}{N}_i$为 $9$ 的倍数的方案数。

因为只能改一位，那么根据原本序列 $N$ 的和模 $9$ 的余数，逐位判断并累加答案即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int m,a[N],nw,ans;
int main(){scanf("%d",&m);for(int i=1;i<=m;i++) scanf("%1d",a+i),nw+=a[i];nw%=9;nw=(nw+8)%9;for(int i=1;i<=m;i++){if(!nw){if(a[i]==0) ans++;}else{if(a[i]+(9-nw)<10) ans++;if(a[i]-nw>-1) ans++;}}return 0;
}

---

T4：莫名其妙的键盘

有一个神奇的键盘，你可以用它输入a到z的字符，然而每当你输入一个元音字母(a,e,i,o,u其中之一)的时候，已输入的字
符串会发生一次反转！ 比方说，当前输入了tw，此时再输入一个o，此时屏幕上的字符串two会反转成owt。 现给出一个
字符串，若用该键盘输入，有多少种方法可以得到？

分析

注意到“有多少种方法可以得到”实现起来相对麻烦，考虑将问题翻转一下变成将一个字符串不断从左右删除直到长度为 0 的方案数。我们知道一个序列被反转了偶数次后形态不变，而这里从左边删除代表了当前序列已被翻转了奇数次。

于是考虑使用区间 dp 解决。

设 $d{p}_{i,j,0/1}$ 表示当前删除到区间为 $[i,j]$ 并且上一次删除了最左 / 右边字符的方案数。

由区间 $[i,j]$ 向 $[i+1,j]$、$[i,j-1]$ 转移，分四种情况：

• $s_i$ 为元音：翻转一次，即 $f_{i+1,j,1}=f_{i+1,j,1}+f_{i,j,0}$
• $s_i$ 为辅音：不用翻转，即 $f_{i+1,j,0}=f_{i+1,j,0}+f_{i,j.0}$
• $s_j$ 为元音：翻转一次，即 $f_{i,j-1,0}=f_{i,j-1,0}+f_{i,j,1}$
• $s_i$ 为辅音：不用翻转，即 $f_{i+1,j,1}=f_{i+1,j,1}+f_{i,j,1}$

那么很明显答案 $Ans$ 为
$$Ans=\sum _{i=1}^n(f_{i,j,0}+f_{i,j,1})$$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[205];
LL ans,dp[205][205][2];
bool ck(char ch){if(ch=='a'||ch=='u'||ch=='o'||ch=='e'||ch=='i') return 1;return 0;
}
int main(){scanf("%s",s+1);int ls=strlen(s+1);dp[1][ls][1]=1;for(int l=ls;l;l--){for(int i=1;i+l-1<=ls;i++){int j=i+l-1,cki=ck(s[i]),ckj=ck(s[j]);if(cki) dp[i+1][j][0]+=dp[i][j][1];if(!cki) dp[i+1][j][0]+=dp[i][j][0];if(ckj) dp[i][j-1][1]+=dp[i][j][0];if(!ckj) dp[i][j-1][1]+=dp[i][j][1];}}for(int i=1;i<=ls;i++) ans+=dp[i][i][0]+dp[i][i][1];return 0;
}

感觉最后一题题解敲得超详细，不妨多支持一下？