夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

CF1400

2021-02-25 9 min read

CF1400A String Similarity

输出S的所有偶数位置字符

#include<bits/stdc++.h>
using namespace std;
int T, n;
char s1[10000000];
int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%d%s", &n, s1);
		for(int i = 0; i < 2 * n - 1; i += 2)printf("%c", s1[i]);
		puts("");
	}
	return 0;
}

CF1400B RPG Protagonist

枚举第一个人买什么

然后第二个人尽可能买小的

#include<bits/stdc++.h>
#define int long long
using namespace std;

int T, p, f, cnts, cntw, s, w;

signed main() {
	scanf("%lld", &T);
	while(T-- > 0) {
		scanf("%lld%lld", &p, &f);
		scanf("%lld%lld", &cnts, &cntw);
		scanf("%lld%lld", &s, &w);
		if(s > w)swap(cnts, cntw), swap(s, w);
		int ans = 0;
		for(int i = 0; i <= cnts; ++i) {
			if(i * s > p)break;
			int tp = min((p - i * s) / w, cntw);
			// printf("First : %d %d\n", i, i + tp);
			if((cnts - i) * s >= f) {
				// puts("/jk");
				ans = max(ans, tp + i + f / s);
				// printf("is %d\n", tp + i + f / s);
			} else {
				tp += min((f - (cnts - i) * s) / w, cntw - tp);
				// printf("%d %d?\n", min((f - (cnts - i) * s) / w, cntw - tp), tp + cnts);
				tp += cnts;
				ans = max(ans, tp);
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

CF1400C Binary String Reconstruction

从小到大扫过去

对于第一个位置看他前面的能不能放1,能放在前面,否则放在后面并判断能不能放

#include<bits/stdc++.h>
const int MAXN = 1e6 + 7;
int T, x, n;
char s[MAXN];
int a[MAXN];
inline int fpd(int i) {
	if((i - x > 0 && a[i - x] == 1) || (i + x <= n && a[i + x] == 1))return 0;
	return 1;
}
inline int pd(int i) {
	if((i + x <= n && s[i + x] != '1') || (i - x > 0 && s[i - x] != '1'))return 0;
	return 1;
}
int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%s", s + 1);
		scanf("%d", &x);
		n = strlen(s + 1);
		for(int i = 1; i <= n; ++i)a[i] = 0;
		bool flg = 1;
		for(int i = 1; i <= n; ++i) {
			if(s[i] == '1' && fpd(i)) {
				if(i - x > 0 && pd(i - x)) {
					a[i - x] = 1;
				} else if(i + x <= n && pd(i + x)) {
					a[i + x] = 1;
				} else {
					flg = 0;
					break;
				}
			}
		}
		if(!flg)puts("-1");
		else for(int i = 1; i <= n; ++i)printf("%d", a[i]);
		puts("");
	}
	return 0;
}

CF1400D Zigzags

第一遍预处理前i个位置有多少个相等数对

第二遍在线统计fi,aif_{i,a_i}表示前i个值为aia_i的求和是什么

CF1400E Clear the Multiset

fl,rf_{l,r}表示区间[l,r][l,r]全部清空的最小代价

第一种转移是把所有的数不断进行1操作剪剪剪到最小值为0,然后区间变成子区间

第二种转移是直接将整个区间使用2操作推平掉

两类转移取min即可

因为我们每次都会减少一个数,相对带来多出一个状态的代价,所以是线性的

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 7;
int a[MAXN], n;

inline int solve(int l, int r) {
	if(l > r)return 0;
	if(l == r) {
		if(a[l] == 0)return 0;
		return 1;
	}
	int ans = 0;
	int ans1 = 0;
	int tmp = 1e9;
	for(int i = l; i <= r; ++i) {
		if(a[i] < tmp)tmp = a[i];
		if(a[i] != 0)ans1++;
	}
	for(int i = l; i <= r; ++i)
		a[i] -= tmp;
	ans = tmp;
	tmp = l;
	for(int i = l; i <= r; ++i) {
		if(a[i] == 0) {
			ans += solve(tmp, i - 1);
			tmp = i + 1;
		} else if(i == r) {
			ans += solve(tmp, i);
		}
	}
	ans = min(ans, ans1);
	return ans;
}

signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);
	printf("%lld\n", solve(1, n));
	return 0;
}

CF1400F x-prime Substrings

李队之前讲过,咕掉

CF1400G Mercenaries

容斥

钦定至少满足其中x个敌对关系

我们只需要选出一些人使得这些人数量满足限制即可

不难发现我们可以很容易求出单点值,就是对于集合大小为x的方案数,假设nin_i为所有满足[li≤x,ri≥x][l_i\leq x,r_i \geq x],应该是

(nix)\binom{n_i}{x}

然后因为我们钦定了几对人,所以是

∑x(ni−cx−c)\sum_x\binom{n_i-c}{x-c}

这个式子好像没法O(1)求啊/ll

但是最后关键的一步,我们容斥要看值域大小!!

这个c的值域只有[0,2m][0,2m],而且只有m种取值

所以就直接做了

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int P = 998244353;
const int MAXN = 3e5 + 7;
const int MAXM = 45;
int n, m, x[MAXN], y[MAXN], cnt[MAXN], l[MAXN], r[MAXN];
int fac[MAXN], ifac[MAXN], vis[MAXN];
vector<int> v;
int pre[MAXM][MAXN];
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline ll add(ll x, ll y) {
	x += y;
	if(x >= P)x -= P;
	return x;
}

inline ll C(ll n, ll m) {
	if(n < m)return 0;
	if(m < 0)return 0;
	return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

inline void init() {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	fac[0] = 1;
	for(int i = 1; i <= n; ++i)fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n] = ksm(fac[n], P - 2);
	for(int i = n - 1; i >= 1; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	ifac[0] = 1;
	for(int j = 0; j <= 2 * m; j++) {
		for(int i = 1; i <= n; ++i) {
			pre[j][i] = add(pre[j][i - 1], C(cnt[i] - j, i - j));
		}
	}
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &l[i], &r[i]);
		cnt[l[i]]++;
		cnt[r[i] + 1]--;
	}
	for(int i = 1; i <= n; ++i)cnt[i] += cnt[i - 1];
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &x[i], &y[i]);
		v.pb(x[i]);
		v.pb(y[i]);
	}
	init();
	int mS = (1 << m) - 1;
	ll ans = 0;
	for(int S = 0; S <= mS; ++S) {
		int cnt = 0, lm = 1, rm = n, qc = 0;
		for(int i = 1; i <= m; ++i) {
			if(S >> (i - 1) & 1) {
				vis[x[i]] = vis[y[i]] = 1;
				qc++;
				lm = max(lm, l[x[i]]);
				rm = min(rm, r[x[i]]);
				lm = max(lm, l[y[i]]);
				rm = min(rm, r[y[i]]);
			}
		}
		for(auto q : v) {
			if(vis[q])cnt++;
			vis[q] = 0;
		}
		if(lm > rm)continue;
		// printf(" ?? %d %d %d %d %d\n", qc, cnt, lm, rm, pre[cnt][rm] - pre[cnt][lm - 1]);
		if(qc & 1)ans = add(ans, P - pre[cnt][rm] + pre[cnt][lm - 1]);
		else ans = add(ans, P + pre[cnt][rm] - pre[cnt][lm - 1]);
		ans %= P;
	}
	printf("%lld\n", ans);
	return 0;

}

直接WA了两发,第一发是求逆元哪里爆int了,然后第二处是我组合数那下标越界了....然后第二个else有减法我又没有判掉WA了第三发.....

Powered by Gridea RSS