Codeforces Round 536 (Div. 2) 解题日志

2019-02-01

字数统计: 1.6k字 | 阅读时长: 8分

比赛的时候写了好久的B发现别人CD都已经过一大片了，赶紧去看C，然后回过头来调B的bug，最后开E发现这场unrated了，溜了溜了。

A Lunar New Year and Cross Counting

思路：直接n²判断便可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1000][1000];
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++)scanf("%s",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][j+2]=='X'&&s[i+1][j+1]=='X'&&s[i+2][j]=='X'&&s[i+2][j+2]=='X')ans++;
        }
    }cout<<ans;
    return 0;
}

B Lunar New Year and Food Ordering

tags: 排序，模拟
思路：

首先对所有商品的价格和编号排序，把最便宜的且编号最小的放前面。
然后直接判断便可，如果不够，用一个指针维护当前最便宜的位置，然后统计贡献。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll a[100005],c[100005];
struct node{
    ll c,id;
    friend bool operator < (node a,node b){
        if(a.c==b.c)return a.id<b.id;
        return a.c<b.c;
    }
}p[100005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    for(int i=1;i<=n;i++){
        scanf("%lld",c+i);
        p[i].c=c[i];p[i].id=i;
    }sort(p+1,p+1+n);
    int pos=1;
    ll t,d;
    while(m--){
        scanf("%lld%lld",&t,&d);
        ll tmp = 0;
        if(a[t]>=d){
            a[t]-=d;
            tmp+=c[t]*d;
        }
        else{
            int need=d-a[t];
            tmp+=c[t]*a[t];
            a[t]=0;
            while(need>0&&pos<=n){
                if(a[p[pos].id]>=need){
                    a[p[pos].id]-=need;
                    tmp += c[p[pos].id]*need;
                    need=0;
                    break;
                }
                else{
                    tmp += c[p[pos].id]*a[p[pos].id];
                    need-=a[p[pos].id];
                    a[p[pos].id]=0;
                    pos++;
                }
            }if(need>0)tmp=0;
        }
        cout<<tmp<<"\n";
    }
    return 0;
}

C Lunar New Year and Number Division

思路：要使得值最小，直接把最大最小组合起来便可。

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

D Lunar New Year and a Wander

思路：

由于要字典序尽可能小，我们只需要维护当前可达却未到达的点，按照编号维护便可，当一个点被访问之后，它所有可达的点变得可达。
显然这样贪心最优，复杂度O(m+nlogn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int n,m;
bool vis[maxn];
vector<int> g[maxn];
int main(){
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    set<int> st;
    st.insert(1);
    vector<int>ans;
    vis[1]=1;
    while(ans.size()<n){
        int u=*st.begin();
        st.erase(u);
        ans.push_back(u);
        for(auto v:g[u]){
            if(vis[v])continue;
            vis[v]=1;
            st.insert(v);
        }
    }
    for(auto v:ans)cout<<v<<" ";
    return 0;
}

E Lunar New Year and Red Envelopes

简单题意：
有k个红包，有n个时间点，对于每个红包，可以抢的时间范围是[s,t]，价值为w，抢了之后只能到d时间后才能继续。
对于红包，能抢就抢，优先w最大的，再优先d最大的。
有m次阻止某一秒抢红包的操作。问最后最小收益是多少。

思路：

设 dp[j][i] 表示在前 i 个时间点使用过 j 次屏蔽的最小收益。
我们需要知道在时间 i 可以抢的红包是确定的，简单证明~~（口胡）~~如下：
- 首先，假设没有屏蔽功能，那么每一个时间点，选择的红包都是一定确定的。
- 无法选择红包有2种情况，1是这个时间点没有被红包覆盖，2是这个时间点被前面被选的红包的d值覆盖，导致无法选。
- 引进屏蔽功能之后，原本在时间i就被抢的红包，可以被拖延到i+1甚至之后，我们假设它最多保留到时间A.t,在后面的时间里只要有一次没有屏蔽，这个红包依旧转移到A.d 。
- 不屏蔽这个红包，导致它被使用，需要移出队列吗？不需要！
- 因为如果已经使用了它，比它优先级低的且在队列里的红包一定都不会被使用，直到时间A.d+1。
- 所以我们只需要在时间A.s的时候把A扔进队列，在A.t+1的时间把A弹出队列便可。
转移方程：
- 如果有红包，屏蔽 $$ dp[j+1][i+1] = min(dp[j+1][i+1],dp[j][i]) $$
- 如果有红包，不屏蔽 $$ dp[j][A.d+1] = min(dp[j][A.d+1],dp[j][i]) $$
- 如果没红包 $$ dp[j][i+1] = min(dp[j][i+1],dp[j][i]) $$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int n,m,k;
struct node{
    int s,t,d,w;
    friend bool operator < (node a,node b){
        return a.s<b.s;
    }
}p[maxn];
struct node2{
    int t,d,w;
    node2(int t=0,int d=0,int w=0):t(t),d(d),w(w){}
    friend bool operator < (node2 a,node2 b){
        if(a.w==b.w){
            return a.d<b.d;
        }return a.w<b.w;
    }
};
ll dp[205][100005];
int main(){
    memset(dp,0x3f,sizeof dp);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d%d%d",&p[i].s,&p[i].t,&p[i].d,&p[i].w);
    }sort(p+1,p+1+k);
    priority_queue<node2>pq;
    int pos=1;
    ll ans=1e18;
    for(int i=0;i<=m;i++)dp[i][0]=dp[i][1]=0;
    for(int i=1;i<=n;i++){
        while(p[pos].s<=i&&pos<=k){
            pq.push(node2(p[pos].t,p[pos].d,p[pos].w));
            pos++;
        }
        for(int j=0;j<=m;j++){
            while(!pq.empty()){
                if(pq.top().t<i)pq.pop();
                else break;
            }
            if(pq.empty()){
                dp[j][i+1]=min(dp[j][i+1],dp[j][i]);
            }
            else{
                node2 now = pq.top();//pq.pop();
                if(j+1<=m)dp[j+1][i+1]=min(dp[j+1][i+1],dp[j][i]);
                dp[j][now.d+1]=min(dp[j][now.d+1],dp[j][i]+now.w);
            }
        }
    }
    for(int i=0;i<=m;i++)ans=min(ans , dp[i][n+1]);
    cout<<ans;
    return 0;
}