Codeforces Round #166 (Div. 2)

A：Beautiful Year

给你一个年份，要你找这之后的第一个没有相同数字的年份。

思路

直接暴力找暴力判断。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int n;
int in[10];

bool ck(int n) {
	memset(in, 0, sizeof(in));
	in[n % 10]++; in[n / 10 % 10]++; in[n / 100 % 10]++; in[n / 1000]++;
	if (in[n % 10] > 1 || in[n / 10 % 10] > 1 || in[n / 100 % 10] > 1 || in[n / 1000] > 1) return 1;
	return 0;
}

int main() {
	scanf("%d", &n);
	
	n++;
	while (ck(n)) n++;
	printf("%d", n);
	
	return 0;
}

B：Prime Matrix

给你一个矩阵，然后你每次操作可以给一个位置加一。
然后问你至少要操作多少次，才会使得这个矩阵中有一个列或者一行全部都是素数。

思路

先预处理出每个数加到质数最少要加多少次。
然后暴力枚举让哪个行或者列都成为质数，然后算一下，选最小的即可。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int n, m, a[501][501], b[501][501];
int prime[200001], st, ans;
bool np[200001];

void Init() {
	for (int i = 2; i <= 200000; i++) {
		if (!np[i]) prime[++prime[0]] = i;
		for (int j = 1; j <= prime[0] && i * prime[j] <= 200000; j++) {
			np[i * prime[j]] = 1; if (i % prime[j] == 0) break;
		}
	}
}

int work(int x) {
	int re = 0;
	for (int i = 1; i <= m; i++) {
		re += b[x][i] - a[x][i];
	}
	return re;
}

int wok(int x) {
	int re = 0;
	for (int i = 1; i <= n; i++) {
		re += b[i][x] - a[i][x];
	}
	return re;
}

int main() {
	Init();
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			b[i][j] = prime[lower_bound(prime + 1, prime + prime[0] + 1, a[i][j]) - prime];
		}
	}
	
	ans = 2e9;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, work(i));
	}
	for (int i = 1; i <= m; i++) ans = min(ans, wok(i));
	printf("%d", ans);
	
	return 0;
}

C：Secret

给你 $k$ 个桶，然后有 $1\sim n$ 这些数要放进去。
然后要你保证每个同里面的数排序之后得到的数组都不是一个等差序列。
要你判断无法构造或给出一种构造方案。

思路

让它不是等差序列其实很简单，就你弄一个挨在一起的，再弄一个独立分开的。

然后你会发现如果不是等差序列一定至少要长度为 $3$，所以 $\lfloor \frac{n}{k}\rfloor$ 一定要大于等于 $3$。

那就不难想到构造方案：先排一个 $1\sim k$，然后剩下的可以放的就 $1,1,...,1,2,2,...,2,.......$ 这样放即可。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int n, k, a[1000001];

int main() {
	scanf("%d %d", &n, &k);
	
	if (n / k < 3) {
		printf("-1"); return 0;
	}
	
	for (int i = 1; i <= k; i++) {
		printf("%d ", i);
	}
	int now = 0;
	for (int i = k + 1; i <= n; i++) {
		a[i] = now + 1; now = (now + 1) % k;
	}
	sort(a + k + 1, a + n + 1);
	for (int i = k + 1; i <= n; i++) printf("%d ", a[i]);
	
	return 0;
}

D：Good Substrings

给你一个字符串，然后问你它有多少种不一样的子串满足一些给定的字母的出现次数不超过 $k$。

思路

看到字符串不一样直接上 SAM（其实 Trie 树和 hash 都可以）。
就直接 DP 子串个数的时候加个出现次数的限制条件，超过了就不要记录不要递归就好了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

char s[1501];
int a[1501], zb[27];
int k, n;
ll ans;

struct node {
	int len, fa;
	ll f;
	int son[31];
	node() {
		memset(son, 0, sizeof(son));
		len = fa = 0;
		f = -1ll;
	}
}d[200001];
int tot, lst;

void SAM_build(int now) {
	int p = lst;
	int np = ++tot;
	d[np].len = d[p].len + 1;
	lst = np;
	
	for (; p && !d[p].son[now]; p = d[p].fa)
		d[p].son[now] = np;
	
	if (!p) d[np].fa = 1;
		else {
			int q = d[p].son[now];
			if (d[q].len == d[p].len + 1) d[np].fa = q;
				else {
					int nq = ++tot;
					d[nq] = d[q];
					d[nq].len = d[p].len + 1;
					d[q].fa = nq;
					d[np].fa = nq;
					for (; p && d[p].son[now] == q; p = d[p].fa) {
						d[p].son[now] = nq;
					}
				}
		}
}

void dfs(int now, int num) {
	d[now].f = 0;
	if (num > k) return ;
	for (int i = 0; i < 26; i++)
		if (d[now].son[i]) {
			dfs(d[now].son[i], num + (!zb[i]));
			d[now].f += d[d[now].son[i]].f;
		}
	d[now].f++;
}

int main() {
	scanf("%s", s + 1); n = strlen(s + 1);
	for (int i = 0; i < 26; i++) scanf("%1d", &zb[i]);
	for (int i = 1; i <= n; i++) a[i] = zb[s[i] - 'a'];
	scanf("%d", &k);
	
	tot = lst = 1;
	for (int i = 1; i <= n; i++)
		SAM_build(s[i] - 'a');
	
	dfs(1, 0);
	
	printf("%d", d[1].f - 1);
	
	return 0;
}

E：Three Horses

有一些卡片的制造方法：
通过 $(a,b)$ 得到 $(a+1,b+1)$
通过 $(a,b)$ 得到 $(a/2,b/2)$，但 $a,b$ 都要是偶数
通过 $(a,b),(b,c)$ 得到 $(a,c)$

然后你被要求制造一些形如 $(1,a_i)$ 的卡片。
然后你初始可以选一个卡片 $(a,b)$ 拿，但是 $1⩽a<b⩽m$，然后问你有多少种拿的方案。

思路

你考虑去想它的性质，你会发现它基本上就是跟 $b-a$ 的值有关。
你考虑去搞。
然后会发现最本质的地方是 $b-a$ 是奇数的部分。
你会发现只要满足这个，其中一个能搞别的都能搞，因为能通过加一再除不断的搞变成同一个。
然后你就考虑有哪些 $b-a$ 是可以的，然后你发现既然是 $b-a$，那我们首先要求所有 $x_i-1$ 的 $\gcd$。
那这个我们还要是奇数，所以我们把偶数的部分全部除去。

然后奇数的部分它的每个因子都可以（因为都是奇数），所以我们要枚举它的因子，这些都能作为 $b-a$。
但是这还没完，你会发现如果 $b-a=d$，你可以加若干次，然后用第三个操作连接起来，就变成了 $2d$，那接着就会有 $4d,8d,16d,...$
那我们就枚举 $l$，然后就会有 $2^{l}d$，然后注意枚举到 $>m$ 就不用了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

int n, m, a[100001], gcd;
ll ans;

int GCD(int x, int y) {
	if (!y) return x;
	return GCD(y, x % y);
}

void work(int x) {
	ll now = x;
	while (now <= m) {
		ans += m - now;
		now = now * 2;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	n = unique(a + 1, a + n + 1) - a - 1;
	
	ll gcd = a[1] - 1;
	for (int i = 2; i <= n; i++) gcd = GCD(gcd, a[i] - 1);
	while (gcd % 2 == 0) gcd /= 2;
	
	for (ll i = 1; i * i <= gcd; i++) {
		if (gcd % i == 0) {
			work(i); if (i * i != gcd) work(gcd / i);
		}
	}
	
	printf("%lld", ans);
	
	return 0;
}