不要问作者分数和排名，触碰到个人心理阴影（
首先先来概括一下我的比赛惨状再进入正题：
T1T2很简单直接开模拟
T3看似是博弈，其实是dp
T4不会开暴力，打表也不行
T1赛后很简单看见一片绿
T2T3出奇迹T4 TLE
T2数组小，T3状态转移
T4不用说，不会ST
T1
题目很简单，模拟一下，就行了。
但是作者太蒟了，一直CE，最后直接打表了每种可能 AC 了（呵呵
题解
网页版： 普及模考T1の题解 - 经验分享区 - 信友队论坛
首先我们将每种 noip 的大小写情况打出来，注意一定要用 char 因为 string 的每位类型为 char
这就是所有可能：char d[20][10]={{'n','o','i','p'},{'N','o','i','p'},{'n','O','i','p'},{'n','o','I','p'},{'n','o','i','P'},{'N','O','i','p'},{'N','o','I','p'},{'N','o','i','P'},{'n','O','I','p'},{'n','O','i','P'},{'n','o','I','P'},{'N','O','I','p'},{'N','O','i','P'},{'N','o','I','P'},{'n','O','I','P'},{'N','O','I','P'}};
接下来模拟一下就行了从字符串的第一位开始，每次读取 4 位，判断这 4 位是否与 noip 的 16 种形式有相同，如果有就输出 CSP，并且将 i 加 4 。
如果不是则就输出 a_i 并且将 i 加一。
伪代码：
while(i<a.size()){
bool flag=0;
for(int j=0;j<16;j++){//查看是否有相同
if(/*判断条件 */){
flag=1;
break;
}
}
if(flag){
cout<<"CSP";
i+=4;
}
else{
cout<<a[i];
i++;
}
}
T2
这道题目也是模拟，但是作者数组开小了惨失 90 分，如果开大一点排名会靠前 20 多名！
题解
这道题目也很简单，我们模拟一下就好了。
我们可以定义一个 ans 数组，来存储每个编号的数的值。
- 如果输入是
ADD则ans[i]=ans[i-1]+t; - 如果输入是
SUB则ans[i]=ans[i-1]-t; - 如果输入是
SET则ans[i]=t; - 如果输入是
back则ans[i]=ans[i-t-1];
我们将每个数都存储入 ans 最后输出即可。
伪代码：
for(int i=1;i<=n;i++){
string op;
int t;
cin>>op>>t;
/*判断*/
}
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;//输出
T3
这道题目一开始看到博弈以为是数学，后来发现是区间 dp
但是可能由于思路不清晰，并且模板没有背熟所以导致 WA10
题解
这道题目看似是博弈，但是其实是区间 dp！
首先区间 dp 的板子大家一定要记住：
for(int len=2;len<=n;len++) {//先枚举区间长度
for(int i=1;i+len-1<=n;i++) {//再枚举区间左端点，左端点加区间长度为右端点，不能大于n
int j=i+len-1; //区间右端点
for(int k=i;k<j;k++) { //枚举区间分割点
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+/*合并区间的消耗*/);
}
}
}
简单认识模板以后我们就可以来求此题了，放上 dp 的要素：
- 定义： dp[i][j] 表示在区间 i 到 j 中 dogwang 的最大的得分的最小值。
- 初始化：因为我们要求最小值所以将 dp 数组初始化为无穷大，并且对于 dp[i][i] 的类型初始化为 0 因为 dogeya 将这唯一一个元素取走后，答案只能为 0 并且为了防止以后在状态转移的时候出现左端点大于右端点的情况，我们将 dp[i+1][i] 也初始化为 0 。
- 状态转移：我们枚举区间中的一个下标 k 设 dogeya 取走了这个下标的元素，那么整个区间被我们分成了 2 段，第一段是 [l,k-1] 第二段是 [k+1,r] 我们分别求出这两种情况的最大值，最后再与 dp[l][r] 取最小值即可。
- 答案：游戏在 [1,n] 中进行，所以答案为 dp[1][n] 。
接下来通过要素来写代码：
/*初始化*/
for(int len=2;len<=n;len++){//枚举区间长度
for(int l=1;l+len-1<=n;l++){//枚举左端点
int r=l+len-1;//右端点
for(int k=l;k<=r;k++)dp[l][r]=min(dp[l][r],max(sum[k-1]-sum[l-1]+dp[k+1][r],sum[r]-sum[k]+dp[l][k-1]));//状态转移
}
}
/*输出*/
T4
这道题目一看数据范围吓了一跳，首先先用数学推了推，然后打了个暴力先骗分。
然后老师提示要用 ST 表能得到 50 分，可惜的是不太熟悉。
最后只用数学优化推出了一个 O(m\sqrt n) 的代码提交了上去得了 30 分。
题解
网页版：
正在努力ing等会更新
总结
以后数据范围要看清，不能再像这次 T2 一样失分。
学过的知识要多巩固练习，模板要背熟。
我的时间分配
首先T1一直CE大概花了半个小时去调。
然后看T2，一眼模拟，用时 5 分钟。
接着看 T3 看到博弈以为是贪心，想不出策略，先看了一下T4。
T4 首先在想如何优化，实在不会打了一下暴力，感觉复杂度太高了，用数学优化了一下，然后去看T3。
老师提示 T3 是区间 dp，打了一下模板，但是没有打对？然后调试了一下大概用时 40 分钟.
然后再回来看T4，测了一下大样例，能过，然后继续向怎么优化。