Goodbye 2018

• 可能是我太菜考试的时候出不了$E$
• 可能是我太菜考试的时候调不出$F$
• 所以转化为手速场之后手速还上不去.jpg

A

模拟题意...

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){    int y,b,r,ans=1<<30;    scanf("%d%d%d",&y,&b,&r);    ans=min(r-2,min(b-1,y));    printf("%d\n",ans*3+3);}
      
     
    

B

因为一定有，所以就一定是一个位置。

然后就相当于是给你$2\times n$个点，两两匹配的中点在同一个点的方案。

然后就直接横坐标纵坐标求平均数即可.jpg

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define ll long longint n,x,y;ll a,b;int main(){ scanf("%d",&n); for(int i=1;i<=n<<1;i++) { scanf("%d%d",&x,&y); a+=x,b+=y; } printf("%lld %lld\n",a/n,b/n);}
           
          
         
        
       
      
     
    

C

推一下式子就完事了.jpg

可以发现，跳的步数一定是$n$的约数，然后发现构成的节点是等差数列。

然后发现，直接暴力求即可...

最后需要排个序...

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define ll long longll n,ans[1000005];int tot;int main(){ scanf("%lld",&n); for(ll i=1;i*i<=n;i++) { if(n%i==0) { ans[++tot]=(2+n-i)*(n/i)>>1; ans[++tot]=(2+n-(n/i))*i>>1; } } sort(ans+1,ans+tot+1); tot=unique(ans+1,ans+tot+1)-ans-1; for(int i=1;i<=tot;i++)printf("%lld ",ans[i]);puts("");}
           
          
         
        
       
      
     
    

D

比较好玩的数数题.jpg

（可能我的数数题也就是这么菜鸡吧.jpg

OEIS了一发，并没有.jpg

然后我们考虑，答案一定会长成这个样子：$n\times n!-\sum\limits_{i=1}^{n-1}\frac{n!}{i!}$

表达的含义很简单，就是对于两个字典序相近的排列，假设前一个字典序结尾有$K$位是递减的，那么说明，下次变动的时候，会有$K+1$为被改掉了，其他的位没有动。

然后可以发现，其他的$n-K$位都能依旧构成一个满足要求的序列，而剩下的$K+1$位都不能满足...

对于这样的前缀，一共有$\frac{n!}{k!}$个，所以答案就是$n\times n!-\sum\limits_{i=1}^{n-1}\frac{n!}{i!}$

#include
    
     #include
     
      #include
      
       using namespace std;#define N 1000010#define ll long long#define mod 998244353int n;ll f[N],g[N],ans,inv[N];inline ll q_pow(ll x,int n){ll ret=1;for(;n;n>>=1,x=x*x%mod)if(n&1)ret=ret*x%mod;return ret;}int main(){    scanf("%d",&n);    f[0]=1ll;    for(int i=1;i<=n;i++)        f[i]=(f[i-1]*i)%mod,inv[i]=q_pow(f[i],mod-2);    for(int i=1;i<=n;i++)g[i]=(f[n]*inv[n-i])%mod;    (ans+=f[n])%=mod;    for(int i=2;i
      
     
    

证明好难.jpg

E

下次题目中的蓝字一定要点开，然后翻译一下，说不定就有题解...

我们发现，对于答案方案来说，一定是满足连续性的，也就是说$K,K+4$是答案，那么$K+2$也一定是答案.jpg

原因很简单，就是说，可以让前面的某俩人互相匹配上，就不用和最后一个人匹配了...

并且可以发现，对于这样的匹配变动，在找到一个最小的满足答案要求的$a_{n+1}$的时候，就不能再找到一个新的变动了

然后就是如何找到答案...

然后那个蓝字中有这样的一个式子.jpg

对于图，满足：对于任意一个$k$满足$\sum\limits_{i=1}^kd_i \le k\times(k-1)+\sum\limits_{i=k+1}^n\min(d_i,k)$，并且$\sum\limits_{i=1}^nd_i$为偶数...

那么我们就可以维护了.jpg

先二分答案，然后考虑如何验证...

对于一个$d_{n+1}$，如果它在排序后位于$t$这个位置，那么如果最先不满足条件的位置$K< t$，说明这个$d_i$太小了...

如果最先不满足跳脚的位置$K\ge t$，那么说明这个$d_i$太大了。

所以根据这个就可以找到最大值和最小值了...

然后就完事了...

至于怎么$O(n)$验证：插入排序...

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 500005#define ll long longint a[N],n,d[N],pos[N];ll s[N];int check(int x){ int flg=0;d[n+1]=-1; for(int i=1,j=0;i<=n;i++) { if(flg||a[i]>=x)d[++j]=a[i]; else flg=++j,d[j]=x,i--; } if(!flg)d[n+1]=x,flg=n+1; s[0]=0; for(int i=1;i<=n+1;i++)s[i]=d[i]+s[i-1];//,printf("%d ",d[i]);;puts(""); for(int i=n+1,now=1;i;i--) while(now<=n+1&&d[i]>now)pos[now++]=i; for(int k=1;k<=n+1;k++) { ll tmp=s[k]-(ll)k*(k-1); tmp-=(ll)k*max(pos[k]-k,0);tmp-=s[n+1]-s[pos[k]]; // printf("%d %d %d %lld\n",x,k,pos[k],tmp); if(tmp>0)return k
            
             >1)+1; while(l
             
              >1; if(check((m<<1)|flg)!=-1)r=m; else l=m+1; } if(check((l<<1)|flg))return puts("-1"),0; int ans=l;r=(n>>1)+1; while(l
              
               >1; // printf("%d %d %d %d\n",l,m,r,check((m<<1)|flg)); if(!check((m<<1)|flg))l=m+1; else r=m; }l--; ans=(ans<<1)|flg,l=(l<<1)|flg; for(int i=ans;i<=l;i+=2)printf("%d ",i);}
              
             
            
           
          
         
        
       
      
     
    

F

通过分析性质可以发现，能在水里多游绝不在草上多走...能在草上走，绝不在水里多游...能在草上飞，就不在水里飞...

然后就变成了增加两个位置的长度了...

分别是：第一块和第一块水...

然后就模拟就好了...

#include
    
     #include
     
      #include
      
       using namespace std;#define N 100005#define ll long longint n,flg;ll a[N],now,ans,res,tmp;char s[N];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);scanf("%s",s+1);    flg=1;    for(int i=1;i<=n;i++)    {        if(s[i]=='W'&&s[flg]=='G')flg=i;        if(s[i]=='L')now-=a[i];        else now+=a[i];        if(now<=0)a[flg]-=now,now=0;    }    now=0;    for(int i=1;i<=n;i++)    {        ll tmp=a[i];        if(s[i]=='W')now+=tmp,ans+=2*tmp;        if(s[i]=='G')        {            ll tnp=min(tmp,now);            now-=tnp,ans+=2*tnp;            ans+=3*(tmp-tnp);        }        if(s[i]=='L')        {            ll tnp=min(tmp,now);            now-=tnp,tmp-=tnp,ans+=2*tnp;            ans+=3*tmp;        }    }    printf("%lld\n",ans);}//sdasdasdas
      
     
    

剩下的还不会，回头补题吧QaQ