A. Subtle Substring Subtraction

题目链接：Problem - A - Codeforces

样例输入： 

5
aba
abc
cba
n
codeforces

样例输出：

Alice 2
Alice 4
Alice 4
Bob 14
Alice 93

题意：给定一个长度为n的字符串，然后Alice和Bob轮流操作，Alice每次取走一段长度为偶数的字符串，Bob每次取走一段长度为奇数的字符串，每次操作得到的价值就是所有字符的价值和，每个字符的价值就是ascall码-96.输出谁获得的价值大并且输出价值差。

分析：如果原串长度为偶数那么Alice一次取完最优，否则Alice取n-1个字符，剩下一个字符，贪心选择一下就行。特别需要注意的一点就是只有一个字符的情况，这种情况Alice无法取，那么就是Bob获胜。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
char s[N+1];
int main()
{int T;cin>>T;while(T--){scanf("%s",s+1);int n=strlen(s+1);if(n==1){printf("Bob %d\n",s[1]-'a'+1);continue;} int ans=0;for(int i=1;i<=n;i++)ans+=s[i]-'a'+1;printf("Alice ");if(n&1)printf("%d\n",max(ans-2*(s[1]-'a'+1),ans-2*(s[n]-'a'+1)));elseprintf("%d\n",ans);}return 0;
} 

B. A Perfectly Balanced String?

题目链接：Problem - B - Codeforces

样例输入： 

5
aba
abb
abc
aaaaa
abcba

样例输出：

YES
NO
YES
YES
NO

题意：给定一个字符串，判断一个字符串是不是perfectly balanced，当且仅当对于s任意的一个子串t，都有字符u和字符v在其中出现的次数差不大于1时s为perfectly balanced，其中u和v必须在s中出现过。

分析：我们首先需要统计一下s串中出现过多少中不同的字符，然后我们讨论同一个字符相隔的距离，如果说距离小于不同字符数说明在其中至少有一个字符没有出现过，那么我们选以这个字符为两端的字符串就不满足题目中的定义，如果没有这种情况就说明s为perfectly balanced。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int f[N][26];
bool vis[26];
char s[N];
int main()
{int T;cin>>T;while(T--){scanf("%s",s+1);int n=strlen(s+1);memset(vis,false,sizeof vis);int cnt=0;for(int i=1;i<=n;i++)if(!vis[s[i]-'a']) vis[s[i]-'a']=true,cnt++;bool flag=true;for(int i=2;i<=n;i++){for(int j=0;j<26;j++)f[i][j]=f[i-1][j];f[i][s[i-1]-'a']=i-1;if(!f[i][s[i]-'a']) continue;if(i-f[i][s[i]-'a']<cnt) flag=false;}if(flag) puts("YES");else puts("NO");}return 0;
}

C. Palindrome Basis

题目链接：Problem - C - Codeforces

样例输入： 

2
5
12

样例输出：

7
74

题意：给定一个n，将n分解为若干个回文数的和式，问分解方案数。

分析：n是小于1e4的，直接暴力预处理出小于1e4的回文数，然后直接看成一个完全背包直接求解即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=4e4+10,mod=1e9+7;
int f[N];
int a[N],tt;
bool check(int x)
{int tx=x,y=0;while(tx){y=y*10+tx%10;tx/=10;}return x==y;
}
int main()
{for(int i=1;i<N;i++)if(check(i)) a[++tt]=i;f[0]=1;for(int i=1;i<=tt;i++)for(int j=a[i];j<N;j++)f[j]=(f[j]+f[j-a[i]])%mod;int T;cin>>T;while(T--){int n;scanf("%d",&n);printf("%d\n",f[n]);}return 0;
}

D. Lost Arithmetic Progression

题目链接：Problem - D - Codeforces

样例输入：

8
-3 1 7
-1 2 4
-9 3 11
0 6 3
2 5 5
7 5 4
2 2 11
10 5 3
0 2 9
2 4 3
-11 4 12
1 12 2
-27 4 7
-17 8 2
-8400 420 1000000000
0 4620 10

样例输出：

0
10
-1
0
-1
21
0
273000

题意：给定一个等差序列B和C，求解等差序列A的方案数使得满足C中包含所有A和B的公共项。

分析：首先我们能够发现等差数列A的公差一定是C的公差的因子，所以我们可以考虑枚举C的公差的因子来求取对于每一种因子对应的A的方案数，本质就是我们在C数组上进行向左向右扩展，假如我们能向左扩展p个点，向右扩展q个点，那么总的方案数就是(p+1)*(q+1)，因为还要包含不扩展的一种情况，扩展的过程中一定要保证不能使得扩展出b数组中有但是c数组中没有的元素。我们先来看一下什么情况下对应着无解情况，其实就是c数组中出现了b数组中不存在的元素，否则我们直接令a数组等于c数组就是一个解，那么我们怎么判断c数组中是否有b数组中不存在的元素呢？就是首先要保证c数组的最小值要大于b数组的最小值，c数组的最大值要小于b数组的最大值，其次还要保证c数组的第一项在b数组中以及c数组的公差是b数组公差的倍数，这样才能保证c数组中的元素都在b数组中出现过。下面我们来看一下如何向左扩展，首先假设我们现在枚举a的公差为d，那么我们先求出来lcm(d,q)，q是b数组的公差，那么每隔lcm(d,q)个数就会重复一次，我们从c数组的左边界lc开始向左扩展，第一个重合的位置是lc-lcm(d,q),如果这个位置b数组没有值，那么这个时候c数组就可以一直向左扩展而不受限制，那么这种情况对应着无穷多解，如果b数组有值那么这个位置a数组是不可能扩展到的，因为c数组没有这个值，那么a数组能够扩展到的最左边就是lc-lcm(d,q)+d,也就是重合元素的位置的右面一个位置，这样我们就求得了左边最多扩展几个元素，右边扩展也是同理的，这里就不赘述了

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10,mod=1e9+7;
long long LCM(long long a,long long b)
{return a/__gcd(a,b)*b;
}
int main()
{int T;cin>>T;while(T--){long long b,q,y,c,r,z;scanf("%lld%lld%lld%lld%lld%lld",&b,&q,&y,&c,&r,&z);long long lb=b,rb=b+(y-1)*q;long long lc=c,rc=c+(z-1)*r;if(lb>lc||rb<rc){puts("0");continue;}else if((lc-lb)%q)//保证c的第一项在b中出现过 {puts("0");continue;}else if(z!=1&&(r%q))//c不只有一项时c的所有项都要在b中出现过 {puts("0");continue;}long long ans=0;for(long long d=1;d<=sqrt(r);d++){if(r%d) continue;long long lcm=LCM(d,q);if(lc-lcm<lb||rc+lcm>rb)//直接无限解 {ans=-1;break;}if(LCM(d,q)%r==0)//保证c数组符合题意 ans=(ans+(lcm/d)*(lcm/d))%mod;if(d*d==r) continue;long long t=r/d;lcm=LCM(t,q);if(lc-lcm<lb||rc+lcm>rb){ans=-1;break;}if(LCM(t,q)%r==0)//保证c数组符合题意ans=(ans+(lcm/t)*(lcm/t))%mod;}printf("%lld\n",ans);}return 0;
}