20230710
I - Visiting Friend(点双/圆方树)
题意
多次询问两个点之间所有路径可能经过的点数，路径只需要满足起点和终点不重复经过。
\(N,M,Q ≤ 5\times10^5\)
题解
建出圆方树，方点点权设为0，圆点点权设为1。维护一下子树和,讨论两个点的LCA是不是其中一个点两种情况，删去不可能经过的点即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, tot, m;
vector<int> g[N], G[N], dcc[N];
int w[N];
int dfn[N], low[N], idx;
stack<int> s;
void yfs(int u, int fa) {
dfn[u] = low[u] = ++idx;
s.push(u);
int cnt = 0;
for (auto v : g[u]) {
if (v == fa) continue;
if (!dfn[v]) {
yfs(v, u);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v]) {
tot++;
int x;
do {
x = s.top(); s.pop();
G[x].push_back(tot); G[tot].push_back(x);
} while (x != v);
G[u].push_back(tot); G[tot].push_back(u);
w[tot] = 0;
}
} else low[u] = min(low[u], dfn[v]);
}
}
int dep[N];
int sum[N];
int f[N][22];
void dfs(int u, int fa) {
//cout << u << "\n";
f[u][0] = fa;
dep[u] = dep[fa] + 1;
sum[u] = w[u];
for (int i = 1; i <= 21; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (auto v : G[u]) {
if (v == fa) continue;
dfs(v, u);
sum[u] += sum[v];
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int k = dep[x] - dep[y];
for (int i = 0; i <= 21; i++) {
if (k >> i & 1) x = f[x][i];
}
if (x == y) return x;
for (int i = 21; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
void solve() {
cin >> n >> m;
tot = n;
idx = 0;
while (!s.empty()) s.pop();
for (int i = 1; i <= n * 4; i++) {
dcc[i].clear(); g[i].clear(); G[i].clear();
dfn[i] = low[i] = dep[i] = sum[i] = 0;
w[i] = 1;
for (int j = 0; j <= 21; j++) f[i][j] = 0;
}
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
yfs(1, 0);
dfs(1, 0);
int q; cin >> q;
while (q--) {
int u, v; cin >> u >> v;
if (dep[u] > dep[v]) swap(u, v);
int t = lca(u, v);
if (t == u) {
int k = dep[v] - dep[u] - 1;
int tv = v;
for (int i = 0; i <= 21; i++) {
if (k >> i & 1) tv = f[tv][i];
}
cout << sum[tv] - sum[v] + 2 << "\n";
} else {
cout << n - (sum[u] - 1) - (sum[v] - 1) << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1; cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
1
9 9
1 2 2 3 3 4 4 5 5 6 6 7 7 1
5 8 5 9
9999
8 9
*/
E - Sum Over Zero(树状数组优化dp)
题意
给定一个序列，选择一些不相交子区间，满足每个子区间的和非负，最大化区间的总长度。
题解
设 \(dp_i\) 表示以 \([1,i]\) 的答案，很容易想到 \(O(n^2)\) 的dp：
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1]; //初始化:不选i
for (int j = 0; j < i; j++)
if (sum[i] - sum[j] >= 0) //更新:枚举所有[j+1,i]非负的区间
dp[i] = max(dp[i], dp[j] + (i - j) )
}
考虑优化：移个项，则更新时有
\[dp[i] - i = \max\limits_{sum[j]\le sum[i]}(dp[j] - j) \]只需要使用树状数组将每次的dp[i] - i插入到下标sum[i]处，维护前缀最大值即可。
sum[i]可能很大，需要离散化 。同时注意一开始dp[0]-0=0,sum[0]=0。需要将离散化后的0插入到树状数组中。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 10, inf = 1e17;
int n, a[N], sum[N], dp[N];
int pos0, val[N];
void work(int arr[]) {
for (int i = 1; i <= n; i++) val[i] = arr[i];
sort(val + 1, val + 1 + n);
int m = unique(val + 1, val + 1 + n) - val - 1;
for (int i = 1; i <= n; i++) {
arr[i] = lower_bound(val + 1, val + 1 + m, arr[i]) - val;
}
pos0 = lower_bound(val + 1, val + 1 + m, 0) - val;
}
int t[N];
void add(int i, int x) {
for (; i <= n; i += i & -i) {
t[i] = max(t[i], x);
}
}
int ask(int i) {
int res = -inf;
for (; i; i -= i & -i) {
res = max(res, t[i]);
}
return res;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
t[i] = -inf;
}
work(sum);
add(pos0, 0);
for (int i = 1; i <= n; i++) {
dp[i] = max(dp[i - 1], ask(sum[i]) + i);
add(sum[i], dp[i] - i);
}
cout << dp[n] << "\n";
}
signed main() {
int T = 1; //cin >> T;
while (T--) {
solve();
}
return 0;
}
20230711
C - Necklace(最小表示法)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
char s[N];
int main() {
scanf("%s", s);
int n = strlen(s);
int p1 = 0, p2 = 1, i = 0;
while (p1 < n && p2 < n && i < n) {
if (s[(p1 + i) % n] == s[(p2 + i) % n]) {
i++;
} else {
if (s[(p1 + i) % n] > s[(p2 + i) % n]) {
p1 += i + 1;
} else {
p2 += i + 1;
}
i = 0;
if (p1 == p2) p2++;
}
}
for (int i = 0; i < n; i++) putchar(s[(p1 + i) % n]);
return 0;
}
B - 我承认阁下的字符串匹配很强(kmp+dp)
题意
给定一个字符串S , 包含小写字母和问号，其中每个问号都可以替换成任意一个小写字母，你需要构造一个方案，最大化字符串T在S出现的次数。
题解
//
// Created by blackbird on 2023/7/9.
//
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e6 + 10;
int n, m, ne[N], ans;
char s[N], t[N];
void getnext(char t[], int m) {
for (int i = 2, j = 0; i <= m; i++) {
while (j && t[j + 1] != t[i]) j = ne[j];
if (t[j + 1] == t[i]) j++;
ne[i] = j;
}
}
int f[N], g[N];
void solve(char s[], int n, char t[], int m) {
for (int i = 1; i - 1 + m <= n; i++) {
bool ok = 1;
for (int j = 1; j <= m; j++) {
if (s[i - 1 + j] != t[j] && s[i - 1 + j] != '?') {
ok = 0; break;
}
}
if (ok) { //T在相同前后缀处重叠
int j = ne[m];
while (j) {
g[i - 1 + m] = max(g[i - 1 + m], g[i - 1 + j] + 1);
j = ne[j];
}
g[i - 1 + m] = max(g[i - 1 + m], f[i - 1] + 1);
}
f[i - 1 + m] = max(f[i - 1 + m - 1], g[i - 1 + m]);
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> s + 1 >> t + 1;
n = strlen(s + 1); m = strlen(t + 1);
getnext(t, m);
solve(s, n, t, m);
cout << f[n] << "\n";
return 0;
}
K - Difficult Constructive Problem(上下界贪心构造/dp)
题意
给定一个长度为 n 的字符串 s ，其中 si ∈ {‘0’, ‘1’, ‘?’}
另外给定一个整数 k，
将字符串中 ‘?’ 换成 ‘0’ 或 ‘1’，使得满足 1 ≤ i < n 且 si != si+1 的下标 i 恰有 k 个。
求字典序最小的一组解。
题解
//
// Created by blackbird on 2023/7/11.
//
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e6 + 10, inf = 1e9;
int n, k, a[N];
char s[N];
int mn[N][2], mx[N][2];
string calc() {
for (int i = 0; i <= 1; i++) {
if (s[n] == i + '0') mn[n][i] = mx[n][i] = 0;
else mn[n][i] = inf, mx[n][i] = -inf;
}
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j <= 1; j++) {
if (s[i] == j + '0' || s[i] == '?') {
mn[i][j] = min(mn[i + 1][j], mn[i + 1][1 - j] + 1);
mx[i][j] = max(mx[i + 1][j], mx[i + 1][1 - j] + 1);
} else mn[i][j] = inf, mx[i][j] = -inf;
}
}
if (k % 2 != mn[1][s[1] - '0'] % 2) {
//cout << "wrong evenodd\n";
return "2";
}
string res;
int cnt = 0;
for (int i = 1; i <= n; i++) {
bool ok = 0;
for (int j = 0; j <= 1; j++) {
int t = (i > 1 && j != res[i - 2] - '0' ? 1 : 0);
if (mn[i][j] <= k - (cnt + t) && k - (cnt + t) <= mx[i][j]) {
res.push_back(j + '0');
cnt += t;
ok = 1; break;
}
}
if (!ok) {
return "2";
}
}
return res;
}
void solve() {
cin >> n >> k >> s + 1;
char s1 = s[1], sn = s[n];
string ans = "2";
for (char i = '0'; i <= '1'; i++) if (s1 == '?' || s1 == i) {
for (char j = '0'; j <= '1'; j++) if (sn == '?' || sn == j) {
s[1] = i;
s[n] = j;
ans = min(ans, calc());
}
}
if (ans == "2") cout << "Impossible\n";
else cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1; cin >> T;
while (T--) {
solve();
}
return 0;
}
20230712
M - Window Arrangement(最小费用最大流)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
struct Edge{
int from, to, cap, flow, cost;
Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
};
struct MCMF{
int n, m, inq[N], d[N], p[N], a[N];
vector<Edge> edges;
vector<int> G[N];
void init(int n){
this->n = n;
for(int i = 0; i <= n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap,long long cost){
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost));
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BellmanFord(int s,int t,int &flow,long long &cost){
for(int i = 0; i <= n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
queue<int> Q;
Q.push(s);
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = 0;
for(int i = 0; i < G[u].size(); i++){
Edge& e = edges[G[u][i]];
if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
d[e.to] = d[u]+e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u],e.cap-e.flow);
if(!inq[e.to]) {Q.push(e.to); inq[e.to] = 1;}
}
}
}
if(d[t]==INF) return false;
flow += a[t];
cost += (long long)d[t]*(long long)a[t];
for(int u = t; u!=s; u = edges[p[u]].from){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return true;
}
int MincostMaxflow(int s,int t,long long &cost){
int flow = 0;
cost = 0;
while(BellmanFord(s,t,flow,cost));
return flow;
}
} g;
int n, m, O, S, T, a[51][51], w[51][51];
int calc_grid(int x, int y) {
return (x - 1) * m + y;
}
int calc_window(int x, int y, int dx, int dy) {
// ‘|’ windows: n*m + 1 ~ n*m + n*(m-1) = n*(2m-1)
// '-' windows: n*(2m-1) + 1 ~ n*(2m-1) + (n-1)*m
if (dx == 0) {
int base = n * m;
if (dy == -1) y--, dy = 1; //left to right
int delta = (m - 1) * (x - 1) + y;
return base + delta;
} else {
int base = n * (m * 2 - 1);
if (dx == -1) x--, dx = 1;//up to down
int delta = m * (x - 1) + y;
return base + delta;
}
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> w[i][j];
g.init(3 * n * m + 5);
O = 3 * n * m;
S = 3 * n * m + 1;
T = 3 * n * m + 2;
//cout << "?????OST\n";
g.AddEdge(O, T, 1e9, 0);
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
g.AddEdge(S, calc_grid(i, j), w[i][j], 0);
for(int d = 0; d < 4; d++) {
int x = i + dx[d], y = j + dy[d];
if(x < 1 || y < 1 || x > n || y > m) {
g.AddEdge(calc_grid(i, j), O, 1, 0);
continue;
}
g.AddEdge(calc_grid(i, j), calc_window(i, j, dx[d], dy[d]), 1, 0);
if (dx[d] + dy[d] == 1) {
g.AddEdge(calc_window(i, j, dx[d], dy[d]), T, 1, 0);
g.AddEdge(calc_window(i, j, dx[d], dy[d]), T, 1, a[i][j] * a[x][y]);
}
}
}
}
long long cost = 0;
g.MincostMaxflow(S, T, cost);
cout << cost << "\n";
return 0;
}
Squirrel Game(阶梯nim游戏)
考虑模k意义下，构成k个倒着的阶梯Nim问题。
阶梯nim问题的结论为，奇数位置的异或和决定状态。(0为先手必败)。
#include<cstdio>
#include<algorithm>
#define ll long long
#define maxn 100005
using namespace std;
int m,n,k;
ll ans,a[maxn],del[maxn];
int main()
{
scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
a[i]-=i;
del[i]=a[i]-a[i-1];
}
// for(int i=1;i<=min(n,k);++i)
// {
// ll ret=0,mx=0;
// for(int j=i;j<=n;j+=k)
// {
// ret+=del[j];
// mx=max(mx,del[j]);
// }
// if(mx<ret)
// ret++;
// ans^=ret;
// }
for(int i=n;i>max(0,n-k);--i)
{
ll ret=0;
for(int j=i,fl=1;j>=1;j-=k)
{
if(fl)
ret^=del[j];
fl^=1;
}
ans^=ret;
}
if(ans)
printf("Twinkle\n");
else printf("Nova\n");
return 0;
}