省队集训-0420模拟赛
allenchoi
·
·
个人记录
比赛链接
A.最小生成树
题意：
$n\le 9,m\le 100$。
#### Sol：
Kruskal。
将 $2m$ 条边从小到大排序，设 $dp_{i,j,f}$ 表示已经考虑到第 $i$ 条边，已选 $j$ 个 $b_i$，并查集状态为 $f$ 时的最大值。
考虑怎么转移。
每一条边有两个分边，在较小的那条时确定选 $a_i/b_i$。
如果 $x_i,y_i$ 已在一个连通块内：
如果这条边是第一个分边，则 $j$ 可以加一，否则 $j$ 只能不加；
如果 $x_i,y_i$ 不在一个连通块内：
如果这条边是第一个分边，则可以选择加入/不加入生成树，$j$ 加上对应的贡献，否则只能加入生成树。
用个 map 即可，细节见代码。
~~~cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 10,M = 210;
int n,m,f[N],g[N],a[M],b[M];
struct Edge{int x,y,z,t,id;} e[M];
bool cmp(Edge x,Edge y)
{
if(x.z == y.z) return x.t < y.t;
return x.z < y.z;
}
unordered_map <int,int> dp[M][M / 2];
void get_t(int s)
{
for(int i = n;i >= 1;i--) g[i] = s % 10,s /= 10;
}
int get_hsh()
{
int s = 0;
for(int i = 1;i <= n;i++) s = s * 10 + f[i];
return s;
}
void merge(int x,int y)
{
if(x > y) swap(x,y);
for(int i = 1;i <= n;i++) if(f[i] == y) f[i] = x;
}
int main()
{
freopen("mst.in","r",stdin);
freopen("mst.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1,x,y;i <= m;i++)
{
scanf("%d%d%d%d",&x,&y,&a[i],&b[i]);
e[i] = (Edge){x,y,a[i],0,i},e[i + m] = (Edge){x,y,b[i],1,i};
}
sort(e + 1,e + 2 * m + 1,cmp);
for(int i = 1;i <= n;i++) f[i] = i;
dp[0][0][get_hsh()] = 0;
for(int i = 1,x,y,z,t,fl;i <= 2 * m;i++)
{
x = e[i].x,y = e[i].y,z = e[i].z,t = e[i].t,fl = (t == (a[e[i].id] > b[e[i].id]));
for(int j = 0;j <= m;j++)
{
for(pair <int,int> p : dp[i - 1][j])
{
int s1 = p.first,s2,v = p.second;
get_t(s1);
if(g[x] == g[y])
{
dp[i][j][s1] = max(dp[i][j][s1],v);
if(fl) dp[i][j + 1][s1] = max(dp[i][j + 1][s1],v);
continue;
}
if(fl) dp[i][j + e[i].t][s1] = max(dp[i][j + t][s1],v);
memcpy(f,g,sizeof(f));
merge(f[x],f[y]);
s2 = get_hsh();
if(fl) dp[i][j + (t ^ 1)][s2] = max(dp[i][j + (t ^ 1)][s2],v + z);
else dp[i][j][s2] = max(dp[i][j][s2],v + z);
}
}
}
for(int i = 1;i <= n;i++) f[i] = 1;
int s = get_hsh();
for(int i = 0;i <= m;i++) printf("%d\n",dp[2 * m][i][s]);
return 0;
}
~~~
### B.操作
#### 题意：
给出 $n$ 个操作以及模数 $p$。
有一个初始为 $1$ 的变量 $x$，操作 $1$：$x\leftarrow v$；操作 $2$：$x\leftarrow x\times v$。
可以以任意顺序操作，问 $[0,p)$ 中有多少个数无论如何都不能在最后得到。
$n,p\le 10^6$。
#### Sol：
等价于在集合 $0$ 中选一个数，在集合 $1$ 中选若干个数（可不选），把它们乘起来。
用一个 $p$ 的原根 $g$ 表示所有数，则乘法转为加法，变成卷积形式。初始时令答案集合为 $0$ 集合，依次卷上 $1$ 集合中的每个数，可以用 bitset。
发现每个数只会加入 $1$ 次，即更新次数 $O(p)$。
于是想到分治+哈希。设我们正在加入 $v$，当区间 $[l,r]$ 和 $[l+v,r+v]$ 的状态不一样时我们才递归进去。然后用树状数组维护哈希。
证明一下这样的次数是对的：
注意到 $i\rightarrow i+v$ 会形成若干个环，而环上相邻位置状态为 $01$ 的数量是等于 $10$ 的数量的，因此总的递归到最底层的次数还是 $O(p)$ 的。每次递归到最底层会走 $\log$ 层，然后每层树状数组求哈希 $O(\log)$，所以总复杂度为 $O(p\log^2p)$。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define pb push_back
#define lb(x) ((x) & (-x))
using namespace std;
const int N = 1e6 + 5,K = 131,mod = 200002333;
int T,n,p,g,tot,fl1,fl2,ans,f[N],prm[N],id[N],mi[N],imi[N],vis[N];
vector <int> a,b,d,pos;
struct Bit
{
int s[N];
void update(int x,int v){for(int i = x;i < p;i += lb(i)) s[i] = (s[i] + v) % mod;}
int query(int x)
{
int ret = 0;
for(int i = x;i;i -= lb(i)) ret = (ret + s[i]) % mod;
return ret;
}
} tr;
int ksm(int x,int y,int mod)
{
int ret = 1;
while(y)
{
if(y & 1) ret = 1LL * ret * x % mod;
x = 1LL * x * x % mod,y >>= 1;
}
return ret;
}
bool check(int x)
{
for(int i : d) if(ksm(x,(p - 1) / i,p) == 1) return false;
return true;
}
int get_hsh(int l,int r){return 1LL * (tr.query(r + 1) - tr.query(l) + mod) * imi[l] % mod;}
bool eql(int l,int r,int v)
{
int tl = l + v,tr = r + v;
if(tr < p - 1) return get_hsh(l,r) == get_hsh(tl,tr);
if(tl < p - 1 && p - 1 <= tr) return get_hsh(l,l + p - 2 - tl) == get_hsh(tl,p - 2) && get_hsh(l + p - 1 - tl,r) == get_hsh(0,tr - p + 1);
return get_hsh(l,r) == get_hsh(tl - p + 1,tr - p + 1);
}
void solve(int l,int r,int v)
{
if(l == r)
{
if(vis[l]) pos.pb((l + v) % (p - 1));
return ;
}
int mid = (l + r) / 2;
if(!eql(l,mid,v)) solve(l,mid,v);
if(!eql(mid + 1,r,v)) solve(mid + 1,r,v);
}
int main()
{
freopen("operation.in","r",stdin);
freopen("operation.out","w",stdout);
for(int i = 2;i < N;i++)
{
if(!f[i]) prm[++tot] = i;
for(int j = 1;j <= tot && i * prm[j] < N;j++)
{
f[i * prm[j]] = 1;
if(i % prm[j] == 0) break;
}
}
mi[0] = imi[0] = 1,imi[1] = ksm(K,mod - 2,mod);
for(int i = 1;i < N;i++) mi[i] = 1LL * mi[i - 1] * K % mod;
for(int i = 1;i < N;i++) imi[i] = 1LL * imi[i - 1] * imi[1] % mod;
scanf("%d",&T);
while(T--)
{
fl1 = fl2 = 0;
a.clear(),b.clear(),d.clear();
scanf("%d%d",&p,&n);
for(int i = 1;i <= tot;i++) if((p - 1) % prm[i] == 0) d.pb(prm[i]);
for(g = 1;!check(g);g++);
for(int i = 0,mi = 1;i < p - 1;i++,mi = 1LL * mi * g % p) id[mi] = i;
for(int i = 1,op,x;i <= n;i++)
{
scanf("%d%d",&op,&x);
if(!x)
{
if(!op) fl1 = 1;
else fl2 = 1;
continue;
}
if(!op) a.pb(id[x]);
else b.pb(id[x]);
}
if(!a.size())
{
printf("%d\n",p - 1);
continue;
}
memset(tr.s,0,sizeof(tr.s));
for(int i = 0;i < p;i++) vis[i] = 0;
for(int i : a) if(!vis[i]) vis[i] = 1,tr.update(i + 1,mi[i]);
for(int i : b)
{
if(eql(0,p - 2,i)) continue;
pos.clear();
solve(0,p - 2,i);
for(int j : pos) vis[j] = 1,tr.update(j + 1,mi[j]);
}
ans = (!fl1 && !fl2);
for(int i = 0;i < p - 1;i++) ans += (!vis[i]);
printf("%d\n",ans);
}
return 0;
}
~~~
### C.排列
#### 题意：
P9265
给出一个排列 $p$，生成一个 $n$ 个点的无向图，对于 $i<j$，它们之间有边，当且仅当 $p_i>p_j$，长度为 $1$。
对于每个 $i$ 问 $\sum\limits_j dis(i,j)$，如果不联通则 $dis=0$。
$n\le 2\times10^5$。
#### Sol：
首先，如果 $\max\limits_{j=1}^{i}p_j=i$，则称 $i$ 为关键点，相邻的两个关键点 $[key_{i-1}+1,key_i]$ 之间是一个极大连通块，证明考虑从这个区间的极大值处断开，然后归纳。
其次，将排列视为平面上的 $n$ 个点 $(p_i,i)$，则 $dis(i,j)\ge k$ 的点是平面左下角一个矩形或右上角一个矩形内，这个矩形的边界由上一次我们走到的最左、最下/最右、最上的点决定，可以归纳证明。
然后发现这两个矩形其实是独立的，因为我们总是用上次最左的点更新现在最下的点，用上次最下的点更新这次最左的点。
所以左下、右上角是等价的。下面只考虑左下角怎么做，右上角把整个平面旋转 $180$ 度即可。
设从 $i$ 出发，走了 $k$ 步后，能到达的最做的点为 $x$，最下的点为 $y$，则 $dis_{i,j}>k+1\Leftrightarrow j<x\land p_j<p_y$。
设 $ls_i$ 表示满足 $j\le i$ 且 $p_j\ge p_i$ 的最小的 $j$，$rs_i$ 表示满足 $j\ge i$ 且 $p_j\le p_i$ 的、同时 $p_j$ 最小的 $j$，则 $(x,y)$ 下一步会走到 $(ls_y,rs_x)$。然后 $i$ 的答案就是从 $(i,i)$ 一直跳，经过的所有点的左下方的点数之和。
不难发现可以由跳的过程形成由向根树构成的森林。有结论：所有点经过的 $(x,y)$ 总个数是 $O(n\sqrt{n})$ 的，证明如下：
对于每个 $x$，将所有 $(x,y)$ 按 $p_y$ 升序排序，得到 $(x,c_{x,1}),(x,c_{x,2})...(x,c_{x,m})$，称 $i\le \sqrt{n}$ 的 $(x,c_{x,i})$ 为好的点，其它的点为坏的点。
注意到对于所有点 $(x,y)$，都有 $x\le y,p_x\ge p_y$。所以，如果在跳的过程中我们经过了某个坏的点 $(x,c_{x,i}),i>\sqrt{n}$，则下一步 $y$ 至少会走到 $c_{x,1}$，即 $p_y$ 至少减少 $\sqrt{n}$。由于一次跳的过程中 $p_y$ 不增，所以一次至多经过 $\sqrt{n}$ 个坏点，总个数 $O(n\sqrt{n})$。而好点个数不超过 $O(n\sqrt{n})$，所以树的点数为 $O(n\sqrt{n})$ 的。
考虑怎么建树。显然可以暴力跳，然后用 set 之类的维护点集，但这样会有个 $\log$。
发现 $p_{rs_x}$ 随 $x$ 的减小而减小。每个 $x$ 维护一个栈 $st_x$ 表示待加入点集的点，点按 $p_y$ 降序排序。从大到小扫 $x$，将栈中的点加入点集，加入 $(x,y)$ 时再将点 $(ls_y,rs_x)$ 插入栈 $st_{ls_y}$ 里面。由于我们从达到小扫 $x$，所以 $p_{rs_x}$ 一定是最小的，和 $st_{ls_y}$ 的栈顶比较一下是否相同即可。这样可以得到点集和所有点的父亲。
查询的话，从小到大扫 $x$，每个点的权值等于其父亲的权值加上自己左下方的点数。查询左下方的点数时，由于有 $O(n\sqrt{n})$ 次查询 $O(n)$ 次插入所以用分块平衡一下复杂度。$i$ 的答案就是 $(i,i)$ 的权值。
一些细节：
1.最前面有说 $[key_{i-1}+1,key_{i}]$ 是一个极大联通快，因此经过一个关键点时要清空分块。
2.我们只算了 $dis_{i,j}>k+1(k\ge 0)$ 的贡献，所以及的加上 $dis_{i,j}>0$ 的贡献，即 $\forall key_{i-1}<j\le key_i,ans_j\leftarrow ans_j+key_i-key_{i-1}-1$。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define lb(x) ((x) & (-(x)))
using namespace std;
typedef long long ll;
const int N = 2e5 + 5,M = 5e7 + 5;
int n,cnt,p[N],ls[N],rs[N],fa[M],id[N],inv[N];
ll ans[N],sum[M];
vector <pii> v[N],tmp;
struct Bit
{
int minn[N];
void init(){memset(minn,127,sizeof(minn));}
void update(int x,int v){for(int i = x;i <= n;i += lb(i)) minn[i] = min(minn[i],v);}
int query(int x)
{
int ret = 2e9;
for(int i = x;i;i -= lb(i)) ret = min(ret,minn[i]);
return ret;
}
} tr;
struct Block
{
int siz,cnt,id[N],L[N],R[N],v[N],sum[N];
void init()
{
siz = (int)sqrt(n);
for(int i = 1;i <= n;i++) v[i] = 0;
for(int i = 1,l = 1,r = siz;l <= n;i++,l += siz,r += siz)
{
L[i] = l,R[i] = min(n,r),sum[i] = 0;
for(int j = L[i];j <= R[i];j++) id[j] = i;
}
cnt = id[n];
}
void update(int x,int k)
{
for(int i = x;i <= R[id[x]];i++) v[i] += k;
for(int i = id[x] + 1;i <= cnt;i++) sum[i] += k;
}
int query(int x){return sum[id[x]] + v[x];}
} B;
void solve(int t)
{
tr.init();
for(int i = 1;i <= n;i++)
{
tr.update(n - p[i] + 1,i);
ls[i] = tr.query(n - p[i] + 1);
}
for(int i = 1;i <= n;i++) inv[p[i]] = i;
for(int i = n,minn = n;i >= 1;i--)
{
minn = min(minn,p[i]);
rs[i] = inv[minn];
}
cnt = 0;
for(int i = 1;i <= n;i++) v[i].clear();
for(int i = n,x,y,cur;i >= 1;i--)
{
tmp.clear(),cur = 0;
while(cur < (int)v[i].size() && p[v[i][cur].fi] > p[i]) tmp.pb(v[i][cur++]);
tmp.pb(mkp(i,id[i] = ++cnt));
while(cur < (int)v[i].size()) tmp.pb(v[i][cur++]);
v[i] = tmp;
for(int t = 0;t < (int)v[i].size();t++)
{
pii j = v[i][t];
x = ls[j.fi],y = rs[i];
if(x == i && y == j.fi)
{
fa[j.se] = 0;
continue;
}
if(v[x].size() && v[x].back().fi == y) fa[j.se] = v[x].back().se;
else v[x].pb(mkp(y,fa[j.se] = ++cnt));
}
}
B.init();
for(int i = 1,lst = 0,maxn = 0;i <= n;i++)
{
for(int t = v[i].size() - 1;t >= 0;t--)
{
pii j = v[i][t];
sum[j.se] = sum[fa[j.se]] + B.query(p[j.fi]);
}
B.update(p[i],1);
ans[i] += sum[id[i]];
maxn = max(maxn,p[i]);
if(maxn == i)
{
for(int j = lst + 1;j <= i;j++) B.update(p[j],-1);
if(t) for(int j = lst + 1;j <= i;j++) ans[j] += i - lst - 1;
lst = i;
}
}
}
int main()
{
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&p[i]);
solve(0);
for(int i = 1;i <= n;i++) p[i] = n - p[i] + 1;
reverse(p + 1,p + n + 1);
reverse(ans + 1,ans + n + 1);
solve(1);
for(int i = n;i >= 1;i--) printf("%lld ",ans[i]);
puts("");
return 0;
}
~~~