2021-03-07发表2021-03-07更新ICPC/CCPC / Contests / Codeforces10 分钟读完 (大约1450个字)

Codeforces Round #705 (Div.2)

A. Anti-knapsack

选出 $\geqslant \lceil k/2\rceil$ 且 $\neq k$ 的所有数即可。

证明：$>k$ 的所有数一定是都可以选的，所以我们关注点主要放在 $1\sim k-1$ 这些数上。首先，容易知道选出 $\geqslant \lceil k/2\rceil$ 的数一定是满足题意的；其次，两两配对，容易知道最多从这 $k-1$ 个数中选出 $\lfloor k/2\rfloor$ 个数；因而我们的方案是最优解。证毕。

#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 main(){
	int T; for(read(T); T; T--){
		int n, k; read(n, k);
		vector<int> ans;
		for(int i = (k + 1) / 2; i <= n; i++)
			if(i != k)	ans.pb(i);
		printf("%d\n", (int)ans.size());
		for(auto &k : ans)	printf("%d ", k);
		puts("");
	}
	return 0;
}

B. Planet Lapituletti

遍历所有的时间，判断是否合法即可。

#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 h, m;
char s[10], t[10];
int mir[15] = {0, 1, 5, -1, -1, 2, -1, -1, 8, -1};

bool ref(){
	if(~mir[s[0]-'0'])	t[4] = mir[s[0]-'0'] + '0';
	else	return false;
	if(~mir[s[1]-'0'])	t[3] = mir[s[1]-'0'] + '0';
	else	return false;
	if(~mir[s[3]-'0'])	t[1] = mir[s[3]-'0'] + '0';
	else	return false;
	if(~mir[s[4]-'0'])	t[0] = mir[s[4]-'0'] + '0';
	else	return false;
	int th = (t[0]-'0')*10 + (t[1]-'0');
	int tm = (t[3]-'0')*10 + (t[4]-'0');
	if(th < h && tm < m)	return true;
	else	return false;
}

int main(){
	int T; for(read(T); T; T--){
		read(h, m);
		scanf("%s", s);
		int sh = (s[0]-'0')*10 + (s[1]-'0');
		int sm = (s[3]-'0')*10 + (s[4]-'0');
		while(!ref()){
			sm++;
			if(sm >= m)	sh++, sm = 0;
			if(sh >= h)	sh = 0;
			s[0] = sh / 10 + '0';
			s[1] = sh % 10 + '0';
			s[3] = sm / 10 + '0';
			s[4] = sm % 10 + '0';
		}
		printf("%s\n", s);
	}
	return 0;
}

C. K-beautiful Strings

如果 $k\nmid n$，那答案不存在；否则答案一定存在，因为 $zz\ldots z$ 是满足题意的一个 beautiful string。

如果 $s$ 本身是 beautiful 的，那么答案就是 $s$；否则，答案一定是从某一位开始与 $s$ 不一样的。枚举这个位置 $\text{pos}$ 以及该位置上的字母（从大于 $s_\text{pos}$ 的字符开始枚举），计算之前出现过的字母还需要出现多少次才能被 $k$ 整除，由于 $\text{pos}$ 处已经保证答案的字典序比 $s$ 大了，所以我们只需要把还差的字母按字典序依次填在 $\text{pos}$ 之后，如果还有剩余的位置，那就补字符 a。

#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 = 100005;

int n, k;
char s[N];
vector<int> cnt[N];

inline int calc(int now){
	int o = now / k;
	while(o * k < now)	o++;
	return o * k - now;
}

int main(){
	int T; for(read(T); T; T--){
		read(n, k);
		scanf("%s", s+1);
		if(n % k){ puts("-1"); continue; }
		cnt[0].clear(); cnt[0].resize(26);
		for(int i = 1; i <= n; i++){
			cnt[i].clear();
			cnt[i].resize(26);
			cnt[i][s[i]-'a']++;
		}
		for(int i = 1; i <= n; i++)
			for(int c = 0; c < 26; c++)
				cnt[i][c] += cnt[i-1][c];
		
		bool ok = true;
		for(int i = 0; i < 26; i++)
			if(cnt[n][i] % k){ ok = false; break; }
		if(ok){ printf("%s\n", s+1); continue; }

		vector<int> need(30, 0);
		for(int i = n; i >= 1; i--){
			for(int j = s[i]-'a'+1; j < 26; j++){
				int sumneed = 0;
				for(int c = 0; c < 26; c++){
					need[c] = calc(cnt[i-1][c] + (c == j));
					sumneed += need[c];
				}
				if(sumneed <= n - i){
					int id = 0;
					string ans;
					for(int c = 25; c >= 0; c--)
						while(need[c]--)	ans += c + 'a';
					while(ans.size() < n - i)	ans += 'a';
					for(int j = 0; j < n - i; j++)	s[n-j] = ans[j];
					s[i] = j + 'a';
					ok = true;
					break;
				}
			}
			if(ok)	break;
		}
		printf("%s\n", s+1);
	}
	return 0;
}

D. GCD of an Array

对 $[1,200000]$ 中的每一个质数维护一个数据结构，能够完成对第 $i$ 个数加 $x$ 、求 $1\sim n$ 的最小值的操作。由于每个数最多有 $6$ 个不同的质因子，每次询问做单点加法的位置很有限，或者说，整个 $n\times P$ 的矩阵是很稀疏的，我们可以用一些 $\text{STL}$ 完成。比如我是对每一个质数开一个 unordered_map 和 multiset 完成的。

注意一个 trick：求 $\gcd$ 时需要作除法，为了避免每次做除法都求逆元耗时过大，可以先把要除的数乘起来，最后求一次逆元就行了。

#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 = 1e9 + 7;

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

bool notP[N];
LL pList[N], pID;
void Euler(int n){
	notP[0] = notP[1] = 1;
	for(int i = 1; i <= n; i++){
		if(!notP[i])	pList[++pID] = i;
		for(int j = 1; j <= pID; j++){
			if(1ll * i * pList[j] > n)	break;
			notP[i * pList[j]] = 1;
			if(i % pList[j] == 0)	break;
		}
	}
}

int n, q;
LL GCD = 1, divGCD = 1;
multiset<LL> st[N];
unordered_map<LL, LL> ids[N];

inline void add(LL p, LL i, LL k){
	if(ids[p].find(i) == ids[p].end())	ids[p][i] = 0;
	else{
		if(k == 1 && ids[p].size() == n)	(divGCD *= fpow(p, *st[p].begin()) % MOD) %= MOD;
		st[p].erase(st[p].find(ids[p][i]));
	}
	ids[p][i]++; st[p].insert(ids[p][i]);
	if(k == 1 && ids[p].size() == n)	(GCD *= fpow(p, *st[p].begin()) % MOD) %= MOD;
}

int main(){
	Euler(200000);
	read(n, q);
	for(int i = 1; i <= n; i++){
		LL t; read(t);
		for(int pid = 1; pList[pid] * pList[pid] <= t && pid <= pID; pid++){
			LL p = pList[pid];
			while(t % p == 0)	add(p, i, 0), t /= p;
		}
		if(t > 1)	add(t, i, 0);
	}
	for(int pid = 1; pid <= pID; pid++){
		LL p = pList[pid];
		if(ids[p].size() == n)	(GCD *= fpow(p, *st[p].begin()) % MOD) %= MOD;
	}
	while(q--){
		LL i, t; read(i, t);
		for(int pid = 1; pList[pid] * pList[pid] <= t && pid <= pID; pid++){
			LL p = pList[pid];
			while(t % p == 0)	add(p, i, 1), t /= p;
		}
		if(t > 1)	add(t, i, 1);
		(GCD *= fpow(divGCD, MOD-2) % MOD) %= MOD;
		divGCD = 1;
		printf("%lld\n", GCD);
	}
	return 0;
}

Codeforces Round #705 (Div.2)

http://xyfjason.github.io/blog-xcpc/2021/03/07/Codeforces-Round-705-Div-2/

作者

xyfJASON

发布于

2021-03-07

更新于

2021-03-07

许可协议

#Codeforces

Codeforces Round #705 (Div.2)

A. Anti-knapsack

B. Planet Lapituletti

C. K-beautiful Strings

D. GCD of an Array

作者

发布于

更新于

许可协议

评论

分类

最新文章

标签