2020ICPC南京站补题题解

本文主要是介绍2020ICPC南京站补题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

菜鸡只写银牌以下的题
这场铜牌4题，银牌5~6题

K Co-prime Permutation

题意：
构造一个n长的1到n不重复序列p，其中 $p_i$ 和 $i$ 互质的个数有k个

思路：
已知： $n$ 和 $n - 1$ 互质，1和任何数互质，任何数和它本身不互质

k要是奇数，1不变，后面的 $\frac{k-1}{2}$ 对数，两两换位
k要是偶数，从1开始所有的 $\frac{k}{2}$ 对数，两两换位

代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=200005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
int p[maxn];
int l[maxn],r[maxn];int main()
{//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);int n,k;cin>>n>>k;int ans;if(k == 0)cout<<-1<<endl;else{if(k & 1){for(int i = 1;i <= k;i++){if(i == 1)cout<<1<<" ";else{if(i % 2 == 0)cout<<i+1<<" ";elsecout<<i-1<<" ";}}}else{for(int i = 1;i <= k;i++){if(i%2){cout<<i+1<<" ";}elsecout<<i-1<<" ";}}for(int i = k+1;i<= n;i++){if(i == n)cout<<i<<endl;elsecout<<i<<" ";}}return 0;
}

L Let’s Play Curling

题意：
当红队某个球到目标位置c的距离比蓝队所有的球到目标位置的距离都要小时，计一分，找到一个c点可以让红队尽可能多赢，输出红队尽可能多赢的次数。

思路：
思维，两个蓝队石头间最多有几个红色石头。

另外lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=200005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;ll a[maxn],b[maxn];int main()
{//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);ios::sync_with_stdio(false); cin.tie(0);int t,n,m;cin>>t;while(t--){cin>>n>>m;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i = 1 ;i <= n; i++)cin>>a[i];for(int i = 1 ;i <= m; i++)cin>>b[i];sort(a + 1,a + 1 + n);sort(b + 1,b + 1 + m);b[0] = -INF;b[m+1] = INF;int ans = 0;for(int i = 1;i <= m + 1; i++){int l = upper_bound(a + 1,a + n + 1,b[i-1]) - a;int r = lower_bound(a + 1,a + n + 1,b[i]) - a;ans = max(ans,r - l );}//ans = max(ans,cnt);if(ans <= 0)cout<<"Impossible"<<endl;elsecout<<ans<<endl;}return 0;
}

E Evil Coordinate

题意：
有一个二维坐标系，
开始在(0,0)点，给定坐标(mx,my),
给定长度为n的字符串，只包含LRUD，对应上下左右，
现在你可以重排这个字符串，要求你按照重排的字符串走，
走的时候不能碰到(mx,my)点，
如果有解输出重排之后的字符串，
如果无解输出Impossible.

思路：
场上是分类讨论做的，当时觉得模拟太恶心了，然后赛后发现这个题有另一种简单解法。

因为不能碰到（mx，my）点，必然最终到达的点x，y中至少有一个点和这个点不同，先走不同的方向的点，再走相同的，所以能走到的时候，必定存在答案：相同的方向连续排在一起，枚举UDLR的全排列 $4!$ 就可以了。

先上训练时写的暴力

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=200005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
int vis[10];int main()
{//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);int t,x,y;cin>>t;string s;while(t--){string ans;string str;memset(vis,0,sizeof(vis));cin>>x>>y;cin>>s;for(int i = 0;i< s.size();i++){if(s[i] == 'L')vis[1]++;if(s[i] == 'R')vis[2]++;if(s[i] == 'U')vis[3]++;if(s[i] == 'D')vis[4]++; }int nx,ny;nx =vis[2] - vis[1];ny = vis[3] - vis[4];if((nx == x && ny ==y) || (x == 0 && y == 0)){cout<<"Impossible"<<endl;continue;}if(x != 0 && y!= 0){if(x != nx){for(int i = 0;i < vis[1] ;i++)ans += 'L';for(int i = 0;i < vis[2] ;i++)ans += 'R';for(int i = 0;i < vis[3] ;i++)ans += 'U';for(int i = 0;i < vis[4] ;i++)ans += 'D';cout<<ans<<endl;continue;}if(y != ny){for(int i = 0;i < vis[3] ;i++)ans += 'U';for(int i = 0;i < vis[4] ;i++)ans += 'D';for(int i = 0;i < vis[1] ;i++)ans += 'L';for(int i = 0;i < vis[2] ;i++)ans += 'R';cout<<ans<<endl;continue;}}if(x==0 || y == 0){if(x == 0){if(vis[1] != 0 || vis[2] != 0){if(vis[1] > vis[2]){for(int i = 0;i < vis[1];i++)ans += 'L';for(int i = 0;i < vis[3] ;i++)ans += 'U';for(int i = 0;i < vis[4] ;i++)ans += 'D';for(int i = 0;i < vis[2] ;i++)ans += 'R';}else{for(int i = 0;i < vis[2] ;i++)ans += 'R';for(int i = 0;i < vis[3] ;i++)ans += 'U';for(int i = 0;i < vis[4] ;i++)ans += 'D';for(int i = 0;i < vis[1] ;i++)ans += 'L';}}else{if(abs(ny) >= abs(y) && ny*y >0){cout<<"Impossible"<<endl;continue;}if(y>0){for(int i = 0;i < vis[4] ;i++)ans += 'D';for(int i = 0;i < vis[3] ;i++)ans += 'U';}else{for(int i = 0;i < vis[3] ;i++)ans += 'U';for(int i = 0;i < vis[4] ;i++)ans += 'D';}}}else{if(vis[3] != 0 || vis[4] != 0){if(vis[3] > vis[4]){for(int i = 0;i < vis[3] ;i++)ans += 'U';for(int i = 0;i < vis[1] ;i++)ans += 'L';for(int i = 0;i < vis[2] ;i++)ans += 'R';for(int i = 0;i < vis[4] ;i++)ans += 'D';}else{for(int i = 0;i < vis[4] ;i++)ans += 'D';for(int i = 0;i < vis[1] ;i++)ans += 'L';for(int i = 0;i < vis[2] ;i++)ans += 'R';for(int i = 0;i < vis[3] ;i++)ans += 'U';}}else{if(abs(nx) >= abs(x) && nx*x >0){cout<<"Impossible"<<endl;continue;}if(x > 0){for(int i = 0;i < vis[1] ;i++)ans += 'L';for(int i = 0;i < vis[2] ;i++)ans += 'R';}else{for(int i = 0;i < vis[2] ;i++)ans += 'R';for(int i = 0;i < vis[1] ;i++)ans += 'L';}}}cout<<ans<<endl;}     }return 0;
}

全排列做法：
组合数学中经常用到排列，这里介绍一个计算序列全排列的函数：next_permutation（start,end），和prev_permutation（start,end）。这两个函数作用是一样的，区别就在于前者求的是当前排列的下一个排列，后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”，我们可以把它理解为序列的字典序的前后。

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=200005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
int vis[10];
int a[4] = {0,1,2,3};
char c[4] = {'U','D','L','R'};
int dir[4][2] = {0,1,0,-1,-1,0,1,0};
string ans;
bool judge(int x,int y)
{ans.clear();int nx = 0,ny = 0;for(int i = 0;i < 4 ;i++){int cnt = vis[a[i]];while(cnt--){ans += c[a[i]];nx += dir[a[i]][0];ny += dir[a[i]][1];if(nx == x && ny == y)return false;}}return true;
}
int main()
{//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);int t,x,y;cin>>t;string s;while(t--){int f = 0;sort(a,a+4);memset(vis,0,sizeof(vis));cin>>x>>y;cin>>s;if(x == 0 && y == 0){cout<<"Impossible"<<endl;continue;}for(int i = 0;i < s.size();i++){if(s[i] == 'U')vis[0]++;if(s[i] == 'D')vis[1]++;if(s[i] == 'L')vis[2]++;if(s[i] == 'R')vis[3]++;}do{if(judge(x,y)){f = 1;break;}}while(next_permutation(a,a+4));            if(f)cout<<ans<<endl;elsecout<<"Impossible"<<endl;}return 0;
}

F Fireworks

题意：制作单个烟火需要n分钟，燃放需要m分钟，每个烟火有 $p*10^{-4}$ 的概率是完美的，求采用最优策略下的期望制作时间的最小值。

思路：
这个题目用到了概率论，该分布为几何分布，
在这里插入图片描述
设每一次燃放成功的概率为 $p^{'}$ ,最小花时间为 $\frac{1}{p'}\times t'$ ，设他每做 $k$ 个烟花燃放一次, $t'=k\times n+m,p'=1-(1-p)^k，$ 答案为 $\frac{k\times n+m}{1-(1-p)^k}$

对这个式子求了个导，大约看了下，是个先减后增的函数，那么对K三分求答案。
太久没写三分了，找了个板子。

inline void sanfen()
{while(r-l>eps){lmid=l+(r-l)/3;rmid=r-(r-l)/3;if(val(lmid)<val(rmid)) l=lmid;else r=rmid;}

代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=200005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
#define eps 1e-9
const int inf=1<<30;
double n,m,p;
int ans ;
double val(double x){return (x * n + m)*1.0 / (1.0-pow(1.0-p,x));
}inline void sanfen()
{double l = 0.0,r = 1e9;double lmid,rmid;while(r - l > eps){lmid = l + (r - l) / 3.0;rmid = r - (r - l) / 3.0;if(val(lmid) > val(rmid)) l = lmid;else r = rmid;}ans = l;
}int main()
{//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);int t;cin>>t;while(t--){cin>>n>>m>>p;p = p * 0.0001;sanfen();// ans = min(val(ans), val(ans+1));printf("%.10lf\n",min(val(ans), val(ans+1)));}return 0;
}

以上是铜牌题

M Monster Hunter

题意：
一个有n个节点，根节点为1的树
只有父节点被杀死了，子节点才能被杀死。
杀死第i个节点的费用是在这里插入图片描述

另外可以使用魔法花费费用为0的让任意节点被杀死。

求可以使用m次魔法时，最少需要花费多少去杀死所有的节点

思路：
这是一个我自己咋也想不出来的题目，一个树形dp，或者说是树上的01背包。
参考了这位大佬的题解https://blog.csdn.net/kangyupl/article/details/111526183

用 $d p [0 / 1] [i] [j]$ 表示节点i在不存在或存在下，有j个子节点时的最小花费。（需要注意的是这里子节点j的数量是子树的所有节点数）

对于每一个点都有 $d p [1] [u] [1] = h p [u], d p [0] [u] [0] = 0$ ,状态转移方程为：

$d p [0] [u] [j + k] = m i n (d p [0] [u] [j + k], d p [0] [u] [j] + m i n (d p [0] [v] [k], d p [1] [v] [k]))$
$d p [1] [u] [j + k] = m i n (d p [1] [u] [j + k], d p [1] [u] [j] + m i n (d p [0] [v] [k], d p [1] [v] [k] + h p [v]))$

在转移的时候用的是一个滚动数组，所以j和k都是从大到小遍历（暂时不是特别想得通）

使用m次魔法，点1的子节点就会减少m个，答案就是 $m i n (d p [0] [1] [n - m], d p [1] [1] [n - m])$

代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=2005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
ll hp[maxn];
ll dp[2][maxn][maxn];
ll siz[maxn];
vector<int> g[maxn];void dfs(int u,int fa){dp[1][u][1] = hp[u];dp[0][u][0] = 0; siz[u] = 1;for(int i = 0; i < g[u].size(); i++ ){int v = g[u][i];if(v == fa)continue;dfs(v,u);for(int j = siz[u]; j >= 0; j--){for(int k = siz[v]; k >= 0; k--){dp[0][u][j + k] = min(dp[0][u][j + k], dp[0][u][j] + min(dp[0][v][k], dp[1][v][k]));dp[1][u][j + k] = min(dp[1][u][j + k], dp[1][u][j] + min(dp[0][v][k], dp[1][v][k] + hp[v]));}}siz[u] = siz[u] + siz[v];}
}void init(int n){for(int i = 1;i <= n; i++){g[i].clear();siz[i] = 0;}for(int i = 0;i <= n; i++)for(int j = 0; j <= n; j++)dp[0][i][j] = dp[1][i][j] = 1e18;
}int main()
{//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);ios::sync_with_stdio(false); cin.tie(0);int t,n,m;cin>>t;while(t--){cin>>n;init(n);int v;for(int i = 2 ;i <= n;i++){cin>>v;g[i].push_back(v);g[v].push_back(i);}for(int i =1 ;i <= n;i++)cin>>hp[i];dfs(1,-1);for(int i = n; i >= 0; i--)cout<<min(dp[0][1][i], dp[1][1][i])<<" ";cout<<endl;}return 0;
}