A Exciting Bets

题目大意

给两个数a, b, 这两个数能同时+1或者-1，求这两个数的最大公约数，以及变到最大公约数最少需要几步

主要思路

a和b不同时，最大公约数d都是a和b的约数，a = x d, b = y d且x != y，也就是说a和b的差是一定的，且a和b中至少相差一个d，所以d的最大值为|a - b|

a和b相同时，最大公约数为a,b本身，由于能无限增大，输出0 0

接下来考虑第二问，设最大公约数|a - b| = d，判断a和b至少需要几步能变到最大公约数为d，由于a,b同时变，所以判断一个即可，用a % d或者b % d得到余数t，答案就是min(t, d - t)，含义就是至少需要几步能变到最大公约数为d的倍数

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 200010;
  20. int n, a[N];
  22. signed main(void)
  23. {
  24.     int T;
  25.     cin >> T;
  26.     while(T--)
  27.     {
  28.         int a, b;
  29.         cin >> a >> b;
  30.         int t = abs(a - b);
  31.         if(t == 0)
  32.         {
  33.             puts("0 0");
  34.         }
  35.         else
  36.         {
  37.             cout << t << ' ';
  38.             cout << min(a % t, t - a % t) << endl;
  39.         }
  40.     }
  41.     return 0;
  42. }

B Customising the Track

题目大意

给定一个长度为n的数组，你可以将任意调整数组，保持数组总和不变求Codeforces Round #730 (Div. 2) - 图1最小值

主要思路

求平均值，先平均分，再将多出的几个数放到开头或者结尾即可

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 200010;
  20. int n, a[N];
  22. signed main(void)
  23. {
  24.     int T;
  25.     cin >> T;
  26.     while(T--)
  27.     {
  28.         int sum = 0;
  29.         cin >> n;
  30.         for(int i = 0; i < n; i++) cin >> a[i], sum += a[i];
  32.         sum %= n;
  33.         //debug(sum)
  34.         cout << sum * (n - sum) << endl;
  35.     }
  36.     return 0;
  37. }

C Need for Pink Slips

题目大意

给出概率p1,p2,p3,参数v ，每轮从p1, p2, p3中抽一个，抽到p1, p2则减去min(p1, v)，平分给另外两个概率，概率小于1e-6视为不合法不能被分配，抽到p3游戏结束，求轮数的期望

主要思路

dfs模拟看代码

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 200010;
  20. double p1, p2, p3, v;
  21. double ans;
  23. void dfs(int u, double p1, double p2, double p3, double now)
  24. {
  25.     ans += u * now * p3;
  26.     if(p1 == 0 && p2 == 0) return ;
  28.     if(p1 >= 1e-6)
  29.     {
  30.         double x = min(p1, v);
  31.         if(p2 >= 1e-6) dfs(u + 1, p1 - x, p2 + x / 2, p3 + x / 2, now * p1);
  32.         else dfs(u + 1, p1 - x, 0, p3 + x, now * p1);
  33.     }
  35.     if(p2 >= 1e-6)
  36.     {
  37.         double x = min(p2, v);
  38.         if(p1 >= 1e-6) dfs(u + 1, p1 + x / 2, p2 - v, p3 + x / 2, now * p2);
  39.         else dfs(u + 1, 0, p2 - x, p3 + x, now * p2);
  40.     }
  41. }
  43. signed main(void)
  44. {
  45.     int T;
  46.     cin >> T;
  47.     while(T--)
  48.     {
  49.         ans = 0;
  50.         cin >> p1 >> p2 >> p3 >> v;
  51.         dfs(1, p1, p2, p3, 1);
  52.         printf("%.8lf\n", ans);
  53.     }
  54.     return 0;
  55. }

D1 RPD and Rap Sheet (Easy Version)

题目大意

给定一个数n和一个初始密码k（0 <= k < n），每次你猜一个密码x时密码都会变成 x ^ k,让你在n次内猜出密码

主要思路

交互题，有两种思路。

  • 将密码”固定”，遍历n次猜出密码
  • 将密码“逼近”到一个固定的数

(第二种我也不知道能不能做，只是在考虑时有的思路)

那么我们就用第一种思路来做

首先考虑密码会变那么怎么将密码“固定”呢，我们每次猜的数x为i ^ i - 1（0 <= i < n）由于密码会改变，我们每次异或相邻的两个数前面的数会被异或两次，相当于没异或，于是密码永远为k ^ i，而我们猜的数也为i - 1 ^ i，在遍历时 总有一个i满足要求

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 200010;
  20. int n, a[N];
  22. signed main(void)
  23. {
  24.     int T;
  25.     cin >> T;
  26.     while(T--)
  27.     {
  28.         int n, k;
  29.         cin >> n >> k;
  30.         for(int i = 0; i < n; i++)
  31.         {
  32.             int x = max((int)0, i - 1) ^ i;
  33.             cout << x << endl;
  34.             int t;
  35.             cin >> t;
  36.             if(t == 1) break;
  37.         }
  38.     }
  39.     return 0;
  40. }

待补充！