Articles12
Tags2
Categories0

Codeforces Round 637 (Div.1)


只包括div1的B和C的题解

传送门

题解比较简单 我也不写题意了 直接写思路

而且因为div2ABC大家都过了我就不献丑了,直接从2D1B开始

B.Nastya and Scoreboard

可以发现n只有2000 考虑DP,同时又能发现 因为越前面的数字对全局的影响越大,所以肯定要贪心求前面最大的数。因此思路就是 DP预处理+贪心

DP预处理的是:当前我在i这个位置,剩余k0根木棍,选了j(0<=j<=9)这个数字,那么我接下来能否用剩下的木棍(k0-选了j需要的木棍)使剩下的位置满足题目的要求。

DPi,j表示从当前的i到最后的n,能否用j根木棍满足题目要求

转移方式:从n到1遍历,再从0到k遍历,再遍历0到9,看能否由dp i+1,j转移过来

如果可以就标记1

最后贪心从头到尾遍历即可

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int dp[2020][2020];
int dig[10]={119,18,93,91,58,107,111,82,127,123};
int gun[10]={6,2,5,5,4,5,6,3,7,6};
int a[2020],sum[2020];char ch[10];
void cal(int j){ int now=1;int ans=0,cnt=0;
    for(int i=6;i>=0;i--){
        if(ch[i]=='1') ans+=now,cnt++;now*=2;
    }sum[j]=cnt;a[j]=ans;
}int main(){
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%s",ch);cal(i);
    }dp[n+1][0]=1;
    for(int i=n;i>=1;i--){
        for(int j=0;j<=k;j++){ if(!dp[i+1][j]) continue;
            for(int q=0;q<=9;q++){
                if(a[i]<=dig[q]&&((a[i]&dig[q])==a[i])){
                    if(j+gun[q]-sum[i]<=k) dp[i][j+gun[q]-sum[i]]=1;
                }
            }
        }
    }int now=0,flag=0;
    for(int i=1;i<=n;i++){
        for(int q=9;q>=0;q--){
            if(a[i]<=dig[q]&&((a[i]&dig[q])==a[i])){
                if(dp[i+1][k-now-(gun[q]-sum[i])]){
                    flag=1;printf("%d",q);now+=gun[q]-sum[i];break;
                }
            }
        }if(!flag) return printf("-1"),0;
    }
}

C.Nastya and Unexpected Guest

这是一道DP+图论题

先对m数组排个序,因为题目给的数据不一定有序

首先我们可以发现 m范围是1e4 g范围是1e3 所以可以想到dp

dp i,j表示的是当前在第i个点,绿灯还剩j秒时的最短时间

因为是最短时间,所以这就类似于最短路的思想

所以转移的方式是 一个点可以向它的左边或者右边走,比如3可以走到0或7,7可以走到3或者14 边界点特判一下。

然后既然是最短路 那转移的时候可以用类似dijkstra的思想

其中dpij的值的意思是 当前经过的周期,比如dpij=1 代表到了这个状态经过了1个(绿灯+红灯)的时间

但是我们能发现 dijkstra的复杂度不满足题目的要求 因为题目中光状态就有1e7个 会TLE

然后我们又发现,转移的时候要么在当前绿灯的范围内,要么到了下一个绿灯的周期中,所以dp的值在转移的时候要么不变要么加一,这时候我们就可以用双端队列代替dij中的优先队列,如果不变,那么push进头部,如果+1,push进尾部,这样也可以保证整个队列是有序的

最后枚举最终状态里的绿灯剩余时间,算最小值

(如果有哪里不懂可以边看代码边理解qwq)

Code

//其中 deque是双端队列

下文还会给出dijkstra优先队列优化的写法,如果不知道的话可以参考一下,大家应该都会吧嘤嘤嘤

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int maxe=1e3+5;
int a[maxn];int dp[maxn][maxe];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    sort(a+1,a+m+1);int g,r;scanf("%d%d",&g,&r);
    for(int i=1;i<=m;i++){
        for(int j=0;j<=g;j++) dp[i][j]=1e9;
    }dp[1][g]=0;deque<pii>q;q.push_front({1,g});
    while(!q.empty()){
        pii now=q.front();q.pop_front();
        int i=now.fi,rem=now.sc;
        if(i>1){ int dis=a[i]-a[i-1];
            if(dis<rem){
                if(dp[i-1][rem-dis]>dp[i][rem]){
                    dp[i-1][rem-dis]=dp[i][rem];q.push_front({i-1,rem-dis});
                }
            }else if(dis==rem){
                if(dp[i-1][g]>dp[i][rem]+1){
                    dp[i-1][g]=dp[i][rem]+1;q.push_back({i-1,g});
                }
            }
        }if(i<m){
            int dis=a[i+1]-a[i];
            if(dis<rem){
                if(dp[i+1][rem-dis]>dp[i][rem]){
                    dp[i+1][rem-dis]=dp[i][rem];q.push_front({i+1,rem-dis});
                }
            }else if(dis==rem){
                if(dp[i+1][g]>dp[i][rem]+1){
                    dp[i+1][g]=dp[i][rem]+1;q.push_back({i+1,g});
                }
            }
        }
    }ll ans=1e18;
    for(int i=1;i<g;i++){
        if(dp[m][i]!=1e9) ans=min(ans,1ll*dp[m][i]*(g+r)+g-i);
    }if(dp[m][g]!=1e9) ans=min(ans,1ll*dp[m][g]*(g+r)-r);
    if(ans==1e18) printf("-1");else printf("%lld\n",ans);
}
//dij优先队列 nlogn
#include<bits/stdc++.h>
#define pii pair<int,ll>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
const ll INF=1e10;
int vis[maxn],path[maxn];
ll dis[maxn];
vector<pii>g[maxn];
int n,m;
void dijkstra(int s){
    for(int i=1;i<=n;i++){
        dis[i]=INF;path[i]=-1;
    }dis[s]=0;
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int now=q.top().second;q.pop();
        if(vis[now]) continue;vis[now]=1;
        for(int i=0;i<g[now].size();i++){
            int e=g[now][i].first;ll c=g[now][i].second;
            if(dis[e]>dis[now]+c){
                dis[e]=dis[now]+c;
                q.push(make_pair(dis[e],e));
                path[e]=now;
            }
        }
    }
}int main(){
    int s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int a,b;ll c;
        scanf("%d%d%lld",&a,&b,&c);
        g[a].push_back(make_pair(b,c));
    }dijkstra(s);
    for(int i=0;i<n;i++){
        printf("%d %lld:",i+1,dis[i+1]);
        int now=i+1;
        while(path[now]!=-1) printf("%d ",path[now]),now=path[now];
        printf("\n");
    }
}
Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2020/04/24/cf637%20-%20%E5%89%AF%E6%9C%AC/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可