Cup
The 1st Universal Cup. Stage 0: Nanjing (Trial Contest)
比赛链接 题面懒得写了。 A. Stop, Yesterday Please No More 袋鼠移动相当于边界和洞移动。通过模拟可以得出:不考虑洞,移动后剩余袋鼠的矩形。以及假设洞在原点,移动后形成的轨迹形状。 枚举洞在哪个位置,多干掉的袋鼠就是两个几何图形的交。由于洞的移动轨迹较复杂,我们考虑让 ......
The 2nd Universal Cup. Stage 3: Binjiang
比赛链接 没做完。 A. Almost Prefix Concatenation 给定字符串 \(S,T\)。称一个串是好的,当且仅当可以通过修改不超过一个字符使其成为 \(T\) 的前缀。 称一个把 \(S\) 划分成 \(n\) 个非空子串 \(S_1,S_2,\cdots,S_n\) 的方案是 ......
2023 China Collegiate Programming Contest (CCPC) Guilin Onsite (The 2nd Universal Cup. Stage 8: Guilin)
题解: https://files.cnblogs.com/files/clrs97/2023Guilin_Tutorial.pdf Code: A. Easy Diameter Problem #include<bits/stdc++.h> using namespace std; const i ......
The 2nd Universal Cup Stage 13: Shenyang A
赛时没有过又为队友拖后腿了。 考虑原限制具有什么性质,可以发现 \(j\) 能接到 \(i\) 后面仅当 \(\text{max}_{S_{i}} \leqslant \text{max}_{S_{j}}\),而当 \(\text{max}_{S_{i}} = \text{max}_{S_{j}}\ ......
The 2nd Universal Cup. Stage 12- Hefei
E. Matrix Distances 因为行列的贡献是独立的,所以可以按照颜色分别统计 #include <bits/stdc++.h> using namespace std; #define int long long using i32 = int32_t; using vi = vecto ......
[XVI Open Cup GP of China] A. Graph Drawing
那确实是神仙题,阅读 jiangly 代码遂取之。 简要题意 给定一个点双联通的平面图,保证每个点的度数不超过 \(4\);具体地对于每个面将会按照逆时针顺序给出上面的顶点。现在要求把它画在无限大的网格上,要求边都平行于坐标轴,且彼此除了两端点外不接触。由于可能不能画出来,允许边进行任意的直角拐弯。 ......
XXII Open Cup named after E.V. Pankratiev, Grand Prix of IMO
Contest link: XXII Open Cup named after E.V. Pankratiev, Grand Prix of IMO。 M. Math 题意:给你一个长度为 \(n\) 的数组 \(a\),求有多少对 \((i,j)\) 满足 \(a_i^2+a_j\) 是完全平方数 ......
The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)
Preface 来场我最爱的SUA的题,而且恰逢南京站因此袋鼠题懂得都懂 然而好家伙点开题目一看怎么全是OP题,我们队没一个玩原的这下大输特输了 因此这场前中期可以说是崩完了,一个签到因为没判\(n=1\)从20min挂到150min,除此之外其它题目基本上都要挂上三四发 不过好在最后20min连着 ......
XXII Open Cup named after E.V. Pankratiev, Grand Prix of Daejeon 部分题解
省流:A、B、C、E、H、K、L。 D 和 I 之后可能会看心情补,剩下的题大概这辈子都不会做了。 A. Points 有两个由二维平面上的点组成的可重点集 \(U,V\)。如下定义 \(D(U,V)\): 当 \(U,V\) 中存在一个为空时,\(D(U,V) = -1\)。 否则 \(D(U,V ......
8VC Venture Cup 2016 - Final Round (CF627)
A. XOR Equation 最低位没有加法进位产生的影响,考虑从低位向高位 dp。 设 \(f_{i,0/1}\) 表示正在考虑第 \(i\) 位,前 \(i-1\) 位都满足限制,有无进位的方案数。 转移的时候枚举这一位两个数分别填 \(a,b\),\(x_i\) 表示 \(x\) 在二进制下 ......
VK Cup 2016 - Round 1 (CF639)
A. Bear and Displayed Friends 这是 Div2 的题,不写。 B. Bear and Forgotten Tree 3 这种东西怎么评蓝的? Description 给定 \(n,d,h\),构造一棵有 \(n\) 个点,直径为 \(d\),高度为 \(h\) 的树。 \ ......
PAT 甲级【1011 World Cup Betting】
import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { @SuppressWarnings("unchecked") publi ......
The 2nd Universal Cup. Stage 6: Warsaw L.Spectacle (思维)
大致题意: 给定n个玩家,每个玩家有一个战力值,安排 x (1 <= x <= n/2(向下取整))场游戏,每场游戏安排x对玩家对战,对于每一场游戏每个玩家只能参加一次对战,要求对于每x场玩家对战的两个玩家rating差的最大值尽可能小。 例如给定6个玩家战力值为10 13 14 20 100 10 ......
The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online (The 2nd Universal Cup. Stage 1: Qingdao)
Preface 好以后我就是SUA铁粉了,每次打SUA出的题感觉都很好,全程有事情干并且中档题很多很适合我们队这种比上不足的队伍打 不过yysy这场题目偏数据结构和图论方面比较重,而数学方向则不多,刚好撞上了我们队熟悉的地方,因此最后卡着时间过了9题 而且最近CF评测机不知道咋了,这场好多题光读入用 ......
The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG)
Preface 昨天下午16:30~21:30刚打完CCPC2021的广州,今天早上九点又开始打这场桂林,压力拉满了属于是 这场比起昨天那场良心太多了,开场还挺顺(虽然因为写Dijkstra偷懒TLE了四发),但开题啥的都是见一个会一个 中期虽然有点卡但因为祁神会了几何所以没有空机,然后再点完外卖后 ......
[QOJ6555] The 2nd Universal Cup. Stage 5. J : Sets May Be Good
先给 EI 磕三个 首先考虑用 \(n\) 个变量 \(x_1,x_2,\cdots,x_n\in\{0,1\}\) 表示第 \(i\) 个点选不选,那么导出子图的边数的奇偶性就是 \[f(x_1,x_2,\cdots,x_n)=\left(\sum_{(i,j)\in E}x_ix_j\right ......
The 2nd Universal Cup. Stage 5: Northern J Sets May Be Good
题解 我们考虑计算 \(\sum_{S\subseteq\{1,2,3,\cdots,n\}} (-1)^{cnt(S)}\),这里 \(cnt(S)\) 表示 \(S\) 集合的导出子图的边数。 我们记 \(x_i=[i\in S]\)。 我们考虑删掉 \(n\) 号点。 注意到如果 \(x_i\ ......
The 2nd Universal Cup. Stage 4: Taipei - I(状压DP)
目录I. Interval Addition I. Interval Addition 题意 给定一个长度为 n $(1\le n \le 23) $ 的数组 a。你可以进行一种操作:选择区间 \([l, r]\) 并给这个区间所有的数都加上一个任意的数。问你使得整个数组均为 0 所需的最小操作次数 ......
The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online (The 2nd Universal Cup
The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online (The 2nd Universal Cup. Stage 1: Qingdao) J - Press the Button \(1 \leq a, b, c, d \leq 10^6\) ......
The 2023 CCPC Online Contest (The 2nd Universal Cup, Stage 3: Binjiang)
题解: https://files.cnblogs.com/files/clrs97/CCPC-Online-2023-%E9%A2%98%E8%A7%A3.pdf Code: A. Almost Prefix Concatenation #include<cstdio> #include<cstr ......
The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong)
题解: https://files.cnblogs.com/files/clrs97/2022Hong_Kong_Tutorial.pdf Code: A. TreeScript #include <bits/stdc++.h> using namespace std; using LL = lon ......
Gym 104270 The 2018 ICPC Asia Qingdao Regional Programming Contest (The 1st Universal Cup, Stage 9: Qingdao)
A. Sequence and Sequence B. Kawa Exam 可以发现,对答案会产生影响的只有割边,把所有边双缩起来,然后就是一个森林。 考虑一个树的时候怎么做,就是对于每条边求出这条边两端的众数个数,考虑线段树合并,每次动态维护子树内的众数和子树外的众数。 #include<iost ......
qoj6735. Tree (The 1st Universal Cup. Stage 22: Shaanxi)
https://qoj.ac/contest/1287/problem/6735 考虑定一个根,然后把每个点的点权附属在父边权上,让每条边的边权变成一个 pair。 这样,一个符合条件的路径需要满足的条件是:路径内所有边的边权 pair 相同,以及 路径根节点(lca)的颜色符合。 对于当前树上每个 ......
Gym 104172 The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2Hong Kong)
A. TreeScript 令 \(f_u\) 表示 \(u\) 及 \(u\) 子树中的节点都创建的最小数量。 如果 \(u\) 只有一个儿子,那么可以将子树最后一个节点存储在当前的 \(u\) 中,答案就是 \(f_v\)。 若 \(u\) 有多个儿子: 令 \(t=\max\limits_{v ......
CF1162 Codeforces Round 557 (Div. 2) [based on Forethought Future Cup - Final Round]
CF1162A Zoning Restrictions Again 每个位置越高越好,暴力模拟即可。 #include<iostream> #include<cstdio> using namespace std; const int N=55; int n,h,m; int a[N]; int m ......
CF957 Codeforces Round 472 (rated, Div. 2, based on VK Cup 2018 Round 2)
CF957A Tritonic Iridescence 如果原序列中有两个相同的字符,显然不合法。 如果开头或者结尾为 ?,或者有两个连续的 ?,或者一个 ? 两边的字符不同显然合法。 否则一定不合法。 #include<iostream> #include<cstdio> using namesp ......
「解题报告」The 1st Universal Cup. Stage 3: Poland
大概按难度排序。签到题没写。 QOJ M. Minor Evil 有 \(n\) 个球与 \(k\) 个操作,初始所有球都是白色的。第 \(i\) 个操作为如果 \(a_i\) 是白色的,那么就将 \(b_i\) 染成黑色,否则什么都不做。你可以选择每个操作执行或不执行,但是不能改变操作之间的相对顺 ......
The 2nd Universal Cup. Stage 2- SPb
A. Mixed Messages dp[i][j]表示前i位,选择\(j\)个移动到一起的最小花费。 #include<bits/stdc++.h> using namespace std; #define int long long constexpr int inf = 1E9; int32_ ......
The 2nd Universal Cup. Stage 2: SPb
链接:https://contest.ucup.ac/contest/1356 A. Mixed Messages #include "bits/stdc++.h" using namespace std; using i64 = long long; int main() { ios::sync_ ......
洛谷 AT_maximum_cup_2018_a フィギュアスケート界の貴公子埼大選手 の 题解
这道题是一道水题,所以你的代码很可能与我相似或相同,如果你的代码出现了问题,你很可能在我的题解里找出答案。 这道题大概思路是一旦 $10$ 秒后运动员会接触到毛绒玩具,那么就加上在这个点上毛绒玩具的数量。 但是! 这道题有一道巨坑的点!由于这道题比较远古,所以说你即使是正解,你也要在输出完答案后换行 ......