自闭了自闭了
自己还是太菜了呀,打的时候只有30pts。


T1 Sequence

就是让我们求存不存在,$A_i+A_j>A_k\&\& A_i+A_k>A_j\&\& A_j+A_k>A_i$这样的位置。
先将序列排序,判断其是否能构成。
考虑不存在的最长序列,如果要最长,那么增量要最小。
也就是斐波那契数列,发现斐波那契的第50项已经大于值域中的最大值,因此仅需要枚举前50项就好了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int m;scanf("%d",&m);
    while(m--)
    {
        int op;scanf("%d",&op);
        if(op==2)
        {
            int ans1=-1,ans2=-1,ans3=-1;bool bk=false;
            for(int k=3;k<=n&&!bk;k++)
                for(int j=2;j<=k-1&&!bk;j++)
                    for(int i=1;i<=j-1&&!bk;i++)
                    {
                        if(a[i]+a[j]>a[k]&&a[i]+a[k]>a[j]&&a[j]+a[k]>a[i])
                        {
                            ans1=min(a[i],min(a[j],a[k]));
                            if(ans1==a[i])ans2=min(a[j],a[k]),ans3=max(a[j],a[k]);
                            if(ans1==a[j])ans2=min(a[i],a[k]),ans3=max(a[i],a[k]);
                            if(ans1==a[k])ans2=min(a[i],a[j]),ans3=max(a[i],a[j]);
                            bk=1;
                        }
                    }
            printf("%d %d %d\n",ans1,ans2,ans3);
        }
        else 
        {
            int x,y;scanf("%d%d",&x,&y);
            a[x]=y;
        }
    }
    return 0;
}

$n^3$轻松水过此题


T2 登山

30pts

打个无脑DP,成就达成。

50pts

C1.PNG
考虑没有障碍的情况,唯一的限制条件就是不能经过粉色这条直线($y=x+1$)。
做一条不合法的路径。
C2.PNG
可以发现做$(N,N)$关于$y=x+1$的对称点$(N-1,N+1)$后,原点到对称点的方案数,实际上就是到$(N,N)$的不合法方案数。
这是因为有一部分路径关于$y=x+1$对称。
也就是说从原点到对称点的一条路径必然会碰到粉线,且可以对称回一条到终点的路径。

那么(0,0)到(x,y)的方案数(不管合不合法)是很容易得知的,也就是$C_{x+y}^x$,做一个插空问题就好了。
(0,0)到(n,n)的合法方案数就为:$C_{2n}^n-C_{2n}^{n-1}$

70pts

已经很接近成功了。
由于直接求关键点比较困难,可以用补集的思想求解。
由于关键点只有一个(x,y),
不合法的方案也就是从原点到(x,y)的合法方案数(合法指不经过粉线)*再从(x,y)到(n,n)的合法方案数。

Tips:

在求解(x,y)到(n,n)的合法方案数时,需先处理出对称点,再平移坐标系,否则y=x+1会随着平移而改变,增加问题的复杂度。

100pts

把关键点按照x为第一关键字,y为第二关键字排序。
设$F_i$为(0,0)到第i个关键点的合法方案数,$G_i=\sum_{j=1}^i F_j*way_{p_j->p_j}$,$F_i=way_{(0,0)->p_i}-G_i$
根据70pts的结论,再加上文字解释,是可以证明的。
撒花。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define ll long long
using namespace std;
const int N=2e5+5;
const int M=5010;
const int mod=1e9+7;
ll p[N],inv[N],f[1010];bool a[M][M];
struct node{int x,y;bool operator <(const node a)const{return x==a.x?y<a.y:x<a.x;}}b[1010];
inline ll pow_mod(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        b>>=1;a=a*a%mod;
    }
    return ans;
}
ll calcat(ll n,ll m)//cat(n)=c(n,2n)-c(n-1,2n)
{
    ll ans=p[n];
    ans=ans*inv[m+1]%mod*inv[n-m]%mod;
    return ans;
}
ll calc(ll n,ll m)
{
    if(n<0||m<0||m>n)return 0;
    ll ans=p[n];
    ans=ans*inv[m]%mod*inv[n-m]%mod;
    return ans;
}
int main()
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    int n,c;scanf("%d%d",&n,&c);
    p[0]=inv[0]=1;for(int i=1;i<=2*n;i++)p[i]=p[i-1]*i%mod;
    inv[2*n]=pow_mod(p[2*n],mod-2);//      1/[(2*n)*(2*n-1)*(2*n-2)*....*1]
    for(int i=2*n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
    if(c==0)
    {
        ll ans=calcat(n*2,n);
        printf("%lld\n",ans);
        return 0;
    }
    if(c==1)
    {
        int x,y;
        scanf("%d%d",&x,&y);//(0,0)->(x,y),(0,0)->(y-1,x+1)
        ll ans=(calcat(n*2,n)-(calc(x+y,x)-calc(x+y,y-1))*(calc(n*2-x-y,n-x)-calc(n*2-x-y,n-x-1))%mod+mod)%mod;
        printf("%lld\n",ans);
        return 0;
    }
    /*memset(a,1,sizeof(a));
    for(int i=1,x,y;i<=c;i++)scanf("%d%d",&x,&y),a[x][y]=0;
    memset(f,0,sizeof(f));f[0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
            if(i<n&&a[i+1][j])f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
            if(j<n&&i!=j&&a[i][j+1])f[i][j+1]=(f[i][j+1]+f[i][j])%mod;
        }
    printf("%lld\n",f[n][n]);*/
    for(int i=1;i<=c;i++)scanf("%d%d",&b[i].x,&b[i].y);
    sort(b+1,b+c+1);b[++c]=(node){n,n};
    int x=b[1].x,y=b[1].y;
    f[1]=(calc(x+y,x)-calc(x+y,y-1)+mod)%mod;
    for(int i=2;i<=c;i++)
    {
        ll sum=0;x=b[i].x,y=b[i].y;
        for(int j=1;j<i;j++)
        {
            int nx=b[j].x,ny=b[j].y;//(nx,ny)->(y-1,x+1),(nx,ny)->(x,y)
            sum=(sum+(f[j]*((calc(x+y-nx-ny,x-nx)-calc(x+y-nx-ny,y-nx-1)+mod)%mod)%mod))%mod;
        }
        //(0,0),(x,y),(0,0),(y-1,x+1)
        f[i]=((calc(x+y,x)-calc(x+y,y-1)+mod)%mod-sum+mod)%mod;
    }
    printf("%lld\n",f[c]);
    return 0;
}
/* 
5 1
1 1



7 4
6 5
5 3
2 1
7 1

*/

T3 melancholy

关于$K=1$的情况,打个简单的线段树,维护一下最小值和区间和,莫得感情的30pts。
之后有两种做法,

  • 容斥原理

先说一下下列的$s_1$为v值的和,$s_2$为v值平方的和,$s_3$为v值立方的和,以此类推。

K=1时,答案就为$s_1$。

K=2时,答案就为${s_{1}}^2-2*{s_2}$,意思就是从n个数中选出2个(可以相同)组成的不同排列(不是组合)的乘积的和 减去 从n个数中选出1个数,将这个数自乘的乘积的和,转化成表达式就是$(A_1\sim A_n) * (A_1\sim A_n) -({A_1}^2\sim{A_n}^2)$

K=3时,答案就为${s_{1}}^3-3*s[1]*s[2]+2*s[3]$,表达式是类似的,$(A_1\sim A_n) * (A_1\sim A_n)* (A_1\sim A_n) -3*({A_1}^2\sim{A_n}^2)*(A_1\sim A_n)+2*({A_1}^3\sim{A_n}^3)$

K=4,5,6时,由于个人能力有限,无法推出,程序打表即可。

时间复杂度 O(nlog_nK)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ui unsigned int
using namespace std;
const int N=1e5+5;
const int K=7;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(ui x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct Seg
{
    ui d,s[K];
    void set(ui x)//类似一个重置
    {    
        s[1]=x;//和 
        for(int i=2;i<K;i++)s[i]=s[i-1]*x;//2:平方和,。。。。 
    }
    ui calc(int k)
    {
        if(k==1)return s[1];
        if(k==2)return s[1]*s[1]-s[2];
        if(k==3)return s[1]*s[1]*s[1]-3*s[2]*s[1]+2*s[3];
        if(k==4)return s[1]*s[1]*s[1]*s[1]-6*s[1]*s[1]*s[2]+8*s[1]*s[3]+3*s[2]*s[2]-6*s[4];
        if(k==5)return s[1]*s[1]*s[1]*s[1]*s[1]-10*s[1]*s[1]*s[1]*s[2]+20*s[1]*s[1]*s[3]+15*s[1]*s[2]*s[2]-30*s[1]*s[4]-20*s[2]*s[3]+24*s[5];
        return s[1]*s[1]*s[1]*s[1]*s[1]*s[1]-15*s[1]*s[1]*s[1]*s[1]*s[2]+40*s[1]*s[1]*s[1]*s[3]+45*s[1]*s[1]*s[2]*s[2]-90*s[1]*s[1]*s[4]-120*s[1]*s[2]*s[3]-15*s[2]*s[2]*s[2]+144*s[1]*s[5]+90*s[2]*s[4]+40*s[3]*s[3]-120*s[6];
    }
    Seg operator +(const Seg a)const
    {
        Seg b;
        for(int i=1;i<K;i++)
            b.s[i]=a.s[i]+s[i];
        return b; 
    }
    Seg operator -(const Seg a)const
    {
        Seg b;
        for(int i=1;i<K;i++)
            b.s[i]=s[i]-a.s[i];
        return b;
    }
}t[N<<2],opf;ui opd;
struct node{ui d,v;bool operator <(const node a)const{return d<a.d;}}a[N];
void build(int p,int l,int r)
{
    if(l==r){t[p].d=a[l].v;t[p].set(t[p].d);return ;}
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    t[p]=t[p<<1]+t[p<<1|1];t[p].d=min(t[p<<1].d,t[p<<1|1].d);
}
void query(int p,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r){opf=opf+t[p];opd=min(opd,t[p].d);return ;}
    int mid=l+r>>1;
    if(ql<=mid)query(p<<1,l,mid,ql,qr);
    if(qr>mid)query(p<<1|1,mid+1,r,ql,qr);
}
int n,m;
int get(ui d)
{
    int l=1,r=n+1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(a[mid].d<d)l=mid+1;
        else r=mid;
    }
    return l;
}
int main()
{
    freopen("melancholy.in","r",stdin);
    freopen("melancholy.out","w",stdout);
    qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(a[i].d);
    for(int i=1;i<=n;i++)qr(a[i].v);
    sort(a+1,a+n+1);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int L,R,k;qr(L),qr(R),qr(k);
        opf.set(0);opd=1e9+5;Seg f;
        int l=get(L),r=get(R);if(a[r].d!=R)r--;
        if(r-l+1<k)
            puts("0");
        else 
        {
            query(1,1,n,l,r);
            f.set(opd);
            opf=opf-f;qw(opf.calc(k));puts("");
        }
    }
    return 0;
}
/*
5 3
5 4 7 2 6
1 4 5 3 2
6 7 1
2 6 2
1 8 3

*/
  • 背包实现
    明天再打。