http://codeforces.com/contest/1295

B. Infinite Prefixes

 

题意：给定一个01串s，构造出一个由s不断重复得到的无限长度的新串，问新串有几个前缀的0的个数减1的个数等于x。

如果s串的01差值等于0，则可以不断像前面插入s而不影响，所以此时如果s中有前缀01值等于x，就有无限多，否则永远不会有。

否则，可以发现s串的每个前缀最多作为答案出现1次，所以可以枚举前缀，判断前缀加k个s串是否能等于x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T, n, x;
char s[maxn];
int sum[maxn];
map<int, int>cnt;
int main() {
	cin >> T;
	while (T--) {
		scanf("%d%d", &n, &x);
		scanf(" %s", s + 1);
		cnt.clear();
		for (int i = 1; i <= n; i++)
			sum[i] = sum[i - 1] + (s[i] == '0') - (s[i] == '1'), cnt[sum[i]]++;
		if (sum[n] == 0) {
			if (cnt[x])puts("-1");
			else puts("0");
		}
		else {
			int ans = !x;
			for (int i = 1; i <= n; i++) {
				if ((x - sum[i]) % sum[n] == 0 && (x - sum[i]) / sum[n] >= 0)ans++;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

 

D. Same GCDs

 

题意：给定 a,m,1≤a<m≤1010a,m,1 \le a < m \le 10^{10}，问有多少个 x,0≤x<mx,0 \le x < m，满足 gcd⁡(a,m)=gcd⁡(a+x,m)\gcd(a, m) = \gcd(a + x, m)

设 gcd(a,m)=p,a=k1p,m=k2pgcd(a,m)=p,a=k_1p,m=k_2p，且 gcd(k1,k2)=1gcd(k_1,k_2)=1，同理 a+x=k3pa+x=k_3p，gcd(k2,k3)=1gcd(k_2,k_3)=1，而由题目范围得到 k1≤k3<k1+k2k_1\leq k_3< k_1+k_2，现在要求这个范围内与 k2k_2 互质的数的个数，最右边的不等式中 k2k_2 到 k1+k2k_1+k_2 的部分减去 k2k_2 后仍与 k2k_2 互质，原先不互质的减去 k2k_2 仍然不互质，所以可以把右边的不等式减去 k2k_2 放到左边，变成了找到 00 到 k2−1k2-1 中与 k2k_2 互质的数的个数，就是 k2k_2 的欧拉函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	return b == 0 ? a : gcd(b, a%b);
}
int T;
ll a, m;
ll euler_Phi(ll n) {
	ll ans = n;
	for (ll i = 2; i*i <= n; i++) {
		if (n%i == 0) {
			ans = ans / i * (i - 1);
			while (n%i == 0) n /= i;
		}
	}
	if (n > 1) ans = ans / n * (n - 1);
	return ans;
}
int main() {
	cin >> T;
	while (T--) {
		cin >> a >> m;
		ll k = m / gcd(a, m);
		cout << euler_Phi(k) << endl;
	}
	return 0;
}

 

E. Permutation Separation

 

题意：给定了一个1到n个排列，先把它分成非空的左右两边，再把某些数花费给定的消耗，换到另一边，使得最终最部分的所有数都小于右部分的所有数，这时可以有一边为空。求最小总花费。

线段树

肯定是要枚举初始的分割线，接下来就需要 O(log⁡n)O(\log n) 地找到最优地交换方式。

假设一个数作为最终的分割点，小于它的放左边，大于它的放右边，他自己原来在哪就还在那。则总花费为初始分割后左边集合中大于它的数的花费之和，加上右边集合中小于它的数的花费之和。记为 sumlb+sumrssum_{lb}+sum_{rs}.

左部分的大于它的数的花费之和等于左边所有数的花费和减去左边小于它的数的花费之和。即 sumlb=sum−sumlssum_{lb}=sum-sum_{ls}。所以 ans=min(sumrs−sumls)+sumans=min(sum_{rs}-sum_{ls})+sum.

而 sumsum 可以在枚举初始分割线的时候一起统计是个定值，所以只要得到每个数左右两边小于它的数的和的差值，找到最小的。

用权值线段树维护每个数小于它的数的花费之和，枚举初始分割点的同时把已经遍历到的，即左部分的数从线段树上减去 2wi2w_i，这样线段树上每个点存储的就是 sumrs−sumlssum_{rs}-sum_{ls}，再找到全局最小值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int p[maxn]; ll w[maxn], sum, ans = 1e18;
ll tr[maxn << 2], laz[maxn << 2];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void update(int l, int r, int rt, int ql, int qr, ll x) {
	if (ql <= l && qr >= r) {
		tr[rt] += x; laz[rt] += x;
		return;
	}
	if (ql <= mid)update(lson, ql, qr, x);
	if (qr > mid)update(rson, ql, qr, x);
	tr[rt] = min(tr[rt << 1], tr[rt << 1 | 1]) + laz[rt];
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)scanf("%d", &p[i]);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &w[i]);
		update(1, n, 1, p[i], n, w[i]);
	}
	ans = w[1];
	for (int i = 1; i < n; i++) {
		sum += w[i];
		update(1, n, 1, p[i], n, -2*w[i]);
		ans = min(ans, tr[1] + sum);
	}
	cout << ans << endl;
	return 0;
}