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

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

T1：幼稚班作业

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

分析

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

#include
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≤N≤1051\leq N\leq 10^51≤N≤105）

分析

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

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

T3：大整数替换数位

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

在一次操作中， 我们可以选择 NNN 的一个数位 NiN_iNi​，并把它替换成另一个不同的 000 到 999 范围之内的数 BBB，当且仅当它们选择的 iii 或 BBB 不同时两种操作方式不同。

分析

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

求对于一个由 nnn 个一位数组成的序列 NNN，试求改变一个 NiN_iNi​，使得 ∑1≤i≤nNi\sum\limits_{1\leq i\leq n}N_i1≤i≤n∑​Ni​为 999 的倍数的方案数。

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

#include
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 解决。

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

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

• sis_isi​ 为元音：翻转一次，即 fi+1,j,1=fi+1,j,1+fi,j,0f_{i+1,j,1}=f_{i+1,j,1}+f_{i,j,0}fi+1,j,1​=fi+1,j,1​+fi,j,0​
• sis_isi​ 为辅音：不用翻转，即 fi+1,j,0=fi+1,j,0+fi,j.0f_{i+1,j,0}=f_{i+1,j,0}+f_{i,j.0}fi+1,j,0​=fi+1,j,0​+fi,j.0​
• sjs_jsj​ 为元音：翻转一次，即 fi,j−1,0=fi,j−1,0+fi,j,1f_{i,j-1,0}=f_{i,j-1,0}+f_{i,j,1}fi,j−1,0​=fi,j−1,0​+fi,j,1​
• sis_isi​ 为辅音：不用翻转，即 fi+1,j,1=fi+1,j,1+fi,j,1f_{i+1,j,1}=f_{i+1,j,1}+f_{i,j,1}fi+1,j,1​=fi+1,j,1​+fi,j,1​

那么很明显答案 AnsAnsAns 为
Ans=∑i=1n(fi,j,0+fi,j,1)Ans=\sum\limits_{i=1}^{n}(f_{i,j,0}+f_{i,j,1})Ans=i=1∑n​(fi,j,0​+fi,j,1​)

#include
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;
}

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