solved 5 problems
A、E: @xmjlove
G、I: @dbywsc
B: @DASJ
A. 两星级竞赛
思路
将竞赛按照星级从大到小排序，越大的星级填充越高的属性
一个星级的属性之和上限就是上一个星级最小的属性之和，模拟即可
代码
int t = read();
while (t-- > 0) {int n = read();int m = read();int k = read();long[][] arr1 = new long[n][2];int[][] arr2 = new int[n][m];Integer[] idx = new Integer[n];for (int i = 0; i < n; i++) {idx[i] = i;arr1[i][0] = read();for (int j = 0; j < m; j++) {int num = read();arr2[i][j] = num;if (num != -1) {arr1[i][1] += num;}}}Arrays.sort(idx, (a, b) -> (int)(arr1[b][0] - arr1[a][0]));long limit1 = Long.MAX_VALUE;long limit2 = Long.MAX_VALUE;int flag = 1;for (int z = 0; z < n; z++) {int i = idx[z];if (z != 0 && arr1[i][0] != arr1[idx[z - 1]][0]) {limit1 = limit2;}if (arr1[i][1] >= limit1) {flag = 0;break;}long sum1 = limit1 - arr1[i][1] - 1;long sum2 = 0;for (int j = 0; j < m; j++) {if (arr2[i][j] == -1) {long sub = Math.min(k, sum1);arr2[i][j] = (int)sub;sum1 -= sub;}sum2 += arr2[i][j];}limit2 = Math.min(limit2, sum2);}if (flag == 0) {pw.println("No");} else {pw.println("Yes");for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {pw.print(arr2[i][j] + " ");}pw.println();}}
}
pw.flush();
E.学而时习之
思路
到达 \(i\) 位置的 \(gcd\) 值有三种
\(s_1\) 表示所有到达当前位置且没有使用过操作的 \(gcd\) 集合
\(s_2\) 表示所有到达当前位置且在当前位置使用操作的 \(gcd\) 集合
\(s_3\) 表示所有到达当前位置且在当前位置没有使用操作但在前面使用过操作的 \(gcd\) 集合
\(s_1\) 能通过 \(i - 1\) 位置的 \(s_1\) 转移过来
\(s_2\) 能通过 \(i - 1\) 位置的 \(s_1\) 或 \(s_2\) 转移过来
\(s_3\) 能通过 \(i - 1\) 位置的 \(s_2\) 或 \(s_3\) 转移过来
注意到一个位置的三个集合大小为 \(log\) 级别，所以暴力
代码
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {String[] input = br.readLine().split(" ");int n = Integer.parseInt(input[0]);long k = Long.parseLong(input[1]);long[] arr = new long[n];input = br.readLine().split(" ");TreeSet<Long> s1 = new TreeSet<>();TreeSet<Long> s2 = new TreeSet<>();TreeSet<Long> s3 = new TreeSet<>();for (int i = 0; i < n; i++) {TreeSet<Long> s4 = new TreeSet<>();TreeSet<Long> s5 = new TreeSet<>();TreeSet<Long> s6 = new TreeSet<>();arr[i] = Long.parseLong(input[i]);for (long num : s1) {s4.add(gcd(num, arr[i]));s5.add(gcd(num, arr[i] + k));}for (long num : s2) {s5.add(gcd(num, arr[i] + k));s6.add(gcd(num, arr[i]));}for (long num : s3) {s6.add(gcd(num, arr[i]));}s1.clear();s1.addAll(s4);s2.clear();s2.addAll(s5);s3.clear();s3.addAll(s6);if (i == 0) {s1.add(arr[i]);s2.add(arr[i] + k);s3.add(arr[i]);}}pw.println(Math.max(s1.last(), Math.max(s2.last(), s3.last())));
}
pw.flush();
G.Be Positive
思路
显然交换顺序是不会影响最终的结果的，如果 \(0...(n - 1)\) 异或起来为 \(0\) 必然无解。
要求字典序最小，最优的方案是从小到大输出。同时维护一个前缀异或和 \(sum\) ，如果 \(sum \oplus i = 0\) ，那么 \(sum \oplus (i + 1)\) 一定不为 \(0\) ，将两项交换即可。
代码
void solve(void) {int n; std::cin >> n;int res = 0;for(int i = 0; i < n; i++) {res ^= i;}if(res == 0) {std::cout << "impossible\n";return;}std::cout << "1 0 ";res = 1;std::vector<int> ans;for(int i = 2; i < n; i++) ans.push_back(i);for(int i = 0; i < (int)ans.size() - 1; i++) {res ^= ans[i];if(res == 0) {res ^= ans[i];std::swap(ans[i], ans[i + 1]);res ^= ans[i];}}for(auto i : ans) std::cout << i << " ";std::cout << '\n';
}
I. Left Shifting 2
思路
答案由两部分组成： \(原本修改的代价 - 左移后消减的代价\) 。可以发现左移的贡献只会是 \(0\) 和 \(1\) ，因此我们要找是否存在贡献为 \(1\) 的点。显然，暴力做会超时。因此先将每一段相同字符的存下来，接下来分三种情况枚举：
- 如果存在三段以上的段，尝试枚举中间每一段，取最大的收益。显然只有当这一段的长度是偶数时，才会带来 \(1\) 的收益。
- 接下来尝试切开第一段，如果首尾不同，且第一段的长度为偶数时，才会带来 \(1\) 的收益。
- 类似地，尝试切开最后一段。
- 最后做一个特判，如果只有一段，也就是 \(s\) 是同一个字符组成的字符串时，无论如何都无法带来贡献。
因此，答案应该为 \(原本的代价 - (是否存在有贡献的点 ? 1 : 0 )\) 。
代码
void solve(void) {std::string s;std::cin >> s;int n = (int)s.size();if(n == 1) {std::cout << "0\n";return;}std::vector<int> len;for(int i = 0; i < n;) {int j = i + 1;while(j < n && s[j] == s[i]) j++;len.push_back(j - i);i = j;}i64 ans = 0;int k = (int)len.size();for(auto i : len) ans += i / 2;int l = len.front(), r = len.back();bool st = (s[0] == s[n - 1]);int op = (st && (l & 1) && (r & 1)) ? 1 : 0;int best = 0;if(k >= 3) {for(int i = 1; i < k - 1; i++) {if((len[i] & 1) == 0) {best = std::min(best, op - 1);break;}}}if(k >= 2 && (r & 1) == 0) {int w1 = (st && (l & 1)) ? 1 : 0;best = std::min(best, w1 - 1);}if(k >= 2 && (l & 1) == 0) {int w1 = (st && (r & 1)) ? 1 : 0;best = std::min(best, w1 - 1);}if(k == 1) best = 0;std::cout << ans + best << '\n';
}
B. 金牌
思路
首先将每支队伍对金牌比例取余并且存在数组里，然后将数组从大到小排序，然后遍历这个数组，如果安排的队伍大于等于金牌比例与余数的差，安排的队伍数量就减去这个差，并且给最后的答案加1，直到数组遍历完或者安排的队伍数量不够凑成一个金牌比例。然后判断剩余安排队伍的数量，如果大于等于金牌比例，就拿安排队伍数量除金牌比例，加起来。最后遍历初始的数组，队伍数量除金牌比例，将答案加起来。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[110];
int b[110]; signed main(){int t;cin>>t;while(t--){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){b[i]=a[i]%k;}sort(b+1,b+n+1,greater<int>());int m;cin>>m;int ans=0;for(int i=1;i<=n;i++){int shu=k-b[i];if(m>=shu){m-=shu;ans+=1; }else{break;}}if(m>=k){ans+=m/k;}for(int i=1;i<=n;i++){ans+=a[i]/k;}cout<<ans<<endl;}return 0;
}