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,还有上面的都要有标记,最后再进行回溯来确定每个点

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define pii pair <int,int>

using namespace std;

const int N=5e3+9,M=1e5+9;
vector <int> adj[N];
int comp[N],num[N][2],cnt=0;
int par[N][N];
int a,b,c,ans[N];
bool mrk[N],dp[N][N],col[N],res[N];

void DFS1(int u,int x,int cl){
    mrk[u]=1;
    comp[u]=x;
    col[u]=cl;
    num[x][cl]++;
    for(int v:adj[u]){
        if(!mrk[v]) DFS1(v,x,!cl);
        else if(col[v]==col[u]){
            cout<<"NO",exit(0);
        }
    }
}

void DFS2(int u,int x){
    mrk[u]=1;
    if(col[u]==x) ans[u]=2,b--;
    else{
        if(a>0) ans[u]=1,a--;
        else ans[u]=3,c--;
    }
    for(int v:adj[u]) if(!mrk[v]) DFS2(v,x);
}

int32_t main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;
    cin>>n>>m;
    cin>>a>>b>>c;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v); adj[v].pb(u);
    }
    for(int i=1;i<=n;i++) if(!mrk[i]) DFS1(i,++cnt,0);
    dp[0][0]=1;
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<=b;j++){
            if(j-num[i][0]>=0 && dp[i-1][j-num[i][0]]){
                dp[i][j]=1;
                par[i][j]=0;
            }
            if(j-num[i][1]>=0 && dp[i-1][j-num[i][1]]){
                dp[i][j]=1;
                par[i][j]=1;
            }
        }
    }
    if(!dp[cnt][b]) return cout<<"NO",0;
    for(int i=cnt;i>0;i--){
        res[i]=par[i][b];
        b-=num[i][par[i][b]];
    }
    fill(mrk,mrk+N,0);
    for(int i=1;i<=n;i++) if(!mrk[i]) DFS2(i,res[comp[i]]);
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++) cout<<ans[i];
    return 0;
}