这场div2前两题如果想通了是比较简单的，一个考思维的题，看能不能转过来，庆幸打通了两题，但是也用了差不多一个小时，以后要提高熟练度，尽快打完前两题。
A. Anti-knapsack
输入n和k，在1-n个数中找尽量多的数，使得组成的集合的任意一个子集的和，都小于k。可以这么想，大于k的数都是可以选的，k这个数不能选，然后再去考虑比k小的能输出多少个，一看example，好像就是这样输出的。对于比k小的数，最多可以选[k / 2]，如果再选多一个，就能匹配加起来等于k，注意要选大的那一半即可（不然可能三个以上加起来就等于k了）。
B. Planet Lapituletti
这个题目是说有一个电子数码钟，然后给出一个时间，求未来最近的一个时间，在镜子里显示的时间同样是合法的（有可能给出的时间就是符合要求的）。有几个要点，模拟即可：镜像后小时、分钟调转，镜像后的数字是什么用数组预先存好，循环今天的所有未来时间找符合要求的（没有找到的话就输出00:00，这是一定符合的）
C. K-beautiful Strings
给一个字符串s和一个数字k，求一个beautiful的字符串a，要求其大于或等于s并尽可能小，而且它里面字符出现的次数必须要可以被k整除。不存在的话就输出-1。
首先需要统计每个字符的出现次数cnti，再计算需要添加sum个字符可以让字符串beautiful。可以用贪心方法，为了让a尽可能的小，要让a和s有尽可能长的前缀，在a中前缀后的第一个字符会较大，然后就在后面安排好缺少的字符，使a能beautiful。
根据这个想法，就从字符串最后一个字符开始向前遍历，逐步缩短前缀，然后看看此时，前缀长度加上sum再加一(这个是1是给前缀后第一个字符的，必须要大于s中对应位置的字符，之后的才能给补充的用)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <iostream>#include <cstring>#include <algorithm> using namespace std; int t;int n, k;string s;int cnt[26]; int main(){ cin >> t; while(t--){ cin >> n >> k; cin >> s; memset(cnt, 0, 26*sizeof(int)); for(int i = 0; i < n; i++){ cnt[s[i] - 'a']++; } int sum = 0; for(int i = 0; i < 26; i++){ sum += (k - cnt[i] % k) % k; } if(sum == 0){ cout << s << endl; continue; } if(n % k != 0){ cout << -1 << endl; continue; } bool f = false; for(int i = n - 1; i >= 0; i--){ //i 前缀长 sum -= (k - cnt[s[i] - 'a'] % k) % k; cnt[s[i] - 'a']--; sum += (k - cnt[s[i] - 'a'] % k) % k; for(int j = s[i] - 'a' + 1; j < 26; j++){ int temp = sum; sum -= (k - cnt[j] % k) % k; cnt[j]++; sum += (k - cnt[j] % k) % k; if(i + sum + 1 <= n){ for(int a = 0; a < i; a++){ cout << s[a]; //输出前缀 } cout << char(j + 'a'); //前缀后第一个不同字符 string add = ""; for(int a = 0; a < 26; a++){ int need = (k - cnt[a] % k) % k; while(need--){ add += a + 'a'; } } while(int(add.size()) + i + 1 < n){ add += 'a'; } sort(add.begin(), add.end()); cout << add << endl; f = true; break; } sum = temp; cnt[j]--; } if(f) break; } } return 0;} |
D. GCD of an Array
本题主要用到的算法：质因数分解、埃氏筛。
输入一系列的数，进行q次操作，每次将其中一个数增加x倍，同时求其最大公约数。
那么可以看到，答案不会变小，只可能变大，我们不可能每次操作后都求一次最大公约数，这样很浪费时间，但是如果我们将所有数都进行质因数分解，每次将x乘上去的时候也不必真的乘上去，也进行分解即可。
那么，在储存的时候，就要记录每个数字对应的分解出来的质因数，还有质因数的指数，这里可以用map做(别用unorder_map会被hack)
同时，也要储存质因数在对应的数字中各出现了多少次，因为我们不可能每次都去遍历上述的map，这样只要质因数对应的数字够了n次(数字的总个数)，就可以用这个质因数更新答案了。至于更新的次数，取决于质因数对应每个数字的出现个数中的最小值的增加值。
由此来看是需要排序的，用multiset即可(不用优先队列是因为它不能删除除队首元素外的其他元素)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #include <iostream>#include <map>#include <cmath>#include <set>using namespace std;const int maxn = 2e5 + 5, maxv = 2e5 + 5;int n, q;int prime[maxn];//如果是素数对应本身，否则对应将其筛掉的素数multiset<int> cnt[maxv];map<int, int> cntd[maxn];long long ans = 1, mod = 1e9 + 7;void add(int i, int x){ while(x != 1){ //逐步进行质因数分解 int div = prime[x], add = 0; while(prime[x] == div){ add++; x = x / prime[x]; } int lst = cntd[i][div]; //第i个数的质数约数div的数量 cntd[i][div] += add; int lst_min = 0; if((int) cnt[div].size() == n){ lst_min = *(cnt[div].begin()); } if(lst != 0){ cnt[div].erase(cnt[div].find(lst)); } cnt[div].insert(lst + add); if((int) cnt[div].size() == n){ for(int j = lst_min + 1; j <= (*cnt[div].begin()); j++){ ans = ans * div % mod; } } }}int main(){ ios::sync_with_stdio(0); cin >> n >> q; //埃拉托斯特尼筛法 求素数 for(int i = 2; i < maxn; i++){ if(prime[i] == 0){ prime[i] = i; if(i > 10000) continue; for(int j = i * i; j < maxn; j += i){ if(prime[j] == 0) prime[j] = i; } } } int x; for(int i = 1; i <= n; i++){ cin >> x; add(i, x); } int i; for(int j = 0; j < q; j++){ cin >> i >> x; add(i, x); cout << ans << endl; } return 0;} |
