Codeforces Round #536 (Div. 2)游记

2019-02-01 20:11:47


2019.1.31

一次难得的中国场,时间还是在 $20:30$ ,虽然说打到一半,公告 $unrated$ 了,虽然说打到一半 $in$ $queue$ 上 $200$ 页了,但本蒟蒻还是打了下去(都是泪呀)。

说一说比赛概况吧。。。 丑陋的水印↑。 被xryjr233虐了。。。

你没看错,rnk1的rqy被我抠了。。。

扯完了,来看一下题目:

A. Lunar New Year and Cross Counting

洛谷链接codeforces链接

题意

给一个 $n\times n$ 的矩阵,这个矩阵由 $X$ 和 $.$ 组成,问在这个矩阵内有多少个图案:

X.X
.X.
X.X

$1\leq n \leq 500$

思路

暴力就好了鸭,但是比赛时不知道哪里打错了。。。交了3次, 都是泪鸭。。。

代码:

#include<bits/stdc++.h>
using namespace std;
char a[710][710];
int n,ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]=='X'&&a[i-1][j-1]=='X'&&a[i-1][j+1]=='X'&&a[i+1][j-1]=='X'&&a[i+1][j+1]=='X'){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

B. Lunar New Year and Food Ordering

洛谷链接codeforces链接

题意

一开始,餐厅里有 $n$ 种菜,第 $i$ 种菜有 $a_i$ 份,每份 $c_i$ 元。 现在时除夕夜,有 $m$ 个顾客要来吃饭,第 $i$ 个顾客吃 $t_i$ 种 $d_i$ 份。 如果不够,就补最便宜的,如果真的不够,那么就走人(支付 $0$ 元,但还是吃了部分)

思路

模拟就好了。。。

#include<bits/stdc++.h>
#define E 100010
#define ll long long
#define Orz 998244353
using namespace std;
ll n,m,kkk;
struct node{
    ll has,cost,id;
}a[E];
ll f[E];
bool cmp(node qx,node qy){
    return qx.cost<qy.cost||(qx.cost==qy.cost&&qx.id<qy.id);
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i].has;
    for(ll i=1;i<=n;i++) cin>>a[i].cost,a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(ll i=1;i<=n;i++){
        f[a[i].id]=i;
    }
    kkk=1;
    for(ll i=1;i<=m;i++){
        ll ci,cn;
        cin>>ci>>cn;
        if(kkk>n) puts("0");
        else{
            ll ans=0;
            ll bn=min(cn,a[f[ci]].has);
            ans+=1ll*a[f[ci]].cost*bn,cn-=bn,a[f[ci]].has-=bn;
            if(cn) while(kkk<=n&&cn) bn=min(cn,a[kkk].has),cn-=bn,a[kkk].has-=bn,ans+=1ll*a[kkk].cost*bn,kkk+=(a[kkk].has==0);
            cout<<(cn?0ll:ans)<<endl;
        }
    }
    return 0;
} 

C. Lunar New Year and Number Division

洛谷链接codeforces链接

题意

将 $n$ 个数字,分成 $m$ 组,使得每一组的数字之和的平方之和最小。 问这个最小值是多少。 $n$ 是偶数。 $m$ 是任意数。

思路

肯定是两两一组啦。。。至于最小嘛肯定是一大一小一组。贪心。 设这 $n$ 个数字为 $a_1,a_2,a_3,a_4...a_{n-1},a_n$ (按从小到大顺序排列),那么贪心的最小值为: $$(a_1+a_n)^2+(a_2+a_{n-1})^2...(a_{n/2}+a_{n/2+1})^2$$ 即: $${a_1}^2+{a_2}^2+...{a_n}^2+2\times a_1 \times a_n+2\times a_2 \times a_{n-1}...+2\times a_{n/2}\times a_{n/2+1}$$ 因为 ${a_1}^2+{a_2}^2+...{a_n}^2$ 是不会变的(更改位置后) 所以只需要比较 $\times a_1 \times a_n+2\times a_2 \times a_{n-1}...+2\times a_{n/2}\times a_{n/2+1}$ 的大小即可,而 $2\times a_1 \times a_n+2\times a_2 \times a_{n-1}...+2\times a_{n/2}\times a_{n/2+1}$ 的最小值必定是 $2\times$ 一大一小(我懒,不证明了),所以最小值肯定为 $(a_1+a_n)^2+(a_2+a_{n-1})^2...(a_{n/2}+a_{n/2+1})^2$ 。

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

D. Lunar New Year and a Wander

洛谷链接codeforces链接

题意

求一个无向图的字典序最小的遍历。

思路

因为每个点是可以走重复的,所以肯定使用 $bfs$ ,而又因为是字典序最小的,所以使用堆 $priority_queue$ ,如果本节点确认后就拓展其他相邻的节点。

#include<bits/stdc++.h>
#define E 200010
using namespace std;
int n,m;
vector<int> v[E];
int vis[E];
int tt[E];
priority_queue<int,vector<int>,greater<int> > q;
void bfs(int x){
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    memset(tt,0,sizeof(tt));
    q.push(x);
    while(!q.empty()){
        int u=q.top();q.pop();
        if(vis[u]==0){cout<<u<<" ";
        vis[u]=1;
        for(int i=0;i<v[u].size();i++){
            int to=v[u][i];

            q.push(to);
        }}
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    } 
    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
    }
    bfs(1);
    return 0;
}

E. Lunar New Year and Red Envelopes

洛谷链接codeforces链接

题意

留个坑以后再填

思路

留个坑以后再填

F. Lunar New Year and a Recursive Sequence

洛谷链接codeforces链接

题意

留个坑以后再填

思路

留个坑以后再填