2020ICPC南京【个人题解EFHKLM】

news/2024/5/19 13:37:38

目录

  • E - Evil Coordinate（思维、暴力）
    • 思路
    • 代码
  • F - Fireworks（概率期望、三分）
    • 思路
    • 代码
  • H - Harmonious Rectangle（思维、暴力）
    • 思路
    • 代码
  • K - K Co-prime Permutation（签到、构造）
    • 思路
    • 代码
  • L - Let's Play Curling（签到）
    • 思路
    • 代码
  • M - Monster Hunter（树形背包）
    • 思路
    • 代码

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个烟花之后放掉，那么如果放了之后没有一个好烟花，状态又回到了初始状态，于是此时也会继续做 x x x个烟花然后放掉，于是若采取最优策略，每一次做的烟花数量是一定的。
考虑期望如何计算，令做 x x x个烟花之后放掉为一轮，那么每一轮产生好烟花的概率为 1 − ( 1 − p ) x 1-(1-p)^x 1−(1−p)x，产生好烟花的分布为几何分布，其轮数期望为 1 1 − ( 1 − p ) x \frac{1}{1-(1-p)^x} 1−(1−p)x1​，由于每一轮所需时间为 x n + m xn + m xn+m，于是期望时间为 x n + m 1 − ( 1 − p ) x \frac{xn+m}{1-(1-p)^x} 1−(1−p)xxn+m​
可以求二阶导证明该时间为关于 x x x的单峰函数，用三分求极值即可。注意要满足 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 n m 3^{nm} 3nm（思考一下即可知道为什么）
对于2<=n,m<=7的矩形而言，我们可以用dfs搜索出所有的答案，然后打个表。
如果直接暴搜的话，估计等一年都等不出结果（复杂度为 3 n m 3^{nm} 3nm），我们可以每次判断一下当前是否存在一组符合条件的点对，如果存在则直接返回的当前的方案数（后面每个点无论涂什么颜色都可以了），这样剪枝之后搜得很快。

代码

#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 k 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 ] dp[u][i][j][fl] dp[u][i][j][fl]表示为以 u u u为根的子树中，枚举到第 i i i棵子树，( i = 0 i = 0 i=0表示子树根本身)，使用了 j j j次魔法， u u u怪兽使用( f l = 1 fl = 1 fl=1)或不使用( f l = 0 fl=0 fl=0)的最小代价。当然枚举到第 i i i棵子树这一维可以通过 j j j的倒序枚举优化掉。
先考虑 u u u本身，而不考虑 u u u的孩子，则 d p [ u ] [ 0 ] [ 0 ] [ 0 ] = h p [ u ] ， d p [ u ] [ 0 ] [ 1 ] [ 1 ] = 0 dp[u][0][0][0] = hp[u]，dp[u][0][1][1] = 0 dp[u][0][0][0]=hp[u]，dp[u][0][1][1]=0。
再考虑 u u u的孩子：

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

于是，状态转移方程可以写为：
d p [ u ] [ i ] [ j ] [ 1 ] = m i n v ( d p [ v ] [ s i z [ v ] ] [ k ] [ 0 ] , d p [ v ] [ s i z [ v ] ] [ k ] [ 1 ] ) + d p [ u ] [ i − 1 ] [ j − k ] [ 1 ] 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][1]=minv​(dp[v][siz[v]][k][0],dp[v][siz[v]][k][1])+dp[u][i−1][j−k][1]
d p [ u ] [ i ] [ j ] [ 0 ] = m i n v ( d p [ v ] [ s i z [ v ] ] [ k ] [ 0 ] + v a l [ v ] , d p [ v ] [ s i z [ v ] ] [ k ] [ 1 ] ) + d p [ u ] [ i − 1 ] [ j − k ] [ 0 ] 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][i][j][0]=minv​(dp[v][siz[v]][k][0]+val[v],dp[v][siz[v]][k][1])+dp[u][i−1][j−k][0]
由于第二维可以优化掉，于是方程可写为：
d p [ u ] [ j ] [ 1 ] = m i n v ( d p [ v ] [ k ] [ 0 ] , d p [ v ] [ k ] [ 1 ] ) + d p [ u ] [ j − k ] [ 1 ] dp[u][j][1] = min_v(dp[v][k][0], dp[v][k][1])+dp[u][j-k][1] dp[u][j][1]=minv​(dp[v][k][0],dp[v][k][1])+dp[u][j−k][1]
d p [ u ] [ j ] [ 0 ] = m i n v ( d p [ v ] [ k ] [ 0 ] + v a l [ v ] , d p [ v ] [ k ] [ 1 ] ) + d p [ u ] [ j − k ] [ 0 ] dp[u][j][0] = min_v(dp[v][k][0]+val[v], dp[v][k][1])+dp[u][j-k][0] dp[u][j][0]=minv​(dp[v][k][0]+val[v],dp[v][k][1])+dp[u][j−k][0]
代码中需要优化掉一些不合法的状态才能通过这道题。

代码

#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();
}

http://lihuaxi.xjx100.cn/news/83424.html

相关文章

navicat11.2 premium install

navicat11.2 premium install

阅读更多...
oracle 12c使用 SEED创建一个PDB

oracle 12c使用 SEED创建一个PDB

1 登录cdb export ORACLE_SIDorclcdb sqlplus / as sysdba 2 建pdb #这里利用pdbseed建一个orclpdb5 CREATE PLUGGABLE DATABASE orclpdb5 ADMIN USER pdbadmin IDENTIFIED BY oracle file_name_convert(pdbseed,orclpdb5) --看到会自动创建orclpdb5目录(和pdbseed并列)&…
阅读更多...
测试开发用例

测试开发用例

为何要写测试用例 测试用例式测试执行的依据测试用例可以复用&#xff0c;在回归测试时不用再次编写测试用例可以衡量需求的覆盖率后人可以借鉴手工测试用例时自动化测试的依据 测试用例的设计方法 基于需求的设计方法 需求是测试人员进行测试的依据&#xff0c;测试人员分…
阅读更多...
从前向数据复制（FDR）到增强管道数据流转（EPDR）-taskBus的前世今生

从前向数据复制（FDR）到增强管道数据流转（EPDR）-taskBus的前世今生

增强管道数据流转技术&#xff08;Enhance Pipeline Data Routing&#xff0c;EPDR&#xff09;是 taskBus 跨平台多进程合作框架创立的开源数据分发技术&#xff0c;在软件无线电方向已经具有了较为完整的应用场景。应一些玩家要求&#xff0c;介绍一下这个技术的起源&#xf…
阅读更多...
【贝塞尔曲线拟合】

【贝塞尔曲线拟合】

贝塞尔曲线拟合问题描述拟合曲线生成过程参考程序注意事项问题描述 已知一条n阶贝塞尔曲线L(P0,P1,P2,P3,...,Pn)L(P0, P1, P2, P3, ..., Pn)L(P0,P1,P2,P3,...,Pn)&#xff08;P0P0P0为起点&#xff0c;P1P1P1为第一个控制点&#xff0c;P2P2P2为第二个控制点&#xff0c;P3P…
阅读更多...
原生 APP、Web、混合 APP，三种开发模式有何不同？

原生 APP、Web、混合 APP，三种开发模式有何不同？

前言 原生 App 又称Native App&#xff0c;该开发针对 IOS、Android、Windows 等不同的手机操作系统要采用不同的语言和框架进行开发&#xff1b;无论是从开发难度&#xff0c;价格还是周期来看&#xff0c;原生开发都更复杂、更昂贵、周期更长 那为什么还要选择原生 App 开发…
阅读更多...
简单利用conda安装tensorflow-gpu=2.2.0

简单利用conda安装tensorflow-gpu=2.2.0

网上安装tensorflow-gpu2.2.0什么的一大推&#xff0c;而且最后还报错&#xff0c;一般问题出现在&#xff1a; 一、安装下载慢 二、cuda和cudnn版本不对 我最后实验了&#xff0c;很好解决上面的问题。 conda install tensorflow-gpu2.2.0 简单利用conda安装tensorflow-gpu2…
阅读更多...
Pytorch单机多卡后台运行的解决办法

Pytorch单机多卡后台运行的解决办法

Pytorch单机多卡后台运行的解决办法 前言 今天初次使用了Pytorch单机多卡的训练方法&#xff0c;并且使用的是数据并行的方法&#xff0c;但是由于是单机多卡&#xff0c;那么服务器就需要创建几个进行来运行GPU&#xff0c;这个也导致了在服务器上使用nohup后台运行行不通&a…
阅读更多...
最新文章

Copyright @ 2022~2023