【赛时·VII】 ABC-106
一条比赛时莫名其妙发了半个小时呆的菜鸡&咸鱼得到了自己应有的下场……279th. Rating:1103（+）
终于AK，一次通过……
◇ 简单总结
ABC还是和往常一样，前两道题比手速（+英语QwQ，那些dalao七分钟AK时我还在看第二题的题意?），感觉自己码代码的速度还是太慢了。
第三题稍动脑筋，发现是一道结论题……
第四题本来没什么难度，但是我时间复杂度分析错了，一直以为我会TLE，就没敢交?，然后开始想优化（实际上发了半个小时呆），于是rank就蹭蹭蹭往下掉。当然最后还是秒掉——ACM赛制还是要快准恨好……
◇ 题目&解析
◆A题◆ Garden ⚔小学数学⚔
· 【翻译】
有一个n*m的花园（2≤n,m≤100），有两条宽度为1的小路，分别是横向、纵向的，其余面积都是草地，求草地的面积。
· 【解析】
把两条小路移动到侧边去，或者说把两条小路割成的四个部分合成一个矩形，我们就会发现草地形成了一个(n-1)*(m-1)的矩形，也就是求这个矩形的面积……（没什么可讲的）
· 【源代码】
/*Lucky_Glass*/#include#include #include using namespace std;int main(){ int A,B; scanf("%d%d",&A,&B); printf("%d\n",(A-1)*(B-1)); return 0;}
◆B题◆ 105 ⚔枚举⚔
· 【翻译】
给出n，求1~n（n≤200）中有多少奇数有恰好8个正因子。
· 【解析】
因为n≤200，O(n2)的算法都不会炸掉……因此直接枚举1~n，再O(n)找出因子数就可以了。其实也可以打表，这玩意200以内都没有几个。
· 【源代码】
/*Lucky_Glass*/#include#include #include using namespace std;int F(int x){ int ret=0; for(int i=1;i<=x;i++) if(x%i==0) ret++; return ret;}int main(){ int n,tot=0; scanf("%d",&n); for(int i=1;i<=n;i+=2) { if(F(i)==8) tot++; } printf("%d\n",tot); return 0;}
◆C题◆ To Infinity ⚔结论⚔
· 【翻译】
给出一个长度不超过100的数字串，每过一天，对于数字串中的每一个第i个字符，会变成 第i个字符的值 个第i个字符。
比如数字串"1325"一天后会变成"13332255555"。你需要求出5*1015天后第k（k≤1018）个字符是什么。
· 【解析】
我们可以发现每个字符是成次方翻倍的，即若第i个字符数值为t，则r天后会变成 tr 个t。然后我们可以发现，除了1，其他数的 5*105 次方远远的超过了 1018 。所以我们枚举0~len-1的字符，若发现前k个字符中包含不为1的字符，则答案就是出现得最早的不为1的字符——因为5*105天后它的数量必然超过k。若没有，则答案为1。
· 【源代码】
/*Lucky_Glass*/#include#include #include #include using namespace std;typedef long long ll;ll k;char S[105];vector POW[10];int main(){ scanf("%s%lld",S,&k); int len=strlen(S); for(int i=0;i
◆D题◆ AtCoder Express 2 ⚔前缀和⚔
· 【翻译】
直线上有n座城市从左到右编号为1~n，一条铁路连接它们。有m辆火车，给出它们的出发城市和终止城市。共q次询问，给出i,j，回答共有多少辆火车只在城市i~j之间行驶（不是恰好，只要在之间就可以）。
· 【解析】
这道题本质就是给出一些线段，求共有多少线段在区间[l,r]中。
可以用分段前缀和解决，定义A[i][j]为起始点为i，终止点为j的火车数量；B[i][j]为起始点为i，终止点不超过j的火车的数量；C[i][j]为起始点大于等于i，终止点小于等于j的火车的数量，其实也就是答案。
输入时直接统计A[i][j]；B[i][j]可以用O(n2)的复杂度递推——B[i][j]=B[i][j-1]+A[i][j]；C也可以用O(n2)递推——C[i][j]=C[i+1][j]+B[i][j]。
然后就输出答案了。
当然还有一种做法是将B数组前缀和为sum，即sum[i][j]表示 B[1~i][j] 。而我们的答案就是 B[l~r][r]，就可以通过前缀和解决，即 sum[r]-sum[l-1]。
· 【源代码】
/*Lucky_Glass*/#include#include #include using namespace std;int n,m,q;int A[505][505],B[505][505],C[505][505];int main(){ //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;i++) { int l,r;scanf("%d%d",&l,&r); A[l][r]++; } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) B[i][j]=B[i][j-1]+A[i][j]; for(int i=n;i>=1;i--) for(int j=i;j<=n;j++) C[i][j]=C[i+1][j]+B[i][j]; for(int i=0;i
个人觉得不是很难……
The End
Thanks for reading!
- Lucky_Glass