2020 ACM - ICPC nanjing 南京站 题解（10 / 13）

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

比赛链接：https://codeforces.com/gym/102992

• A. 构造
• D. 图论
• E. 构造，爆搜
• F. 期望，三分
• H. 抽屉原理，爆搜打表，组合计数
• I. 计算几何
• J. 博弈论，吉司机线段树
• K. 数论，签到
• L. 思维，签到
• M. 树上背包 $O(n^2)$

A、Ah, It’s Yesterday Once More

Problem

对于给定的 $n\times m$ 的方格，$0$ 代表障碍，$1$ 代表袋鼠。有一串随机生成的长为 $5\times 10^4$的指令，仅包含 $\text{LRUD}$ 字符，分别表示将所有袋鼠同时向某个方向移动（若能移动，即不经过障碍、不超出方格范围）。现要求构造一个 $n\times m$ 方格图，使得对于随机生成的 $500$ 串指令，至少有 $125$ 个满足执行后，所有袋鼠不都在同一个方格。要求构造的袋鼠方格连通、且不含环。

$1\le n,m\le 20$。

Solution

我们只需要执行 $\frac{1}{4}$ 的指令执行即可，也就是每只袋鼠至少有一个方向是墙，所以我们可以构造一个不对称的路径，以及一些分岔路口，例如一些 Z 字形路径。注意袋鼠们必须连通以及不能有环。

#include<bits/stdc++.h>
using namespace std;

int main(){
    char ans[21][21] = {
    "20 20",
    "11011111011111011111",
    "10110100110100110100",
    "11101101101101101101",
    "10011011011011011001",
    "10110110110110110111",
    "01101101101101101101",
    "11011011011011011011",
    "10110110110110110110",
    "11101101101101101101",
    "10011011011011011001",
    "10110110110110110111",
    "01101101101101101101",
    "11011011011011011011",
    "10110110110110110110",
    "11101101101101101101",
    "10011011011011011001",
    "10110110110110110111",
    "01101101101101101101",
    "01011001011001011001",
    "11110111110111110111",
    };
    for(int i = 0; i <= 20; ++i){

        cout << ans[i] << endl;
    }
    return 0;
}

D、Degree of Spanning Tree

Problem

给出一个无向图，寻找它的一棵生成树，要求生成树上每个点的度数都要小于等于 $\frac{n}{2}$ 。

Solution

首先随便找到一棵生成树，寻找它度数最大的点，在所有节点中，度数大于 $\frac{n}{2}$ 的节点最多只有一个，若找不到直接输出，找到了则令其为根节点，对所有不在生成树上的边进行枚举，若这条边的起点终点在树上的lca是根节点，则说明这条边的加入可以令根节点度数-1，但是在两个点都是根节点的儿子节点的情况下，会令选择的另一边的节点度数+1，所以在删边加边的过程中要判断是否会导致其他节点度数大于 $\frac{n}{2}$。

动态加边删边求lca实在是不会…但是还好可以用并查集来做，首先将根节点的所有子树各自构成集合，集合祖先为根节点的儿子节点，每次遍历边查询两端点是否在同一集合即可。

Code

#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;

vector<pair<int,int>> es;
map<pair<int,int>,int> mp;
struct Edge{
    int to,nxt;
}edges[maxn << 2];

int head[maxn], idx;
int deg[maxn];
void add(int u,int v)
{
    edges[idx] = {v,head[u]}, head[u] = idx++;
    edges[idx] = {u,head[v]}, head[v] = idx++;
}
int pre[maxn];
int chose[maxn];

int fi(int x) {return x == pre[x] ? x : pre[x] = fi(pre[x]);}

void dfs(int u,int fa, int sig)
{
    pre[u] = sig;
    for(int i = head[u];~i;i = edges[i].nxt){
        int v = edges[i].to;
        if(v == fa) continue;
        dfs(v,u,sig);
    }
}

void init(int n,int m)
{
    mp.clear();
    es.clear();
    for(int i = 0;i <= n;++i){
        head[i] = -1;
        deg[i] = 0;
        pre[i] = i;
    }
    for(int i = 0;i <= m;++i){
        chose[i] = 0;
    }
    idx = 0;
}

int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d %d",&n,&m);
        init(n,m);
        for(int i = 0;i < m;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            if(u > v) swap(u,v);
            es.push_back({u,v});
        }
        sort(es.begin(),es.end());
        es.erase(unique(es.begin(),es.end()),es.end());
        m = static_cast<int>(es.size()); // 删除重边自环
        for(int i = 0;i < m;++i){
            int u = es[i].first;
            int v = es[i].second;
            mp[{u,v}] = mp[{v,u}] = i;
            int fu = fi(u),fv = fi(v);
            if(fu != fv){ 
                add(u,v);		//kruskal 建生成树
                pre[fu] = fv;
                deg[u]++;
                deg[v]++;
                chose[i] = 1;
            }
        }
        int flag = 0;
        for(int i = 2;i <= n;++i){
            if(fi(i) != fi(1))  flag = 1;
        }
        if(flag) {
            puts("No");
            continue;
        }

        int rt = -1;
        for(int i = 1;i <= n;++i){
            if(deg[i] > n/2){
                rt = i;
                break;
            }
        }
        if(rt == -1){
            puts("Yes");
            for(int i = 0;i < m;++i){
                if(chose[i]){
                    printf("%d %d\n",es[i].first,es[i].second);
                }
            }
            continue;
        }
        for(int i = 1;i <= n;++i) pre[i] = i;
        for(int i = head[rt];~i;i = edges[i].nxt){
            dfs(edges[i].to,rt,edges[i].to);
        }
        for(int i = 0;i < m;++i){
            if(chose[i]) continue;
            int u = es[i].first, v = es[i].second;
            int fu = fi(u), fv = fi(v);
            if(fu == fv || u == rt || v == rt) continue;
            deg[rt]--;
            deg[u]++;
            deg[v]++;
            deg[fu]--;
            if(deg[u] > n/2 || deg[v] > n/2){	//检测是否可行，不可行就恢复
                deg[fu]++;
                deg[fv]--;
                if(deg[u] > n/2 || deg[v] > n/2){
                    deg[rt]++;
                    deg[u]--;
                    deg[v]--;
                    deg[fv]++;
                    continue;
                }
                else{
                    pre[fv] = fu;
                    chose[i] = 1;
                    chose[mp[{rt,fv}]] = 0;
                }
            }
            else{
                pre[fu] = fv;
                chose[i] = 1;
                chose[mp[{rt,fu}]] = 0;
            }
            if(deg[rt] <= n/2) break;
        }
        if(deg[rt] <= n/2){
            puts("Yes");
            for(int i = 0;i < m;++i){
                if(chose[i]){
                    printf("%d %d\n",es[i].first,es[i].second);
                }
            }
        }
        else puts("No");
        
    }

    return 0;
}

E、Evil Coordinate

Problem

在一个直角坐标系中，给定起点 $(0,0)$，一个障碍 $(m_x,m_y)$ 以及一串长度为 $n$ 的指令，仅包含 $\text{L?/?R?/?U?/?D}$ 字符，分别表示向左右上下移动，请你调整指令顺序让移动过程不经过 $(m_x,m_y)$，有解输出指令字符，无解输出 $\text{impossible}$ 。

$1\le n\le 10^5,?10^9\le m_x,m_y\le 10^9,\sum n_i\le 10^6$ 。

Solution

开始想的是左右走完，然后上下，发现可以先上下再左右，然后又发现反例，然后也可以先左再上再下再右，明白了，所有的方向排列一共有 $4!=24$ 种，直接求全排列，然后对于每一个排列，分别判断即可。

最后注意 ios 加速之后 puts 就不能用了…

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;

bool cal(int x,int y, int l,int r,int u, int d,vector<int> v)
{
    string res;
    for(int i = 0;i < v.size();++i){
        if(v[i] == 1) while(l--) res.push_back('L');
        if(v[i] == 2) while(r--) res.push_back('R');
        if(v[i] == 3) while(u--) res.push_back('U');
        if(v[i] == 4) while(d--) res.push_back('D');
    }
    int flag = 0;
    int nx = 0,ny = 0;
    for(int i = 0;i < res.size();++i){
        if(res[i] == 'L') nx--;
        if(res[i] == 'R') nx++;
        if(res[i] == 'U') ny++;
        if(res[i] == 'D') ny--;
        if(nx == x && ny == y){
            flag = 1;
        }
    }
    if(!flag) {
        cout<<res<<endl;
        return 1;
    } 
    else return 0;
}


int main()
{
    int t;
    cin>>t;
    while(t--){
        int x,y;
        cin>>x>>y;
        string s;
        cin>>s;
        int l,r,u,d;
        l = r = u = d = 0;
        int nx = 0,ny = 0;
        int flag = 0;
        for(int i = 0;i < s.size();++i){
            if(s[i] == 'L') l++,nx--;
            if(s[i] == 'R') r++,nx++;
            if(s[i] == 'U') u++,ny++;
            if(s[i] == 'D') d++,ny--;
            if(nx == x && ny == y){
                flag = 1;
            }
        }

        if((x == 0 && y == 0) || (x == nx && y == ny)){
            puts("Impossible");
            continue;
        } 
        vector<int> v = {1,2,3,4};
        flag = 0;
        do{
            if(cal(x,y,l,r,u,d,v)){
                flag = 1;
                break;
            }
        }while(next_permutation(v.begin(),v.end()));
        if(!flag) puts("Impossible");
        
    }

    return 0;
}

F、Fireworks

Problem

制作一支烟花需要花费 $n$ 分钟，每支烟花有 $p\times 10^{?4}$的概率是完美的，每次可以花费 $m$ 分钟点燃之前制作的所有烟花，若发现至少有一支完美的，则停止。问最优策略下，最短的停下的时间期望是多少？

多组数据，$1\le T\le 10^4,1\le n,m\le 10^9,1\le p\le 10^4$ 。

Solution

不是完美烟花的概率 $q=1?(p\times 10^{?4})$，假设最优策略为连续制作 $k$ 支烟花后花费 $m$ 的时间一次全部点燃，若发现有完美烟花则停止，若没有则回到初始状态，继续执行最优策略，发现实际上求的就是期望最早第几次成功，也就是前 $k?1$ 次失败，第 $k$ 次成功发现只有两种情况，显然服从几何分布（前 $k?1$ 次失败，第 $k$ 次成功 ），即 $n$ 重伯努利实验的几何概型，根据几何概型的期望公式得： $E(X)=\frac{1}{1?q^k}$，期望时间为 $f(k)=\frac{n\times k+m}{1?q^k}$ ，显然答案就是峰值，打表发现这是一个单峰函数，直接三分答案即可，或者也可以二分 + 求导。

Code

#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-9;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;

int n, m, t;
double p;

double qpow(double a, ll b)
{
    double res = 1;
    while(b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

double f(double k)
{
    double ans = 0;
    double up = k * n + m;
    double down = 1 - qpow((1 - p), k);
    return up / down;
}

void solve()
{
    scanf("%d%d%lf", &n, &m, &p);
    p /= 10000.0;
    ll l = 1, r = 1e18;
    while(r - l > 2) {
        ll x = (2 * l + r) / 3;
        ll y = (2 * r + l) / 3;
        //cout << l << " " << r <<endl;
        if(f(x) < f(y) + eps) r = y;
        else l = x;
    }
    printf("%.10f\n", min({f(l), f(l + 1), f(l - 1), f(l + 2)}));
}
/*
3
1 1 5000
1 1 1
1 2 10000
*/
int main()
{
    scanf("%d", &t);
    while(t -- ) {
        solve();
    }
}

H、Harmonious Rectangle

Problem

定义 Harmonious Rectangle 为一个矩形内存在
$$\begin{gathered} \{\begin{array}{l}\text{color}(x_1,y_1)=\text{color}(x_1,y_2)\\ \text{color}(x_2,y_1)=\text{color}(x_2,y_2)\end{array} \\ 或 \\ \{\begin{array}{l}\text{color}(x_1,y_1)=\text{color}(x_2,y_1)\\ \text{color}(x_1,y_2)=\text{color}(x_2,y_2)\end{array} \end{gathered}$$

其中这四个点是矩形的端点。 问一个 $n\times m$ 的矩阵，每个点可以涂 $0，1，2$ 三种颜色，存在多少种矩阵是和谐矩阵。

$n,m\le 3000$

Solution

凭感觉可知 $n$ 和 $m$ 大于某个数后，一定全都含有和谐矩阵，（不然就没法玩了 ，如果后面数据大，答案不是公式那将毫无意义 ）即任意一种染色的方案都有贡献，即答案就是染色总方案，每个格子有三种颜色可选，总方案为 $3^{n\times m}$，然后爆搜找边界就行了。

或者说使用抽屉原理，三种颜色，任意一组 $(a,b)$ 每个都有三种选择，一共有 $3\times 3=9$ 种，根据抽屉原理，若 m a x { n , m } > 9 max\{n,m\}>9 max{n,m}>9 则无论怎么排列，都一定存在 和谐矩形。

可以在线搜索所有非法矩阵，枚举当前点是否可以放某个颜色的点，将爆搜优化到 $3^n{n}^2$，对 $9\times 9$ 以下的矩阵达打表输出即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int res = 0;


int mat[9][9] = {{3,9,27,81,243,729,2187,6561},
                    {9,66,390,1800,6120,13680,15120,0},
                    {27,390,3198,13176,27000,13680,15120,0},
                    {81,1800,13176,24336,4320,0,0,0},
                    {243,6120,27000,4320,4320,0,0,0},
                    {729,13680,13680,0,0,0,0,0},
                    {2187,15120,15120,0,0,0,0,0},
                    {6561,0,0,0,0,0,0,0}};
void dfs(int cur,int n,int m)	//爆搜打表代码
{
    if(cur == n * m){
        res++;
        return ;
    }
    for(int col = 0;col < 3;++col){
        int x = cur / m;
        int y = cur % m;
        bool flag = 1;
        for(int i = 0;i < x && flag;++i){
            for(int j = 0;j < y && flag;++j){
                if(mat[i][y] == mat[i][j] && mat[x][j] == col){
                    flag = 0;
                    break;
                }
                if(mat[i][y] == col && mat[i][j] == mat[x][j]){
                    flag = 0;
                    break;
                }
            }
        }
        mat[x][y] = col;
        if(flag)dfs(cur + 1, n, m);
    }
}

ll qpow(ll a, ll b)
{
    ll res = 1;
    while(b){
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    int  t;
    cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        if(n == 1 || m == 1) puts("0");
        else if(n < 9 && m < 9){
            printf("%lld\n",(qpow(3,n*m)-mat[n-1][m-1]+mod) % mod);
        }
        else{
            printf("%lld\n",qpow(3,n*m));
        }
    }
   return 0;
}

I、Interested in Skiing

Problem

二维平面 $[?m,m]\times \mathbb{R}$ 上有 $n$ 条线段作为障碍，以端点坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$ 表示，起点为 $(0,?\inf )$ 的一个点以 $v_y$的速度向 $\text{y}$ 轴正方向移动，终点为 $(0,\inf )$ 。求最小的 $v_x^{?}$，使得当水平速度 $v_x>v_x^{?}$ 时，能从起点移动到终点，无解则输出 $?1$ 。

$1\le n\le 100,1\le m\le 10^4,1\le v_y\le 10,?m\le x_1,x_2\le m,?10^{?4}\le y_1,y_2\le 10^4$。

J - Just Another Game of Stones

Problem

给定一个长度为 $n$ 的数组 $a_i$ ，有 $q$ 次操作：

$1lrx$ ，表示令 a i = max ? { a i , x } , i ∈ [ l , r ] a_i = \max\{a_i, x\}, i \in [l, r] ai?=max{ai?,x},i∈[l,r]。

$2lrx$ ，表示询问用 $[l,r]$ 的石堆和额外的一堆有 $x$ 个石子的石堆一起，进行 $\text{Nim}$ 博弈的必胜情况的第一步操作种数。

$1\le n,q\le 2\times 10^5,1\le l,r\le n,0\le a_i,x<2^{30}?1$。

Solution

经典 $\text{Nim}$ 博弈，若所有石子堆的石子数量的异或和为 $0$ 则先手必败，否则先手必胜。那么我们假设当前区间异或和为 $S$，显然我们想要必胜，只需要取石子使得当前状态变为必败态送给对手，即在一堆里取石子，使得异或和变为 $0$ ，显然有结论：对于一个石子数量为 $a_i$ 的石堆，取走 $a_i?a_i\oplus S$ 个石子，使得异或和 $S$ 变为 $0$。也就是说若当前结点权值 $a_i$，当 $a_i\ge a_i\oplus S$ ，则对该石子堆进行修改，即为一种合法的操作。故答案（总操作种数）即为区间里 $a_i\ge a_i\oplus S$ 的结点的数量。显然异或是不进位的加法，即我们只需要考虑，对于当前区间的异或和 $S$ ，$S$ 的最高位 $1$，若 $a_i$ 在该最高位也是 $1$ ，则必有 $a_i\ge a_i\oplus S$ ，反之一定不成立。

这个题主要就是看会不会SGB,如果会的话就很简单了。对于opt 1可以用SegmentTreeBeats的操作进行维护，对于opt 2可以考虑为线段树的每个节点维护区间异或和，并开一个桶记录每个位对应个数。向上合并的时候直接暴力合并就行了。总体复杂度 $O(nlogn\times 30)$

记得考虑操作 2 加进来的石头…

Code

 #include <bits/stdc++.h>
 
 using namespace std;
 using ll = long long ;
 const int maxn = 2e5+5;
 
 struct node
 {
 	ll mi;
 	ll smi;
 	ll xsum;
 	ll cntmi;
 	ll cnt[31];
 	ll tag;
 }tree[maxn*4];
 ll a[maxn];
 
 struct Segment_tree_beats
 {
 
 	void pushup(int rt){
 		if(tree[rt<<1].mi < tree[rt<<1|1].mi){
 			tree[rt].mi = tree[rt<<1].mi;
 			tree[rt].cntmi = tree[rt<<1].cntmi;
 			tree[rt].smi = min(tree[rt<<1].smi,tree[rt<<1|1].mi);
 			tree[rt].xsum = tree[rt<<1].xsum^tree[rt<<1|1].xsum;
 			for(int i = 0;i <= 30;++i)tree[rt].cnt[i] = tree[rt<<1].cnt[i]+tree[rt<<1|1].cnt[i];
 		}
 		else if(tree[rt<<1].mi > tree[rt<<1|1].mi){
 			tree[rt].mi = tree[rt<<1|1].mi;
 			tree[rt].cntmi = tree[rt<<1|1].cntmi;
 			tree[rt].smi = min(tree[rt<<1|1].smi,tree[rt<<1].mi);
 			tree[rt].xsum = tree[rt<<1|1].xsum^tree[rt<<1].xsum;
 			for(int i = 0;i <= 30;++i)tree[rt].cnt[i] = tree[rt<<1].cnt[i]+tree[rt<<1|1].cnt[i];
 		}
 		else{
 			tree[rt].mi = tree[rt<<1].mi;
 			tree[rt].cntmi = tree[rt<<1].cntmi+tree[rt<<1|1].cntmi;
 			tree[rt].smi = min(tree[rt<<1].smi,tree[rt<<1|1].smi);
 			tree[rt].xsum = tree[rt<<1].xsum^tree[rt<<1|1].xsum;
 			for(int i = 0;i <= 30;++i)tree[rt].cnt[i] = tree[rt<<1].cnt[i]+tree[rt<<1|1].cnt[i];
 		}
 	}
 
 	void pushtag(int rt,int val){
 		if(tree[rt].mi >= val)return;
 		if(tree[rt].cntmi&1){
 			tree[rt].xsum^=tree[rt].mi;
 			tree[rt].xsum^=val;
 		}
 		for(int i = 0;i <= 30;++i){
 			if(tree[rt].mi>>i&1)tree[rt].cnt[i]-=tree[rt].cntmi;
 			if(val>>i&1)tree[rt].cnt[i]+=tree[rt].cntmi;
 		}
 		tree[rt].mi = val;
 		tree[rt].tag = val;
 	}
 	void pushdown(int rt){
 		if(tree[rt].tag==-1)return;
 		pushtag(rt<<1,tree[rt].tag),pushtag(rt<<1|1,tree[rt].tag);
 		tree[rt].tag = -1;
 	}
 
 	void build(int rt,int l,int r){
 		tree[rt].tag = -1;
 		if(l==r){
 			tree[rt].mi = a[l];
 			tree[rt].xsum = a[l];
 			tree[rt].cntmi = 1;
 			tree[rt].smi = 1e18;
 			for(int j = 0;j <= 30;++j){
 				if(a[l]>>j&1)tree[rt].cnt[j]++;
 			}
 			return;
 		}
 		int mid = l+r>>1;
 		build(rt<<1,l,mid);
 		build(rt<<1|1,mid+1,r);
 		pushup(rt);
 	}
 
 	void modify_max(int rt,int l,int r,int ql,int qr,int val){
 		if(tree[rt].mi >= val)return;
 		if(l >= ql&& r<= qr&&tree[rt].smi > val){
 			pushtag(rt,val);
 			return;
 		}
 		pushdown(rt);
 		int mid = l+r>>1;
 		if(ql <= mid)modify_max(rt<<1,l,mid,ql,qr,val);
 		if(qr > mid)modify_max(rt<<1|1,mid+1,r,ql,qr,val);
 		pushup(rt);
 	}
 	int querysum(int rt,int l,int r,int ql,int qr){
 		if(l >= ql&& r <= qr){
 			return tree[rt].xsum;
 		}
 		pushdown(rt);
 		int mid = l+r>>1;
 		int sum = 0;
 		if(ql <= mid)sum^=querysum(rt<<1,l,mid,ql,qr);
 		if(qr > mid)sum^=querysum(rt<<1|1,mid+1,r,ql,qr);
 		return sum;
 	}
 	int querybit(int rt,int l,int r,int ql,int qr,int bit){
 		if(l >= ql&& r <= qr){
 			return tree[rt].cnt[bit];
 		}
 		pushdown(rt);
 		int mid = l+r>>1;
 		int sum = 0;
 		if(ql <= mid)sum+=querybit(rt<<1,l,mid,ql,qr,bit);
 		if(qr > mid)sum+=querybit(rt<<1|1,mid+1,r,ql,qr,bit);
 		return sum;
 	}
 }sgb;
 
 int main()
 {
 	int n,m;
 	scanf("%d%d",&n,&m);
 	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);
 	sgb.build(1,1,n);
 	while(m--){
 		int opt,l,r,val;
 		scanf("%d%d%d%d",&opt,&l,&r,&val);
 		if(opt==1){
 			sgb.modify_max(1,1,n,l,r,val);
 		}
 		else{
 			ll xsum = sgb.querysum(1,1,n,l,r);
 			xsum^=val;
 			int mx = -1;
 			for(int j = 30;j >= 0;--j){
 				if(xsum>>j&1){
 					mx = j;
 					break;
 				}
 			}
 			if(mx==-1)printf("0\n");
 			else{
 				printf("%d\n",sgb.querybit(1,1,n,l,r,mx)+(val>>mx&1));
 			}
 		}
 	}
 	return 0;
 }

K、K Co-prime Permutation

Problem

给定 $n$ 和 $k$ ，构造一个排列 $p_i$ 使得 $\gcd (p_i,i)=1$ 的 $i$ 的个数恰有 $k$ 个，无解输出 $?1$ 。

$1\le n\le 10^6,0\le k\le n$。

Solution

显然相邻的两个自然数互质，相邻的两个奇数互质。具体细节看代码即可。

#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;

int n ,m, k;

int main()
{

    scanf("%d%d", &n, &k);
    if(k == 0) {
        puts("-1");
        return 0;
    }
    if(k == 1) {
        for(int i = 1; i <= n; ++ i)
        cout << i << " ";
        return 0;
    } 
    for(int i = 1; i < k; ++ i) {
        cout << i + 1 << " ";
    }
    cout << "1 ";
    for(int i = k + 1; i <= n; ++ i) {
        cout << i << " ";
    }
    puts("");
    return 0;
}

L、Let’s Play Curling

Problem

给定长度为 $n$ 的数组 $a_i$ 和长度为 $m$ 的数组$b_i$，对于一个数 $c$ ，若 $a_i$满足对于所有 $j$ ，$|c?a_i|<|c?b_j|\mid$ 则得分加 $1$ ，最终得分 $f(c)$ 为满足的 $i$ 的个数，求最大的 $f(c)$ 。

Solution

显然两个 $b$ 之间的数量最多的 $a$ 的个数就是答案。

#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;

int a[maxn],b[maxn];

int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
    ios;
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i = 1;i <= n;++i){
            cin>>a[i];
        }
        for(int i = 1;i <= m;++i){
            cin>>b[i];
        }
        b[0] = -inf;
        b[m + 1] = inf;
        sort(a+1,a+n+1);
        sort(b,b + m + 1);
        int res = 0;
        for(int i = 0;i <= m;++i){
            int l = upper_bound(a+1,a+n+1,b[i]) - a;
            int r = lower_bound(a+1,a+n+1,b[i+1]) - a - 1;
            res = max(r - l + 1, res);
        }
        if(!res) puts("Impossible");
        else printf("%d\n",res);
    }

    return 0;
}

M、Monster Hunter

树上背包可以做到 $O(n^2)$

#include <bitsdc++.h>
using namespace std;

using ll = long long;
const int maxn = 2003;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dp[maxn][maxn][2];
int sz[maxn];
int a[maxn];
int n;
ll sum = 0;
vector<int>v[maxn];

void dfs(int now)
{
    sz[now] = 1;
    if(now!=1)sum += a[now]*2;
    else sum += a[now];
    dp[now][0][0] = 0;
    if(now!=1)
    dp[now][1][1] = 2*a[now];
    else dp[now][1][1] = a[now];
    dp[now][1][0] = -inf;
    dp[now][0][1] = -inf;
    if(v[now].size()==0){
        return;
    }
    for(int i = 0;i < v[now].size();++i){
        dfs(v[now][i]);
        for(int p = 0;p < 2;++p){
            for(int j = sz[now];j >= p;--j){
                for(int k = sz[v[now][i]];k >= 0;--k){
                    if(p==0){
                        dp[now][j+k][p] = max(dp[now][j+k][p],dp[now][j][p]+max(dp[v[now][i]][k][0],dp[v[now][i]][k][1]));
                    }
                    else{
                        long long tmp = dp[now][j][p]+dp[v[now][i]][k][0]+a[v[now][i]];
                        tmp = max(tmp,dp[now][j][p]+dp[v[now][i]][k][1]);
                        dp[now][j+k][p] = max(dp[now][j+k][p],tmp);
                    }
                }
            }
        }
        sz[now] += sz[v[now][i]];
    }
}

void solve()
{
    sum = 0;
    scanf("%d",&n);
    for(int i = 0;i <= n;++i){
        for(int j = 0;j <= n;++j)
        {
            for(int p = 0;p < 2;++p)dp[i][j][p] = -inf;
        }
    }
    for(int i = 1;i <= n;++i)v[i].clear();
    for(int i = 2,a;i <= n;++i){
        scanf("%d",&a);
        v[a].push_back(i);
    }
    for(int i = 1;i <= n;++i)scanf("%d",&a[i]);
    dfs(1);
    for(int i = 0;i <= n;++i){
        printf("%lld%c",sum-max(dp[1][i][0],dp[1][i][1]),i==n?'\n':' ');
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
}