Codeforces Round #552 (Div. 3)-蒲公英云

Codeforces Round #552 (Div. 3)

C. Gourmet Cat

题目：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

输入是 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

暴力第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

前缀和大神就是大神膜拜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

倍增找最小的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;
}