Codeforces Round #470 Div. 1

　　A：暴力枚举x₂的因子，由此暴力枚举x₁，显然此时减去其最大质因子并+1即为最小x₀。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 1000010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,p[N],prime[N],cnt,ans=N;
bool flag[N];
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read();flag[1]=1;for (int i=2;i<=1000000;i++){if (!flag[i]) {prime[++cnt]=i;p[i]=i;}for (int j=1;j<=cnt&&prime[j]*i<=n;j++){flag[prime[j]*i]=1;p[prime[j]*i]=p[i];if (i%prime[j]==0) break;}}for (int i=1;i<=n;i++)if (n%i==0&&!flag[i]){for (int x=n-i+1;x<=n;x++)if (flag[x]) ans=min(ans,x-p[x]+1);}cout<<ans;return 0;//NOTICE LONG LONG!!!!!
}

　　B：小根堆维护每堆雪的体积，记录总偏移量，堆顶融化完就将其弹出。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;
#define ll long long
#define int long long
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,a[N],b[N],cnt;
priority_queue<int,vector<int>,greater<int> > q;
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read();for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=n;i++) b[i]=read();ll delta=0;for (int i=1;i<=n;i++){q.push(a[i]+delta);cnt++;ll ans=0;while (!q.empty()&&q.top()<=b[i]+delta) ans+=q.top()-delta,cnt--,q.pop();ans+=1ll*b[i]*cnt;delta+=b[i];printf("%I64d ",ans);}return 0;//NOTICE LONG LONG!!!!!
}

codeforces教程。　　C：建棵trie，维护子树内数的个数，暴力按位贪心即可。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;
#define ll long long
#define N 300010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,a[N],b[N],trie[N<<5][2],size[N<<5],cnt;
void ins(int x)
{int k=0;for (int i=31;~i;i--){if (!trie[k][(x&(1<<i))>0]) trie[k][(x&(1<<i))>0]=++cnt;k=trie[k][(x&(1<<i))>0];size[k]++;}
}
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read();for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=n;i++) ins(read());for (int i=1;i<=n;i++){int k=0,x=0;for (int j=31;~j;j--){if (a[i]&(1<<j)){if (size[trie[k][1]]) k=trie[k][1];else k=trie[k][0],x|=(1<<j);}else{if (size[trie[k][0]]) k=trie[k][0];else k=trie[k][1],x|=(1<<j);}size[k]--;}printf("%d ",x);}return 0;//NOTICE LONG LONG!!!!!
}

　　D：降智好题。首先发现BC可以相互转化，变换3次再删掉AAA即可。同时发现每次可以增加AA，由于可以删除AAA，也就是说可以任意增删AA。并且BC的数量不会减少且奇偶性不变。哇这个题好弱智！一发wa on 2。

　　冷静一下可以发现，当原串没有BC且目标串也没有BC时，我们是不能任意变换的，而只能删除AAA。于是特判一下这种情况。哇这个题好弱智！一发wa on 8。

xcode。　　再冷静一下发现，我们对A的增删事实上并不能在尾部进行。于是满足之前条件的同时，数一下原串尾部A的长度x和目标串尾部A的长度y。如果BC数量相同，只能通过删AAA来对尾部变换，于是判一下是否x%3==y%3&&x>=y；否则可以在任意位置截掉，只需要x>=y。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
char a[N],b[N];
int n,m,q,s1[N],s2[N];
int query1(int x,int y)
{int l=x,r=y+1,ans=y+1;while (l<=r){int mid=l+r>>1;if (s1[mid]==s1[y]) ans=mid,r=mid-1;else l=mid+1;}return y-ans+1;
}
int query2(int x,int y)
{int l=x,r=y+1,ans=y+1;while (l<=r){int mid=l+r>>1;if (s2[mid]==s2[y]) ans=mid,r=mid-1;else l=mid+1;}return y-ans+1;
}
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifscanf("%s",a+1);n=strlen(a+1);scanf("%s",b+1);m=strlen(b+1);for (int i=1;i<=n;i++) s1[i]=s1[i-1]+(a[i]!='A');for (int i=1;i<=m;i++) s2[i]=s2[i-1]+(b[i]!='A');q=read();while (q--){int l1=read(),r1=read(),l2=read(),r2=read();int x=s1[r1]-s1[l1-1],y=s2[r2]-s2[l2-1];if (x|y){int u=query1(l1,r1),v=query2(l2,r2);if (x==y){if (u%3==v%3&&u>=v) putchar('1');else putchar('0');}else if (x>y) putchar('0');else{if ((x&1)==(y&1)&&u>=v) putchar('1');else putchar('0');}}else{if ((r1-l1)%3==(r2-l2)%3&&(r1-l1>=r2-l2)) putchar('1');else putchar('0');}}return 0;//NOTICE LONG LONG!!!!!
}

　　E怎么是这种不可能会的板子题啊