A - GCD vs LCM
题目要求 a + b + c + d , gcd ? ( a , b ) × gcd ? ( c , d ) = c × d a + b + c + d, \gcd(a, b) \times \gcd(c, d) = c \times d a+b+c+d,gcd(a,b)×gcd(c,d)=c×d，那么直接等号两侧都是 1 1 1即可。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
inline void solve(){
int n = 0; cin >> n, n -= 2;
cout << 1 << ' ' << n - 1 << ' ' << 1 << ' ' << 1 << endl;
}
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 0; cin >> t;
while(t--) solve();
return 0;
}
B - Array Cloning Technique
显然第一步先复制，选择出现次数最多的数字(出现 m a x _ t i m e s max\_times max_times次)对其它数字进行替换，完成该轮替换耗时 m a x _ t i m e s max\_times max_times，出现次数最多的数字出现次数变为 m a x _ t i m e s × 2 max\_times \times 2 max_times×2。不难发现，除该数字外所有数字一定被替换最多且最少一次，那么只需要计算复制的次数即可，即为查需要翻倍多少次。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
int a[N];
map<int, int> mp;
inline void solve(){
mp.clear();
int n = 0; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], mp[a[i]]++;
if(n == 1){
cout << 0 << endl;
return;
}
int maxx = -1;
for(auto x : mp) maxx = max(maxx, x.second);
int ans = n - maxx;
while(maxx < n) maxx <<= 1, ans++;
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 0; cin >> t;
while(t--) solve();
return 0;
}
C - Tree Infection
考虑二分答案， c h e c k check check的方式是：每个节点先选一个子节点染一次色，可以发现在第 i i i秒感染第一个孩子后，第 t t t秒会有 t ? i t - i t?i个该孩子的兄弟被感染。对于一个时间 x x x，枚举所有以上情况进行感染操作，然后检查能否是都所有节点至少有一个子节点被感染。然后再查没能被感染剩余节点，对其手动感染再检查时间是否足够即可。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
int sz[N], tmp[N];
vector<int> g[N];
inline void solve(){
int n = 0; cin >> n;
memset(sz, 0, sizeof(int) * (n + 5));
sz[1] = 1;
for(int i = 2; i <= n; i++){
int p = 0; cin >> p;
sz[++p]++;
}
sort(sz + 1, sz + 2 + n, [](const int &x, const int &y){ return x > y; });
auto check = [&](int x){
memset(tmp, 0, sizeof(int) * (n + 5));
int times = 0, left = 0;
for(int i = 1; i <= x; i++){
if(sz[i]) tmp[i] = x - times++;
}
if(times > x) return false;
for(int i = 1; i <= n; i++){
if(sz[i] && sz[i] > tmp[i]) left += sz[i] - tmp[i];
}
if(times + left > x) return false;
else return true;
};
int l = 0, r = n + 1, ans = 0, mid = l + r >> 1;
while (l <= r) {
mid = l + r >> 1;
if (check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 0; cin >> t;
while(t--) solve();
return 0;
}
D - GCD Guess
看到 30 30 30次询问，立即想到枚举数位。
首先从最低位开始判断数位，可以发现判断最低位是否为 1 1 1可以查询 gcd ? ( x + 2 , x + 4 ) ≠ 2 \gcd(x + 2, x + 4) \neq 2 gcd(x+2,x+4)?=2即为 1 1 1，类似的，我们查询低二位时，只需要查 gcd ? ( x , x + 4 ) \gcd(x, x + 4) gcd(x,x+4)。即每次消除低位影响后求 gcd ? \gcd gcd。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int query(int val,int mul){
int x;
printf("? %lld %lld\n", val, val + mul);
fflush(stdout);
scanf("%lld", &x);
return x;
}
inline void solve(){
int x = 0;
for(int i = 1; i <= 1e9; i = i * 2){
if(query(-x + i, i * 2) != i) x += i;
}
printf("! %lld\n",x);
fflush(stdout);
}
signed main(){
int t = 0; cin >> t;
while(t--) solve();
return 0;
}
