[Acwing] 第 28 场周赛

• • • 前言
    • A.
    • B.
    • C.

难度 : 入门+普及+提高

传送门 :

既然都提示暴力了,那么直接暴力就行 ;

typedef pair pii;
map mp;

const int N  = 1e5+10;
void solve()
{
	string s;cin>>s;
	int len = s.size()-1;
	int cnt = 0 ;
	
	for(int i =  0;i<=len;i++)
	{
		if(s[i] == 'Q')
			for(int j = i+1;j<=len;j++)
				if(s[j]=='A')
					for(int k = j+1;k<=len;k++)
					if(s[k] == 'Q' )
					++cnt;
	}			
	
	cout<>t;while(t -- )
    solve();
    return 0;
}

倍数筛质数的选法,对于每个数都标记一下,如果存在则出现它出现的次数
特别的 :
如果 _ _ g c d ( a , a ) = a __gcd(a,a) = a __gcd(a,a)=a

void get_div()
{
		for(int i=2;i<=N;i++)
		{
			int res  = 0 ;
			
			if(mp[i])
			res+=mp[i];
			
			if(st[i]) continue;
			for(int j = i+i;j<=N;j+=i)
			{
				st[j] = 1;
				if(mp[j])
				res+=mp[j];
			}
			
			ans = max(res,ans);
		}
	
}
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		mp[x]++;
	}
	get_div();
	cout<>t;while(t -- )
    solve();
    return 0;
}

显然,我们需要将能交换到的点放到一个集合里,但是如何判断是否是属于自己的牌子呢?

我们只需要再创建一个集合用来装我们本身的位置即可,因为范围小

对于每个集合我们都排序,之后判断当前集合是否是满足条件的即可

const int N  = 110;
int n;
int a[N],d[N],p[N];
vector A[N],B[N];

int find(int x)
{
	if(p[x]!=x)
	return p[x]  =find(p[x]);
	return p[x];
}

void megre(int a,int b)
{
	if(a<1 || a>n)
	return;

	p[find(a)] = find(b);
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	p[i]=i;
	
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>d[i];

	for(int i=1;i<=n;i++)
	{
		megre(i-d[i],i);
		megre(i+d[i],i);
	}

	for(int i = 1;i<=n;i++)
	{
		A[find(i)].pb(i);
		B[find(i)].pb(a[i]);
	}

	for(int i=1;i<=n;i++)
	{
		sort(B[i].begin(),B[i].end());

		if(A[i]!=B[i])
		{
			cout<<"NO"<>t;while(t -- )
    solve();
    return 0;
}