Codeforces Round #678 (Div.2)

比赛链接 / 官方题解链接

A. Reorder

$$\sum_{i=1}^n\sum_{j=i}^n\frac{a_j}{j}=\sum_{j=1}^n\sum_{i=1}^j\frac{a_j}{j}=\sum_{j=1}^n a_j$$

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 105;

int n, m;

int main(){
	int T; for(scanf("%d", &T); T; T--){
		scanf("%d%d", &n, &m);
		LL sum = 0;
		for(int i = 1; i <= n; i++){
			LL a; scanf("%lld", &a);
			sum += a;
		}
		puts(sum == m ? "YES" : "NO");
	}
	return 0;
}

---

B. Prime Square

形如

$$\begin{matrix} 1&0&0&\cdots&0&1\\ 1&1&0&\cdots&0&0\\ 0&1&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&1&0\\ 0&0&0&\cdots&1&1 \end{matrix}$$

即可。

#include<bits/stdc++.h>

using namespace std;

int main(){
	int T; for(scanf("%d", &T); T; T--){
		int n; scanf("%d", &n);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(i == j)	printf("%d%c", 1, " \n"[j==n]);
				else if(i == j + 1)	printf("%d%c", 1, " \n"[j==n]);
				else if(i == 1 && j == n)	printf("%d%c", 1, " \n"[j==n]);
				else	printf("%d%c", 0, " \n"[j==n]);
			}
		}
	}
	return 0;
}

---

C. Binary Search

根据题目给的代码走，当当前区间中点为 $mid$ 时，为了满足最后能找到 $pos$ 处，要求：

• 如果 $mid \leqslant pos$，则需要执行 l=mid+1，因此要求 $mid$ 处的值 $\leqslant x$；
• 否则 $mid>pos$，则需要执行 r=mid，因此要求 $mid$ 处的值 $>x$。

设要求小于 $x$ 的数有 $a$ 个，要求大于 $x$ 的数有 $b$ 个，则答案为 $A_{x-1}^a\times A_{n-x}^b\times (n-a-b-1)!$.

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9+7;

LL fpow(LL bs, LL idx){
	bs %= MOD;
	LL res = 1;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

LL fact[1005] = {1}, invfact[1005] = {1};

int main(){
	for(int i = 1; i <= 1000; i++){
		fact[i] = fact[i-1] * i % MOD;
		invfact[i] = fpow(fact[i], MOD-2);
	}
	int x, n, pos;
	cin >> n >> x >> pos;
	int l = 0, r = n, a = 0, b = 0;
	while(l < r){
		int mid = (l + r) >> 1;
		if(pos < mid)	r = mid, b++;
		else	 l = mid+1, a += (pos > mid);
	}
	if(x-1-a < 0 || n-x-b < 0)	cout << 0 << endl;
	else	cout << fact[x-1] * invfact[x-1-a] % MOD * fact[n-x] % MOD * invfact[n-x-b] % MOD * fact[n-a-b-1] % MOD << endl;
	return 0;
}

---

D. Bandit in a City

二分答案，$mid$ 表示叶节点最多容纳的人数，check 是否能够满足该条件。

设 $sum[x]$ 表示以 $x$ 为根的子树中 $a_i$ 的和，$cnt[x]$ 表示以 $x$ 为根的子树的叶节点数量，则 $cnt[x]\times mid$ 表示当前二分的答案下子树 $x$ 能容纳的最多人数。结论是当且仅当

$$sum[x]\leqslant cnt[x]\times mid,\quad\forall x\in[1,n]$$

时满足 check 条件，可以自下向上数学归纳证明。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200005;

int n;
vector<int> edge[N];
LL a[N];

LL cnt[N], sum[N];
void dfs(int x){
	cnt[x] = (edge[x].size() == 0), sum[x] = a[x];
	for(auto &to : edge[x]){
		dfs(to);
		cnt[x] += cnt[to], sum[x] += sum[to];
	}
}
inline bool check(LL mid){
	memset(cnt, 0, sizeof cnt);
	memset(sum, 0, sizeof sum);
	dfs(1);
	for(int i = 1; i <= n; i++)
		if(sum[i] > (unsigned long long)mid * cnt[i])
			return false;
	return true;
}

int main(){
	scanf("%d", &n);
	for(int i = 2; i <= n; i++){
		int f; scanf("%d", &f);
		edge[f].emplace_back(i);
	}
	LL l = 0, r = 0;
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]), r += a[i];
	while(l < r){
		LL mid = (l + r) >> 1;
		if(check(mid))	r = mid;
		else	 l = mid + 1;
	}
	printf("%lld\n", l);
	return 0;
}

---

E. Complicated Computations

$x$ 不是答案 $\iff$ 存在一个不包含 $x$ 的区间包含了 $1\sim x-1$。

于是我们只需要考虑 $x$ 两次出现之间包夹的区间，如果这里面的数字种数为 $x-1$，那么 $x$ 不是答案。

所有这样的区间是 $O(n)$ 的，所以只需要 $O(\lg n)$ 地查询即可。

我们开一颗线段树，以数值为值域，在从左往右扫描的过程中存储该数值最近一次的编号（即一个存储最近一次编号的桶）。当加入数字 $a[i]$ 时，查询 $1\sim a[i]-1$ 这些桶内的最小编号 $l$，如果 $l$ 大于 $a[i]$ 上一次出现的位置，则说明从 $a[i]$ 上一次出现到当前出现这一段区间内，$1\sim a[i]-1$ 全部出现了，于是 $a[i]$ 不是答案。

#include<bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, a[N], lst[N];
bool notAns[N];

struct segTree{
	int l, r, id;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
	tr[id].id = min(tr[lid].id, tr[rid].id);
}
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].id = 0;
	if(l == r)	return;
	build(lid, l, mid), build(rid, mid+1, r);
	pushup(id);
}
void modify(int id, int pos, int val){
	if(tr[id].l == tr[id].r){ tr[id].id = val; return; }
	if(pos <= mid)	modify(lid, pos, val);
	else 	modify(rid, pos, val);
	pushup(id);
}
int query(int id, int l, int r){
	if(l > r)	return 0;
	if(tr[id].l == l && tr[id].r == r)	return tr[id].id;
	if(r <= mid)	return query(lid, l, r);
	else if(l > mid)	return query(rid, l, r);
	else	return min(query(lid, l, mid), query(rid, mid+1, r));
}

int main(){
	scanf("%d", &n);
	build(1, 1, n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		if(query(1, 1, a[i] - 1) > lst[a[i]])	notAns[a[i]] = true;
		if(a[i] == 1 && i-1 > lst[a[i]])	notAns[a[i]] = true;
		lst[a[i]] = i;
		modify(1, a[i], i);
	}
	for(int i = 1; i <= n+1; i++){
		notAns[i] |= (query(1, 1, i-1) > lst[i]);
		if(i == 1)	notAns[i] |= (n > lst[a[i]]);
		if(!notAns[i]){
			printf("%d\n", i);
			return 0;
		}
	}
	printf("%d\n", n+2);
	return 0;
}

---