Codeforces Round #536 (Div. 2)(ABCD)-蒲公英云

Codeforces Round #536 (Div. 2)(ABCD)

A. Lunar New Year and Cross Counting(水)

题意：找x满足以当前为中心四个角都为x的点；

暴力遍历一下就ok了；

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
string s[510];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(s[i][j]=='X'&&s[i-1][j-1]=='X'&&s[i-1][j+1]=='X'&&s[i+1][j-1]=='X'&&s[i+1][j+1]=='X')ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

B. Lunar New Year and Food Ordering（模拟）

题意：有n种菜，每个菜有ai盘，价格为ci；m个客人，如果客人点的菜不够上，往价格小的补，如果补不够那么就为0；

解：按价格排序，然后记录价格从小到大的位置，然后判断，如果不够上就从pos里找还能够上的菜，如果每次都从1开始找价格小且能上的菜会超时，

所以要记录一下价格在当前最小且有菜的位置；

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
struct node{
    ll a,c;
    int id;
}Q[maxn],T[maxn];
int pos[maxn];
bool cmp(node a,node b){
    return a.c<b.c;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    ll sum=0LL;
    for(int i=1;i<=n;i++){
        cin>>Q[i].a;
        sum+=Q[i].a;
    }
    for(int i=1;i<=n;i++){
        cin>>Q[i].c;
        Q[i].id=i;
        T[i]=Q[i];
    }
    sort(T+1,T+n+1,cmp);
    for(int i=1;i<=n;i++){
        pos[i]=T[i].id;
    }
    int now=0;
    while(m--){
        int u,v;
        cin>>u>>v;
        if(sum<=0){
            cout<<0<<endl;
            continue;
        }
        if(Q[u].a>=v){
            cout<<1LL*Q[u].c*v<<endl;
            sum-=v;
            Q[u].a-=v;
        }
        else{
            ll ans=0LL;
            ans+=1LL*Q[u].a*Q[u].c;
            v-=1LL*Q[u].a;
            sum-=Q[u].a;
            Q[u].a=0;
            while(Q[pos[now]].a==0&&now<=n)now++;
            for(int i=now;i<=n;i++){
                if(v==0)break;
                if(Q[pos[i]].a==0)continue;
                if(Q[pos[i]].a>=v){
                    ans+=1LL*Q[pos[i]].c*v;
                    sum-=1LL*v;
                    Q[pos[i]].a-=1LL*v;
                    v=0;
                }
                else{
                    sum-=1LL*Q[pos[i]].a;
                    ans+=1LL*Q[pos[i]].a*Q[pos[i]].c;
                    v-=1LL*Q[pos[i]].a;
                    Q[pos[i]].a=0;
                }
            }
            if(v!=0){
                cout<<0<<endl;
            }
            else cout<<ans<<endl;
        }
    }
    return 0;
}

C. Lunar New Year and Number Division

题意：给偶个数，然后让你组合，每个组最少2个数，然后求每个组的平方和，要求和最小；

解：一个大的配一个小的，然后求平方和；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
ll a[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    ll ans=0LL;
    for(int i=1;i<=n/2;i++){
        ans+=1LL*(a[i]+a[n-i+1])*(a[i]+a[n-i+1]);
    }
    cout<<ans<<endl;
    return 0;
}

D. Lunar New Year and a Wander

题意：给一个连通无向图，从1开始走，走遍全图，输出最小字典序的路径；

解：用优先队列，每走一个点，把所有能走的点都push进来，然后每次输出最小序的那个，直到全输出完；

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>g[maxn];
bool vis[maxn];
priority_queue<int,vector<int>,greater<int>>que;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    que.push(1);
    while(!que.empty()){
        int u=que.top();
        que.pop();
        if(vis[u])continue;
        cout<<u<<' ';
        vis[u]=true;
        for(int i=0;i<g[u].size();i++){
            if(!vis[g[u][i]]){
                que.push(g[u][i]);
            }
        }
    }
    return 0;
}