传送门

A. XORinacci

手玩三四项发现序列就是 $a,b,a\ xor\ b,a,b,...$，直接输出即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
int T,a,b,n;
// a b ab a b
int main()
{
    T=read();
    while(T--)
    {
        a=read(),b=read(),n=read();
        if(n%3==0) printf("%d\n",a);
        if(n%3==1) printf("%d\n",b);
        if(n%3==2) printf("%d\n",a^b);
    }
    return 0;
}

View Code

 

B. Uniqueness

$n$ 不大，直接枚举所有左端点，移动右端点并动态维护，数值比较大用 $map$ 即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2007;
int n,a[N],tot,ans=N;
map <int,int> sum,cnt,vis;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),sum[a[i]]++;
    for(int i=1;i<=n;i++)
        if(sum[a[i]]>1&&!vis[a[i]]) tot++,vis[a[i]]=1;
    if(!tot) { printf("0\n"); return 0; }
    for(int i=1;i<=n;i++)
    {
        cnt.clear(); int now=0;
        for(int j=i;j<=n;j++)
        {
            cnt[a[j]]++; if(cnt[a[j]]==sum[a[j]]-1) now++;
            if(now==tot) { ans=min(ans,j-i+1); break; }
        }
    }
    printf("%d\n",ans);
    return 0;
}

View Code

 

C. Magic Grid

又是构造题...

猜一下有规律，发现这样的矩阵横竖异或和都是 $0$：

 

......

发现 $n$ 一定是 $4$ 的倍数，所以把大矩形分成一些 $4*4$ 的矩形，然后把按上面的规律把矩阵一个个填入即可

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2007;
int n,a[N][N],tot;
int main()
{
    n=read();
    for(int i=1;i<=n;i+=4)
        for(int j=1;j<=n;j+=4)
            for(int k=0;k<4;k++)
                for(int l=0;l<4;l++)
                    a[i+k][j+l]=tot++;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}

View Code

 

 

D. Restore Permutation

正难则反，考虑从后往前确定所有数，对于当前最后面的数，之前所有还没填的小于它的数都会产生贡献，发现当前位置的数越大，前面的贡献也越大

所以根据单调性直接二分最后一个位置的数，维护当前小于某个数的和用树状数组即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e5+7;
int n,b[N];
bool vis[N];
ll a[N],t[N];
inline void add(int x,int v) { while(x<=n) t[x]+=v,x+=x&-x; }
inline ll ask(int x) { ll res=0; while(x) res+=t[x],x-=x&-x; return res; }
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),add(i,i);
    for(int i=n;i>=1;i--)
    {
        int L=1,R=n,mid,res;
        while(L<=R)
        {
            mid=L+R>>1;
            if(ask(mid-1)<=a[i])
            {
                L=mid+1;
                if(!vis[mid]) res=mid;
            }
            else R=mid-1;
        }
        b[i]=res; vis[res]=1; add(res,-res);
    }
    for(int i=1;i<=n;i++) printf("%d ",b[i]);
    printf("\n");
    return 0;
}

View Code

 

E. Let Them Slide

看一眼直接单调队列走起，然后被区间细节搞死，其实直接 $ST$ 表就可以了..

发现每一行可以分开处理，求出每一行每个位置的贡献加起来就行了

发现如果一行的数不多，那么中间一段位置的贡献都是最大的数，所以只要求出左右两边位置的最大值

发现左右两边的情况都差不多，先考虑左边

对于位置 $i$，在它之前的位置为 $j$ 的数要能够移动到 $i$ 的条件是 $i-j<=m-R$，其中 $m$ 是每一行最大长度，$R$ 是此行的数的数量

然后就可以单调队列维护，右边也同理，注意边界一段也可以没有数，即为 $0$，要记得处理

中间的话，维护一下差分标记即可，一些数组用完一定要记得还原！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e6+7,INF=1e9+7;
int n,m;
vector <int> V[N];
ll sum[N],tag[N]; int now[N];
int Q[N],l,r;
int main()
{
    n=read(),m=read(); int a;
    for(int i=1;i<=n;i++)
    {
        a=read();
        for(int j=1;j<=a;j++) V[i].push_back(read());
    }
    memset(now,~0x3f,sizeof(now));//初始为-INF
    for(int i=1;i<=n;i++)
    {
        int R=V[i].size(),mx=0; l=1,r=0;
        for(int j=1;j<=min(m-R,R);j++) now[j]=0;
        for(int j=m;j>max(m-R,R);j--) now[j]=0;//边界可以没有数
        for(int j=1;j<=R;j++)
        {
            while(l<=r && j-Q[l]>m-R) l++;
            while(l<=r && V[i][j-1]>=V[i][Q[r]-1]) r--;//记得vector下标从0开始
            Q[++r]=j; now[j]=max(now[j],V[i][Q[l]-1]); mx=max(mx,V[i][j-1]);
        }
        if(R*2<m) tag[R+1]+=mx,tag[m-R+1]-=mx;//打差分标记
        l=1,r=0;
        for(int j=R;j;j--)
        {
            int p=m-R+j;//当前位置
            while(l<=r && Q[l]-j>m-R) l++;
            while(l<=r && V[i][j-1]>=V[i][Q[r]-1]) r--;
            Q[++r]=j; now[p]=max(now[p],V[i][Q[l]-1]);
        }
        for(int j=1;j<=R;j++) sum[j]+=now[j];//累计贡献
        for(int j=max(R+1,m-R+1);j<=m;j++) sum[j]+=now[j];
        for(int j=1;j<=R;j++) now[j]=now[m-R+j]=-INF;//记得还原
    }
    ll S=0;
    for(int i=1;i<=m;i++) S+=tag[i],sum[i]+=S;//处理差分标记
    for(int i=1;i<=m;i++) printf("%lld ",sum[i]);
    printf("\n");
    return 0;
}

View Code