NOI Online 2020 Round1 家里蹲记_综合

这一切的一切，要从一只蝙蝠说起…
因为新冠病毒的肆虐，CCF 良心地为我们准备一场史无前例的~~开黑大赛~~。
~~说是要在3.20更的结果被我咕到了3.22…~~
OI/语文大佬当然可以来这篇博客看笑话，围观者可是这世界上必不可少的一类人。

赛时

CCF果不其然用了一个远古比赛系统来考试…比赛过了1h我才能够交题。
看完T1之后感觉心态有点崩…觉得这道题目并不简单…不过部分分是给了很多的，看了一下80分可以轻松拿到手，但是100分还真没有这么简单了。大概想了1h左右终于有了一些思路，然后就开始写，过了样例和自己出的几组数据之后已经大概1h45min了，所以赶紧去看后面的题。
然后看T2，看到这种题目感觉很复杂…然后顺便看了一眼T3，一脸可做的样子，于是决定先想T3。
10min发现80分很容易就可以拿到，后来想起了长度为 $n$ 划分为 $k$ 个循环节每个大小为 $g c d (n, k)$ ，于是在 $O (n D (n))$ 内就可以出解了…然后赶紧把正解打了…
打完这些就只剩下大概50min了，赶紧看T2…由于时间是在是太少了，心态一直很慌。中途有想过打对于每个数的逆序对的表来找规律，以为没什么用，就放弃了。然后突然脑袋一进水以为序列是随着2操作修改的…搞出来了一个特别奇怪的算法…写了一会之后清醒了…然后就真的没什么时间了，只好把20pts的暴力打了。
中间有个小插曲，就是突然在UOJ群里发现有题目更正[顺便吐槽一下CCF这是什么操作…]…赶紧把代码改了…
考完之后很崩溃，UOJ一群大佬估计前25%全部AK，其他同学好像也考的很好的样子…那我这次不是完了…
期望得分: $100 + 20 + 100 = 220$ [丢脸选手]
洛谷上测出来一样…

赛后分析

出分了: $85 + 40 + 100 = 225$
T1居然FST了…后来发现我只判了自环没判奇环…
T2莫名其妙多了20分，不过这样其他同学也多了20分…我的排名大概是变低了[~~不过250很能体现我的真实智商水平~~]。
不知为何我们学校高一高二的全炸了，我这点分居然还算是考的比较好的了。感到一阵寒意。

首先评价一下这次NOI Online 2020 准备计划的效果。题目算是出乎我的意料吧。首先确实没有预料到这套题目是PKU出的，之前的复习确实也就没什么意义了，不过它还是没有逃脱THU永恒不变的四大主题(树,数据结构,dp,结论题)。个人认为这次的题目实际上就是三道结论题。其次是我没有预料到这次的题目的难度会这么平均，而且有一种打乱顺序的感觉。不过我赛前对自己的大致估分也是200左右。
然后反思一下这次比赛的策略。应该说还是没什么OI比赛的经验，平常打CF的时候就想着打OI比赛的时候就可以慢点做，不用这么着急。结果真正OI赛制考试的时候还是没有充足的时间把题目做完。或者说，我还是没有找到一种好的策略来合理做题跳题，之后的OI比赛要多打些才行。
接着反思一下这次比赛的技巧问题。如果我T2尝试了打表找规律的话，这次考试可能就不会只有这点分数了（当然先打40分暴力保底同样重要）。这也和我很久没有机会在OI比赛中乱搞有关系。我认为在OI赛制考试中的乱搞能力很重要，其实这也能算是一种脑洞。由于我们很长一段时间通过Codeforces和Atcoder训练，我们这届高一的同学做OI题目通常很死板，基本上是要么AC要么就爆零。除非是很容易的部分分，多数同学才会选择去打，但即使如此也不会像AC代码那样仔细地去验证。可是真正到了大型比赛的时候，这些部分分往往是我们能用来区分对手的关键分数。虽然有时确实需要拼一些运气，但联赛这种用来保底的比赛真的没有必要。
最后反思一下这次比赛的心态问题。我觉得我有考试deadline焦虑综合症…我确实是一个心态很失控的人，不过这几年以来心态好多了[可能和我whk日常垫底有关系]。当然这是一个长期的过程，还需要继续调整。
现在的我已经高一了，不知不觉间成了OI中老年选手。现在的我也终于能够感受到原来高二同学巨大压力。原来初三的时候我一直支持THU将联赛的知识点尽量简化，将重心转为考察选手思维的模式，毕竟我也算是其中的受益者。但是如今我却也因此而垂头懊恼。如今的OI已经逐渐低龄化，作为想要冲顶却极有可能被过河拆桥的高一高二同学来说，这是一个巨大的挑战。我不敢试看几年后的OI会怎么样，那必将是一个让现在的我们感到惶恐的时代。如今已经即将奔向沙滩的我们，是否会为在这个时代学习OI而感到窃喜，抑或是为没能在以前的时代学习OI而感到懊悔？无论如何，我都无悔于这段带着沙粒奔向沙滩的时光。
最近生物课学了细胞的分化，我们身上的无数的细胞正是由一个小小的卵细胞所分裂和分化而成的，在基因不断地选择性表达过后，最终找到一个稳定的状态。我想，我现在为何不是处在这样的时期中的呢?在找到一个长久不变的状态之前，我们还需要经历多少次的选择，这些选择真的会是自由的吗?我疑惑，我不解，我迷茫。

简单题解

T1-序列

一道结论性的图论题目。
首先对于 $t_i=2$ 的情况，我们很容易发现:如果将操作看做一条边，对于一个连通块的总和是不变的。
所以我们考虑并查集，考虑将通过并查集将一些点合并为一个点。
然后是 $t_i=1$ 时的操作，这时候你会发现如果合并后的点连 $t_i=1$ 操作的边，图显然会构成一个连通块。对于每个连通块显然都必须满足条件。
考虑一个路径 $(x, y, z)$ ，先把 $v_x+1,v_y+1$ ，再把 $v_y-1,v_z-1$ ，你会发现这与对 $(x, z)$ 做 $2$ 操作是等价的。所以我们对每个连通块做二分图染色，显然如果两个部分的差等于 $0$ 是一定可以的。注意到这个图还可以有自环，这时候你可以不断加 $2$ ，因此这时候差只要是 $2$ 的倍数即可。更进一步你会发现奇环也可以达到这样的目的，因此也需要这样判断。
复杂度: $O(N+Mlog?N)O(N+M\log N)$

/*Lower_Rating*/
/*NOI Online*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 200000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int T,n,m,cnt,ans,F;
int fa[MAXN+5],vis[MAXN+5],val[MAXN+5];LL sum[MAXN+5];
vector<int> G[MAXN+5];
int xfind(int x){
    return (fa[x]==x)?x:fa[x]=xfind(fa[x]);}
struct edge{
    int u,v;
}e[MAXN+5];void dfs(int x,int col){
    F|=val[x],vis[x]=1+col;for(int i=0;i<G[x].size();i++){
    int v=G[x][i];if(!vis[v]){
    dfs(v,col^1);sum[x]-=sum[v];}else F|=(vis[v]==col+1);}
}int main(){
    //freopen("sequence.in","r",stdin);//freopen("sequence.out","w",stdout);T=read();while(T--){
    ans=1,cnt=0,mem(vis,0),mem(val,0);n=read(),m=read();for(int i=1;i<=n;i++)sum[i]=read(),fa[i]=i,G[i].clear();for(int i=1;i<=n;i++)sum[i]-=read();for(int i=1;i<=m;i++){
    int op=read(),u=read(),v=read();if(op==1)e[++cnt]=(edge){
    u,v};else{
    u=xfind(u),v=xfind(v);if(u!=v)fa[u]=v,sum[v]+=sum[u];}}for(int i=1;i<=cnt;i++){
    int a=xfind(e[i].u),b=xfind(e[i].v);if(a==b)val[a]=1;else G[a].push_back(b),G[b].push_back(a);}for(int i=1;i<=n;i++)if(xfind(i)==i&&!vis[i]){
    F=0,dfs(i,0);if(F)ans&=(sum[i]%2==0);else ans&=(!sum[i]);}if(ans)puts("YES");else puts("NO");}
}

T2-冒泡排序

T3-最小环

我认为这题是全场最简单的一道题目吧…
所以就不想口胡了…

/*Lower_Rating*/
/*NOI Online*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 200000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int n,m,a[MAXN+5];
LL ans[MAXN+5],tmp[MAXN+5];
int gcd(int a,int b){
    if(!b)return a;return gcd(b,a%b);
}LL cal(int L){
    LL res=0;//printf("::%d\n",L);for(int i=1;i<=n;i+=L){
    int l=i,r=i+L-1,pl=(L+1)/2,pr=(L+1)/2;tmp[pl]=a[l];for(int j=1;j<L;j++){
    if(j&1)pr++,tmp[pr]=a[j+l];else pl--,tmp[pl]=a[j+l];}for(int j=1;j<=L;j++)res+=tmp[j]*tmp[j%L+1];}return res;
}int main()
{
    //freopen("ring.in","r",stdin);//freopen("ring.out","w",stdout);n=read(),m=read();for(int i=1;i<=n;i++)a[i]=read();sort(a+1,a+n+1);reverse(a+1,a+n+1);for(LL i=1;i*i<=n;i++)if(n%i==0){
    ans[i]=cal(i);if((n/i)!=i)ans[n/i]=cal(n/i);}while(m--){
    int k=read();int L=n/gcd(n,k);printf("%lld\n",ans[L]);}
}