幸运串

题意：长度为n，字符集大小为m的字符串中有多少不同的不含回文的串

n,m<10^9

---

 

我靠这不就是萌数的DP部分吗

有规律

f[2][j][k]=1

f[i][j][k]=sigma{f[i-1][k][z]|z!=j&&z!=k}

答案就是m*(m-1)*(m-2)^(n-2)

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const ll MOD=1e9+7;ll n,m;inline ll powMod(ll a,ll b){    ll ans=1;    for(;b;b>>=1,a=(a*a)%MOD)        if(b&1) ans=(ans*a)%MOD;    return ans;}int main(){    freopen("lucky.in","r",stdin);     freopen("lucky.out","w",stdout);    scanf("%lld%lld",&n,&m);    if(m==1) printf("%d",n==1?1:0);     else if(n==1) printf("%d\n",m);     else printf("%lld",m*(m-1)%MOD*powMod(m-2,n-2)%MOD);}
        
       
      
     

---

---

最优排名

很明显贪心

先v大到小排序

找之前w-v最小的，送她气球，删掉它；送气球之后加入后面又超过自己的

用set超时了，直接用堆就好，只需要删除最大元素

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=3e5+5;typedef long long ll;inline ll read(){    char c=getchar();ll x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n;struct team{    int id;    ll w,v;    bool operator <(const team &r)const{
   return v>r.v;}}a[N];multiset
          
            s;int main(){ freopen("rank11.in","r",stdin); freopen("rank11.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i].id=i,a[i].v=read(),a[i].w=read(); sort(a+1,a+1+n); ll p=0,rank; for(int i=1;i<=n;i++){ if(a[i].id==1) break; p++; s.insert(a[i].w-a[i].v+1); } rank=p+1;//printf("rank %d\n",rank); ll v=a[rank].v,ans=rank,tail=rank+1; while(v&&!s.empty()){ ll now=*s.begin(); //printf("now %d\n",now); s.erase(s.begin()); if(v-now>=0) v-=now,rank--; while(v
          
         
        
       
      
     

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=3e5+5;typedef long long ll;inline ll read(){    char c=getchar();ll x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n;struct team{    int id;    ll w,v;    bool operator <(const team &r)const{
   return v>r.v;}}a[N];priority_queue
          
           
            ,greater
            
              > q;int main(){ freopen("rank.in","r",stdin); freopen("rank.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i].id=i,a[i].v=read(),a[i].w=read(); sort(a+1,a+1+n); ll p=0,rank; for(int i=1;i<=n;i++){ if(a[i].id==1) break; p++; q.push(a[i].w-a[i].v+1); } rank=p+1;//printf("rank %d\n",rank); ll v=a[rank].v,ans=rank,tail=rank+1; while(v&&!q.empty()){ ll now=q.top();q.pop(); if(v-now>=0) v-=now,rank--; while(v
            
           
          
         
        
       
      
     

 

---

---

运输任务

貌似是树链剖分，不会

能骗20到50分吧