我这个代码能力下降到\rm{-INF}

并查集板子打了15分钟 还有谁??

气死了

算了赶紧写完赶紧睡觉

A. Mahmoud and Ehab and the even-odd game(真长)

就这题!!!卡了我五分钟!!我觉得它长的像SG,是它的错还是我的?!

一定注意a \leq n!!

然后你就会发现这游戏最多就一轮

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n; scanf("%d",&n);
	if (n%2) cout<<"Ehab"<<endl;
	else cout<<"Mahmoud"<<endl;
}

B. Mahmoud and Ehab and the message(这个更长?)

然后并查集板子+map……能这个点打Cf的都能看出来也不说了……

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdlib>
#include<iterator>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;

int fa[100010]={0},hea[100010]={0};
ll cost[100010]={0},minc[100010]={0};
char words[100010][30]={0},mes[30]={0};
int n,kx,m,cache1,siz;
ll ans=0;
map <string,int> mapx;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline int findx(int e)
{
	if (fa[e]!=e) fa[e]=findx(fa[e]);
	return fa[e];
}
inline void mergex(int a,int b)
{
	fa[findx(b)]=findx(a);
}

int main()
{
	readx(n); readx(kx); readx(m);
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=n;i++) 
	{
		scanf("%s",words[i]);
		mapx[words[i]]=i;
	}
	for (int i=1;i<=n;i++) scanf("%lld",&cost[i]);
	
	for (int i=1;i<=kx;i++)
	{
		readx(siz); readx(hea[i]); minc[hea[i]]=cost[hea[i]];
		for (int j=2;j<=siz;j++)
		{
			readx(cache1);
			mergex(hea[i],cache1);
			minc[hea[i]]=min(minc[hea[i]],cost[cache1]);
		}
	}
	
	for (int i=1;i<=m;i++) 
	{
		scanf("%s",mes);
		ans+=minc[findx(mapx[mes])];
	}
	cout<<ans<<endl;
	return 0;
}

C. Mahmoud and Ehab and the wrong algorithm(哇,还是这么长)

送分(ming)构造题

两问分别长这样

注意第一问只有n \geq 5才有解……原因是层数和两个点的解的限制(也就是说第二层最少3个点然后第三层必须有两个点及以上((一个点的话那个算法也是正确的)))

D. Mahmoud and Ehab and another array construction task(最长!)

这题,扫一下然后质因数分解

如果分解有重那么立即断开,前面的原样输出,后面的贪心地选一个质数输出

注意特判

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdlib>
#include<iterator>
#include<algorithm>
#define ll long long
using namespace std;

int n,seq[2000010]={0},vis[2000010]={0};
int tvis[10010]={0},cpos,pnum[2000010]={0};
bool nnum[2000010]={0};

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void EulerShake(ll upat)
{
	int ctr1=0; nnum[0]=nnum[1]=true; 
	for (ll i=2;i<=upat;i++)
	{
		if (!nnum[i]) pnum[++ctr1]=i;
		for (int j=1;j<=ctr1 && pnum[j]*i<=upat;j++)
		{
			nnum[i*pnum[j]]=true;
			if (!(i%pnum[j])) break;
		}
	}
}
inline bool divi(int nq)
{
	int upat=sqrt(nq)+1,n1=nq;
	cpos=0;
	for (int i=2;i<=upat;i++)
	{
		if (n1%i==0)
		{
			tvis[++cpos]=i;
			n1=n1/i;
			upat=sqrt(n1)+1;
		}
		while (n1%i==0)
		{
			n1=n1/i;
			upat=sqrt(n1)+1;
		}
	}
	if (n1!=0 && n1!=1) tvis[++cpos]=n1;
	return 1;
}

inline bool solve(int now)
{
	divi(now);
	for (int i=1;i<=cpos;i++) if (vis[tvis[i]]) return false;
	for (int i=1;i<=cpos;i++) vis[tvis[i]]=1;
	return 1;
}

int main()
{
	readx(n); EulerShake(2000000);
	for (int i=1;i<=n;i++) readx(seq[i]);
	for (int i=1;i<=n;i++)
	{
		if (!solve(seq[i]))
		{
			for (int j=1;j<i;j++) printf("%d ",seq[j]);
			for (int j=seq[i]+1;;j++) if (solve(j)) { printf("%d ",j); break; }
			
			int pos=1;
			for (int j=i+1;j<=n;j++)
			{
				while (vis[pnum[pos]]) pos++;
				printf("%d ",pnum[pos]); pos++;
			}
			printf("\n");
			return 0;
		}
	}
	for (int i=1;i<=n;i++) printf("%d ",seq[i]); printf("\n");
	return 0;
}<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1">​</span>

E. Mahmoud and Ehab and the xor-MST(哈!变短了吧!)

我们考虑……有什么好考虑的。。。

那就……从高位来考虑?

当前考虑的,要求mst的点集的所有点权,在目前位上, 必然是n_1 \text{ — } n_x这一部分是0,然后n_{x+1} \text{ — } n_{last}1,那么点 x+1 \text{ — } last之间独立连边,1 \text{ — } x之间独立连边,这么做,可以保证对答案贡献都是0,是最优的。

·

但是如果当前确实有一个满足上述条件的x存在的话,

(其实也就是现在考虑的点集的最大点权的点,点权模掉2^{w-1}大于等于2^w,其中w是当前考虑的位数)

(也就是这一位上有1的出现,所以点被划成了这一位是0 \; , \; 1两个子点集)

那么还要把左右两个点集联通。先加上这样的代价 :2^w

·

我们其实并不关心这两个点集是怎么内部联通的,因为这个可以递归求解。把两个点集的点权模掉2^w之后就成为子问题了,对吧?

但是0集那个子问题是可以预处理的,要不然会T。

f[i]表示从02^i-1的贡献和。怎么转移?这个其实就是……你把它按照上面我说的拆一下点集就好了。然后方程在这儿:f[i]=2*f[i-1]+(1LL<<w-1)这个不难理解吧……

我希望我这题说明白了.

(我怕我long long的位运算出锅于是打了快速幂……)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdlib>
#include<iterator>
#include<algorithm>
#define ll long long
using namespace std;


ll f[100]={0};
ll n,ans=0;


inline ll fastpow(ll a,int p)
{
	ll ret=1;
	for (;p;p>>=1,a*=a) if (p&1) ret*=a;
	return ret;
}

inline void solve1(ll now,int w)
{
	if (w<0) return;
	ll mo=fastpow(2,w+1),lowx=fastpow(2,w); 
	if (now%mo>=lowx)//1
	{
		ans+=lowx+f[w];
		solve1(now%lowx,w-1);//1 part
	}
	//all 0
	else solve1(now,w-1);
}

int main()
{
	scanf("%lld",&n); n--;
	for (int i=1;i<=40;i++) f[i]=2*f[i-1]+fastpow(2,i-1);
	
	for (int w=40;w>=0;w--)
	{
		ll upat=fastpow(2,w);
		if (n>=upat) 
		{
			solve1(n,w);
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

F. Mahmoud and Ehab and yet another xor task

留坑

分类: Codeforces

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.