A判断一下前面能否空出来就就行，也就是 $l \geq r-l+1$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl int main(){ int T;scanf("%d",&T); while(T--){ int l,r;scanf("%d%d",&l,&r); puts(l >= r-l+1 ? "YES" : "NO"); } return 0; }B相当于不能有子串 11 和 00。那么如果有 11 肯定在后面有一个地方有 00 （反证），所以每次操作最多可以消去两个这样的连续的东西，求出有多少个相邻相同的位置 $x$，答案就是 $\lceil \frac{x}{2} \rceil$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; char str[MAXN]; int main(){ int T;scanf("%d",&T); while(T--){ int n;scanf("%d",&n); scanf("%s",str+1); int ans = 0; FOR(i,2,n) if(str[i] == str[i-1]) ans++; ans = (ans+1)>>1; printf("%d\n",ans); } return 0; }C首先可以发现一个东西：将匹配方式连边，一定存在一种分配方式使得最优解没有包含关系的线段，因为包含关系可以通过交换变成相交，并且代价不变。排序后可以设 $f_{i,j}$ 表示考虑了前 $i$ 个数，最小的 $j$ 满足 $j$ 开始后面一段数字都没有被用过的代价，转移直接枚举下一个填啥就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 600+5; int n,a[MAXN]; bool vis[MAXN]; int f[2][MAXN],now; int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i); std::sort(a+1,a+n+1); CLR(f,0x3f); f[now = 0][0] = 0; FOR(i,1,n){ CLR(f[now^1],0x3f); FOR(j,0,3*n){ if(f[now][j] == 0x3f3f3f3f) continue; FOR(k,j+1,3*n){ f[now^1][k] = std::min(f[now^1][k],f[now][j]+std::abs(a[i]-k)); } } now ^= 1; } int ans = 1e9; FOR(i,1,3*n) ans = std::min(ans,f[now][i]); printf("%d\n",ans); } return 0; }D感性理解一下，我们每次取出深度最小的点，接上连续的一段递增序列作为它的后继即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,a[MAXN]; int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i); std::priority_queue<P,std::vector ,std::greater > q; q.push(MP(0,1));int p = 2; int ans = 0; while(!q.empty()){ int dep = q.top().fi;q.pop();ans = std::max(ans,dep); int las = -1;std::vector<int> v; while(p <= n && las <= a[p]) las = a[p++],v.pb(las); for(auto x:v) q.push(MP(dep+1,x)); } printf("%d\n",ans); } return 0; }E如果没有不能选的限制就是经典 dp：我们观察两个位置 $i<j$ 能同时不改变的条件是 $a_j-a_i-1 \geq j-i-1$，也就是 $a_i-i \leq a_j-j$，最多能不修改的数也就是设 $b_i=a_i-i$，$b_i$ 的非严格最长上升子序列长度。这个题限定某些数不能改变，先判完无解后相当于变成了强制选取某些位置的最长上升子序列，对于每段分别做即可。注意这里 infty 开大点。。要不然判无解会判错。。。真正考试对拍的时候还是多试试 corner case 吧。。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5e5 + 5; int n,k; LL a[MAXN]; std::vector<int> S; std::vector<LL> SS; struct BIT{ #define lowbit(x) ((x)&(-(x))) int tree[MAXN],ts[MAXN],now; inline void reset(){ ++now; } inline void add(int pos,int x){ while(pos < MAXN){ if(ts[pos] != now) tree[pos] = 0,ts[pos] = now; tree[pos] = std::max(tree[pos],x); pos += lowbit(pos); } } inline int query(int pos){ int res = 0;if(!pos) return 0; while(pos){ if(ts[pos] != now) tree[pos] = 0,ts[pos] = now; res = std::max(res,tree[pos]); pos -= lowbit(pos); } return res; } }bit; int b[MAXN]; int main(){ scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d",a+i); a[0] = -1e18;a[n+1] = 1e18; FOR(i,0,n+1) SS.pb(a[i]-i); std::sort(all(SS));SS.erase(std::unique(all(SS)),SS.end()); FOR(i,0,n+1) b[i] = std::lower_bound(all(SS),a[i]-i)-SS.begin()+1; S.pb(0); FOR(i,1,k){ int x;scanf("%d",&x); S.pb(x); } S.pb(n+1); FOR(i,1,(int)S.size()-1){ if(a[S[i]]-a[S[i-1]] < S[i]-S[i-1]){ puts("-1"); return 0; } } int ans = 0; FOR(i,1,(int)S.size()-1){ auto work = [&](int l,int r){ bit.reset(); int res = 0; FOR(i,l,r){ if(b[i] < b[l]) continue; res = bit.query(b[i])+1; bit.add(b[i],res); } return r-l+1-res; }; ans += work(S[i-1],S[i]); } printf("%d\n",ans); return 0; }F居然让我想了一会。。不过也是简单题直接做我们可能需要记录哪些数选了，状态会爆炸。我们考虑不断往后面加数，如果这个序列的最大值确定了，那么这个序列不改变最大值的前提下的最大长度就确定了，如果知道了目前长度，我们就能知道不改变最大值前提下这个位置的数有多少种可能。于是设 $f_{i,j}$ 表示放了 $i$ 个数，最大值是 $j$ 的方案数，预处理 $las_i$ 表示最大值是 $i$ 的时候序列的最长长度，$nxt_i$ 表示最大值是 $i$ 要改变最大值可以放的最小的数，$cnt_i$ 表示值为 $i$ 的数的个数，转移：不改变最大值：$f_{i,j}\times (las_j-i+1) \to f_{i+1,j}$改变最大值：$f_{i,j}\times cnt_k \to f_{i+1,k}(k \geq nxt_j)$用一些前缀和技巧可以优化到 $O(n^2)$。看了一个比较 nb 的做法，大概是我们 dp 的时候只在放满的时候转移（也就是最大值为 $j$ 的时候我们只考虑状态 $f_{las_j,j}$），这个就是设 $f_i$ 表示最大值为 $i$ 的方案数，这样长度就是 $las_i+1$，转移的时候枚举上一次的最大值，乘上一个系数选进去就行了。$$ \begin{aligned} f_i &= \sum_j f_j\binom{n-las_j-2}{las_i-las_j-1}(las_i-las_j-1)!\\ &= \frac{1}{(n-las_i-1)}\sum_j f_j (n-las_j-2)! \end{aligned} $$然后前缀和优化一下就 $O(n)$ 了。还是要考虑大多数 dp 状态都是无用的，只对真正有用的决策即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5000+5; const int ha = 998244353; int a[MAXN],n; int f[2][MAXN],cf[MAXN]; // 选了 i 个数 最大值是 j std::vector<int> S; int las[MAXN];// 选了 i 之后 还有几个数可以放 int nxt[MAXN];// 选了 i 之后 下一个必须选啥 int cnt[MAXN]; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i); std::sort(a+1,a+n+1); FOR(i,1,n) S.pb(a[i]);S.erase(std::unique(all(S)),S.end()); FOR(i,1,n) cnt[std::lower_bound(all(S),a[i])-S.begin()+1]++; int m = S.size(); FOR(i,1,m){ las[i] = las[i-1]; while(las[i]+1 <= n && a[las[i]+1]*2 <= S[i-1]) las[i]++; } nxt[0] = 1; FOR(i,1,m){ nxt[i] = -1; FOR(j,i+1,m){ if(S[i-1]*2 <= S[j-1]) {nxt[i] = j;break;} } } int now = 0;f[now][0] = 1; FOR(i,1,n){ CLR(f[now^1],0);CLR(cf,0); FOR(j,0,m){ if(!f[now][j]) continue; int t = las[j]-i+1+1; if(j == 0) t = 0; if(t > 0) add(f[now^1][j],1ll*f[now][j]*t%ha); if(nxt[j] != -1) add(cf[nxt[j]],f[now][j]); } FOR(j,1,m) add(cf[j],cf[j-1]),add(f[now^1][j],1ll*cf[j]*cnt[j]%ha); now ^= 1; // FOR(i,0,m) printf("%d ",f[now][i]);puts(""); } printf("%d\n",f[now][m]); return 0; }G建 AC 自动机，我们枚举询问串的每一个后缀，走到对应的节点上，这个串的子串就是 fail 树的祖先，所以相当于要支持单点修改，查询到根的一条链上的最大值，树剖即可。$O(n \log^2 n)$。题解做法一：我们发现对于一个点，它在 fail 树上到根的路径上终止节点最多有 $O(\sqrt n)$ 个（因为 $\sum_{i=1}^n i = O(n^2)$），所以记录一下每个点上面距离最近的终止节点，暴力跳就好了。$O(q\sqrt n)$。一个比较 nb 的离线单 log 做法：先把询问和修改挂在树上，我们经过一个点 apply 它的所有操作，现在只有了操作时间的限制，我们用一个线段树，第 $i$ 个位置维护操作时间为 $i$ 的答案，不难发现要支持区间对一个数取 $\max$，撤销，单点求值。因为只需要单点求值，搞个标记永久化就好了，这样就只会改变 $O(\log n)$ 个节点，可以存下来了。这种线段树+撤销都可以考虑下标记永久化...#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; int ch[MAXN][26],fail[MAXN],tot = 1,rt = 1; int ps[MAXN]; inline void insert(char str[],int id){ int len = strlen(str+1),v = rt; FOR(i,1,len){ int o = str[i]-'a'; if(!ch[v][o]) ch[v][o] = ++tot; v = ch[v][o]; } ps[id] = v; } std::vector<int> G[MAXN]; inline void build(){ std::queue<int> q; FOR(i,0,25){ if(ch[rt][i]) q.push(ch[rt][i]),fail[ch[rt][i]] = rt; else ch[rt][i] = rt; } while(!q.empty()){ int v = q.front();q.pop(); FOR(i,0,25){ if(ch[v][i]) q.push(ch[v][i]),fail[ch[v][i]] = ch[fail[v]][i]; else ch[v][i] = ch[fail[v]][i]; } } FOR(i,2,tot) G[fail[i]].pb(i); } int mx[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void update(int x,int l,int r,int p,int d){ if(l == r){ mx[x] = d; return; } int mid = (l + r) >> 1; if(p <= mid) update(lc,l,mid,p,d); else update(rc,mid+1,r,p,d); mx[x] = std::max(mx[lc],mx[rc]); } inline int query(int x,int l,int r,int L,int R){ if(l == L && r == R) return mx[x]; int mid = (l + r) >> 1; if(R <= mid) return query(lc,l,mid,L,R); if(L > mid) return query(rc,mid+1,r,L,R); return std::max(query(lc,l,mid,L,mid),query(rc,mid+1,r,mid+1,R)); } int dfn[MAXN],sz[MAXN],tp[MAXN],fa[MAXN],son[MAXN]; inline void dfs1(int v){ sz[v] = 1; for(auto x:G[v]){ fa[x] = v; dfs1(x);sz[v] += sz[x]; if(sz[son[v]] < sz[x]) son[v] = x; } } inline void dfs2(int v,int tp=1){ static int ts = 0;dfn[v] = ++ts;::tp[v] = tp; if(son[v]) dfs2(son[v],tp); for(auto x:G[v]){ if(x == son[v]) continue; dfs2(x,x); } } inline int query(int x){ int res = -1; while(tp[x] != 1){ res = std::max(res,query(1,1,tot,dfn[tp[x]],dfn[x])); x = fa[tp[x]]; } res = std::max(res,query(1,1,tot,dfn[1],dfn[x])); return res; } int n,m; std::multiset<int> S[MAXN]; int val[MAXN]; char str[MAXN]; int main(){ scanf("%d%d",&n,&m); CLR(mx,-1); FOR(i,1,n){ scanf("%s",str+1); insert(str,i); S[ps[i]].insert(0); } build(); dfs1(1);dfs2(1); FOR(i,1,n) update(1,1,tot,dfn[ps[i]],*S[ps[i]].rbegin()); while(m--){ int opt;scanf("%d",&opt); if(opt == 1){ int p,x;scanf("%d%d",&p,&x); S[ps[p]].erase(S[ps[p]].find(val[p])); val[p] = x; S[ps[p]].insert(val[p]); update(1,1,tot,dfn[ps[p]],*S[ps[p]].rbegin()); } else{ scanf("%s",str+1);int len = strlen(str+1); int v = 1,res = -1; FOR(i,1,len){ v = ch[v][str[i]-'a']; res = std::max(res,query(v)); } printf("%d\n",res); } } return 0; }
A. 跳石头首先我们观察一下青蛙是怎么跳的：对于一个断点 $(i,i+1)$，如果有 $x$ 只青蛙往左跳，那么一定有 $x$ 只青蛙往右跳，所以 $a_i$ 一定是偶数。并且我们发现从 $a_i$ 到 $a_{i+1}$，变化的只可能是 $i+1$ 这一个青蛙，也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。我们考虑 $a_i$ 到 $a_{i+1}$ 的变化：如果是 $0$ 说明一定是 $i$ 跳到自己，如果多了 $2$ 说明 $i$ 往后跳，少了 $2$ 是往前跳。所以我们可以得出每个点往哪里跳，然后用类似括号序列的方式配对就行了：遇到往右的加入栈，往左的就随便取出一个。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,a[MAXN]; int ans[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n-1) scanf("%d",a+i); bool flag = 1; FOR(i,1,n){ flag &= !(a[i]&1); flag &= (std::abs(a[i]-a[i-1]) == 2 || a[i] == a[i-1]); } if(!flag){ puts("No"); return 0; } std::vector<int> S; FOR(i,1,n){ if(a[i] == a[i-1]+2){// 左括号 S.pb(i); } else if(a[i] == a[i-1]){ ans[i] = i; } else{ // 右括号 if(S.empty()){ puts("No"); return 0; } ans[S.back()] = i; ans[i] = S.back(); S.pop_back(); } } if(!S.empty()){ puts("No"); return 0; } puts("Yes"); FOR(i,1,n) printf("%d%c",ans[i]," \n"[i==n]); return 0; } /* 1. a[i] 都是偶数 并且正好一半往左一半往右 2. 考虑 a[i] 和 a[i+1]:如果中间不动 a[i]==a[i+1],如果中间往右 a[i+1] = a[i]+2,如果中间往左 a[i+1] = a[i]-2 往右必然要有一个往左 所以遇到往右的可以看成左括号 往左的可以看成右括号 就行了 */B. 树先把颜色相同的缩成一个树，感性理解操作肯定是每次操作同一个联通块，让他的影响不断增大。我们设第一次操作的点是 $x$ ，以 $x$ 为根建树，发现操作最大深度次就能完成。所以我们要让最大深度尽量小，就是直径的长度除以二。稍微注意下处理重边即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5e5 + 5; int n,a[MAXN]; std::vector<int> G[MAXN],T[MAXN]; bool vis[MAXN]; int f[MAXN]; inline int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); } inline void merge(int x,int y){ x = find(x);y = find(y); if(x == y) return; f[x] = y; } inline void dfs(int v){ vis[v] = 1; for(auto x:G[v]){ if(vis[x]) continue; if(a[x] != a[v]) continue; merge(v,x); dfs(x); } } int g[MAXN][2],ans; inline void dfs2(int v,int fa=0){ for(auto x:T[v]){ if(x == fa) continue; dfs2(x,v); if(g[v][0] < g[x][0]+1){ g[v][1] = g[v][0]; g[v][0] = g[x][0]+1; } else if(g[v][1] < g[x][0]+1){ g[v][1] = g[x][0]+1; } } ans = std::max(ans,g[v][0]+g[v][1]); } std::map<P,int> S; int main(){ scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),f[i] = i; FOR(i,2,n){ int u,v;scanf("%d%d",&u,&v);G[u].pb(v);G[v].pb(u); } FOR(i,1,n){ if(vis[i]) continue; dfs(i); } FOR(v,1,n){ for(auto x:G[v]){ if(find(x) != find(v)){ int a = find(x),b = find(v); if(a > b) std::swap(a,b); S[MP(a,b)] = 1; } } } for(auto x:S){ T[x.fi.fi].pb(x.fi.se); T[x.fi.se].pb(x.fi.fi); } dfs2(find(1)); printf("%d\n",(ans+1)/2); return 0; }C. 背包如果没有背包的限制，那么答案就是按照重量从大到小排序，求价值的 LDS。我们按照重量从大到小排序，那么位置 $i$ 我们能得出最多能选几个物品，设 $f_i$ 表示考虑了前 $i$ 个的答案，树状数组优化转移后特判一下能选几个物品的数量限制就行了。也就是 $f_i = \min(f_i,lim_i)$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; struct BIT{ #define lowbit(x) ((x)&(-(x))) int tree[MAXN]; inline void add(int pos,int x){ while(pos){ tree[pos] = std::max(tree[pos],x); pos -= lowbit(pos); } } inline int query(int pos){ int res = 0; while(pos < MAXN){ res = std::max(res,tree[pos]); pos += lowbit(pos); } return res; } }bit; int n; P a[MAXN]; int lim[MAXN],w[MAXN],m; inline void Solve(){ scanf("%d",&n);std::vector<int> S;CLR(bit.tree,0); FOR(i,1,n) scanf("%d%d",&a[i].fi,&a[i].se),S.pb(a[i].se); std::sort(all(S));S.erase(std::unique(all(S)),S.end()); FOR(i,1,n) a[i].se = std::lower_bound(all(S),a[i].se)-S.begin()+1; std::sort(a+1,a+n+1,[&](const P &x,const P &y){return x.fi > y.fi || (x.fi == y.fi && x.se > y.se);}); scanf("%d",&m); FOR(i,1,m) scanf("%d",w+i);std::sort(w+1,w+m+1);std::reverse(w+1,w+m+1); int ans = 0; FOR(i,1,n){ lim[i] = lim[i-1]; while(lim[i]+1 <= m && w[lim[i]+1] >= a[i].fi) ++lim[i]; int f = bit.query(a[i].se)+1;f = std::min(f,lim[i]); bit.add(a[i].se,f); ans = std::max(ans,f); } printf("%d\n",ans); } int main(){ // freopen("C.in","r",stdin); int T;scanf("%d",&T); while(T--) Solve(); return 0; }D. 蚂蚁先考虑不需要支持修改怎么做：假设现在有 $k$ 只蚂蚁，所在的点分别为 $v_1\ldots v_k$，设每个蚂蚁到达根的时间为 $t_i$，答案就是 $\max t_i$，我们观察一下有哪些限制：首先，每个蚂蚁的 $t_i \geq dep_{v_i}$，因为就算从开始爬也要花这些时间才能过去。然后，我们要保证不会在某时刻在同一个点，我们可以发现如果两只蚂蚁在某个时候在同一个点上，那么它们在根的时候也会在同一个点上，所以我们只需要保证 $t_i$ 互不相同就行了。所以问题变成了，每个变量有一个下界 $lim_i$，要求分配使得变量互不相同，并且最大值尽量小，这是个经典问题：考虑记 $s_i = \sum_{x=1}^k [lim_x \geq i]$，答案显然是 $\max(s_i+i-1)$，用线段树维护即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; int mx[MAXN<<2],tag[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void cover(int x,int d){ mx[x] += d;tag[x] += d; } inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(l == L && r == R){ cover(x,d); return; } int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); mx[x] = std::max(mx[lc],mx[rc]); } inline void build(int x,int l,int r){ tag[x] = 0; if(l == r){ mx[x] = l;return; } int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); mx[x] = std::max(mx[lc],mx[rc]); } int n,m; std::vector<int> G[MAXN]; int dep[MAXN]; inline void dfs(int v,int fa=0){ dep[v] = dep[fa]+1; for(auto x:G[v]) if(x != fa) dfs(x,v); } inline int query(int x,int l,int r,int L,int R){ if(L > R) return 1; if(l == L && r == R) return mx[x]; int mid = (l + r) >> 1;pushdown(x); if(R <= mid) return query(lc,l,mid,L,R); if(L > mid) return query(rc,mid+1,r,L,R); return std::max(query(lc,l,mid,L,mid),query(rc,mid+1,r,mid+1,R)); } std::multiset<int> S; int main(){ scanf("%d%d",&n,&m); FOR(i,2,n){ int f;scanf("%d",&f); G[f].pb(i); } dfs(1);build(1,1,n); S.insert(0); FOR(i,1,m){ int opt,x;scanf("%d%d",&opt,&x); if(opt == 1){ if(x != 1){ S.insert(dep[x]); modify(1,1,n,1,dep[x],1); } } else{ if(x != 1){ S.erase(S.find(dep[x])); modify(1,1,n,1,dep[x],-1); } } int t = *S.rbegin(); printf("%d\n",query(1,1,n,1,t)-1); } return 0; }E. 划分为啥完全没有思路。。。我们考虑固定 $1$ 为根，定义每个连通块的根为连通块深度最小的点，我们枚举其中一个连通块的根为 $x \neq 1$，那么有一个连通块根一定为 $1$，我们设剩下的那个连通块的根为 $y$，分类讨论：如果 $sz_x = |A|$：如果 $y$ 不是 $x$ 的祖先，$sz_y = sz_x$ 或 $sz_y=n-2sz_x$如果 $y$ 是 $x$ 的祖先，$sz_y=2sz_x$ 或 $sz_y=n-sz_x$如果 $sz_x = |C|$：如果 $y$ 不是 $x$ 的祖先，$sz_y=\frac{n-sz_x}{2}$如果 $y$ 是 $x$ 的祖先，$sz_y = \frac{n-sz_x}{2}+sz_x = \frac{n+sz_x}{2}$相当于我们对于一个点，想要询问到根的链上是否有点的 $sz$ 是某个值，这个可以 dfs 的时候处理一个数组搞出来；还需要询问某个点子树外并且不是它的祖先的所有点中是否有点 $sz$ 是某个值，预先处理所有的点的 $sz$ 出现情况，补集转化后变成了求子树内某个值的出现次数，这个可以用类似差分计算增量的方法实现，也就是在进入子树前记录一下要查询的值，然后进入这个子树，遍历完所有的点并且加到桶里后再求一下值，做个差就能得到子树的值。详情可以看代码#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; std::vector<int> G[MAXN]; int n; int sz[MAXN]; int c1[MAXN],c2[MAXN],c3[MAXN]; // c1: 整棵树 // c2: 查询子树用 // c3: 祖先 inline void dfs1(int v,int fa=0){ sz[v] = 1; for(auto x:G[v]){ if(x == fa) continue; dfs1(x,v); sz[v] += sz[x]; } ++c1[sz[v]]; } int ans = 0; inline void dfs2(int v,int fa=0){ if(2*sz[v] <= n && c3[2*sz[v]] && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(c3[n-sz[v]] && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(!((n+sz[v])&1) && c3[(n+sz[v])>>1]) ans = std::max(ans,(n-sz[v])>>1); int p1 = c2[sz[v]],p2 = n-2*sz[v] > 0 ? c2[n-2*sz[v]] : -1e9,p3 = (n-sz[v])&1 ? -1e9 : c2[(n-sz[v])>>1]; ++c3[sz[v]];++c2[sz[v]]; for(auto x:G[v]){ if(x == fa) continue; dfs2(x,v); } p1 = c1[sz[v]]-(c2[sz[v]]-p1); if(p2 != -1e9) p2 = c1[n-2*sz[v]]-(c2[n-2*sz[v]]-p2); if(p3 != -1e9) p3 = c1[(n-sz[v])>>1]-(c2[(n-sz[v])>>1]-p3); if(p1 > 0 && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(p2 > 0 && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(p3 > 0) ans = std::max(ans,(n-sz[v])>>1); --c3[sz[v]]; } int main(){ scanf("%d",&n); FOR(i,2,n){ int u,v;scanf("%d%d",&u,&v); G[u].pb(v);G[v].pb(u); } dfs1(1);dfs2(1); printf("%d\n",ans); return 0; }
A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的往右走，那么之后一定有一次往左走，并且跨越起点的，我们可以一开始就走到这个点，答案不会变劣。所以我们的路径只有可能是先往右最多走一次，再往左走。我们观察一下一个点 $v$ 到达左边的点 $x$ 的最短距离的分布是怎么样的：如果 $dis(v,x)=1$，那么有 $l_v \leq x$。如果 $dis(v,x) \leq 2$，那么我们就会先走一步，用这个点中转，也就是问在区间 $[l_v,n]$ 内是否存在点 $y$，使得 $dis(x,y) \leq 1$。注意这里这个区间包含了一些根本不跨过 $v$ 的点，但这是显然不影响答案的。归纳可以得到：如果 $dis(v,x) \leq k$，当且仅当存在一个点 $y \in [l_v,n]$，满足 $dis(x,y) \leq k-1$。所以一个暴力的想法是每次先特判了距离为 $1$ 的点，然后每次求出最往左的距离为 $2$ 的点跳过去，以此类推。。对于跳这种东西，我们肯定想到要用倍增优化。我们想找到 $\leq k$ 的最往左的点，就要找到 $dis(x,y) \leq k-1$ 的最往左的点。。。所以我们定义在找 $dis(v,x) \leq k$ 的一次跳跃是从 $x$ 点找到最小的一个点 $z$，满足 $\exists y \in [l_v,n],dis(z,y) \leq k-1$，所以设 $f_{i,j}$ 表示从 $i$ 号点，跳了 $2^j$ 次（也就是处理了距离为 $[1,2^j+1]$ 的点），为了统计答案，设 $g_{i,j}$ 表示从 $i$ 号点跳了 $2^j$ 的所有答案，初始化 $f_{i,0} = \min_{j \geq i}\{l_j\}$，$f_{1,0} = 0,g_{i,0} = i-f_{i,0}$。转移大概写一下 ：$$ \begin{aligned} f_{i,j} &= f_{f_{i,j-1},j-1}\\ g_{i,j} &= g_{i,j-1}+g_{f_{i,j-1},j-1}+2^{j-1}(f_{i,j-1}-f_{i,j}) \end{aligned} $$查询的时候跳一下，记一下已经跳了多少长度即可。最后有一些零散的边界要判掉。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; const int MAXM = 18; int n,l[MAXN]; // 处理[i,n]跳2^j步的最远位置 和这一块的答案 int f[MAXN][MAXM+1]; LL g[MAXN][MAXM+1]; int pw[MAXM+1]; inline LL calc(int l,int p){ if(l > p) return 0; if(l >= ::l[p]) return p-l; LL res = p-::l[p],now = 1;p = ::l[p]; ROF(i,MAXM,0){ if(f[p][i] < l) continue; res += g[p][i] + now*(p-f[p][i]); now += (1<<i); p = f[p][i]; } if(l <= p) res += (now+1)*(p-l); return res; } inline LL gcd(LL x,LL y){ return !y ? x : gcd(y,x%y); } int main(){ pw[0] = 1;FOR(i,1,MAXM) pw[i] = pw[i-1]<<1; scanf("%d",&n); FOR(i,2,n) scanf("%d",l+i),f[i][0] = l[i]; ROF(i,n-1,2) f[i][0] = std::min(f[i][0],f[i+1][0]),g[i][0] = i-f[i][0]; f[1][0] = 0; FOR(j,1,MAXM){ FOR(i,1,n){ f[i][j] = f[f[i][j-1]][j-1]; g[i][j] = g[i][j-1]+g[f[i][j-1]][j-1]+(f[i][j-1]-f[i][j])*pw[j-1]; } } int q;scanf("%d",&q); // DEBUG(calc(3,6)); // exit(0); while(q--){ int l,r,x;scanf("%d%d%d",&l,&r,&x); LL res = calc(l,x)-calc(r+1,x); LL g = gcd(r-l+1,res); printf("%lld/%lld\n",res/g,(r-l+1)/g); } return 0; }B. Minimax设 $f_{v,i}$ 表示 $v$ 号点权值为 $i$ 的概率，考虑如何合并两个子树 $x,y$：$$ f_{v,i} = f_{x,i}(p_v\sum_{j < i} f_{y,j}+(1-p_v)\sum_{j > i} f_{y,j}) + f_{y,i}(p_v\sum_{j < i} f_{x,j}+(1-p_v)\sum_{j > i} f_{x,j}) $$这种 dp 维护可以搞个线段树合并，每次在区间 $[l,r]$ 的时候考虑同时维护一个对 $x,y$ 分别应该打什么标记，类似cdq分治那样处理左边对右边的贡献，和右边对左边的贡献即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; const int ha = 998244353; const int inv = 796898467; int n; std::vector<int> G[MAXN]; int a[MAXN]; int rt[MAXN],sm[MAXN*25],tag[MAXN*25],lc[MAXN*25],rc[MAXN*25],tot; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } inline void cover(int x,int d){ // add(tag[x],d); tag[x] = 1ll*tag[x]*d%ha; sm[x] = 1ll*sm[x]*d%ha; } inline void pushdown(int x){ if(tag[x] != 1){ if(lc[x]) cover(lc[x],tag[x]); if(rc[x]) cover(rc[x],tag[x]); tag[x] = 1; } } int p,M; inline void update(int &x,int l,int r,int p){ x = ++tot;sm[x] = tag[x] = 1; if(l == r) return; int mid = (l + r) >> 1; if(p <= mid) update(lc[x],l,mid,p); else update(rc[x],mid+1,r,p); } inline int merge(int x,int y,int dx,int dy){ if(!x && !y) return 0; if(!x || !y){ cover(x|y,x?dx:dy); return x|y; } pushdown(x);pushdown(y); int lsx = sm[lc[x]],rsx = sm[rc[x]],lsy = sm[lc[y]],rsy = sm[rc[y]]; lc[x] = merge(lc[x],lc[y],(dx+1ll*(1+ha-p)%ha*rsy%ha)%ha,(dy+1ll*(1+ha-p)%ha*rsx%ha)%ha); rc[x] = merge(rc[x],rc[y],(dx+1ll*p*lsy%ha)%ha,(dy+1ll*p*lsx%ha)%ha); sm[x] = (sm[lc[x]]+sm[rc[x]])%ha; return x; } inline int query(int x,int l,int r,int p){ if(l == r) return sm[x]; int mid = (l + r) >> 1;pushdown(x); if(p <= mid) return query(lc[x],l,mid,p); return query(rc[x],mid+1,r,p); } inline void dfs(int v){ if(G[v].empty()){ update(rt[v],1,M,a[v]); return; } for(auto x:G[v]) dfs(x); if(G[v].size() == 1){ rt[v] = rt[G[v][0]]; return; } p = a[v]; rt[v] = merge(rt[G[v][0]],rt[G[v][1]],0,0); } int main(){ scanf("%d",&n); FOR(i,1,n){ int f;scanf("%d",&f); if(f) G[f].pb(i); } std::vector<int> S; FOR(i,1,n){ scanf("%d",a+i); if(G[i].empty()) S.pb(a[i]); else a[i] = 1ll*a[i]*inv%ha; } std::sort(all(S));M = S.size(); FOR(i,1,n) if(G[i].empty()) a[i] = std::lower_bound(all(S),a[i])-S.begin()+1; dfs(1); int ans = 0; FOR(i,1,M){ int t = query(1,1,M,i); // DEBUG(t); add(ans,1ll*i*S[i-1]%ha*t%ha*t%ha); } printf("%d\n",ans); return 0; }C. 随机算法考虑给定最终选出的一个独立集序列 $p_1,p_2,\ldots,p_m$，如何求有多大的概率生成的排列能得到这个序列。首先第一个数一定是 $p_1$，接下来和 $p_1$ 相连的点就可以乱放了，在剩下的点中第一个要放的一定是 $p_2$，然后和 $p_2$ 相连，还没有被放完的点也可以乱放了。所以我们处理出 $sz_S$ 表示集合 $S$ 放完之后，有多少个点可以乱放（包含集合 $S$ 内的点），并且这个只对独立集有定义。所以概率就是：$$ \prod_{i=1}^m \frac{1}{n-sz_{\cup_{j=1}^{i-1}\{p_j\}}} $$我们考虑对这个dp：设 $f_S$ 表示最终独立集序列为 $S$ ，所有 $|S|!$ 种方案的概率的和，答案显然就是每个最大独立集的 $f_S$。转移只需要枚举一个点，如果可以加入这个独立集就把对应的概率乘上就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 20; const int ha = 998244353; #define lowbit(x) ((x)&(-(x))) int n,m,e[MAXN]; int ee[(1<<MAXN)+3],sz[(1<<MAXN)+3];// 选了独立集 S 后 位置可以自由选择的位置的数量 int f[(1<<MAXN)+3];// S 内 任意顺序排列概率的和 bool vis[(1<<MAXN)+3]; int inv[MAXN+1]; inline void add(int &x,int y){ x += y-ha;x += (x>>31&ha); } int main(){ inv[1] = 1;FOR(i,2,MAXN) inv[i] = (ha-1ll*(ha/i)*inv[ha%i]%ha)%ha; scanf("%d%d",&n,&m); FOR(i,1,m){ int u,v;scanf("%d%d",&u,&v);--u;--v; e[u] |= (1<<v);e[v] |= (1<<u); } FOR(i,0,n-1) ee[1<<i] = e[i]; FOR(S,1,(1<<n)-1) ee[S] = ee[S-lowbit(S)]|ee[lowbit(S)]; int mx = 0; FOR(S,0,(1<<n)-1) if(!(ee[S]&S)) vis[S] = 1,mx = std::max(mx,(int)__builtin_popcount(S)); FOR(S,0,(1<<n)-1) sz[S] = __builtin_popcount(ee[S]|S); f[0] = 1; FOR(S,0,(1<<n)-1){ if(!f[S]) continue; if(!vis[S]) continue; FOR(i,0,n-1){ if((S>>i)&1) continue; if(!vis[S|(1<<i)]) continue; add(f[S|(1<<i)],1ll*f[S]*inv[n-sz[S]]%ha); } } int ans = 0; FOR(S,0,(1<<n)-1) if(vis[S] && __builtin_popcount(S) == mx) add(ans,f[S]); printf("%d\n",ans); return 0; }
A考虑枚举右端点，维护所有左端点的答案：只需要处理出 $pre_i$ 表示 $i$ 前面第一个和它一样的位置，每次让 $(pre_i,i]$ 加上 $w$，$(pre_{pre_i},pre_i]$ 减去 $w$ 即可。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } const int MAXN = 1e6 + 5; LL mx[MAXN<<2],tag[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void cover(int x,LL d){ mx[x] += d;tag[x] += d; } inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(l == L && r == R) return cover(x,d); int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); mx[x] = std::max(mx[lc],mx[rc]); } int n,m,c[MAXN],w[MAXN]; int lst[MAXN],pre[MAXN]; int main(){ read(n);read(m); FOR(i,1,n) read(c[i]); FOR(i,1,m) read(w[i]); LL ans = 0; FOR(i,1,n){ pre[i] = lst[c[i]];lst[c[i]] = i; int p1 = pre[i],p2 = pre[p1]; modify(1,1,n,p1+1,i,w[c[i]]); if(p1) modify(1,1,n,p2+1,p1,-w[c[i]]); ans = std::max(ans,mx[1]); } printf("%lld\n",ans); return 0; }B观察一下距离一个点直接距离为 $d$ 的图像是啥：倾斜不是很好处理，于是我们旋转 $45$ 度，现在直接距离定义变成了 $\min(x_i-x_j,y_i-y_j)$。然后我彩笔直接去扫描线，结果爆零了。。我们先考虑如何求出距离最小值：发现这只可能会在相邻的 $x$ 坐标或者 $y$ 坐标产生。我们先将直接距离为 $0$ 的点都并起来，然后将点按照 $x$ 坐标排序，相邻的权值判断一下如果在不同连通块就能对答案产生贡献。判断 $-1$ 只需要判断连通块大小是否是 $1$ 即可。那么现在如何去计算方案数呢？一个 $O(n^2)$ 的想法是数连通块之间有多少条边，去重后每条边贡献是连通块大小乘积。我考试的时候自闭了。。但是实际上发现这样的边只有 $O(n)$ 条：因为只会在按照某一维排序后相邻的点对中产生，所以去个重统计答案就行了。发现就是没去写距离的式子。。被降智了。。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n; struct Node{ int x,y,id; Node(int x=0,int y=0,int id=0) : x(x),y(y),id(id) {} }a[MAXN]; int f[MAXN],sz[MAXN]; inline int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); } inline void merge(int x,int y){ x = find(x);y = find(y); if(x == y) return; f[x] = y; } std::map<P,int> S; inline void addedge(int x,int y){ x = find(x);y = find(y); if(x == y) return; if(x > y) std::swap(x,y); S[MP(x,y)] = 1; } int main(){ scanf("%d",&n); FOR(i,1,n){ int x,y;scanf("%d%d",&x,&y); a[i] = Node(x+y,x-y,i);f[i] = i; } std::sort(a+1,a+n+1,[&](const Node &x,const Node &y){return x.x < y.x;}); for(int l = 1,r;l <= n;l = r+1){ r = l; while(r+1 <= n && a[r+1].x == a[r].x) ++r; FOR(i,l+1,r) merge(a[i].id,a[i-1].id); } std::sort(a+1,a+n+1,[&](const Node &x,const Node &y){return x.y < y.y;}); for(int l = 1,r;l <= n;l = r+1){ r = l; while(r+1 <= n && a[r+1].y == a[r].y) ++r; FOR(i,l+1,r) merge(a[i].id,a[i-1].id); } std::sort(a+1,a+n+1,[&](const Node &x,const Node &y){return x.x < y.x;}); int ans = 1e9; for(int l = 1,r;l <= n;l = r+1){ r = l; while(r+1 <= n && a[r+1].x == a[r].x) ++r; if(l-1 && find(a[l-1].id) != find(a[l].id)) ans = std::min(ans,a[l].x-a[l-1].x); } std::sort(a+1,a+n+1,[&](const Node &x,const Node &y){return x.y < y.y;}); for(int l = 1,r;l <= n;l = r+1){ r = l; while(r+1 <= n && a[r+1].y == a[r].y) ++r; if(l-1 && find(a[l-1].id) != find(a[l].id)) ans = std::min(ans,a[l].y-a[l-1].y); } if(ans == 1e9){ puts("-1"); return 0; } printf("%d\n",ans); std::sort(a+1,a+n+1,[&](const Node &x,const Node &y){return x.x < y.x;}); for(int l = 1,r;l <= n;l = r+1){ r = l; while(r+1 <= n && a[r+1].x == a[r].x) ++r; if(l-1 && a[l].x-a[l-1].x == ans) addedge(a[l-1].id,a[l].id); } std::sort(a+1,a+n+1,[&](const Node &x,const Node &y){return x.y < y.y;}); for(int l = 1,r;l <= n;l = r+1){ r = l; while(r+1 <= n && a[r+1].y == a[r].y) ++r; if(l-1 && a[l].y-a[l-1].y == ans) addedge(a[l-1].id,a[l].id); } FOR(i,1,n) sz[find(i)]++; LL res = 0; for(auto x:S) res += 1ll*sz[x.fi.fi]*sz[x.fi.se]; printf("%lld\n",res); return 0; }C可以发现这个操作本质是对 $1$ 的移动。移动问题可以考虑维护处什么时候移动了。我们考虑对于每个 $1$，求出它在哪些时间往前移动了一格，我们用一个 $01$ 串表示，第 $i$ 位是 $1$ 表示在时间 $i$ 这个 $1$ 往前移动了一格。如果能对于每个 $1$ 都求出来这个，就能求出每个 $1$ 最后到了哪里。我们一开始是一个全 $0$ 的串，考虑有了第 $i$ 个 $1$ 的串，如何转移到第 $i+1$ 个 $1$ 的串？如果下一个 $1$ 和这个 $1$ 是相邻的，可以发现如果在第 $i$ 个位置的第 $j$ 个时刻往前移动了一次，那么第 $i+1$ 的第 $j+1$ 个时刻也会往前移动，所以相当于是做一个右移操作，删除最后一个数字，并且在最前面加上一个 $0$。如果和下一个 $1$ 中间有 $c$ 个 $0$，那么相当于还可以将这个序列的前 $c$ 个 $0$ 变成 $1$，相当于可以抵消 $c$ 次上一个不动但是这一个动的情况。所以我们要支持如下操作：循环右移一位，将前 $c$ 个 $0$ 变成 $1$。于是我们考虑直接维护 $0$ 在序列中的位置，相当于要支持从后端删除，从前端插入，从前端删除，全局加，用双端队列+全局 tag 就可以解决了。如何算逆序对呢？我们考虑每次加入一个 $1$ ，它对哪些轮有贡献：显然这个 $1$ 会一直右移，移动到最后面出去就结束了，在它经过的所有时间答案都会 $+1$，根据这个在序列中的位置可以算出多少时间后它会被弹掉，就能确定他贡献的一段区间，差分即可。这种题就是我完全想不到吧。。如果发现本质是对谁的移动就可以考虑什么时候移动#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int ha = 998244353; const int MAXN = 5e6 + 5; LL ans; int b=1; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } inline void answer(int val){ ans ^= (1ll*val*b%ha); b = 233ll*b%ha; } char str[MAXN]; int n,T; std::vector<int> ps; bool vis[MAXN]; int cf[MAXN]; int main(){ scanf("%d",&T);scanf("%s",str+1);n = strlen(str+1); FOR(i,1,n) if(str[i] == '1') ps.pb(i); std::deque<int> q;int tag = 0;int las = 0; FOR(i,1,T) q.pb(T-i);int rem = (int)ps.size(); for(auto x:ps){ int cur = x-las-1;--rem; if(!q.empty() && q.back()+tag == 0) q.pop_back(); tag--; q.push_front(T-1-tag); while(!q.empty() && cur--){ int pos = T-(q.front()+tag); cf[pos]++;cf[pos+rem+1]--; q.pop_front(); } vis[x-(T-(int)q.size())] = 1; // if(x == 4){ // for(auto y:q) DEBUG(y+tag); // } las = x; } FOR(i,1,n) putchar(vis[i]+'0');puts(""); FOR(i,1,T) add(cf[i],cf[i-1]); int sm = 0; ROF(i,n,1){ if(str[i] == '0') sm++; else add(cf[0],sm); } FOR(i,1,T) add(cf[i],cf[i-1]); FOR(i,0,T) answer(cf[i]); printf("%lld\n",ans); return 0; }
A. 旅游设连通块的大小为 $sz_i$，要求计算 $\sum sz_i(sz_i-1)$。离线，排序，并查集维护。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; struct Edge{ int u,v,w; inline bool operator < (const Edge &t) const { return w < t.w; } }e[MAXN]; int n,m,q; int f[MAXN],sz[MAXN]; inline int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); } LL now = 0; inline LL C(int n){ return 1ll*n*(n-1); } inline void merge(int x,int y){ x = find(x);y = find(y); if(x == y) return; now -= C(sz[x])+C(sz[y]); sz[x] += sz[y];f[y] = x; now += C(sz[x]); } LL ans[MAXN]; P qry[MAXN]; inline void Solve(){ scanf("%d%d%d",&n,&m,&q); now = 0;FOR(i,1,n) f[i] = i,sz[i] = 1; FOR(i,1,m) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); std::sort(e+1,e+m+1); FOR(i,1,q){ scanf("%d",&qry[i].fi);qry[i].se = i; } std::sort(qry+1,qry+q+1); int tp = 1; FOR(i,1,q){ while(tp <= m && e[tp].w <= qry[i].fi) merge(e[tp].u,e[tp].v),++tp; ans[qry[i].se] = now; } FOR(i,1,q) printf("%lld\n",ans[i]); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }B. Tom显然一定是一个子树放早餐，另一个子树放晚餐。找到这样的子树后分别从下往上放即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; int n,a,b; std::vector<int> G[MAXN]; int sz[MAXN],fa[MAXN]; int ps = 0; inline void dfs(int v,int fa=0){ sz[v] = 1;::fa[v] = fa; for(auto x:G[v]){ if(x == fa) continue; dfs(x,v);sz[v] += sz[x]; } if(sz[v] == a) ps = v; else if(sz[v] == b) ps = -v; } std::vector<int> node[MAXN]; inline void dfs2(int v,int d=1,int fa=0){ node[d].pb(v); for(auto x:G[v]){ if(x == fa) continue; dfs2(x,d+1,v); } } int ans[MAXN]; int main(){ scanf("%d%d%d",&n,&a,&b); FOR(i,2,n){ int u,v;scanf("%d%d",&u,&v); G[u].pb(v);G[v].pb(u); } dfs(1); dfs2(std::abs(ps),1,fa[std::abs(ps)]); int m = 1;while(!node[m+1].empty()) ++m; int t = 1; ROF(i,m,1){ for(auto x:node[i]) ans[x] = (ps>0?1:-1)*t,++t; node[i].clear(); } dfs2(fa[std::abs(ps)],1,std::abs(ps)); t = m = 1;while(!node[m+1].empty()) ++m; ROF(i,m,1){ for(auto x:node[i]) ans[x] = (ps>0?-1:1)*t,++t; node[i].clear(); } FOR(i,1,n) printf("%d\n",ans[i]); return 0; }C. Jerry只有减法后面会加括号，并且可以发现加括号后可以通过里面再加一层让括号内除了一开始一段的 + 之外的数字贡献都为正。维护前缀最小值 直接 dp 即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n; char opt[MAXN]; int a[MAXN]; // 括号只可能嵌套一层 // f[i] = f[j-1] -sm[i]+sm[j]-a[j] (opt[j]=='-') LL f[MAXN],sm[MAXN],pre[MAXN]; inline void Solve(){ scanf("%d",&n); scanf("%d",a+1); FOR(i,2,n){ char str[23]; scanf("%s",str); opt[i] = str[0]; scanf("%d",a+i); } sm[1] = a[1];FOR(i,2,n) sm[i] = sm[i-1]+a[i]; pre[n] = a[n]; ROF(i,n-1,1){ if(opt[i+1] == '-') pre[i] = a[i]; else pre[i] = pre[i+1]+a[i]; } // f[i] = f[j-1]-2*pre[j]+sm[i]-sm[j-1] (opt[j]=='-') LL mx = -1e18;f[1] = a[1]; FOR(i,2,n){ f[i] = f[i-1]+(opt[i]=='-'?-1:1)*a[i]; if(opt[i] == '-') mx = std::max(mx,f[i-1]-2*pre[i]-sm[i-1]); f[i] = std::max(f[i],mx+sm[i]); } printf("%lld\n",f[n]); } // -(a+b-(c+d)-(e+f)) // -a-b+c+d+e+f //前面最连续的一段+不能取 int main(){ freopen("jerry.in","r",stdin); freopen("jerry.out","w",stdout); int T;scanf("%d",&T); while(T--) Solve(); return 0; } D. Speike首先发现边界是可以走的并且矩形之间无交，所以我们可以推出只有边界上四个点有用。首先贪心地想，路径上一定不会往左走，所以我们只需要关注 $y$ 坐标上的走动即可。考虑走最短路的过程：$x$ 轴如果和矩阵无交，那么就可以直接走过去，否则考虑最后一次走到的一定是最后一个相交的矩形的左边界，然后绕过去。这种题要考虑反过来，从最后一个去观察，发现从终点开始每次都要从横坐标上距离当前点最近的，覆盖了当前 $y$ 坐标的矩形转移过来。所以这个形式可以倒过来 dp：只从前面最后一个覆盖 $y$ 坐标的地方转移即可（可以用线段树或者 set 维护）这种观察走路性质然后倒过来挺妙的。。不太会。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; int n,xt; struct Node{ int x1,y1,x2,y2; Node(int x1=0,int y1=0,int x2=0,int y2=0) : x1(x1),y1(y1),x2(x2),y2(y2) {} inline bool operator < (const Node &t) const { return x1 == t.x1 ? x2 < t.x2 : x1 < t.x1; } }a[MAXN]; int mx[MAXN<<2],tag[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void cover(int x,int d){ mx[x] = d;tag[x] = d; } inline void pushdown(int x){ if(tag[x] != -1){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = -1; } } inline void build(int x,int l,int r){ tag[x] = -1;mx[x] = 1; if(l == r) return; int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); } inline void modify(int x,int l,int r,int L,int R,int d){ if(l == L && r == R) return cover(x,d); int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); mx[x] = std::max(mx[lc],mx[rc]); } inline int query(int x,int l,int r,int p){ if(l == r) return mx[x]; int mid = (l + r) >> 1;pushdown(x); if(p <= mid) return query(lc,l,mid,p); else return query(rc,mid+1,r,p); } std::vector<int> S; LL f[MAXN][2]; int main(){ #ifndef RainAir freopen("speike.in","r",stdin); freopen("speike.out","w",stdout); #endif scanf("%d%d",&n,&xt);S.pb(0); FOR(i,1,n){ scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); if(a[i].x1 > a[i].x2) std::swap(a[i].x1,a[i].x2); if(a[i].y1 > a[i].y2) std::swap(a[i].y1,a[i].y2); S.pb(a[i].y1);S.pb(a[i].y2); } a[++n] = Node(0,0,0,0);a[++n] = Node(xt,0,xt,0); std::sort(a+1,a+n+1); std::sort(all(S)); FOR(i,1,n) a[i].y1 = std::lower_bound(all(S),a[i].y1)-S.begin()+1, a[i].y2 = std::lower_bound(all(S),a[i].y2)-S.begin()+1; int M = S.size(); build(1,1,M); assert(a[1].x1 == 0 && a[1].x2 == 0); FOR(i,2,n){ int p = query(1,1,M,a[i].y1); f[i][0] = std::min(f[p][0]+std::abs(S[a[i].y1-1]-S[a[p].y1-1]),f[p][1]+std::abs(S[a[i].y1-1]-S[a[p].y2-1])); p = query(1,1,M,a[i].y2); f[i][1] = std::min(f[p][0]+std::abs(S[a[i].y2-1]-S[a[p].y1-1]),f[p][1]+std::abs(S[a[i].y2-1]-S[a[p].y2-1])); modify(1,1,M,a[i].y1,a[i].y2,i); } printf("%lld\n",f[n][0]+xt); return 0; }
A设第 $i$ 个女生的限制为 $mx_i$，意思是存在一个男生给她 $mx_i$ 的礼物。设第 $i$ 个男生的限制为 $mn_i$，意思是要给所有女生 $mn_i$ 的礼物。设男女生都根据限制大小从小到大排序，首先如果 $mx_n > b_1$ 那么就无解（所有女生至少收到了 $mx_n$ 的礼物，但是第一个女生说她没收到，矛盾了）对于每个女生，我们都要钦定好一个男生送给他礼物，我们肯定要找一个限制最宽的男生给女生送满足她限制的礼物（也就是 $n$），要注意如果 $mx_n < mn_1$ 需要留一个位置来送 $mx_n$ 的礼物来满足限制，这时候会贪心的让男 $n$ 送给女 $1$ 价值 $mx_n$ 的礼物，再让男 $n-1$ 送女 $1$ 价值 $mn_1$ 的礼物。B这题我只会找规律。为了方便找规律，先将 $k$ 的定义改为最大的 $k$ 满足 $[1 \ldots k]$ 的串要么没出现，要么出现 $\geq 2$ 次。（也就是 $k+1$ 时题目定义的实际答案）观察这样的串：10101010101010 100100100100100100 10001000100010001000 1000010000100001000010000设它们的一个循环节长度为 $d$，我们发现长度在 $\leq 3d-1$ 时答案一直是 $\leq d$，之后每增加一个长度答案就会 $+1$，所以可以得到一个式子：$3d-1+(k-d-1) = n \Rightarrow d = \frac{n-k+2}{2}$，而在题目的限制下又一定整除，就可以构造出来了。感觉完全看运气。。C相当于限定了一个数和一段区间的大小关系，线段树优化建图+拓扑排序即可。D也算是半个构造题？先考虑没有规定拐点顺序怎么做：这是个经典问题。我们一开始选取最左边的点，每次走的点只要保证所有的点都在两点连线的一边就好了。明白了这个就会有拐点顺序了：因为你选的“一边”可以是左边也可以是右边，根据题意调整即可。如果是 L 就选择最右边的点，R 就选择最左边的点。E神仙交互题。。这个询问的本质是将每个点 $i$ 距离自己 $\leq d_i$ 的点都染黑（不包含自己）然后输出来哪些点被染黑了。首先我们选取 $1$ 号点为根，我们考虑过程分两步走：求出每个点的深度一个 naive 的做法是询问出所有距离 $\leq i$ 的点，做个类似差分的东西就好了。这个询问能传入长度为 $n$ 的数组，我们只用一个未免太奢侈了，对于这种问题需要考虑如何合并询问。我们如果维护处当前还未确定的深度区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$，对于每个区间我们只需要询问 $mid-1,mid$ 就可以得出距离是 $mid$ 的有哪些了。如果所有询问直接扔进去一块做会怎么样？那么很有可能 $mid-1$ 会超出边界，影响到上一个的选取，所以我们考虑排序后奇偶分组，这样就不会出现边界重复问题了，我们花了 $4$ 次操作能将问题规模减小一般，这一部分操作是 $4\lceil \log_2n \rceil$。求出每个点的父亲另一个 naive 的做法是对于一个深度为 $d$ 的点 $v$，我们枚举所有深度为 $d-1$ 的点 $u$，查询 $u$ 到距离为 $1$ 的点的集合，判断是否在里面。我们先想想能不能优化到对每一层能一起判断：考虑如果选择了多个点其实相当于是能确定某个点的父亲是否在这个集合内，于是我们考虑逐位确定：假设现在考虑所有点父节点编号二进制位第 $i$ 位是啥，我们把所有 $d-1$ 层二进制第 $i$ 位是 $1$ 的扔进去查询就好了。发现询问距离为 $1$ 的询问会影响上面和下面一层，于是考虑按层 $\bmod 3$ 分类，就不会有干扰的问题了。F你觉得我会神奇 $O(\frac{n^3}{\log n})$的 $3500$ 计数题？大概省选的时候会补。现在已经补了。这种没见过的题就是要找性质然后对性质dp，具体过程是（判定性问题 $\to $ 状态和转移 $\to $ 优化）判定性问题如果判定一个串是否是 $p$ 密度的呢？我们发现如果一个串是 $p$ 密度的，首先 $1 \ldots c$ 都要出现了，然后我们删掉 $1\ldots c$ 这一段的所有的数，剩下的应该是一个 $p-1$ 密度的串。设计状态有了这个东西就可以 dp 了：考虑设 $f_{i,j}$ 表示强制最后一次选的是 $i$，$j$ 密度串的个数，转移的时候只需要预处理 $g_{l,r}$ 表示区间 $[l,r]$ 的子序列数量，满足 $1 \ldots c$ 只出现了一次，并且选择 $a_r$ 后才满足 $1 \ldots c$ 都出现了一次（否则会算重）。这个可以先枚举右端点，然后扫左端点，维护一个出现次数的桶，相当于限制 $a_r$ 只能选一次，其他的只要至少选一个就行。时间复杂度 $O(n^3)$优化首先发现一个性质：$p$ 密度串的长度至少是 $cp$ 的。考虑判定过程每次至少删除 $c$ 个字符可得。那么发现 $f_{i,j}$ 中，$j \leq \frac{i}{c}$，复杂度降为了 $O(\frac{n^3}{c})$。但是还是不太行。我们考虑复杂度瓶颈主要在枚举下一个段是什么，但是枚举下一个段是为了防止算重的，如果不想算重就只能记录下当前还没填完的段已经选过哪些数了。于是考虑设 $f_{i,j,S}$ 表示考虑了前 $i$ 个数，最后一次选的是 $j$，当前这一个还没完整的段已经选过的数字集合是 $S$，我们只要在某次转移 $S=U$ 的时候直接将其强制转移到 $S'=0$，就和上面的方法是等价的了，这样的复杂度是 $O(\frac{n^2 2^c}{c})$，当 $c=\log_2 n$ 的时候两式的最小值取到最大值 $O(\frac{n^3}{\log_2 n})$ 。所以就当 $c \leq \log_2n$ 的时候用方法二（状压），否则用方法一，总复杂度 $O(\frac{n^3}{\log_2 n})$（代码里是反着写的）顺便一提时限 6s 我的代码是 5990ms 飘过的。。一些卡常技巧比如把能预先算的都放在最外层算有奇效。#include <bits/stdc++.h> #define fi first #define se second #define db double #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3000+5; const int ha = 998244353; int n,c,a[MAXN]; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } int ans[MAXN]; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } namespace Subtask1{ // O(n^2/c * 2^c) int f[2][MAXN][(1<<10)+3],now; // 考虑了前i个数 凑了j个[1..c],当前段哪些还没凑 inline void Solve(){ int U = (1<<c)-1; f[now=0][0][0] = 1;FOR(i,1,n) --a[i]; FOR(i,1,n){ FOR(j,0,(i-1)/c) FOR(S,0,U-1) f[now^1][j][S] = f[now][j][S]; int t = (1<<a[i]); FOR(j,0,(i-1)/c){ FOR(S,0,U-1){ if(!f[now][j][S]) continue; int nS = S|t,nj = j; if(nS == U) nS = 0,nj = j+1; add(f[now^1][nj][nS],f[now][j][S]); } } now ^= 1; } FOR(S,0,(1<<c)-2) FOR(j,0,n/c) add(ans[j],f[now][j][S]); add(ans[0],ha-1);// 空 } } namespace Subtask2{ int f[MAXN][MAXN],g[MAXN][MAXN]; /* f[i][j]: 最后一次选的是i,搞出了j个段 转移需要预处理 g[i][j]: 最后一次选的是j,选出了一段 计算g只需要得到出现次数就行了 */ int cnt[MAXN],now,sm; int pw[MAXN],inv[MAXN]; inline void reset(){ FOR(i,1,c) cnt[i] = 0;now = 0;sm = 1; } inline void add(int x){ if(!cnt[x]){ ++cnt[x];++now; return; } sm = 1ll*sm*inv[cnt[x]]%ha; ++cnt[x]; sm = 1ll*sm*(pw[cnt[x]]+ha-1)%ha; } inline void Solve(){ pw[0] = 1;FOR(i,1,MAXN-1) pw[i] = 2ll*pw[i-1]%ha; FOR(i,0,MAXN-1) inv[i] = qpow((pw[i]+ha-1)%ha); FOR(r,1,n){ reset(); ROF(l,r,1){ add(a[l]); if(now != c) g[l][r] = 0; else g[l][r] = 1ll*sm*inv[cnt[a[r]]]%ha; } } f[0][0] = 1; FOR(i,0,n-1){ FOR(j,0,i/c){ if(!f[i][j]) continue; FOR(k,i+c,n){ ::add(f[k][j+1],1ll*f[i][j]*g[i+1][k]%ha); } } } // DEBUG(f[2][2]); // exit(0); FOR(j,0,n/c){ reset(); ROF(i,n,0){ if(!f[i][j]){ add(a[i]);continue; } int t=0; t = pw[n-i]; if(now == c) ::add(t,ha-sm); ::add(ans[j],1ll*f[i][j]*t%ha); add(a[i]); } } ::add(ans[0],ha-1); } } int main(){ scanf("%d%d",&n,&c); FOR(i,1,n) scanf("%d",a+i); if(c <= 10) Subtask1::Solve(); else Subtask2::Solve(); FOR(i,0,n) printf("%d ",ans[i]);puts(""); return 0; }
这场 C sb了敲错一个字符爆零了。。最后发现 D 也很简单。策略以后还是要先做掉简单题，然后难题调不出来就换题，先大体浏览一下题目再做（说不定后面有我擅长的题呢）A我们按照 $x$ 坐标排序，设 $y$ 坐标处于中间位置的点是 $a$，另外的点是 $b,c$，那么可以先连两条过 $b,c$ 垂直于 $a$ 所在的水平线上的两条线，然后连一下 $a$ 的水平线即可。B注意到可以设置为 $0$ 边，并且直径的两个端点一定是叶子，设叶子有 $l$ 个，可以给每个叶子上面的边分配 $\frac{s}{l}$，答案是 $2\frac{s}{l}$。C类似数位 dp 枚举卡上界/下界分别卡到哪里，能得到一堆限制区间，现在变成了将区间和区间内的点配对的问题，可以按照左端点排序每次取右端点最小的区间配对。但是我把 $n$ 和 $k$ 写反了。。。要不然早就过了D发现一个点前后是独立的，分别考虑。考虑它的前缀：这个点能胜利要么前面所有的点都和它平局或者被它打败，要么有能打败它的和能被它打败的。证明考虑每一对能打败它的和能被它打败的点即可。统计答案的时候我们枚举每种动作，如果一个点合法，当且仅当它的前缀/后缀不会出现仅存在能打败它的动作，但是发现这是若干个区间的交，不是很好做，于是我们容斥后去求不合法的区间的并，用 set 维护一下每种颜色编号最大和最小的位置，树状数组维护一下数字的排名就行了。E先思考有多少个好的矩阵：这个矩阵要求这一行是上一行的错排，设错排为 $h(n)$，那么数量就是 $n!h(n)^{n-1}$。字典序问题肯定是枚举到哪个位置失配，由于第一行没有错排限制所有可以先特判掉。接下来考虑剩下的一般情况：假设我们考虑到 $(i,j)$ 失配，首先下面的 $n-j$ 行方案都是错排，也就是 $h(n)^{n-j}$，现在只需要考虑这一行：先考虑暴力枚举 $a_{i,j}$ 是啥，然后发现这种问题相当于钦定了若干数的错排问题，而这种问题的答案只和长度与有效的限制有关（有效的限制指这个数之前都没被用过，也就是不属于可以随便放的状态）。这里有一个容斥式子可以做，但是需要 NTT。发现所有的方案乘上一个置换后是等价的，于是考虑设计 dp $f_{i,j}$ 表示长度为 $i$ 有 $j$ 条限制的方案数。那么有转移 $f_{i,j} = f_{i,j-1}-f_{i-1,j-1}$（相当于用全部的情况减去违反最后一个限制的情况）如果暴力枚举 $a_{i,j}$ 是啥能得到一个 $O(n^3)$ 的做法过不去，但是发现各种 $a_{i,j}$ 的不同之处仅在与它是不是属于一个有效的限制，所以只需要数一下可选的数有多少个是属于有效的限制并且 $< x$，多少不是并且 $<x$ ，可以用桶+树状数组维护。注意要特判一下这个位置和上一行不能相等即可。一类求排名的问题也就是求字典序比它小个数，不要被骗了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2000+5; const int ha = 998244353; int f[MAXN][MAXN]; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } // 长度为i的排列 有j个位置限制 inline void prework(){ f[0][0] = 0; f[1][0] = 1;f[1][1] = 0; FOR(i,2,MAXN-1){ f[i][0] = 1ll*f[i-1][0]*i%ha; FOR(j,1,i){ f[i][j] = f[i][j-1]; add(f[i][j],ha-f[i-1][j-1]); } } } int n,a[MAXN][MAXN]; int cnt[MAXN],now; struct BIT{ #define lowbit(x) ((x)&(-(x))) int tree[MAXN]; inline void add(int pos,int x){ while(pos < MAXN){ tree[pos] += x; pos += lowbit(pos); } } inline int query(int pos){ int res = 0;if(!pos) return 0; while(pos){ res += tree[pos]; pos -= lowbit(pos); } return res; } }bit1,bit2; bool vis[MAXN]; // 1=无限制 // 2=有限制 inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } inline void ins(int x,int d){ ++cnt[x];if(cnt[x] == 2) ++now; if(d){ if(cnt[x] == 1) bit1.add(x,1); else bit2.add(x,1); } else{ if(cnt[x] == 2) bit1.add(x,-1),bit2.add(x,1); } } int main(){ prework(); scanf("%d",&n);FOR(i,1,n) FOR(j,1,n) scanf("%d",&a[i][j]); // TODO: 第一行特判 int ans = 0; ROF(i,n,1){ // 第一行没有错排限制! int c = bit1.query(a[1][i]); if(c) add(ans,1ll*c*f[n-i][0]%ha); bit1.add(a[1][i],1); } // DEBUG(ans); ans = 1ll*ans*qpow(f[n][n],n-1)%ha; FOR(i,2,n){ CLR(cnt,0);CLR(vis,0);CLR(bit1.tree,0);CLR(bit2.tree,0);now = 0; int gx = 0; ROF(j,n,1){ /* 首先要计算出前i个中有多少数字是相同的k,那么后面的数有j-k个没有限制 然后枚举这个位置填什么 情况只有填都有的和没有的 */ // 现在需要知道 当前的位置 有多少个数字 有限制/无限制 ins(a[i-1][j],0);ins(a[i][j],1); int t1 = bit1.query(a[i][j]-1),t2 = bit2.query(a[i][j]-1),sz = n-j+1; if(cnt[a[i-1][j]] == 2 && a[i-1][j] < a[i][j]) t2--; // if(j == 2)DEBUG(sz-1),DEBUG(now); add(gx,1ll*t1*f[sz-1][now-(cnt[a[i-1][j]]==2)]%ha); add(gx,1ll*t2*f[sz-1][now-1-(cnt[a[i-1][j]]==2)]%ha); } // if(i == 2) exit(0); gx = 1ll*gx*qpow(f[n][n],n-i)%ha; add(ans,gx); } printf("%d\n",ans); return 0; } /* 每一行是以上一行为基的错排 设错排为 h(n) 有多少个好矩阵? h(n)^n 枚举第i行开始不同 后面都是错排方案数 然后枚举 (i,j) 格子不同,如果能枚举这个格子填的是啥,相当于就是一个固定数字的错排问题了 */F这个东西显然是不能直接算的，但是我们发现设 $f(x)$ 表示 $x$ 时刻覆盖面积大小还是可以算的，考虑转化到这上面。首先有一个经典的考虑贡献的转化：设 $t_i$ 表示 $i$ 点被燃烧的时间，那么 $\sum t_i = \sum (t-t_i) = tf(t)-\sum_{i=0}^{t-1}f(i)$。所以现在的目标是如何求 $\sum_{i=0}^{t-1}f(i)$。剩下的我也想不到。。对于 $t$ 这么大肯定要考虑插值之类的，首先容斥原理变成求交，我们考虑两个点的交的情况：首先在没有触碰的时候一直是 $0$，之后就是一个二次函数。所以相当于在每两个矩形开始相碰的时候就要加上一个二次函数，也就是在这里分段，整体形状是分段二次函数。而将分段二次函数段内线性组合不会影响函数的形态，所以整个 $f(i)$ 就是分段二次函数，段都分在某个时间点两个矩形开始相交的时候。然后对每一段插个值就行了。这里不得不提一下线段树求矩形并或者离散化维护东西的细节：必须要让区间是左闭右开/左开右闭区间才不会算重，可以好好看看代码。。写了一晚上#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int ha = 998244353; const int inv2 = 499122177; const int inv6 = 166374059; const int MAXN = 300+5; std::vector<LL> Sx,Sy; namespace DS{ int sm[MAXN<<2],tag[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void modify(int x,int l,int r,int L,int R,int d){ // int len = Sy[r-1]-(l==1?Sy[0]:Sy[l-2]); int len = Sy[r]-Sy[l-1]; // if(l == 1 && r == 2) DEBUG(Sy[r]),DEBUG(Sy[l-1]); // DEBUG(l);DEBUG(r);DEBUG(len); if(l == L && r == R){ tag[x] += d; sm[x] = tag[x] ? len : (l==r?0:(sm[lc]+sm[rc])%ha); return; } int mid = (l + r) >> 1; if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); sm[x] = tag[x]?len:(l==r?0:(sm[lc]+sm[rc])%ha); } } using DS::modify; int x[MAXN],y[MAXN],n; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } struct Node{ int x1,y1,x2,y2;//(x1,y1) <= (x2,y2) Node(int x1=0,int y1=0,int x2=0,int y2=0) : x1(x1),y1(y1),x2(x2),y2(y2) {} }a[MAXN]; std::vector<std::pair<P,int> > G[MAXN]; inline int f(int k){ Sx.clear();Sy.clear(); FOR(i,1,n){ a[i] = Node(x[i]-k,y[i]-k,x[i]+k+1,y[i]+k+1); Sx.pb(x[i]-k);Sy.pb(y[i]-k);Sx.pb(x[i]+k+1);Sy.pb(y[i]+k+1); // DEBUG(x[i]+k+1);DEBUG(y[i]+k+1); } std::sort(all(Sx));Sx.erase(std::unique(all(Sx)),Sx.end()); std::sort(all(Sy));Sy.erase(std::unique(all(Sy)),Sy.end()); // Sx.pb(Sx[0]-1);Sy.pb(Sy[0]-1); // std::sort(all(Sx));std::sort(all(Sy)); int m = Sx.size(),M = Sy.size(); FOR(i,0,m+1) G[i].clear(); FOR(i,1,n){ a[i].x1 = std::lower_bound(all(Sx),a[i].x1)-Sx.begin()+1; a[i].x2 = std::lower_bound(all(Sx),a[i].x2)-Sx.begin()+1; a[i].y1 = std::lower_bound(all(Sy),a[i].y1)-Sy.begin()+1; a[i].y2 = std::lower_bound(all(Sy),a[i].y2)-Sy.begin()+1; // printf("%d %d %d %d\n",a[i].x1,a[i].y1,a[i].x2,a[i].y2); G[a[i].x1].pb(MP(MP(a[i].y1,a[i].y2),1)); G[a[i].x2].pb(MP(MP(a[i].y1,a[i].y2),-1)); } Sy.pb(Sy.back()); // Sy.pb(Sy[0]-1);std::sort(all(Sy)); // exit(0); CLR(DS::sm,0);CLR(DS::tag,0); int ans = 0; FOR(i,1,m){ int t = (Sx[i-1]-Sx[std::max(i-2,0)])%ha; // DEBUG(t); // DEBUG(DS::sm[1]); add(ans,1ll*t*DS::sm[1]%ha); for(auto x:G[i]) modify(1,1,M,x.fi.fi,x.fi.se-1,x.se);//,DEBUG(x.fi.fi),DEBUG(x.fi.se-1),DEBUG(x.se); } return ans; } inline int sm2(int n){ int res = 0;if(n < 0) return 0; if(n <= 5){ FOR(i,1,n) add(res,i*i); } else{ res = 1ll*n*(n+1)%ha*(2ll*n+1)%ha*inv6%ha; } return res; } inline int sm(int n){ int res = 0;if(n < 0) return 0; if(n <= 5){ FOR(i,1,n) add(res,i); } else{ res = 1ll*n*(n+1)%ha*inv2%ha; } return res; } inline int sm(int l,int r){ return (sm(r)+ha-sm(l-1))%ha; } inline int sm2(int l,int r){ return (sm2(r)+ha-sm2(l-1))%ha; } int main(){ int t;scanf("%d%d",&n,&t); // t = 100000; FOR(i,1,n) scanf("%d%d",x+i,y+i); std::vector<int> part;part.pb(0);part.pb(t); FOR(i,1,n){ FOR(j,i+1,n){ int d = std::max(std::abs(x[i]-x[j]),std::abs(y[i]-y[j])); d = (d+1)/2; if(d >= t) continue; part.pb(d); // if(d-1 > 0) part.pb(d-1); // if(d+1 < t) part.pb(d+1); } } // DEBUG(f(t)); // exit(0); // DEBUG(1ll*(400000000ll+1)*(400000000+1)%ha); // exit(0); // int ttt = 0; // FOR(i,0,t-1) add(ttt,f(i)); // DEBUG(ttt); std::sort(all(part));part.erase(std::unique(all(part)),part.end()); int ans = 0; FOR(i,1,(int)part.size()-1){ int l = part[i-1],r = part[i]-1; // DEBUG(l);DEBUG(r); if(r-l+1 <= 3){ FOR(k,l,r) add(ans,f(k)); continue; } int x[3],y[3]; FOR(j,0,2) y[j] = f(x[j]=l+j); int a = 1ll*y[0]*inv2%ha; add(a,ha-y[1]);add(a,1ll*y[2]*inv2%ha); int b = 1ll*y[0]*inv2%ha*(x[1]+x[2])%ha; add(b,ha-1ll*y[1]*((x[0]+x[2])%ha)%ha); add(b,1ll*y[2]*inv2%ha*(x[1]+x[0])%ha); b = ha-b; int c = 1ll*x[1]*x[2]%ha*y[0]%ha*inv2%ha; add(c,ha-1ll*x[0]*x[2]%ha*y[1]%ha); add(c,1ll*x[0]*x[1]%ha*y[2]%ha*inv2%ha); // DEBUG(a);DEBUG(b);DEBUG(c); // DEBUG(sm(l,r)); // int tt = 0; // FOR(i,l,r) add(tt,i); // DEBUG(tt); add(ans,1ll*sm2(l,r)*a%ha); // DEBUG(sm2(l,r)); add(ans,1ll*sm(l,r)*b%ha); add(ans,1ll*(r-l+1)*c%ha); } // DEBUG(ans); // DEBUG(ans); // int _ = 400000000ll*400000000%ha; add(ans,ha-1ll*t*f(t)%ha); ans = (ha-ans)%ha; printf("%d\n",ans); return 0; } /* 设 f(i) 表示 i 时间有多少个格子着火了 答案就是 tf(t)-\sum_{i=0}^{t-1}f(i) 单次询问 f(i) 是可以求矩阵面积并的,但是你不能询问1e8次 考虑用容斥原理将矩形面积并变成交 观察一个子集 发现只有在某两个矩形由不交变成相交的时候才会分段 所以只有 n^2 段 插值 每一段需要做3/4次矩形面积并 矩形面积并就是离散化后排序 支持区间加删线段 全局查询 修改到对应线段即可 */
A发现操作相当于花费 $x$ 消掉一个 $0$ 的连续段，或者是花费 $y$ 将两个连续段拼起来，显然如果使用了拼接操作就会拼到只剩一个，所以直接判断即可。B打表发现在 $n$ 较大的时候是个等差数列，小范围暴力即可。一个比较有理有据的做法是首先考虑我们先将集合转化为 $\{0,4,9,49\}$ 考虑，然后我们为了保证不重，必须限制 $4$ 的个数 $\leq 8$ 个，并且如果取了 $4$，那么为了去重也只能取 $\leq 4$ 个 $9$，没有取 $4$ 就可以取 $\leq \gcd(49,9)=9$ 个。剩下的用 $0$ 和 $49$ 填充即可。通过整体平移让某一个出现 $0$ 是很不错的套路，可以直接少考虑一个维度。C必然是容斥原理。我们去枚举多少行多少列是相同颜色的，设 $f(i,j)$ 表示 $i$ 行 $j$ 列每行每列相同颜色的方案数，答案就是：$$ \sum_{i=0}^n \sum_{j=0}^n [i+j \neq 0](-1)^{i+j+1}\binom n i\binom n j f(i,j) $$其中：$$ \begin{aligned} f(i,j) = \begin{cases} 3^{n(n-j)} \times 3^j ,&i=0\\ 3^{(n-i)n} \times 3^i, &j=0\\ 3^{(n-i)(n-j)} \times 3,& \text{otherwise} \end{cases} \end{aligned} $$接下来考虑如何优化：首先 $i=0$ 和 $j=0$ 的情况比较平凡，我们只需要考虑算：$$ -3\sum_{i=1}^n (-1)^i\binom n i\sum_{j=1}^n (-1)^{j}\binom n j 3^{(n-i)(n-j)} $$对后面用二项式定理，后面的式子等价于 $(3^{n-i}-1)^n-3^{(n-i)n}$，就可以 $O(n \log n)$ 计算了。同时算多个 $n$ 的答案感觉可以卷积。。不错以后出了。D首先要直观理解一下在图上怎么走路的：你从 $(u,v)$ 可以走到 $(u,w)$满足树 $2$ 上有边 $(v,w)$，树 $1$ 同理。主要是要观察到一个性质：两棵树起点确定，长度为 $x,y$ 的环能组合出长度为 $x+y$ 的环，方案是 $\binom {x+y} x$。所以我们对树分开处理，只需要对于每棵树处理出长度 $=i$ 的环的个数就行了（在环上每个点都要贡献一次），如果我们现在求 $1$ 号点的环个数，可以将这个点设为根，然后设 $f_{i,j}$ 表示从 $i$ 开始的长度为 $j$ 的环的数量。考虑写出生成函数 $F_i = \sum_{j} f_{i,j}x^j$，考虑如何用生成函数的形式刻画转移：首先我们可以算出 $G_i$ 表示经过 $i$ 一次的情况，显然有 $G_i = x^2\sum{v \in son_i} F_{v}$，$x^2$ 是因为要走回来，那么就可以得到 $F_i = \sum_{j \geq 0} G_i^j = \frac{1}{1-G_i}$，所以多项式求逆就可以求出来了。但是因为要求出所有点的答案，所以我们要考虑换根：实际上就是去掉/加入一些子树，先修改 $G$ 再修改 $F$ 即可。这样复杂度是 $O(nk \log k)$ 的，但是由于 $k$ 很小并且 NTT 常数巨大跑不过 $O(nk^2)$ 的做法。官方题解给的做法是用那个 dp 套在点分治上，也是很妙的，对这种类似路径条数和连通块的问题我们可以考虑点分治每次只 dp 分治区域内所有的点。E先考虑如果全局询问怎么做：因为是排列，限制可以拆成 $r-l = mx-mn$，并且我们发现一定有 $r-l \leq mx-mn$，也就是 $r \leq mx-mn+l$，所以我们枚举右端点，线段树维护所有左端点的 $mx-mn+l$，每次如果存在合法的区间值一定是最小值 $r$，记录最小值个数即可，维护单调栈每次更新即可。这个题是要对一个子区间全部做，相当于要维护历史贡献信息：对于这种题我们线段树上记一个值专门用来存答案，每次更新完右端点的操作后我们在根打一个答案标记，答案标记下传到某个儿子当且仅当这个点儿子的最小值和父亲的最小值相等，并且一定要在加法下传后再下传（因为前面的加法标记都是应该加完后判断的），然后查询就区间查询和就好了。建议看代码意会一下。。这个东西感觉是可以扩展的，好多利用线段树枚举左端点维护右端点的题都可以改改做了。核心思想还是每次修改前肯定先处理完标记再下传，那么统计答案的标记优先级一定小于修改的标记。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; int mn[MAXN<<2],cnt[MAXN<<2],tag[MAXN<<2]; LL res[MAXN<<2],tag2[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void pushup(int x){ mn[x] = std::min(mn[lc],mn[rc]);cnt[x] = 0; if(mn[x] == mn[lc]) cnt[x] += cnt[lc]; if(mn[x] == mn[rc]) cnt[x] += cnt[rc]; } inline void cover(int x,int d){ mn[x] += d;tag[x] += d; } inline void cover2(int x,int mn,int d){ if(::mn[x] != mn) return; res[x] += 1ll*cnt[x]*d;tag2[x] += d; }// 注意这个标记是后打的 所以最后pushdown这个标记 inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } if(tag2[x]){ cover2(lc,mn[x],tag2[x]); cover2(rc,mn[x],tag2[x]); tag2[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(l == L && r == R){ cover(x,d);return; } int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); pushup(x); } inline void build(int x,int l,int r){ if(l == r){ mn[x] = l;cnt[x] = 1; return; } int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); pushup(x); } inline LL query(int x,int l,int r,int L,int R){ if(l == L && r == R) return res[x]; int mid = (l + r) >> 1;pushdown(x); if(R <= mid) return query(lc,l,mid,L,R); if(L > mid) return query(rc,mid+1,r,L,R); return query(lc,l,mid,L,mid)+query(rc,mid+1,r,mid+1,R); } int a[MAXN]; int n; int stk1[MAXN],stk2[MAXN],tp1,tp2; // 后缀加 std::vector G[MAXN]; LL ans[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i); int q;scanf("%d",&q); FOR(i,1,q){ int l,r;scanf("%d%d",&l,&r); G[r].pb(MP(l,i)); } build(1,1,n); // 1=min,2 = max // r-l = mx-mn // r = mx-mn+l FOR(i,1,n){ while(tp1 && a[stk1[tp1]] <= a[i]){// max modify(1,1,n,stk1[tp1-1]+1,stk1[tp1],-a[stk1[tp1]]); --tp1; } while(tp2 && a[stk2[tp2]] >= a[i]){// min modify(1,1,n,stk2[tp2-1]+1,stk2[tp2],a[stk2[tp2]]); --tp2; } modify(1,1,n,stk1[tp1]+1,i,a[i]); modify(1,1,n,stk2[tp2]+1,i,-a[i]); stk1[++tp1] = i;stk2[++tp2] = i; cover2(1,mn[1],1); for(auto x:G[i]) ans[x.se] = query(1,1,n,x.fi,i); } FOR(i,1,q) printf("%lld\n",ans[i]); return 0; }
A考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）B把未被锁定的位置从大到小排序即可。因为无论如何放最后一个未锁定的位置的前缀和不会变，那么肯定先把所有最大的都用上去尽量 cover 掉小的贡献。Cdp。设 $f_{i,0/1}$ 表示打了前 $i$ 关，轮到玩家还是玩家的朋友打的最小代价，直接枚举转移即可。D假设两个位置选择的分别是 $x_1,x_2(x_1 < x_2)$，把坐标排好序后肯定存在一个分解点 $mid$，满足 $i \leq mid$ 都走到 $x_1$，并且 $i > mid$ 都走到 $x_2$。设第 $i$ 个坐标位置 $p_i$，发现这样的代价为 $p_n-p_1-(p_{mid+1}-p_{mid})$，所以实际上是要你支持插入，删除，维护相邻差的最大值，用两个 multiset 就可以了。E根据期望的线性性，我们只需要计算每一个 boss 对玩家的期望伤害即可。boss 可以分为两类：一类是会削玩家护盾耐久的，一类是螳臂当车的。对于会削玩家护盾耐久的，设这样的 boss 有 $m$ 个，能打到玩家的概率是 $\frac{m-a_i}{m}$（因为它在这 $m$ 个数的相对排名只有 $m$ 种情况，后面 $m-a_i$ 种是合法的）对于螳臂当车的 boss，设这样的 boss 有 $k$ 个，能打到玩家的概率是 $\frac{m+1-a_i}{m+1}$。（因为它只能选择 $m+1$ 个空插进去，后面 $m+1-a_i$ 个空是合法的）分开乘起来就行。多组询问只需要离线排序，变成了维护每次将一个削玩家耐久的变成螳臂当车的boss的操作，记录一下权值和就行了。F发现一个结论：对于任何一对 $x_1y_1 = x_2y_2(x_1 < x_2)$，都存在一对正整数 $a < b$，满足 $x_2 = \frac{x_1}{a}b,y_2 = \frac{y_1}{b}a$。[collapse status="false" title="证明"]设 $g=\gcd(x_1,x_2)$，我们构造 $a=\frac{x_1}{g},b = \frac{x_2}{g}$，不难发现 $\frac{x_1}{a}b = x_2$，接下来只需要证明 $b|y_1$即可。注意到 $b=\frac{x_2}{g} | \frac{x_2y_2}{g} = \frac{x_1y_1}{g}$，又因为有 $(b,\frac{x_1}{g}) = 1$，所以得到 $b|y_1$。[/collapse]因为 $a|x_1,b|y_1$，所以有效的 $(a,x_1)$ 只有 $O(n \log n)$ 对。现在我们去固定 $x_1$，考虑 $y_1$ 的种种限制：首先要保证 $y_1 \leq m$，其次还要保证 $\lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor$。我们考虑枚举一对 $(a,x_1)$，现在相当于要求快速询问是否存在一对 $(b,y_1)$ 满足如下条件：$$ \begin{aligned} y_1 \leq m\\ \lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor\\ \frac{x_1}{a}b \leq n\\ a < b \end{aligned} $$显然我们会贪心选择能选择的 $b$ 中最小的去判断第三个限制是否成立。第一个和第二个限制可以通过从小到大枚举 $x$ 双指针解决，第四个限制可以维护当前所有可选值的 set 解决，复杂度 $O(n \log^2 n)$。G确定性做法我们考虑枚举右端点，维护每个左端点是否合法。我们的目标是让对于每一种颜色，如果左端点区间是合法的，贡献就是 $0$，否则贡献是 $1$。那么一个左端点合法当且仅当这个位置的值是 $0$。我们每次加入一个点 $i$，设它前面第一个，第二个，第三个，第四个和它相等的是 $p_1,p_2,p_3,p_4$，我们只需要让 $(p_1,i]+1$，$(p_3,p_2]-1$，$(p_4,p_3]+1$ 即可。线段树维护最小值和最小值个数，支持区间加即可。基于这个做法我把题目小小加强了一下链接（不确定正确性详细维护方式可以见代码：#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5e5 + 5; int a[MAXN],n; #define lc ((x)<<1) #define rc ((x)<<1|1) int mn[MAXN<<2],cnt[MAXN<<2],tag[MAXN<<2]; inline void pushup(int x){ mn[x] = std::min(mn[lc],mn[rc]);cnt[x] = 0; if(mn[x] == mn[lc]) cnt[x] += cnt[lc]; if(mn[x] == mn[rc]) cnt[x] += cnt[rc]; } inline void cover(int x,int d){ mn[x] += d;tag[x] += d; } inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(L > R) return; if(l == L && r == R){ cover(x,d);return; } int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); pushup(x); } inline void build(int x,int l,int r){ if(l == r){ cnt[x] = 1;mn[x] = 1e9;return; } int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); pushup(x); } int lst[MAXN],pre[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i); FOR(i,1,n){ pre[i] = lst[a[i]]; lst[a[i]] = i; } build(1,1,n);LL ans= 0; FOR(i,1,n){ int p1 = pre[i],p2 = pre[p1],p3 = pre[p2],p4 = pre[p3]; modify(1,1,n,i,i,-1e9); modify(1,1,n,p1+1,i,1); if(p2) modify(1,1,n,p3+1,p2,-1); if(p3) modify(1,1,n,p4+1,p3,1); if(mn[1] == 0) ans += cnt[1]; } printf("%lld\n",ans); return 0; }基于随机的做法出现三次不难联想到三进制不进位加法。我们对于每个数字随机一个 $60$ 维模 $3$ 意义下的向量，前缀和后两个位置前缀和相同就表示这一段区间所有出现次数 $\bmod 3=0$，但是我们想要的是 $=3$，我们只需要用双指针维护出满足所有颜色出现次数 $\leq 3$ 的区间即可。出题人说：[scode type="blue"]Assume you use $K$ trits. I guess the probability of the collision is the same as two vectors (out of $n$) colliding in a $K$ - dimensional space with their coordinates being from $0$ to $2$. That will be about $\frac{1}{2}$ when $n≈3^K$ (according to birthday paradox) — and way less if we increase $K$.[/scode]
A考虑 dp。设 $f_{i,0/1}$ 表示考虑到根是 $i$ 前缀，最后一次删除的串长度为 $2/3$ 的方案数。转移就判断一下两次长度相等是否子串相等即可。B这种最长的最短路链问题贪心超过两步都是错的。首先 $O(n^2)$ 预处理 $dis_{i,j}$ 表示 $i \to j$ 的最短路，注意到贪心一步是正确的，我们去枚举 $b,c$，预处理最远，次远，第三远的点即可（因为路径不能重复）。C首先可以写出一个dp：设 $f_{i,j}$ 表示考虑填了前 $i$ 位，匹配了 $t$ 的前 $j$ 位的方案数。转移：$$ \begin{aligned} \text{if }j \neq m :\\ f_{i,j} \to 25f_{i+1,j}\\ f_{i,j} \to f_{i+1,j+1}\\ \text{if } j = m:\\ f_{i,j} \to 26f_{i+1,j} \end{aligned} $$这种转移形式简单的计数问题可以抽象到网格图游走上：如果你当前在的坐标 $j \neq m$，可以选择走 $(1,0)$，方案 $25$，走 $(1,1)$ 方案数是 $1$；如果已经 $j=m$，那么只能走 $(1,0)$，方案数 $26$。发现 $(1,1)$ 的数量恰为 $m$；考虑整个操作序列，在最后一个 $(1,1)$ 后的 $(1.0)$ 贡献都是 $26$，前面都是 $25$。考虑枚举最后一个 $(1,1)$：$$ \sum_{i=m}^n \binom{i-1}{m-1}25^{i-m}26^{n-i} = \frac{26^n}{25^m}\sum_{i=0}^m \binom{i-1}{m-1} (\frac{25}{26})^i $$注意 $\sum m \leq 10^5$，所以本质不同的 $m$ 只会有 $\sqrt m$ 个，每次都预处理所有答案，复杂度 $O(n \sqrt m)$。D这题暴力就行了。我们先枚举每个点最终对应的点哪个坐标相等（可以看成是枚举在一条横线还是纵线上），然后分类讨论：首先如果存在交点一定选交点要不然点就不够用了。我们将所有的线去重之后分类讨论：两横两纵每个点都是确定的，判断是否是正方形后 $4!$ 枚举配对方案求答案即可。两横一纵（或两纵一横）我们确定了两个点和这个正方形的边长 $D$，所以另外两个点只有可能是坐标某一维 $\pm D$，对每一种情况 $4!$ 统计答案即可。两横或两纵我们考虑两横：首先确定了正方形的边长 $D$，一个暴力的想法枚举一个点，就能确定所有的点。假设现在上面的点是 $x_1,x_2$，下面的点是 $x_3,x_4$，不失一般性设当前枚举的两条竖线是 $x,x+D$。不失一般性我们设 $x_1,x_3$ 匹配 $x$，$x_2,x_4$ 匹配 $x+D$（这里可以通过枚举完成所有情况），那么答案就是 $\max\{|x_1-x|,|x_3-x|,|x_2-(x+D)|,|x_4-(x+D)|\}$，拆开变成四个坐标 $x_1,x_3,x_2-D,x_4-D$，只需要取最大值和最小值的中点左右挨个判断一下即可。代码太长了（170+），这里给出提交链接E先对所有的 $t$ 建出广义SAM，现在先考虑如何确定 $S[l,r]$ 对应的位置：我们先找到 $S[1,r]$ 对应的位置，不断跳 fail 并保证一直包含这个区间，需要用倍增预处理一下。然后就直接线段树合并一发维护处最大值和最大值的位置就行了。细节比较多，放一下代码：#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; struct Node{ int mx,ps; Node(int mx=0,int ps=-1) : mx(mx),ps(ps) {} friend Node operator + (const Node &x,const Node &y){ Node res; if(x.mx >= y.mx) res.mx = x.mx,res.ps = x.ps; else res.mx = y.mx,res.ps = y.ps; return res; } }sm[MAXN<<5]; // 最大值,非0位置个数 int lc[MAXN<<5],rc[MAXN<<5],tot; inline Node query(int x,int l,int r,int L,int R){ if(!x) return Node(); if(l == L && r == R) return sm[x]; int mid = (l + r) >> 1; if(R <= mid) return query(lc[x],l,mid,L,R); if(L > mid) return query(rc[x],mid+1,r,L,R); return query(lc[x],l,mid,L,mid)+query(rc[x],mid+1,r,mid+1,R); } inline void update(int &x,int l,int r,int p){ if(!x) x = ++tot; if(l == r){ sm[x].mx++;sm[x].ps = l; return; } int mid = (l + r) >> 1; if(p <= mid) update(lc[x],l,mid,p); else update(rc[x],mid+1,r,p); sm[x] = sm[lc[x]]+sm[rc[x]]; } inline int merge(int x,int y,int l,int r){ if(!x || !y) return x|y; int now = ++tot; if(l == r){ sm[now] = sm[x]; sm[now].mx += sm[y].mx; return now; } int mid = (l + r) >> 1; lc[now] = merge(lc[x],lc[y],l,mid); rc[now] = merge(rc[x],rc[y],mid+1,r); sm[now] = sm[lc[now]]+sm[rc[now]]; return now; } int ch[MAXN][26],fail[MAXN],len[MAXN],_tot = 1,las = 1; int rt[MAXN]; inline void copy(int x,int y){ FOR(i,0,25) ch[x][i] = ch[y][i]; fail[x] = fail[y];len[x] = len[y]; } inline int work(int p,int c){ int q = ch[p][c],nq = ++_tot; copy(nq,q);len[nq] = len[p]+1;fail[q] = nq; for(;p&&ch[p][c]==q;p=fail[p]) ch[p][c] = nq; return nq; } inline int insert(int p,int c){ int q = ch[p][c]; if(q){ if(len[q] == len[p]+1) return q; return work(p,c); } int np = ++_tot;len[np] = len[p]+1; for(;p&&!ch[p][c];p=fail[p]) ch[p][c] = np; if(!p) fail[np] = 1; else{ q = ch[p][c]; if(len[q] == len[p]+1) fail[np] = q; else fail[np] = work(p,c); } return np; } const int MAXK = 5e5 + 5; char S[MAXK],str[MAXN]; int n; std::vector<int> G[MAXN]; const int MAXM = 16; int f[MAXN][MAXM+1],m; inline void dfs(int v){ FOR(i,1,MAXM) f[v][i] = f[f[v][i-1]][i-1]; for(auto x:G[v]){ f[x][0] = v;dfs(x); rt[v] = merge(rt[v],rt[x],1,m); } } int to[MAXK],le[MAXK]; int main(){ scanf("%s",S+1);n = strlen(S+1); scanf("%d",&m); FOR(i,1,m){ las = 1; scanf("%s",str+1);int len = strlen(str+1); FOR(j,1,len) las = insert(las,str[j]-'a'),update(rt[las],1,m,i); } // DEBUG(query(rt[12],1,m,1,2).mx); // exit(0); FOR(i,2,_tot) G[fail[i]].pb(i); // for(auto x:G[81]){ // DEBUG(x); // DEBUG(sm[rt[x]].mx); // for(auto y:G[x]){ // DEBUG(y); // DEBUG(sm[rt[y]].mx); // } // } // exit(0); dfs(1);to[0] = 1; int now=1,len = 0; FOR(i,1,n){ int c = S[i]-'a'; if(ch[now][c]) len++,now = ch[now][c]; else{ while(now && !ch[now][c]) now = fail[now]; if(!now) now = 1,len = 0; else len = ::len[now]+1,now = ch[now][c]; } to[i] = now;le[i] = len; } int q;scanf("%d",&q); while(q--){ int l,r,pl,pr;scanf("%d%d%d%d",&l,&r,&pl,&pr); int v = to[pr]; if(le[pr] < pr-pl+1){ printf("%d %d\n",l,0); continue; } ROF(i,MAXM,0){ if(::len[f[v][i]] >= pr-pl+1){ v = f[v][i]; } } Node ans = query(rt[v],1,m,l,r); if(ans.ps == -1) printf("%d %d\n",l,0); else printf("%d %d\n",ans.ps,ans.mx); } return 0; }