题面

\(1143A\)

咕咕

n=read();fp(i,1,n)a[i]=read(),++cnt[a[i]];fp(i,1,n)if(++c[a[i]]==cnt[a[i]])return printf("%d\n",i),0;

\(1143B\)

显然最终的答案肯定是后面一堆\(9\)加上前面的数字，模拟一下就行了

//minamoto#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
       
        =now?res:res-1)*i*10+now));    }    printf("%d\n",mx);    return 0;}
       
      
     
    

\(1143C\)

显然合法的点永远合法，不合法的点永远不合法，直接把所有合法的点找出来\(sort\)一下就行了

//minamoto#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)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R int x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]=' ';}const int N=1e5+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 sz[N],val[N],vva[N],st[N];int n,rt,top,x;void dfs(int u){    sz[u]=1,vva[u]=val[u];    go(u)dfs(v),++sz[u],vva[u]+=val[v];    if(sz[u]==vva[u])st[++top]=u;}int main(){//  freopen("testdata.in","r",stdin);    n=read();    fp(i,1,n){        x=read(),val[i]=read();        if(~x)add(x,i);else rt=i;    }    dfs(rt);    sort(st+1,st+1+top);    if(!top)return puts("-1"),0;    else fp(i,1,top)print(st[i]);    return Ot(),0;}
     
    

\(1142A\)

首先如果环长为\(p\)，跨一步距离为\(a\)，那么\({p\over \gcd(p,a)}\)步之后可以回到原点

所以枚举一下开头和第一次跳到的地方就行了，开头只有两个是有用的

//minamoto#include
    
     #define R register#define ll long long#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;int n,k,a,b,s,t;ll mx,mn,p,res;ll calc(R ll x,R ll y){R ll k=(y-x+p)%p;return p/__gcd(p,k);}int main(){//  freopen("testdata.in","r",stdin);    scanf("%d%d%d%d",&n,&k,&a,&b),mx=0,mn=1e18,p=1ll*n*k;    s=a+1;    for(t=b+1;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);    for(t=k+1-b;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);    s=k+1-a;    for(t=b+1;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);    for(t=k+1-b;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);    printf("%I64d %I64d\n",mn,mx);    return 0;}
        
       
      
     
    

\(1142B\)

因为是这个排列的循环位移，所以每一个数前面能接哪个数是已经确定的了，记为\(las\)

对于\(a\)中的每一个数字，显然是接在前面离它最近的值为\(las\)的数后面最优，对于每一个数都预处理出它应该接在谁后面，记为\(to[i]\)

显然，对于\(i\)来说，它跳\(n-1\)次\(to[i]\)之后到达的点是一个合法的点，且是最右边的合法的点。我们可以倍增预处理出对于每一个点\(i\)最右边的合法的点，记为\(pos_i\)

那么就是有一堆区间\([pos_i,i]\)，以及一对询问\([l,r]\)，每次问你有多少区间被询问区间完全包含

我们离线，把询问按右端点排序，每次对于一个点\(i\)，把它的左端点，也就是\(pos_i\)加入一个树状数组，那么对于所有右端点为\(i\)的询问来说，显然只有现在在树状数组中的，且位置在\([l,r]\)之间的左端点是有用的，查询一下就行了

//minamoto#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)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int K=-1,Z=0;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}const int N=2e5+5;struct node{    int l,r,id;    inline bool operator <(const node &b)const{return r
      
       >j&1)x=to[x][j];        p[i]=x;    }}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read(),Q=read();    fp(i,1,n)a[i]=read(),las[a[i]]=a[i-1];    las[a[1]]=a[n];    fp(i,1,m)b[i]=read(),to[i][0]=pos[las[b[i]]],pos[b[i]]=i;    init();    fp(i,1,Q)q[i].l=read(),q[i].r=read(),q[i].id=i;    sort(q+1,q+1+Q);    for(R int i=1,j=1;i<=m;++i){        if(p[i])upd(p[i]);        while(j<=Q&&q[j].r==i)ans[q[j].id]=query(q[j].l,i),++j;    }    fp(i,1,Q)sr[++K]=(ans[i]?'1':'0');sr[++K]='\n';    return Ot(),0;}
      
     
    

\(1142C\)

我sb了这都没想到……

假设有一个点满足\(y>x^2+bx+c\)，那么就是有\(y-x^2>bx+c\)

所以我们把每个点的坐标转化为\((x,y-x^2)\)，那么就可以转化为不在直线的上方，直接求个上凸包，计算一下凸包上的边数就可以了

//minamoto#include
    
     #define R register#define ll long long#define inf 0x3f3f3f3f#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)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=1e5+5;struct node{    ll x,y;    inline node(){}    inline node(R ll xx,R ll yy):x(xx),y(yy){}    inline node operator +(const node &b)const{return node(x+b.x,y+b.y);}    inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}    inline ll operator *(const node &b)const{return x*b.y-y*b.x;}    inline bool operator <(const node &b)const{return x==b.x?y>b.y:x
      
       1&&(st[top]-st[top-1])*(p[i]-st[top-1])>=0)--top;        st[++top]=p[i];    }    printf("%d\n",top-1);}int main(){//  freopen("testdata.in","r",stdin);    n=read();    for(R int i=1,x,y;i<=n;++i)x=read(),y=read(),p[i]=node(x,y-1ll*x*x);    solve();    return 0;}
      
     
    

\(1142D\)

话说巨巨们写完题就不能顺手写个题解么……对着\(yyb\)巨巨那长达\(20\)行的代码盯了一个下午……

首先题目里说的太麻烦了，我们把它用代码的形式写出来，大概是这样的

fp(i,1,9)q[++t]=i;while(true){    int u=q[h];    fp(j,0,h%11-1)q[++t]=q[h]*10+j;    ++h;}

那么我们发现这个数列显然是递增的

我们先来思考一个问题，对于数列中的第\(i\)个数，往它后面怼一个\(c\)，那么这个新的数在数列中的标号是多少呢？

因为这个数列是递增的，那么显然我们只需要计算出有多少数比它小就可以了

先给出柿子，\(i\)后面怼一个\(c\)，新的数的标号为

\[9+\sum_{k=1}^{i-1}k\%11+c+1\]

\(9\)代表初始的\(9\)个数，然后\(1\)到\(i-1\)中每个数后面怼一个数位显然都会比新数小，\(c+1\)应该不用解释了

然而这柿子看着就很麻烦……我们发现后面可以怼的数字只与标号对\(11\)取模的值有关，我们尝试把整个柿子都放到\(\bmod 11\)的意义下，这样就能把中间的\(k\%11\)去掉了

\[9+\sum_{k=1}^{i-1}k+c+1\bmod 11\]

\[9+{i(i-1)\over 2}+c+1\bmod 11\]

如此这般之后，我们发现数字的标号，其实只需要维护\(\bmod 11\)意义下的值就可以了

我们设\(f_{i,j}\)表示末尾数位为\(s[i]\)，标号在\(\bmod 11\)意义下为\(j\)，且能匹配上以\(i\)为结尾的子串的数的个数

我们记上面那个值为\(nxt(i,j)\)，就是标号为\(i\)的后面怼个\(j\)的数的标号，那么转移就有

\[f_{i,nxt(j,s[i])}+=f_{i-1,j}\]

记得这里要满足\(j>s[i]\)

顺便注意如果\(s[i]>0\)的话单独一个数字也是可以匹配的

//minamoto#include
    
     #define R register#define ll long long#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)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'9'||ch<'0'));    for(s[++len]=ch;(ch=getc())>='0'&&ch<='9';s[++len]=ch);    return s[len+1]='\0',len;}const int N=1e5+5;char s[N];int f[N][15],n;ll res;inline int nxt(R int x,R int c){return ((x*(x-1)>>1)+c+10)%11;}int main(){//  freopen("testdata.in","r",stdin);    n=read(s);    fp(i,1,n){        fp(j,s[i]-'0'+1,10)f[i][nxt(j,s[i]-'0')]+=f[i-1][j];        if(s[i]>'0')++f[i][s[i]-'0'];        fp(j,0,10)res+=f[i][j];    }    printf("%I64d\n",res);    return 0;}
     
    

\(1142E\)

好迷……

我们先考虑完全没有粉色边的情况

我们维护一个\(top\)集合，集合里是所有可能成为答案的点，并且维护一个\(gg\)集合，里面是所有不可能成为答案的点（严格来说还是有可能成为答案的，只不过我们不需要了）

然后我们每次从\(top\)集合里取出两个点，询问它们之间的边的方向，如果边形如\((u,v)\)，就把\(v\)从\(top\)集合里取出，加入\(gg\)集合

那么最后\(top\)集合里只剩一个点的时候这个点显然可以成为答案

然而粉色边的参战导致事情变得辣手了起来

大体思路还是和之前一样的，只不过我们一开始并不能把所有点都加入\(top\)集合里不然跟一开始的情况有什么区别……

我们先把所有的粉边构成的强连通分量搞出来，然后每个强连通分量里取出一个点加入\(top\)集合

然后照例每次从\(top\)集合里取出两个点，假设边的方向为\((u,v)\)，那么照例把\(v\)删掉就万事大吉……

等会儿\((u,v)\)是绿色的吧？\(v\)到它所在强连通分量中的点的边是粉色的吧？这显然颜色不同啊？

也就是说，只有\(v\)是需要加入\(gg\)集合的，而\(v\)所在的强连通分量中其它的点可能还是需要加入\(top\)集合的

那么我们把每个强连通分量删掉一些边使之成为一个\(DAG\)，每次把度数为\(0\)的点加入\(top\)集合，然后询问完之后把\(v\)以及\(v\)连出去的所有边都删掉，再看看有没有度数为\(0\)的点就是了，需不需要加入\(top\)就是了。直到\(top\)集合只剩下一个元素为止

正确性？显然所有\(gg\)集合里的元素都能通过绿色边走到，既不在\(top\)也不在\(gg\)里的元素都可以通过粉色边到达，那么正确性就没问题了

//minamoto#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 cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;int read(){    R int res,f=1;R char ch;    while((ch=getchar())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getchar())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}inline int get(){R char ch;while((ch=getchar())>'1'||ch<'0');return ch-'0';}const int N=1e5+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;}inline bool query(R int u,R int v){printf("? %d %d\n",u,v),fflush(stdout);return read();}int vis[N],ins[N],deg[N];vector
       
        to[N],now;int n,m;void tarjan(int u){    vis[u]=ins[u]=1;    go(u){        if(!ins[v])to[u].push_back(v),++deg[v];        if(!vis[v])tarjan(v);    }    ins[u]=0;}int main(){    n=read(),m=read();    for(R int i=1,u,v;i<=m;++i)u=read(),v=read(),add(u,v);    fp(i,1,n)if(!vis[i])tarjan(i);    fp(i,1,n)if(!deg[i])now.push_back(i);    while(now.size()>1){        int u=now.back();now.pop_back();        int v=now.back();now.pop_back();        if(!query(u,v))swap(u,v);now.push_back(u);        fp(i,0,to[v].size()-1)if(!--deg[to[v][i]])now.push_back(to[v][i]);    }    printf("! %d\n",now.front());    return 0;}