`
暴风雪
  • 浏览: 389014 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

Codeforces Round #268 (Div. 2)

 
阅读更多

A判断输入的数字有没有覆盖1--n,n最大只有100,所以直接暴力

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<int ,int>mmp;
int n;
int main(){
    int i,j,k,b,a;
    while(scanf("%d",&n)!=EOF){
        mmp.clear();
        scanf("%d",&a);
        while(a--){
            scanf("%d",&b);
            mmp[b]=1;
        }
        scanf("%d",&a);
        while(a--){
            scanf("%d",&b);
            mmp[b]=1;
        }
        bool flag=0;
        for(i=1;i<=n;i++){
            if(mmp[i]==0){
                flag=1;
                break;
            }
        }
        if(flag==1){
            printf("Oh, my keyboard!\n");
        }else{
            printf("I become the guy.\n");
        }
    }
    return 0;
}

 

B,如果数据量很大的话可能会用rmq吧,这里直接暴力判定

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
bool vis1[3000];
bool mov[3000];
int main(){
    int p,q,l,r,i,j,k,a,b,c,d;
    while(scanf("%d%d%d%d",&p,&q,&l,&r)!=EOF){
        memset(vis1,0,sizeof(vis1));
        memset(mov,0,sizeof(mov));
        for(i=0;i<p;i++){
            scanf("%d%d",&a,&b);
            for(j=a;j<=b;j++)vis1[j]=1;
        }
        for(i=0;i<q;i++){
            scanf("%d%d",&a,&b);
            for(j=l;j<=r;j++){
                c=a+j;
                d=b+j;
                for(k=c;k<=d;k++){
                    if(vis1[k]){
                        mov[j]=1;
                        break;
                    }
                }
            }
        }
        int res=0;
        for(i=l;i<=r;i++){
            if(mov[i])res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

 

C,这一场最逗比的一题。题意是给出n,用1,2,3,4……n-1,n,这n个数字,只有加减乘算24,为什么逗比呢,看代码就知道了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
int main(){
    int i,j,k;
    while(scanf("%d",&n)!=EOF){
        if(n<=3){
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        if(n%2==0){
            printf("3 * 4 = 12\n");
            printf("12 * 2 = 24\n");
            printf("24 * 1 = 24\n");
            for(i=5;i<n;i+=2){
                printf("%d - %d = 1\n",i+1,i);
            }
            for(i=5;i<n;i+=2){
                printf("24 * 1 = 24\n");
            }
        }else{
            printf("5 * 4 = 20\n");
            printf("20 + 2 = 22\n");
            printf("22 + 3 = 25\n");
            printf("25 - 1 = 24\n");
            for(i=6;i<n;i+=2){
                printf("%d - %d = 1\n",i+1,i);
            }
            for(i=6;i<n;i+=2){
                printf("24 * 1 = 24\n");
            }
        }
    }
    return 0;
}

 

D,裸的2-sat,才发现当年的2-sat模板很久没用快发霉了,就当是来验模板吧。这里构图要注意一点:如果第I位数选择a集合时,第J 位数也要选a,同时也要连接一条边第j位选b时第i位也要选b

#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
#include<map>
using namespace std;
const int inf=1<<31;
const int nMax=300015;
const int mMax=1000010;
class edge{
public:
    int u,v,nex;
};edge e[mMax],e2[mMax];
int k,head[nMax],head2[nMax],k2;//head[i]是以点i为起点的链表头部
int dfn[nMax],low[nMax],sta[nMax],top,atype,ans[nMax],belon[nMax],dep;   //atype 强连通分量的个数


void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b
 //   cout<<a<<" add "<<b<<endl;
    e[k].u=a;
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}


void addedge2(int a,int b){
 //   cout<<a<<" 222add222 "<<b<<endl;
    e2[k2].u=a;
    e2[k2].v=b;
    e2[k2].nex=head2[a];
    head2[a]=k2;k2++;
}


int tim1[nMax],tim2[nMax],cost[nMax],in[nMax],color[nMax],oppo[nMax],que[nMax];//囧
bool insta[nMax];


void Tarjan(int u){
    int v,i;
    low[u]=dfn[u]=++dep;
    insta[u]=1;
    sta[++top]=u;
    for(i=head[u];i;i=e[i].nex){
        v=e[i].v;
        if(!dfn[v]){
            Tarjan(v);
            if(low[u]>low[v])
                low[u]=low[v];
        }
        else if(insta[v]&&low[u]>dfn[v])
            low[u]=dfn[v];
    }
    if(low[u]==dfn[u]){
        atype++;
        do{
            v=sta[top--];
            insta[v]=false;
            belon[v]=atype;
        }while(u!=v);
    }
    return;
}


void buildremap(){
    int i;
    for(i=1;i<k;i++){
        if(belon[e[i].u]!=belon[e[i].v]){
            addedge2(belon[e[i].v],belon[e[i].u]);
            in[belon[e[i].u]]++;
        }
    }
}

int n,m,a,b,num[100030];
map<int,int>mpp;

void topsort(){
    int i,l=0,r=0,u,v;
    for(i=1;i<=atype;i++){
        if(in[i]==0){
            que[r++]=i;
      //      cout<<"inque "<<i<<endl;
        }
    }
    while(l<r)  {
        u=que[l++];
        if(color[u]==0){
            color[u]=1;
            color[oppo[u]]=-1;
   //         cout<<u<<" u="<<color[u]<<" oppou="<<oppo[u]<<" colorop="<<color[oppo[u]]<<endl;
        }
        v=head2[u];
        while(v!=0){
            if(--in[e2[v].v]==0){
     //           cout<<"inque "<<e2[v].v<<endl;
                que[r++]=e2[v].v;
            }
            v=e2[v].nex;
        }
    }
    for(i=1;i<=n;i++){
        if(color[belon[i*2]]==1)
            ans[i]=1;
    }
}


void init(){
    k=k2=1;
    dep=1;
    top=atype=0;
    memset(ans,0,sizeof(ans));
    memset(color,0,sizeof(color));
    memset(in,0,sizeof(in));
    memset(insta,0,sizeof(insta)); //是否在栈中
    memset(head,0,sizeof(head));   //静态链表头指针
    memset(low,0,sizeof(low));     //Tarjan的low数组
    memset(dfn,0,sizeof(dfn));     //Tarjan的dfn数组
    memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
    memset(head2,0,sizeof(head2));
}



bool judge(){
    for(int i=1;i<=n;i++){
        if(belon[i*2]==belon[i*2+1]){
            return 0;
        }
        oppo[belon[i*2]]=belon[i*2+1];
        oppo[belon[i*2+1]]=belon[i*2];
    }
    return 1;
}

int main(){
    int i,tmp;
    while(scanf("%d%d%d",&n,&a,&b)!=EOF){
        mpp.clear();
        for(i=1;i<=n;i++){
            scanf("%d",&num[i]);
            mpp[num[i]]=i;
        }
        //i*2   A
        //i*2+1 B
        init();
        bool flag=1;
        for(i=1;i<=n;i++){
            tmp=num[i];
            if(mpp[a-tmp]==0&&mpp[b-tmp]==0){
                flag=0;
                break;
            }
            if(mpp[a-tmp]!=0&&mpp[b-tmp]==0){
                addedge(i*2+1,i*2);
                addedge(i*2,mpp[a-tmp]*2);
                addedge(mpp[a-tmp]*2+1,i*2+1);
            }
            if(mpp[a-tmp]==0&&mpp[b-tmp]!=0){
                addedge(i*2,i*2+1);
                addedge(i*2+1,mpp[b-tmp]*2+1);
                addedge(mpp[b-tmp]*2,i*2);
            }
            if(mpp[b-tmp]!=0&&mpp[a-tmp]!=0){
                addedge(i*2,mpp[a-tmp]*2);
                addedge(mpp[a-tmp]*2+1,i*2+1);
                addedge(i*2+1,mpp[b-tmp]*2+1);
                addedge(mpp[b-tmp]*2,i*2);
            }
        }
        if(!flag){
            printf("NO\n");
            continue;
        }
        for(i=2;i<=2*n+1;i++){
            if(!dfn[i])Tarjan(i);
        }
        if(judge()){
            printf("YES\n");
            buildremap();
            topsort();
            for(i=1;i<n;i++){
                printf("%d ",1-ans[i]);
            }printf("%d\n",1-ans[n]);
        }
        else printf("NO\n");
    }
    return 0;
}

 

0
0
分享到:
评论

相关推荐

    Codeforces Round #723 (Div. 2).md

    Codeforces Round #723 (Div. 2).md

    Codeforces Round 961 (Div. 2) 编程竞赛的详细解析

    codeforces round 961 (div. 2)

    Codeforces Round 961 (Div. 2):深度解析与实战技巧.pdf

    ### Codeforces Round 961 (Div. 2):深度解析与实战技巧 #### 引言 Codeforces 是一个国际知名的在线编程竞赛平台,它汇聚了来自世界各地的编程爱好者和专业人士。每一轮比赛都旨在测试参赛者的算法思维、编程...

    codeforces round 962 (div. 3)tion-ma笔记

    codeforces round 962 (div. 3)tion-ma笔记

    codeforces round 961 (div. 2)

    ### Codeforces Round 961 (Div. 2) A题解析 #### 题目背景 Codeforces Round 961 (Div. 2) 是一场针对中级水平程序员的编程竞赛,通常会包含几个不同难度级别的题目。A题作为入门级题目,旨在测试参赛者的基础算法...

    codeforces round 962 (div. 3).docx

    Codeforces Round 962 (Div. 3) 是一场编程竞赛,其中包含了多个编程题目,每个题目都有其独特的挑战和解题思路。以下是对该竞赛中部分题目的简要介绍及解题思路概述: A题: Legs 题意: 一只鸡有2条腿,一头奶牛有...

    codeforces round 962 (div. 3) .zip

    Codeforces Round 962 (Div. 3) 是一场编程竞赛,旨在测试参赛者在算法和数据结构方面的能力。由于篇幅限制,我将对这场竞赛中的几个关键问题进行详细解析,但请注意,由于具体实现细节可能因题目而异,且无法在此...

    Codeforces Round 964 (Div. 4).pdf

    A~G

    Codeforces Round #627 (Div. 3) C. Frog Jumps(思维)

    传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l

    Codeforces Round #627 (Div. 3) B. Yet Another Palindrome Problem

    就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...

    Codeforces Round #479 (Div. 3) E. Cyclic Components

    E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...

    Codeforces Round #629 (Div. 3) E.Tree Queries (DFS)

    Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...

    Codeforces Round #627 (Div. 3) D. Pair of Topics(二分,思维)

    ### Codeforces Round #627 (Div. 3) D. Pair of Topics(二分,思维) #### 题目背景与概述 本题目来自Codeforces Round #627 (Div. 3),编号为D的题目“Pair of Topics”,这是一道结合了二分搜索与逻辑思维的...

    Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系

    标题中的"Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系"指的是一场编程竞赛中的问题,涉及到树结构的查询和深度优先搜索(DFS)来判断节点间的祖先关系。这个问题的目标是设计算法来确定在...

    Codeforces Round #618 (Div. 2) C. Anu Has a Function(进制,位运算,贪心)

    题目“Anu Has a Function”源自Codeforces Round #618 (Div. 2)的一道竞赛编程问题,主要涉及进制转换、位运算和贪心算法。问题要求定义一个函数f(x, y) = (x | y) - y,并对数组进行排序,以最大化最后的结果。 ...

    Codeforces Round 962

    Codeforces Round 962 (Div. 3) 编程竞赛 Codeforces Round 962 (Div. 3) 编程竞赛 Codeforces Round 962 (Div. 3) 编程竞赛 Codeforces Round 962 (Div. 3) 编程竞赛

    Codeforces Round #628 (Div. 2)

    给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...

    Codeforces Round #627 (Div. 3) A. Yet Another Tetris Problem

    给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai​变成ai​+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...

    Codeforces Round #628 (Div. 2) A. EhAb AnD gCd

    输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...

Global site tag (gtag.js) - Google Analytics