ICPC
2019-2020 ICPC, NERC, Northern Eurasia Finals
组队打 \(\rm ICPC\),队友是 \(\rm fishead\) 和 \(\rm Liang_Yusong\)。 只过了五个题,还是太菜了。 开局 \(6 \min\) 我先把 \(\rm B\) 切了,然后 \(\rm LYS\) 在 \(34 \min\) 时过了 \(\rm E\)。 ......
ICPC2020 Shanghai R E题
传送门 description 给定 \(n,k\),求有多少个 \(n\) 的排列满足 \(\forall i\in[k+1,n],\min\limits_{j=i-k}^{i-1} a_j < a_i\)。 \(n,k\leq 10^7\) solution 设 \(f_i\) 表示对于给定的 ......
P9821 [ICPC2020 Shanghai R] Sum of Log
原题链接 题意,求: \[\sum_{i=0}^{X}\sum_{j=[i=0]}^{Y}[i\&j=0]\lfloor\log_2(i+j)+1\rfloor \]为简洁,记 \(\lg(x)=\lfloor\log_2(x)\rfloor,n=\max(X,Y)\) 由于 \(i\&j=0\) ......
2022ICPC杭州站 - C D
目录The 2022 ICPC Asia Hangzhou Regional Programming ContestC. No Bug No Game cf 传送门 C DP The 2022 ICPC Asia Hangzhou Regional Programming Contest C. No ......
The 2021 ICPC Asia Macau Regional Contest
\(C. Laser Trap\) 根据题意不难判断出需要极角排序,然后对于每个点寻找更小的一个 \(180\) 度的点数。即使听说是用双指针实现查找依旧没什么思路。后来看了别人的实现方法发现确实比较简单,甚至只需要维护极角就可以了。 const long double pi=acosl(-1); ......
P9669 [ICPC2022 Jinan R] DFS Order 2
Description P 有一棵树,根节点是 \(1\),总共有 \(n\) 个节点,从 \(1\) 到 \(n\) 编号。 他想从根节点开始进行深度优先搜索。他想知道对于每个节点 \(v\),在深度优先搜索中,它出现在第 \(j\) 个位置的方式有多少种。深度优先搜索的顺序是在搜索过程中访问节点 ......
The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online (The 2nd Universal Cup. Stage 1: Qingdao)
Preface 好以后我就是SUA铁粉了,每次打SUA出的题感觉都很好,全程有事情干并且中档题很多很适合我们队这种比上不足的队伍打 不过yysy这场题目偏数据结构和图论方面比较重,而数学方向则不多,刚好撞上了我们队熟悉的地方,因此最后卡着时间过了9题 而且最近CF评测机不知道咋了,这场好多题光读入用 ......
Tiachi的2023西安ICPC区域赛银牌游记
时隔一年半没写博客,反正也是写给自己看的,就当一个树洞吧。 去年11月份的ICPC和CCPC都理所应当又有点遗憾地打铁了,当时从3月开始打了快一年ACM,发现周边同届的队员都有铜牌在身,就我和队友两人身上啥也没有,有种不敢自称打ACM的感觉了。到今年3月的蓝桥杯,打了个破省二且队内倒一且分低于某没打 ......
[ICPC2014 WF] Pachinko
[ICPC2014 WF] Pachinko 题面翻译 题目描述 有一个宽度为 \(w\) 高度为 \(h\) 的方格纸, $ w \times h$ 的格子中,有一些是空的,有一些是洞,有一些是障碍物。从第一行的空的格子中随机选一个放置一个球,向上下左右移动的概率比为 \(p_u : p_d : ......
2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)
\(A. Average Rank\) 将每个人的排名看作是前面一个人的贡献,然后采用类似懒标记的形式优化复杂度。 int sum[N],point[N],cnt[N],pre[N],laz[N]; void solve(){ int n=read(),w=read(); laz[0]=w; cnt ......
2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) N. Waste Sorting
有五种种类的垃圾,数量分别为 \(a_1, a_2, a_3, a_4, a_5\) 。 第一种为纸质垃圾 第二种为塑料垃圾 第三种双非垃圾 第四种基本纸质垃圾 第五种基本塑料垃圾 有三种垃圾桶,容量分别为 \(c_1, c_2, c_3\) 。 第一种垃圾桶可以放入:纸质垃圾和基本纸质垃圾 第二种 ......
2021-2022 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2021) gym 104670 C
原题 容易想到最短路 DAG 求出来,起初我以为要求最小割,但这是错误的,因为可能有多条边联通了一个点的情况,这时候选择最小割不一定是最优的 我们猜想一个思路:答案一定是包含 \(1\) 号节点的连通块全部填 \(N\) ,剩下的填 \(S\) 。发现在最短路 DAG 中, \(1 \rightar ......
2022 杭州 ICPC 补题 ACKG
2022 杭州 ICPC 补题 ACKG https://codeforces.com/gym/104090 笨成sb, 啥也不会写完两个签到就坐牢 (要补到银首,所以还差一个G题没补) 说实话补了三题,感觉就是一些算法的延申,比如这一场的铜牌题其实考到的就是exgcd,Trie,背包dp,但是又不 ......
[ICPC2015WF] Tours
题目描述 The Arca Carania Mountain national park is opening up for tourist traffic. The national park has a number of sites worth seeing and roads that co ......
The 2023 ICPC Asia EC Regionals Online Contest (I) B.String
The 2023 ICPC Asia EC Regionals Online Contest (I)B.String 题意: 给定等长字符串\(S_1,S_2\),下标从\(1\)开始 给出\(q\)个询问,每次给出一个字符串\(T\) 每次询问计算出三元组数量\((i, j, k)(1\le i\ ......
2022-2023 ICPC Central Europe Regional Contest
The 1st Universal Cup. Stage 8: Slovenia D. Deforestation 这道题出题人比较谜语人,对于一个分叉点,只能选择若干个儿子和父亲组成一组,剩下的儿子之间不能相互组合。所以从叶子节点开始贪心处理就好。对于一个父亲他有若干个儿子,就贪心的选择剩下部分更 ......
The 2021 ICPC Asia Macau Regional Contest
A. So I'll Max Out My Constructive Algorithm Skills 首先一行正一行反的把所有的行拼到一起,然后判断一下正着走时候合法不合法就反过来走就好。 #include <bits/stdc++.h> using namespace std; #define ......
The 2022 ICPC Asia Jinan Regional Contest
A. Tower 首先用了 dp 验证出把一个数字变成另一个数字的最优解一定是能除就先进行除法,然后再使用加一减一。 这样我们就有\(O(\log n)\)的复杂度求出把一个数变成另一个数的最小代价。 然后就是猜测最终的目标一定是某个数除了若干次二得到的。所以就枚举一下目标即可。 #include ......
2023 ICPC HIAST Collegiate Programming Contest
因为补题的时候,发现网上找不到一篇题解(补题补的很是痛苦),所以写了一篇,希望能帮助之后补这场比赛的人~~~ 有些太简单签到就没写,还有 \(2-3\) 题还没补出来,之后补了会加上去。 A. Gym Plates 解题思路 比较裸的一个状压 DP,我们考虑把数字的选取次数压到 DP 里面去,显然 ......
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\) ......
2023 ICPC 网络预选赛补题 II
2023 ICPC 网络预选赛 II 赛时 AC 题目 M. Dirty Work 点击查看代码 #include<bits/stdc++.h> #define ld double using namespace std; const int maxn=1e6+5; int a[maxn],b[ma ......
The 2023 ICPC Asia EC Regionals Online Contest (I) - Problem C. Multiply Then Plus
离线询问,建立时间线段树,那么每条直线存在的时间是一个区间,对应时间线段树上$\mathcal{O}(\log n)$个节点,每个询问对应时间线段树上某个叶子到根的$\mathcal{O}(\log n)$ 个节点。 对于时间线段树中的某个节点,它代表的直线集合是静态的,问题转化为静态区间查询。对于 ......
The 2023 ICPC Asia EC Regionals Online Contest (I) - Problem H. Range Periodicity Query
对于一个周期长度$p$来说,如果它不是$S_k$的周期,那么它一定不是$S_{k+1}$的周期,因此可以二分出分界线$t_p$满足它是$S_p,S_{p+1},S_{p+2},\dots,S_{t_p}$的周期,但不是$S_{t_p+1}$的周期。对于一个询问$(k,l,r)$,问题等价于寻找区间中 ......
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 ......
The 2022 ICPC Asia Hangzhou Regional Programming Contest
题解: https://files.cnblogs.com/files/clrs97/2022ICPCHangzhouTutorial.pdf Code: A. Modulo Ruins the Legend #include<bits/stdc++.h> using namespace std; ......
SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Preface 纯纯的智商场,只能说老外的出题风格和国内的比赛差异还是挺大的 这场开局被签到题H反杀后灰溜溜地下机,结果后面的题出的都还挺顺的 等到最后徐神把J过掉后我们都以为D是个大分类讨论(实际上机房里的学长们都是用分类讨论过的),就不想写了挂机到结束 后面看题解发现确实是分类讨论,但民间做法有 ......
2020 ICPC 南京 EFKL
2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing) E. Evil Coordinate 思路:因为如果给定了起点和初始走法,其实我们的终点是一定确定的。我们不妨让上下左右的连 ......
The 2021 ICPC 南京 ACJM
The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing) A.Oops, It’s Yesterday Twice More 思路:考虑先把所有袋鼠集中在一起然后再移动。因为有步数限制(\(\ ......
The 2022 ICPC 南京 ADG
The 2022 ICPC Asia Nanjing Regional Contest A.Stop, Yesterday Please No More 思路:因为袋鼠是同时移动的,所以我们可以不考虑袋鼠怎么动,而去考虑边界怎么动。所以我们先不考虑洞的影响,先确定哪些会因为边界而离开。确定好最终边界 ......
2023 ICPC 香港
gym 开场发现 E 是传统数据结构题很高兴,不过先跳了。F 知道相邻两段的长度差 \(\le1\),以为最终每段长度只有 \(\lfloor\frac{n}{m+1}\rfloor,\lceil\frac{n}{m+1}\rceil\) 两种,那就可以 DP 了,队友签完 H A 我上去写,呼救两 ......