SJTU ACM 2022 Preseason Training - Warmup

A - Handling the Blocks Gym - 103388H

题意

给定一个排列，每个数都有个颜色，同颜色的可以交换位置，求是否可以将此序列排序。

解法

套路题，想将其排序，考虑这个序列能否与其下标形成置换环。

而题目中的颜色就是制约是否能成为置换环。

用时：6min

const int N = 1e5 + 10;
 
int n, k;
int a[N], c[N];
 
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i]>>c[i];
	for(int i=1;i<=n;i++) 
		if(c[i] != c[a[i]])
		{
			cout<<"N"<<endl;
			return ;
		}
	cout<<"Y"<<endl;
}

B - Dividing Candy Gym - 103185D

题意

2048典中典。

有一天他们一起得到了 \(n\) 盒糖果，里面糖果的数量都是 \(2\) 的幂。现在他们想知道，如果不允许拆开盒子，他们是否能够让两人得到的糖果总数都是 \(2\) 的幂？

解法

每两个 \(x\) 能合成一个 \(x + 1\)，模拟。

const int N = 1e5 + 10;

int n;
int a[N];

void solve()
{
	cin>>n;
	if(n == 1) 
	{
		cout<<"N"<<endl;
		return ;
	}

	for(int i=1,x;i<=n;i++) cin>>x,a[x]++;
	for(int i=0;i<N;i++)
		if(a[i] >= 2) 
			a[i+1] += a[i] / 2, a[i] %= 2;

	int cnt = 0;
	for(int i=0;i<N;i++) // 这里写成<=1e5寄了一发，没有考虑到1e5也可以进位
		if(a[i])
			cnt += a[i];

	if(cnt > 2) cout<<"N"<<endl;
	else cout<<"Y"<<endl;
}

C - LRU Gym - 103366J

题意

给出 cache 的工作方式:

1. 如果请求的块在已存储在cache中，则成功访问。
2. 否则，CPU只能从内存中访问该块并将该块写入cache中。如果cache未满，则将块追加到缓存中。
3. 如果cache已满，则将用新块替换已在cache中最长时间的未被访问的块。

再给出一个长为 \(n\) 的操作序列，要求至少要访问成功 \(k\) 次，求 cache 大小至少为多少。

解法

看到至少为多少，又发现答案有二段性，一眼丁真二分。

const int N = 1e5 + 10;

int n, k;
int a[N];

int solve(int m)
{
	map<int,int> h;
	queue<int> q;

	int cnt = 0, ans = 0;
	for(int i=1;i<=n;i++)
	{
		if(h[a[i]] == 0) h[a[i]] ++, cnt ++;
		else h[a[i]] ++, ans ++;
		q.push(a[i]);
		while(cnt > m)
		{
			int u = q.front();
			q.pop();
			h[u] --;
			if(h[u] == 0) cnt --;
		}
	}
	return ans;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];

	if(solve(n) <= k) 
	{
		cout<<"cbddl";
		return 0;
	}

	int l = 0, r = n+1;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(solve(mid) >= k) r = mid;
		else l = mid + 1; 
	}

	cout<<l;

    return 0;
}