100+30+30+100

T1 F

x 只可能有 n 种情况，枚举每个 x，暴力扫一个数组找到所需的另一个值，然后开个桶判断是否合法即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[4001],b[4001],tong[4001],tot,san[4001],id[4001];
set<int>st;
inline bool check(int x)
{   if(st.find(x)!=st.end())return 0;
    for(int i=2;i<=n;++i)
    {   int y=a[i]^x;
        int id=lower_bound(san+1,san+1+tot,y)-san;
        if(san[id]!=y)return 0;
        if(!tong[id])return 0;
        --tong[id];
    }
    return 1;
}
signed main()
{   freopen("f.in","r",stdin);  
    freopen("f.out","w",stdout);
    scanf("%d",&n);    
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)scanf("%d",&b[i]),san[++tot]=b[i];
    sort(san+1,san+1+tot);tot=unique(san+1,san+1+tot)-san-1;san[tot+1]=1e9+1;
    for(int i=1;i<=n;++i)id[i]=lower_bound(san+1,san+1+tot,b[i])-san;
    for(int i=1;i<=n;++i)
    {   for(int j=1;j<=n;++j)tong[j]=0;
        for(int j=1;j<=n;++j)tong[id[j]]++;
        int x=a[1]^b[i];tong[id[i]]--;
        if(check(x))st.insert(x);
    }
    printf("%d\n",(int)st.size());
    for(auto i:st)printf("%d\n",i);
}

T2 S

神仙dp，我不会。瞎扫混了30。

考虑到交换后每种颜色内部的相对顺序不会改变，而交换次数实质就是逆序对数，于是可以 dp 构造出逆序对最小的序列。

#include<bits/stdc++.h>
using namespace std;
char a[501];
int n,ans,seq[501],tong[501],cnt[501][3],f[401][401][3],g[401][401][3];
vector<int>p[3];
inline bool check()
{   for(int i=2;i<=n;++i)if(seq[i]==seq[i-1])return 0;
    return 1;
}
signed main()
{   freopen("s.in","r",stdin);
    freopen("s.out","w",stdout);
    scanf("%d",&n);scanf("%s",a+1);
    for(int i=0;i<=2;++i)p[i].push_back(0);
    for(int i=1;i<=n;++i)
    {   if(a[i]=='R')seq[i]=0;
        if(a[i]=='G')seq[i]=1;
        if(a[i]=='Y')seq[i]=2;
        for(int opt=0;opt<=2;++opt)cnt[i][opt]=cnt[i-1][opt];
        cnt[i][seq[i]]++;p[seq[i]].push_back(i);
    }
    if(cnt[n][0]>(n+1)/2 or cnt[n][1]>(n+1)/2 or cnt[n][2]>(n+1)/2){puts("-1");return 0;}
    memset(f,0x3f3f3f3f,sizeof(f));if(cnt[n][0])f[1][0][0]=0;if(cnt[n][1])f[0][1][1]=0;if(cnt[n][2])f[0][0][2]=0;
    for(int i=1;i<n;++i)
    {   memset(g,0x3f3f3f3f,sizeof(g));
        int numa=min(cnt[n][0],i);
        for(int a=0;a<=numa;++a)
        {   int numb=min(i-a,cnt[n][1]);
            for(int b=0;b<=numb;++b)
            {   int c=i-a-b;
                for(int opt=0;opt<=2;++opt)
                {   if(f[a][b][opt]==0x3f3f3f3f)continue;
                    if(opt!=0 and a+1<=cnt[n][0])g[a+1][b][0]=min(g[a+1][b][0],f[a][b][opt]+max(0,b-cnt[p[0][a+1]][1])+max(0,c-cnt[p[0][a+1]][2]));
                    if(opt!=1 and b+1<=cnt[n][1])g[a][b+1][1]=min(g[a][b+1][1],f[a][b][opt]+max(0,a-cnt[p[1][b+1]][0])+max(0,c-cnt[p[1][b+1]][2]));
                    if(opt!=2 and c+1<=cnt[n][2])g[a][b][2]=min(g[a][b][2],f[a][b][opt]+max(0,a-cnt[p[2][c+1]][0])+max(0,b-cnt[p[2][c+1]][1]));
                }
            }
        }    
        numa=min(i+1,cnt[n][0]);
        for(int a=0;a<=numa;++a)
        {   int numb=min(i+1-a,cnt[n][1]);
            for(int b=0;b<=numb;++b)for(int opt=0;opt<=2;++opt)f[a][b][opt]=g[a][b][opt];
        }
    }
    printf("%d\n",min(f[cnt[n][0]][cnt[n][1]][0],min(f[cnt[n][0]][cnt[n][1]][1],f[cnt[n][0]][cnt[n][1]][2])));
}

T3

神仙dp，我不会，暴搜30。

发现肯定有一个人拿出了 0 个，因为全局减一会抵消掉，然后dp。

我们先做一些初步分析，设每个点往后给了 ci，若 ∀ci > 0，那么我们可以全部 −1。
于是我们考虑枚举一个 0，这样这个点是没有往后放的，就可以破环为链。
为了避免重复计数，我们枚举第一个0，强制前面没有0。此时，我们计算所有情况的贡献
和。此时，我们暴力设 dpi,j 表示到 i，给后面 j 个的贡献，那么有 dpi,j = (ai + k −j)dpi−1,k。
我们注意到只需要维护 ∑dpi,j , ∑dpi,j ×j 就可以完成转移。此时复杂度 O(n2)。注意到
转移可以写成一个 2 ×2 的矩阵乘法，我们维护一个前后缀就可以了。复杂度 O(n)。

#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;
const int mod=1000000007,inv2=500000004,inv6=166666668;
int n,a[N],f[N][2],minn=1e18,ans;
inline int calc1(int x){return x%mod*((x+1)%mod)%mod*inv2%mod;}
inline int calc2(int x){return x%mod*((x+1)%mod)%mod*((2*x+1)%mod)%mod*inv6%mod;}
inline int work(int sta,int lim)
{   memset(f,0,sizeof(f));f[1][sta]=1;
    for(int i=1;i<=n;++i)f[i+1][0]=(f[i+1][0]+f[i][0]*calc1(a[i]-lim)%mod+f[i][1]*(a[i]+1-lim)%mod+mod)%mod,
    f[i+1][1]=(f[i+1][1]+f[i][0]*((a[i]*calc1(a[i])%mod-calc2(a[i])+mod)%mod)%mod+f[i][1]*calc1(a[i])%mod+mod)%mod;
    return f[n+1][sta];
}
signed main()
{   freopen("y.in","r",stdin);
    freopen("y.out","w",stdout);
    scanf("%lld",&n);for(int i=1;i<=n;++i)scanf("%lld",&a[i]),minn=min(a[i],minn);
    ans=(work(0,0)+work(1,0))%mod;if(minn)ans=(ans-work(1,1)-work(0,1)+mod*2)%mod;printf("%lld\n",ans);
}

T4 O

我猜数据不会很强。。。

大数据不可能全部单调递减。。。

然后数据真是随出来的。。

甚至精心构造了单调递增的序列。。。

然后暴力修改就跑过了。

题目即为：给出 ai，每次问 (t, l, r) 表示 ∑r
i=l maxi−t≤j≤iaj
考虑向前面第一个大于它的连边，那么会变成一颗树，那么就是每个点不断往上跳，然后
求和。
我们考虑枚举每条边，求出它被跳过的次数，设它的子树是 [i, ri)，权值为 c 那么它会对
x ∈[i, ri), y ≥p −t 的点加上 c，记 x ≥a, y ≥x −b 的修改为 (a, b, c)。
差分成两个直角三角形，从下往上扫描线。
考虑询问前缀 p，那么贡献就是 c(min(p, b + t) −min(p, a)) 容易注意到两维已经独立开
了，分别前缀加前缀求和就可以了（前面变成 t + min(p −t, b)）

#include<bits/stdc++.h>
#define int long long
#define N 200050
using namespace std;
int maxn[N<<2],sum[N<<2],n,q,a[N],sta[N],top,ans[N];
vector<pair<int,int> >ve[N];
struct jj
{int times,l,r,id;}Q[N];
inline void pushup(int x)
{   sum[x]=sum[x<<1]+sum[x<<1|1];
    maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
}
inline void build(int x,int l,int r)
{   if(l==r){sum[x]=maxn[x]=a[l];return;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    pushup(x);
}
inline int qmax(int x,int l,int r,int L,int R)
{   if(l>=L and r<=R)return maxn[x];
    int mid=(l+r)>>1,res=0;
    if(mid<R)res=max(res,qmax(x<<1|1,mid+1,r,L,R));
    if(mid>=L)res=max(res,qmax(x<<1,l,mid,L,R));
    return res;
}
inline void ins(int x,int l,int r,int pos,int val)
{   sum[x]+=val;if(l==r)return;
    int mid=(l+r)>>1;
    if(mid<pos)ins(x<<1|1,mid+1,r,pos,val);
    else ins(x<<1,l,mid,pos,val);
}
inline int qsum(int x,int l,int r,int L,int R)
{   if(l>=L and r<=R)return sum[x];
    int mid=(l+r)>>1,res=0;
    if(mid<R)res+=qsum(x<<1|1,mid+1,r,L,R);
    if(mid>=L)res+=qsum(x<<1,l,mid,L,R);
    return res;
}
inline void work()
{for(int i=1;i<=q;++i)printf("%lld\n",qmax(1,1,n,max(1ll,Q[i].l-Q[i].times),Q[i].l));}
inline bool cmp(jj i,jj j){return i.times<j.times;}
signed main()
{   freopen("o.in","r",stdin);
    freopen("o.out","w",stdout);
    scanf("%lld%lld",&n,&q);   
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    build(1,1,n);bool bo=1;
    for(int i=1;i<=q;++i)
    {   scanf("%lld%lld%lld",&Q[i].times,&Q[i].l,&Q[i].r);Q[i].id=i;
        if(Q[i].l!=Q[i].r)bo=0;
    }
    if(bo){work();return 0;}
    for(int i=1;i<=n;++i)
    {   while(top and a[sta[top]]<=a[i])--top;
        sta[++top]=i;
        for(int j=top-1;j;--j)ve[i-sta[j]].push_back(make_pair(i,a[sta[j]]-a[sta[j+1]]));

    }
    sort(Q+1,Q+1+q,cmp);int zhi=0;
    for(int i=1;i<=q;++i)
    {   while(zhi+1<=Q[i].times)
        {   ++zhi;
            for(auto j:ve[zhi])ins(1,1,n,j.first,j.second);
        }
        ans[Q[i].id]=qsum(1,1,n,Q[i].l,Q[i].r);
    }
    for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
}