2020 ACM - ICPC nanjing 南京站题解（10 / 13）_小言_互联网的博客

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

2021-04-14 18:56 340人阅读评论(0)

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

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

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

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

A、Ah, It’s Yesterday Once More

Problem

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

$\le n, m \le 20$ 。

Solution

我们只需要执行 $\cfrac{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

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

Solution

首先随便找到一棵生成树，寻找它度数最大的点，在所有节点中，度数大于 $\cfrac{n}{2}$ 的节点最多只有一个，若找不到直接输出，找到了则令其为根节点，对所有不在生成树上的边进行枚举，若这条边的起点终点在树上的lca是根节点，则说明这条边的加入可以令根节点度数-1，但是在两个点都是根节点的儿子节点的情况下，会令选择的另一边的节点度数+1，所以在删边加边的过程中要判断是否会导致其他节点度数大于 $\cfrac{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$ 分钟，每支烟花有 $\times 10^{-4}$ 的概率是完美的，每次可以花费 $m$ 分钟点燃之前制作的所有烟花，若发现至少有一支完美的，则停止。问最优策略下，最短的停下的时间期望是多少？

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

Solution

不是完美烟花的概率 $\times 10^{-4})$ ，假设最优策略为连续制作 $k$ 支烟花后花费 $m$ 的时间一次全部点燃，若发现有完美烟花则停止，若没有则回到初始状态，继续执行最优策略，发现实际上求的就是期望最早第几次成功，也就是前 $k - 1$ 次失败，第 $k$ 次成功发现只有两种情况，显然服从几何分布（前 $k - 1$ 次失败，第 $k$ 次成功），即 $n$ 重伯努利实验的几何概型，根据几何概型的期望公式得： $\cfrac{1}{1 - q^k}$ ，期望时间为 $\cfrac{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{cases} color (x_{1}, y_{1}) = color (x_{1}, y_{2}) \\ color (x_{2}, y_{1}) = color (x_{2}, y_{2}) \end{cases}

$\begin{cases} \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{cases}$ \\或\\

{\begin{cases} color (x_{1}, y_{1}) = color (x_{2}, y_{1}) \\ color (x_{1}, y_{2}) = color (x_{2}, y_{2}) \end{cases}

$\begin{cases} \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{cases}$

{color (x_{1}, y_{1}) = color (x_{1}, y_{2}) color (x_{2}, y_{1}) = color (x_{2}, y_{2}) 或 {color (x_{1}, y_{1}) = color (x_{2}, y_{1}) color (x_{1}, y_{2}) = color (x_{2}, y_{2})

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

$n,m\le 3000$

Solution

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

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

可以在线搜索所有非法矩阵，枚举当前点是否可以放某个颜色的点，将爆搜优化到 $3^nn^2$ ，对 $\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

二维平面 $\times \mathbb{R}$ 上有 $n$ 条线段作为障碍，以端点坐标 $x_1, y_1)$ 和 $x_2, y_2)$ 表示，起点为 $-\inf)$ 的一个点以 $v_y$ 的速度向 $\text{y}$ 轴正方向移动，终点为 $\inf)$ 。求最小的 $v_x^*$ ，使得当水平速度 $v_x \gt v_x^*$ 时，能从起点移动到终点，无解则输出 $- 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$ 次操作：

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

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

$\le n, q \le 2 \times 10^5, 1 \le l, r \le n, 0 \le a_i, x \lt 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$ 。

$\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$ ， $\vert c - a_i \vert \lt \vert c - b_j \vert∣$ 则得分加 $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();
    }
}

转载：https://blog.csdn.net/weixin_45697774/article/details/114681396

查看评论

小言_互联网的博客

小言_互联网的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章