和 \(\color{black}{a}\color{red}{rtalter}\) 一起打的
顺嘴说一下今天（周日）早晨的趣逝
事情发生在吃完早饭后，\(\color{grey}{WintersRain}\) 和 \(\color{black}{S}\color{red}{akura}\) 结伴而行
由于时间比较紧， \(\color{black}{S}\color{red}{akura}\) 手里拿着鸡排，嘴里嚼着包子
旁边一位初中大佬与我们并排前进
大佬：您走着吃饭啊？
\(\color{black}{S}\color{red}{akura}\) ：（嚼）也许
大佬：校长在前面你还吃？
\(\color{black}{S}\color{red}{akura}\) ：？？？？？
\(\color{grey}{WintersRain}\) ：？？？？？
果然前方一位校长缓缓走来
\(\color{grey}{WintersRain}\) ：（鞠躬）校长好——
\(\color{black}{S}\color{red}{akura}\) ：（将手中的鸡排藏在身后）
大佬：你是不是[数据删除]
\(\color{grey}{WintersRain}\) ：
A. GCD vs LCM
题意：给定一个正整数 \(n\)，求一组正整数 \(a\), \(b\), \(c\), \(d\)，使得 \(a+b+c+d=n\)，并且 \(\gcd(a,b) = \operatorname{lcm}(c,d)\)
解法：注意到 \(\gcd(1,x)\) 在 \(x\neq 0\) 的情况下恒为 \(1\)
又注意到 \(\operatorname{lcm}(1,1)\) 显然等于 \(1\)
因此构造 \(1~,~n-3~,~1~,~1\) 就符合要求
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
int T=read();
while(T--){
int n=read();
printf("1 %lld 1 1\n",n-3);
}
return 0;
}
B. Array Cloning Technique
注意到答案一定是选取一开始出现次数最多的东西，然后乘上 \(2\) 的幂得来
于是可以轻松构造
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
int n;
int a[WR],rec[WR],tot;
int cnt[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
bool cmp(int x,int y){
return x>y;
}
signed main(){
int T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++) cnt[i]=0;
for(int i=1;i<=n;i++) a[i]=rec[i]=read();
sort(rec+1,rec+1+n);
tot=unique(rec+1,rec+1+n)-rec-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(rec+1,rec+1+tot,a[i])-rec;
for(int i=1;i<=n;i++) cnt[a[i]]++;
sort(cnt+1,cnt+1+n,cmp);
// printf("%lld\n",cnt[1]);
int tot=cnt[1],ans=0;
while(tot*2<n) ans+=1+tot,tot*=2;
if(tot!=n) ans+=1+n-tot;
printf("%lld\n",ans);
}
return 0;
}
C. Tree Infection
注意题目要求的是子节点而不是子树
也就是说每一个点的子节点和其它的所有点都是割裂开的，可以先将所有的点的子节点的数量预处理出来
然后问题也就转化成一些互相独立的集合，每一个集合中如果存在被标记的点就能在每一个单位时间内拓展一个点
每一个单位时间内可以对一个点进行标记
对于转化后的问题，可以发现至少要对所有的集合进行一次标记，可以先将这一部分拿出来
然后考虑对于一些集合进行额外的标记以在最短的时间内让所有的点被标记
可以二分出需要额外进行的标记次数，在这个时间内优先进行贪心，优先标记集合内元素较多的集合
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
int n;
int cnt[WR];
vector<int>vec;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
bool check(int mid){
int tot=0;
for(int i=0;i<vec.size();i++){
tot+=max(0ll,vec[i]-mid-1-i);
}
if(tot>mid) return false;
else return true;
}
signed main(){
int T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++) cnt[i]=0;
cnt[0]=1;
for(int i=2;i<=n;i++){
int fa=read();
cnt[fa]++;
}
vec.clear();
for(int i=0;i<=n;i++){
if(cnt[i]) vec.emplace_back(cnt[i]);
}
sort(vec.begin(),vec.end());
int l=0,r=n+1,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%lld\n",ans+vec.size());
}
return 0;
}
D. GCD Guess
为什么题解是中国剩余定理啊
从低位到高位猜
假设现在猜的是从右往左第 \(i\) 位，那么我们现在就已经知道了右边 \(i-1\) 位
这些位的数值的和记作 \(y\)，令 \(a=2^{i-1}-y\)，\(b=2^{i}+2^{i-1}-y\)
假设返回的数是 \(m\)
如果 \(m=2^i\)，也就是说，在第 \(i\) 位加上了 \(1\) 会产生进位，那么这一位就是 \(1\)，反之这一位就是 \(0\)。
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18,base=2*3*7*11*13*17*19*23*29;
const int prime[30]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43};
int n;
int cnt[WR];
int a[WR],b[WR];
vector<int>vec;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
int gcd(int x,int y){
if(!y) return x;
return gcd(y,x%y);
}
signed main(){
int T=read();
while(T--){
int ans=0;
for(int i=0;i<30;i++){
printf("? %lld %lld\n",(1<<i)-ans,(1<<(i+1))+(1<<i)-ans);
fflush(stdout);
int res=read();
if(res==(1<<(i+1))) ans|=(1<<i);
}
printf("! %lld\n",ans);
fflush(stdout);
}
return 0;
}