\(A\)

直接按时间排序之后贪心就可以了

const int N=1e5+5;int a[N],q[N],c,k,h,t,n,res;inline int min(R int x,R int y){return x

\(B\)

发现吃的时候从小到大吃肯定是最优的，那么从小到大排个序，找到右边开始的第一个\(sum_{i-1}\times 2<a_i\)的位置即可

typedef long long ll;const int N=1e5+5;ll sum[N];int a[N],n;int main(){    scanf("%d",&n);    fp(i,1,n)scanf("%d",&a[i]);    sort(a+1,a+1+n);    fp(i,1,n)sum[i]=sum[i-1]+a[i];    fd(i,n,1)if(a[i]>(sum[i-1]<<1))return printf("%d\n",n-i+1),0;    return 233;}

\(C\)

把\(O(n)\)的图和\(O(n^2)\)的图分别记为\(S\)和\(T\)

首先把\(S\)中只有一个点的连通块特判掉，因为只要\(u\)这个联通块中只有一个点，那么\(T\)中任何一个包含\(u\)的点绝对不会和别的任何点相连

现在假设每一个连通块中有至少两个点，那么\(T\)中的一个点\((u,v)\)（\(u,v\)是否在同一连通块中都可以），绝对和所有形如\((u,w)\)的点在同一连通块中，其中\(v,w\)之间存在一条路径使其距离为偶数。这个很显然，因为只要\(v\)在走这条路径的过程中，\(u\)只要和一个与它相邻的点反复横跳就可以了。更进一步我们发现当\(v\)所在的连通块中存在奇环时\(w\)可以为整个连通块，否则只能为其中一部分点

那么对于\(S\)中每一个连通块，我们\(dfs\)一遍判断是否有奇环，那么对于两个不同的连通块，贡献分别为奇奇和奇偶\(1\)，偶偶\(2\)（可以画个图自己理解一下），连通块相同类似讨论就行了

//quming#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;typedef long long ll;const int N=5e5+5;struct eg{int v,nx;}e[N<<1];int head[N],tot;inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}int dis[N],deg[N],cnt[3],n,m,flag;ll res;void dfs(int u,int d){    dis[u]=d;    go(u)if(dis[v]==-1)dfs(v,d^1);        else if(dis[v]!=dis[u]^1)flag=1;}int main(){    scanf("%d%d",&n,&m);    for(R int i=1,u,v;i<=m;++i){        scanf("%d%d",&u,&v);        add(u,v),add(v,u),++deg[u],++deg[v];    }    memset(dis,-1,sizeof(dis));    fp(i,1,n)if(!deg[i])++cnt[2],++res;        else if(dis[i]==-1)flag=0,dfs(i,0),++cnt[flag],res+=2-flag;    res+=1ll*cnt[2]*(n-cnt[2])<<1;    res+=1ll*cnt[2]*(cnt[2]-1);    res+=1ll*cnt[0]*(cnt[0]-1)*2+1ll*cnt[0]*cnt[1]*2+1ll*cnt[1]*(cnt[1]-1);    printf("%lld\n",res);    return 0;}
        
       
      
     
    

\(D\)

方便起见把\(A\)定义为\(1\)，\(B\)定义为\(0\)

首先自己画个图手玩一下，发现一次操作之后，如果\(a_1=1\)，那么变成\(a_1=0\)，否则导致\(a_i=a_{i+1}^1\)，且\(a_n=1\)

那么我们可以有一个\(O(k)\)的做法，每一次判断开头元素，如果是\(1\)直接改为\(0\)，否则就把数列整体左移一位并区间取反以及在后面加数，区间取反记个标记就可以了，用一个队列去模拟就行

然后这样显然是不行的，所以如果这个队列的开头元素的位置大于\(n\)了我们就退出

手玩一下之后发现，如果\(n\)是偶数，那么整个序列必定形如\(01010101....0101\)，且进行任何多次操作之后仍然长这样

再手玩一下之后发现，如果\(n\)是奇数，那么整个序列必定形如\(1010101010...101\)，第一个位置根据操作次数的奇偶而定，而且操作两次之后会变回原样

那么讨论一下就可以了

//quming#include
    
     #define R register#define pb push_back#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=2e6+5;char s[N];int n,k;inline void print(R char *s){s[n]='\0',printf("%s\n",s);}void solve(R int k){    R int i=1;    while(i<=n&&k--){        R int op=(i<=n?((i-1)&1):((n-1)&1));        if((s[i]=='A')^op){s[i]=(s[i]=='A'?'B':'A');continue;}        s[i+n]='A',++i;    }    if(i<=n){        R int op=(i-1)&1;        fp(k,i,i+n-2){            if(op)s[k]=(s[k]=='A'?'B':'A');            if(k+1>n)op^=1;        }        s[i+n-1]='A';        return print(s+i);    }    if(n&1^1){        fp(i,1,n)s[i]=((i&1)?'B':'A');        print(s+1);        return;    }    R int op=(n-1)&1;    if(op)--k;    s[n]=(k&1?'B':'A');    fp(i,1,n-1)s[i]=((i&1)?'A':'B');    reverse(s+1,s+1+n);    print(s+1);}int main(){    scanf("%d%d%s",&n,&k,s+1);    solve(k);    return 0;}
        
       
      
     
    

\(E\)

为啥全世界都是按分解成全\(1\)数来做的……只有我是贪心的么……

事先声明我并不会证明这个贪心的正确性

贪心起见，我们每一次都选择把原数减去一个尽量大的数

假设这个数按数位可以写成\(a_1a_2a_3...a_n\)，那么我们找到最大的\(p\)，满足对于\(i<p\)都有\(a_i\leq a_{i+1}\)且\(a_{p-1}<a_p\)，那么我们选择减去的数字就是\(a_1a_2...a_{p-1}(a_{p}-1)9...9\)，也就是说前面那些加上后面若干个⑨。容易发现减去的数字必然合法且一定是最大的

然而我们显然不能高精减否则复杂度会炸掉……所以减去这个数字等价于把前\(p\)个数删掉并在后面加上\(1\)，根据\(01\)计算器的原理如果加了\(n\)次\(1\)，总复杂度是\(O(n)\)的，所以这一部分没问题

那么现在唯一的问题就是我们该如何找到这个\(p\)了，首先肯定不能暴力因为数据里有几个点专门卡掉了。我们发现合法的\(p\)必定是一段极长的连续相同数字的开头，那么我们用一个队列存储所有的合法的开头，每一次比较队头和队头的下一个元素，如果下一个元素更优那么直接把队头弹掉就好了，否则就找到了。这样的话每个数加入一次删除一次，或者因为\(+1\)的缘故而加入删除的话也是\(O(n)\)，于是这一部分也是\(O(n)\)

综上总复杂度为\(O(n)\)

//quming#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=1e6+5;char s[N];int a[N],q[N],h,t,n,res;inline int min(R int x,R int y){return x
         
          a[q[h]])++h; if(h>t)break; fd(i,n,q[h]+1){ if(a[i]==9){a[i]=0;continue;} ++a[i]; while(h<=t&&q[t]>=i)--t; if(i==q[h]+1||a[i-1]!=a[i])q[++t]=i; if(i+1<=n)q[++t]=i+1; break; } ++h; if(q[h]!=q[h-1]+1)++q[h-1],--h; while(h<=t&&!a[q[h]])++h; if(h>t)break; } printf("%d\n",res); return 0;}
         
        
       
      
     
    

\(F\)

题目太神仙了我不看题解连题目都看不懂……

所以一起去膜拜吧

//quming#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=5e5+5;typedef long long ll;struct node;typedef node* ptr;struct node{    ptr lc,rc;int c;    inline void pd(){if(c)lc->c=c,rc->c=c,c=0;}}e[N<<2],*pp=e,*rt;ll s[N],dp[N],res;int a[N],b[N],l[N],r[N],st[N];int n,P,m,top;inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}void build(ptr &p,int l,int r){    p=++pp;if(l==r)return;    int mid=(l+r)>>1;    build(p->lc,l,mid),build(p->rc,mid+1,r);}int query(ptr p,int l,int r,int x){    if(p->c||l==r)return p->c;    int mid=(l+r)>>1;    return x<=mid?query(p->lc,l,mid,x):query(p->rc,mid+1,r,x);}void update(ptr p,int l,int r,int ql,int qr,int v){    if(ql>qr)return;    if(ql<=l&&qr>=r)return p->c=v,void();    int mid=(l+r)>>1;p->pd();    if(ql<=mid)update(p->lc,l,mid,ql,qr,v);    if(qr>mid)update(p->rc,mid+1,r,ql,qr,v);}ll ask(R int x){    R int p=query(rt,1,top,x);    if(!p)return 0;    return dp[p]+dec(st[l[p]],st[x]);}int main(){//  freopen("testdata.in","r",stdin);    scanf("%d%d",&n,&P);    fp(i,1,n){        scanf("%d%d",&a[i],&b[i]),s[i]=s[i-1]+a[i];        if(b[i]==1&&(a[i]<<1)>P)return puts("-1"),0;    }    fd(i,n,1){        if(b[i]==1)l[i]=mul(s[i-1]%P,P-2),r[i]=mul(s[i]%P,P-2);            else l[i]=0,r[i]=P-1;        st[++top]=l[i],st[++top]=r[i];    }    sort(st+1,st+1+top),top=unique(st+1,st+1+top)-st-1;    build(rt,1,top);    fd(i,n,1){        l[i]=lower_bound(st+1,st+1+top,l[i])-st;        r[i]=lower_bound(st+1,st+1+top,r[i])-st;        dp[i]=ask(l[i]);        if(l[i]>r[i])update(rt,1,top,r[i]+1,l[i]-1,i);        else update(rt,1,top,1,l[i]-1,i),update(rt,1,top,r[i]+1,top,i);    }    res=dp[1];    fp(i,1,top)cmin(res,ask(i));    printf("%lld\n",res+(s[n]<<1));    return 0;}