首页 > 其他分享 >Educational Codeforces Round 71 (Rated for Div. 2)

Educational Codeforces Round 71 (Rated for Div. 2)

时间：2023-07-25 13:22:19浏览次数：52  
标签：Educational Rated const int Codeforces long typedef dp define

Educational Codeforces Round 71 (Rated for Div. 2)

A - There Are Two Types Of Burgers

思路：价格高的优先取

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;

int st[205][205],vis[205][205];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

void solve(){
    int ans=0;
    int b,p,f;cin>>b>>p>>f;
    int h,c;cin>>h>>c;
    if(h>=c){
        int cp=min(b/2,p);
        b-=cp*2;
        ans+=cp*h;
        int cf=min(b/2,f);
        ans+=cf*c;
    }else{
        int cf=min(b/2,f);
        b-=cf*2;
        ans+=cf*c;
        int cp=min(b/2,p);
        ans+=cp*h;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

B - Square Filling

思路：遍历每个点，若以该点为左上角的2*2矩阵都为1，则取该点，并将b对应的点都覆盖为1，最后判断a、b是否相等

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=50+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int a[N][N],b[N][N];
void solve(){
    int n,m;cin>>n>>m;
    vector<PII>ans;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)cin>>a[i][j];
    }
    for(int i=1;i<n;++i){
        for(int j=1;j<m;++j){
            if(a[i][j]&&a[i+1][j]&&a[i][j+1]&&a[i+1][j+1]){
                b[i][j]=b[i+1][j]=b[i][j+1]=b[i+1][j+1]=1;
                ans.push_back({i,j});
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]!=b[i][j]){
                cout<<"-1\n";
                return ;
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans)cout<<v.first<<' '<<v.second<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

C - Gas Pipeline

题意：1的高度一定为2，0的高度可以为1/2，问管道和柱子的最小总cost

思路：

  • dp

　　dp[i][j]表示前i段高度为j的最小cost；

　　首尾都是0，所以dp[0][1]=a+b，若s[1]='1'，则dp[0][2]=2*a+b；

　　从1开始遍历所有s，若s[i]=1，dp[i][2]=dp[i-1][2]+2*b+a；

　　　　　　　　　　　若s[i]=0，1. s[i-1]=='1'且s[i+1]=='1'　：dp[i][2]=dp[i-1][2]+2*b+a；

　　　　　　　　　　　　　　　  2. s[i-1]=='0'且s[i+1]=='1'　：dp[i][2]=min(dp[i-1][2]+2*b+a,dp[i-1][1]+2*a+b)；

　　　　　　　　　　　　　　　  3. s[i-1]=='1'　：dp[i][2]=dp[i-1][2]+2*b+a；

　　　　　　　　　　　　　　　　　　　　　　　dp[i][1]=dp[i-1][2]+2*a+2*b；

　　　　　　　　　　　　　　　  4.s[i-1]=='0'且s[i+1]=='0'　：dp[i][2]=min(dp[i-1][1]+2*a+b,dp[i-1][2]+2*b+a)；

　　　　　　　　　　　　　　　　　　　　　　　　　　　　 dp[i][1]=min(dp[i-1][2]+2*a+2*b,dp[i-1][1]+a+b)；

  • 贪心

　　对于0的地方，可以选两种高度，找到每段连续的0，取两种高度cost少的

 

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int dp[N][3];
void solve(){
    int n,a,b;cin>>n>>a>>b;
    string s;cin>>s;
    for(int i=0;i<=n;++i)dp[i][1]=dp[i][2]=inf;
    if(s[1]=='0')dp[0][1]=a+b;
    else dp[0][2]=2*a+b;
    for(int i=1;i<n;++i){
        if(s[i]=='1')dp[i][2]=dp[i-1][2]+2*b+a;
        else{
            if(s[i-1]=='1'&&s[i+1]=='1')dp[i][2]=dp[i-1][2]+2*b+a;
            else if(s[i-1]=='1'){
                dp[i][2]=dp[i-1][2]+2*b+a;
                dp[i][1]=dp[i-1][2]+2*a+2*b;
            }else if(s[i-1]=='0'&&s[i+1]=='1')dp[i][2]=min(dp[i-1][2]+2*b+a,dp[i-1][1]+2*a+b);
            else{
                dp[i][2]=min(dp[i-1][1]+2*a+b,dp[i-1][2]+2*b+a);
                dp[i][1]=min(dp[i-1][2]+2*a+2*b,dp[i-1][1]+a+b);
            }
        }
    }
    cout<<dp[n-1][1]+b<<'\n';

}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    cin>>T;
    while(T--){
        solve();

    }
    return 0;
}
dp 
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=50+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int T=1;

void solve(){
    int n,a,b;cin>>n>>a>>b;
    string s;
    cin>>s;
    bool ok=false;
    int ans=n*2*b+(n+2)*a;
    for(int i=0,l=-1,r;i<n;++i){
        if(l==-1&&s[i]=='0'){
            l=i;r=i;
        }else if(s[i]=='0'){
            r=i;
        }else if(l!=-1){
            if(l==0){
                ans-=(r-l)*b;
            }else if(r-l>0){
                int aa=2;
                int bb=r-l;
                int d=aa*a-bb*b;
                if(d<0)
                    ans+=d;
            }
            l=-1;
        }
        if(i==n-1){
            ans-=(r-l)*b;
            if(l==0)ans-=2*a;
        }
    }//cout<<aa<<' '<<bb<<"\n";
    cout<<ans<<'\n';//cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //int T=1;
    //init();
    cin>>T;
    while(T--){
        solve();

    }
    return 0;
}
贪心

 

D - Number Of Permutations

题意：问s有多少种排序，使得p的a和b分别是递减的

思路：找出所有递增的，那么递减的即为n！减去递增的。

对于 1 2 2 3 4 4 4 5，可以求出递增的序列有 2！* 3！种，即每种数的个数的阶乘的积。

可以求出a和b的序列分别递增的数目，但还需减去其中重复的（在某种递增的序列中，另一个ai和令一个bi又组成了同样的序列）

将所有（a，b）按a从小到大排序，看是否存在a和b都是递增的情况，若存在则重复的情况就是该种情况的数量，同样的方法求出递增的数量即为重复的数量

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};

vector<int>fac(N);
vector<PII>ve;
map<int,int>mp1,mp2;
map<PII,int>mp3;
void init(){
    fac[0]=1ll;
    for(int i=1;i<N;++i)fac[i]=fac[i-1]*i%mod;
}
void solve(){
    int n;cin>>n;
    ve=vector<PII>(n);
    bool ok=true;
    for(int i=0;i<n;++i){
        cin>>ve[i].first>>ve[i].second;
        mp1[ve[i].first]++,mp2[ve[i].second]++;
        if(mp1[ve[i].first]==n||mp1[ve[i].second]==n)ok=false;
    }
    if(!ok){
        cout<<0;return ;
    }
    int ans,t=1;
    for(auto v:mp1)t=(t%mod*fac[v.second]%mod)%mod;
    ans=t%mod;
    t=1;
    for(auto v:mp2)t=(t%mod*fac[v.second]%mod)%mod;
    ans=(ans%mod+t%mod)%mod;
    sort(ve.begin(),ve.end());
    for(int i=1;i<ve.size();++i){
        if(ve[i].second<ve[i-1].second){ok=false;break;}
    }
    if(ok){
        for(auto v:ve)mp3[v]++;
        t=1;
        for(auto v:mp3){
            t=(t%mod*fac[v.second]%mod)%mod;
        }
        ans-=t;
    }
    cout<<((fac[n]%mod-ans)%mod+mod)%mod;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

E - XOR Guessing

思路：第一次的数中二进制的第7~14位都为0，第二次的数中二进制的第0~6位都为0，这样两次就可以分别求出x的二进制情况

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};


void init(){

}
void solve(){
    cout<<"? ";
    for(int i=1;i<=100;++i)cout<<" "<<i;cout<<'\n';
    int x;cin>>x;
    int ans=0;
    for(int i=7;i<14;++i)ans+=((x>>i&1)<<i);
    cout<<"? ";
    for(int i=1;i<=100;++i)cout<<" "<<(i<<7);cout<<'\n';
    cin>>x;
    for(int i=0;i<7;++i)ans+=((x>>i&1)<<i);
    cout<<"! "<<ans<<'\n';
}
signed main(){
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

F - Remainder Problem

思路：分块√5e5=707，对于大于707的可以直接暴力求，小于707的用ans[i][j]存%i等于j的答案

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};

int ans[705][705],a[N];

void solve(){
    int q;cin>>q;
    while(q--){
        int op,x,y;cin>>op>>x>>y;
        if(op==1){
            a[x]+=y;
            for(int i=1;i<=700;++i)ans[i][x%i]+=y;
        }else{
            if(x<=700)cout<<ans[x][y]<<'\n';
            else{
                int res=0;
                for(int i=y;i<N;i+=x)res+=a[i];
                cout<<res<<'\n';
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

标签：Educational,Rated,const,int,Codeforces,long,typedef,dp,define
From： https://www.cnblogs.com/bible-/p/17577442.html

相关文章

  • 题解 Codeforces Round 887 (Div 1+Div 2) / CF1853AB,CF1852ABCD
    下大分！悲！Div1只过了1A！！！但还是补完整场Div2吧。A.Desortinghttps://codeforces.com/problemset/problem/1853/Aproblem用操作：\([1,i]++,[i+1,n]--\)，使得数组不单调不降，求最小操作次数。\(n\leq10^5\)。solution操作等同于在差分数组上选出\(i\)，做\(c_1:=c_1+1,c_i:......
  • Codeforces Round #887 Div.2 A-E
    CodeforcesRound#887Div.2一定要手玩哦前言：一定要手玩，一定要手玩！我今早一手玩发现C很TM简单，如果赛时我能切C说不定直接上1800.。。。时隔多年，我的CodeforcesRating(1718)再次超越了@cqbzlhy(1674)！！！赛时错误：B题出得太慢了->劣于pzj半小时。%%%pzjC没有手玩，瞪眼半天......
  • Codeforces Round #885 数学专场
    妙，我只能说妙。今天补DEF发现除了F诡秘的杨辉三角，我都能独立做出来。但为什么我感觉DE难度不如C！！！！A题意：一个人站在\((x,y)\)处，而其他人分别在\((x_1,y_1)\dots(x_n,y_n)\)，每一次这个人先移动一步到上下左右四个格子，然后其他\(n\)个人再移动一步，求是否永远这个人与其他人不......
  • Codeforces Round 887 (Div. 2)记录
    A.Desorting如果有$a_1\leqa_2\leq\ldots\leqa_{n-1}\leqa_n$，则称长度为$n$的数组$a$已排序。Ntarsis有一个长度为$n$的数组$a$。他可以对数组进行一种操作（0次或多次）：-选择一个索引$i$（$1\leqi\leqn-1$）。-将$1$加到$a_1,a_2,\ldots,a_i$。-用$a_{......
  • Codeforces Round 887(Div 2)（A-C）
    A.Desorting题目里说的无序是指后面的一个数大于前面一个数，所以只要有一个a[i+1]-a[i]<0就说明已经符合题目的无序要求了，不需要改变即可，即输出0如果有该序列是非严格递增的根据题目所说的改变就只需要求出最小的差值即可，最后用最小的差值除以2（因为每次可以让选中的部分之前的......
  • 【题解】Imbalanced Arrays - Codeforces 1852B
    出处：CodeforcesRound887链接：https://codeforces.com/problemset/problem/1852/B题目大意：给定一个包含\(n\)个非负整数的频次序列\(f\)。构造任意一个等长的整数序列\(b\)，要求①\(b\in[-n,n]\)but$b\neq0$②\(b\)中不存在相反数③对于每个坐标\(i\)......
  • Codeforces Round 886 (Div. 4)
    Dashboard-CodeforcesRound886(Div.4)-CodeforcesA.ToMyCritics判断任意两个大于10即可#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=2e5+10;signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);......
  • 【题解】Ntarsis' Set - Codeforces 1852A
    出处：CodeforcesRound887链接：https://codeforces.com/problemset/problem/1852/A题目大意：给定一个包含\(n\)个正整数的表示删除位置的严格升序序列\(p\)，以及另外一个连续正整数的被删除的无穷序列\(l\)。进行\(k\)次删除操作，每次操作从无穷序列\(l\)中同时删除位......
  • Educational Codeforces Round 71
    A.ThereAreTwoTypesOfBurgers#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){intb,p,f,h,c;cin>>b>>p>>f>>h>>c;b/=2;intres=0;for(inti......
  • Codeforces Round 887 (Div. 1) 题解
    https://codeforces.com/contest/1852/problemsA.Ntarsis'Sethttps://codeforces.com/contest/1852/problem/A感觉不是很一眼。\(n\)和\(k\)都是\(2\times10^5\)，不能暴力，设当前集合为\({1,2,\dots,10^{1000}}\)，那么被操作过一次的最小值就应该是\(\text{MEX}(0,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99