2020ICPC区域赛南京站

K Co-prime Permutation

解题思路:

首先，根据样例2不难发现，\(k\)的下界为\(1\)，因为1和排列中的任何数都会互质。

其次，我们考虑下上界大概是多少，也就是\(k = n\)是否一定合法。

假设，我们有一个初识排列\(p_i = i\).此时我们有\(1\)个元素和他的下标互质。

根据经验，我们将升序排列的元素向左错位一个偏移量就会得到\(p_1 = 2，p_2 = 3,...,p_n = 1\).此时，有\(n\)个元素和下标互质。

如果我们要恰好\(k\)个元素和下标互质，那么我们将前\(k\)个数看作一个环，同时向左错位一个偏移量即可。

注意，\(k=1\)的情况要特判。该情况上面也已经讨论过。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a,ll b)
{
	return b ? gcd(b,a %b): a;
}

void solve()
{
	int n,k;
	scanf("%d %d",&n,&k);
	if(k == 0)
	{
		puts("-1");
	}
	else if(k == 1)
	{
		for(int i = 1;i<=n;i++)
		{
			printf("%d ",i);
		}
	}
	else
	{
		vector<int> a(n + 1);
		int cnt = 2;
		for(int i = 1;i<=k;i++)
		{
			a[i] = cnt ++;
			if(cnt > k)
			{
				cnt = 1;
			}
		}
		for(int i = k + 1;i<=n;i++)
		{
			a[i] = i;
		}
		cnt = 0;
		for(int i = 1;i<=n;i++)
		{
			printf("%d ",a[i]);
		}
	}
}

int main()
{
	int t = 1;
	while(t--)
	{
		solve();
	}
	return 0;
}

L Let's Play Curling

解题思路:

稍微写一下样例，不难发现，能对答案产生贡献的红球之间没有一个蓝球。

所以，本题能够转化为，没两蓝球之间的最大红球个数。

排序后，双指针遍历即可。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;
void solve()
{
	
	scanf("%d %d",&n,&m);
	vector<int> a(n + 1),b(m + 1);
	unordered_map<int,int> q;
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		q[a[i]] ++;
	}
	for(int i = 1;i<=m;i++)
	{
		scanf("%d",&b[i]);
	}
	sort(a.begin() + 1,a.end());
	sort(b.begin() + 1,b.end());
	a.erase(unique(a.begin() + 1,a.end()),a.end());
	b.erase(unique(b.begin() + 1,b.end()),b.end());
	int i = 1;
	int j = 1;
	ll ans = 0;
	n = a.size() - 1;
	m = b.size() - 1;
//	for(int i = 1;i<=n;i++)
//	{
//		cout<<a[i]<<' ';
//	}
//	cout<<endl;
//	for(int i= 1;i<=m;i++)
//	{
//		cout<<b[i]<<' ';
//	}
//	cout<<endl;
	while(i <= n && j <= m)
	{
		ll cnt = 0;
		while(j <= m && b[j] <= a[i])
		{
			if(a[i] == b[j])
			{
				i ++;
				j ++;
			}
			else
			{
				j ++;
			}
		}
		if(j > m)
		{
			break;
		}
		while(i <= n && a[i] <= b[j])
		{
//			cout<<i<<' '<<a[i]<<endl;
			if(a[i] == b[j])
			{
				i ++;
				j ++;
				ans = max(ans,cnt);
				cnt = 0;
				continue;
			}
			else
			{
				cnt += q[a[i]];
				i ++;
				
			}
			
		}
//		cout<<i<<' '<<j<<' '<<cnt<<endl;
		ans = max(ans,cnt);
	}
	ll sum = 0;
	while(i <= n)
	{
		sum += q[a[i]];
		i ++;
	}
	ans = max(sum,ans);
	if(ans == 0)
	{
		puts("Impossible");
	}
	else
	{
		printf("%lld\n",ans);
	}
}

int main()
{
	int t = 1;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}