Educational Codeforces Round 86

比赛链接 / 官方题解链接

A. Road To Zero

Solution

先把两个数减到相同，再一起减到 $0$.

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T;
LL x, y, a, b;

int main(){
	for(read(T); T; T--){
		read(x, y, a, b);
		if(b > 2 * a)	b = 2 * a;
		if(x > y)	swap(x, y);
		LL ans = (y - x) * a;
		ans += x * b;
		printf("%lld\n", ans);
	}
	return 0;
}

---

B. Binary Period

Solution

如果 $t$ 中字符全部相同那么输出 $t$ 即可；否则以 $01$ 为循环节输出。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T;
char t[205], s[205];

int main(){
	for(read(T); T; T--){
		scanf("%s", t+1);
		int len = strlen(t+1);
		int sid = 0;
		bool same = true;
		for(int i = 1; i <= len; i++)
			if(t[i] != t[1]){
				same = false;
				break;
			}
		if(same){
			printf("%s\n", t+1);
			continue;
		}
		int now = 0;
		for(int i = 1; i <= len; i++){
			if(t[i] != now + '0'){
				s[++sid] = now + '0';
				now ^= 1;
				i--;
			}
			else{
				s[++sid] = now + '0';
				now ^= 1;
			}
		}
		if(s[sid] == '0')	s[++sid] = '1';
		s[++sid] = '\0';
		printf("%s\n", s+1);
	}
	return 0;
}

---

C. Yet Another Counting Problem

Solution

$[1,ab]$ 是一个循环节，可以先预处理出 $f[1\sim ab]$ 存储答案的前缀和，则 $1\sim U$ 的答案就是 $f[ab]\cdot\left\lfloor\frac{U}{ab}\right\rfloor+f[U\mod(ab)]$.

$[L,R]$ 的答案即是 $[1,R]$ 的答案减去 $[1,L-1]$ 的答案。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a % b); }

int T, q;
LL a, b, L, R, f[40005];

inline LL calc(LL U){
	return f[a*b] * (U / (a*b)) + f[U%(a*b)];
}

int main(){
	for(read(T); T; T--){
		read(a, b, q);
		memset(f, 0, sizeof f);
		for(int i = 1; i <= 40000; i++){
			if((i % a) % b != (i % b) % a)
				f[i]++;
			f[i] += f[i-1];
		}
		while(q--){
			read(L, R);
			printf("%lld ", calc(R) - calc(L-1));
		}
		puts("");
	}
	return 0;
}

---

D. Multiple Testcases

Solution

从大到小贪心放置 $m_i$，每次寻找第一个可放置 $m_i$ 的 testcase，可放置当且仅当这个 testcase 里现有元素个数严格小于 $m_i$ 允许个数。所以我们需要单点修改、查找小于某数的第一个位置，用值域线段树可解决。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, k, m[N], c[N], mx;

vector<int> a[N];

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

int main(){
	read(n, k);
	for(int i = 1; i <= n; i++)	read(m[i]);
	sort(m+1, m+n+1);
	reverse(m+1, m+n+1);
	for(int i = 1; i <= k; i++)	read(c[i]);
	build(1, 1, n);
	for(int i = 1; i <= n; i++){
		int limit = c[min(k, m[i])];
		int pos = query(1, 1, n, limit);
		a[pos].pb(m[i]);
		add(1, 1, n, pos);
		mx = max(mx, pos);
	}
	printf("%d\n", mx);
	for(int i = 1; i <= mx; i++){
		printf("%d ", (int)a[i].size());
		for(auto k: a[i])	printf("%d ", k);
		puts("");
	}
	return 0;
}

---

E. Placing Rooks

Solution

要使每一个格子都被攻击到，有两种情况——每一行都有且仅有一个车，或者每一列都有且仅有一个车。

只考虑每一行都有且仅有一个车的情形：如果我们想要有 $k$ 个车互相攻击，那么我们需要把 $n$ 个车放在 $n-k$ 列中——因为每把一个车放到非空的列上时，能互相攻击的车数加一。所以问题变成了把 $n$ 个车放到 $c$ 列中且每列不空的方案数。这可以容斥：总数是 $c^n$，即每个车都有 $c$ 中选择，减去有空列的方案数——至少有一个空列的方案数为 $C_c^1(c-1)^n$，至少有两个空列的方案数为 $C_c^2(c-2)^n$，……，因此答案是 $\sum\limits_{i=0}^c(-1)^iC_c^i(c-i)^n$. 乘上 $C_n^c$，即选择哪些列放车，就是每一行有且只有一个车的情形的答案。

如果 $k=0$，那么每一行有且仅有一个车和每一列有且仅有一个车情形重合；否则，答案再乘上 $2$.

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;
const LL MOD = 998244353;

LL n, k, C[N] = {1}, inv[N];

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

int main(){
	read(n, k);
	k = n - k;
	for(int i = 1; i <= k; i++){
		if(i == 1)	inv[i] = 1;
		else{
			inv[i] = -(MOD / i) * inv[MOD % i] % MOD;
			((inv[i] %= MOD) += MOD) %= MOD;
		}
		C[i] = C[i-1] * (k - i + 1) % MOD * inv[i] % MOD;
	}
	LL res = 0;
	for(int i = 0; i <= k; i++){
		(res += ((i & 1) ? -1 : 1) * C[i] % MOD * fpow(k - i, n) % MOD) %= MOD;
		(res += MOD) %= MOD;
	}
	LL CC = 1;
	for(int i = 1; i <= k; i++)
		(CC *= (n - i + 1) * inv[i] % MOD) %= MOD;
	printf("%lld\n", (1 + (k != n)) * CC * res % MOD);
	return 0;
}