省队集训-0420模拟赛

A.最小生成树

题意：

n

个点，

m

条边，每条边有两个边权

a_i,b_i

，可以选一个定为该边边权。对于每个

0\le c\le m

，求恰好选

c

个

a_i

，

m-c

个

b_i

时最大的最小生成树。

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;
}

省队集训-0420模拟赛

文章操作

A.最小生成树

题意：

Sol：

B.操作

题意：

Sol：

Code：

C.排列

题意：

Sol：

Code：

相关推荐

评论

省队集训-0420模拟赛