A  根据题意找出递推式 发现上一项的ans作为下一项的幂次 所以欧拉降幂 (写错递归 背锅背锅

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
        
       
      
     

 B DP

队友博客

C 数位dp

队友博客

D 构造 发现偶数项转移规律

#include
     
      using namespace std;int a[205][205];int n;void ycl(){    a[1][1] = 0;a[1][2] = -1;    a[2][1] = 1;a[2][2] = 1;   for(int nn = 4;nn<=200;nn+=2)   {    for(int j = 1;j<=nn;j++) a[nn-1][j] = a[j][nn] = -1,a[nn][j] = a[j][nn-1] = 1;    a[nn-1][nn-1] = 0;   }   return ;}int main(){    ycl();    int _;cin>>_;   while(_--)   {      cin>>n;    if(n%2 == 1) cout<<"impossible"<
     

 E 题意题  ....看懂题以后 发现是扫描线线段树板子题  不想写离散化的辣鸡写动态开点调了一天...然后是没有取膜也没开ll 做法还是很明显:动态开点+扫描线线段树

#include 
     
      using namespace std;#define ll long longconst int MAXN=1e5+10;const ll mod=1e9+7;ll read(){    ll x=0,f=1;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return f*x;}ll ksm(ll a,ll b,ll c){    ll ans=1;    while(b){    if(b&1)ans=ans*a%c;    a=a*a%c;b=b>>1;    }    return ans;}typedef struct node{    int l,r;ll sum,flag;}node;node d[MAXN*25];int cnt;ll ans=0;void newnode(int &x,int len){x=++cnt;;d[x].l=d[x].r=0;d[x].sum=len;d[x].flag=1;}void up(int x,int l,int r){    int mid=(l+r)>>1;    if(!d[x].l)d[x].sum=mid-l+1;else d[x].sum=d[d[x].l].sum*d[d[x].l].flag%mod;    if(!d[x].r)d[x].sum+=r-mid;else d[x].sum+=d[d[x].r].sum*d[d[x].r].flag%mod;    d[x].sum%=mod;}ll tag,tag1,vul1;void update(int &x,int l,int r,int ql,int qr,ll vul){    if(!x)newnode(x,r-l+1);    if(ql<=l&&r<=qr){    d[x].flag=d[x].flag*tag1%mod;    vul1=vul*d[x].flag%mod;    ans=(ans+tag*(r-l+1)%mod)%mod;    ans=(ans+((-1ll*((vul1*(tag*(d[x].sum%mod)%mod))%mod))%mod+mod)%mod)%mod;    return ; }    int mid=(l+r)>>1;    if(ql<=mid)update(d[x].l,l,mid,ql,qr,vul*d[x].flag%mod);    if(qr>mid) update(d[x].r,mid+1,r,ql,qr,vul*d[x].flag%mod);    up(x,l,r);}int n;typedef struct Node{    ll x,y;ll vul;    friend bool operator<(Node aa,Node bb){    if(aa.y==bb.y)return aa.x>bb.x;    return aa.y>bb.y;    }}Node;Node que[MAXN];vector
      
       vec;void slove(){    n=read();ll t1,t2;ll Xmax=-1,Ymax=-1;vec.clear();cnt=0;ans=0;    for(int i=1;i<=n;i++)que[i].x=read(),que[i].y=read(),vec.push_back(que[i].y),t1=read(),t2=read(),Xmax=max(Xmax,que[i].x),Ymax=max(Ymax,que[i].y),que[i].vul=1ll*(t2-t1)*ksm(t2,mod-2,mod)%mod;    sort(que+1,que+n+1);ll last=Xmax;tag=0;vec.push_back(0);    sort(vec.begin(),vec.end());    int sz=unique(vec.begin(),vec.end())-vec.begin();    t1=sz-1;t2=sz-2;    que[n+1].x=que[n+1].y=0;    Ymax++;    int tot=1;tag1=1ll;int rt=0;    while(tot<=n){    tag=vec[t1]-vec[t2];    if(Xmax!=que[tot].x)update(rt,1,last,que[tot].x+1,Xmax,1ll);//cout<
       
        <<"====="<
        
         <<" "<
         
          <
          
           =1){update(rt,1,last,1,Xmax,1ll);Xmax=0;} if(que[tot+1].y!=que[tot].y&&!Xmax){Xmax=last;tag1=1ll;t1=t2;t2--;} tot++; } printf("%lld\n",ans);}int main(){ int _;_=read(); while(_--){ slove(); } return 0;}
          
         
        
       
      
     

 F 签到

#include
     
      using namespace std;char maps[2005][2005];int n,m;int main(){    ios::sync_with_stdio(false);    int T;    cin>>T;    while(T--)    {    cin>>n>>m;    for(int i = 1;i<=n;i++)    {        for(int j = 1;j<=m;j++) cin>>maps[i][j];    }    int heng= 0,shu = 0;    for(int i = 1,j = n;i
     

 G 贪心 二分前缀和即可

#include 
     
      const int MAXN=1e5+10;#define ll long longusing namespace std;int d[MAXN],b[MAXN];vector
      
       vec;ll num[MAXN];int a[MAXN];int main(){    int _;scanf("%d",&_);    while(_--){        int n,m;scanf("%d%d",&n,&m);        int t;        for(int i=1;i<=n;i++)scanf("%d",&a[i]),vec.push_back(a[i]);        sort(vec.begin(),vec.end());        int sz=unique(vec.begin(),vec.end())-vec.begin();        for(int i=1;i<=n;i++)a[i]=lower_bound(vec.begin(),vec.begin()+sz,a[i])-vec.begin()+1,d[a[i]]++;        for(int i=1;i<=sz;i++)b[i]=d[i];        sort(d+1,d+sz+1);        bool flag=0;        for(int i=1;i<=sz;i++)num[i]=num[i-1]+d[i];        for(int i=sz-1;i>=0;i--){            int t=b[i+1];            int pos=lower_bound(d+1,d+sz+1,t)-d;            ll num1=num[sz]-num[pos-1]-t;            ll t1=num1-1ll*(t-1)*(sz-pos);            if(t1<=m){flag=1;printf("%d\n",vec[i]);break;}        }        if(!flag)puts("-1");        vec.clear();memset(num,0,sizeof(num));memset(d,0,sizeof(d));    }}
      
     

 J

一个比较神奇的题 首先明白每个不在对应位置的vul 他将收到一段区间的控制(具体是什么区间 自行理解) 如果这段区间最小值是-1 则是不存在的序列 然后想办法和这区间的点建图 但是明显 这个图建图是n^2的 考虑到分块的思想 结合线段树中的分块 我们按照线段树建树优化建图  通过拓扑解决问题(有环 则这个序列不成立)

#include 
     
      #define ll long longconst int MAXN=2e5+10;const int inf=1e9+7;using namespace std;int read(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return x*f;}int a[MAXN];typedef struct node{    int id,vul;    friend bool operator<(node aa,node bb){    return aa.vul>bb.vul;    }}node;priority_queue
      
       que;int dp[MAXN][21];int n;int ma[MAXN];int key[MAXN<<2];vector
       
        vec[MAXN<<2];int pos[MAXN];int du[MAXN<<2];void built(int rt,int l,int r){    key[rt]=-1;du[rt]=0;    if(l==r){pos[l]=rt;key[rt]=a[l];return ;}    vec[rt<<1].clear();vec[rt<<1|1].clear();    vec[rt<<1].push_back(rt);    vec[rt<<1|1].push_back(rt);    du[rt]+=2;    int mid=(l+r)>>1;    built(rt<<1,l,mid);    built(rt<<1|1,mid+1,r);}void update(int rt,int l,int r,int ql,int qr,int vis){    if(ql<=l&&r<=qr){vec[rt].push_back(vis);du[vis]++;return ;}    int mid=(l+r)>>1;    if(ql<=mid)update(rt<<1,l,mid,ql,qr,vis);    if(qr>mid)update(rt<<1|1,mid+1,r,ql,qr,vis);}void st(){    for(int i=1;i<=n;i++)dp[i][0]=a[i];    for(int j=1;(1<<(j-1))<=n;j++){    for(int i=1;i+(1<
        
         <=n+1;i++){        dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);    }    }}int rmq(int l,int r){    if(l>r)return inf;    int k=ma[r-l+1];int k1=(1<
         

ans;void bfs(){ for(int i=1;i<=n;i++){ if(!du[pos[i]]&&a[i]!=-1)que.push((node){pos[i],a[i]}); } if(que.empty())return ; while(!que.empty()){ node t=que.top();que.pop(); if(t.vul!=-1)ans.push_back(t.vul); for(int i=0;i

t1){ int t2=rmq(t1,i-1); if(t2==-1){flag=1;break;} update(1,1,n,t1,i-1,pos[i]); } else{ int t2=min(rmq(t1,n),rmq(1,i-1)); if(t2==-1){flag=1;break;} update(1,1,n,t1,n,pos[i]); if(i!=1)update(1,1,n,1,i-1,pos[i]); } } if(!cnt){puts("");continue;} if(flag){puts("-1");continue;} bfs(); if(ans.size()