A. Anti-knapsack
题意
给你k和n，让你在1-n中找不重复的数组成一个集合，要求集合的任意子集的所有数字加起来不等于k，求最大的集合。
分析
首先，大于k的肯定可以放入集合（无论怎么加都是大于k的），k不能放入集合（否则k一个数组成的子集等于k），再考虑小于k的数，可以发现，拿所有大于等于k/2的数也都是可行的（任意两个数加起来都大于k，切每个数本身都小于k），代码就出来了。
代码
代码语言：javascript复制#include <bits/stdc .h>
#define LL long long
using namespace std;
const int maxn = 1e5 10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
vector<int> ans;
for(int i = k 1; i <= n; i ) ans.push_back(i);
for(int i = k-1; i >= k-k/2; i --) ans.push_back(i);
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i ) printf("%d%c",ans[i],i == ans.size() - 1 ? 'n' : ' ');
}
return 0;
}B. Planet Lapituletti
题意
告诉你一个地区的时间进位方式h,m（如h = 26,m = 50表示一天26小时，每小时50分钟），再告诉你现在的时间hh：mm，要求你找到离现在最近的一个时间点，满足镜面反射的时间也是合法的（即不超过h和m），若当天没有则可以跨越到第二天。
分析
首先，根据镜面反射的特点可知：0、1、8不变，2会变5,5会变2，其余的都是非法的。由于数据量不大，可以直接暴力每一分钟，每次检查一下这个时间点的镜面是否也合法即可。由于有前导零，镜面反射的时候会有影响（01遍10），推荐用字符串表示时间，计算的时候再转换成数字。
代码
代码语言：javascript复制#include <bits/stdc .h>
#define LL long long
using namespace std;
const int maxn = 1e5 10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int h, m;
bool judge(char *t) {
char s[10];
memcpy(s,t,5);
for(int i = 0; i < 5; i ) {
if(i == 2) continue;
if(s[i] == '2') s[i] = '5';
else if(s[i] == '5') s[i] = '2';
else if(s[i] == '3' || s[i] == '4' || s[i] == '6' || s[i] == '7' || s[i] == '9') return 0;
}
int x = (s[4] - '0') * 10 s[3] - '0';
int y = (s[1] - '0') * 10 s[0] - '0';
if(x < h && y < m) return 1;
return 0;
}
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
char clo[10];
cin >> h >> m >> clo;
while(judge(clo) == 0) {
int y = (clo[3] - '0') * 10 clo[4] - '0';
y ;
if(y == m) {
int x = (clo[0] - '0') * 10 clo[1] - '0';
x ;
y = 0;
if(x == h) x = 0;
clo[0] = x/10 '0';
clo[1] = x % 10 '0';
}
clo[3] = y / 10 '0';
clo[4] = y % 10 '0';
}
cout << clo << endl;
}
return 0;
}D. GCD of an Array
题意
给你n个数存入数组a中，q次询问。每次询问给你i和x，表示将a[i]乘上x后，输出n个数的gcd。
分析
求n个数的gcd，我们假设这 n 个数的gcd为 p = 84 ，将 p 分解质因数后得到 p = 2 * 2 * 3 * 7 ，说明这n个数分解质因数后每个数也都包含 2 , 2 , 3 , 7 这几个质因数。也就是说，我们需要记录一下每个数的每个质因数j出现的次数k，然后记录一下每个质因数j出现k次的次数，如果出现k次的次数达到了n次，则表示每个数字都含有k个质因数j，那么gcd分解质因数后也会有k个质因数j，上述的两个记录可以通过两个map来实现。对于每次询问，会在 i 这个位置乘 x ，实际上就是给i这个位置贡献了若干个由x分解得来的质因数，维护一下map对应的值，再判断是否到达 n 次，如果到达 n 次则 gcd 乘上这个质因数（因为每次质因数j出现k次的次数只会有一次到达n次，所以不会重复计算）。
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const long long N = 501000;
const long long mod = 1e9 7;
long long a[N], n, m;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
unordered_map<int,map<int,int>> mp,cnt;
long long ans = 1;
void solve(int pos, int x) {
for (int j = 2; j <= sqrt(x); j ) {
while (x % j == 0) {
//第pos个位置对应的数中质因数j出现的次数 1
mp[pos][j] ;
//质因数j出现mp[pos][j]次的次数 1
cnt[j][mp[pos][j]] ;
//设mp[pos][j]= k
//如果质因数j出现k次的次数达到n次，则说明gcd中有k个质因数j相乘，
//但由于既然每个数中同时有k个j，那肯定也满足同时有k-1个j，
//故这次只要将答案乘以j就行了，k-1个已经在之前乘过了。
if (cnt[j][mp[pos][j]] == n) ans = (ans * j) % mod;
x /= j;
}
}
//别忘了x不为1的话也是一个质因数，处理方式同上
if (x > 1) {
mp[pos][x] ;
cnt[x][mp[pos][x]] ;
if (cnt[x][mp[pos][x]] == n) ans = (ans * x) % mod;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ) {
scanf("%lld", &a[i]);
solve(i,a[i]);
}
while (m--) {
long long pos, mul;
scanf("%d %lld",&pos, &mul);
solve(pos,mul);
printf("%lldn",ans%mod);
}
return 0;
}
