Codeforces Round #552 (Div. 3)

骑猪看日落 2022-04-24 07:04 135阅读 0赞

### C. Gourmet Cat ###

题目：[http://codeforces.com/contest/1154/problem/C][http_codeforces.com_contest_1154_problem_C]

摘除 3：2：2之后 暴力

#include<iostream>
    #define N 100
    using namespace std;
    int a[4],d[4];
    int s[7]={1,1,2,3,1,3,2};
    int main(){
    	cin>>a[1]>>a[2]>>a[3];
    	int ans=0;
    	for(int j=1;j<=7;j++){
    	    int b=min((a[1])/3,min((a[2])/2,(a[3])/2));
    		int d[4]={0,a[1]-3*b,a[2]-2*b,a[3]-2*b};
    		int c=b*7;
    	  
    	for(int i=1;i<=7;i++){
    		if(d[s[i]]) {
    			d[s[i]]--;
    			c++;
    		}
    		else break;
    	 } 
    	 a[s[j]]++;
    	 ans=max(ans,c-j+1);
       }
    	 cout<<ans<<endl;
    	 return 0;
    }
    /*
    30 20 10
    输出：39 
    */

### D. Walking Robot ###

题目：[http://codeforces.com/contest/1154/problem/D][http_codeforces.com_contest_1154_problem_D]

输入是 n b a；

当无光即==0时 先使用a;

当有光即==1时 先使用b同时保证a不满；

#include<iostream>
    using namespace std;
    int main(){
    	int n,b,a;
    	cin>>n>>b>>a;
    	int aa=a;
    	for(int i=1;i<=n;i++){
    		int x;
    		cin>>x;
    		if(x==0){
    			if(a) a--;
    			else  b--;
    		}
    		else{
    			if(b&&a<aa){
    				b--;
    				a++;
    			}
    			else a--;
    		}
    		if(a==0&&b==0) {
    			cout<<i<<endl;return 0;
    		}
    	}
    	cout<<n<<endl;
    	return 0;
    }

### E. Two Teams ###

题目：[http://codeforces.com/contest/1154/problem/E][http_codeforces.com_contest_1154_problem_E]

暴力第37个点超时emmmmm

So    数组模拟链表

#include<iostream>
    #include<queue>
    #define N 200010
    #define P pair<int,int>
    using namespace std;
    int n,K,opt,a[N],vis[N],pre[N],net[N];
    priority_queue<P> q,p;//大顶堆 
    int main(){
    	cin>>n>>K;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		pre[i]=i-1;net[i]=i+1;
    		q.push(P(a[i],i));
    	} 
    	while(!q.empty()){
    		//将已标记过的数据从原数组中删除 
    		while(p.size()&&p.top()==q.top()) p.pop(),q.pop();
    		int i=0,j=0,k=0;
    		if(q.empty()) break;
    		//后继 
    		for(i=1,j=net[q.top().second];i<=K&&j;i++,j=net[j]){
    			vis[j]=opt+1;p.push(P(a[j],j));
    		}
    		
    		//前驱 
    		for(i=1,k=pre[q.top().second];i<=K&&k;i++,k=pre[k]){
    			vis[k]=opt+1;p.push(P(a[k],k));
    		}
    		vis[q.top().second]=opt+1;q.pop();
    		//更改对应的前驱与后继 
    		pre[j]=k;net[k]=j;opt^=1;
    	}
    	for(int i=1;i<=n;i++) cout<<vis[i];
    	return 0;
    }  
    /*
    5 1
    2 4 5 3 1
    输出： 
    21112
    */

### F. Shovels Shop ###

题目：[http://codeforces.com/contest/1154/problem/F][http_codeforces.com_contest_1154_problem_F]

前缀和    大神就是大神  膜拜ing

为什么我没有想到？菜是原罪！！！

#include<iostream>
    #include<algorithm>
    #define N 100010
    using namespace std;
    int n,m,k;
    int a[N],g[N],f[N];
    int main(){
    	cin>>n>>m>>k;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	sort(a+1,a+n+1);
    	for(int i=1;i<=n;i++) a[i]+=a[i-1]; //前缀和 
    	for(int i=1;i<=m;i++){
    		int x,y;
    		cin>>x>>y;
    		g[x]=max(g[x],y);//买x个最多免费g[x]个 
    	}
    	
    	for(int i=1;i<=k;i++){//dp; 
    		f[i]=0x3f3f3f3f;
    		for(int j=0;j<i;j++){
    			f[i]=min(f[i],f[j]+a[i]-a[j+g[i-j]]);
    		}
    	}
    	cout<<f[k]<<endl;
    	return 0;
    }

### G. Minimum Possible LCM ###

题目：[http://codeforces.com/contest/1154/problem/G][http_codeforces.com_contest_1154_problem_G]

倍增找最小的lcm

#include<iostream>
    #define ll long long
    using namespace std;
    const int N=1e7+50;
    int n,x,vis[N],t1,t2,s1,s2;
    ll ans=1e14;
    int main(){
    	cin>>n;
    	//如果存在两个数相同 ans记录最小的那个  
    	//t1记录ans在数组中的第一个位置，t2记录ans在数组中的第二个位置 
    	//如果不存在t1=t2=0;
    	for(int i=1;i<=n;i++){
    		cin>>x;
    		if(vis[x]){
    			if(ans>x) {
    				ans=x;
    				t1=vis[x];
    				t2=i;
    			}
    		}
    		if(!vis[x]) vis[x]=i;
    	}
    	//从最小数开始倍增 同时判断该数组中有没有这个数 
    	for(int i=1;i<N;i++){
    		if(i>=ans) break;
    		s1=s2=0;
    		for(int j=i;j<N;j+=i){//倍增 
    		if(!vis[j]) continue;
    		if(!s1) {
    			s1=j;s2=vis[j];
    		} 
    		else{
    			if(ans>1ll*s1*j/i){
    				ans=1ll*s1*j/i;
    				t1=s2;t2=vis[j];
    				break;
    			}
    		}
    	}
       }
    	if(t1>t2) t1^=t2^=t1^=t2; //异或交换t1,t2的值 
    	cout<<t1<<" "<<t2<<endl;
    	return 0;
    }

[http_codeforces.com_contest_1154_problem_C]: http://codeforces.com/contest/1154/problem/C
[http_codeforces.com_contest_1154_problem_D]: http://codeforces.com/contest/1154/problem/D
[http_codeforces.com_contest_1154_problem_E]: http://codeforces.com/contest/1154/problem/E
[http_codeforces.com_contest_1154_problem_F]: http://codeforces.com/contest/1154/problem/F
[http_codeforces.com_contest_1154_problem_G]: http://codeforces.com/contest/1154/problem/G