NOIP(csp?)前的比赛

发表于 更新于 阅读次数：

记录下各种考试。

Manthan, Codefest 19

总结：

熬夜打了一半就咕了，只写了3题，当时想出了D的正解然而懒得打了。

如果时间是5h大概可以写出前6题的样子，但是2h完全码不动。

A. XORinacci

题目链接

题意：f(0)=a,f(1)=b,f(n)=f(n-1)^f(n-2)，求f(n)。(a,b,n<=1e9)

solution:显然可以拆位，每一位分成四种情况讨论，显然有循环节，打个表即可。

B. Uniqueness

题目链接

题意：给定一个数列，求删去最短的连续一段使得剩下的数字不重。(n<=2000)

solution:二分答案之后每次暴力扫，离散化了开个权值线段树维护一下就是O(nlog^2n)的，2000不知道是干什么。

C. Magic Grid

题目链接

题意：给定一个n，求一个n*n的方阵，权值为[0,n^2-1]的排列，使得所有行列的异或和相等。(n<=1000,n=4k)

solution:构造题，卡了一会，开始的思路是直接顺序填，这样行全是0，但是这样只有n为2的整数次幂的时候才有用。然后可以发现n=4k，这样只要顺序填4*4的小方阵即可。这样同一行相邻两列相差1，异或和为0，同一列同小方阵差4，一列相邻4行异或和也为0。

D. Restore Permutation

题目链接

题意：已知有一个长为n的排列a，现在给定一个数列S，S_i表示\sum_{j=1}^{i-1}[a_j<a_i]a_j。(n<=2e5)

solution:考虑当前最小值就是S中最靠后的那个0，每次填一个最小值x就把它后面所有S_i都减去一个x即可。用线段树维护区间最小值，区间最小值最靠右的出现位置，以及区间加即可。

E. Let Them Slide

题目链接

题意：有n个数组，都放在长为w的框中，数组长度为len_i，数组可以在框里面滑动，求每一列通过滑动数组能拼出的最大和。(n,w,\sum_{i=1}^{n}len_i<=1e6)

solution:考虑第i行对第j列的贡献，就是max(a[i][j-(w-len_i),j])，一眼滑动窗口，当len_i>=\frac{w}{2}的时候暴力滑动（边加边删），否则分成三段（只加、不加不删、只删），中间不加不删直接打差分标记即可。

总复杂度O(\sum len)。

F. Bits And Pieces

题目链接

题意：给定一个数列a，求a_i|(a_j&a_k)(i<j<k)，(n，a_i<=1e6)

solution:考虑先把后面a_j&a_k算出来，设f[i][1/2]表示i出现最靠后的两个位置，注意这里出现不一定就是i=a_j这样，而是(i&a_j)=i就算i在j位出现了。初值就是真实出现的位置，然后每次枚举删去某一位的1来更新dp值。比如10101在枚举第5位的时候更新00101，在枚举第3位的时候10101更新10001、00101更新00001。

然后枚举每一位，显然我们有的位置使得其为0能放宽条件，设二进制都为1的时候为limit，那么我们只用考虑limit-a[i]中的1那些可以选到即可。还是从高位到低位枚举，若f[val][1]>i且f[val][2]有值那么该位就可以为1。对每个max_i|a[i]取个最大值即可。

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=2e6+10;
int n,a[N],ans,f[N][3],limit,maxn;
void add(int val,int x){
    if(!f[val][1])f[val][1]=x;
    else if(!f[val][2])f[val][2]=x;
    else{
        if(f[val][2]<x)f[val][1]=f[val][2],f[val][2]=x;
        else if(f[val][1]<x)f[val][1]=x;
    }
    if(f[val][1]>f[val][2]&&f[val][2])swap(f[val][1],f[val][2]);
}
void up(int v,int u){
    if(f[u][1])add(v,f[u][1]);
    if(f[u][2])add(v,f[u][2]);
}
int main(){
    register int i,j;
    n=read();
    for(i=1;i<=n;i++)a[i]=read(),maxn=max(maxn,a[i]);
    limit=log2(maxn);
    maxn=(1<<(limit+1))-1;
    for(i=n;i>=1;i--)add(a[i],i);
    for(i=0;i<=limit;i++)
        for(j=0;j<=maxn;j++)
            if(j&(1<<i))up(j^(1<<i),j);
    for(i=1;i<=n-2;i++){
        int now=0,nowmax=maxn-a[i];
        for(j=limit;j>=0;j--)
            if(nowmax&(1<<j)){
                int to=(now|(1<<j));
                if(f[to][1]>i&&f[to][2])now=to;
            }
        ans=max(ans,a[i]|now);
    }
    cout<<ans;
    return 0;
}
/*
3
1 5 15
*/

G. Polygons

题目链接

题意：给定n,k，求构造k个边数为[3,n]之间的正多边形，使其外切圆相同，问最少需要几个本质不同的点。(n,k<=1e6)

solution:有点厉害的构造题，发现一个贪心：一个x边形被选中当且仅当边数为其因子的多边形都被选完。我们考虑把所有多边形旋转至共同一点P，如果某个因子代价为cost，不选它而直接选x的代价会增加cost，即总代价没变但是选的多边形白少一个，显然是不优秀的。考虑所有因子选完后，选x新增的大家就是\phi(x)，考虑这个x边形把圆分成了几段等长弧：(\frac{1}{x},\frac{2}{x}...\frac{x}{x})*圆周长。如果\frac{y}{x}不是一个最简分数，约分后为\frac{z}{p}，那么在枚举p的时候就会算了答案，只有最简分数会贡献新的代价，故每个x新增代价\phi(x)。

这里有个很巧妙的实现，就是直接选出[1,n]中前k小的\phi，因为\phi(\text{x的因子})<=\phi(x)所以当我们真的取了\phi(x)的时候，它的因子的\phi一定都被取完了。

还有一点就是我们默认要取1边形和2边形(即1和\frac{1}{2})，当k>1的时候一定会取到2的倍数，所以这里算进去没有问题，但是当k=1的时候取x=3，没有把2边形算进去，所以需要特判。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=2100000;
int vis[N],prim[N],phi[N],cnt;
void pre(int n){
    register int i,j;
    phi[1]=1;
    for(i=2;i<=n;i++){
        if(!vis[i])prim[++cnt]=i,phi[i]=i-1;
        for(j=1;j<=cnt&&i*prim[j]<=n;j++){
            vis[i*prim[j]]=1;
            if(i%prim[j]==0){
                phi[i*prim[j]]=phi[i]*prim[j];
                break;
            }
            else{
                phi[i*prim[j]]=phi[i]*(prim[j]-1);
            }
        }
    }
}
int n,K;
long long ans;
int main(){
    register int i;
    n=read();K=read();
    if(K==1){
        cout<<3;return 0;
    }
    pre(n);
    sort(phi+1,phi+1+n);
    for(i=1;i<=K+2;i++)ans+=phi[i];
    cout<<ans;
    return 0;
}

H. Red Blue Tree

题意：给定一棵红蓝树，叶子有颜色，设一个点蓝儿子有b个，红儿子有r个，若b>=r+k则该点为蓝，否则为红。

支持以下操作：

1.询问某个点的颜色。

2.修改某个叶子的颜色。

3.修改k

(n,m<=1e5)

solution:咕咕咕。

8.28 树专题模拟赛

总结：

上了看T1，感觉自己写不出圆方树，觉得肝T2的边分治套虚树。

深吸一口气，感觉码量不少。

我好像没写过边分支诶，一直点分的来着。随手yy了一下，于是就有了这么个实现：找个重心，然后选重心的最大的儿子那条边。

之后发现随机数据都很卡常，感觉不大对劲，但是一直以为是两个log的缘故，于是一直想着去归并建虚树。知道最后20min突然意识到这样选边可能是O(n^2logn)的，造了个菊花就把自己卡掉了。

于是就很慌，感觉得多叉转二叉，又忘了多叉转二叉怎么写（-_-||）,然后突然小样例都过不了了。

最后10s赶紧一顿ctrl+z撤回到十万个版本之前。只测了小样例，望着5k代码感觉很虚。

码力还是不够强，本来写这种板子套板子套板子应该得2h写完的，但是总是因为变量名混用和一些细节调很久很久。

9.3 字符串专题赛

总结：

T1想到根号分治，然而最后结论是“小于根号暴力，大于根号放弃”，于是GG，还因为数组开小了爆了30pts。

T2没取模挂了10pts。

这种挂分简直是弱智行为。

9.5 计算几何专题赛

总结:

T2阅读理解题恶心人，T1半平面交一堆细节结果挂了，T3文件名写错了(弱智行为)。

Codeforces Round #582 (Div. 3)

总结：

弱智手速场，死于网进不去+手速不够，只写了6道。

Codeforces Round #583 (Div.1+Div.2)

比赛链接

总结：

肝D肝炸了，GG。还好手速够快1A了三道水题保住了rating。

ABC

弱智题不解释。

D. Treasure Island

题意:给定一张网格图，其中有些点是障碍，只能忘右/下走，问至少再放几个障碍使得S(1,1),T(n,m)不联通。

感觉很像[NOI2016网格]，答案肯定不超过2，就一直往割点方向想，然而有向图割点是什么东西？然后又觉得是个最小割，但是1e6不转对偶图可能很悬，转了又要判障碍来重新标号，感觉更恶心。结果写了一堆特判还是G了。

solution:BFS，因为不管怎么走到一个点的距离是一定的，如果不连通就是0，否则就是元素最少的那一层。另外，因为流量显然最大是2，所以网络流复杂度是对的。。。。。(不知道为什么考场上那么蠢)

E. Petya and Construction Set

题意：给定n个限制k_i，表示2i-1号点和2i号点距离为k_i，求构造一棵树满足所有要求。(k_i<=n)

solution:这个k_i<=n很关键。首先假设限制是不增的，构造一棵“毛毛虫”，即一条链上挂一些单个的点，不能挂长>1的链。

首先把所有2i抽出来形成长为n的链，按照限制从大到小排序，每次忘i+k_i-1号节点上扔一个2i-1。特别的，如果扔到了结尾，则把这个新的点加入链。因为k_i<=n所以一定每次都是有接的。

FG

看不懂。

H. Tiles Placement

题意：给定一棵树和k，求一种染色方案使得所有点颜色\in[1,k]且任意一条长为k的链颜色互不相同。

solution:首先拎出来直径，依次[1,k]染色，显然这是正确的，因为颜色直径互换互不影响，所以我们假设他们按顺序排列。然后每个点的颜色就都可以由直径或k级祖先递推出来了，如果一个点k级祖先在直径上且从直径两端的递推结果不同，那么无解。

为什么要拎直径呢？因为这样任何一个点的递推起点都会是直径往左或往右，只要每个点都满足关于直径的递推那么就是合法的，如果不是直径可以情况会很复杂。

欢乐模拟赛DAY5

总结：

感冒了。。。打到后面几乎自闭，大概就是T1的计算几何被各种乱搞搞过去了并且题解还咕咕咕了。

T1

题意：求最远异色点对。

KD-Tree可以搞，但是似乎K邻远搜索是没有复杂度保证的。。。于是我看着n<=3e5不敢写，最后写了个奇怪的算法，大概就是二进制分组之后搞出俩凸包，强行旋转卡壳，如果当前转不动就看看往前扫100能不能转动。

T2

咕咕咕

T3

咕咕咕

Codeforces Round #584

比赛链接

总结：

Rating+=3

不会做D，没得大众分，最后B被叉了全面崩盘。。。

AB

太水了。

C

题意：给定一个数列，将其分成两个子序列，使得这两个子序列拎出来再接起来之后是单调不降的。

solution:二分(原题值域过小可以枚举)，较小一段的最大值，然后把所有<mid的都接到第一个序列然后判合法性，然后把能接的mid都接上去，在判断第二个序列是否单调递增，复杂度O(nlogn)。

D

题意：有n个人，m种零食，每个人有两种爱吃的零食，一个人来的时候会吃掉所有他能吃且爱吃的零食，如果他至少吃掉一个那么他会开心，求最优入队顺序使得开心的人最多，输出最多开心人数。

solution:考虑点对(x,y)我们在(x,y)间连无向边，那么一个大小为x的连通块满意人数最多是x-1

，这是上界，因为第一个人要吃两个，构造方法是取该连通块的生成树，按照树的dfs序来进队。

E

题意：给定一个n*m的矩阵(n<=12,m<=1e5)，每次可以旋转某一列，最后答案为每一行的最大值之和，求最大答案。

solution:首先m有用的部分只会有n个，拎出来变成n*n的矩阵，然后做子集DP，0/1表示该行是否已经被某一列贡献过，每次n*2^{n}转移，总复杂度O(n^22^n)。

G1

G2还是看不懂诶。。

题意：给定一个数列，每个元素是一种颜色，求最少染多少次色使得原数列变成若干个同色段，另外如果一个颜色为x的点变了色，所有x颜色的点都要被染色，代价是这种颜色的点的个数。

solution:考虑一个“块”，它是一段区间[l,r]其中若存在x色点，那么所有x色点都要在该块中，我们可以扫一遍把数列分成若干块，每个块的答案就是len-max(\text{某颜色出现次数})，复杂度O(n)

G2

G1带修改。

Codeforces Round #585

比赛链接

总结：

Rating+=118

手速不够快，没有配备ACM式的健壮板子，导致看出F题正解却不能很快写出来，不过发挥还算可以喽。

C

题意：给定两个01串，每次可以将两个串的某两个字符进行交换（位置可以不同），问最少几次交换后两个串相等。

solution:首先00和11不管（00表示上下两串当前位置都是0，其它同理），然后2个01或者2个10是可以一次抵消的，一个01和一个10是可以花两次抵消的，无解就是01和10的奇偶性不同。

D

题意：两个人做填数游戏，可以填[0,9]，有两块板，有些格子已经填了，共有m(m是偶数)个格子还是空着的，两块板分别有n/2(n为偶数)个格子，B希望填完后两边和相等，W希望不等，W先手，双方轮流填，问谁必胜。

solution:首先若两边都有空着的，B可以直接抵消W的操作，否则B可以使得两次操作的增量和为9，只要判断抵消完后差值是否等于(剩余次数/2)*9即可。

E

题意：和Round 594一样是变成若干同色连续段，把染色换成交换相邻元素，问最少几次交换。

咕咕咕

F

题意：2-sat型限制，且每个元素是个区间，要求求出的元素集合代表的区间有交，求一个合法的元素集合。

solution:把区间按照左端点排序，然后每个点对L>=其右端点的元素连边，这里可以线段树优化连边，但是会被卡空间，换成后缀优化连边就过了，复杂度瓶颈是排序和二分查找的O(nlogn)，所以优化连边的方式不会影响时间复杂度。

0%