Comet OJ Contest 4

　　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 T,a[6],cnt[6];

signed main()

{

	T=read();

	while (T--)

	{

		for (int i=1;i<=5;i++) a[i]=read();

		memset(cnt,0,sizeof(cnt));

		for (int i=1;i<=5;i++) cnt[a[i]]++;

		int mx=0;

		for (int i=1;i<=5;i++) if (cnt[i]>cnt[mx]) mx=i;

		cout<<mx<<endl;

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：k是奇数时函数值均为1，k是偶数时每k+1个出现一个0。

#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);}

ll read()

{

	ll 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 T;

ll l,r,k;

ll f(ll x)

{

	return x-(x+1)/(k+1);

}

signed main()

{

	T=read();

	while (T--)

	{

		l=read(),r=read(),k=read();

		if (k&1) cout<<r-l+1<<endl;

		else cout<<f(r)-f(l-1)<<endl;

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：暴力枚举横竖各切多少刀，将矩阵压成一行可以得到该情况下列的划分位置，压成一列可以得到该情况下行的划分位置，然后二维前缀和暴力验证即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 1010

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);}

ll read()

{

	ll 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 T,n,m,k,tot,a[N][N],s[N],s2[N],s3[N][N],ans[N<<1],way[N<<1];

int calc(int x,int y,int l,int r)

{

	return s3[y][r]-s3[x-1][r]-s3[y][l-1]+s3[x-1][l-1];

}

signed main()

{

	T=read();

	while (T--)

	{

		n=read(),m=read(),k=read();tot=0;

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

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

			{

				char c=getc();

				if (c=='0') a[i][j]=0;else a[i][j]=1,tot++;

			}

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

		{

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

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

			if (a[i][j]) s[i]++;

		}

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

		{

			s2[i]=s2[i-1];

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

			if (a[j][i]) s2[i]++;

		}

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

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

			s3[i][j]=s3[i-1][j]+s3[i][j-1]-s3[i-1][j-1]+1-a[i][j];

		tot=n*m-tot;

		bool isac=0;

		for (int i=1;i<=k;i++) ans[i]=2010;

		for (int i=0;i<=k;i++)

		if (tot%((i+1)*(k-i+1))==0)

		{

			int sum=tot/((i+1)*(k-i+1));

			int last=0;

			int cnt=0;

			bool flag=1;

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

			if (cnt<i)

			{

				if ((j-last)*m-(s[j]-s[last])==sum*(k-i+1))

				{

					way[++cnt]=j;

					last=j;

				}

				else if ((j-last)*m-(s[j]-s[last])>sum*(k-i+1)) {flag=0;break;}

			}

			if (cnt<i) flag=0;

			if (flag)

			{

				last=0;

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

				if (cnt<k)

				{

					if ((j-last)*n-(s2[j]-s2[last])==sum*(i+1))

					{

						way[++cnt]=n+j-1;

						last=j;

					}

					else if ((j-last)*n-(s2[j]-s2[last])>sum*(i+1)) {flag=0;break;}

				}

			}

			if (cnt<k) flag=0;

			if (flag)

			{

				bool u=1;

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

				{

					for (int y=i+1;y<=k;y++)

					{

						if (calc(way[x-1]+1,way[x],(y==i+1?1:way[y-1]-n+2),way[y]-n+1)!=sum) {u=0;break;}

					}

					if (!u) break;

				}

				if (u)

				{

					isac=1;

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

					{

						if (way[j]<ans[j])

						{

							for (int x=1;x<=k;x++) ans[x]=way[x];

							break;

						}

						else if (way[j]>ans[j]) break;

					}

				}

			}

		}

		if (!isac) printf("Impossible\n");

		else

		{

			for (int i=1;i<k;i++) printf("%d ",ans[i]);

			printf("%d\n",ans[k]);

		}

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：打表可知10k~10k+9范围内0~9各出现一次，于是只需要计算零散部分。

#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);}

ll read()

{

	ll 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 l,r,a[30],f[1000000];

int ff(ll n)

{

	if (n<1000000) return f[n];

	int cnt=0;

	while (n) a[++cnt]=n%10,n/=10;

	for (int j=1;j<cnt;j++) a[j]+=a[j+1];

	a[cnt]=0;

	ll t=0;

	for (int j=cnt;j>=1;j--) t=t*10+a[j]%10;

	return ff(t);

}

ll calc(ll n)

{

	int s=0;int w=ff(n/10*10);

	for (ll i=n/10*10;i<=n;i++) s+=(w+(i-n/10*10))%10;

	return n/10*45+s;

}

signed main()

{

	for (int i=0;i<=9;i++) f[i]=i;

	for (int i=10;i<=1000000;i++)

	{

		ll cnt=0,x=i;

		while (x) a[++cnt]=x%10,x/=10;

		for (int j=1;j<cnt;j++) a[j]+=a[j+1];

		a[cnt]=0;

		ll t=0;

		for (int j=cnt;j>=1;j--) t=t*10+a[j]%10;

		f[i]=f[t];

	}

	int T=read();

	while (T--)

	{

		l=read(),r=read();

		cout<<calc(r)-calc(l-1)<<endl;

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　先咕着。

巴特西

Comet OJ Contest 4

最新文章

热门文章