T1 洛希极限

咕。

#include<bits/stdc++.h>
#define N 2010
#define mod 1000000007
#define left llllll
using namespace std;
int T,n,m,q,lim[N],minn[N<<2],left[N][N],down[N][N];
vector<int>q1[N],q2[N],q3[N],Q1[N],Q2[N],Q3[N];
struct zxb
{   int maxn,sum;
    zxb operator +(zxb x)
    {return (maxn==x.maxn)?(zxb){maxn,(sum+x.sum)%mod}:(maxn>x.maxn?(zxb){maxn,sum}:x);}
}ans,rmp,dp[N][N];
struct Queue
{   int head,tail,q[N],tong[N];zxb v[N];
    inline void push(int id,zxb x){while(head<=tail and v[tail].maxn<x.maxn)tong[v[tail--].maxn]=0;v[++tail]=x;q[tail]=id;(tong[x.maxn]+=x.sum)%=mod;}
    inline zxb query(int lim){while(head<=tail and q[head]<lim)tong[v[head].maxn]=(tong[v[head].maxn]-v[head].sum+mod)%mod,++head;return (head<=tail)?(zxb){v[head].maxn,tong[v[head].maxn]}:(zxb){0,0};}
    inline void clear(){while(head<=tail)tong[v[tail--].maxn]=0;head=1;tail=0;}
}s[N],h[N];
inline void build(int x,int l,int r){minn[x]=N;if(l==r)return;int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);}
inline void update(int x,int l,int r,int L,int R,int val){if(val>minn[x])return;if(l>=L and r<=R){minn[x]=min(minn[x],val);return;}int mid=(l+r)>>1;if(mid<R)update(x<<1|1,mid+1,r,L,R,val);if(mid>=L)update(x<<1,l,mid,L,R,val);}
inline void print(int x,int l,int r,int val){val=min(val,minn[x]);if(l==r){lim[l]=val;return;}int mid=(l+r)>>1;print(x<<1,l,mid,val);print(x<<1|1,mid+1,r,val);}
signed main()
{   freopen("roche.in","r",stdin);
    freopen("roche.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {   scanf("%d%d%d",&n,&m,&q);ans=(zxb){0,0};
        
        for(int i=1;i<=m;++i)Q1[i].clear(),Q2[i].clear(),Q3[i].clear(),s[i].clear();
        for(int i=1;i<=n;++i)q1[i].clear(),q2[i].clear(),q3[i].clear(),h[i].clear();
        for(int i=1;i<=q;++i)
        {   int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2 or y1==y2)continue;
            Q1[y2].push_back(x1+1),Q2[y2].push_back(x2),Q3[y2].push_back(y1);
            q1[x2].push_back(y1+1),q2[x2].push_back(y2),q3[x2].push_back(x1);
        }        
        build(1,1,n);
        for(int i=m;i;--i)
        {   for(int j=0;j<Q1[i].size();++j)update(1,1,n,Q1[i][j],Q2[i][j],Q3[i][j]);
            print(1,1,n,m);for(int j=1;j<=n;++j)left[j][i]=min(i,lim[j]);
        }
        build(1,1,m);
        for(int i=n;i;--i)
        {   for(int j=0;j<q1[i].size();++j)update(1,1,m,q1[i][j],q2[i][j],q3[i][j]);
            print(1,1,m,n);for(int j=1;j<=m;++j)down[i][j]=min(i,lim[j]);
        }
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
        {   dp[i][j]=(zxb){0,1};
            if(i-1>=1 and j-1>=1)h[i-1].push(j-1,dp[i-1][j-1]);
            if(i-2>=1 and j-1>=1)s[j-1].push(i-2,dp[i-2][j-1]);
            dp[i][j]=dp[i][j]+h[i-1].query(left[i][j])+s[j-1].query(down[i][j]);
            ++dp[i][j].maxn;ans=ans+dp[i][j];
        }
        printf("%d %d\n",ans.maxn,ans.sum);
    }
}

T2 特立独行的图

咕。

T3 玩游戏

咕。

#include<bits/stdc++.h>
#define int long long
#define double long double 
using namespace std;
int n,k,now;
double ans=1,f[2][1000001];
const double r=0.577215664;
inline double H(int x){return log(n+1)+r;}
inline double solve(int n,int k)
{   if(!k){return H(n);}
    double tmp=1.L/k;
    for(int i=k;i>=1;--i)tmp=tmp*(n+i)/i;
    return solve(n+1,k-1)/k*(n+1)-tmp;
}
signed main()
{   freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
    cout.unsetf(ios::fixed);
    cout.setf(ios::scientific);
    cout.precision(9);
    cin>>k>>n;
    if(n<=1000000)
    {
        for(int i=1;i<=n;++i)f[0][i]=f[0][i-1]+1.0/i;
        for(int i=1;i<=k;++i)
        {   now^=1;double sum=0;
            for(int j=1;j<=n;++j)sum+=f[now^1][j],f[now][j]=sum;
        }
        cout<<f[now][n]<<endl;
        return 0;
    }
    else
    {   if(!k){cout<<H(n)<<endl;return 0;}
        cout<<solve(n,k)<<endl;
    }
}

T4 骆驼

咕。