1.足球比赛

推出了式子，不会组合数线性求法

写了个n^2dp 炸了

有点痛

#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}
const int maxn=1e7+5,mod=1e9+7;
int inv[maxn];
inline int pow(int a,int x)
{
    int ret=1;
    while(x) 
    {
        if(x&1)ret=1ll*ret*a%mod;
        x>>=1;
        a=1ll*a*a%mod;
    }

    return ret;
} 


int main()
{

    int n,pa,pb,qa,qb,invb;
//    freopen("in.txt","r",stdin);
    rd(n);
    rd(pa),rd(pb),rd(qa),rd(qb);
    if(pa==pb)
    {
        ll x=pow(qa,n);
        ll y=pow(qb,n);
        invb=pow(qb,(int)(1ll*n*(mod-2)%(mod-1)));
        printf("%lld",1ll*invb*(y-x+mod)%mod);
    }
    else if(!qa)
    {
        ll x=pow(pb-pa,n);
        ll y=pow(pb,n);
        invb=pow(pb,(int)(1ll*n*(mod-2)%(mod-1)));
        printf("%lld",1ll*(y-x+mod)%mod*invb%mod);
    }
    else if(!pa||qa==qb)
    {
        printf("0");
    }
    else 
    {
        inv[1]=inv[0]=1;
        for(register int i=2;i<=n;++i)
            inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        invb=pow((int)(1ll*pb*qb%mod),(int)(1ll*n*(mod-2)%(mod-1)));
        int P=pow(pb-pa,mod-2),Q=pow(qb-qa,mod-2);
        
        int lastq=pow(qb-qa,n),lastp=1ll*pa*pow(pb-pa,n-1)%mod;
        int sum=lastq,C=n,ans=(ans+1ll*sum*C%mod*lastp%mod)%mod;
        for(register int i=2;i<=n;++i)
        {
            lastp=1ll*lastp*pa%mod*P%mod;
            lastq=1ll*lastq*qa%mod*Q%mod;
            sum=(sum+1ll*lastq*C)%mod;
            C=1ll*C*(n-i+1)%mod*inv[i]%mod;
            ans=(ans+1ll*sum*C%mod*lastp)%mod;
        }
    
        printf("%d",1ll*ans*invb%mod);
    } 
    return 0;
}

2. 文明

虽然明知道是树剖

还是很暴力地用十分钟写了个Lca倍增

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

const int maxn=5e5+5;
int n,m,k=1,tot,son[maxn],top[maxn],rev[maxn],fa[maxn];
int hd[maxn],deep[maxn],siz[maxn],seg[maxn],he[maxn];
struct node{
    int to,nt;
}e[maxn<<1];

inline void add(int x,int y)
{
    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;
    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;
}

inline void dfs(int x)
{
    deep[x]=deep[fa[x]]+(siz[x]=1);
    for(int i=hd[x];i;i=e[i].nt)
    {
        int v=e[i].to;
        if(v==fa[x])continue;
        fa[v]=x;
        dfs(v);
        siz[x]+=siz[v];
        if(siz[v]>siz[son[x]])
        son[x]=v;
    }
}

inline void dfs2(int x,int ftop)
{
    top[x]=ftop;
    seg[x]=++tot;
    rev[tot]=x;
    if(son[x])
    {
        dfs2(son[x],ftop);
        for(int i=hd[x];i;i=e[i].nt)
        {
            int v=e[i].to;
            if(!top[v])
            dfs2(v,v);
        }
    }
}

int sum[maxn<<2],lazy[maxn<<2];

#define ls rt<<1
#define rs rt<<1|1
inline void pushup(int rt)
{
    sum[rt]=sum[ls]+sum[rs];
}

inline void pushdown(int rt,int l,int r,int mid)
{
    lazy[ls]=lazy[rs]=lazy[rt];
    if(lazy[rt]==1)
    sum[ls]=mid-l+1,sum[rs]=r-mid;
    else sum[ls]=sum[rs]=0;
    lazy[rt]=0;
}

inline void build(int rt,int l,int r)
{
    if(l==r)
    {
        sum[rt]=1;
        re ;
    }
    
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(rt);
}

inline void modify(int rt,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        sum[rt]=0;
        lazy[rt]=2;
        re ;
    }
    int mid=(l+r)>>1;
    if(lazy[rt])pushdown(rt,l,r,mid);
    if(x<=mid)modify(ls,l,mid,x,y);
    if(y>mid)modify(rs,mid+1,r,x,y);
    pushup(rt);
}

inline int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])x^=y^=x^=y;
        x=fa[top[x]];
    }
    re deep[x]<deep[y]?x:y;
}

inline int jump(int x,int dis)
{
    while(dis&&dis>=deep[x]-deep[fa[top[x]]])
    {
        dis-=(deep[x]-deep[fa[top[x]]]);
        x=fa[top[x]];
    }
    re rev[seg[x]-dis];
}

int main()
{
    int x,y,rt,k;
    rd(n),rd(m);
    inc(i,2,n)
    {
        rd(x),rd(y);
        add(x,y);
    }
    
    fa[1]=1;
    dfs(1);
    dfs2(1,1);
    build(1,1,n);
    inc(i,1,m)
    {
        lazy[1]=1;
        sum[1]=n;
        rd(k);
        rd(rt);
        inc(j,1,k-1)
        {
            rd(x);
            int lca=LCA(x,rt);
            int left=deep[rt]-deep[lca],right=deep[x]-deep[lca];
            if(left<=right)
            {
                int v=jump(x,(left+right-1)>>1);
                modify(1,1,n,seg[v],seg[v]+siz[v]-1);
            }
            else
            {
                int v=jump(rt,(left+right)>>1);
                modify(1,1,n,1,seg[v]-1);
                modify(1,1,n,seg[v]+siz[v],n);
            }
        }
        printf("%d
",sum[1]);
    }
    re 0;
}

3.贪玩蓝月

渣渣辉……

暴力背包合并+单调队列

#include<bits/stdc++.h>
#define re return
#define ll long long
#define dec(i,l,r) for(int i=l;i>=r;--i)
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}
const int N=5e4+10;
int P;
struct node{
    int w,v;
    node(int ww=0,int vv=0){
        w=ww;v=vv;
    }
}Q[N];

struct quu
{
    ll top,f[N][505];
    node g[N];
    inline void init()
    {
        top=f[0][0]=0;
        inc(i,1,P-1)f[0][i]=-1147483647;
    }
    inline void push(node x)
    {
        g[++top]=x;
        inc(i,0,P-1)
        f[top][(i+x.w)%P]=max(f[top-1][(i+x.w)%P],f[top-1][i]+x.v);     
    }
}L,R;

inline void rebuild()
{
    int r=0;
    dec(i,L.top,1)Q[++r]=L.g[i];
    inc(i,1,R.top)Q[++r]=R.g[i];
    L.init();R.init();
    //重新初始化 
    int mid=r>>1;
    dec(i,mid,1)  L.push(Q[i]);
    inc(i,mid+1,r)R.push(Q[i]);
    
}

inline int Next(int x){re x>0?x-1:P-1;}
inline bool check_in(int x,int l,int r)
{
    if(l<=r){re (x>=l&&x<=r);}
    else re x>=l||x<=r;
}

int q[1005];

inline void query(int l,int r)
{
    int head=1,tail=0;
    ll ans=-1;
    dec(i,r,l)
    {
        while(head<=tail&&L.f[L.top][i]>=L.f[L.top][q[tail]])--tail;
        q[++tail]=i;
        ans=max(ans,L.f[L.top][i]+R.f[R.top][0]);
    }
    //初始化单调序列 
    l=Next(l),r=Next(r);
    for(int i=1;i<=P-1;++i,l=Next(l),r=Next(r))
    {
        while(head<=tail&&(!check_in(q[head],l,r)))++head;
        while(head<=tail&&L.f[L.top][l]>=L.f[L.top][q[tail]])--tail;
        q[++tail]=l;
        ans=max(ans,L.f[L.top][q[head]]+R.f[R.top][i]);
    } 
    if(ans<0)
    printf("-1
");
    else printf("%lld
",ans);
    re ;
}
int m;
int main()
{
    //freopen("in.txt","r",stdin);
    int test_id,x,y;
    rd(test_id);//输入测试数据编号 
    rd(m),rd(P);//操作数以及模数 
    L.init(),R.init();//左右区间初始化 
    char opt[20];
    inc(i,1,m)
    {
        scanf("%s",opt);
        if(opt[0]=='I'&&opt[1]=='F')
        {
            rd(x),rd(y);
            L.push((node){x,y});//左端进入 
        }
        else if(opt[0]=='I')//右端加入 
        {
            rd(x),rd(y);
            R.push((node){x,y});
        }
        else if(opt[0]=='D'&&opt[1]=='F')//左端弹出 
        {
            if(!L.top)rebuild();//没有了。暴力重构 
            if(L.top)--L.top;//有直接减 
            else --R.top;
            
        }
        else if(opt[0]=='D')
        {
            if(!R.top)
                rebuild();
            if(R.top)--R.top;//其实Rebuild后R.top还等于0应该是不存在的 
                else --L.top;            
        }
        else 
        {
            rd(x),rd(y);
            //查询 
            query(x,y);
        }
    }
    re 0;
}

View Code

——九月22日考试有感