- 博客(6)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #791 (Div. 2) 部分题解
A AvtoBus不难发现如果我们要车尽可能多，那么我们就需要最大化 444 的数目，尽可能少的情况就是最大化 666 的数目，我们同时发现 222 辆 666 轮车等价于 333 辆 444 轮车，有了这两个性质就不难解决。B Stone Age Problem考虑两种修改对于答案的影响，由于我们只关注序列权值的总和，我们只要记录什么时候进行了修改，在单点修改时判断下即可。C Rooks Defenders不难发现如果要将一个矩阵填满，那么有且仅有所有行均被覆盖或者所有列均被覆盖才合法，所以我们
2022-05-15 23:36:16
362
原创 第46届ICPC亚洲区域赛（沈阳）部分题解
E Edward Gaming, the Champion输出字符串中一共出现了多少次edgnbedgnbedgnb，考虑到所有的字母均不相同，顺序处理即可。F Encoded Strings I按照要求进行替换，然后快速排序，cmpcmpcmp函数按照字典序比较即可。J Luggage Lock考虑到状态数不多，我们强制从000000000000开始变换，bfsbfsbfs即可，可以通过本题。队友在vpvpvp时写了个别的做法，留坑待填。B Bitwise Exclusive-OR Sequ
2022-04-29 11:30:07
899
原创 Educational Codeforces Round 127 部分题解
A String Building考虑一段全部为AAA或BBB的子段，不难发现只有在该子段长度为111的时候不能用AAAAAA或者AAAAAAAAA凑出，这样顺序扫一遍即可。B Consecutive Points Segment考虑顺序进行移动，如果一个点它不受左侧点的制约，那么一定将它越往右越好，如果受制约判断二者之间距离并向左移或者不移，如果在左侧的点考虑完之后还相差≥2\geq 2≥2那么就是不合法的，这样我们在扫的时候判断是否有不合法的情况即可。C Dolce Vita首先将序列排序，考
2022-04-24 15:46:04
1516
原创 第46届ICPC亚洲区域赛（昆明）部分题解
K King of Games考虑到输赢的形式一定是一个winwinwin后面跟着一堆loseloselose，不难发现这个是有一个循环节的，并且a/ba/ba/b的输赢形式不受nnn影响，只是从中截取了一个前缀，打表发现当n∗a/bn*a/bn∗a/b的整数部分每次加一的时候就会少一个胜场，答案就是n∗a/bn*a/bn∗a/b，否则就是n∗a/b+1n*a/b+1n∗a/b+1，注意特判a=0a=0a=0的情况。F Find the Maximum考虑将式子变形−x2+∑u∈Vbu∣V∣x-x^2
2022-04-23 16:38:56
1242
原创 第45届ICPC亚洲区域赛（济南）部分题解
C Stone Game首先数目为 333 的石堆对于答案没有贡献，考虑目前数目为 111 和 222 的石堆的数目，如果二者都不为零，那么将两者合并一定最优，这样就得到了对于答案没有贡献的数目为 333 的石堆，如果只剩一堆，那么我们考虑将这一堆的 23\frac{2}{3}32 进行合并，这样剩余的 13\frac{1}{3}31 就能和新得到的进行合并，实现的时候需要注意边界的小细节，复杂度O(logn)O(logn)O(logn)。#include<bits/stdc++.h>
2022-03-05 22:57:38
362
原创 算法竞赛回归日志—基础图论
有向图强联通分量的Tarjan算法算法内容dfn[u]dfn[u]dfn[u] ：节点 uuu 搜索的次序编号low[u]low[u]low[u] ：节点 uuu 或 uuu 的子树（经过最多一条后向边或栈中横叉边）能回溯到的最早的栈中节点的次序编号void Tarjan(int u){ dfn[u]=low[u]=++idx; ins[u]=true,stk[++top]=u; for(int i=0;i<e[u].size();++i){ int v
2022-02-25 21:23:26
617
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人