- 博客(132)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final) F. Identify the Operations
http://codeforces.com/contest/1443/problem/F#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>#include <cstdio>#include <map>#include <set>#include <utility
2020-11-20 20:24:15
159
原创 Codeforces Round #683 (Div. 2, by Meet IT) E. Xor Tree
http://codeforces.com/contest/1447/problem/E题意：给出n个互不相同的数字，对每个i（1<=i<=n）找到ai^aj最小的j（1<=j<=n, j != i）连边，求最少删除多少个数能使得这样操作出来得到的是树思路：从位运算的角度来看，决定数值大小的首先要看最高位考虑一个位，如果该位为0或1的数都有，那么为0的肯定与为0的数相连，因为这样该位的异或值为0，与为1的相连则会为1，肯定优先选小的只考虑单个位的话，同位相同的肯定会在一个连
2020-11-18 00:36:48
240
原创 vimrc
"Version: 1.0 by momodi@whuacm"Modified by [email protected] $VIMRUNTIME/mswin.vimbehave mswinimap <c-d> <c-o>ddimap <cr> <cr><left><right>map o o...
2019-05-08 20:10:26
277
原创 Educational Codeforces Round 58 (Rated for Div. 2) F （单调dp）
http://codeforces.com/contest/1101/problem/F容易发现对于每种起点终点组合的种类数很少所以考虑对于不同组合的最优答案用dp[ i ][ j ][ k ] 记录对于一个起点 i 到终点 j 分成 k+ 1段其中的最大值对于每个车的最优答案就是 c * dp[ s ][ f ][ r ]假如分成k段的话 可以考虑枚举最后一段或者最前一段假如断点是p...
2019-01-12 15:53:24
187
原创 ACM-ICPC 2018 徐州赛区网络预赛 ABCFGHIJ
按过题顺序丢 IGHJFABCI 好像是个模拟 队友写的 https://nanti.jisuanke.com/t/31461#include&lt;bits/stdc++.h&gt;using namespace std;#define LL long long#define ll long long#define fi first#define se second#de...
2018-09-09 19:23:40
441
原创 ACM-ICPC 2018 沈阳赛区网络预赛 J Ka Chang 分块
https://nanti.jisuanke.com/t/31451对每层的个数分块 当这个深度的节点个数&gt;block时 暴力维护每个点的子树有多少个这个深度的节点 这样的层数最多有n/block个 预处理复杂度O(n*n/block) 修改直接修改这个层数总共加了多少当深度的节点个数&lt;=block时 暴力修改这个深度的每个节点 用一个bit或者线段树维护树的d...
2018-09-08 23:32:15
336
原创 ACM-ICPC 2018 沈阳赛区网络预赛 D Made In Heaven （k短路 ：最短路 + 可持续化堆/A*）
https://nanti.jisuanke.com/t/31445#include &amp;lt;algorithm&amp;gt;#include &amp;lt;iostream&amp;gt;#include &amp;lt;cstring&amp;gt;#include &amp;lt;cstdio&amp;gt;#include &amp
2018-09-08 22:36:03
259
原创 Educational Codeforces Round 49 (Rated for Div. 2) F - Session in BSU
一个人选一个点 也就是可以看成一条边要选一个点 那么就只要单独考虑一个个联通块就可以了一个点代表一个时间 假设这个联通块的点数<边数 就代表人数>可选时间数 不可行假如 点数 = 边数 也就是所有点都必须选 取最大值假如 点数>边数 说明这是一棵树 丢掉最大值取次大#include <iostream>#include <algori...
2018-08-25 11:04:22
181
原创 Educational Codeforces Round 49 (Rated for Div. 2) E - Inverse Coloring
题意： 有一个n*n的方格需要染成黑白颜色 定义方格为beautiful的当且仅当每对相邻行的对应格子都相同或都不同，对列同理。 定义方格为suitable的当且仅当不存在大小&gt;=k的同色子矩阵首先考虑单独一行 可以通过dp算出长度为n的序列中最大连续同色长度为i的总方案那么再考虑列 因为方格是n*n的 所以行跟列考虑其实是一样的 选出了一行方案的再选列的方案就能确定涂完...
2018-08-23 22:38:16
133
原创 Caravan Robbers CF Gym - 100134C
https://cn.vjudge.net/problem/Gym-100134C http://codeforces.com/gym/100134/attachments答案就是最小的min(bi-aj)/(i-j+1) 用斜率优化 维护一个上凸壳 在上面三分答案插入的时候插入原点 算答案的时候再+1 当做当前点往右偏移了一个位置#include <iostream&g...
2018-07-29 02:54:13
260
原创 2018 SCAU暑假个人排位赛Ⅱ
A HDU - 4333 https://cn.vjudge.net/problem/30656/origin扩展Kmp 先翻倍原串s1得到s2 再用exkmp求s2的后缀跟s1的LCP 假如ex[i]&gt;=len说明相等 &lt; len则判断下一位的大小关系需要注意判断循环节 假如是有循环节的那么需要整体除掉循环次数#include &lt;iostream&gt...
2018-07-13 01:44:03
179
原创 2018 SCAU暑假个人排位赛Ⅰ
A HDU - 4324 https://cn.vjudge.net/problem/30578/origin找一个有向三元环 因为是一个竞赛图 所以三个点之间的关系只有两种 对于不合法的第一种可以通过一个点的入度计算出来 总共有C(n,3)个关系 那么剩下的关系就是三元环的关系 char s[maxm][maxm];int inp[maxm];int main() {...
2018-07-11 01:12:48
229
原创 2018广东省赛总结
又是一次省赛 这一次的成绩感觉不大理想 ————————比赛开始之前打开电脑发现鼠标用不了只能先开好另一台机 然后比赛过了10分钟有个人跑来把鼠标换了又只能关掉机子用修好的 重新打开网页和codeblocks重新配置 感觉有点烦 不过问题不大刚开始一会 队友hq说A好像能做 看了一眼 嗯 一个神奇的数学式子 我觉得我不会 按气球颜色先看了一下B和E 研究了下B 发现B是每个点的路线
2018-05-07 13:12:18
611
原创 Codeforces Round #476 (Div. 2) [Thanks, Telegram!] E. Short Code CF965E
http://codeforces.com/contest/965/problem/E首先建一棵trie树 问题转化为把有权的点的深度和尽量缩小 容易想到即把所有点尽量往上放 当一个节点有空位并且有多个子节点的时候 首选把最长的放在这个位置想了半天怎么dp 想来想去觉得麻烦最后还是STL好用(#include <iostream>#include <algorithm>#include
2018-04-27 12:52:38
316
原创 Codeforces Round #476 (Div. 2) [Thanks, Telegram!] D. Single-use Stones CF965D
看到题目先想到这明显是一个最大流 但是边太多了不可能用模版做 已知有 最大流 = 最小割 那么最小割一定是割了连续l个点 所以直接找最小割就是答案#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>#include <cstdio>#include <m
2018-04-26 09:24:40
214
原创 CS Academy Round #77 (Div. 2 only) C D
https://csacademy.com/contest/round-77/summary/C 对矩阵从右往左做一个先后手的dp dp[o][i][j]表示o玩家在从左边走到i行j列后可以取到的想要的最优解#include <iostream>#include <algorithm>#include <sstream>#include <...
2018-04-19 19:18:04
154
原创 2018SCAU校赛题解
出题组说难度顺序是ABIC EH FG D 不过这里还是按照题目顺序 如果遇见不懂的神秘词汇(例如尺取) 请百度“acm 尺取” 代码我会只留必要的定义并且尽量减短长度AUnsolved Problem Description Ly is participating in a programming game！The programming game includes n ...
2018-04-19 13:12:05
1197
原创 Lock (fft + 状压dp)
Description Yplusplus has a rotary password lock. The lock has n(n <= 50000) positions and each position corresponds to a number from 0 to 3. This is a rotating lock, so digits of each position ar...
2018-04-18 21:12:21
271
原创 Hari Merdeka UVALive - 6806
用给的模式串build一个ac自动机 然后在fail树上做一个背包dp dp[i][j]表示第i个状态下花费了 j 获得的最大价值（顺便升级了一下原来的ac自动机模版）#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>#include <cstdio>#i
2018-04-09 14:08:56
114
原创 Best Position UVALive - 6808
枚举 + bitset用bitset记录GL的情况 然后直接枚举每个位置为左上角时候的答案char s[maxm][maxm];char s2[maxm][maxm];int main() {#ifdef LOCAL freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout);#endif // L
2018-04-08 18:23:00
151
原创 Divide by Zero 2018 and Codeforces Round #474 (Div. 1 + Div. 2, combined) C D
C Subsequence Counting http://codeforces.com/contest/960/problem/C 构造一段一段的 每一段只能跟自己这一段的数字产生贡献int x,d; sdd(x,d); ll now = 1; vector<ll>v; while(x) { int w = 0; ...
2018-04-08 12:02:53
162
原创 Circle and Marble UVALive - 6803 （SG函数+nim博弈）
普通的SG博弈 就是对每个可操作的部分算一个mex 也就是SG值 然后把所有能操作的部分的sg值异或起来 为0则先手必输 不为0则先手必胜#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>#include <cstdio>#include <map>#
2018-04-06 13:10:22
259
1
原创 51nod 1577 异或凑数 （线性基）
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1577构造出一个最大无关组 然后对询问检查这个k是否可以由最大无关组表达出来 即是否能异或出0 一边插入一边解决询问#include <iostream>#include <algorithm>#include <sstream>#include <string
2018-04-06 10:49:32
248
原创 BZOJ 3232: 圈地游戏 （分数规划+最小割）
转化成最大权闭合子图的问题二分答案x 分数规划 将源点与每个点相连 容量为点权 将每个点与相邻点相连 容量为x*公共边边权 将边界点与汇点相连 容量为x*外边权（可以理解为即使选了这些点也要割掉这些边）这样建图可以大概理解成选了一个点而相邻点没有选的话就一定要把它连出去的边割掉 也就是要用线围起来注意容量答案什么的要全部改成double 按值域初始化ｒ 当然这个ｒ是取不到的...
2018-04-06 10:15:11
318
原创 The Mountain of Gold? UVALive - 6800
https://cn.vjudge.net/problem/UVALive-6800题意： 问是否有从0出发并且回到0的负环假如没有负环每个点最多被松弛n次 所以直接对每条边松弛n次 再看能不能松弛 可以的话就说明存在这样的负环#include <iostream>#include <algorithm>#include <sstream>...
2018-04-03 13:16:56
138
原创 BZOJ 3679: 数字之积
<1e9的乘积的状态并不多 所以直接用map写个dfs的数位dp#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>#include <cstdio>#include <map>#include <set>#include <utility>#inclu
2018-03-31 15:03:19
255
原创 BZOJ 3251: 树上三角形
https://www.lydsy.com/JudgeOnline/problem.php?id=3251考虑到一个序列如果不能组成三角形那么一定是fib序列 fib增长得很快并且值域只有1e9 那么50个一定有解 暴力跑路径 大于50个直接跳出循环就可以了 需要注意的是判断时候要用上LL#include <iostream>#include <algorithm>#include <
2018-03-31 12:32:09
148
原创 51nod 1436 方程的解数
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1436大概就是一个按位分析k再加上快速幂就可以了#include <iostream>#include <algorithm>#include <sstream>#include <string>#inc...
2018-03-31 11:45:34
192
原创 51nod 1486 大大走格子
容斥把(h,w)看成黑格子 先按偏序对黑格子排序然后对每个黑格子算出到不经过前面每个黑格子的方案数 最后的到(h,w)黑格子的方案数就是答案因为对于每个方案数 都减去了前面不能走的方案 （另外，题目根本没说只能往右往下，还以为是插头什么的）#include <iostream>#include <algorithm>#include <sstream>#include <string>
2018-03-31 10:39:44
190
原创 Codeforces 955C - Sad powers
http://codeforces.com/problemset/problem/955/C假设p=2 那么底数范围是1~1e9 假设p>=3 那么底数范围是1~1e6 并且后面的数的power会递增得越来越快 所以可以考虑O(nlogn)预处理出p为奇数时的x 然后加上p为偶数时的x就是答案很明显p为偶数时是某个的平方 所以注意筛选#include <iostream>#include
2018-03-30 14:11:14
520
原创 True Liars POJ - 1417
题意： 有p1个好人,p2个坏人 好人只说真话 坏人只说谎话 给出n句某个人说某个人是真人还是坏人 问是否存在好人和坏人方案的唯一解 有的话则升序输出好人先用一个带权并查集维护一个联通块内的关系 然后dp[i][j]表示前i个联通块内有j个好人的方案 因为是唯一解 所以输出方案的时候倒过来推就可以了#include <iostream>#include <algorithm>#i
2018-03-30 09:25:29
278
原创 CS Academy Round #74 (Div. 2 only) A B C D E
A找出有多少独角兽因为范围很小 所以枚举即可 int a,l,h; sddd(a,l,h); for(int i=0;i<=a;++i) { int leg = l - i*4; int ho = h - i; if(ho&1)continue; if(ho*2>leg)continue;
2018-03-29 16:20:16
200
2
原创 Painting the balls SGU - 183
定义 dp[i][j] 表示最后一个在位置i 倒数第二个在j时候的代价 这个复杂度是O(n*m*m)的 所以需要优化转移的时候是枚举ijk 三个点 优化实际上就是固定了中间那个点j 移动最后面的点i 往前移动i的同时用f[j][i-m]更新最小值 同时这个最小值也能更新新的f[i][j]优化后的复杂度为O(n*m)#include <iostream>#include <algorit
2018-03-28 21:08:06
438
原创 Damn Couples ZOJ - 3161
考虑一串相邻的关系 设f[i]为有i个人的时候最多剩下的人 那么转移就为 f[ i ] = max( f[ i ] , min ( f[ i-j ] + f[ j-1 ] , f[ i-j-1 ] + f[ j ])( j< i ) 右边的min表示两个人其中一个人走掉的最坏情况然后把关系分成一段段连续的处理就行了 需要注意给出的序号并不是有序的这是我自己的写法 把连续的一段减少的算出来
2018-03-28 13:59:48
469
原创 Prince and Princess UVA - 10635
找出两个序列的最长公共子序列因为每个序列中每个数只出现一次 所以可以先记录每个数字在第一个序列中出现的位置 再把第二个序列的数字换成这个数字在第一个序列中出现的位置 这样求一个最长上升子序列就是答案#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>#inc
2018-03-28 12:51:28
202
原创 SGU 143 Long Live the Queen
求一棵树上的联通子图使得其所有节点权值和最大树形dp dp[u]表示这个结点为根的最大权联通子图 转移为dp[u] = val[u] + sum( max(0,dp[v]) ) 假如选儿子节点的贡献为负则不选#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>
2018-03-27 12:59:29
170
原创 Codechef CSUBSEQ February Cook-Off 2018 Chef and Chefness
用dpijkl记录每个状态的子序列最大长度 i,j,k,l表示以c,h,e,f结尾的合法子序列个数 因为k<=32所以每个最多只需要记录到32假如当前f结尾的合法子序列个数=K 那么后面的f都得删掉#include <iostream>#include <algorithm>#include <sstream>#include <string>#include <queue>#inc
2018-02-19 10:54:17
180
原创 Codeforces Good Bye 2017 D. New Year and Arbitrary Arrangement
首先考 虑dp [i] [j] 表示 i 个a j个子序列ab 时候执行算法的期望那么转移就是dp[i][j] = ( pa * dp [i+1][j] + pb * dp[i][i+j] ) / (pa + pb)因为长度可以任意长所以首先考虑初始化的位置可以发现当a的个数为k的时候再添加一次b就结束算法了 所以考虑初始化dp[k][x]PA = pa/(pa+pb) , PB = pb/(pa
2017-12-30 12:05:00
270
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人