oidoidooid-CSDN博客

原创 CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）

今天打了CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）对退休老年党太友好了！码量小的惊人，且思路简单，瞎捏捏就粗来了。鉴于太久没有更博了，我今天要更博！感觉太久没打代码了，假期回去会被锤爆吧！我要趁工作之余悄悄代码，不能称为一条竞赛咸鱼！E可以推导出当位于前k格的时候，到达终点的期望都是一样的。后面就可以直接用矩乘推出来了。（在网上扒拉...

2019-07-28 20:03:07 138

原创 CCPC2018 湖南全国邀请赛补题（DP/并查集/最长上升子序列）（H待补）

D比赛时的思路是计数，没有想到DP，现在一想其实DP的挺明显的。这个思路是网上一个我看的比较明白的思路。题解：1. 直接把整个环看成相同数目的黑白段的连接（必定是相同数目）。2. 用DP计算将i个数分解成j段的所有分发的乘积和，，dp的时候用前缀和和滚动数组优化。3.拼接的时候后取模。#include<bits/stdc++.h>#define MOD ...

2019-05-16 16:23:26 183

原创 HDU 4622/4641 后缀自动机简单应用

46414641因为是多组数据所以为了方便把板子改成了用数组的二而不是指针的写法。计算出现k次以上的字符串一共有几个。对于已经建立好的SAM，每加入一个字符，多出来了一次的字符串就是所有的以这个字符为结尾的后缀字符串。所以只需要统计加入这个字符之后又多了几个就可以了，用后缀数组就可以实现。记录一下每个状态的right集合的大小（size的求法可以想象成一个树形dp）然后如果...

2019-03-03 16:11:17 184 1

原创 CF 105 div 2 (dp水题）

写过史上最简单的一套cf代码量少，想也好想D概率dp，转移只用考虑公主就可以了#include<iostream>#define N 1005using namespace std;double dp[N][N];bool vis[N][N];double dfs(int nw, int nb){ if (vis[nw][nb]) return dp[nw...

2019-02-28 20:58:12 142

原创 CF 106 div 2 (乘法dp/后缀自动机）

比赛连接D简单区间dp一个合法的括号序列染色，一对匹配的括号必须有一个被染成红色或者蓝色，另一个不染色。被染色的相邻括号不能相同颜色，问有几种染色的方法。直接区间dp，转移就是考虑每种情况然后相乘就可以了。#include<bits/stdc++.h>#include<stack> #define MOD 1000000007using n...

2019-02-28 12:29:41 229

原创 CF 365 div 2 (线段树应用/dp）

比赛网址D题意是对于一个序列，有一些询问，询问一个区间里出现了偶数次的数字的异或和。离线回答，应用线段树即可#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<vector>#include<se...

2019-02-26 20:53:36 165

原创 Google Kickstart round G 2018（状压搜索）

A输出满足条件的三元组的个数特殊考虑0和1WA2细节写的太丑了#include<iostream>#include<string.h>#include<algorithm>#define N 10005using namespace std;long long a[N];long long sum[200005];int ma...

2019-02-11 19:12:17 466

原创 AIM Tech Round 3（树形dp/multiset)

比赛网站D给你子序列11，10，01，00的个数，问是否存在这样的01序列，若有则输出一种。简单数学题#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<vector>#include<set&g...

2018-12-03 23:13:08 129

原创 Google Kickstart round H 2018

网址第一次kickstart体验很迷，感觉题目比想象的简单了ORZ，但是还是发现了自己的很多不足，继续加油吧A暴力写了trie树，用总方案数遍历减去所有不可行方案数即可，不写trie树应该也能过。#include<iostream>#include<stdio.h>#include<algorithm>#include<stri...

2018-11-18 23:28:37 882

原创 2017 CCPC秦皇岛 H Prime Set（二分图匹配）

是一个二分图匹配而我和舟神bbbbbbbbbbbbbbbbb了大概一个小时，不想写二分图，甚至想建网络流模型我也是服了，可能这就是不会算时间复杂度的菜鸡吧题目思路：1.打素数表2.将奇数和偶数分开到两边，因为只有奇数加偶数才可以是素数。3.1特殊处理，如果有两个1，1之间也可以匹配，但优先考虑1和偶数的匹配，此处要注意细节，我用了两个set来减少讨论#include&...

2018-10-18 21:26:12 401

原创 CF 368 div 2（bitset/主席树/二维线段树）

比赛链接C输入三角形的一条边，输出另外两条可以和他组成一个直角三角形的整数边。以前似乎做过，但是忘记了可以的公式，但时间范围很长可以直接递归公式：#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<...

2018-10-14 10:28:59 247

原创牛客国庆集训派对day1 J Princess Principal（RMQ或栈）

题目链接题解1：统计每个括号匹配的位置，统计区间最小和区间最大，如果都在区间内说明是一个有效的序列。题解2：直接用栈统计，通过记录每个括号进栈时栈的状态，来比较得出是否为有序的序列。敲了个RMQ的板子写的很好的BLOg题解1代码（空间和时间其实有点极限）#include<iostream>#include<stack>#include<s...

2018-10-05 11:54:33 161

原创牛客国庆集训派对day1 G Kimi to Kanojo to Kanojo no Koi（构造矩阵）

题目链接本来是想好好打的，但是刚安装上了中国式家长，太想玩了，一直在玩玩玩玩玩，玩到两点多，写了两个签到又开始玩，玩玩玩然后写了一下g又开始玩，玩玩玩，然后下午就写了两个签到和一个g题奇怪的是，感觉其他题目都挺麻烦的，过了几百个人，这题才28个人为了不显得下午什么事情都没干，写一下这个题的题解……可以简单发现奇数是肯定可以构造的，2肯定不可以构造，2的倍数需要一些操作然后因...

2018-10-01 17:04:56 311

原创 HDU 6305 RMQ Similar Sequence（笛卡尔树/概率）

题目链接昨天对着题解看了好久也没看懂那个n!是要干什么题解大概是这样虽然还是没懂这个公式是什么意思，但是我知道为什么答案是了，手动狗头逆元打表的代码void inverse(ll n, ll mod) { inv[1] = 1; for (int i=2; i<=n; ++i) { inv[i] = (ll) (...

2018-09-30 21:04:28 208

原创 HDU 6304 Chiaki Sequence Revisited（分型未补）

看的大佬的博客园，因为没有博客园账号所以没发给大佬点赞！题解用的分形的思想，但是我感觉看不太出来……emmm还好找到了有别的做法QOQ这里收藏了一个求lowbit的方法，因为从来没写过树状数组所以觉得很有意思！ll lowbit(x){ return x&(-x);//大佬可太秀了}题目的做法：1.用log2（n)方的复杂度找到a[n]对应的数字2....

2018-09-29 17:33:14 96

原创 HDU 6302 Maximum Weighted Matching（图论/STL）

神特么图论题ORZORZORZ，fong了大概就是通过一种操作得到一个图，求这个图的最大匹配，和取得最大的可能种数思路倒是很容易看懂，这个代码也太emmm了吧做法：1.按照操作逆着dp，还原回最后只有一条边时的情况2.注意处理每次更新的步骤（刚开始完全没想到还有可能已经存在一条相同的边，更新也一开始想错了3.好多STL的应用，学到辽学到辽，STL真实一窍不通啊 4.补了...

2018-09-29 11:57:14 619 2

原创 2018/9/27 离散大作业根据输入命题输出真值表及主析取（合取）范式

zl老师布置的作业，网上代码都好长，自己写一个才200行自己写就是很开心，抄代码有什么意思呢/*符号注记： + * - -> <-> T F合取析取非单条件双条件 true false 运用的方法：1.将中缀表达式转换为后缀表达式便于计算 2.DFS二进制枚举每个状态并用后缀...

2018-09-27 20:49:22 4066 11

原创 2018 ccpc吉林 H Lovers（线段树）

硬核线段树现在无处补题，输入输出的格式也都忘记了，无法贴代码，先捏一个思路。大意就是每次对于一个区间对这个区间的数字字符串的左边和右边都加上一个同一个数字，询问操作是对区间求和。当时觉得这个题目没有什么思路，就放弃了这道硬核线段树，今天贤神在群里列了一下公式，还是有一点可惜。思路具体如下：1.维护两颗线段树：sum2(k,l,r)= 10^len[ai], (l<=...

2018-09-27 20:40:16 1180

原创 2018 ACM-ICPC南京赛区网络赛 B The writing on the wall

题目单调栈真的是很可爱的东西！应用也很多啊，应该多想想#include<iostream>#include<stdio.h> #include<algorithm>#include<string.h>#include<vector>#include<set>#include<math.h>

2018-09-05 20:56:43 138

原创 2018 ACM-ICPC南京赛区网络赛 E AC challenge

题目比赛的时候想了很多……傻死了，看数据就是写状压，但是比赛完补了题发现自己好像还是算不太清楚状态压缩的时间效率，gay尬好奇：？？？？ #include<iostream>#include<stdio.h> #include<algorithm>#include<string.h>#include<vector&gt...

2018-09-05 19:46:32 176

原创 HDU 1281 棋盘游戏（二分图匹配）

题目今天学了一下二分图匹配，开始写这个题目。刚开始感觉根本不用二分图匹配就可以做啊……emmm然后开始想怎么建图，感觉怎么建图都很麻烦，最后yy了一个不算建图的写法，直接在map里找，然后横坐标和纵坐标算成二分图的两边？写代码真实有趣！有时候思维就是被模板僵化的鸭#include<iostream>#include<stdio.h> #incl...

2018-08-31 20:10:30 91

原创 HDU 6299 Balanced Sequence

题目题目的意思是给你很多个字符串包含‘（’和‘）’，你可以改变这些字符串的顺序但是不能改变字符串本身。问你最多能有多少括号匹配，一个左括号在一个右括号的左边他们就可以匹配。输出匹配书乘2。比赛的时候总觉得自己可以想出来，但是就是怎么排序完全没有思路。看了题解发现自己还有一些理解没有到位，比如说这里的是子序列，所以中间的连接不会有浪费的，不必考虑。题解直接排序，虽然看了题解写了一个排...

2018-08-31 13:36:05 124

原创 HDU 6296 代码派对

题目用了二维前缀和，然后解题的思路感觉像是又嵌套了一个二维前缀和，很奇妙欸用o(n+m^2)可以求出每个格子的覆盖的次数，可求ans1=∑C(sum[i][j],3)，显然这里面有重复的内容。(1)将每个矩形减去最上面的一条边，求此时的ans2=∑C(sum[i][j],3)(2)将每个矩形减去最左边的一条边，求此时的ans3=∑C(sum[i][j],3)(3)将每个矩形同...

2018-08-30 22:47:45 375

原创 HDU 6295 回文树（双指针）

题目直接枚举，没写过双指针，写了一下看了标程，改了一下存图的方法，真滴很妙#include<iostream>#include<stdio.h> #include<algorithm>#include<string.h>#include<vector>#include<set>#include<...

2018-08-29 21:13:42 452 2

原创 HDU 6290 奢侈的旅行

题目题目的思路很简单，又式子可得就是求到达n的时候level最小是多少，又由通过路径的要求可以得，level越大越不可能通过这条路径，所以就是一个跑一遍单源最短路就可以了。默念三遍priority_queue<int> 是大根堆priority_queue<int, vector<int>, greater<int> > 是小根堆 ...

2018-08-29 16:48:48 221

原创 HDU 6289 寻宝游戏

题目看了题解才会写的题，而且题解和标称x和y的含义略有出入，看了巨久才看明白。f[i][j][x][y]表示到达第i行第j列时路径内有x个没取，路径外有y个东西取了的可以达到的最大值。然后向右向下转移即可，需要注意的是向右转移可以直接转移，但是向下转移时还需要考虑当前行左边未访问的格子和下一行当前列之前未访问的格子，需要进行预处理。代码#include<iostream...

2018-08-29 15:29:53 437

原创 HDU 6288 缺失的数据范围

题目思路简单，wa题无数遍，哭了对了个拍，发现log2不可以用log来求，因为不能保证精度，预处理了2的倍数用二分找了。 #include<iostream>#include<stdio.h> #include<algorithm>#include<string.h>#include<vector>#inclu...

2018-08-28 20:49:21 216

原创 HDU 6287 口算训练

题目是有一点思路的，但是因为一直都没有用过vector所以不知道怎么存放。将所有的序列中的数字都分解质因数，用vector[N]存放，查找时使用lower_bound和upper_bound判断这个序列里所有数总和的这个质数出现的次数是不是大于d中这个质数出现的次数就可以了。#include<iostream>#include<stdio.h> #incl...

2018-08-28 18:31:43 247

原创 ARC B the median of the median

题目题目的意思是对于序列a1,a2,……,an，求其中所有子串的中位数组成的序列的中位数。1.在比赛的时候想到了二分答案，但是对于如何进行验证完全没有头绪2.二分答案，对于每个枚举的答案数，求中位数比他小的字串的个数和以其为中位数的字串的个数，就可以通过和n*（n-1)/2+1比较判断该数是不是答案3.实现：将所有>所验证数的答案全都赋值成1，所有<=验证数的答案全都赋...

2018-08-27 21:04:42 148

题目博弈题意思大概是有一个棋盘，黑子总在白子上面，黑子只能往下走，白子只能网上走，在底部或者在顶部的棋子可以选择走一步或者走两步，哪方无法挪动棋子了算输，问：从白子开始挪动棋子，哪方可以获胜1.特殊考虑n==4的情况2.n>4时不用考虑双方都在顶端的情况，因为如果可以在其他列完成后获胜，在后手进入该状态也能获胜3.其他情况因为白先手，只要先把对方逼的不得不走joker（在底部或在顶部的棋子）...

2018-07-15 15:13:24 189

原创 HDU 1811 Rank of Tetris

之前写了没调，今天捏了一个小样例就过了，卒今天苟完了粗糙的推箱子大作业，太丑陋了，但是认真敲代码的感觉真好不能再赖床了，要认真学习是一go并查集+拓扑排序，有俩处理：1.等于的把他们合并在一起变成一个2.最后拓扑排序的时候，如果队列里有大于一个元素，说明排列不唯一题目#include<iostream>#include...

2018-07-05 20:29:02 123

原创 CF 55D Beautiful numbers

天啊，期末考终于结束了，真的好久没有打代码了！今天日常感叹一句，fxy也太菜了吧！徐老师也太强了吧！题目大意就是，求一个[l,r]区间里所有能被【自己所含有的数字】整除的数字的个数。1.要用sum%(x*n)%x==sum%x来处理2.最小公倍数的处理（二进制存不下丫3.徐老师太强了#include<iostream>#include<algorithm>#includ...

2018-06-30 12:01:31 114

oidoidoid的博客