选取字符串 60pts
直接暴力60pts；
这题难点在于读懂题把。。。
考虑建出 $ KMP $ 树，然后在其中选出 $ k $ 个数，他们的 $ LCA $ 的深度的平方和就是这个答案，然后简单统计一下即可；
具体地，把 $ KMP $ 树建出来，然后求每 $ k $ 个点的 $ LCA $ 的深度的平方和即可，最后乘上方案数（总的减去每棵子树的）；
直接枚举 $ LCA $ 即可；
时间复杂度：$ \Theta(n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long mod = 998244353;
int k;
int n;
char s[1000005];
long long fac[1000005], fav[1000005];
inline long long ksm(long long a, long long b) {
long long ans = 1;
while(b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
inline long long C(long long a, long long b) {
if (a < b) return 0;
if (b < 0) return 0;
return fac[a] * fav[b] % mod * fav[a - b] % mod;
}
long long ans;
int pi[1000005];
struct sss{
int t, ne;
}e[2000005];
int h[2000005], cnt;
inline void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
inline void KMP() {
int j = 0;
add(0, 1);
for (int i = 2; i <= n; i++) {
while(j && s[i] != s[j + 1]) j = pi[j];
if (s[i] == s[j + 1]) j++;
pi[i] = j;
add(j, i);
}
}
int dep[1000005], siz[1000005];
long long sum[1000005];
void dfs(int x, int de) {
dep[x] = de;
siz[x] = 1;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
dfs(u, de + 1);
siz[x] += siz[u];
sum[x] = (sum[x] + C(siz[u], k)) % mod;
}
}
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> k;
cin >> (s + 1);
n = strlen(s + 1);
fac[0] = 1;
fav[0] = 1;
for (int i = 1; i <= n + 1; i++) {
fac[i] = fac[i - 1] * i % mod;
fav[i] = ksm(fac[i], mod - 2);
}
KMP();
dfs(0, 1);
for (int i = 0; i <= n; i++) {
if (siz[i] < k) continue;
long long res = (C(siz[i], k) - sum[i] + mod) % mod;
ans = (ans + res * dep[i] % mod * dep[i] % mod) % mod;
}
cout << ans;
return 0;
}
取石子 10pts
考虑如果是有奇数个，那么直接取 $ 1 $ 个先手必胜；
那么扩展一下，发现我们先求出异或和 $ sum $ ，然后如果 $ lowbit(sum) \leq k $ 那么我们就能选这一位，然后累加继续判断，否则直接 $ break $ 即可；
我们对于每个数都进行一边这个操作，时间复杂度 $ \Theta(n \log w) $，其中 $ w $ 为值域；
具体看代码；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, k;
int a[100005];
int main() {
freopen("nim.in", "r", stdin);
freopen("nim.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum ^= a[i];
}
if (!sum || (sum & (-sum)) > k) {
cout << 0;
return 0;
}
cout << 1 << '\n';
for (int i = 1; i <= n; i++) {
int p = 0;
int now = sum;
for (int j = 0; j <= 30; j++) {
if ((now >> j) & 1) {
now ^= (a[i] - p);
p += (1 << j);
if (p > a[i] || p > k) break;
now ^= (a[i] - p);
cout << i << ' ' << p << '\n';
}
}
}
return 0;
}
均衡区间 0pts
赛时想出正解然后全RE，ACCODERS上还被卡常了。。。
我们先维护出一个数前面和后面第一个小于它的和大于它的，这个可以单调栈维护；
主要讲一下这个单调栈，这里用线段树会T掉；
我们维护一个单调递增的栈，然后栈顶就是第一个小于它的，反之同理；
考虑为什么是对的，因为这样会将中间的小于它的全丢掉，这些数对后面的没有贡献，而且这样会尽可能的将最值往后移，所以是对的；
考虑后面的操作，我们发现，对于一个数 $ a_i $，设它后面的最大的第一个小于它的和大于它的的最大的位置为 $ R_i $，前面的为 $ L_i $，当它做左端点时，只有它满足题意的对应的右端点范围为 $ [R_i + 1, n] $，反之如果它做右端点，只有它满足题意的左端点的范围为 $ [1, L_i - 1] $，那么我们要找两者都满足条件的，直接将这些区间排序后上扫描线即可；
扫描线部分具体看代码；
时间复杂度：$ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define Flush FastIO::Fflush()
namespace FastIO {
const int SIZE = 1 << 16;
char buf[SIZE], obuf[SIZE], str[60];
int bi = SIZE, bn = SIZE, opt;
inline int read(register char *s) {
while(bn) {
for (; bi < bn && buf[bi] <= ' '; bi = -~bi);
if (bi < bn) break;
bn = fread(buf, 1, SIZE, stdin);
bi &= 0;
}
register int sn=0;
while(bn) {
for (; bi < bn && buf[bi] > ' '; bi = -~bi) s[sn++] = buf[bi];
if(bi < bn) break;
bn = fread(buf,1,SIZE,stdin);
bi &= 0;
}
s[sn] &= 0;
return sn;
}
inline bool read(register int &x){
int n = read(str), bf = 0;
if(!n) return 0;
register int i=0;
(str[i] == '-') && (bf = 1, i = -~i);
(str[i] == '+') && (i = -~i);
for (x = 0; i < n; i = -~i) x = (x << 3) + (x << 1) + (str[i] ^ 48);
bf && (x = ~x + 1);
return 1;
}
inline bool read(register long long &x) {
int n = read(str), bf = 1;
if(!n) return 0;
register int i=0;
(str[i] == '-') && (bf = -1,i = -~i);
for (x = 0; i < n; i= -~i) x = (x << 3) + (x << 1) + (str[i] ^ 48);
(bf < 0) && (x = ~x + 1);
return 1;
}
inline void write(register int x) {
if(!x) obuf[opt++] = '0';
else {
(x < 0) && (obuf[opt++] = '-', x = ~x + 1);
register int sn = 0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1; i >= 0; i = ~-i) obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void write(register long long x) {
if(!x) obuf[opt++] = '0';
else {
(x < 0) && (obuf[opt++] = '-', x = ~x + 1);
register int sn = 0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1; i >= 0; i = ~-i) obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void write(register unsigned long long x){
if(!x) obuf[opt++] = '0';
else {
register int sn=0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1 ; i >= 0 ; i = ~-i)obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void write(register char x) {
obuf[opt++] = x;
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void Fflush(){
opt && fwrite(obuf, 1, opt, stdout);
opt &= 0;
}
}
int n, id;
int a[1000005], ans[1000005];
pair<int, int> L[1000005], R[1000005];
struct sss{
int l, r;
}e[1000005];
namespace BIT{
inline int lowbit(int x) {
return x & (-x);
}
int tr[1000005];
inline void add(int pos, int d) {
for (int i = pos; i <= n; i += lowbit(i)) tr[i] += d;
}
inline int ask(int pos) {
int an = 0;
for (int i = pos; i; i -= lowbit(i)) an += tr[i];
return an;
}
}
int st[1000005], s[1000005], cnt, tot;
int main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
FI(n); FI(id);
for (int i = 1; i <= n; i++) {
FI(a[i]);
}
for (int i = 1; i <= n; i++) {
while(cnt > 0 && a[i] <= a[st[cnt]]) cnt--;
while(tot > 0 && a[i] >= a[s[tot]]) tot--;
e[i].r = min(st[cnt], s[tot]);
st[++cnt] = i;
s[++tot] = i;
}
cnt = tot = 0;
for (int i = n; i >= 1; i--) {
while(cnt > 0 && a[i] <= a[st[cnt]]) cnt--;
while(tot > 0 && a[i] >= a[s[tot]]) tot--;
e[i].l = max(st[cnt], s[tot]);
if (cnt == 0 || tot == 0) e[i].l = 2e9;
st[++cnt] = i;
s[++tot] = i;
}
for (int i = 1; i <= n; i++) {
L[i] = {e[i].l, i};
R[i] = {e[i].r, i};
}
sort(L + 1, L + 1 + n, greater<pair<int, int> >());
sort(R + 1, R + 1 + n);
for (int i = 1; i <= n; i++) BIT::add(i, 1);
int now = 1;
for (int i = 1; i <= n; i++) {
while(now <= n && R[now].first < i) {
BIT::add(R[now].second, -1);
now++;
}
if (e[i].l > n) FO(0);
else FO(BIT::ask(n) - BIT::ask(e[i].l - 1));
FO(' ');
}
FO('\n');
while(now <= n) BIT::add(R[now].second, -1);
now = 1;
for (int i = 1; i <= n; i++) BIT::add(i, 1);
for (int i = n; i >= 1; i--) {
while(now <= n && L[now].first > i) {
BIT::add(L[now].second, -1);
now++;
}
if (e[i].r < 1) continue;
ans[i] = BIT::ask(e[i].r);
}
for (int i = 1; i <= n; i++) {
FO(ans[i]);
FO(' ');
}
Flush;
return 0;
}