Educational Codeforces Round 71 (Rated for Div. 2)(ABCD)

偏执的太偏执、 2023-06-03 13:52 20阅读 0赞

A. There Are Two Types Of Burgers

题意：有两种汉堡，第一种可以卖h元，需要2个面包和一个牛肉，第二种可以买c元，需要两个面包和一个鸡肉；

问最多可以买多少钱；（自己沙雕，非要弄的跟题目给的变量一样，搞得一直用错，耽误了很多时间）

解：因为面包的数量一定，且两个所需的面包数都一样，所以直接按钱多的先做；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
     
     
     
    int main(){
        int T;
        cin>>T;
        while(T--){
            int b,p,f,h,c;
            cin>>b>>p>>f>>h>>c;
            int ans=0;
            b/=2;
            if(h>=c){
                ans+=min(b,p)*h;
                b-=p;
                if(b>0){
                    ans+=min(b,f)*c;
                }
     
            }
            else{
                ans+=min(b,f)*c;
                b-=f;
                if(b>0){
                    ans+=min(b,p)*h;
                }
            }
            cout<<ans<<endl;
        }
     
     
     
        return 0;
    }

B. Square Filling

题意：给你一个矩阵A和矩阵B，矩阵B初始全为0，每次操作可以选择x，y，让(x,y)(x+1,y)(x,y+1)(x+1,y+1)全变为1，问能否从B变为A，如果可以输出选择的x，y

不要求最小次数（这样就降低了难度了）

解：暴力全图，如果在A里选的2\*2的格子里有0就不能选，否则都选上，然后在最后再判断一下是否全部都符合A；（WA在存放答案的结构体没有开大，wa了4发，沙雕）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=150;
    int a[maxn][maxn];
    bool vis[maxn][maxn];
    struct node{
    int x,y;
    }ans[100000];
    int tot;
    bool check(int x,int y){
        if(a[x+1][y]==0||a[x][y+1]==0||a[x+1][y+1]==0||a[x][y]==0)
            return false;
        return true;
    }
    int main(){
        int n,m;
        cin>>n>>m;
        tot=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                if(a[i][j]==0)vis[i][j]=true;
            }
        }
        for(int i=1;i<=n-1;i++){
            for(int j=1;j<=m-1;j++){
                if(check(i,j)){
                    ans[tot].x=i,ans[tot++].y=j;
                    vis[i+1][j]=vis[i][j+1]=vis[i+1][j+1]=vis[i][j]=true;
                }
            }
        }
        int flag=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!vis[i][j]){
                    flag=0;
                }
            }
        }
        if(flag==0)cout<<"-1"<<endl;
        else {
            cout<<tot<<endl;
            for(int i=0;i<tot;i++){
                cout<<ans[i].x<<' '<<ans[i].y<<endl;
            }
        }
     
     
        return 0;
    }

C. Gas Pipeline

题意：在公路上搭建管道，如果遇到路口需要搭高度为2，不然就可以搭1，具体看图更能理解把；（[https://codeforces.com/contest/1207/problem/C][https_codeforces.com_contest_1207_problem_C]）

me：看这道题的时候，没想到管子和柱子的价格会影响结果，然后一直想贪心，写到后面，发现不行，沙雕了……然后好像是dp，不会写了…

解：dp\[i\]\[1\],dp\[i\]\[2\]表示在i位置时高度为1or2时的所需要的最小花费，dp不是很会，感觉讲不通……；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=2e5+100;
    int n;
    ll a,b;
    ll dp[maxn][3];
    char s[maxn];
    void init(int n){
        for(int i=0;i<=n;i++){
            dp[i][1]=dp[i][2]=1e18;
        }
    }
    int main(){
        int T;
        cin>>T;
        while(T--){
            cin>>n>>a>>b;
            init(n);
            cin>>s+1;
            dp[0][1]=b;
            for(int i=1;i<=n;i++){
                if((i==n)||(s[i]=='0'&&s[i+1]=='0')){
                    dp[i][1]=min(dp[i][1],dp[i-1][1]+a+b);//1-1
                    dp[i][1]=min(dp[i][1],dp[i-1][2]+2*a+b);//2-1
                    dp[i][2]=min(dp[i][2],dp[i-1][1]+2*a+2*b);//1-2
                    dp[i][2]=min(dp[i][2],dp[i-1][2]+a+2*b);//2-2
                }
                else{
                    dp[i][2]=min(dp[i][2],dp[i-1][1]+2*a+2*b);//1-2
                    dp[i][2]=min(dp[i][2],dp[i-1][2]+a+2*b);//2-2
                }
            }
            cout<<dp[n][1]<<endl;
        }
     
     
     
        return 0;
    }

D. Number Of Permutations

题意：给你n个集合，每个集合两个值，(xi,yi)；求这n个集合的所有排列数，满足 排列的xi不是递增的，且yi不是递增的；

解：根据容斥原理，ans=全排列-xi递增的排列数-yi递增的排列数+xiyi同时递增的排列数；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=3e5+10;
    const int mod=998244353;
    ll fac[maxn];
    void init(){
        fac[0]=1;
        for(ll i=1LL;i<maxn;i++){
            fac[i]=(1LL*(fac[i-1]%mod)*i)%mod;
        }
    }
    struct node{
        int x,y;
    }a[maxn];
    bool cmp1(node a,node b){
        if(a.x==b.x)return a.y<b.y;
        return a.x<b.x;
    }
    bool cmp2(node a,node b){
        if(a.y==b.y)return a.x<b.x;
        return a.y<b.y;
    }
    int main(){
        init();
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].x>>a[i].y;
        }
        sort(a+1,a+n+1,cmp1);
        ll both=1LL;
        for(int i=1;i<=n-1;i++){
            if(a[i].y>a[i+1].y){
                both=0LL;break;
            }
        }
        //cout<<both<<endl;
        int flagx=a[1].x;
        int cntx=1,cntb=1;
        ll ansx=1LL;
        node b=a[1];
        for(int i=2;i<=n;i++){
            if(a[i].x==flagx){
                cntx++;
            }
            else {
                ansx=((ansx%mod)*(fac[cntx]%mod))%mod;
                cntx=1;
                flagx=a[i].x;
            }
            if(i==n&&cntx!=1){
                ansx=((ansx%mod)*(fac[cntx]%mod))%mod;
                cntx=1;
                flagx=a[i].x;
            }
            if(b.x==a[i].x&&b.y==a[i].y){
                cntb++;
            }
            else{
                both=((both%mod)*(fac[cntb]%mod))%mod;
                cntb=1;
                b=a[i];
            }
            if(i==n&&cntb!=1){
                both=((both%mod)*(fac[cntb]%mod))%mod;
                cntb=1;
                b=a[i];
            }
        }
        sort(a+1,a+1+n,cmp2);
        ll ansy=1LL,cnty=1;
        int flagy=a[1].y;
        for(int i=2;i<=n;i++){
            if(flagy==a[i].y){
                cnty++;
            }
            else{
                ansy=((ansy%mod)*(fac[cnty]%mod))%mod;
                flagy=a[i].y;
                cnty=1;
            }
            if(i==n&&cnty!=1){
                ansy=((ansy%mod)*(fac[cnty]%mod))%mod;
                flagy=a[i].y;
                cnty=1;
            }
        }
        ansx%=mod;
        ansy%=mod;
        both%=mod;
        //cout<<ansx<<' '<<ansy<<' '<<both<<endl;
        ll ans=(fac[n]-ansx-ansy+both)%mod;
        while(ans<0)ans+=mod;
        ans%=mod;
        cout<<ans<<endl;
     
     
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11402885.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/7c43dbe68fa24fb8a7ac5deb9ffb5b3a.png
[https_codeforces.com_contest_1207_problem_C]: https://codeforces.com/contest/1207/problem/C