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

B.Binary Tree

题意

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

思路

这是一个博弈论，我们先分析他最基础的性质，一个完美二叉树是2^k -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都同时是偶数或奇数，删除多必然能保证相等），所以根据这个规律我们对于每个数分别处理时间复杂度为$\mathcal{O}(n^2)$ (对于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 = 10¹⁰ 显然是不够的我们需要对数组进行优化，首先f(x) == x 我们可以优化为一个数组，用dfs来枚举可以在优化一维，也就变为5000 * 60 * 60 = 1.8 * 10⁷ 是足够的，在时间上5000 * 10 * 60 * 60 = 1.8 * 10⁸ 有点卡常

代码

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