【洛谷月赛】洛谷三月月赛题解报告
昨天就是洛谷三月月赛，小编考的并不好，才31分，隔壁大佬50分，于是小编决定改一改题，先看第一题：
P5238 整数校验器
题目描述
有些时候需要解决这样一类问题：判断一个数 xx 是否合法。
xx 合法当且仅当其满足如下条件：
- xx 格式合法，一个格式合法的整数要么是 00，要么由一个可加可不加的负号，一个 11 到 99 之间的数字，和若干个 00 到 99 之间的数字依次连接而成。
- xx 在区间 [l,r][l,r] 范围内（即 l \le x \le rl≤x≤r）。
你需要实现这样一个校验器，对于给定的 l, rl,r，多次判断 xx 是否合法。
输入输出格式
输入格式：
第一行三个整数 l,r,Tl,r,T，表示校验器的校验区间为 [l,r][l,r]，以及需要校验的 xx 的个数。
接下来 TT 行，每行一个 xx，表示要校验的数，保证 xx 长度至少为 11 且仅由 ‘0’~’9′ 及 ‘-‘ 构成，且 ‘-‘ 只会出现在第一个字符。
输出格式：
输出共 TT 行，每行一个整数，表示每个 xx 的校验结果。
校验结果规定如下：00 表示 xx 合法；11 表示 xx 格式不合法；22 表示 xx 格式合法且不在 [l,r][l,r] 区间内。
输入输出样例
这道题一看很有思路，不就是输入字符串，在多判断几次，代码很快就出来了。
1 // luogu-judger-enable-o2 2 #include<iostream> 3 #include<cstdio> 4 using namespace std; 5 char c[1000000000];long long T,l,r,cnt,sum,k;bool flag;char x; 6 int main() 7 { 8 scanf("%lld%lld%lld",&l,&r,&T); 9 x=getchar(); 10 for(int i=1;i<=T;i++) 11 { 12 //x=getchar(); 13 cnt=0;sum=0;flag=false;k=0; 14 for(;;) 15 { 16 c[++cnt]=getchar();//cout<<"1:"<<cnt<<" "<<c[cnt]<<endl; 17 //cout<<c[cnt]<<" "<<sum<<endl; 18 if(c[cnt]=='-') sum=0-sum; 19 else if(c[cnt]=='\n') break; 20 else 21 { 22 sum*=10;sum+=(c[cnt]-48); 23 } 24 25 } 26 // for(int j=1;j<=cnt;j++) 27 // cout<<c[j]; 28 // cout<<endl; 29 //cout<<"1:"<<cnt<<" "<<sum<<endl; 30 for(int j=1;j<=cnt;j++) 31 { 32 33 34 if(c[j]=='0'&&cnt>2&&j==1) 35 { 36 //cout<<"c["<<j<<"]=='0'&&"<<cnt<<">2"<<endl; 37 printf("1 \n");k=1; 38 break; 39 } 40 else if(c[j]=='-') 41 { 42 //cout<<"c["<<j<<"]=='-'"<<endl; 43 if(c[j+1]=='0') 44 { 45 printf("1 \n");k=1; 46 break; 47 } 48 } 49 else if(l>sum||sum>r) 50 { 51 //cout<<l<<" "<<sum<<" "<<r; 52 printf("2 \n");k=1; 53 break; 54 } 55 // else if(flag==true) 56 // { 57 // if(l>(0-sum)||(0-sum)>r) 58 // { 59 // printf("2 \n");k=1; 60 // break; 61 // } 62 // } 63 } 64 if(k==0) printf("0 \n"); 65 } 66 return 0; 67 }
草草一写，只得了5分，令小编十分伤心，于是小编就开始找自己写的漏洞，发现当l=-100，r=100时，输入100会输出1，这是为什么呢？还有输入0102时应该输出1，而这个程序却输出了2，小编才发现有些地方顺序不对，还有的多加了回车。于是更改如下：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 char c[1000000000];long long T,l,r,cnt,sum,k;bool flag;char x; 5 int main() 6 { 7 scanf("%lld%lld%lld",&l,&r,&T); 8 x=getchar(); 9 for(int i=1;i<=T;i++) 10 { 11 //x=getchar(); 12 cnt=0;sum=0;flag=false;k=0; 13 for(;;) 14 { 15 c[++cnt]=getchar();//cout<<"1:"<<cnt<<" "<<c[cnt]<<endl; 16 //cout<<c[cnt]<<" "<<sum<<endl; 17 if(c[cnt]=='-') sum=0-sum; 18 else if(c[cnt]=='\n') break; 19 else 20 { 21 sum*=10;sum+=(c[cnt]-48); 22 } 23 24 } 25 // for(int j=1;j<=cnt;j++) 26 // cout<<c[j]; 27 // cout<<endl; 28 //cout<<"1:"<<cnt<<" "<<sum<<endl; 29 for(int j=1;j<=cnt;j++) 30 { 31 32 //cout<<c[j]<<" "<<c[j+1]<<endl; 33 if(c[j]=='0'&&c[j+1]!='\n'&&j==1) 34 { 35 //cout<<"c["<<j<<"]=='0'&&"<<cnt<<">2"<<endl; 36 printf("1 \n");k=1; 37 break; 38 } 39 else if((c[j]=='-'&&c[j+1]=='\n')||(c[j]=='-'&&c[j+1]=='0')) 40 { 41 //cout<<"c["<<j<<"]=='-'"<<endl; 42 printf("1 \n");k=1; 43 break; 44 } 45 else if(l>sum||sum>r) 46 { 47 //cout<<l<<" "<<sum<<" "<<r; 48 printf("2 \n");k=1; 49 break; 50 } 51 // else if(flag==true) 52 // { 53 // if(l>(0-sum)||(0-sum)>r) 54 // { 55 // printf("2 \n");k=1; 56 // break; 57 // } 58 // } 59 } 60 if(k==0) printf("0 \n"); 61 } 62 return 0; 63 }
一个可爱的10分，没事，不自卑，好歹多了5分，5分也是分啊。
那么究竟什么样的数不符合规则呢？
- -0当然不符合，谁家0写‘-’号呢？
- -当然也不合适，后面没有数字了。
- 0……有前导0的当然也不行。
- 爆long long的当然不可能正常。
- 超过l，r范围的也不行。
既然这些都不行，那么剩下的都可以喽，看了题解之后才发现缺了第4条的判断。思路很简单：先判断格式是否正确和是否爆unsigned long long，然后判断是否超出范围，总之一大堆判断模拟即可，代码如下：
1 #include<iostream> 2 #include<sstream> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 long long l,r,T,cnt=0,len=0;char c[100000]; 7 int main() 8 { 9 cin>>l>>r>>T; 10 for(int i=1;i<=T;i++) 11 { 12 len=0;cnt=0; 13 cin>>(c+1);//输入字符串，这么写是为了去掉多出的回车 14 len=strlen(c+1); 15 //cout<<c[1]<<endl; 16 if(c[1]=='-'&&(len==1||c[2]=='0'))//只有一个‘-’的和‘-0’当然不行 17 { 18 cout<<"1"<<endl; 19 continue; 20 } 21 else if(c[1]=='0'&&len!=1)//有前导0的也不行 22 { 23 cout<<"1"<<endl; 24 continue; 25 } 26 else if(c[1]=='-'&&len>20)//负数太小了不可能 27 { 28 cout<<"2"<<endl; 29 continue; 30 } 31 else if(c[1]!='-'&&len>19)//正数太大了不可能 32 { 33 cout<<"2"<<endl; 34 continue; 35 } 36 unsigned long long sum;//之前的处理是为了防止数字爆unsigned long long 37 long long x;//可以说x存的是sum的绝对值 38 if(c[1]=='-') 39 { 40 sscanf(c+2,"%llu",&sum);//注意在#include<cstdio>和#include<sstrea 41 if(sum>(1LL<<63)) //m>两个头文件下才可以使用,把字符串转换成 42 { //数字，当然，也可以手写。 43 cout<<"2"<<endl; //1LL表示（long long）1，1<<63表示1*2^63 44 continue; 45 } 46 x=0-sum; 47 } 48 else 49 { 50 sscanf(c+1,"%llu",&sum); 51 if(sum>=(1LL<<63)) 52 { 53 cout<<"2"<<endl; 54 continue; 55 } 56 x=sum; 57 } 58 if(x>=l&&x<=r) cout<<"0"<<endl; 59 else cout<<"2"<<endl;//超出范围当然不行 60 } 61 return 0; 62 }
接着看第二题：
P5239 回忆京都
题目背景
第十五届东方人气投票 音乐部门 106名
第四次国内不知道东方的人对东方原曲的投票调查 51名
回忆京都副歌我tm吹爆，东方文花帖我tm吹爆！
题目描述
输入输出格式
输入格式：
第一行输入一个q，表示有q次询问。
第二行开始，一共q行，每行两个数字n,m，意思如题所示。
输出格式：
一共q行，对于每一个询问，都输出一个答案。
输入输出样例
这道题一看就明白了，只要暴力求解不就行了吗，但是小编表示看不懂
这个是干什么的，看了题解才发现这个式子是让求1~n和1~m的所有C的和，什么意思呢？举个例子。
就比如说样例吧当m=2，n=3时，i的取值是1~2，j的取值是1~3，那么C₃¹+C₃²+C₃³+C₂¹+C₂²+C₁¹就是这一串式子的值。
看完题解发现这道题是一道前缀和的模板题，之前学动态规划和树状数组的时候有点印象，那么什么是前缀和呢？好说，如图所示：
像这样，有一个数组，里面有若干个数字，你的任务是输出每次询问的前i个数的和，但是这和我们的题有什么关系呢？别着急把它扩展成二维前缀和。
如果每一个方格中存储的值都为C[i][j]的值，sum数组存的是前i行前j列所有C的和，那么就能得到动态规划的状态转移方程：
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+C[i][j]。
这个状态转移方程应该比较好理解吧。举个例子，假设要求i=3，j=4时的sum值，那么sum[i][j]用方格可以表示为：
sum[i-1][j]可以表示为：
sum[i][j-1]可以表示为：
很显然，下图的棕色区域被算了2次，要减掉，同时加上C[i][j]（深蓝色格子）的值，还要记得过程中不停取模。
但是暴力去算每一个C都非常麻烦，不妨用动态规划的思路来解题，这种组合题对于每一个数，只有两种情况，要么选（共有C[i-1][j-1]种情况），要么不选（共有C[i][j-1]种情况），所以C[i][j]只和C[i-1][j-1]，C[i][j-1]有关，得到以下状态转移方程：
C[i][j]=C[i-1][j-1]+C[i][j-1]
就这样按顺序递推，代码就出来了：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 long long c[1001][1001],sum[1001][1001],n,m,q; 5 int main() 6 { 7 c[1][1]=1;c[1][0]=1; 8 for(int i=2;i<=1000;i++)//打表 9 { 10 c[i][0]=1; 11 for(int j=1;j<=i;j++) 12 c[i][j]=(c[i-1][j-1]+c[i-1][j])%19260817; 13 } 14 for(int i=1;i<=1000;i++)//打表 15 for(int j=1;j<=1000;j++) 16 sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+c[i][j]+19260817)%19260817; 17 cin>>q; 18 for(int i=1;i<=q;i++) 19 { 20 cin>>m>>n; 21 cout<<sum[n][m]<<endl;//询问时直接输出即可 22 } 23 return 0; 24 }
为什么这道题可以打表呢？很简单，这道题的数据范围如下：
n和m最大值只有1000，就不必一次一次慢慢算了，这样比较快。