一片伟大的净土

灵魂的归处,肉体的坟墓。

zzczzczzc's home

2023ICPC杭州站铜牌题

2023/12/11

1月14号之后将本篇内容更新到CSDN中,如果我看到了。
https://blog.csdn.net/qq_17807067/article/details/134909554

补题链接(英文题面):https://codeforces.com/contestInvitation/f9525e4ae38eefdd9062ae5f43d8c9fdee80ad6e

简单题:M,J

J. Mysterious Tree

题面大意:给你一棵树,这棵树只能是一个链或者是菊花,没有别的情况,菊花就是有一个点和其他点都有边,
其他点和其他点直接都没边。判断这棵树是链还是环,询问次数为 n/2向上取整+3

此题是交互题所以不可以使用cin.tie,define endl '\n',具体来说是使用cin.tie就不可以使用'\n'换行
原因:https://icpc.xidian.wiki/cce/cin-tie0

基本上是cfl单杀的一道题,询问1-2,3-4,5-6,最多询问n/2次就能找到菊花中心,如果没找到这样的边,说明
是链(奇数和偶数分开,需要特判两次,没找到一定是链),比赛的时候WA两次找出来的两个血汗特判。
一开始cfl给了思路之后我和z01去做题了,个人原因没听清思路WA两次,应该是谁给思路谁来写题,加上
中间一个敲代码的,保证给思路的要在线。

这种特判要从代码角度去考虑是否完备,顺着代码去考虑某一行是否有问题,思路上很难看出来。

找到这条边之后再去询问3次一定就能问出是链还是菊花,次数刚好。

-------------------------------------------------------------------------------------

M. V-Diagram

题目大意:给你一个序列,必然是一个先降后增的序列(V图),找出一个平均值最大的连续子V图。

这道题差不多是三个人一起想出来的,最后根据z01和cfl的思路点出如果某一边被选了,那么必然被全选,
结束战斗。

最终结果只能是V的左侧被全选 或者 V的右侧被全选 或者 全部选上,只有三种情况。
因为平均值特性 3 3,选上平均值不变,如果递增 3 4 5 6,选上平均值必然增大,所以全选。

造数据测试后,1发过,最稳的一题。

-------------------------------------------------------------------------------------

铜牌题:D,G

D. Operator Precedence

题目大意:(a1×a2)+(a3×a4)+···+(a2n−1×a2n)=a1×(a2+a3)×(a4+a5)×···×(a2n−2+a2n−1)×a2n

满足上述式子,其中条件是等式值不为0,ai的取值也不为0

比较可惜的是正式赛的时候没有做出来,赛后z01 3小时把这道题AC了

正式赛找了3个小时规律没找出来,尝试化简式子也都失败了。
打表代码写的有问题,某些n的取值找出来的不是第一个合法构造,导致规律找不出来。
同时样例也具有误导性质,前面给的是平方的规律,后面是没规律。
只能说这种Special Judge的样例看看就行,还是以自行思考为主。

尝试解式子的时候因为直接设了a1和a2n为1(根据样例设的)所以左右式项数还是不统一,没法做。
正确的是设a1或者a2n其中一个为1,因为右式是乘法,所以我们希望它不要乘的太大,另括号中的加法
均为2,-1,2,-1的构造,直接求和为1抵消。然后代入左式解出a2n的合法取值。

-------------------------------------------------------------------------------------

G. Snake Move

题目大意:给你一条蛇,可以WSAD走,也可以特殊操作执行自己缩短一个长度(不能把蛇头缩了)。
问蛇到矩阵中的所有点最快只要几次操作。

有思路但是题目读不太懂,这个最小操作是蛇一次就要移动完还是每次出发到达那个点的最小操作。
如果是每次出发就可以采用bfs遍历一次所有点来求出答案,对于某个被蛇身挡住的点,标记一下被
蛇身挡住的长度来当作答案,下次bfs答案来和他比较应该就可以了。(读不懂操作数也可以把bfs
代码敲出来看看和样例比较一下)

但是题目中最终输出的答案是连乘后对2^64取模,直接给long long爆了,不知道怎么解决所以最终还是
没敲代码。



阅读全文

ACM学习动态-断更

2023/11/17

2024-07-22
感觉有点做无用功,如果有好用的模板我会放在/index/ACM模板里面,其他就不做维护了
毕竟学到脑子里面就行了,反正我也不复习。

codeforces:1433(specialist)
atcoder:865(6kyu)
洛谷:1047(LESS div4)
牛客:1343(RANK 2902)
力扣:1550(TOP 35.23%)

分数转换网站cf和at分互换
蓝桥杯备赛
代码压行

正在学习

张能祎神犇的模板
张能祎神犇的博客
洛谷各色模板
Oi-wiki各模块例题以及知识点
Codeforce div/vp gym-vp
Atcoder abc/vp arc/vp
洛谷月赛

upd:2024-4-1
OI-WIKI 杂项 离散化
复习time

UKE warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

upd:2024-3-31
2024年度第五届全国大学生算法设计与编程挑战赛(春季赛)
AC:4/10
Rank:502/2177(一人组,二人组,三人组,合榜,前23.06%)
Reward:UKE,运气好铜
补题记录:4/10

upd:2024-3-30
AtCoder Beginner Contest 347
AC:3/7
Rank:3212/13360(前24.05%)
Rating:865(+14)
补题记录:4/7

upd:2024-3-24
AtCoder Regular Contest 175
AC:1/6
Rank:1233/3780(前32.62%)
Rating:851(+47)
补题记录:2/6

upd:2024-3-23
UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
AC:5/7
Rank:1984/10531(前18.84%)
Rating:804(+73)
补题记录:5/7

upd:2024-3-22
牛客小白月赛89
AC:3/6
Rank:437/2208(前19.80%)
Rating:1343(+121)
补题记录:3/6

upd:2024-3-19
Codeforces Round 935 (Div. 3)
AC:4/8
Rank:2440/7818(前31.22%)
Rating:1433(-17)
补题记录:5/8

upd:2024-3-18
AtCoder Regular Contest 174
AC:1/6
Rank:2105/3900(前53.98%)
Rating:731(-7)
补题记录:2/6

upd:2024-3-17
【LGR-179-Div.2】复旦勰码 3 月月赛 II & ZHYOI Round 4
AC:2/4
Rank:84/1701(前4.94%)
Rating:1047(+207)
补题记录:2/4

upd:2024-3-17
力扣第 126 场双周赛
AC:2/4
Rank:1031/3234(前31.89%)
Rating:1550(+61)
补题记录:2/4

upd:2024-3-17
Monoxer Programming Contest 2024(AtCoder Beginner Contest 345)
AC:3/7
Rank:3692/9742(前37.90%)
Rating:738(+19)
补题记录:3/7

upd:2024-3-15
牛客挑战赛73
AC:2/6
Rank:316/1104(前28.63%)
Rating:1222(+222)
补题记录:2/6

upd:2024-3-12
Codeforces Round 933 (Div. 3)
AC:5/7
Rank:1236/27781(前4.45%)
Rating:1450(+81)
补题记录:5/7

upd:2024-3-10
AtCoder Regular Contest 173
AC:0/6
Rank:1323/4400(前30.07%)
Rating:719(-41)

upd:2024-3-10
【LGR-177-Div.3】洛谷基础赛 #8 & Westlake OI #1
AC:1/4
Rank:814/1900(前42.85%)
Rating:840(+63)
补题记录:1/4

upd:2024-3-10
力扣第 388 场周赛
AC:2/4
Rank:2850/4291(前66.42%)
Rating:1489
补题记录:2/4

upd:2024-3-10
【LGR-176-Div.2】[yLCPC2024] 洛谷 3 月月赛 I
AC:2/7
Rank:273/2005(前13.62%)
Rating:777(+468)
补题记录:4/7

upd:2024-3-9
Toyota Programming Contest 2024#3(AtCoder Beginner Contest 344)
AC:3/7
Rank:4967/11155(前44.53%)
Rating:760(-10)
补题记录:3/7

upd:2024-3-2
AtCoder Beginner Contest 343
AC:4/7
Rank:3795/11706(前32.42%)
Rating:770(+17)
补题记录:5/7

upd:2024-2-28
Codeforces Round 929 (Div. 3)
AC:4/7
Rank:3938/26561(前14.83%)
Rating:1369(+10)
补题记录:5/7

upd:2024-2-20
Codeforces Round 928 (Div. 4)
AC:5/7
Rank:820/14636(前5.7%)
Rating:1355(+120)
补题记录:5/7

upd:2024-2-19
AtCoder Regular Contest 172
AC:1/6
Rank:1364/3681(前37.03%)
Rating:753(+68)
补题记录:1/6

upd:2024-2-18
Toyota Programming Contest 2024#2(AtCoder Beginner Contest 341)
AC:4/7
Rank:3476/13120(前26.50%)
Rating:685(+37)
补题记录:3/7

upd:2024-2-14
Codeforces Round 925 (Div. 3)
AC:4/7
Rank:5634/24858(前22.67%)
Rating:1235(+27)
补题记录:5/7

upd:2024-2-11
Codeforces Round 924 (Div. 2)
AC:2/6
Rank:5003/13067(前38.29%)
Rating:1197(+21)
补题记录:2/6

upd:2024-2-10
KAJIMA CORPORATION CONTEST 2024(AtCoder Beginner Contest 340)
AC:3/7
Rank:3562/10617(前33.48%)
Rating:648(+31)
补题记录:4/7

upd:2024-2-5
AtCoder Regular Contest 171
AC:1/6
Rank:1964/4844(前40.55%)
Rating:617(+61)
补题记录:2/6

upd:2024-2-3
Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339)
AC:3/7
Rank:3098/10799(前28.69%)
Rating:556(+125)
补题记录:3/7

upd:2024-1-31
Codeforces Round 922 (Div. 2)
AC:2/7
Rank:13613/20643(前65.95%)
Rating:1176(-24)
补题记录:2/7

upd:2024-1-28
Codeforces Round 921 (Div. 2)
AC:1/6
Rank:11495/18710(前61.44%)
Rating:1200(+19)
补题记录:3/6

upd:2024-1-22
AtCoder Regular Contest 170
AC:1/6
Rank:1587/2058(前77.12%)
Rating:431(+219)
补题记录:2/6

upd:2023-12-16
Toyota Programming Contest 2023#8(AtCoder Beginner Contest 333)
AC:5/7
Rank:2437/12304(前19.81%)
Rating:212(+177)
补题记录:5/7

upd:2023-12-14
OI-wiki搜索:洛谷搜索题单
CSDN记录

upd:2023-12-11
AtCoder Beginner Contest 332
AC:3/7
Rank:4033/7452(前54.12%)
Rating:35(+35)
补题记录:4/7

upd:2023-12-10
2023ICPC杭州站
AC:2/13
Rank:379/435(前87.13%,铁牌)
补题记录:2/13

upd:2023-12-6
Codeforces Round 913 (Div. 3)
AC:2/7
Rank:6388/19176(前33.32%)
Rating:1177(+93)
补题记录:3/7

upd:2023-12-5
AtCoder Beginner Contest 331
CSDN记录

upd:2023-12-1
OI-wiki构造
CSDN记录

upd:2023-11-24
Educational Codeforces Round 158 [Rated for Div. 2]
AC:3/6
Rank:2184/12126(前18.02%)
Rating:1084(+313)
补题记录:3/6

upd:2023-11-23
OI-wiki二分
CSDN记录

upd:2023-11-22
OI-wiki差分,模板优化(参考张能祎神犇)
CSDN记录

upd:2023-11-21
OI-wiki树上前缀和
CSDN记录

upd:2023-11-19
Codeforces Round #910 (Div. 2)
AC:1/6
Rank:3985/8026(前49.66%)
Rating:771(+305)
补题记录:1/6

upd:2023-11-18
Codeforces Round #909 (Div. 3)
AC:3/7
Rank:5434/18717(前29.04%)
Rating:466(+466)
补题记录:4/7

赛前必看

upd:2024-4-1 关于离散化
如果离散化之后用到的不是点,而是点和点之间的关系,线段。
那么可能会有 1-2覆盖3 2-3覆盖2 3-4覆盖1,可以发现中间的2-3,被左右两边抵消看不到了。
此时离散化需要将点x,右边的x+1,也进行离散化。
注意使用set和map离散化时候,x+1会出现重复的情况,注意判断,if(!f[x])f[x]=cnt++;

upd:2024-3-19
字符串拼接
string s
s=”0”+s;
而不是
s=’0’+s
注意区别。

upd:2024-3-17
答案从不等式出来的话,一定要谨慎思考。
如果凑形式,答案>=x,x不是答案的值,即 答案>=3,
若答案是4,也是满足等式的,不能使用3作为答案。

upd:2024-3-9
via z01Prime
每一段的最大值,最大值里面的最大值尽可能小,二分答案。(最大最小)

upd:2024-3-8
二维不确定的数组如int a[n+1][m+1],随着程序运行确定的这种,不可被函数和lambda以及function
函数调用,只能直接写循环。
如果代码复杂度符合预期,提交却TLE,那么多关注代码的下标是否越界。

upd:2023-12-10
2023ICPC杭州站
1.cin.tie和ios,’\n’在交互题中不可用,千万注意。
2.题目谁给的点子谁就必须是主体手之一,A给的点子,不能B和C来做,必须是A和B或者A和C
3.XCPC也许会给中文题面,需要提前注意。
4.题目造数据也许细节造不出来,需要思维跟随代码跑一遍,看看是否有缺漏的情况。

upd:2023-12-9
XCPCtip
1.前几题过的人多的大概率就是简单题和签到题,可以先跟榜单。后面如果有熟悉的但是强的不是特别多的人可以跟着做,比如台州学院和xhy,榜单那边可以点星号关注。(最好还是自己做)
2.看题分配一下反正别看同一题。
3.ICPC-WF镜像比赛使用的是乌班图系统,需要打开桌面的Home,里面有Clionproject,点开就有main.cpp,右键,使用更多应用,用Clion打开。(在此之前先把Dom平台打开,点开题目缩小放在屏幕的右半边。敲模板的时候找个人在右边看题,不是前几题就换题(以看题为主,敲模板为辅)
4.有实在没思路做不来的题,可以考虑用rand函数暴力卡出来(try个100次)
5.有除法和乘法不要用取模(不然要用乘法逆元和除法逆元),尽量变成减法和加法,减法也要先加模再取模。

upd:2023-11-20
巧技(有时作用很明显)
1.正难则反。包括但不限于逆向思维,逆向建图,逆向遍历数组。
2.建图思维。从S->T点,中间有n个加速点可以选择是否加速,问最短时间。并不是考虑某个点是否使用(01dp),而是图论问题,S->所有点连线,其他点都连线,实际上就是一个从S点出发的最短路问题。
3.lower_bound不要用在STL上,否则复杂度会退化成n,要使用STL自带的lower才是logn。例如:sets,s.lower_bound。如果不需要大于等于,需要小于等于,请使用set<int,greater>s
4.max({})中间加花括号可以多个比较,例如max({a,b,c})

upd:2023-11-17
XCPCtip
1.不能乱try,10分钟造数据/对拍 优势远大于 一次罚时。对于显而易见的签到题,队友感觉都没问题的时候,可以选择直接提交。
2.先跟榜单做题,如果卡了没思路感觉有难度马上换题,可能被强队带偏了。

关于本文

upd:2023-11-17
蒟蒻就要有蒟蒻的样子,蒟蒻不刷题才是常态。
作为督促自己的一种方式就是更新博文,将自己的努力可视化。
学习内容和学习方向如果有更好的,欢迎各位神犇在下方留言。

你是否正在寻找:算法和数据结构模板?

阅读全文

JetBrains-IntelliJ-系列全家桶激活服务器内容备份

工具 2023/11/15

之前备份的全倒闭了,重新搞一次。

阅读全文

算法设计与分析-汉诺塔

教程 2023/9/27

OI WIKI:写递归的要点
明白一个函数的作用并相信它能完成这个任务,千万不要跳进这个函数里面企图探究更多细节, 否则就会陷入无穷的细节无法自拔,人脑能压几个栈啊。

阅读全文

Web开发第5章-设计一个计算器

教程 2023/9/25

主要用到一行两列和两行一列类似的属性,最后一节课还提到了form表单,用于input。

源码右下角可以拉开查看

实现效果

···
AC +/- % ÷
7 8 9 ×
4 5 6 -
1 2 3 +
0 . =
阅读全文
1 ... 24 25 26 27 28 ... 33