Mail.Ru Cup 2018 Round 3

时间：2021-12-27 18:42:17

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

}

　　G：先暴力让t%n==0。然后考虑预处理出当t=n时每个点到达的位置，如果能求出，将该过程进行t/n轮即可，可以倍增。注意到对于t=n~1的每一步，实际上是对每个点将到达的位置做一个区间复制与平移操作，可持久化treap维护即可。

　　注意到如果使用普通的随机优先级treap，我们区间操作时会改变每个点的优先级，这样实际上是无法保证复杂度的。（我一直以为写挂了调了一天）考虑使用clj论文中的随机化合并方法，即Mail.Ru Cup 2018 Round 3

　　然而即使这样还是会出现深度变得很大的情况。使用朝鲜树式重构，超过一定深度直接拍扁重构即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cassert>

using namespace std;

#define ll long long

#define N 100010

#define lson tree[k].ch[0]

#define rson tree[k].ch[1]

#define pii pair<int,int>

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,s,to[N][50],cnt,root;

ll t;

struct data{int ch[2],x,size,d;

}tree[N<<8];

int jump(ll x,ll y){if (x<=m) x+=y;else x-=y;if (x>n) x=(x-1)%n+1;else x=(x%n+n-1)%n+1;return x;}

void up(int k){tree[k].size=tree[lson].size+tree[rson].size+1;tree[k].d=max(tree[lson].d,tree[rson].d)+1;}

int newpoint(int x){cnt++;tree[cnt].x=x,tree[cnt].size=1,tree[cnt].d=1;tree[cnt].ch[0]=tree[cnt].ch[1]=0;return cnt;}

void getto(int k)

{

	if (lson) getto(lson);

	to[++cnt][0]=tree[k].x;

	if (rson) getto(rson);

}

int merge(int x,int y)

{

	if (!y||!x) {tree[++cnt]=tree[x|y];return cnt;}

	int k=++cnt;

	if (1ll*rand()*(tree[x].size+tree[y].size)<1ll*tree[x].size*RAND_MAX)

	{

		tree[k]=tree[x];

		rson=merge(rson,y);

		up(k);

	}

	else

	{

		tree[k]=tree[y];

		lson=merge(x,lson);

		up(k);

	}

	return k;

}

pii split(int x,int u)

{

	if (!x) return make_pair(0,0);

	int k=++cnt;tree[k]=tree[x];

	if (u==tree[k].size) return make_pair(k,0);

	if (u==0) return make_pair(0,k);

	if (tree[lson].size>=u)

	{

		pii t=split(lson,u);

		lson=t.second;up(k);

		return make_pair(t.first,k);

	}

	else if (tree[lson].size+1==u) {int t=rson;rson=0;up(k);return make_pair(k,t);}

	else

	{

		pii t=split(rson,u-tree[lson].size-1);

		rson=t.first;up(k);

		return make_pair(k,t.second);

	}

}

void build(){root=cnt=0;for (int i=1;i<=n;i++) root=merge(root,newpoint(to[i][0]));}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#endif

	srand(20020509);

	n=read(),m=read(),s=read();cin>>t;

	for (;t%n;t--) s=jump(s,t);t/=n;

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

	build();

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

	{

		int lastroot=root;

		if (m+i<=n)

		{

			pii a=split(lastroot,m+i),b=split(a.first,i);

			root=b.second;

		}

		else

		{

			pii a=split(lastroot,i),b=split(a.first,m+i-n);

			root=merge(a.second,b.first);

		}

		if (m+1-i>0)

		{

			pii a=split(lastroot,n-i),b=split(a.first,m-i);

			root=merge(root,b.second);

		}

		else

		{

			pii a=split(lastroot,m+n-i),b=split(a.first,n-i);

			root=merge(root,merge(a.second,b.first));

		}

		if (tree[root].d>200) cnt=0,getto(root),build();

	}

	cnt=0;getto(root);

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

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

		to[i][j]=to[to[i][j-1]][j-1];

	for (int j=49;~j;j--) if (t&(1ll<<j)) s=to[s][j];

	cout<<s;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　H：相当于判断是否存在首尾相同但本质不同的子串。因为只需要判断是否存在，在比较两个首尾相同的字符串时，可以只比较字符串第二位，因为如果其相同我们仍会继续比较以这个第二位为首的字符串。

　　考虑根号分块，将字符串长度以u=√Σk为界分为两组。

　　对于长度均小于u的组，考虑固定子串的末位字符，找到该字符的所有出现位置，然后暴力判断是否存在某一对位置，其前缀中有相邻字符满足第一位相同但第二位不同。这显然可以做到O(uΣk)。

　　然后考虑长度大于u的组，显然组内字符串数量不会超过u个，我们将其中每一个与其他所有字符串进行考虑。如果能将每一对以O(较短字符串长度)的复杂度check即可做到O(uΣk)。枚举长度较小的字符串中的每个相邻字符对，在较长字符串中找到首字符的出现位置，若第二个字符不同则记录；然后枚举末位字符在较长字符串中找到出现位置，如果前缀记录的东西有小于该位置的说明存在这样的字符串。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

#include<bitset>

using namespace std;

#define ll long long

#define N 300010

#define pii pair<int,int>

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,m,nxt[N],pos[N];

vector<int> a[N],b[N],c[N];

vector< pii > app[N];

signed main()

{

#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#endif

	T=read();

	while (T--)

	{

		n=read(),m=read();

		bool flag=0;

		int p=0,q=0,K=0;

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

		{

			c[i].clear();

			c[i].push_back(read());K+=c[i][0];

			for (int j=1;j<=c[i][0];j++) c[i].push_back(read());

		}

		int u=sqrt(K);

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

		if (c[i][0]>u) a[++p]=c[i];else b[++q]=c[i];

		for (int i=1;i<=n;i++) app[i].clear();

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

			for (int j=1;j<=b[i][0];j++)

			app[b[i][j]].push_back(make_pair(i,j));

		memset(nxt,255,sizeof(nxt));

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

		if (app[i].size()>1)

		{

			for (int j=0;j<app[i].size();j++)

			{

				int x=app[i][j].first,y=app[i][j].second;

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

				if (nxt[b[x][k]]!=-1&&nxt[b[x][k]]!=b[x][k+1]) {flag=1;break;}

				else nxt[b[x][k]]=b[x][k+1];

				if (flag) break;

			}

			for (int j=0;j<app[i].size();j++)

			{

				int x=app[i][j].first,y=app[i][j].second;

				for (int k=1;k<y;k++) nxt[b[x][k]]=-1;

			}

		}

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

		{

			for (int j=1;j<=a[i][0];j++) pos[a[i][j]]=j;

			for (int j=i+1;j<=p;j++)

			{

				int first=a[i][0]+1;

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

				{

					if (pos[a[j][k]]>first) {flag=1;break;}

					if (pos[a[j][k]]&&k<a[j][0]&&pos[a[j][k]]<a[i][0]&&a[j][k+1]!=a[i][pos[a[j][k]]+1]) first=min(first,pos[a[j][k]]);

				}

				if (flag) break;

			}

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

			{

				int first=a[i][0]+1;

				for (int k=1;k<=b[j][0];k++)

				{

					if (pos[b[j][k]]>first) {flag=1;break;}

					if (pos[b[j][k]]&&k<b[j][0]&&pos[b[j][k]]<a[i][0]&&b[j][k+1]!=a[i][pos[b[j][k]]+1]) first=min(first,pos[b[j][k]]);

				}

			}

			for (int j=1;j<=a[i][0];j++) pos[a[i][j]]=0;

		}

		if (flag) puts("Human");

		else puts("Robot");

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　

相关文章