centos idea 工厂模式 delphi vue标签 vue修改样式 郑州小程序公司 angular视频 jquery事件绑定 matlab根号怎么打出来 chrome发送post请求 js对象添加元素 mysql汉化包 配置tomcat环境变量 flutter 缺点 python自学教程 python语言 python编程工具 python函数大全 java对象 java开发 java中的基本数据类型 java泛型的使用 java路径 java中的泛型 linuxgrep linux基础教程 linux简介 java项目下载 corelpainter r语言和python 跳一跳脚本 考试练习系统 脚本大全 js日期格式化 pycharm中文版 英雄联盟设置 udp测试工具 松下plc编程软件 facetime要钱吗
当前位置: 首页 > 学习教程  > 编程语言

2019-2020 ICPC Asia Hong Kong Regional Contest B D E G J

2020/10/8 18:38:45 文章标签:

B.Binary Tree 题意 给定一个二叉树,每次Alice和Bob可以取走一个完全二叉树,直到完全不能取为止,第一个不能取得为输,求那个输 思路 这是一个博弈论,我们先分析他最基础的性质,一个完美二叉树是2k -1&a…

B.Binary Tree

题意

给定一个二叉树,每次Alice和Bob可以取走一个完全二叉树,直到完全不能取为止,第一个不能取得为输,求那个输

思路

这是一个博弈论,我们先分析他最基础的性质,一个完美二叉树是2k -1,很明显他是一个奇数,最小的完美二叉树就是一个叶节点,所以最终结果必然是全部取完的,且每次取必然是奇数,所以我们就能得到如果是奇数,那么Alice 获胜,反之Bob

代码

#include<iostream>

using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i = 1;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
        }
        if(n & 1) puts("Alice");
        else puts("Bob");
    }
    
    return 0;
}

D Defining Labels

题意

给定一个k,其中 10 - k <= x <= 9,他的表现形式为a,b,c,d,e,f,aa,ab,ac,ad,ae,af……ff,给定k求第i个这样的数

思路

我们可以把它看做k进制,但是从1开始,所以给他减1即可

代码

#include<iostream>
#include<vector>
using namespace std;
 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        vector<int > ans;
        int k,n;
        scanf("%d%d",&k,&n);
        int u = 9 - (10 - k) + 1;
        while(n){
            n -= 1;
            int t = n % u;
            ans.push_back(t + 10 - k);
            n /= u;
        }
        for(int i = ans.size() - 1;i >= 0;i--){
            printf("%d",ans[i]);
        }
        puts("");
    }
    
    return 0;
}

E Erasing Numbers

题意

给定一个1-n的排列,对于连续的三个数,可以删除它的最小值和最大值,求最后可以剩下的数

思路

对于要保留的数来说,剩余的数我们无需关注他本身的大小,只需关注和这个数的大小,所以剩余的数用0和1表示,0表示比他小的 1表示比他大的。保留这个数也就是最后要剩余一个01,在删除的时候如果三个数有01,那么 必然删除一个0和1,我们只需0和1的个数相等(因为必然有0 1 连接的地方,那样就能一次次删除一个 0 1),所以问题就转换为怎样删除才能使0 1 个数相等,只有使用000,111 删除两个0 或 1才能使0和1的个数有可能相等相等(也就等价于0 1 中个数多的只删除这个数,能否小于等于个数小的那个数,因为0和1都同时是偶数或奇数,删除多必然能保证相等),所以根据这个规律我们对于每个数分别处理时间复杂度为 O ( n 2 ) \mathcal{O(n^2)} O(n2)
(对于11011这种情况我们可以先删去一个0 1 在处理)

代码

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 5010;
int a[N];
int n;
bool check(int x){
    bool v = a[x] < (n + 1)/2;
    int k = abs(a[x] - 1 - (n  - a[x])); // 多的比少的 多的个数
    // cout<<k<<endl;
    int t = 0;
    for(int i = 1;i <= n;i++){
        if(i == x) { // 如果中间穿插这个数,两个类型相同的必然会使这个数被删除
            t = 0;
            continue;
        }
        if((a[i] < a[x]) != v){ // 和多的数是一个类型的
            t++;
            if(t == 3){  // 等于三个删除两个
                t = 1;
                k -= 2;
            }
        }
        else t = max(t - 1,0); // 如果两个不同的数在一起可以尝试先删除这个使他前面的能够组成 相同类型即那种特殊情况
    }
    return k <= 0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i = 1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i = 1;i <= n;i++){
            if(check(i)) printf("1");
            else printf("0");
        }
        puts("");
    }
    
    return 0;
}

G Game Design

题意

有一颗树它的叶子节点会被敌军攻击,需要建立防御系统,防御系统会抵御所有的在这个节点的攻击,在不同的节点建立防御系统的代价是有可能不同(是由自己定义的),目的是守护最后根节点的安全,并且根节点也可以建立防御系统。给定一个方案数,求自己设计一个树,根节点为1号点,每个点防御的代价自己设定,需要满足最小代价的方案数为给定方案数

思路

我们可以想象一下对于一个数,假定为二叉树,在这个点的方案数就等于 左子数的方案数 * 右子数的方案数 + (根节点是否有方案数有则为1反之为0),所以根据这个性质我们就能一个给左子数建立方案数为2的,如果这个方案数为奇数那么给根节点建立1,对右子数递归处理

在这里插入图片描述

代码

#include<iostream>

using namespace std;
const int N = 1e5+10;
int h[N];
int c[N];
int cnt = 2;
int dfs(int n,int u,int fa){
    h[u] = fa;  // 这个节点的父节点
    if(n == 1){ // 只剩一个节点 这个节点建立一个权重为1
        c[u] = 1;
        return 1;
    }
    // 左子数建立2的方案数
    c[cnt++] = 1,h[cnt - 1] = cnt + 1; 
    c[cnt++] = 1,h[cnt - 1] = cnt;
    c[cnt++] = 2,h[cnt - 1] = u;
    // 方案数为奇数 给根建立1的方案数  递归处理右子数
    if(n & 1) 
    {
        c[u] = dfs(n / 2,cnt++,u) + 2;
        return c[u];
    }
    else{
        c[u] = N;
        return dfs(n / 2,cnt++,u) +2;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    if(n == 1){ // 特例
        puts("3");
        puts("1 1");
        puts("5 1 1");
        return 0;
    }
    dfs(n,1,-1);
    cout<<cnt - 1<<endl;
    for(int i = 2;i<cnt;i++){
        printf("%d ",h[i]);
    }
    puts("");
    for(int i = 1;i<cnt;i++){
        printf("%d ",c[i]);
    }
    return 0;
}

J Junior Mathematician

题意

在这里插入图片描述
其中d(x,i) 表示x的第i位对应的数
对于这个方程我们大概的理解就是第i位乘上它后面所有位对应的数字的和,求在[l,r]存在多少个数字的和为等于x本身

思路

很明显这是一个数位dp,我们需要预处理第i位选择哪个值,对应的前缀和,以及这个值本身和f(x)那么我们需要很多的内存,5000 * 10 * 60 * 60 * 60 = 1010 显然是不够的我们需要对数组进行优化,首先f(x) == x 我们可以优化为一个数组,用dfs来枚举可以在优化一维,也就变为5000 * 60 * 60 = 1.8 * 107 是足够的,在时间上5000 * 10 * 60 * 60 = 1.8 * 108
有点卡常

代码

#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;
const int N = 5010,M = 65,mod = 1e9 + 7;
int f[N][M][M];
char l[N],r[N];
int dight[N];
int p[N];
int m;
int dfs(int pos,int v,int sum,bool limit){ // v = f(x) - x,sum 各个位置之和
    if(pos == 0) return v == 0; // 边界
    if(!limit && f[pos][v][sum] != -1) return f[pos][v][sum];
    int up = limit?dight[pos]:9;
    long long ans = 0;
    for(int i = 0;i <= up;i++){
        int vv = (v + (sum * i - i * p[pos - 1])%m + m)%m;
        ans += dfs(pos - 1,vv,(sum + i)%m,limit&&i == up);
    }
    ans %= mod;
    if(!limit) f[pos][v][sum] = ans;
    return ans;
}
int solve(char *s,int len){
    for(int i = 1,j = len;i <= len;i++,j--){
        dight[i] = s[j];
    }
    return dfs(len,0,0,true);
}

int main(){
    int T;
    scanf("%d",&T);
    p[0] = 1;
    while(T--){
        scanf("%s%s%d",l + 1,r + 1,&m);
        int n = strlen(l + 1),k = strlen(r + 1);
        for(int i = 1;i <= n;i++) l[i] -= '0';
        for(int i = 1;i <= k;i++) r[i] -= '0';
        // 在对第x位的数字处理的时候使用
        for(int i = 1;i <= k;i++)
            p[i] = 1ll * p[i - 1] * 10 % m;
        // 初始化
        for(int i = 1;i <= k;i++){
            for(int j = 0;j < m;j++)
                for(int u = 0;u < m;u++)
                    f[i][j][u] = -1;
        }
        int t = -1;
        for(int i = n;i >= 1;i--){
            l[i] += t;
            if(l[i] < 0) l[i] += 10;
            else break;
        }
        printf("%d\n",(solve(r,k) - solve(l,n) % mod + mod)%mod);
    }
    
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_250070.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?