A. Maximize?
题意:给定x,求一个范围在[1, x)的数字y,内使得gcd(x, y) + y最大,输出任意的y
思路:数据范围很小,暴力枚举即可
void solve(){ int x; cin >> x; int y = 1, ma = 0; for(int i = 1; i < x; i ++){ int res = __gcd(i, x) * i; if(res > ma){ ma = res; y = i; } } cout << y << '\n'; }
B. Prefiquence
题意:给定字符串s1, s2,求字符串s1是s2子序列一个最大前缀的长度
思路:两个指针即可,i 指针在s2, j 指针s1,当s2[i] == s1[j],j ++,最后答案就是 j
void solve(){ int n, m; string s1, s2; cin >> n >> m >> s1 >> s2; int i = 0, j = 0; for(i = 0, j = 0; i < m && j < n; i ++){ if(s1[j] == s2[i]) j ++; } cout << j << '\n'; }
C. Assembly via Remainders
题意:给定一个长度为n-1的数组a,构造一个长度为n的数组b,a[i] = b[i + 1] % b[i]
思路:求前缀和,然后把每个数加上一个极大值即可
void solve(){ int n; cin >> n; vector<int> a(n + 1); for(int i = 2; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++) a[i] += a[i - 1]; for(int i = 1; i <= n; i ++){ cout << a[i] + 1000000 << ' '; } cout << '\n'; }
D. Permutation Game
题意:给定两个数组a,p,刚开始两人分别位于pb,ps,没人一共可以进行k次操作,每次操作会发生两件事:
(1):获得a[pb]的分数
(2):从pb转移到p[pb](可以选择不转移)
(ps同理)
最后分数高的获胜,求最后获胜者或者平局
思路:赛时想太多了,其实很简单,枚举min(n, k)次转移,因为可以发现转移次序是一个环,求假设这次转移之后一直待在这个点直到最后获得的分数取max即可
void solve(){ ll n, k, pb, ps; cin >> n >> k >> pb >> ps; vector<ll> p(n + 1), a(n + 1); for(int i = 1; i <= n; i ++) cin >> p[i]; for(int i = 1; i <= n; i ++) cin >> a[i]; ll ans_pb = 0, ans_ps = 0; ll res_pb = 0, res_ps = 0; for(int i = 0; i < min(k, n); i ++){ res_pb += a[pb]; ans_pb = max(ans_pb, res_pb + (k - i - 1) * a[pb]); pb = p[pb]; res_ps += a[ps]; ans_ps = max(ans_ps, res_ps + (k - i - 1) * a[ps]); ps = p[ps]; } if(ans_pb > ans_ps) cout << "Bodya\n"; else if(ans_pb == ans_ps) cout << "Draw\n"; else cout << "Sasha\n"; }
E. Cells Arrangement
题意:给定一个n*n的矩阵,在矩阵中放置n个点,求每个点到所有点的曼哈顿距离的总种类数最多的一种放置方式
思路:构造,观察发现,在(1,1)放一个,然后(2,1)下面放一个,如果有多的,右下角放一个, 剩下的放在(1,3)~(1,3 + n - 3)
void solve(){ int n; cin >> n; cout << "1 1\n2 1\n"; if(n > 2){ cout << n << ' ' << n << '\n'; for(int i = 3; i < n; i ++){ cout << 1 << ' ' << i << '\n'; } } }
F. Equal XOR Segments
题意: 给定一个数组,一个数组为有趣的定义为:可以分为k>1个部分,每个部分连续异或后的结果相等,现在对这个数组查询q次子数组,判断子数组是否有趣
思路:可以确定,如果一个区间的异或和为0,那么肯定可以分为两个部分,如果不是0的话应该是分成三份,因为这三份异或之后还是这个区间的异或和,先处理出来前缀异或和,记录前缀异或和对应的每个点的下标,然后:
(1):找区间内左边的点PL,PL对 a[r] 的异或为PL的前缀异或和,因为pl~r的区间异或和为0
(2):找区间内右边的点PR,PR对 a[l - 1] 的异或为 a[l - 1] 的前缀异或和,与(1)同理
void solve(){ ll n, q; cin >> n >> q; vector<ll> a(n + 1); map<int, vector<int>> mp; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++){ a[i] ^= a[i - 1]; mp[a[i]].push_back(i); } while(q --){ int l, r; cin >> l >> r; ll p = a[r] ^ a[l - 1]; if(p == 0){ cout << "YES\n"; } else{ auto &v1 = mp[a[r]]; auto pl = lower_bound(v1.begin(), v1.end(), l); if(pl == v1.end() || *pl >= r){ cout << "NO\n"; continue; } ll posl = *pl; auto &v2 = mp[a[l - 1]]; auto pr = lower_bound(v2.begin(), v2.end(), posl + 1); if(pr != v2.end() && *pr < r){ cout << "YES\n"; } else cout << "NO\n"; } } }
G1. Division + LCP
题意:定义 f(x) 为将字符串分割成 x 份的最大公共前缀,求 fl,fl+1,…,fr
思路:pending
标签:ps,int,res,943,Codeforces,pb,异或,ans,Div From: https://www.cnblogs.com/RosmontisL/p/18171771