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_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=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_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=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!!!!!

}

　　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_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=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。

　　再冷静一下发现，我们对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_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	scanf("%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怎么是这种不可能会的板子题啊