Codeforces Round #390 (Div. 2)

/*Codeforces Round #390 (Div. 2)时间: 2017/02/16A题题意：将集合分成几个小集合，要求小集合的和不为0.题解：遍历过去，一直到不满足集合并数字非0前生成一个集合*/#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <iostream>#include <queue>using namespace std;const int INF = 0x3f3f3f3f;const int N = 110;int a[N];int rel[N],rer[N];int main(){    int n;    while(~scanf("%d",&n))    {        int flag = 0;        for(int i = 1; i <= n; i++)        {            scanf("%d",&a[i]);            if(a[i])                flag = 1;        }        if(!flag)            puts("NO");        else        {            puts("YES");            int r = 1,l = 1;            int sum = 0;            int k = 0;            while(r <= n)            {                sum += a[r];                if(!sum && a[r])                {                    rel[k] = l;                    rer[k++] = r-1;                    l = r;                }                else                    r++;            }            rel[k] = l;            rer[k++] = r-1;            PRintf("%d/n",k);            for(int i = 0; i < k; i++)                printf("%d %d/n",rel[i],rer[i]);        }    }    return 0;}
/*Codeforces Round #390 (Div. 2)时间: 2017/02/16B题题意：给你一个4*4的棋盘，谁先连成三子谁赢，‘x’为先手下的棋，‘o’为后手下的棋，‘.’为空，问先手下一步能不赢题解：将枚举每个空格位置，判断位置可行性*/#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <iostream>#include <queue>using namespace std;const int INF = 0x3f3f3f3f;const int N = 10;int p[N][N];bool hefa(int x,int y){    if(x >= 0 && x <= 3 && y >= 0 && y <= 3)        return true;    return false;}bool pan(int x,int y){    if(hefa(x-1,y) && hefa(x-2,y) && p[x-1][y] == 1 && p[x-2][y] == 1)        return true;    if(hefa(x-1,y-1) && hefa(x-2,y-2) && p[x-1][y-1] == 1 && p[x-2][y-2] == 1)        return true;    if(hefa(x+1,y) && hefa(x+2,y) && p[x+1][y] == 1 && p[x+2][y] == 1)        return true;    if(hefa(x+1,y+1) && hefa(x+2,y+2) && p[x+1][y+1] == 1 && p[x+2][y+2] == 1)        return true;    if(hefa(x-1,y-1) && hefa(x+1,y+1) && p[x-1][y-1] == 1 && p[x+1][y+1] == 1)        return true;    if(hefa(x-1,y) && hefa(x+1,y) && p[x-1][y] == 1 && p[x+1][y] == 1)        return true;    if(hefa(x,y-1) && hefa(x,y-2) && p[x][y-1] == 1 && p[x][y-2] == 1)        return true;    if(hefa(x-1,y+1) && hefa(x-2,y+2) && p[x-1][y+1] == 1 && p[x-2][y+2] == 1)        return true;    if(hefa(x,y+1) && hefa(x,y+2) && p[x][y+1] == 1 && p[x][y+2] == 1)        return true;    if(hefa(x+1,y-1) && hefa(x+2,y-2) && p[x+1][y-1] == 1 && p[x+2][y-2] == 1)        return true;    if(hefa(x+1,y-1) && hefa(x-1,y+1) && p[x+1][y-1] == 1 && p[x-1][y+1] == 1)        return true;    if(hefa(x,y-1) && hefa(x,y+1) && p[x][y-1] == 1 && p[x][y+1] == 1)        return true;    return false;}int main(){    char s[N];    while(~scanf("%s",s))    {        int a;        for(int j = 0; j < 4; j++)        {            if(s[j] == 'x')                a = 1;            else if(s[j] == '.')                a = 0;            else                a = 2;            p[0][j] = a;        }        for(int i = 1; i < 4; i++)        {            scanf("%s",s);            for(int j = 0; j < 4; j++)            {                if(s[j] == 'x')                    a = 1;                else if(s[j] == '.')                    a = 0;                else                    a = 2;                p[i][j] = a;            }        }        int flag = 0;        for(int i = 0; i < 4; i++)        {            for(int j = 0; j < 4; j++)            {                //printf("%d ",p[i][j]);                if(!p[i][j] && pan(i,j))                {                    flag = 1;                    break;                }            }            //puts("");            if(flag)                break;        }        if(flag)            puts("YES");        else            puts("NO");    }    return 0;}
/*Codeforces Round #390 (Div. 2)时间: 2017/02/16D题题意：给你n个具有范围的礼券，选择k个礼券，要求k个礼券交叉包含的范围最大，输出范围大小和选择的礼券。题解：要选k个礼券维护最大，我们要使礼券交叉左极限小，右极限大。这样看来将礼券按左极限排序，然后右极限用优先队列维护即可。*/#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <iostream>#include <queue>using namespace std;const int INF = 0x3f3f3f3f;const int N = 300010;struct asd{    int l,r,id;    friend bool Operator< (asd n1,asd n2)    {        return n1.r > n2.r;    }}a[N];bool cmp(asd n1,asd n2){    return n1.l < n2.l;}int main(){    int n,k;    while(~scanf("%d%d",&n,&k))    {        for(int i = 1; i <= n; i++)        {            scanf("%d%d",&a[i].l,&a[i].r);            a[i].id = i;        }        sort(a+1,a+n+1,cmp);        priority_queue<asd> q;        int ans = 0,res = 0;        for(int i = 1; i <= n; i++)        {            asd temp;            if(!q.empty())                temp = q.top();            if(q.size() < k)                q.push(a[i]);            else if(temp.r < a[i].r)            {                q.pop();                q.push(a[i]);            }            if(q.size() == k)            {                temp = q.top();                if(temp.r-a[i].l+1 > ans)                {                    ans = temp.r-a[i].l+1;                    res = i;                }            }        }        printf("%d/n",ans);        if(ans)        {            int id = 0;            for(int i = 1; i <= res && id < k; i++)            {                if(a[res].l+ans-1 <= a[i].r)                {                    printf("%d ",a[i].id);                    id++;                }            }        }        else        {            for(int i = 1; i <= k; i++)                printf("%d ",i);        }        puts("");    }    return 0;}