Codeforces Global Round 14 补题 A B C

A. Phoenix and Gold

Codeforces Global Round 14 补题 A B C

分析: 直接遍历,因为所有的物品各不相同,所以如果遇到前缀和为 x x x的情况直接交换某一项和下一项即可。如果所有物品的和为 x x x,那么无论如何都不满足题意,直接输出 NO \text{NO} NO。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int t,n,a[N],x;
int main(){
    cin>>t;
    while(t--){
        int sum=0;
        cin>>n>>x;
        for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
        if(sum==x) cout<<"NO"<<endl;
        else{
            sum=0;
            cout<<"YES"<<endl;
            for(int i=1;i<=n;i++){
                if(sum+a[i]==x){
                    swap(a[i],a[i+1]);
                }
                sum+=a[i];
                cout<<a[i]<<" ";
            }
            cout<<endl;
        }
    }
}

B. Phoenix and Puzzle

Codeforces Global Round 14 补题 A B C

分析: 首先判断是否能被 2 2 2和 4 4 4整除,因为只有 2 2 2和 4 4 4可以拼成一个小正方形,再判断 n / 2 n/2 n/2或 n / 4 n/4 n/4是否为平方数即可。

代码:

#include<bits/stdc++.h>
using namespace std;
int t,n;
map<int,int> pd;
void init(){
    for(int i=1;i*i<=1e9;i++){
        pd[i*i]=1;
    }
}
int main(){
    init();
    cin>>t;
    while(t--){
        cin>>n;
        if(n%2==0&&pd[n/2]||n%4==0&&pd[n/4]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

C. Phoenix and Towers

Codeforces Global Round 14 补题 A B C

分析: 先把每个塔放入小根堆, 每次往堆顶放入方块,最后判断一下最大的塔和最小的塔差值是否为 x x x即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,m,x,h[N],ans[N],res;
struct node{
    int x,id;
    bool operator<(const node num)const{
        return x>num.x;
    }
}tower[N];
int main(){
    cin>>t;
    while(t--){
        memset(tower,0,sizeof tower);
        res=0;
        int flag=0,mx=0,mi=2e9;
        priority_queue<node> q;
        cin>>n>>m>>x;
        for(int i=1;i<=m;i++){
            node k;
            k.x=tower[i].x;
            k.id=i;
            q.push(k);
        }
        for(int i=0;i<n;i++){
            cin>>h[i];
            auto t=q.top();
            q.pop();
            t.x+=h[i];
            ans[res++]=t.id;
            q.push(t);
        }
        for(int i=1;i<=m;i++){
            mx=max(mx,tower[i].x);
            mi=min(mi,tower[i].x);
        }
        if(mx-mi>x) cout<<"NO"<<endl;
        else{
            cout<<"YES"<<endl;
            for(int i=0;i<res;i++) cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
}
上一篇:Os-hackNos-1靶机过关记录


下一篇:poj1958——Strange Towers of Hanoi