2022 ICPC 济南(待补)

https://codeforces.com/gym/104076

E. Identical Parity

分析：

简化问题 A个长度为M的长链 B个长度为M-1的短链 问能否将这些链分为两部分 两部分差值小于等于1

特别注意：对于正数和负数的向上向下取整不可同日而语 两种操作不同

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define LL ll
void solve();
ll msum,mlen,Msum,Mlen,Ans,n,k;
void solve(LL a,LL b,LL c){
	LL x=c,y=-c;
	ll L=max(-a*x,b*(y-msum)),R=min(b*y,a*(Msum-x));
	if(L>=0){
		if(L%(a*b)!=0)
	L=L/(a*b)+1;
	else L/=(a*b);
	}else L/=(a*b);
	if(R>=0)
	R/=(a*b);
	else {
		if(R%(a*b)!=0)R=R/(a*b)-1;
		else R/=(a*b);
	}
	if(R>=L)Ans=1;
	return;
}
int main(){
	int T;cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
    cin>>n>>k;
    if(n==1){
    	printf("Yes\n");
    	return;
	}
    if(k==1){
    	printf("No\n");
    	return;
	}
	if(!(k%2)){
		printf("Yes\n");
		return;
	}
	Ans=0;
	mlen=n/k,Msum=n%k;
	Mlen=mlen+1,msum=k-Msum;
	solve(Mlen,mlen,n/2);
	if(Ans)printf("Yes\n");
	else printf("No\n");
}

A. Tower

分析：

注意：一直挂因为没开longlong 以后做题都开longlong得了

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define int ll
const int maxn=505;
set<int>Q;
set<int>::iterator it;
vector<int>ans;
int n,m,aim,Ans,a[maxn];
void solve();
int calc(int x){
	int res1=0,res2=0;
	if(x<=aim)return aim-x;
	while((x/2)>=aim)x/=2,res1++,res2++;
	res1+=x-aim;
	if(x/2){
	x/=2,res2++;
	res2+=(aim-x);
	return min(res1,res2);
	}else return res1;
	
}
signed main(){
	int T;cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
	Ans=1e9+7;
	Q.clear();
	scanf("%lld%lld",&n,&m);
	for(int x,i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		x=a[i];
		while(x)Q.insert(x),x/=2;
	}
	for(it=Q.begin();it!=Q.end();it++){
		aim=*it;
		ans.clear();
		for(int i=1;i<=n;i++)
			ans.push_back(calc(a[i]));
		sort(ans.begin(),ans.end());
		int res=0;
		for(int i=0;i<n-m;i++)
		res+=ans[i];
		Ans=min(Ans,res);
	}
	printf("%lld\n",Ans);
}