Summer Training 2023 Mini Comp 1 (Experts)

2338 Carnival - PCOI Online Judge (pcoij8.ddns.net)

题目大意

交互题，n个人穿着衣服，共有c种颜色，每一次可以询问一些人穿的衣服有多少种不同的颜色，最多可以询问3500次，请确定每个人穿的衣服是什么颜色

做法

第一眼可以看出来答案的上界是\(n*(n-1)/2\)，就是两两询问衣服颜色是否相同。

考虑到3500的询问次数，很容易可以猜到对于每一个人，我们大约可以询问\(logn\)次

于是我们可以考虑从左到右逐个确定

我们假设前面的n个都已经确定了，我们现在考虑确定第n＋1个

我们设前面n个一共有a种不同的种类，这个我们可以很容易的记录下来我们可以直接选择将第n＋1个与前面的n个进行比对，时间复杂度显然为\(n^2\)

我们考虑进行优化

如果我们直接询问1到n＋1的颜色，只会出现两种答案，a或a＋1

如果返回为a+1，那么第n+1个就是新的颜色

如果返回为a就是说明和前面的颜色重合

我们询问1-mid，加上n+1的颜色，如果是比1-mid的颜色多，但是1-n+1的颜色数又为a，那么说明n+1的颜色与mid+1到n的相同

这样我们就可以不断确定l-r区间，最终确定到一个数

考虑到这一道题的n比较小，对于询问过的区间，我们可以记录下来，采用记忆化

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=155;
int cnt=0,q[maxn],c,n,f[maxn],A[maxn][maxn];
int guess(int l,int r,int now){
	if(l==r&&now==-1)return 1;
	if(now==-1&&A[l][r])return A[l][r];
	int whi=(now==-1)?1:0;
	cout<<r-l+1 +1-whi<<" ";
	for(int i=l;i<=r;i++){
		cout<<q[i]<<" ";
	}
	if(!whi)
	cout<<now;
	cout<<endl;
	cin>>c;
	if(now==-1)A[l][r]=c;
	return c;
}
int main(){
	cin>>n;
	f[1]=1;
	q[1]=1;
	cnt=1;
	for(int i=2;i<=n;i++){
		if(guess(1,cnt,i)==cnt+1){
			f[i]=++cnt;
			q[cnt]=i;
			continue;
		}
		int l=1,r=cnt;
		while(l<r){
			int mid=(l+r)/2;
			if(guess(1,mid,i)!=guess(1,mid,-1))l=mid+1;
			else r=mid;
		}
		f[i]=l;
	}
	cout<<0;
	for(int i=1;i<=n;i++)cout<<" "<<f[i];
	cout<<endl;
	
	return 0;
}

2339 Toys "R" Us - PCOI Online Judge (pcoij8.ddns.net)

题目大意

询问\([l,r]\)中第一个没有出现的正整数

做法

一眼莫队，对于寻找第一个没出现的正整数，我们考虑用set查询

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int cnt[maxn],a[maxn],ans[maxn];
set<int>Set;
int n,m,l,size;
struct node{
	int x,y,id;
}q[maxn];
bool cmp(node x,node y){
	if(x.x/size==y.x/size)return x.y<y.y;
	return x.x/size<y.x/size;
}
void update(int now,int whi){
	if(whi==1){
		cnt[a[now]]++;
		if(cnt[a[now]]==1){
			Set.erase(a[now]);
		}
	}
	else{
		cnt[a[now]]--;
		if(!cnt[a[now]])
			Set.insert(a[now]);
	}
}
int main(){
	for(int i=1;i<=100001;i++)Set.insert(i);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].x,&q[i].y);
		q[i].id=i;
	}
	size=sqrt(m);
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].x,qr=q[i].y;
		while(r<qr)update(++r,1);
		while(r>qr)update(r--,-1);
		while(l>ql)update(--l,1);
		while(l<ql)update(l++,-1);
		ans[q[i].id]=*Set.begin();
	}
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
	
	
	return 0;
}

2340 Xor-Paths - PCOI Online Judge (pcoij8.ddns.net)

题目大意

走路径，路径上异或和为k的方案数

做法

一开始以为暴力的时间复杂度是\(2^{20}\),交完之后发现T掉了，才发现复杂度是\({2^{40}}\)

但也不难，一眼折半搜索

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=25;
int n,m,K,a[maxn][maxn],ans=0;
map<int,int>mp1[maxn],mp2[maxn];
bool check(int x,int y){
	return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs1(int x,int y,int k){
	if(!check(x,y))return ;
	k=(k^a[x][y]);
	if(x+y==m+1){
		mp1[x][k]++;
		return ;
	}
	dfs1(x+1,y,k);
	dfs1(x,y+1,k);
	return ;
}
void dfs2(int x,int y,int k){
	if(!check(x,y))return ;
	k=(k^a[x][y]);
	if(x+y==m+1){
		k^=a[x][y];
		mp2[x][k]++;
		return ;
	}
	dfs2(x-1,y,k);
	dfs2(x,y-1,k);
	return ;
}
signed main(){
	cin>>n>>m>>K;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dfs1(1,1,0);
	dfs2(n,m,0);
	for(int whi=1;whi<=n;whi++)
	for(map<int,int>::iterator it=mp1[whi].begin();it!=mp1[whi].end();it++){
		int num1=it->first,cnt1=it->second;
		int num2=(K^num1),cnt2=mp2[whi][num2];
		ans+=cnt1*cnt2;
	}
	cout<<ans<<endl;
	return 0;
}

2343 Make Divisible - PCOI Online Judge (pcoij8.ddns.net)

题目大意

找到正整数\(X,Y\),使得\(A+X\mid B+Y\),且\(X+Y\)最小

做法

明显发现有\(Y\le A\),所以答案上界为\(X+Y\le A\)

Subtask 1,2：枚举\(X\),然后我们可以\(O(1)\)算出\(Y\),，直接算出答案

Subtask 4：明显\(A-B\)

Subtask 3：分类讨论，

若\(A,B\le 10^5\),则为Subtask 1；

若\(A> 10^5,B\le 10^5\),则为Subtask 4；

Subtask 5:

\[\begin{aligned} &设正整数k，满足k(A+X)=B+Y\\ &有kA+kX=B+Y\\ &就有kX=B-kA+Y\\ &我们枚举k，如果B-kA<0,则X=0,Y=kA-B\\ &如果B-kA>0,则X=\lceil\frac{B-kA}{k}\rceil时最好，同时算出Y\\ &随着k增大，B-kA越来越小，小于0之后kA-B越来越大，答案越来越劣\\ &大约要枚举\frac{B}{A}次，最多枚举10^5次\\ \end{aligned} \]

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,a,b;
signed main(){
    cin>>t;
    while(t--){
    	int minn=1e9+7;
        cin>>a>>b;
        if(a>=b){
        cout <<a-b<<endl;
        continue;
        }
        if (a>1e5&&b>1e5){
        	for(int k=1;k<=1e5;k++){
        		if(k*a>b)minn=min(minn,k*a-b);
        		else{
		          	int B1=b-k*a;
		          	if(B1<0)minn=min(minn,-B1);
		          	int X=ceil(B1*1.0/k),Y=k*X-B1;
		          	minn=min(minn,X+Y);
	          	}		
		  }
        }
        else 
        for(int i =0;i <=min(a,minn);i ++){
            minn =min (minn,i +(a+i-b%(a+i))%(a+i));
            int A1=a+i,B1= b+(a+i-b%(a+i))%(a+i),K=B1/A1,N=A1+B1;
		}
		cout<<minn<<endl;

    }
    return 0;
}