Codeforces汇总

最近感觉自己又行了。就很想打 Codeforces,这里罗列一下从 2020/05/16 开始提交的(不是特别水的)AC代码。想有生之年上一次黄,先定个小目标上个1900!茶茶白加油!

图论很久没搞了,基本都忘了导致很多题没法做,图论还是一个特别强的工具。为什么没有图论的STL?

技巧:

  • 不要急着写代码!!!不要为了上分就不交题了!!!
  • 计算式要列的清晰,并且最好是好输入的。
  • 仔细读完题目有明显思路赶紧写,然后要细心把公式列出来不要跳,再去写代码,过了再看别的题
  • caseInput.cpp, nocaseinput.cpp模板先建好
  • A~F.cpp先创建好,用好 fopen 但是记得关
  • m2.codeforces.ml 打开所有题
  • 推荐在submit界面交题目(不推荐选择文件,有时候网慢,很可能没交上题)。
  • 另外一个浏览器(或另一个主界面)看一下关注Standing,不要把简单问题想复杂了
  • 不要写这样的代码:if(a[j++]),while(a[j++])

题集

按照提交时间排序

1355B :贪心模仿加法进位。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];

int getans(int n){
int ans = 0,x=0;
for(int i=1;i<=n;++i){
x+=a[i];
ans+=x/i;
x%=i;
}
return ans;
}

int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,x;
cin>>cas;
while(cas--){
cin>>n;
for(int i=1;i<=n;++i) a[i]=0;
for(int i=0;i<n;++i){
cin>>x;
++a[x];
}
cout<<getans(n)<<endl;
}
return 0;
}

1354C :计算包含单位正$n$边形的最小正方形的边长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);

int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n;
cin>>cas;
cout.precision(10);
while(cas--){
cin>>n;
if(n&1){
double x = sqrt(1-cos((n/2)*pi/n));
double y = sqrt(1-cos((n/2+1)*pi/n));
cout<<(x+y)/2/sin(pi/2/n)<<endl;
}else cout<<1.0/tan(pi/2/n)<<endl;
}
return 0;
}

1354D :模拟操作: 加数字或删除第$k$小的数。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int s[N], Size;

int lowbit(int n) {
return n & (-n);
}
void add(int id, int p) {
while (id <= Size) {
s[id] += p;
id += lowbit(id);
}
}
int sum(int id) {
int r = 0;
while (id) {
r += s[id];
id -= lowbit(id);
}
return r;
}
int find(int k) {
int l = 0, r = Size;
while (r>l) {
int m = (l + r) >> 1;
if (sum(m) >= k) r = m;
else l = m+1;
}
return r;
}
void del(int k) {
add(find(k), -1);
}

int main() {
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int q, x;
while (cin >> Size >> q) {
for (int i = 1; i <= Size; ++i) s[i] = 0;
for (int i = 1; i <= Size; ++i) {
cin >> x;
add(x, 1);
}
while (q--) {
cin >> x;
if (x > 0) add(x, 1);
else {
del(-x);
}
}
int ans = find(1);
cout <<(sum(ans)>0?ans:0)<< endl;
}
return 0;
}

1354F :经典DP问题

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
#include<bits/stdc++.h>
using namespace std;
const int N = 102;
int dp[N][N];
bool isin[N][N],chose[N];
using node = tuple<int,int,int>;
node q[N];
void getans(int n,int k){
for(int i=1;i<=n;++i){
dp[i][0] = dp[i-1][0]+(k-1)*get<2>(q[i]);
for(int j = 1;j<i && j<=k;++j){
int x = dp[i-1][j]+(k-1)*get<2>(q[i]);
int y = dp[i-1][j-1]+(j-1)*get<2>(q[i])+get<1>(q[i]);
if(x>y){
dp[i][j] = x;
isin[i][j] = false;
}else{
dp[i][j] = y;
isin[i][j] = true;
}
}
if(i<=k){
dp[i][i] = dp[i-1][i-1]+(i-1)*get<2>(q[i])+get<1>(q[i]);
isin[i][i] = true;
}
}
for(int i=n,j=k;i;--i){
if(isin[i][j]){
chose[i]=true;
--j;
}else{
chose[i]=false;
}
}
}

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,k,a,b;
cin>>cas;
while(cas--){
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a>>b;
q[i] = {i,a,b};

}
sort(q+1,q+n+1,[](const node & x, const node & y){
return get<2>(x)<get<2>(y);
});
cout<<(2*n-k)<<endl;
getans(n,k);
int last = 0;
for(int i=1;i<=n;++i){
if(chose[i]){
if(++last == k){
last = i;
break;
}
cout<<get<0>(q[i])<<" ";
}
}
for(int i=1;i<=n;++i){
if(!chose[i]) cout<<get<0>(q[i])<<" "<<-get<0>(q[i])<<" ";
}
cout<<get<0>(q[last])<<endl;
}
return 0;
}

1345F :经典二分,利用二阶偏导(离散偏导,即增量)是常量!

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
LL k,x;
while(cin>>n>>k){
vector<LL> q;
for(int i=0;i<n;++i){
cin>>x;
q.push_back(x);
}
auto get = [](LL x ,LL mx){
LL l=0,r=x-1;
while(l<=r){
LL m=(l+r)>>1;
if(x-m*(m+1)*3 == mx) return make_pair(m,m+1);
if(x-m*(m+1)*3 > mx) l = m+1;
else r = m-1;
}
return make_pair(l,l);
};
LL l = -3e18-3e8, r = 1e9;
while(l<=r){
LL m = (l+r)>>1,x=0,y=0;
for(auto &i:q){
auto tmp = get(i,m);
x+=tmp.first;
y+=tmp.second;
}
if(x>k) l = m+1;
else if(y<k) r = m-1;
else{
y-=k;
for(auto &i:q){
auto tmp = get(i,m);
//cout<<endl<<tmp.first<<" "<<tmp.second<<endl;;
if(tmp.first<tmp.second && y-->0){
cout<<tmp.first<<" ";
}else{
cout<<tmp.second<<" ";
}
}
cout<<endl;
break;
}
}
}
return 0;
}

1325B:Set的用法举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,x;
cin>>cas;
while(cas--){
cin>>n;
set<int> q;
for(int i=0;i<n;++i){
cin>>x;
q.insert(x);
}
cout<<q.size()<<endl;
}
return 0;
}

1325D:(异或 )位运算:判断是否有$n$ 个数,异或和为$u$, 和为$v$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
LL u,v;
while(cin>>u>>v){
if(u>v||((v-u)&1)){
cout<<-1<<endl;
}else if(u == v){
if(u) cout<<1<<endl;
cout<<u<<endl;
}else{
v = (v-u)>>1;
if(u&v) cout<<3<<endl<<u<<" "<<v<<" "<<v<<endl;
else cout<<2<<endl<<u+v<<" "<<v<<endl;
}
}
return 0;
}

注意到 $a+b = a \wedge b + 2(a\&b)$,并且 $(a \wedge b) \& (a\&b) = 0$ 当且仅当 $ab=0$

1358D:给定区间最值问题,但是可以写的很漂亮

注意到区间最值一定在左或者右端点达到局部最大值(极值)

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 4e5+102;
int n,n2;
LL a[N],b[N],s[N];
LL f(LL x){
return ((x+1)*x)>>1;
}
LL sumx(LL x){
int it = lower_bound(b,b+n2,x) - b;
// 这里注意是it, 比赛的时候没减,搞得怀疑人生
return s[it-1]+f(x-b[it-1]);
}
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
LL d;
cin>>n>>d;
n2=n<<1;
for(int i=0;i<n;++i){
cin>>a[i];
a[i+n] = a[i];
}
b[0] = a[0];s[0] = f(a[0]);
for(int i=1;i<n2;++i){
b[i]=b[i-1]+a[i];
s[i]=s[i-1]+f(a[i]);
}
LL ans = 0;
for(int i=0;i<n;++i){
ans = max(ans,sumx(b[i]+d-1)-s[i]+a[i]);
}
for(int i=n;i<n2;++i){
ans = max(ans,s[i]-sumx(b[i]-d));
}
cout<<ans<<endl;
return 0;
}

1358E:很有意思的数据处理题目,官方题解

注意到如果$k$ 满足答案,则$2k$也满足,所以不妨设$k> \lfloor \frac{n}{2} \rfloor$,另一方面题目中要求若$i> \lceil \frac{n}{2} \rceil$,$a_{i} = x$

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5+5;
LL a[N],s[N],m[N];
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
cin>>n;
int n2 = (n+1)>>1;
for(int i=1;i<=n2;++i){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
LL x;
cin>>x;
for(int i=n2+1;i<=n;++i){
a[i]=x;
s[i]=s[i-1]+x;
}
for(int i=1;i<=n2;++i){
m[i+1] = min(m[i],x*i-s[i]);
}
for(int k=n2;k<=n;++k){
if(s[k]+m[n-k+1]>0){
cout<<k<<endl;
return 0;
}
}
cout<<-1<<endl;
return 0;
}

1359C: 读题被坑…(反正就是倒冷热水接近给定温度)

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
int h,t,c;
cin>>h>>c>>t;
h-=c;t-=c;
if(h>=2*t){
cout<<2<<endl;
}else{
LL n = (h-t)/(2*t-h);
auto f = [](LL n,int h,int t){
return (n+1)*(2*n+3)*h+(2*n+1)*(n+2)*h>(2*n+1)*(2*n+3)*t*2;
};
if(f(n,h,t)) ++n;
cout<<2*n+1<<endl;
}
}
return 0;
}

然后对于奇数项,单调递减趋于平均问题,然后判断的时候转化成整数的判断

1359D:线段树,但是由于数据特殊,可以不用线段树

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5+5;
int a[N];
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(NULL);
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
int ans=0;
for(int m=1;m<=30;++m){
int suml =0,sum=0,maxa = -31;
for(int i=1;i<=n;++i){
if(a[i]>m){
sum = suml = 0;
maxa = -31;
}else{
sum+=a[i];
//这里取全局最大是因为,我们枚举了最大值的可能
maxa = max(maxa,a[i]);
ans = max(ans,sum-suml-maxa);
//相当于前面是全0的部分删了!并且这样不会避免中间负的情况
suml = min(sum,suml);
}
}
}
cout<<ans<<endl;
return 0;
}

注意到 $-30<a_i$<30$

1359E:找到公式后就是模素数组合数

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
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
const int N = 5e5+2;
const LL M = 998244353;
LL inv[N],frac[N];
LL powmod(LL x, LL n, LL p) {
LL r=1;
while(n) {
if(n&1) r=r*x%p;
n>>=1;
x=x*x%p;
}
return r;
}
void init(){
frac[0]=inv[0]=1;
for(int i=1;i<N;++i){
frac[i] = frac[i-1]*i%M;
}
inv[N-1] = powmod(frac[N-1],M-2,M);
for(int i=N-2;i;--i){
inv[i] = inv[i+1]*(i+1)%M;
}
}
LL C(int n,int m){
if(n<m) return 0;
if(n==m||m==0) return 1;
return frac[n]*inv[m]%M*inv[n-m]%M;
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(NULL);
int n,k;
cin>>n>>k;
init();
LL ans = 0;
for(int i=1;i<=n;++i){
int x = n/i;
if(x<k) break;
ans += C(x-1,k-1);
}
cout<<ans%M<<endl;
return 0;
}

先考虑$k=2$ 的情况知道 $a_1|a_2$,然后发现对于任意$k$,仅需 $a_1|a_i$ 即可。

补充和强化知识

  • 需要补充:图论
  • 需要强化:二分法,动态规划,代码能力,找公式速度,读题速度。
  • 需要模板:高斯消元法C++版。

OI-wiki 复习和学习算法,在 codeforces 训练算法和编程能力。

图论

图的存储

  • 直接tuple类型数组直接存边
  • 邻接矩阵(只能用于无重边的图)
  • 链式前向星(推荐,优雅)

前两种都很基础,我们一般用链式前向星来存储,oi-wiki上的例子

1
2
3
4
5
6
7
8
9
10
11
// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v) {
nxt[++cnt] = head[u]; // 当前边的后继
head[u] = cnt; // 起点 u 的第一条边
to[cnt] = v; // 当前边的终点
}

// 遍历 u 的出边
for (int i = head[u]; ~i; i = nxt[i]) { // ~i 表示 i != -1
int v = to[i];
}

但是,自从我会C++17后,我们可以这么写(优雅)

1
2
3
4
5
6
7
8
9
10
11
12
13
// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v, int w){
edge.push_back({head[u],v,w});
head[u] = ++cnt;
}
// 遍历 u 的出边
void vis(int u){
for (int i = head[u]; ~i;) { // ~i 表示 i != -1
auto [t,v,w] = edge[i];
cout<<u<<" "<<v<<endl;
i=t;
}
}

存双向边时 i ^ 1 即是 i 的反边。

DFS(深度优先搜索)

递归的调用自己,要用到

在 Windows 上,通常的方法是在 编译选项 中加入 -Wl,--stack=1000000000

在 Linux 上,通常的方法是在运行程序前 在终端内 执行 ulimit -s unlimited (WSL下无法设置可惜)

BFS(广度优先搜索)

queue保存节点,先进先出。队列为空。

priority_queue 保存节点,可用于优化Dijkstra算法。

无根树的Prufer序列

$n$个节点的无根树和长度为$n-2$,数值在$1 \to n$ 的序列有一一对应

构造方式:删除编号最小的叶子节点,并记录它的父节点。

之前在猫咪状态数 中有记录过,代码可以见这里

有根树的Euler序列

通过DFS,可以把一个有根树转化成长度为$2n-1$,数值在$1 \to n$ 的序列。

最近公共祖先简称 LCA(Lowest Common Ancestor)

  • 策略1:其中一个节点一直往上标记父辈到根,然后另一个节点往上找父辈,直到找到首次被标记过的节点
  • 策略2:标记没个节点的深度,深度高的往上到同一层,然后一起一步步上去,直到是公共节点
  • 策略3:做一次DFS得到Euler序列,然后就变成找区间最小值问题了(可以使用线段树)
  • 其他:倍增(记录fa[u][i]:表示u的第$2^i$祖先),Tarjan 算法,动态树

有向图的拓扑排序之Kahn算法

给定有向图,然后把节点按照顺序排列,使得任意有向边的起点在终点前。

做法:维护一个入度为0的节点集合,一次删除节点(加入拓扑序列),删除的时候它连接的所有点入度减1,为0就加入节点集合。

一个有向图是无环图,当且仅当它存在拓扑排序。

有向图最小生成树的Kruskal算法(更推荐)

把边排序,每次加入最短边,如果加入不构成环,就加入,否则不加。

需要(带路径压缩)并查集维护。

(有向图)最小生成树的Prim算法

讲节点分为两类:已加入和未加入。每次从未加入的节点中找一个和已知节点最近的边,然后加入该节点,连接这条边。(初始加入节点任意)

(有向图)的次小生成树(下次一定)

最小树形图(有向图的最小生成树)的朱刘算法

  1. 找入度为0的root节点(唯一,否则不存在最小树形图)
  2. 除了root节点外,找出每个点的最小入边
  3. 检测是否有环,有环则缩点,更新新节点的距离
  4. 重复上述过程

强连通分量的Kosaraju 算法

Kosaraju 算法依靠两次简单的 DFS 实现。

第一次 DFS,选取任意顶点作为起点,遍历所有未访问过的顶点,并在回溯之前给顶点编号,也就是后序遍历。

第二次 DFS,对于反向后的图,以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点,选取标号最大的,重复上述过程。

两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为O(m+n)。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// g 是原图,g2 是反图
void dfs1(int u) {
vis[u] = true;
for (int v : g[u])
if (!vis[v]) dfs1(v);
s.push_back(u);
}

void dfs2(int u) {
color[u] = sccCnt;
for (int v : g2[u])
if (!color[v]) dfs2(v);
}

void kosaraju() {
sccCnt = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i]) dfs1(i);
for (int i = n; i >= 1; --i)
if (!color[s[i]]) {
++sccCnt;
dfs2(s[i]);
}
}

我们可以将一张图的每个强连通分量都缩成一个点,然后这张图会变成一个有向无环图

强连通分量的Tarjan算法

二分图的匈牙利算法:dfs硬搞

Kirchhoff 矩阵树定理:解决了一张图的生成树个数计数问题

耻辱记录

  • 2020/5/24 水题竟然也能被卡,傻子吧我!
  • lower_bound 坑了,也怪自己,lower_bound(a.begin(),a.end(),x)-a :对于单调递增的序列,返回第一个大于等于x的序号。upper_bound 同理。
欧尼酱,人家想喝可乐!