最后的赠礼。
CodeForces 1770
打得不怎么好，只做了 ， 有一定思路但是还是靠 巨佬贺过去的。后面几道题都比较长没看。
A. Koxia and Whiteboards
题目简介
题目来源：
评测链接：https://codeforces.com/contest/1770/problem/A
形式化题意：给定一个长度为 的序列 ，有 个数 ，每次必须使用 代替任意一个 ，求 次操作之后最大化的 。多测。
数据范围：
考虑每一次用 去替代最小的 ，时间复杂度 。这是最朴素的模拟做法。也可以将题目转换为，从一个长度为 的序列中选择最大的 个，其中至少包含 个 ，这种做法的时间复杂度为 。也没快多少。
B. Koxia and Permutation
题目简介
题目来源：
评测链接：https://codeforces.com/contest/1770/problem/B
形式化题意：对于一个长度为 的序列 ，定义其 权值为一个长度为 的序列 ， 的计算方式如下： ，而这个序列的权值 ，求对于一个 的全排列 ，构造一个序列使得 最小， ，多测。
数据范围：
有意思的构造题，考虑到 的计算关系到 中的极值，我们就要让其中一个极值在被计算的时候能把其它的极值给消耗掉，使其不会成为另外一些区间内被取到的极值。
我们猜测 ，那我们就让 两个数分别位于一个区间 的两端，当 的时候两端一定是极值，这样的话，位于其中的极值就会被 给消耗掉。但随着 向右推进的时候，也就是 不会被取到的地方，可能 就会再次被取到，我们就考虑将 提出来与其中和。
这样的话，我们就有一个构造的思路了，下面以 为例：
容易发现，任意相邻 个数的极值和都不会超过 。
维护双指针初始分别位于 ，以 为周期推进 。
C. Koxia and Number Theory
题目简介
题目来源：
评测链接：https://codeforces.com/contest/1770/problem/C
形式化题意：给定一个长度为 的序列 ，问是否存在正整数 使得 ，具体来讲，使得整个序列都加上一个非零整数 后两两互质，多测。
数据范围：
考虑 的性质，也是欧几里得 解法的第一步： ，那么我们就可以这样考虑： ，这样的话，可以使得 的一个数固定，会使得计算简洁很多。
可以考虑开一个桶 ，表示是否存在 余 的数存在。
那我们应该如何判断有无解，对于每一个 ，如果只存在一对数 满足 的话，则无解。也就是当只有 的时候无解。这样的话，无论 的取值为多少，都会使得有一组解会在 的时候不互质。
AC 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
| read(Test);
while(Test--)
{
bool flag=0;
read(N);
int M=N<<1;
for(int i=1;i<=N;++i) read(a[i]);
std::sort(a+1,a+N+1);
for(int i=2;i<=N;++i)
if(a[i-1]==a[i]){ flag=1;break; }
if(flag){ puts("NO");continue; }
for(int i=1;i<=M;++i)
for(int j=0;j<=M;++j)
T[i][j]=0;
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
{
if(i==j) continue;
ll x=std::abs(a[i]-a[j]);
for(int k=2;k<=M;++k)
if(x%k==0) T[k][a[i]%k]=1;
}
for(int i=2;i<=M;++i)
{
ll sum=0;
for(int j=0;j<i;++j) sum+=T[i][j];
if(sum==i){ flag=1;break; }
}
if(flag) puts("NO");
else puts("YES");
}
|
后面都不会了，题也没读，有机会再做。
LGR - 127
全靠猜结论，喜提瞬时最高 rk3 。
A. Jump
题目简介
题目来源：
评测链接：https://www.luogu.com.cn/problem/P8918
形式化题意：给定一个 ，问是否存在一组解 使得 ，也就是将 拆分成 ，多测。
数据范围：
良心的出题人给了我们 组样例，我们可以大胆猜结论。
首先， 必然存在，所以当 为偶数时必然无解，样例也应证了我们的猜测说不定正确。然后，容易发现，当我们已经填到了第 位时， 的所有奇数都是可以到达的。因为我们填了第 位就相当于是把第 位左移了第 位，全部为 之后所能到达的最大值也是 ，而根据二进制填充，无论舍弃哪一位，都可以使得 的任意数都被到达（本题不可舍弃末位，所以偶数无解）。
那么，答案就呼之欲出了：
时间复杂度可以是 也可以是 ， 嘛，主要是拼手速和算力。
B. Message
题目简介
题目来源：
评测链接：https://www.luogu.com.cn/problem/P8919
形式化题意：一共有 条信息，给定一个长度为 的 串 ，并指定 条特殊信息 ，每一次操作可以删除一条信息，问最少的操作次数使得 。
数据范围：
由于限定了 巨大的数据范围，所以估计是个线性的贪心思路。可以考虑，如果我们要使得第 条特殊信息不受惩罚，可以选择 之前的任意一条信息删除，但这个操作都可以用直接删除 代替，所以我们的贪心决策——只删除特殊信息。
有了这一个限制那就简单得多了，我们从前往后搜，记录一个 表示当前我们已经删除了多少条信息了，然后每次考虑 是否为 来考虑删不删除。
关键代码部分
1
2
3
4
5
6
7
8
| read(N,M);
scanf("%s",f+1);
for(int i=1,x;i<=N;++i)
{
read(x);
if(f[x-delta]=='1') ++delta;
}
write(delta);
|
C. Variance
题目简介
题目来源：
评测链接：https://www.luogu.com.cn/problem/P8920
形式化题意：有两个长度为 的序列 ，要求构造一个序列 ，使得 的方差最大，求最大方差 。
数据范围：
特殊条件：
刚开始根本没啥思路，以为是一个什么神仙 ，然后就看见了那两个特殊条件，抽象一下，把 和 放到平面直角坐标系里，可以抽象成两条直线，但 始终在 之上。
然后偶然搜方差公式的时候（主要不知道那个 怎么转化，我太菜惹），看见一句话：
一个序列越分散，差值越大，方差越大。
那么，显然， 本身都是单调递增序列，而 恒成立的事实告诉我们一个假设：我们把 切分成前后两部分，使得：
也就是既定一个 ，其前取 ，其后取 。信念告诉我们这种做法是对的。
然后说说这个 应该怎么优化。
首先列出方差的公式：
然后我们 之后化简：
我们记录一个 ，则：
这样就很好计算了，我们对于 分别维护一个前缀（后缀）和，枚举中结点 ，然后记录答案，时间复杂度 。需要开 __int128_t 。
AC 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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using int128=__int128_t;
const int MAXN=1e6+10;
int N;
int128 a[MAXN],b[MAXN],c[MAXN];
int128 ans,Suma[MAXN],Sumb[MAXN];
int128 Suqa[MAXN],Suqb[MAXN];
inline int128 calc(int x)
{
int128 sum=Suma[x]+(Sumb[N]-Sumb[x]);
int128 suq=Suqa[x]+(Suqb[N]-Suqb[x]);
return N*suq-sum*sum;
}
int main()
{
read(N);
for(int i=1;i<=N;++i) read(a[i]),Suma[i]=Suma[i-1]+a[i],Suqa[i]=Suqa[i-1]+a[i]*a[i];
for(int i=1;i<=N;++i) read(b[i]),Sumb[i]=Sumb[i-1]+b[i],Suqb[i]=Suqb[i-1]+b[i]*b[i];
ans=N*Suqb[N]-(Sumb[N]*Sumb[N]);
for(int i=1;i<=N;++i) checkMax(ans,calc(i));
write(ans);
return 0;
}
|
D. Triangulation
题目简介
题目来源：
评测链接：https://www.luogu.com.cn/problem/P8921
形式化题目：给定一个正 多边形的三角剖分，转化为一个有 个结点， 条边的无向图。求一种构造这张图的生成树使得每一个结点的度数为奇数。
数据范围：
考场上并没有想到，两场都被构造卡掉惹。可惜没有 。
根据样例以及 以及排行榜可知——当 为奇数时无解。
这个的证明其实也是很简单的，对于一张图的生成树一共会有 条边，所以度数和应该为 ，是偶数。但如果要满足要求的话，每一个结点度数应该是奇数，一共有 个结点，也是奇数，计算得出的度数和应当为奇数，与生成树性质相悖，所以无解。
然后考虑如何构造。
由于给定的图是一个三角剖分，那我们也可以从三角形的方面来考虑生成树。如果我们当前已经拥有了一个内部封闭的 边形，然后在这个图形的外围再添上一个三角形，对已知结点的度数会做出什么改变。
会新增一个度数为 的结点，并改变其相连的那 个结点的奇偶性，这是显然的。我们保证了原先的图是一个满足要求的生成树结构，所以我们只需要考虑现在被改变了的三个结点。
我们试图简化这个问题，求问是否存在一种构造方案使得每个结点的度数都不超过 ，这样的话，我们可以构造出的生成树是一棵二叉树。
那我们按以下操作来整：
- 如果结点 的两个子结点都有偶数个三角形，则 与其父结点相连；
- 如果结点 的两个子结点都有奇数个三角形，则 充当外添三角形的外添结点。
- 如果结点 的两个子结点一奇一偶，则让 与奇子结点充当外添三角形的内接结点。
按照这样的话，至少在执行这一步的是正确的。对于实现，我们可以分为两步走。
第一步构造出对偶图，给出 个长度和为 的数列全排列排序，用计数排序实现，时间复杂度 ，求出每一个结点的前驱后继。可以放 个哈希表记录每一个结点在 std::vector 中的下标。
第二步区分三角形的边，按照一定顺序排列。
AC 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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e5+10,MAXM=1e6+10;
int N,M;
struct G
{
int next,to;
}Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
Edge[++Total]=(G){Head[u],v};Head[u]=Total;
Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
std::vector<int>G[MAXN];
std::unordered_map<int,int>Loc[MAXN];
#define lc G[u][Loc[w][u]+1]
#define rc G[v][Loc[w][v]-1]
int dfsTree(int u,int v,int w)
{
int lz=0,rz=0;
if(!(w==u-1||w==N&&u==1)) lz=dfsTree(u,w,lc);
if(!(w==v+1||w==1&&v==N)) rz=dfsTree(w,v,rc);
if((lz+rz)&1)
{
if(lz&1==1) write(u,' ',w,'\n',u,' ',lc,'\n');
else write(v,' ',w,'\n',v,' ',rc,'\n');
}
else if(lz&1==1) write(w,' ',lc,'\n',w,' ',rc,'\n');
return lz+rz+1;
}
int main()
{
read(N);addEdge(1,N);
for(int u=2;u<=N;++u) addEdge(u-1,u);
for(int i=4,u,v;i<=N;++i){ read(u,v);addEdge(u,v); }
if(N&1) return puts("-1"),0;
for(int x=1;x<=N;++x)
for(int e=Head[x],v;e;e=Edge[e].next)
{
v=Edge[e].to;
if(v>x) continue;
Loc[x][v]=G[v].size();
G[v].push_back(x);
}
for(int x=1;x<=N;++x)
for(int e=Head[x],v;e;e=Edge[e].next)
{
v=Edge[e].to;
if(v<x) continue;
Loc[x][v]=G[v].size();
G[v].push_back(x);
}
write("1 2\n");
dfsTree(1,2,G[1][1]);
return 0;
}
|
后面的 和 事神仙 和多项式，所以不做。