题目链接：传送门
A. Elections （思维+暴力）
思路：
从最小的k开始枚举就好了- -。
#include <bits/stdc++.h>using namespace std;
const int MAX_N = + ;int a[MAX_N];int main()
{
int N;
cin >> N;
int m = -, sum = ;
for (int i = ; i <= N; i++) {
scanf("%d", a+i);
m = max(m, a[i]);
sum += a[i];
}
int ans = m;
int Awruk = N*m-sum;
while (Awruk <= sum) {
Awruk += N;
ans++;
}
cout << ans << endl;
return ;
}
B. Lost Array （暴力枚举）
思路：
把差分预处理出来，枚举长度，可以跑到最后的就加入答案。
#include <bits/stdc++.h>using namespace std;
const int MAX_N = 1e3 + ;int a[MAX_N];
int b[MAX_N];
int ans[MAX_N];int main()
{
int N;
cin >> N;
a[] = ;
for (int i = ; i <= N; i++) {
scanf("%d", a+i);
b[i] = a[i] - a[i-];
}
int cnt = ;
for (int i = ; i <= N; i++) {
int j;
for (j = ; j <= N; j++) {
if (b[j] != b[(j-)%i+])
break;
}
if (j == N+)
ans[cnt++] = i;
}
cout << cnt << endl << ans[];
for (int i = ; i < cnt; i++)
cout << ' ' << ans[i];
cout << endl;
return ;
}
C. Smallest Word （思维）
思路：
遇到连续的a就找到最后一个，翻转。
遇到连续的b也找到最后一个，如果下一个是a，翻转。
#include <bits/stdc++.h>using namespace std;
const int MAX_N = 1e3 + ;bool ans[MAX_N];int main()
{
string s;
memset(ans, false, sizeof ans);
cin >> s;
int len = s.size();
int i = ;
while (i < len) {
while (i < len && s[i] == 'a')
i++;
ans[i-] = true;
while (i < len && s[i] == 'b')
i++;
if (i < len && s[i] == 'a')
ans[i-] = true;
}
cout << ans[];
for (int i = ; i < len; i++)
cout << ' ' << ans[i];
cout << endl;
return ;
}
D. Mysterious Crime （尺取+暴力）
思路：
从第一行开始，往下面几行找最长的匹配。每行从上一行的最左端的数开始往右匹配，匹配到不同的就break，进入下一行。
预处理一个pos[i][j]，表示第i行的值为j的数在哪个位置。
找完最后一行后得到最长的匹配的长度为len，计算len对答案产生的贡献。
注意M为1的时候不能匹配要特判一下，答案就是N*（N+1）/2。
#include <bits/stdc++.h>using namespace std;
const int MAX_N = 1e5 + ;
const int MAX_M = + ;int N, M;
int a[MAX_M][MAX_N];
int pos[MAX_M][MAX_N];
bool vis[MAX_N];int main()
{
cin >> N >> M;
memset(vis, false, sizeof vis);
for (int i = ; i <= M; i++)
for (int j = ; j <= N; j++) {
scanf("%d", &a[i][j]);
pos[i][a[i][j]] = j;
}
long long ans = ;
for (int i = ; i <= N; i++) if (!vis[a[][i]]){
int l = i, r = N;
long long len = ;
for (int j = ; j <= M; j++) {
int nxtl, nxtr;
nxtl = nxtr = pos[j][a[j-][l]];
while (l <= r && nxtr <= N && a[j][nxtr] == a[j-][l]) {
l++;
nxtr++;
}
l = nxtl, r = nxtr-;
if (j == M) {
len = r-l+;
for (int k = l; k <= r; k++)
vis[a[M][k]] = true;
}
}
ans += (len+)*len/;
}
if (M == )
ans = (long long)(N+)*N/;
cout << ans << endl;
return ;
}
E. Train Hard, Win Easy（思维+排序）
思路：
两个人（u，v）组队时他们的得分是min（xu+yv，xv+yu），考虑到：
xu+yv ＜ xv+yu
=>yv-xv ＜ yu-xu
令di = yi-xi，则组队时d小的一方出y，d大的一方出x。
根据d排序后，对于（1 ≤ i ＜ j ≤ N）有di ＜ dj，所以第i个人和第j个人组队的得分为yi+xj。
预处理x和y的前缀和，对于第i个人，他与在他之前的人组队的得分为：
$\sum_{j=1}^{i-1}y_{j}$ + xi * （i-1）;
与在他之后的人组队的得分为：
$\sum_{j=i+1}^{N}x_{j}$ + yi * （N-i）;
这样可以O(1)算出每个人的得分，然后再减去不能和自己比赛的人的贡献就好了。
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int MAX_N = 3e5 + ;struct Node{
int ind;
ll x, y;
ll d;
Node(int _i = , ll _x = , ll _y = ) : ind(_i), x(_x), y(_y) {d = y-x;}
bool operator < (const Node& a) const {
return d < a.d;
}
}nodes[MAX_N];ll sumx[MAX_N], sumy[MAX_N];
ll ans[MAX_N];int main()
{
int N, M;
cin >> N >> M;
memset(ans, , sizeof ans);
for (int i = ; i <= N; i++) {
ll x, y;
scanf("%I64d%I64d", &x, &y);
nodes[i] = Node(i, x, y);
}
for (int i = ; i <= M; i++) {
int u, v;
scanf("%d%d", &u, &v);
ll tmp = ;
if (nodes[u] < nodes[v])
tmp = nodes[u].y + nodes[v].x;
else
tmp = nodes[v].y + nodes[u].x;
ans[u] -= tmp;
ans[v] -= tmp;
}
sort(nodes+, nodes++N);
sumx[] = sumy[] = ;
for (int i = ; i <= N; i++) {
sumx[i] = sumx[i-] + nodes[i].x;
sumy[i] = sumy[i-] + nodes[i].y;
}
for (int i = ; i <= N; i++) {
Node cur = nodes[i];
ans[cur.ind] += sumy[i-] + cur.x*(i-);
ans[cur.ind] += sumx[N] - sumx[i] + cur.y*(N-i);
}
bool firstprint = true;
for (int i = ; i <= N; i++) {
if (firstprint)
firstprint = false;
else
printf(" ");
printf("%I64d", ans[i]);
}
puts("");
return ;
}
F. Make It One（组合数学+数论+dp）
思路：
说实话这题比较玄学。
2 * 3 * 5 * 7 * 11 * 13 * 17 ≈ 5e5，所以3e5范围内一个数最多有6个质因数。所以答案是不会超过6的，考虑从1开始枚举答案。
状态：
f[i][j]表示选择的数字数量为i时，最大公约数为j的方案数，若f[i][1] ＞ 0，就说明符合题意，直接输出。
已知所有的ai中j的倍数有cnt[j]个，则由容斥原理知：
状态转移方程：
f[i][j] = $C_{cnt[j]}^{i}-\sum_{k=2}^{\infty}f[i][k*j]$
组合数预处理一个逆元可以O(1)求出，总时间复杂度为O(loga * (N + a))
#include <bits/stdc++.h>using namespace std;
const int MAX_N = 3e5 + ;
const int MOD = 1e9 + ;int fpow(int a, int p) {
int ans = ;
while (p) {
if (p&) ans = (1LL * ans * a) % MOD;
p >>= ;
a = (1LL * a * a) % MOD;
}
return ans;
}int N;
int a[MAX_N];
int f[][MAX_N], cnt[MAX_N];
int fac[MAX_N], inv[MAX_N];int newton(int m, int n) {
if (n < || m < n) return ;
return ((1LL * fac[m] * inv[n])%MOD * inv[m-n]) % MOD;
}void init() {
fac[] = ;
for (int i = ; i <= MAX_N; i++)
fac[i] = (1LL * fac[i-] * i) % MOD; inv[MAX_N-] = fpow(fac[MAX_N-], MOD-);
for (int i = MAX_N-; i >= ; i--)
inv[i-] = (1LL * inv[i] * i) % MOD;
}void sub(int& a, int b) {
a -= b;
if (a < )
a += MOD;
}int main()
{
init();
scanf("%d", &N);
memset(cnt, , sizeof cnt);
for (int i = ; i <= N; i++) {
scanf("%d", a+i);
cnt[a[i]]++;
}
for (int i = ; i < MAX_N; i++) {
for (int j = *i; j < MAX_N; j += i) {
cnt[i] += cnt[j];
}
}
for (int i = ; i < ; i++) {
for (int j = MAX_N-; j >= ; j--) {
f[i][j] = newton(cnt[j], i);
for (int k = j+j; k < MAX_N; k += j)
sub(f[i][j], f[i][k]);
}
if (f[i][] > ) {
printf("%d\n", i);
return ;
}
}
puts("-1");
return ;
}
