竞赛讨论区 > 【题解】"蔚来杯"2022牛客暑期多校训练营10
头像
王清楚
发布于 2023-02-10 16:07 北京
+ 关注

【题解】"蔚来杯"2022牛客暑期多校训练营10

A

考虑容斥。如果把每对不合法的相邻的 au,ava_u,a_v 连起来的话,发现是若干个连通块。

那么设 f(x,i)f(x,i) 表示 xx 子树内,xx 所在联通块 bib_i 最小值为 ii 。(这样的话,这个连通块有 ii 种取值可以连起来)。

转移考虑子树合并。

  • 不把儿子 yy 并上来,有 f(x,i)=f(x,i)×j×f(y,j)f'(x,i)=f(x,i)\times \sum j\times f(y,j)
  • 把儿子 yy 并上来
    • 儿子 yy 所在连通块最小值大于 xx 所在连通块最小值 f(x,i)=f(x,i)×(jif(y,j))f'(x,i)=f(x,i)\times(-\sum_{j\geq i} f(y,j))
    • 儿子 yy 所在连通块最小值小于 xx 所在连通块最小值 f(x,j)=f(y,j)×(ijf(x,i))f'(x,j)=f(y,j)\times(-\sum_{i\geq j} f(x,i))

用线段树合并在 O(nlogn)\mathcal O(n\log n) 的时间下实现。

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pi pair<int, int>
const int N = 500010, K = 60;
const int mod = 998244353;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int n, b[N];
vector<int> G[N];
int rt[N], lc[N * K], rc[N * K], tag[N * K], sf[N * K], sfi[N * K], idx;
void push_up(int x) {
    sf[x] = (sf[lc[x]] + sf[rc[x]]) % mod;
    sfi[x] = (sfi[lc[x]] + sfi[rc[x]]) % mod;
}
void Mul(int x, int v) {
    sf[x] = sf[x] * v % mod;
    sfi[x] = sfi[x] * v % mod;
    tag[x] = tag[x] * v % mod;
}
void push_down(int x) {
    if (tag[x] != 1) {
        if (lc[x])
            Mul(lc[x], tag[x]);
        if (rc[x])
            Mul(rc[x], tag[x]);
        tag[x] = 1;
    }
}
void insert(int& x, int l, int r, int p) {
    if (!x) {
        x = ++idx;
        tag[x] = 1;
    }
    if (l == r) {
        sf[x] = 1, sfi[x] = p;
        return;
    }
    int mid = l + r >> 1;
    push_down(x);
    if (p <= mid)
        insert(lc[x], l, mid, p);
    else
        insert(rc[x], mid + 1, r, p);
    push_up(x);
}
void merge(int& u1, int u2, int l, int r, int c1, int c2) {
    if (!u1 && !u2)
        return;
    if (!u2) {
        Mul(u1, c1);
        return;
    }
    if (!u1) {
        u1 = u2;
        Mul(u1, c2);
        return;
    }
    if (l == r) {
        int f1 = sf[u1], f2 = sf[u2];
        f1 = f1 * ((c1 - f2 + mod) % mod) % mod;
        f2 = f2 * c2 % mod;
        f1 = (f1 + f2) % mod;
        sf[u1] = f1, sfi[u1] = f1 * l % mod;
        return;
    }
    push_down(u1), push_down(u2);
    int mid = l + r >> 1;
    merge(lc[u1], lc[u2], l, mid, (c1 - sf[rc[u2]] + mod) % mod, (c2 - sf[rc[u1]] + mod) % mod);
    merge(rc[u1], rc[u2], mid + 1, r, c1, c2);
    push_up(u1);
}
void dfs(int x, int f) {
    insert(rt[x], 1, mod - 1, b[x]);
    for (int y : G[x]) {
        if (y == f)
            continue;
        dfs(y, x);
        merge(rt[x], rt[y], 1, mod - 1, sfi[rt[y]], 0);
    }
}
signed main() {
    n = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }
    dfs(1, 0);
    printf("%lld\n", sfi[rt[1]]);
    return 0;
}

B

最大值最小,考虑二分答案。

把坐标 (x,y)(x,y) 转化为 (x+y,xy)(x+y,x-y) 将曼哈顿距离转为切比雪夫距离。

问题变成每种颜色矩形面积并的交是否非空。

每种颜色个数不超过 2020 个,所以暴力离散化,填色,然后在原矩形内打差分标记,二位前缀和看是否有一个格子被覆盖了 mm 次。

#include <bits/stdc++.h>
#define pi pair<int, int>
#define y1 qweqwe
using namespace std;
const int N = 2e3 + 9;
int n, m, a[N][N];
vector<pi> p[N * N];
int s[N][N], v[N][N];
int X[N * N], Y[N * N], x, y;
int ok[N][N];
int check(int d) {
    memset(v, 0, sizeof v);
    for (int c = 1; c <= m; c++) {
        x = 0, y = 0;
        X[x++] = 0;
        Y[y++] = 0;
        for (pi I : p[c]) {
            int i = I.first, j = I.second;
            int x1 = max(1, i - d);
            X[x++] = x1;
            int y1 = max(1, j - d);
            Y[y++] = y1;
            int x2 = min(2 * n + 1, i + d + 1);
            X[x++] = x2;
            int y2 = min(2 * n + 1, j + d + 1);
            Y[y++] = y2;
        }
        sort(X, X + x), sort(Y, Y + y);
        x = unique(X, X + x) - X, y = unique(Y, Y + y) - Y;
        for (int i = 0; i < x; i++)
            for (int j = 0; j < y; j++) s[i][j] = 0;
        for (pi I : p[c]) {
            int i = I.first, j = I.second;
            int x1 = lower_bound(X, X + x, max(1, i - d)) - X;
            int y1 = lower_bound(Y, Y + y, max(1, j - d)) - Y;
            int x2 = lower_bound(X, X + x, min(2 * n + 1, i + d + 1)) - X;
            int y2 = lower_bound(Y, Y + y, min(2 * n + 1, j + d + 1)) - Y;
            s[x1][y1]++;
            s[x1][y2]--;
            s[x2][y1]--;
            s[x2][y2]++;
        }
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
        }
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) s[i][j] = s[i][j] > 0;
        }
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                v[X[i]][Y[j]] += s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
            }
        }
    }

    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * n; j++) {
            v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
            if (ok[i][j] && v[i][j] == m)
                return 1;
        }
    }
    return 0;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            ok[i + j][i - j + n] = 1;
            p[a[i][j]].push_back({ i + j, i - j + n });
        }
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r << endl;
    return 0;
}

C

f(x,V)f(x,V) 表示前 xx 轮选择后当前连通块为 VV

V=1|V|=1 的时候,可以不用继续搜索。否则,枚举这一层保留哪些边转移到下一层。

而对于一个 xx 所有的合法 VV 大小总和不超过 2n2n 。因为一个连通块的集合可以等价于一个边集。每一层的边集不交,所以经过一轮选择后的边集也不会相交。

只需要 dfs 暴力做即可,用 map 或者桶存储每个点属于哪个连通块。时间复杂度 O(nm)\mathcal O(nm)

#include <bits/stdc++.h>
#define vi vector<int>
#define vii vector<vi>
using namespace std;
const int N = 1e6 + 9;
vii a[2][N];
vi pos[2][N];
int n, m, ans[N], j[N];
void dfs(int d, vector<int>& A) {
    if (A.size() == 1)
        return;
    if (d == m + 1) {
        int len = A.size();
        for (int y : A) ans[y] = max(ans[y], len);
        return;
    }
    for (int o = 0; o < 2; o++) {
        int cnt = 0;
        vii res(0);
        for (int x : A) {
            int t = pos[o][d][x];
            if (j[t] == -1) {
                j[t] = cnt++;
                vi ret(0);
                ret.push_back(x);
                res.push_back(ret);
            } else
                res[j[t]].push_back(x);
        }
        for (int x : A) j[pos[o][d][x]] = -1;
        for (auto re : res) dfs(d + 1, re);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        for (int k = 0; k <= 1; k++) {
            int cntpart;
            cin >> cntpart;
            a[k][i] = vii(cntpart);
            pos[k][i] = vi(n + 1);
            for (int j = 0; j < cntpart; j++) {
                int cntnode;
                cin >> cntnode;
                a[k][i][j] = vi(cntnode);
                for (int s = 0; s < cntnode; s++) {
                    int node;
                    cin >> node;
                    a[k][i][j][s] = node;
                    pos[k][i][node] = j;
                }
            }
        }
    }
    vector<int> A(n);
    for (int i = 0; i < n; i++) j[i] = -1, A[i] = i + 1;
    for (int i = 1; i <= n; i++) ans[i] = 1;
    dfs(1, A);
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}

D

首先把只循环一次的贡献提前计算

枚举周期含有 kk 的子串有多少个。

kk 个点设立一个关键点,由于循环一次的贡献已经被计算,那么串长至少为 2k2k ,所以每个符合条件的子串至少包含两个关键点。

111

假设某一个串 TT 的周期含有 kk ,第一次遇到的关键点为 ii 。由于 TT 肯定会包含 [i,i+k][i,i+k] ,不妨贪心把左端点 llii 往前扩展,直到 S[l1]S[l+k1]\orl=ik+1S[l-1]\not=S[l+k-1]\or l=i-k+1,把右端点 rri+ki+k 扩展,直到 S[r+1]S[r+1k]\orr=SS[r+1]\not=S[r+1-k]\or r=|S| 。那么左端点在 ll 的时候,右端点有 max{r,l+2k1}(l+2k1)\max\{r,l+2k-1\}-(l+2k-1) 种取值。所以可以快速计算第一次遇到的关键点为 ii 的子串方案数。

而贪心扩展的部分,可以使用后缀数组快速求出。

而枚举周期为 kk ,只有 Sk\frac{|S|}{k} 个关键点,总时间复杂度就是 O(SlogS)\mathcal O(|S|\log |S|)

#include <bits/stdc++.h>
#define int long long
const int N=1e6+9;
using namespace std;
int lo[N];
int n;
char s[N];
struct suf{
	int m;
	int tong[N],rnk[N],sa[N],y[N],h[N];
	signed p[N][22];
	void qsort(){
		for(int i=0;i<=m;++i)tong[i]=0;
		for(int i=1;i<=n;++i)tong[rnk[i]]++;
		for(int i=1;i<=m;++i)tong[i]+=tong[i-1];
		for(int i=n;i>=1;--i)sa[tong[rnk[y[i]]]--]=y[i];
	}
	inline int lcp(int x,int y){
		x=rnk[x];y=rnk[y];
		if(x>y)swap(x,y);
		x++;
		int o=lo[y-x+1];	
		return min(p[x][o],p[y-(1<<o)+1][o]);
	}
	void SA(){
		m=30;
		for(int i=1;i<=n;++i){rnk[i]=s[i]-'a'+1;y[i]=i;}
	    qsort();
	    for(int w=1,p=0;p<n;w<<=1,m=p){
	    //	cout<<1;
	    	p=0;
	    	for(int i=n-w+1;i<=n;++i)y[++p]=i;
	    	for(int i=1;i<=n;++i)if(sa[i]>w)y[++p]=sa[i]-w;
	        qsort();
	        for(int i=1;i<=n;++i){
	        	swap(rnk[i],y[i]);
			}
		//	swap(rnk,y);
			rnk[sa[1]]=p=1;
	        for(int i=2;i<=n;++i)rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;
	    }
	    for(int i=1,j;i<=n;++i){
	    	if(rnk[i]==1)continue;
	    	j=max(0ll,h[rnk[i-1]]-1);
	    	while(s[i+j]==s[sa[rnk[i]-1]+j])++j;
	    	h[rnk[i]]=j;
	    	p[rnk[i]][0]=j;
	    }
	    for(int i=1;(1<<i)<=n;++i){
	    	for(int j=1;j+(1<<i)-1<=n;++j){
	    		p[j][i]=min(p[j][i-1],p[j+(1<<(i-1))][i-1]);
			}
		}
	}
	void clear(){
		for(int i=0;i<=n;++i){
			tong[i]=rnk[i]=sa[i]=y[i]=h[i]=0;
		}
	}
}sa1,sa2;
signed main(){  
	int T;cin>>T;
	for(int i=2;i<=N-1;++i)lo[i]=lo[i>>1]+1;
	while(T--){
	 	scanf("%s",s+1);
	 	n=strlen(s+1);
	 	sa1.SA();
	 	reverse(s+1,s+n+1);
	 	sa2.SA();
	 	int ans=0;
	 	for(int d=1;d<=n;++d){
	 		for(int i=1;i<=n;i+=d){
	 			int j=i+d,k=j+d-1;
	 			if(k>n)continue;
	 			int num1=min(d,sa2.lcp(n-(j-1)+1,n-k+1));
	 			int q1=i+(d-num1);
	 			int q2=j+(d-num1);
	 			int num=sa1.lcp(q1,q2);
	 			int nn=min(num1,num-(num/d*d)+1);
	 			num=num/d*d;
	 			if(!num)continue;
	 			ans+=num*nn+(num-d)*(num1-nn);
			}
		 }
		for(int i=1;i<=n;++i)
			ans+=i*(n-i+1);
		printf("%lld\n",ans);
		sa1.clear();sa2.clear();
   }
   return 0;
}

E

考虑费用流,源点和每个人,每个人和能审的论文之间连接流量为 11 ,费用为 00 的边。每个论文和汇点连 nn 条边,流量都是 11 ,权值分别为 (1,2,3...n)(1,2,3...n) 。那么花费是递增的凸函数,最后的解满足条件。

#include <bits/stdc++.h>
using namespace std;
const int N = 409;
const int M = N << 2;
const int inf = 1 << 30;
struct Edge {
    int nxt, to, c;
} e[M * M];
int head[M << 2], tot = 1;
queue<int> q;
int n, m, S, T;
int d[M << 2], now[M << 2], ans[N << 3];
void add(int from, int to, int c) {
    e[++tot].to = to;
    e[tot].c = c;
    e[tot].nxt = head[from];
    head[from] = tot;
    e[++tot].to = from;
    e[tot].c = 0;
    e[tot].nxt = head[to];
    head[to] = tot;
}
bool bfs() {
    memset(d, 0, sizeof(d));
    while (!q.empty()) q.pop();
    q.push(S);
    d[S] = 1;
    now[S] = head[S];
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].to;
            if (e[i].c && !d[y]) {
                q.push(y);
                now[y] = head[y];
                d[y] = d[x] + 1;
                if (y == T)
                    return 1;
            }
        }
    }
    return 0;
}
int dinic(int x, int flow) {
    if (x == T)
        return flow;
    int rest = flow, k;
    for (int i = now[x]; i && rest; i = e[i].nxt) {
        int y = e[i].to;
        now[x] = i;
        if (e[i].c && d[y] == d[x] + 1) {
            k = dinic(y, min(e[i].c, rest));
            if (!k)
                d[y] = 0;
            e[i].c -= k;
            e[i ^ 1].c += k;
            rest -= k;
        }
    }
    return flow - rest;
}
int main() {
    scanf("%d%d", &n, &m);
    char s[M << 2];
    S = n + m + 1, T = n + m + 2;
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; j++)
            if (s[j] == '1')
                add(i, j + n, 1);
    }
    for (int i = 1; i <= n; ++i) add(S, i, 1);
    int flow, maxflow = 0;
    for (int t = 1; t <= n; ++t) {
        for (int j = 1; j <= m; j++) add(j + n, T, 1);
        while (bfs())
            while (flow = dinic(S, inf)) maxflow += flow;
        if (maxflow == n) {
            for (int i = 1; i <= n; ++i)
                for (int j = head[i]; j; j = e[j].nxt)
                    if (e[j].c == 0) {
                        ans[i] = e[j].to - n;
                        break;
                    }
            for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], (i == n) ? '\n' : ' ');
            return 0;
        }
    }
    puts("-1");
    return 0;
}

F

考虑求出一个集合 AA 满足 SAS\in A 都是先手必胜的起点。那么 tt 必定在这个集合中。

xAx\in A ,那么 xx 的所有出边一定能达到至少两个 AA 中的点。否则先手会把唯一那条边ban掉,从而导致后手输掉。

那么建反图,从 tt 开始用队列更新出所有在 AA 的点。时间复杂度 O(n+m)\mathcal O(n+m)

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, s, t, w[N];
vector<int> g[N];

void dfs(int u) {
    w[u]++;
    if (w[u] != 2)
        return;
    for (auto v : g[u]) {
        dfs(v);
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d", &n, &m, &s, &t);
        for (int i = 0; i <= n; i++) g[i].clear();
        memset(w, 0, sizeof(w));
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        w[t] = 1;
        dfs(t);
        if (w[s] >= 2)
            puts("Join Player");
        else
            puts("Cut Player");
    }
    return 0;
}

G

发现和 staircase nim 类似,于是直接写出有解条件。

nn 为奇数时,先手必败当且仅当 (AnAn1)(An2An3)...(A1A0)=0(A_n-A_{n-1})\oplus(A_{n-2}-A_{n-3})\oplus...\oplus(A_1-A_0)=0

nn 为偶数时,先手必败当且仅当 (AnAn1)(An2An3)...(A2A1)=0(A_n-A_{n-1})\oplus(A_{n-2}-A_{n-3})\oplus...\oplus(A_2-A_1)=0

我们假设 nn 是偶数(否则可以补一个 00 )。并且令 An+1=mA_{n+1}=m

AA 差分得到数组 Bi=AiAi1B_i=A_i-A_{i-1} ,序列需要满足

  • i=1n+1Bi=m\sum _{i=1}^{n+1}B_i=m
  • Bi0B_i\geq 0
  • i=1n/2B2i=0\bigoplus_{i=1}^{n/2}B_{2i}=0

二进制问题,考虑数位dp。设 f(i,S)f(i,S) 表示选定 BB 序列的前 ii 位,并且满足异或和为 00 的条件下,i=1n+1Bi=miS\sum _{i=1}^{n+1}B_i=m_i-S 的方案数。其中 mim_i 表示保留 mm 二进制下前 ii 位的值。

f(i+1,2S+(mi+1%2)j)+=f(i,S)×g(j)f(i+1,2S+(m_{i+1}\%2)-j)+=f(i,S)\times g(j)

其中 g(j)g(j) 表示,给 n+1n+1 个数这一位选取 0/10/1 ,和为 jj ,其中下标为偶数的位置异或和是 00 的方案数。

可以把下标为偶数的全部移到前面来,所以等价于 n+1n+10/10/1 ,和为 jj ,前 n2\frac{n}{2} 个数异或和为 00 的方案数。

设多项式 Ai=[i%2=0](n/2i)A_i=[i\%2=0]\binom{n/2}{i}

那么 g=A×(1+x)n/2+1g=A\times(1+x)^{n/2+1} ,因为最后 n/2+1n/2+1 个数可以任选。

这个和转移都用多项式来转移,时间复杂度 O(nlognlogm)\mathcal O(n\log n\log m)

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 8e5 + 9;
const int mod = 998244353;
const int G = 3;
const int Gi = 332748118;
int n, k, T;
int m;
int limit = 1, L, r[N];
int a[N], b[N];
int jie[N], rjie[N];
int g[N], temp[N], dp[N];

int inv(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1)
            res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}
int re(int x) { return inv(x, mod - 2, mod); }
void NTT(int *A, int op) {
    for (int i = 0; i < limit; i++)
        if (i < r[i])
            swap(A[i], A[r[i]]);
    for (int mid = 1; mid < limit; mid <<= 1) {
        int Wn = inv(op == 1 ? G : Gi, (mod - 1) / (mid << 1), mod);
        for (int j = 0; j < limit; j += (mid << 1)) {
            int w = 1;
            for (int k = 0; k < mid; k++, w = (w * Wn) % mod) {
                int x = A[j + k], y = w * A[j + k + mid] % mod;
                A[j + k] = (x + y) % mod, A[j + k + mid] = (x - y + mod) % mod;
            }
        }
    }
}
signed main() {
    scanf("%lld%lld", &n, &m);
    jie[0] = rjie[0] = 1;
    for (int i = 1; i <= n; i++) jie[i] = jie[i - 1] * i % mod, rjie[i] = re(jie[i]);
    for (int i = 0; i <= (n + 1) / 4; i++)
        a[i << 1] = jie[(n + 1) / 2] * rjie[2 * i] % mod * rjie[(n + 1) / 2 - 2 * i] % mod;
    for (int i = 0; i <= n / 2; i++) b[i] = jie[n / 2] * rjie[i] % mod * rjie[n / 2 - i] % mod;

    int ma = 2 * n;
    while (limit <= ma) limit <<= 1, L++;
    for (int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    NTT(a, 1);
    NTT(b, 1);
    for (int i = 0; i < limit; i++) a[i] = (a[i] * b[i]) % mod;
    NTT(a, -1);
    int rll = re(limit);
    for (int i = 0; i <= n; i++) g[i] = a[i] * rll % mod;
    dp[0] = 1;
    limit = 1, L = 0;
    while (limit <= 3 * n) limit <<= 1, L++;
    for (int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    int rl = re(limit);
    NTT(g, 1);
    for (int i = 40; i >= 0; i--) {
        int d = m >> i & 1;
        for (int j = 0; j < limit; j++) temp[j] = 0;
        for (int j = 0; j <= 2 * n; j++) (temp[min(2 * n, 2 * j + d)] += dp[j]) %= mod;

        reverse(temp, temp + 2 * n + 1);
        NTT(temp, 1);
        for (int i = 0; i < limit; i++) temp[i] = (temp[i] * g[i]) % mod;
        NTT(temp, -1);
        for (int i = 0; i <= 2 * n; i++) temp[i] = temp[i] * rl % mod;
        reverse(temp, temp + 2 * n + 1);
        for (int i = 0; i <= 2 * n; i++) dp[i] = temp[i];
    }
    int res = 0;
    for (int i = 0; i <= 2 * n; i++) res = (res + dp[i]) % mod;
    printf("%lld", res);
}

H

无论还剩几个随从,随机到 AABB 的概率都是相等的,于是可以不考虑随从。

a=A10,b=B10a=\lceil\frac{A}{10}\rceil,b=\lceil\frac{B}{10}\rceil

i=0a1(b+i1i)×12b+i\sum_{i=0}^{a-1}\binom{b+i-1}{i}\times \frac{1}{2^{b+i}}

上述式子表示在第 i+bi+b 轮结束,其中“我”损失血量只能在前 i+b1i+b-1 轮,而每一轮的概率为 12\frac{1}{2}

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
const int N = 1e6 + 9;

int A, B;
long long inv[N], cur, ans;

int main() {
    scanf("%d", &A);
    for (int i = 0; i < 8; ++i) scanf("%d", &B);
    A = (A - 1) / 10 + 1;
    B = (B - 1) / 10 + 1;
    inv[1] = 1;
    for (int i = 2; i <= 1000000; ++i) inv[i] = (P - P / i) * inv[P % i] % P;
    cur = 1;
    for (int i = 1; i <= B; ++i) cur = cur * inv[2] % P;
    ans = cur;
    for (int i = B + 1; i < A + B; ++i) {
        cur = cur * (i - 1) % P * inv[i - B] % P * inv[2] % P;
        ans = (ans + cur) % P;
    }
    printf("%lld\n", ans);
    return 0;
}

I

等价于 ai+bl=aj+bka_i+b_l=a_j+b_k 。因为 ai,bj[107]a_i,b_j\in[10^7] ,所以 max{ai+bl}2×107\max\{a_i+b_l\}\leq 2\times 10^7 。首先特殊处理有重复元素的情况,剩下的根据鸽巢原理,保留 {b}\{b\} 的前 2×107n\lceil\frac{2\times 10^7}{n}\rceil 即可保证一定有至少两对和相等且下标不同。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 9;
const int M = 1e6 + 9;
int i, j, k, l, n, m, a[M], b[M], A, B, p1, p2, p3, p4, e[M], f[M];
int ais[N], bis[N];
int p[2 * N][2];
int main() {
    cin >> n >> m;
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (i = 1; i <= m; i++) scanf("%d", &b[i]);
    for (i = 1; i <= n; i++) {
        if (ais[a[i]]) {
            p2 = ais[a[i]], p1 = i;
        } else
            ais[a[i]] = i, e[++k] = i;
    }
    for (i = 1; i <= m; i++) {
        if (bis[b[i]]) {
            p4 = bis[b[i]], p3 = i;
        } else
            bis[b[i]] = i, f[++l] = i;
    }
    if (p1 && p3) {
        cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << '\n';
        return 0;
    }
    for (i = 1; i <= k; i++) {
        for (j = 1; j <= l; j++) {
            int x = a[e[i]] + b[f[j]];
            if (p[x][0]) {
                cout << e[p[x][0]] << ' ' << e[i] << ' ' << f[p[x][1]] << ' ' << f[j];
                return 0;
            } else
                p[x][0] = i, p[x][1] = j;
            ;
        }
    }
    cout << -1;
    return 0;
}

J

首先考虑排列的情况,并离散化使得 Ai=iA_i=i 。由于交换一次会使得逆序对奇偶性变化,所以直接判掉 (n2)\binom{n}{2}BB 逆序对奇偶性不同的情况。

然后进行归纳构造

  • 当存在 AuBuA_u\not =B_u 时,找到 Av=BuA_v=B_u ,依次操作 (u,i)(iu,v)(u,i)(i\not =u,v),最后操作 (u,v)(u,v) 。操作后 Au=BuA_u=B_u,并把问题变成 n1n-1 的子问题。
  • i,Ai=Bi\forall i,A_i=B_i ,根据有解必有 n%4=1,0n\%4=1,0 。那么假设 n4n\geq 4 , 依次进行 (1,5),(1,6)..(1,n),(1,2),(2,n),(2,n1)...(2,5)(1,5),(1,6)..(1,n),(1,2),(2,n),(2,n-1)...(2,5) ,此时交换了 1122 。再对 3,43,4 也进行上述操作,使得 3,43,4 的值也交换了。最后执行 (1,4),(2,3),(1,3),(2,4)(1,4),(2,3),(1,3),(2,4) 让四个元素归位,并删除了这四个点所有相邻的边,变成 n4n-4 的子问题。

而对于不是排列的情况,交换两个相等的元素,使得序列不变但是逆序对奇偶性变化从而一定有解。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 9;
int T, n, a[N], b[N], aa[N], bb[N], ok, v[N], c[N], cnt, p, x[N], t, q;
void opt(int x, int y) {
    if (x < y)
        printf("%d %d\n", x, y);
    else
        printf("%d %d\n", y, x);
    swap(c[x], c[y]);
}
void solve(int t) {
    if (t < 4)
        return;
    t -= 4;
    for (int i = 1; i <= t; i++) opt(x[i], x[t + 1]);
    for (int i = t + 1; i; i--) opt(x[i], x[t + 2]);
    for (int i = 1; i <= t; i++) opt(x[i], x[t + 3]);
    for (int i = t + 3; i; i--)
        if (i != t + 2 && i != t + 1)
            opt(x[i], x[t + 4]);
    opt(x[t + 1], x[t + 3]);
    opt(x[t + 2], x[t + 4]);
    opt(x[t + 1], x[t + 4]);
    opt(x[t + 2], x[t + 3]);
    solve(t);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
        for (int i = 1; i <= n; i++) v[i] = c[i] = 0;
        ok = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                if (!v[j] && a[i] == b[j]) {
                    v[j] = 1;
                    c[i] = j;
                    break;
                }
            if (!c[i]) {
                printf("NO\n");
                ok = 0;
                break;
            }
        }
        if (!ok)
            continue;
        cnt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; j++)
                if (c[j] > c[i])
                    cnt++;
        if ((cnt + n * (n - 1) / 2) % 2 != 0) {
            ok = 0;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j < i; j++)
                    if (ok == 0 && b[c[i]] == b[c[j]]) {
                        ok = 1;
                        swap(c[i], c[j]);
                    }
            if (!ok) {
                printf("NO\n");
                continue;
            }
        }
        printf("YES\n");
        for (int i = 1; i <= n; i++) v[i] = 0;
        for (int i = 1; i <= n; i++) {
            p = 0;
            for (int j = 1; j <= n; j++)
                if (c[j] != j)
                    p = j;
            if (p == 0) {
                t = 0;
                for (int j = 1; j <= n; j++)
                    if (!v[j])
                        x[++t] = j;
                solve(t);
                break;
            } else {
                for (int j = 1; j <= n; j++)
                    if (c[j] == p)
                        q = j;
                v[p] = 1;
                for (int j = 1; j <= n; j++)
                    if (!v[j] && j != q)
                        opt(j, p);
                opt(q, p);
            }
        }
    }
    return 0;
}

K

当点权范围只有 [1,k][1,k] 的时候,可以状压 f(x,S)f(x,S) 表示以 xx 为根的子树,选了的颜色集合为 SS 的最大权值。时间复杂度 O(n×3k)\mathcal O(n\times 3^k)

那么给每一种原本的权值随机一个新的权值 [1,k][1,k] 。随机后得到的一组合法解,在随机前也一定是合法解。设最优答案的 kk 个颜色随机后仍然互不相同,概率为 k!kk\frac{k!}{k^k}k=5k=5 时为 0.03840.0384 。多随机几次即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 9;
int f[N][(1 << 5) + 10];
struct node {
    int v, w;
};
vector<node> g[N];
int pos[N], a[N];
int res, n, k;
;
void dfs(int u, int fa) {
    f[u][0] = 0;
    f[u][1 << (pos[a[u]])] = 0;
    for (auto X : g[u]) {
        int v = X.v, w = X.w;
        if (v == fa) {
            continue;
        }
        dfs(v, u);
        for (int i = (1 << k) - 1; i >= 1; i--) {
            for (int j = i; j; j = (j - 1) & i) {
                f[u][i] = max(f[u][i], f[u][i - j] + f[v][j] + w);
                if (i - j) {
                    res = max(res, f[u][i - j] + f[v][j] + w);
                }
            }
        }
    }
}
signed main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1, u, v, w; i < n; i++) {
        scanf("%lld%lld%lld", &u, &v, &w);
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    int t = 200;
    while (t--) {
        memset(f, -0x3f, sizeof(f));
        for (int i = 1; i <= n; i++) pos[i] = rand() % k;
        dfs(1, 0);
    }
    printf("%lld\n", res);
    return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐