2020ICPC南京【个人题解EFHKLM】-Toy模板网

这篇具有很好参考价值的文章主要介绍了2020ICPC南京【个人题解EFHKLM】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

E - Evil Coordinate（思维、暴力）

思路

首先如果炸弹在(0,0)或者机器人最终停在炸弹处，那么一定Impossible。
对于其他的情况，如果存在一条路径使得机器人可以不经过炸弹，那么一定存在一种方案，使得相同的方向在这个方案种是连在一起的。
于是可以直接枚举所有方向的排列，共4!个，判断每一种排列能否绕过炸弹即可。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100005

using namespace std;

int mx,my;
int n;
char s[N];
int L,R,D,U;
char tmp[4] = {'U','D','L','R'};

bool check(){
    int stx = 0,sty = 0;
    for(int i = 0;i < n;i ++){
        if(stx == mx && sty == my) return false;
        if(s[i] == 'U') sty ++;
        if(s[i] == 'D') sty --;
        if(s[i] == 'L') stx --;
        if(s[i] == 'R') stx ++;
        if(stx == mx && sty == my) return false;
    }
    return true;
}

void solve(){
    L = R = D = U = 0;
    scanf("%d%d",&mx,&my);
    scanf("%s",s);
    n = strlen(s);

    for(int i = 0;i < n;i ++)
        if(s[i] == 'U') U ++;
        else if(s[i] == 'L') L ++;
        else if(s[i] == 'R') R ++;
        else if(s[i] == 'D') D ++;

    sort(tmp,tmp + 4);
    do{
        int cnt = 0;
        for(int i = 0;i < 4;i ++){
            if(tmp[i] == 'U'){
                for(int j = 0;j < U;j ++)
                    s[cnt++] = 'U';
            }
            else if(tmp[i] == 'D'){
                for(int j = 0;j < D;j ++)
                    s[cnt++] = 'D';
            }
            else if(tmp[i] == 'L'){
                for(int j = 0;j < L;j ++)
                    s[cnt++] = 'L';
            }
            else if(tmp[i] == 'R'){
                for(int j = 0;j < R;j ++)
                    s[cnt++] = 'R';
            }
        }
        s[cnt] = '\0';
        if(check()){
            printf("%s\n",s);
            return;
        }
    }while(next_permutation(tmp,tmp + 4));
    puts("Impossible");
}

int main(){
    int T;scanf("%d",&T);
    while(T --)
        solve();
    return 0;
}

F - Fireworks（概率期望、三分）

思路

假设一开始，最优解为做 $x$ 个烟花之后放掉，那么如果放了之后没有一个好烟花，状态又回到了初始状态，于是此时也会继续做 $x$ 个烟花然后放掉，于是若采取最优策略，每一次做的烟花数量是一定的。
考虑期望如何计算，令做 $x$ 个烟花之后放掉为一轮，那么每一轮产生好烟花的概率为 $1-(1-p)^x$ ，产生好烟花的分布为几何分布，其轮数期望为 $\frac{1}{1-(1-p)^x}$ ，由于每一轮所需时间为 $x n + m$ ，于是期望时间为 $\frac{xn+m}{1-(1-p)^x}$
可以求二阶导证明该时间为关于 $x$ 的单峰函数，用三分求极值即可。注意要满足 $x$ 为整数，三分我用的是浮点数，最后上取整与下取整取个最小值即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double esp = 1e-6;

int n, m;
double p;

double f(double x)
{
    return (x * n + m) / (1 - pow(1 - p, x));
}

double solve()
{
    double l = 1, r = 1e9;
    while (r - l > esp)
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if (f(mid) < f(mmid))
            r = mmid;
        else l = mid;
    }
    return min(f((int)l), f((int)l + 1));
}   

int main()
{
    #ifdef ZYCMH
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
    int _; scanf("%d", &_);
    while (_ --)
    {
        scanf("%d%d%lf", &n, &m, &p);
        p /= 10000;
        printf("%.10f\n", solve());
    }
    return 0;
}

H - Harmonious Rectangle（思维、暴力）

思路

首先，如果n==1 || m == 1那么答案为0
如果n >= 8 || m >= 8那么答案为 $3^{nm}$ （思考一下即可知道为什么）
对于2<=n,m<=7的矩形而言，我们可以用dfs搜索出所有的答案，然后打个表。
如果直接暴搜的话，估计等一年都等不出结果（复杂度为 $3^{nm}$ ），我们可以每次判断一下当前是否存在一组符合条件的点对，如果存在则直接返回的当前的方案数（后面每个点无论涂什么颜色都可以了），这样剪枝之后搜得很快。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1000000007;

int n, m;
int a[10][10];
int id[10][10];

int res[] = {15,339,4761,52929,517761,4767849,339,16485,518265,14321907,387406809,460338013,4761,518265,43022385,486780060,429534507,792294829,52929,14321907,486780060,288599194,130653412,748778899,517761,387406809,429534507,130653412,246336683,579440654,4767849,460338013,792294829,748778899,579440654,236701429};

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

int main()
{
    #ifdef ZYCMH
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
    int _; scanf("%d", &_);
    while (_ --)
    {
        scanf("%d%d", &n, &m);
        if (n == 1 || m == 1) puts("0");
        else if (n >= 8 || m >= 8) 
            printf("%d\n", qpow(3, n * m));
        else{
            for (int i = 2, k = 0; i <= 7; i ++ )
                for (int j = 2; j <= 7; j ++, k ++ )
                    if (i == n && j == m)
                    {
                        printf("%d\n", res[k]);
                        break;
                    }
        }   
    }
    return 0;
}

K - K Co-prime Permutation（签到、构造）

思路

若k==0，无解。
否则，直接把前 $k$ 个数左移一位即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int main()
{
    #ifdef ZYCMH
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
    int n, k;
    scanf("%d%d", &n, &k);
    if (k == 0) puts("-1");
    else 
    {

        for (int i = 1; i < k; i ++ )
            printf("%d ", i + 1);
        printf("1 ");
        for (int i = k + 1; i <= n; i ++ )
            printf("%d ", i);
        puts("");
    }
    return 0;
}

L - Let’s Play Curling（签到）

思路

本质上就是求每两个蓝色冰壶中有多少个红色冰壶，排序之后二分即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100005;

int n, m;
int a[N], b[N];

int main()
{
    #ifdef ZYCMH
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
    int _; scanf("%d", &_);
    while (_ --)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ )
            scanf("%d", &a[i]);
        for (int i = 1; i <= m; i ++ )
            scanf("%d", &b[i]);
        b[m + 1] = -2e9, b[m + 2] = 2e9;
        m += 2;
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + m);
        int ans = 0;
        for (int i = 1; i < m; i ++ )
        {
            int l = upper_bound(a + 1, a + 1 + n, b[i]) - a;
            int r = lower_bound(a + 1, a + 1 + n, b[i + 1]) - a - 1;
            ans = max(r - l + 1, ans);
        }
        if (!ans) puts("Impossible");
        else printf("%d\n", ans);
    }
    return 0;
}

M - Monster Hunter（树形背包）

思路

挺经典的树形背包题目。
我们可以用魔法⭐打败怪兽👾哟。
因为怪兽构成了一个树形结构，因此可以先考虑每棵子树的情况。对于某个节点的怪兽，可以选择是否使用魔法攻击，因此可以开一个维0/1来表示(常规操作）。每棵子树还能使用不同的魔法次数，这个状态也需要记录。
因此可用 $d p [u] [i] [j] [f l]$ 表示为以 $u$ 为根的子树中，枚举到第 $i$ 棵子树，( $i = 0$ 表示子树根本身)，使用了 $j$ 次魔法， $u$ 怪兽使用( $f l = 1$ )或不使用( $f l = 0$ )的最小代价。当然枚举到第 $i$ 棵子树这一维可以通过 $j$ 的倒序枚举优化掉。
先考虑 $u$ 本身，而不考虑 $u$ 的孩子，则 $d p [u] [0] [0] [0] = h p [u] ， d p [u] [0] [1] [1] = 0$ 。
再考虑 $u$ 的孩子：

若 $u$ 是用魔法打败的，那么顺序必然为先用魔法打败 $u$ ，再去打 $u$ 的孩子，这样 $u$ 的孩子可以选择不用魔法。
若 $u$ 不是用魔法打败的，最终打败 $u$ 的代价还需要加上其孩子中不使用魔法的 $h p$ ，因为这些不使用魔法打败的孩子，必然是在 $u$ 被打败之后才被打败，即在 $u$ 未被打败的时候这些孩子还存活。

于是，状态转移方程可以写为：
$dp[u][i][j][1] = min_v(dp[v][siz[v]][k][0], dp[v][siz[v]][k][1])+dp[u][i-1][j-k][1]$
$dp[u][i][j][0] = min_v(dp[v][siz[v]][k][0]+val[v], dp[v][siz[v]][k][1])+dp[u][i-1][j-k][0]$
由于第二维可以优化掉，于是方程可写为：
$dp[u][j][1] = min_v(dp[v][k][0], dp[v][k][1])+dp[u][j-k][1]$
$dp[u][j][0] = min_v(dp[v][k][0]+val[v], dp[v][k][1])+dp[u][j-k][0]$
代码中需要优化掉一些不合法的状态才能通过这道题。文章来源地址https://www.toymoban.com/news/detail-407377.html

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e3 + 10;
int hp[N];
LL f[N][N][2], inf = 1e18;
int n;
//f[u][j][0/1]表示以u为子树的根，使用了i次魔法，u使用魔法(1) u不使用魔法(0) 的最小代价
//考虑更新f[u][j][1]，需要对子树进行背包：有j次魔法的使用机会去分配给子树，根已被消除，孩子使用或不使用魔法均可
/*
1
5
1 2 3 4
1 2 3 4 5
*/
struct E
{
    int nxt, to;
}e[N];
int head[N], cnt, sz[N];
void add(int u, int v)
{
    e[++ cnt] = {head[u], v};
    head[u] = cnt;
}
inline LL min_(LL a, LL b)
{
    if(a > b) return b;
    return a;
}
void dfs(int u)
{
    sz[u] = 1, f[u][0][0] = hp[u], f[u][1][1] = 0;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        dfs(v);
        sz[u] += sz[v];
        for(int j = sz[u]; j >=0; j --)
        {
            LL cur1 = inf, cur2 = inf;
            for (int k = min_(j, sz[v]); k >= 0; k -- )
            {
                if (j - k > sz[u] - sz[v]) break; //!!!优化掉一些不合法的状态
                cur1 = min_(cur1, f[u][j - k][0] + min_(f[v][k][0] + hp[v], f[v][k][1]));
                cur2 = min_(cur2, f[u][j - k][1] + min_(f[v][k][0], f[v][k][1]));
            }
            f[u][j][0] = cur1, f[u][j][1] = cur2;
        }
    }
}
void solve()
{
    cnt = 0;
    scanf("%d", &n);    
    for(int i = 0; i <= n; i ++) head[i] = 0;
    for(int i = 0; i <= n; i ++) for(int j = 0; j <= n; j ++) f[i][j][0] = f[i][j][1] = inf;
    for(int i = 2; i <= n; i ++)
    {
        int p; scanf("%d", &p);
        add(p, i);
    }
    for(int i = 1; i <= n; i ++) scanf("%d", &hp[i]);
    dfs(1);
    for(int i = 0; i <= n; i ++) printf("%lld ", min_(f[1][i][0], f[1][i][1]));
    puts("");
}
int main()
{
    int T; scanf("%d", &T);
    while(T --)
        solve();
}