首页 > 其他分享 >Codeforces Round 871 (Div. 4)

Codeforces Round 871 (Div. 4)

时间：2023-05-07 12:56:14浏览次数：54  
标签：typedef const int ll cin long Codeforces Div 871

Codeforces Round 871 (Div. 4)

A - Love Story

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s;
    cin>>n;
    string a="codeforces";
    while(n--){
        cin>>s;
        int c=0;
        for(int i=0;i<10;++i){
            if(s[i]!=a[i])c++;
        }
        cout<<c<<'\n';
    }
    return 0;
}
View Code

 

B - Blank Space

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int res=0;
        for(int i=0,x,ma=0;i<n;++i){
            cin>>x;
            if(x==0)ma++;
            else ma=0;
            res=max(res,ma);
        }
        cout<<res<<'\n';
    }

    return 0;
}
View Code

 

C - Mr. Perfectly Fine

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int l=INF,r=INF,lp=-1,rp=-1,a=INF;
        string s;
        for(int i=0,m;i<n;++i){
            cin>>m>>s;
            if(s[0]=='1'&&s[1]=='1')a=min(m,a);
            else{
                if(s[0]=='1')l=min(l,m),lp=i;
                if(s[1]=='1')r=min(r,m),rp=i;
            }
        }
        if((lp==-1||rp==-1)&&a==INF)cout<<"-1\n";
        else{
            cout<<min(a,l+r)<<'\n';
        }
    }

    return 0;
}
View Code

 

D - Gold Rush

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e7+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n,m;
bool st[N];
bool bfs(){
    memset(st,false,sizeof st);
    queue<int>q;
    q.push(n);
    st[n]=true;
    while(q.size()){
        int f=q.front();q.pop();
        if(f==m){
            return true;
        }
        if(f%3==0){
            if(!st[f/3*2])q.push(f/3*2),st[f/3*2]=true;
            if(!st[f/3])q.push(f/3),st[f/3]=true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        if(n>=m&&bfs())cout<<"YES\n";
        else cout<<"NO\n";
    }

    return 0;
}
View Code

 

E - The Lakes

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n,m;
int a[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int bfs(int x,int y){
    int res=a[x][y];
    queue<PII>q;
    q.push({x,y});
    a[x][y]=0;
    while(q.size()){
        auto f=q.front();q.pop();
        int x1=f.first,y1=f.second;
        for(int i=0;i<4;++i){
            int xx=x1+dx[i],yy=y1+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]>0){
                res+=a[xx][yy];
                q.push({xx,yy});
                a[xx][yy]=0;
            }
        }
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        int res=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)cin>>a[i][j];
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(a[i][j]>0){
                    res=max(res,bfs(i,j));
                }
            }
        }
        cout<<res<<'\n';
    }

    return 0;
}
View Code

 

F - Forever Winter

思路：求每个节点的入度，除了叶子节点的入度为1，剩余的入度只有两种或一种；若为两种，数量少的为中心

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n,m;
int ru[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        memset(ru,0,sizeof ru);
        for(int i=0,u,v;i<m;++i){
            cin>>u>>v;
            ru[u]++,ru[v]++;
        }
        map<int,int>mp;
        for(int i=1;i<=n;++i){
            if(ru[i]>1){
                mp[ru[i]]++;
            }
        }
        if(mp.size()==1){
            int c=mp.begin()->first;
            cout<<c<<' '<<c-1<<'\n';
        }
        else{
            int a[2],b[2],i=0;
            for(auto u:mp){
                a[i]=u.first;
                b[i++]=u.second;
            }
            if(b[0]<b[1])swap(b[0],b[1]),swap(a[0],a[1]);
            cout<<a[1]<<' '<<a[0]-1<<'\n';
        }
    }

    return 0;
}
View Code

 

G - Hits Different

思路：a[i][j]表示第i行第j列的数，a[i][j]=a[i-1][j]+a[i-1][j-1]-a[i-2][j-1]，（有被重复加的格子）；第i层的数有i*（i+1）/2个，前i层的数有i*（i+1）*（i+2）/6个，可以二分求出层数，也可以直接用数组标记每个数的位置

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1500+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll t,n,a[N],idx;
ll b[N][N];
void P(){
    ll i;
    for(i=1;;++i){
        a[i]=i*(i+1)/2;
        if(a[i]>=1e6)break;
    }idx=i;
    ll c=1;
    for(ll k=1;k<=idx;++k){
        for(ll j=1;j<=k;++j){
            b[k][j]=c*c;c++;
            b[k][j]+=b[k-1][j]+b[k-1][j-1];
            if(k>2&&j!=1&&j!=k)b[k][j]-=b[k-2][j-1];
        }
    }
    
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    P();
    while(t--){
        cin>>n;
        ll p= lower_bound(a+1,a+idx+1,n)-a;
        ll i=p,j=n-a[p-1];
        cout<<b[i][j]<<'\n';
    }
    return 0;
}
View Code

 

标签：typedef,const,int,ll,cin,long,Codeforces,Div,871
From： https://www.cnblogs.com/bible-/p/17379162.html

相关文章

  • Codeforces 871 div4(重拳出击)
    Codeforces871div4ABC简单题D题意每次操作可以将当前的数分成两份，一份是\(\frac{1}{3}\)，一份是\(\frac{2}{3}\)，问当前数n可否进行若干次操作，最终出现一份大小为m的片。递归一下就好了，数据最大才\(10^7\)代码voiddfs(intx){ if(x==m){flag=1;return;} if(flag)re......
  • Codeforces Round 870 (Div. 2)
    CodeforcesRound870(Div.2)A-TrustNobody思路：枚举每一种说谎人数x，若a[i]大于x则说谎人数加一，判断最后说谎总人数是否为x，若是则输出x，结束枚举；若没有满足的x则-1#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;......
  • Codeforces 1817F - Entangled Substrings（SA）
    为什么赛时不开串串题？为什么赛时不开串串题？为什么赛时不开串串题？为什么赛时不开串串题？为什么赛时不开串串题？一种SA做法，本质上和SAM做法等价，但是说来也丢人，一般要用到SAM的题我都是拿SA过的/wul考虑将\(ac\)看作一个整体。记\(\text{occ}(S)\)为\(S\)出现位置的集......
  • Codeforces Round 848 (Div. 2)C
    B.TheForbiddenPermutation一定要注意题目中说的是对于alli满足才算不好的，我们做的时候只要破坏一个i这个a就不算好的了,被这一点坑了，没注意到all。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=2e5+10;intp[N],a[N];vo......
  • Codeforces Round 856 (Div. 2)C
    C.ScoringSubsequences思路：我们想要找到满足的最大值的长度最长的的区间，因为单调不减，所以更大的数一定在最大值的里面包含，所以我们用两个指针维护这样一个满足当前i的最大值区间，当新来一个数，这时我们答案里面一定要包含这个数，我们看能否保持这个长度，能不能保持需要看j指针所指......
  • Codeforces——870
    A.TrustNobody题目大意给你一个长度为\(n\)的数组\(a\)，\(a\)中每个元素\(a_i\)表示当前人认为\(n\)个人中至少有\(a_i\)个人说谎，让你找出说谎的人的个数。思路：枚举说谎人数\(x\)，遍历\(a\)数组，对于当前\(a_i\)，如果有\(a_i\geqx\)，那么显然第\(i\)个人在说谎，记录人数看是否等......
  • [CodeForces-143A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch设有一个\(2\times2\)的棋盘，上面可以填入\(1-9\)的数字。给出\(6\)个数字，为每行每列以及每个对角线上的数字之和，求相应的摆放方式，无解输出\(-1\)。PartIIIAnalysis观察此题数据规模，不难发现数据......
  • [CodeForces-1104A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个整数\(n\)。将\(n\)拆分成一个数列\(a_1,a_2,a_3,\dots,a_m\)。使得\(\sum\limits_{k=1}^{m}a_k=n\)，每个\(a_i\in[0,9]\)且数列中不相同的数的数量尽量少。PartIIIAnalysis我们很容易......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\)，表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\)，第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\)，表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\)，第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99