2018 CCPC 桂林站（upc复现赛）补题
G.Greatest Common Divisor（思维）
求相邻数的差值的gcd，对gcd分解素因子，对所有的素因子做一次遍历，找出最小答案。
几个样例： ans : 0 1 0 2
3
3 6 9
1
1
1
2
2
11 76
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int MAXN= 1e5+; LL t, n, a[MAXN], fac[], cnt;
LL gcd(LL a, LL b){return b== ? a : gcd(b, a%b);}
void work(LL x){
LL temp = x;
for(LL i=; i*i<=temp; i++)
if(x%i == ) {
fac[++cnt] = i;
while(x%i == ) x /= i;
}
if(x>) fac[++cnt] = x;
}
int main()
{
LL Case = ;
cin >> t;
while(t--){
cnt = ;
bool flag1=true, flag2=true;
scanf("%lld", &n);
for(LL i=; i<=n; i++) scanf("%lld", &a[i]);
sort(a+, a+n+);
n = unique(a+, a+n+) - a - ;
printf("Case %lld: ", ++Case); if(n == ){
if(a[] == ) cout << "" << endl;
else cout << "" << endl;
continue;
} LL temp = a[]-a[];
for(LL i=; i<=n; i++)
temp = gcd(temp, a[i]-a[i-]); if(temp == ){
cout << "-1" << endl;
continue;
}
work(temp);
LL ans = 1e17;
for(LL i=; i<=cnt; i++){
if(a[] % fac[i] == ) ans = ;
ans = min(ans, fac[i]-(a[]%fac[i]));
}
cout << ans << endl;
}
}
J.石头游戏 （博弈）
Alice和Bob总是在玩游戏！今天的比赛是关于从石堆中依次取出石头。
有n堆石头，第i堆包含A [i]个石头。
由于每个堆中的宝石数量与其邻居的宝石数量不同，因此他们决定在不打破该属性的情况下从其中一个中取出一块石头。Alice先拿。
规定当谁不能拿石头将输掉比赛。
现在给出一个数字N和N个数字代表每堆石子的个数，你要确定最后的获胜者，假设他们都足够聪明。
Ps: 你应该注意到即使是一堆0石头仍然被视为一堆！
第一次看题时没有看到每次限取一颗，后来发现时比赛已经快结束了orz。读错题坑了队友。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e5+;
int num[maxn],a[maxn]; int main()
{
int t,n;
scanf("%d",&t);
for(int k=;k<=t;k++)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&num[i]);
a[i]=num[i];
} int ans=,pos=;
if(num[]<num[])
{
int st=,t=;
while(num[st]<num[st+])
{
pos=st;
num[st]=t;
st++; t++;
}
pos++;
}
if(num[n]<num[n-])
{
int st=n,t=;
while(num[st]<num[st-])
{
pos=st;
num[st]=t;
st--; t++;
}
pos--;
}
bool flag=true;
for(int i=;i<n;i++)
{
flag=false;
if(num[i]<num[i-]&&num[i]<num[i+])
{
int st=,s=i;
while(num[s]<num[s-])
{
num[s]=st;
s--;st++;
}
num[s]=max(num[s-],num[s+])+;
st=;s=i;
while(num[s]<num[s+])
{
num[s]=st;
s++;st++;
}
num[s]=max(num[s-],num[s+])+;
}
}
if(num[]>num[]+)
num[]=num[]-;
if(num[n]>num[n-]+)
num[n]=num[n-]-;
for(int i=;i<=n;i++)
{
if(num[i]>num[i-]&&num[i]>num[i+])
num[i]=max(num[i-],num[i+])+;
ans+=a[i]-num[i];
}
if(ans&)
cout<<"Case "<<k<<": Alice"<<endl;
else
cout<<"Case "<<k<<": Bob"<<endl;
}
return ;
}
H.汉明距离 (字符串贪心构造)
在信息理论中，两个相等长度的串之间的汉明距离是指相同位置字符不同的数量。换句话说，它计算将一个字符串更改为另一个字符串所需的最小替换次数，或者可能将一个字符串转换为另一个字符串的最小更改数。
假设有两个字符串s1,s2具有相同的长度，仅限于包含小写字符，找到一个相同长度的、字典序最小的字符串s，使得s1,s2与s的汉明距离相等。
一开始发现情况太多被劝退的，实际发现也没那么难以实现。emm...一言难尽。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1e4+;
char c1[maxn],c2[maxn],c3[maxn];
int sum[maxn];
char MIN(char a,char b)
{
for(char i='a'; i<='z'; i++)
{
if(i!=a&&i!=b)
return i;
}
}
int main()
{
int t;
while(~scanf("%d",&t))
{
for(int i=; i<=t; i++)
{
scanf("%s%s",c1,c2);
int len=strlen(c1);
sum[len]=;
for(int j=len-; j>=; j--)
{
sum[j]=sum[j+];
if(c1[j]!=c2[j])
sum[j]++;
}
int num=;
for(int j=; j<len; j++)
{
if(abs(num) < sum[j+]||c1[j]==c2[j])
{
c3[j]='a';
if(c1[j]=='a'&&c2[j]!='a')
num++;
if(c1[j]!='a'&&c2[j]=='a')
num--;
continue;
}
else
{
char ch=MIN(c1[j],c2[j]);
if(num>)
{
if(ch<c2[j]&&num==sum[j+])
c3[j]=ch;
else
{
c3[j]=c2[j];
num--;
}
}
else if(num<)
{
if(ch<c1[j]&&-num==sum[j+])
c3[j]=ch;
else
{
c3[j]=c1[j];
num++;
}
}
else
c3[j]=ch;
}
}
c3[len]='\0';
printf("Case %d: %s\n",i,c3);
}
}
return ;
}