NOIP模拟赛20161114

幸运串

题意：长度为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 <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const ll MOD=1e9+;

ll n,m;

inline ll powMod(ll a,ll b){

    ll ans=;

    for(;b;b>>=,a=(a*a)%MOD)

        if(b&) 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==) printf("%d",n==?:);

    else if(n==) printf("%d\n",m);

    else printf("%lld",m*(m-)%MOD*powMod(m-,n-)%MOD);

}

最优排名

很明显贪心

先v大到小排序

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

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

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <set>

using namespace std;

const int N=3e5+;

typedef long long ll;

inline ll read(){

    char c=getchar();ll x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';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<ll> s;

int main(){

    freopen("rank11.in","r",stdin);

    freopen("rank11.out","w",stdout);

    n=read();

    for(int i=;i<=n;i++) a[i].id=i,a[i].v=read(),a[i].w=read();

    sort(a+,a++n);

    ll p=,rank;

    for(int i=;i<=n;i++){

        if(a[i].id==) break;

        p++;

        s.insert(a[i].w-a[i].v+);

    }

    rank=p+;//printf("rank %d\n",rank);

    ll v=a[rank].v,ans=rank,tail=rank+;

    while(v&&!s.empty()){

        ll now=*s.begin(); //printf("now %d\n",now);

        s.erase(s.begin());

        if(v-now>=) v-=now,rank--;

        while(v<a[tail].v) {s.insert(a[tail].w-a[tail].v+);tail++;rank++;}

        ans=min(ans,rank);

    }

    printf("%d",ans);

}

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

const int N=3e5+;

typedef long long ll;

inline ll read(){

    char c=getchar();ll x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';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<ll,vector<ll>,greater<ll> > q;

int main(){

    freopen("rank.in","r",stdin);

    freopen("rank.out","w",stdout);

    n=read();

    for(int i=;i<=n;i++) a[i].id=i,a[i].v=read(),a[i].w=read();

    sort(a+,a++n);

    ll p=,rank;

    for(int i=;i<=n;i++){

        if(a[i].id==) break;

        p++;

        q.push(a[i].w-a[i].v+);

    }

    rank=p+;//printf("rank %d\n",rank);

    ll v=a[rank].v,ans=rank,tail=rank+;

    while(v&&!q.empty()){

        ll now=q.top();q.pop();

        if(v-now>=) v-=now,rank--;

        while(v<a[tail].v) {q.push(a[tail].w-a[tail].v+);tail++;rank++;}

        ans=min(ans,rank);

    }

    printf("%d",ans);

}

运输任务

貌似是树链剖分，不会

能骗20到50分吧

巴特西

NOIP模拟赛20161114

最新文章

热门文章