文章列表

# AtCoder Beginner Contest 418 比赛链接 # A - I'm a teapot 模拟即可 #include<bits/stdc++.h>#define int long long#define in inline#define ri register#define _123hh2 0using namespace std;in int read(){ int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0')...

# 分块 分块是一种将一些需要维护的数据划分为一些小块后，预处理每个小块的信息从而实现较暴力更优的复杂度的一种思想，优化后的复杂度一般是 O(nn)O(n \sqrt{n})O(nn​)​ 的 接下来从最简单的求区间和来看看分块的实现方法 对于一个长度为 sss 的序列 aaa，我们将这个序列分成连续的大小相同的 bbb 块 注意最后一个块可能并不完整，但这并没有多大影响 那么我们可以维护每个块的所有元素之和，这样我们在查询区间 [l,r][l,r][l,r] 的和时，就可以快速计算 如果 lll 和 rrr 在一个块中，那么直接暴力求和即可，复杂度最坏为...

# Entangled Coins 题目链接 首先我们简化题意 现有一数 xxx ，它的可达范围是 [0,n][0,n][0,n]​ 你可以进行任意多次如下操作： 你可以选择一数 a(0≤a≤k)a(0 \leq a \leq k)a(0≤a≤k) ，使得 xxx 变为 x+k−2ax+k-2ax+k−2a 且不能超过 xxx 的可达范围 问将数 xxx 变为数 yyy 的最小操作次数，若无解则输出 -1 不难注意到 kkk 的奇偶性决定了 xxx 的变化情况，所以我们自然地按 kkk 的奇偶性进行分类讨论 当 kkk 为偶数时，操作任意多次后，xxx 的奇偶性是不变的 当...

# 牛客周赛 Round 102 比赛链接 # A 小红的好 01 串 只有两种情况，要么以 1 开头要么以 0 开头 #include<bits/stdc++.h>#define int long long#define in inline#define ri register#define _123hh2 0using namespace std;in int read(){ int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0')...

# 光速幂 在同一底数 aaa 和同一模数 ppp 的情况下，大量询问 axmod  pa^x \mod paxmodp 的时候，可以使用光速幂做到 O(p)O(\sqrt{p})O(p​) 预处理， O(1)O(1)O(1) 查询 我们选定一个数 xxx 并处理 a0,a1,a2……axa^0,a^1,a^2 …… a^xa0,a1,a2……ax 和 a0×x,a1×x,a2×x……a⌈px⌉×xa^{0 \times x},a^{1 \times x},a^{2 \times x}……a^{\lceil \frac{p}{x}...

# 牛客周赛 Round 101 比赛链接 # A 题解的 token 计算 调用自带的 logloglog 函数，默认以 eee 为基底 #include<bits/stdc++.h>#define int long long#define in inline#define ri register#define _123hh2 0using namespace std;in int read(){ int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0')...

# AtCoder Beginner Contest 416 比赛链接 # A - Vacation Validation 模拟 #include<bits/stdc++.h>#define int long long#define in inline#define ri register#define _123hh2 0using namespace std;in int read(){ int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0')...

# CF1899F Alex's whims 题目链接 # 题目大意 要求你构造一课 nnn 个点的树，并且给出 qqq 次询问使得 每次询问前可以对这棵树断开一个边并于其他一个点相连使得操作后图的仍为树（条件 1） 树中存在一条简单路径长度等于每次询问给出的数 xxx（条件 2） 若某次询问可以不进行断边重连操作，则输出 -1 -1 -1 ，否则输出 u,v1,v2u,v_1,v_2u,v1​,v2​，其中 u和v1u和v_1u和v1​ 是原先相连的点，u和v2u和v_2u和v2​ 是操作后相连的点 # 思路 由题意可知，构造出的这个树必定满足条件 2，假设给出的 xxx 等于...

# CF1898D Absolute Beauty 题目链接 # 题目大意 给定两个长度相等的数组 a,ba,ba,b，你可以最多交换一次 bi,bj(1≤i<j≤n)b_i,b_j(1 \leq i < j \leq n)bi​,bj​(1≤i<j≤n) 的值，使得 ∑i=1n∣ai−bi∣\sum\limits_{i=1}^{n}|a_i -b_i|i=1∑n​∣ai​−bi​∣ 的值最大 # 思路 ∣ai−bi∣|a_i - b_i|∣ai​−bi​∣ 可以具体为在数轴上的一条左端点为 aia_iai​，右端点为...

# CF1898C Colorful Grid 题目链接 # 题目大意 给定一个有 nnn 条水平线和 mmm 条垂直线组成的网格，水平线从上到下用 1−n1-n1−n 编号，垂直线从左到右用 1−m1-m1−m 编号，(x,y)(x,y)(x,y) 表示第 xxx 个水平线和第 yyy 个垂直线的交点，当且仅当 ∣x1−x2∣+∣y1−y2∣=1|x_1-x_2| + |y_1-y_2| = 1∣x1​−x2​∣+∣y1​−y2​∣=1 时，两点 (x1,y1)(x_1,y_1)(x1​,y1​) 和 (x2,y2)(x_2,y_2)(x2​,y2​)...