ACM-ICPC 2017 Asia Nanning

A. Abiyoyo、

题意

输出n个Abiyoyo, Abiyoyo.在输出两个Abiyoyo, yo yoyo yo yoyo.

代码

#include<iostream> using namespace std; int main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); while(n--){ puts("Abiyoyo, Abiyoyo."); } puts("Abiyoyo, yo yoyo yo yoyo."); puts("Abiyoyo, yo yoyo yo yoyo."); } return 0; }

E The Champion

题意

给了r，k，p 三个数，表示一用有 2^r 给人，当前这个人在第k个强，如果强的人和弱的人打获胜的概率为p，求这个人获胜的最大可能

思路

如果一个要想获得胜率的可能性最大，那么他应该尽可能先和比他弱的人打（先和获胜概率大的人比赛，否则这个概率会一直在比赛中间接性的减小），争取强的人淘汰更多强的人，按照这个贪心的思路，如果有弱的人，那么就和弱的人打，就只能和强的人打，那么弱的人应该淘汰的尽可能少，所以弱的和弱的打，强的和强的打，对于有一个弱的和一个强的的情况单独处理，就可以使用dfs的思路，统计每次的剩下的强和弱 人的个数，然后继续递归，直到这个人获胜

代码

#include<iostream> #include<cstring> #include<map> using namespace std; #define x first #define y second typedef pair<int ,int > PII; #define int long long int r,k; double p; map<PII ,double > mp; double dfs(int higher,int lower){ if(higher == 0&& lower == 0) return 1; // 没人, 必胜 if(mp.count({higher,lower})) return mp[{higher,lower}]; // 记忆化搜索 auto &v = mp[{higher,lower}]; if(lower & 1){ // 弱的人为奇数，那么和一个弱的人比 获胜概率p return v = p * dfs(higher/2,lower/2); } else{ // 如果 弱的人是偶数，还是和弱的人比，但是就会有一个弱的和强的比较，对应不同的概率和剩余人数 if(lower != 0){ return v = p * (p * dfs(higher/2 + 1,lower/2 - 1) + (1 - p) * dfs(higher/2,lower/2)); } else{ //如果没有 弱的人，那么只会和强的比较 return v = (1 - p) * dfs(higher/2,0); } } } signed main(){ int T; cin>>T; while(T--){ mp.clear(); scanf("%lld%lld%lf",&r,&k,&p); r = 1ll<<r; // 总人数 int higher = k - 1,lower = r - k; //强的人数和弱的人数 if(p < 0.5) swap(higher,lower), p = 1 - p; // 如果概率小则交换 double res = dfs(higher,lower); printf("%.6lf\n",res); } return 0; }

F. The Chosen One

题意

有n个人站成一排，每次会淘汰奇数位置的人，然后在剩余人中继续淘汰，只到最后一个人为为止，求最后一个人的编号

思路

我们在每k次淘汰中只会剩下 2^k的倍数的人，那么最后一次人的编号就是2^k，且不存在他的倍数，即不存在2^k+1这个编号

代码

T = int(input("")) while T: T -= 1 n = int(input("")) ans = 1 while ans * 2 <= n: # 存在就一直运算 ans *= 2 print(ans)

H. The Game of Life

题意

给定几个细胞在无限大的平面上扩展，默认其余细胞都是死的，求在0 - 321次中最多的细胞是哪次，个数为多少，321次有多少个细胞 细胞的成活满足 1.如果活细胞的周围小于2个或大于3个那么他就会死 2.活细胞只有周围有2个或三个才能存活到下一次 3.死细胞的周围有精确地3个就活

思路

就是简单的模拟，但是卡常，一直过不去，参考别人的代码写的

代码

#include<iostream> #include<cstring> #include<set> #include<vector> using namespace std; #define x first #define y second typedef pair<int ,int > PII; const int N = 1010,M = 350; bool a[N][N]; set<PII> s; vector<PII > live,died; int dx[] = {1,-1,0,0,1,1,-1,-1}; int dy[] = {0,0,1,-1,1,-1,1,-1}; char str[10]; void insert(int x,int y){ for(int i = -1;i<=1;i++) for(int j = -1;j<=1;j++) s.insert({x + i,y + j}); } int get(int x,int y){ int t = 0; for(int i = 0;i<8;i++){ int p = x + dx[i],q = y + dy[i]; if(a[p][q]) t++; } return t; } int main(){ int T; scanf("%d",&T); while(T--){ memset(a,0,sizeof a); s.clear(); int n,m; scanf("%d%d",&n,&m); int sum = 0; for(int i = 0;i < n; i++){ scanf("%s",str); for(int j = 0;j < m; j++) { if(str[j] == '#'){ int x = i + M,y = j + M; insert(x,y); sum ++; a[x][y] = true; } } } int max_id = 0,max_s = sum; for(int i = 1;i <= 321;i++){ live.clear(); died.clear(); for(auto it:s){ int x = it.x,y = it.y; if(a[x][y]){ int t = get(x,y); if(t == 2||t == 3) continue; died.push_back({x,y}); sum--; } else{ int t = get(x,y); if(t == 3) live.push_back({x,y}),sum++; } } if(sum > max_s) max_id = i,max_s = sum; for(auto it:live){ insert(it.x,it.y); a[it.x][it.y] = true; } for(auto it:died){ a[it.x][it.y] = false; } } printf("%d %d %d\n",max_id,max_s,sum); } return 0; }

I. Rake It In

题意

给定一个4 * 4的地方，有两个人，他们分别选一块2 * 2的地方，并把上面的分数加到总分且这四个单元格会逆转，每个人分别操作k次第一个人想让总分最大，第二个人想让总分最小，求最后的总分数

思路

因为每次的范围很小很小，而且单元的也很小就可以直接考虑爆搜，如果第一个人就选择地方的分数 + 他和第二个人之后的操作分数 中最大的那个，第二个也是同样，只不过找分数最小的地方

代码

#include<iostream> #include<cstring> using namespace std; const int N = 10; int g[N][N]; int n; int dfs(int u){ // u为偶数则认为是第一个人 反正第二个人 if(u == 2 * n) return 0; int res = 0; // 第一人最大化答案 if(u%2) res = 0x3f3f3f3f; // 第二人 最小化答案 for(int i = 0;i<=2;i++) for(int j = 0;j<=2;j++) { // 逆时针旋转 int a = g[i][j],b = g[i][j + 1]; int c = g[i+1][j],d = g[i + 1][j + 1]; g[i][j] = b,g[i][j + 1] = d,g[i + 1][j + 1] = c,g[i+1][j] = a; // if(u%2) res = min(res,dfs(u + 1) + a + b + c + d); else res = max(res,dfs(u + 1) + a + b + c + d); // 恢复现场 g[i][j] = a,g[i][j+1] = b,g[i + 1][j] = c,g[i + 1][j + 1] = d; } return res; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i = 0;i<4;i++) for(int j = 0;j<4;j++) scanf("%d",&g[i][j]); cout<<dfs(0)<<endl; } return 0; }

J. Rearrangement

题意

给定一个2 * n的序列，请对它们重新排列，使得相邻的两个数的之和不是三的倍数

思路

我们可以间接的想，只用考虑%3的余数，其中余数为1和为2的不能相邻，但是他们可以和余数为0的相邻，余数为0的只要不和自己相邻即可 首先，考虑余数为0的不能自己相邻，即余数为0的个数只用不大于n即可 其次，考虑余数为1和为2的不能相邻，那么我们可以把余数为1的放在一边，余数为2的放在另一边中间使用两个余数为0的建立分割线，（剩余的余数为0的可以按照余数为1或余数为2分别处理）如果余数为0的小于两个且余数为1和为2的都存在那么他们必然相邻， 特殊情况 只有2个余数为0时，余数为1的个数必须为奇数，因为隔离的两边都能只能有奇数个

111022110222

或者

110222111022

都是奇数个，余数为0大于三可以给余数为1或2自由分配这不需要考虑这种情况

代码

#include<iostream> #include<cstring> using namespace std; int cnt[3]; int main(){ int T; scanf("%d",&T); while(T--){ int n; memset(cnt,0,sizeof cnt); scanf("%d",&n); for(int i = 1;i<=2 * n;i++){ int x; scanf("%d",&x); int v = x%3; cnt[v]++; // 统计各自的个数 } bool flag = true; if(cnt[0] > n){ // 余数为0大于n flag = false; } if(cnt[0] <= 2 &&(cnt[1]&&cnt[2])){ if(cnt[0] < 2) //小于2且余数为1,2都存在 flag = false; if(cnt[0] == 2 &&(cnt[1]%2 == 0&&cnt[2]%2==0)){ //等于2 他们都为偶数 flag = false; } } if(flag) puts("YES"); else puts("NO"); } return 0; }

L. Twice Equation

题意

给出L，求不小于L的满足 2m(m + 1) = n(n + 1)的最小m

思路

不会推公式，打表加在 推公式网站上搜 公式 a₀ = 0,a₁ = 3, a_n = 6 * a_n-1 - a_n-2 + 2

代码

T = int(input("")) while T: T -= 1 n = int(input("")) a = 0 b = 3 while a < n: t = 6 * b - a + 2 a = b b = t print(a)

M. The Maximum Unreachable Node Set

题意

给定一个DAG（有向图），求有向图的最大独立集，即最大的不可达点集

思路

总个数 - 最小覆盖数，最小覆盖数就是二分图的最大匹配数 可以先用Floyd算法求出所有点的可达点

代码

/* 最小点覆盖 == 最大匹配 */ #include<iostream> #include<cstring> using namespace std; const int N = 110; int match[N]; bool st[N]; bool g[N][N]; int n,m; bool find(int u){ for(int i =1;i<=n;i++){ if(!g[u][i]||st[i]) continue; int t = match[i]; st[i] = true; if(t == 0||find(t)){ match[i] = u; return true; } } return false; } int main(){ int T; scanf("%d",&T); while(T--){ memset(match,0,sizeof match); memset(g,0,sizeof g); scanf("%d%d",&n,&m); while(m--){ int a,b; scanf("%d%d",&a,&b); g[a][b] = true; } for(int k = 1;k<=n;k++) for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) g[i][j]|=g[i][k]&g[k][j]; int res = 0; for(int i = 1;i<=n;i++){ memset(st,0,sizeof st); if(find(i)) res++; } printf("%d\n",n - res); } return 0; }