Educational Codeforces Round 87 (Rated for Div. 2)(D,E补题)

A,B,C1比较简单没什么说的,C2........图都画不出来,就是再考画图.......画出图不就是一个三角函数

D

两种做法
(1)树状数组

#include<iostream>
using namespace std;

int n;
int a[1000005],c[1000005]; //对应原数组和树状数组

int lowbit(int x){
    return x&(-x);
}

void updata(int i,int k){    //在i位置加上k
    while(i <= n){
        c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){        //求A[1 - i]的和
    int res = 0;
    while(i > 0){
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

int search(int l,int r,int num)
{
    int left = 1,right = r;
    int mid;
while(left < right)
{
  //这里不需要加1。我们考虑如下的情况，最后只剩下A[i],A[i + 1]。
  //首先mid = i，如果A[mid] > key，那么right = left = i，跳出循环，如果A[mid] < key，left = right = i + 1跳出循环，所有不会死循环。
  mid = (left + right) / 2;
  if(getsum(mid) >= num)//如果要求大于等于可以加上等于，也可以是check(A[mid])
    right = mid;
  //因为找的是大于key的第一个元素，那么比A[mid]大的元素肯定不是第一个大于key的元素，因为A[mid]已经大于key了，所以把mid+1到后面的排除
  else
    left = mid + 1;
  //如果A[mid]小于key的话，那么A[mid]以及比A[mid]小的数都需要排除，因为他们都小于key。不可能是第一个大于等于key的元素，
}
return right;
}



int main()
{
    int q;
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i++)
    scanf("%d",&a[i]);
    for(int i = 1; i <= n ;i++)
    {
        updata(a[i],1);
    }
    int flag = 0;
    for(int i = 1; i <= q; i++)
    {
        int k;
        scanf("%d",&k);
        if(k > 0)
        {
            updata(k,1);
            flag++;
        }
        else{
            k = -k;
            flag -- ;
            int pos = search(1,n,k);
            if(pos > 0)
            updata(pos,-1);
        }
    }
    if(n + flag <= 0)
    printf("0\n");
    else{
        int pos = search(1,n,1);
        if(pos >= 1)
        printf("%d\n",pos);
    }
}

(2)二进制枚举答案
用二分直接对于每种情况,用数组判断大小,然后缩小区间,最后剩下的,就是答案

#include<bits/stdc++.h>
using namespace std;
int a[1000009];
int k[1000009];
int n,q;
int check(int x)
{
    int ans=0;
    for(int i=0; i<n; i++)
    {
        if(a[i]<=x)
            ans++;
    }
    for(int i=0; i<q; i++)
    {
        if(k[i]>0&&k[i]<=x)
            ans++;
        if(k[i]<0&&abs(k[i])<=ans)
            ans--;
    }
    return ans;
}
signed main()
{

    scanf("%d%d",&n,&q);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    for(int i=0; i<q; i++)
         scanf("%d",&k[i]);
    if(check(1e9)==0)
    {
        cout<<0;
        return 0;
    }
    int l=0,r=1e6+1;
    while(r>l)
    {
        int mid=r+l;
        mid/=2;
        if(check(mid)>0)
            r=mid;
        else
            l=mid;
    }
    cout<<r;
}

E

题意:给定一个图,n个点,m条边,然后对于每个点赋值,可以赋值为1,2,3,并且每个边的两点的差的绝对值为1,然后输出每个点的值,答案不唯一
题解:因为每个边的两点的差的绝对值为1,所以相当于赋值奇偶数
然后我们可以把图当成1棵树,根节点为奇数,第二层第四层....为偶数,第三层第五层为奇数,如果搜到某个点,发现它可以与之前某个已经搜过的点相连,那么如果这两个点奇偶性相同,那么整张图直接no
然后这样之后我们发现还要满足n1+n2+n3=n所以对于每张图不一定是以根节点为奇数开始的,然后进行一个dp,来确定每个图的起始点的奇偶性,如果奇偶数的点的关系与n1,n2,n3的不等,输出no,还有上面的都要有标记,最后再进行回溯来确定每个点

Educational Codeforces Round 87 (Rated for Div. 2)(D,E补题)

D

E

全站热榜