2018 ACM-ICPC南京区域赛

A.Adrien and Austin

大意: n个石子编号1...n, 两个人轮流取, 每次取编号连续的1到k个石子, 不能取则输, 求谁赢.

先特判n=0. 当k>=2时先手必胜, 直接在中间取让两边对称即可. k=1时奇数先手必胜, 偶数后手必胜.

 

B.Tournament

大意: 给定直线上$n$个点$a$, 要求建$k$个体育馆$s$, 使得$sumlimits_{i=0}^{n-1}minlimits_{j=0}^{k-1}dis(a_i,s_j)$最小, 求最小值.

wqs二分不会

 

C.

 

D. Country Meow

大意:给定空间n个点, 求一个点到n个点距离最大值的最小, 输出最小值.

 

E. Eva and Euro coins

大意:给定两个01串$s$,$t$, 每次操作将$s$翻转长度为$k$的同色区间, 可以操作任意次, 求$s$和$t$是否可以相同.

核心观察是每出现连续$k$个相同的, 一定可以将它们移动到最后的位置.

 

复制代码#include <iostream> #include <cstdio> #define REP(i,a,n) for(int i=a;i<=n;++i) using namespace std; const int N = 1e6+10; int n, k; char s[N], t[N]; int a[N], c[N]; void get(char *s) { int now = 0; REP(i,1,n) { ++now, a[now] = s[i], c[now] = 1; if (now>1&&a[now]==a[now-1]) c[now-1]+=c[now], --now; c[now]%=k; if (!c[now]) --now; } int cnt = 0; REP(i,1,now) while (c[i]--) s[++cnt]=a[i]; while (cnt!=n) s[++cnt]=0; } int main() { scanf("%d%d%s%s", &n, &k, s+1, t+1); REP(i,1,n) s[i]-='0',t[i]-='0'; if (k==1) return puts("Yes"),0; get(s),get(t); REP(i,1,n) if (s[i]!=t[i]) return puts("No"),0; puts("Yes"); }

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 <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10;
int n, k;
char s[N], t[N];
int a[N], c[N];

void get(char *s) {
	int now = 0;
	REP(i,1,n) {
		++now, a[now] = s[i], c[now] = 1;
		if (now>1&&a[now]==a[now-1]) c[now-1]+=c[now], --now;
		c[now]%=k;
		if (!c[now]) --now;
	}
	int cnt = 0;
	REP(i,1,now) while (c[i]--) s[++cnt]=a[i];
	while (cnt!=n) s[++cnt]=0;
}

int main() {
	scanf("%d%d%s%s", &n, &k, s+1, t+1);
	REP(i,1,n) s[i]-='0',t[i]-='0';
	if (k==1) return puts("Yes"),0;
	get(s),get(t);
	REP(i,1,n) if (s[i]!=t[i]) return puts("No"),0;
	puts("Yes");
}

 

 

 

J. Prime Game

大意: 给定序列$a$, 定义$fac(l,r)$表示$[l,r]$区间包含的不同素数个数, 求$sumlimits_{1le ile jle n}fac(i,j)$.

枚举素因子, 补集转化.

 

复制代码#include <iostream> #include <cstdio> #include <queue> #define REP(i,a,n) for(int i=a;i<=n;++i) using namespace std; typedef long long ll; const int N = 1e6+10; int n, mi[N], a[N]; vector<int> g[N]; int main() { REP(i,1,N-1) mi[i]=i; REP(i,2,N-1) if (mi[i]==i) { for (int j=i;j<N;j+=i) mi[j]=min(mi[j],i); } scanf("%d", &n); REP(i,1,n) { scanf("%d", a+i); while (a[i]!=1) g[mi[a[i]]].push_back(i),a[i]/=mi[a[i]]; } ll ans = 0; REP(i,2,N-1) if (g[i].size()) { ll t = (ll)n*(n+1)/2; int now = 1; g[i].push_back(n+1); for (int j:g[i]) { t -= (ll)(j-now)*(j-now+1)/2; now = j+1; } ans += t; } printf("%lldn", ans); }

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
#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;

const int N = 1e6+10;
int n, mi[N], a[N];
vector<int> g[N];

int main() {
	REP(i,1,N-1) mi[i]=i;
	REP(i,2,N-1) if (mi[i]==i) { 
		for (int j=i;j<N;j+=i) mi[j]=min(mi[j],i);
	}
	scanf("%d", &n);
	REP(i,1,n) { 
		scanf("%d", a+i);
		while (a[i]!=1) g[mi[a[i]]].push_back(i),a[i]/=mi[a[i]];
	}
	ll ans = 0;
	REP(i,2,N-1) if (g[i].size()) {
		ll t = (ll)n*(n+1)/2;
		int now = 1;
		g[i].push_back(n+1);
		for (int j:g[i]) {
			t -= (ll)(j-now)*(j-now+1)/2;
			now = j+1;
		}
		ans += t;
	}
	printf("%lldn", ans);
}