首页 > 其他 > 详细

Mail.Ru Cup 2018 Round 3

时间：2019-02-16 19:41:43      阅读：295      评论：0      收藏：0      [点我收藏+]

　　A：签到

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 110
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,cnt[N];
signed main()
{
/*#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#endif*/
	n=read();
	for (int i=1;i<=n;i++)
	{
		int m=read();
		while (m--) cnt[read()]++;
	}
	for (int i=1;i<=100;i++) if (cnt[i]==n) cout<<i<<‘ ‘;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　B：考虑模意义下每个数的贡献即可。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 1100
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,m,cnt[N];
ll ans;
signed main()
{
/*#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#endif*/
	n=read(),m=read();
	for (int i=1;i<=m;i++) cnt[i*i%m]+=n/m+(n%m>=i);
	ans=1ll*cnt[0]*cnt[0];
	for (int i=1;i<m;i++) ans+=1ll*cnt[i]*cnt[m-i];
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　C：如果上一轮对方选择了某一组英雄中的一个，而另一个还没被选，显然只能选择他。否则显然应该先把每一组英雄中价值较大的选中，这样对方必须选择另一个，最后再将剩余英雄从大到小选取即可。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 2100
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,m,a[N<<1],match[N<<1],cnt;
bool flag[N<<1];
signed main()
{
/*#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#endif*/
	n=read(),m=read();
	for (int i=1;i<=2*n;i++) a[i]=read();
	for (int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		match[x]=y,match[y]=x;
	}
	int t=read(),x=0;
	if (t==2) {x=read();flag[x]=1;cnt++;}
	while (cnt<2*n)
	{
		if (match[x]&&!flag[match[x]]) cout<<match[x]<<endl,flag[match[x]]=1,cnt++;
		else
		{
			bool f=0;
			for (int i=1;i<=2*n;i++)
			if (match[i]&&!flag[i])
			{
				if (a[i]>a[match[i]]) cout<<i<<endl,flag[i]=1,cnt++;
				else cout<<match[i]<<endl,flag[match[i]]=1,cnt++;
				f=1;
				break;
			}
			if (!f)
			{
				int u=0;
				for (int i=1;i<=2*n;i++)
				if (!flag[i]&&a[i]>a[u]) u=i;
				cout<<u<<endl,flag[u]=1,cnt++;
			}
		}
		if (cnt==2*n) break;
		x=read();flag[x]=1;cnt++;
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

 

　　D：大胆猜想答案等于子树内叶子数量。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
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;
}
int n,fa[N],size[N],p[N],t;
struct data{int to,nxt;
}edge[N<<1];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k)
{
	size[k]=(p[k]==0);
	for (int i=p[k];i;i=edge[i].nxt)
	{
		dfs(edge[i].to);
		size[k]+=size[edge[i].to];
	}
}
signed main()
{
/*#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#endif*/
	n=read();
	for (int i=2;i<=n;i++) fa[i]=read(),addedge(fa[i],i);
	dfs(1);
	sort(size+1,size+n+1);
	for (int i=1;i<=n;i++) printf("%d ",size[i]);
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　E：暴力枚举0串的长度，显然1串的长度可以由此确定，然后哈希暴力匹配判断即可。复杂度大约线性。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define int long long
#define N 2000010
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,m,cnt0,cnt1,ans,Hash[2][N],P[2],Q[2][N];
char a[N],b[N];
int get(int x,int y,int op)
{
	return (Hash[op][y]-1ll*Hash[op][x-1]*Q[op][y-x+1]%P[op]+P[op])%P[op];
}
signed main()
{
/*#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#endif*/
	scanf("%s",a+1);n=strlen(a+1);
	scanf("%s",b+1);m=strlen(b+1);
	for (int i=1;i<=n;i++) if (a[i]==‘0‘) cnt0++;else cnt1++;
	P[0]=1000000007,P[1]=19260817;
	for (int i=1;i<=m;i++) Hash[0][i]=(Hash[0][i-1]*509ll+b[i])%P[0];
	for (int i=1;i<=m;i++) Hash[1][i]=(Hash[1][i-1]*509ll+b[i])%P[1];
	Q[0][0]=Q[1][0]=1;
	for (int i=1;i<=m;i++) Q[0][i]=Q[0][i-1]*509ll%P[0];
	for (int i=1;i<=m;i++) Q[1][i]=Q[1][i-1]*509ll%P[1];
	for (int i=1;i<=m;i++)
	if (m>cnt0*i&&(m-cnt0*i)%cnt1==0)
	{
		int j=(m-cnt0*i)/cnt1;
		int cur=1,pos0=0,pos1=0;
		for (int x=1;x<=n;x++)
		if (a[x]==‘0‘) pos0=cur,cur+=i;
		else pos1=cur,cur+=j;
		cur=1;int tot=1;
		if (i==j)
		{
			tot=0;
			for (int x=1;x<=i;x++)
			if (b[pos0+x-1]!=b[pos1+x-1]) {tot=1;break;}
		}
		if (tot==0) continue;
		for (int x=1;x<=n;x++)
		if (a[x]==‘0‘)
		{
			tot=(get(cur,cur+i-1,0)==get(pos0,pos0+i-1,0)&&get(cur,cur+i-1,1)==get(pos0,pos0+i-1,1));
			cur+=i;
			if (tot==0) break;
		}
		else
		{
			tot=(get(cur,cur+j-1,0)==get(pos1,pos1+j-1,0)&&get(cur,cur+j-1,1)==get(pos1,pos1+j-1,1));
			cur+=j;
			if (tot==0) break;
		}
		ans+=tot;
	}
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　F：先不考虑training。显然如果确定了切题集合，应该按照难度从高到低做。于是按难度从高到低排序，设f[i][j][k]为前i个题切j个，得到的分数和为k时的最小耗时。复杂度T*10*n^3。training时间可以三分，但套上去就多了个log跑不过了。事实上training时间不影响决策，并且有training后可以直接算出答案，dp完解方程即可。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 110
#define inf 10000000000000000
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,n;
const double eps=1E-8;
double c,t,f[N][N][N*10],p[N];
struct data
{
	int x,y;
	bool operator <(const data&a) const
	{
		return x>a.x;
	}
}a[N];
double work(double a,double b,double c)
{
	return (-b+sqrt(b*b-4*a*c))/(2*a);
}
int calc()
{
	for (int i=n*10;i>=0;i--)
		for (int j=0;j<=n;j++)
		{//c*x^2+(1-c(t-10*j))x+f[j][i]-(t-10*j)
			double u=max(0.0,work(c,1-c*(t-10*j),f[n][j][i]+10*j-t));
			if (f[n][j][i]/(u*c+1)+10*j+u<=t+eps) return i;
		}
}
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("f.in","r",stdin);
	freopen("f.out","w",stdout);
	const char LL[]="%I64d\n";
#endif
	T=read();
	p[0]=1;for (int i=1;i<=100;i++) p[i]=p[i-1]*0.9;
	while (T--)
	{
		n=read();
		cin>>c>>t;
		for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
		sort(a+1,a+n+1);
		for (int i=0;i<=n;i++)
			for (int j=0;j<=n;j++)
				for (int k=0;k<=n*10;k++)
				f[i][j][k]=inf;
		f[0][0][0]=0;
		for (int i=1;i<=n;i++)
			for (int j=0;j<=i;j++)
				for (int k=0;k<=j*10;k++)
				{
					f[i][j][k]=f[i-1][j][k];
					if (k>=a[i].y&&j) f[i][j][k]=min(f[i][j][k],f[i-1][j-1][k-a[i].y]+a[i].x/p[j]);
				}
		printf("%d\n",calc());
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　剩下的先咕着。

 

Mail.Ru Cup 2018 Round 3

原文：https://www.cnblogs.com/Gloid/p/10388719.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！