CF1701.

A. Grass Field

分析

有 \(0\) 个草地，答案为 \(0\)。

有 \(1 \sim 3\) 个草地，答案为 \(1\)。

有 \(4\) 个草地，答案为 \(2\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t, a[5][5];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	for(int i=1;i<=2;++i) for(int j=1;j<=2;++j) a[i][j]=read();
	int cnt0=0, cnt1=0;
	for(int i=1;i<=2;++i) for(int j=1;j<=2;++j) {
		if(a[i][j]) ++cnt1; else ++cnt0;
	}
	if(!cnt1) puts("0");
	else if(cnt1<4) puts("1");
	else puts("2");
}
int main() {
	t=read();
	while(t--) solve();
}

B. Permutation

分析

对于区间 \([1,n]\)，其中 \(n \neq 1\)，那么当 \(d = 2\) 的时候，成倍数关系的数对是最多的。直接输出 \(2\) 即可。

然后先把所有 \(1\) 和 \([2,n]\) 之间的所有偶数加入排列，并把每个加入排列的数打标记。之后对于每个没有被打标记的数，用类似埃氏筛的方式筛去它和它的 \(2\) 次幂倍并加入排列。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int t, cnt, n, p[N];
bool v[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	cnt=0;
	memset(v,0,sizeof(v));
	n=read();
	printf("2\n");
	int cnt=0;
	for(int i=1;i<=n;i<<=1) v[i]=1, p[++cnt]=i;
	for(int i=3;i<=n;i+=2) if(!v[i]) {
		for(int j=i;j<=n;j<<=1) v[j]=1, p[++cnt]=j;
	}
	for(int i=1;i<=n;++i) printf("%d%c",p[i]," \n"[i==n]);
}
int main() {
	t=read();
	while(t--) solve();
}

C. Schedule Management

分析

工人工作是同时进行的，不论是贪心还是 DP 都做不了，我还是太弱了……

二分答案转判定，明明想到了的，却没写出来……

二分一个 \(mid\)，表示用 \(mid\) 小时能否完成 \(m\) 个任务。对于每个工人，所有任务只有两种类型：精通的和不精通的。所以一个很显然的贪心策略就是，每一个任务都优先让精通它的工人去完成。记录 \(cnt_i\) 表示第 \(i\) 个工人精通的任务数量。

当 \(cnt_i < mid\) 时，\(i\) 不仅能够用 \(cnt_i\) 小时完成所有精通的任务，还有时间完成其他的任务，可是其他的任务只能用 \(\frac{1}{2}\) 的效率来完成，所以这种情况下一共能完成的任务数量为 \(cnt_i + \frac{mid - cnt_i}{2}\)。

否则只能够完成 \(cnt_i\) 个任务。

是不是一想就明白了呢？我还是趁早退役咯~

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int t, n, m, a[N], cnt[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
bool check(int x) {
	ll tot=0;
	for(int i=1;i<=n;++i) {
		if(cnt[i]<x) tot+=cnt[i]+(x-cnt[i])/2;
		else tot+=x;
	}
	return tot>=m;
}
void solve() {
	memset(cnt,0,sizeof(cnt));
	n=read(), m=read();
	for(int i=1;i<=m;++i) ++cnt[a[i]=read()];
	int l=0, r=0;
	for(int i=1;i<=n;++i) r=max(r,cnt[i]*2);
	while(l<r) {
		int mid=(l+r)/2;
		if(check(mid)) r=mid; else l=mid+1;
	}
	
	printf("%d\n",l);
}
int main() {
	t=read();
	while(t--) solve();
}

D. Permutation Restoration

分析

下文除法均向下取整。

对于每个 \(b_i\)，都有一个「决策区间」。意思是，只要 \(a_i\) 属于这个区间，那么就一定满足条件。

考虑求出这个区间，当 \(b_i\) 为 \(0\) 的时候，只需要保证 \(i < a_i\) 就好了，所以决策区间的左端点是 \(i+1\)，右端点一定是 \(n\)。

当 \(b_i > 0\) 时，其左右端点一定在 \([1,i]\) 里面，那就查找最小的使得 \(\frac{i}{x} \le b_i\) 的 \(x\) 作为做端点（因为 \(x\) 越小左式越大），查找最大的使得 \(\frac{i}{x} \ge b_i\) 的 \(x\) 作为右端点（因为 \(x\) 越大左式越小）。可以使用二分查找。

打表发现，如果 \(b_i > 0\)，那么左端点为 \(\frac{i}{b_i +1} +1\)，右端点为 \(\frac{i}{b_i}\)。证明？不会。

然后贪心，对于一个 \(i\)，将所有以它为左端点的元素加入决策集合，排除所有右端点小于 \(i\) 的元素，找到右端点最小的 \(x\) 并令 \(a_x = i\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<int,int>
#define fst first
#define sec second
#define pb push_back
const int N=5e5+5;
int t, n, m, b[N], d[N], ans[N];
priority_queue<PII > q;
vector<int> v[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void bsearch(int a,int b,int x,int& l,int& r) {
	int L=a, R=b;
	while(L<R) {
		int mid=(L+R)/2;
		if(b/mid<=x) R=mid; else L=mid+1; 
	}
	l=L;
	L=a, R=b;
	while(L<R) {
		int mid=(L+R+1)/2;
		if(b/mid>=x) L=mid; else R=mid-1;
	}
	r=L;
}
void solve() {
	n=read();
	for(int i=1;i<=n;++i) {
		b[i]=read();
		int l, r;
		if(!b[i]) { l=i+1, r=n; goto record; }
		// bsearch(1,i,b[i],l,r);
		l=i/(b[i]+1)+1, r=i/b[i];
		record: v[l].pb(i), d[i]=r;
		// printf("b[%d]=%d l: %d r: %d\n",i,b[i],l,r);
	}
	for(int i=1;i<=n;++i) {
		for(int j=0;j<v[i].size();++j)
			q.push(make_pair(-d[v[i][j]],v[i][j]));
		if(-q.top().fst<i) q.pop();
		ans[q.top().sec]=i, q.pop();
	}
	for(int i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]), v[i].clear();
}
int main() {
	t=read();
	while(t--) solve();
}

E. Text Editor

没看，不会。

F. Points

没看，不会。