diverta 2019 Programming Contest

　　A：签到。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

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,k;

signed main()

{

	n=read(),k=read();

	cout<<n-k+1;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：签到。背包。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 3010

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 r,g,b,n;

ll f[N];

signed main()

{

	r=read(),g=read(),b=read(),n=read();

	f[0]=1;

	for (int i=r;i<=n;i++) f[i]+=f[i-r];

	for (int i=g;i<=n;i++) f[i]+=f[i-g];

	for (int i=b;i<=n;i++) f[i]+=f[i-b];

	cout<<f[n];

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：太难了吧。先统计一下内部的AB，然后只留下首尾两字符，显然只有BB、AA、BA是有用的。把BA全部接起来，相当于至多剩下一个BA，将其接在BB前或者AA后。AABB两两配对。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 10010

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,ans,f[N][2];

char s[N][12];

signed main()

{

	n=read();

	for (int i=1;i<=n;i++) scanf("%s",s[i]+1);

	for (int i=1;i<=n;i++)

	{

		int m=strlen(s[i]+1);

		for (int j=1;j<m;j++)

		if (s[i][j]=='A'&&s[i][j+1]=='B') ans++;

		if (s[i][1]=='A') f[i][0]=0;

		else if (s[i][1]=='B') f[i][0]=1;

		else f[i][0]=2;

		if (s[i][m]=='A') f[i][1]=0;

		else if (s[i][m]=='B') f[i][1]=1;

		else f[i][1]=2;

	}

	int cnt0=0,cnt1=0,cnt10=0;

	for (int i=1;i<=n;i++)

	{

		if (f[i][0]==1&&f[i][1]==0) cnt10++;

		else if (f[i][1]==0) cnt0++;

		else if (f[i][0]==1) cnt1++;

	}

	if (cnt10) ans+=cnt10-1,cnt10=1;

	if (cnt0&&cnt10) ans++,cnt10=0;

	ans+=min(cnt0+cnt10,cnt1);

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：设n=km+x(0<x<m)。则[n/m]=n%m即k=n-km k(m+1)=n 枚举n的因子即可，注意判断0<x<m。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

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;

}

ll n,ans;

signed main()

{

	cin>>n;

	for (ll i=1;i*i<=n;i++)

	if (n%i==0)

	{

		if ((i-1)*(n/i+1)>n) ans+=i-1;

		if (i*i!=n) if ((n/i-1)*(i+1)>n) ans+=n/i-1;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：做一个异或前缀和，则要选一个x、0交替序列。如果序列异或和不为0，则x只能取该值。否则枚举x。都是要用O(x个数)的复杂度统计序列个数。找出所有x的位置，前缀和求出之间0的个数，然后做一个dp即可，即f[i][0/1]为到第i个位置时最后一个取的是01的方案数，注意一下细节即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 2000010

#define P 1000000007

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],s[N],id[N],nxt[N],p[N],b[N],f[N][2],m,ans;

int ksm(int a,int k)

{

	int s=1;

	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;

	return s;

}

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int solve(int x)

{

	if (p[x]<=n)

	{

		id[m=1]=p[x];

		while (nxt[id[m]]<=n) id[m+1]=nxt[id[m]],m++;

	}

	else return 0;

	int t=0;

	for (int i=1;i<=m;i++)

	{

		b[++t]=-1;

		if (i<m) b[++t]=s[id[i+1]]-s[id[i]];

	}

	f[0][0]=1;

	for (int i=1;i<=t;i++)

	{

		f[i][0]=f[i][1]=0;

		if (b[i]==-1)

		{

			f[i][0]=f[i-1][0];

			f[i][1]=(f[i-1][1]+f[i-1][0])%P;

		}

		else

		{

			f[i][1]=f[i-1][1];

			f[i][0]=(f[i-1][0]+1ll*f[i-1][1]*b[i])%P;

		}

	}

	return f[t][1];

}

int solve2(int x)

{

	if (p[x]<=n)

	{

		id[m=1]=p[x];

		while (nxt[id[m]]<n) id[m+1]=nxt[id[m]],m++;

	}

	else return 0;

	int t=0;id[m+1]=n;

	for (int i=1;i<=m;i++)

	{

		b[++t]=-1;

		b[++t]=s[id[i+1]]-s[id[i]];

	}

	f[0][0]=1;

	for (int i=1;i<=t;i++)

	{

		f[i][0]=f[i][1]=0;

		if (b[i]==-1)

		{

			f[i][0]=f[i-1][0];

			f[i][1]=(f[i-1][1]+f[i-1][0])%P;

		}

		else

		{

			f[i][1]=f[i-1][1];

			f[i][0]=(f[i-1][0]+1ll*f[i-1][1]*b[i])%P;

		}

	}

	return f[t][0];

}

signed main()

{

	n=read();

	for (int i=1;i<=n;i++) a[i]=a[i-1]^read();

	for (int i=1;i<=n;i++)

	{

		s[i]=s[i-1];

		if (a[i]==0) s[i]++;

	}

	for (int i=0;i<(1<<20);i++) p[i]=n+1;

	for (int i=n;i>=1;i--)

	{

		nxt[i]=p[a[i]];

		p[a[i]]=i;

	}

	if (a[n]==0)

	{

		ans=ksm(2,s[n]-1);

		for (int i=1;i<(1<<20);i++) inc(ans,solve(i));

	}

	else ans=solve2(a[n]);

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　result：rank 76

巴特西

diverta 2019 Programming Contest

最新文章

热门文章