16.0
邮寄
有史以来考的最好的一次。
开场秒 B。
A 想了一个做法。然后光速假掉，加了个三分勉强能行。
然后 cd 不会。
A
显然可以三分科技使用次数，然后 RMQ 计算答案。
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int id, t;
bool operator >(const node &b) const {
return t > b.t;
}
};
int n, k, arr[100010], fa[100010][22], fw[100010][22];
vector<int> v;
long long check(int x) {
long long rs = 0;
for(int i = 1; i <= n; i++) {
int c = 0, t = i;
for(int j = 20; j >= 0; j--) {
if(c + fw[t][j] <= x) {
c += fw[t][j];
t = fa[t][j];
}
}
rs += arr[t];
}
return rs + k * x;
}
long long lmrm() {
int l = 0, r = n + 2;
long long ans = LLONG_MAX;
for(; l <= r; ) {
int len = (r - l) / 3;
int lmid = l + len, rmid = r - len;
if(check(lmid) <= check(rmid)) {
ans = min(ans, check(lmid));
r = rmid - 1;
}else {
ans = min(ans, check(rmid));
l = lmid + 1;
}
}
return ans;
}
signed main() {
freopen("collect.in", "r", stdin);
freopen("collect.out", "w", stdout);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
rotate(arr + 1, min_element(arr + 1, arr + n + 1), arr + n + 1);
for(int i = n; i >= 1; i--) {
fw[i][0] = 100000000;
for(; v.size() && arr[v.back()] > arr[i]; v.pop_back()) {
fw[v.back()][0] = v.back() - i;
fa[v.back()][0] = i;
}
v.push_back(i);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 20; j++) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
fw[i][j] = fw[i][j - 1] + fw[fa[i][j - 1]][j - 1];
}
}
cout << lmrm() << '\n';
return 0;
}
B
容斥，倍增。
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int lc, rc;
}ctl[200020], ctg[200020];
int n, arr[200020], fl[200020][22], fr[200020][22], rcl, rcg;
long long ans;
vector<int> v;
// 5.1 Minimum, except in both
void TVl(int x, int l, int r) {
if(!x) {
return ;
}
ans -= (r - l);
int cl = x, cr = x;
for(int i = 20; i >= 0; i--) {
if(fl[cl][i] >= l) {
cl = fl[cl][i];
ans += (1 << i);
}
if(fr[cr][i] <= r) {
cr = fr[cr][i];
ans += (1 << i);
}
}
TVl(ctl[x].lc, l, x - 1);
TVl(ctl[x].rc, x + 1, r);
}
// 5.2 Maximum
void TVg(int x, int l, int r) {
if(!x) {
return ;
}
ans -= (r - l);
TVg(ctg[x].lc, l, x - 1);
TVg(ctg[x].rc, x + 1, r);
}
signed main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
// 1. Cartesian, <
for(int i = 1; i <= n; i++) {
if(!v.size()) {
v.push_back(i);
continue;
}
for(; v.size() > 1 && arr[v.back()] > arr[i]; v.pop_back()) {
ctl[i].lc = v.back();
}
if(arr[v.back()] > arr[i]) {
ctl[i].lc = v.back();
v.pop_back();
}else {
ctl[v.back()].rc = i;
}
v.push_back(i);
}
rcl = v[0];
v.clear();
// 2. Cartesian, >
for(int i = 1; i <= n; i++) {
if(!v.size()) {
v.push_back(i);
continue;
}
for(; v.size() > 1 && arr[v.back()] < arr[i]; v.pop_back()) {
ctg[i].lc = v.back();
}
if(arr[v.back()] < arr[i]) {
ctg[i].lc = v.back();
v.pop_back();
}else {
ctg[v.back()].rc = i;
}
v.push_back(i);
}
rcg = v[0];
v.clear();
// 3. Left-first, >
for(int i = n; i >= 1; i--) {
for(; v.size() && arr[v.back()] < arr[i]; v.pop_back()) {
fl[v.back()][0] = i;
}
v.push_back(i);
}
v.clear();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 20; j++) {
fl[i][j] = fl[fl[i][j - 1]][j - 1];
}
}
/*
for(int i = 1; i <= n; i++) {
cout << fl[i][0] << ' ';
}
cout << '\n';
//*/
// 4. Right-first, >
for(int i = 0; i <= 20; i++) {
fr[n + 1][i] = n + 1;
}
for(int i = 1; i <= n; i++) {
for(; v.size() && arr[v.back()] < arr[i]; v.pop_back()) {
fr[v.back()][0] = i;
}
v.push_back(i);
}
for(int i = n; i >= 1; i--) {
if(!fr[i][0]) {
fr[i][0] = n + 1;
}
for(int j = 1; j <= 20; j++) {
fr[i][j] = fr[fr[i][j - 1]][j - 1];
}
}
/*
for(int i = 1; i <= n; i++) {
cout << fr[i][0] << ' ';
}
cout << '\n';
//*/
// 5. Cal ans
ans = 1ll * n * (n - 1) / 2;
TVl(rcl, 1, n);
TVg(rcg, 1, n);
cout << ans << '\n';
return 0;
}
//Cartesian (<, >), Left-first with fa[200020][20], Right-first with fa[200020][20]
C
定义转移矩阵 \(A(c)_{i, j} = \begin{cases} 1 &\text{if } c \text{ is the } j \text{-th character or } i = j \\ 0 &\text{otherwise} \end{cases}\)
然后就可以 121312141213121 做了。
答案矩阵 \(B(i) = B(i + 1) \times A(s_i) \times B(i + 1)\)。
#include <bits/stdc++.h>
using namespace std;
const int kMod = int(1e9) + 7;
struct node {
int a[27][27];
node() {
memset(a, 0, sizeof(a));
}
auto operator [](int x) {
return a[x];
}
void init() {
for(int i = 0; i <= 26; i++) {
a[i][i] = 1;
}
}
node operator *(node b) {
node rs;
for(int i = 0; i <= 26; i++) {
for(int j = 0; j <= 26; j++) {
for(int k = 0; k <= 26; k++) {
rs[i][j] = (rs[i][j] + 1ll * a[i][k] * b[k][j]) % kMod;
}
}
}
return rs;
}
};
int n, ans;
char c[550];
node convs(char c) {
node rs;
for(int i = 0; i <= 26; i++) {
if(c - 'a' == i) {
fill(rs[i], rs[i] + 27, 1);
}else {
rs[i][i] = 1;
}
}
return rs;
}
node solve(int x) {
if(x > n) {
node tmp;
tmp.init();
return tmp;
}
node tmp = solve(x + 1);
return tmp * convs(c[x]) * tmp;
}
int main() {
freopen("subseq.in", "r", stdin);
freopen("subseq.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> c[i];
}
node rs = solve(1);
for(int i = 0; i < 26; i++) {
ans = (ans + rs[i][26]) % kMod;
}
cout << ans << '\n';
return 0;
}
D
首先建出 DFS 树。
显然，删除的两条边中必然有一条是树边。
注意：我们不考虑树边中存在桥的情况。
- 树+其他
此时，这个其他一定是唯一一个覆盖了这条树边的其他边。
- 树+树
此时，覆盖了这两个树边的的其他边的集合 相同。
然后，对于 2.，使用 xor hash 维护。
#include <bits/stdc++.h>
#define st first
#define nd second
#define u64 unsigned long long
#define int long long
using namespace std;
int n, m, k, u, v, is[200020], dfn[200020], low[200020], dcnt, cnt[200020], vis[200020];
long long ans;
random_device rd;
mt19937_64 mt(rd());
u64 sum[200020];
map<u64, int> mp;
multiset<pair<int, int> > to[200020];
void DFS(int x, int pd) {
dfn[x] = low[x] = ++dcnt;
for(auto i : to[x]) {
if(!dfn[i.st]) {
DFS(i.st, i.nd);
low[x] = min(low[x], low[i.st]);
if(low[i.st] > dfn[x]) {
is[i.st] = 1;
}
}else {
if(i.nd != pd) {
if(dfn[i.st] < dfn[x]) {
int tmp = mt();
cnt[x]++, sum[x] ^= tmp;
cnt[i.st]--, sum[i.st] ^= tmp;
}
low[x] = min(low[x], dfn[i.st]);
}
}
}
}
void cal(int x) {
vis[x] = 1;
for(auto i : to[x]) {
if(!vis[i.st]) {
cal(i.st);
cnt[x] += cnt[i.st];
sum[x] ^= sum[i.st];
}
}
}
signed main() {
//#ifndef LOCAL
freopen("attack.in", "r", stdin);
freopen("attack.out", "w", stdout);
//#endif
cin >> n >> m >> k;
for(int i = 1; i <= m; i++) {
cin >> u >> v;
to[u].insert({v, i});
to[v].insert({u, i});
}
if(k == 1) {
DFS(1, 0);
cout << accumulate(is + 1, is + n + 1, 0) << '\n';
}else {
DFS(1, 0);
cal(1);
int cur = m;
for(int i = 2; i <= n; i++) {
if(is[i]) {
ans += cur;
cur--;
}else {
ans += (cnt[i] == 1);
mp[sum[i]]++;
}
}
for(auto i : mp) {
ans += i.second * (i.second - 1) / 2;
}
cout << ans << '\n';
}
return 0;
}