pubgoso-CSDN博客

原创一些需要注意的小细-持续补充

1.函数传参问题。2.不应在函数中声明较大的变量3.尽量降低函数调用次数，合并相同操作，减少函数调用次数4.变量重复命名问题，尽量使用具有实际意义的变量名5.其他。。。。

2020-11-14 12:47:56 77

原创个人感悟-持续更新(想起来就更吧？

写在前面：如果你看到这篇文章，或许你曾经也跟我一样，经历过绝望，也曾心怀信心。比赛的一些感悟：1.2019.10.00从大一到现在打的比赛也很多了，感觉最重要的还是心态吧（当然水平是第一位），心态稳定的话，就能放下心来仔细思考题目，才可能去解决问题。就拿最近的一次哈尔滨ccpc来说吧，第一发签到题wa了之后就有点着急了，然后下三发签到都平稳度过，卡在了第4题上，卡了4个小时…成功卡到铁牌。...

2019-10-22 12:02:21 457

A.最美合数思路：预处理处理每个数多少个因数，遍历a到b找最大的即可。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 2e6+3;#define fi first#define se second#define pb push_back#define wzh(x) cerr&

2021-04-25 12:39:59 1791

原创 leetcode 5. 最长回文子串(马拉车)

题目链接思路：马拉车算法。。主体大概是：先将字符串用一个特殊字符分隔开，这样就不用讨论奇偶了。然后，定义一个ex数组，表示以i位置为中心的回文串的一半长为ex[i]（整体即为2*ex[i]+1）然后我们枚举每个中心位i。但是直接枚举的话肯定最劣复杂度会退化至O(N2)O(N^2)O(N2)。所以我们需要用到前面算完的ex数组。记录x+ex[x]最大的位置x，如果x+ex[x]大于i的话，找到i关于x的对称点x-(i-x) 记为y，那么我们就可以利用ex[y]来省略一些判断，即我们可以跳过一些字

2021-03-31 23:23:02 160

原创 2019icpc 南昌邀请赛 A. Attack (斯坦纳树)

题面链接思路：斯坦纳树模板。处理出以i为根节点，集合j中的点全联通的最小代价。然后由于要4对相互连通，。。。就相当于选不超过4个子树来凑成合法方案。显然又是另一个状压dp。。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 55;#define fi first#define

2020-12-25 00:23:31 287

原创 2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) K - Computer Cache

题目链接第一眼看到这个题目以为是平衡树类的题，但是这样内存不太行（很大可能是我没做多少平衡树的题我们把m个数组拉成一个数组，赋予连续的编号，区间赋值相当于就是线段树上区间赋一个等差数列。我们询问的时候可以单点查询这个位置具体是哪个数组的哪个元素。由于m个数组存在的区间更新问题。所以我们可以更新线段树的时候加上一个时间戳。把更新操作加上时间戳全都提出来，询问操作也提出时间戳存下来。问题就转变成了一个区间加法加单点查询的问题了。。。#include <bits/stdc++.h>usi

2020-12-20 11:00:02 352 1

原创 2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) F - Carny Magician dp

题目链接套路题，枚举每一个位置放什么。。。具体来说，设我们当前枚举到的位置为i，有j个未选的且>=i 的数，还剩下m个位置未匹配。我们有三种case来转移当前状态。长度为i 有j个可能匹配的剩余数还有m个位置要填 case 1: 第一个不匹配放前面i-j个不合法的位置 <<== i-1 j-1 m *(i-j) case 2: 第一个不匹配放后面的j-1个中的一个<<== i-1 j-2 m *(j-1 ) case 3 第一个匹配 <<=

2020-12-20 10:53:10 363 1

原创 2020-2021 ACM-ICPC Brazil Subregional Programming Contest M - Machine Gun

题目链接敌人(x,y)(x,y)(x,y)能被(xm,ym)(x_m,y_m)(xm,ym)打中当且仅当：ym−x−xm2≤y≤ym+x−xm2y_m- \frac{x-x_m}{2}\leq y\leq y_m+\frac{x-x_m}{2}ym−2x−xm≤y≤ym+2x−xm我们化简一下这个不等式，x,yx,yx,y放一边，xm,ymx_m,y_mxm,ym放一边:{ 2y−x≤2ym−xm−2y−x≤−2ym−xm\begin{cases}~

2020-12-16 14:55:53 472

原创牛客挑战赛46 E.反演

设d(n)=∑i=1n[nmod i=0],s(n)=∑i=1nnid(n)=\sum\limits_{i=1}^n[n\mod i=0],s(n)=\sum\limits_{i=1}^n\frac{n}{i}d(n)=i=1∑n[nmodi=0],s(n)=i=1∑ninans=∑i=1n∑j∣md(ij)=∑i=1n∑j∣m∑x∣i∑y∣j[(x,y)=1]ans=\sum\limits_{i=1}^n \sum\limits_{j|m}d(ij)=\sum\limits_{i=1}^n \s

2020-12-15 19:41:00 170 2

原创 2020icpc 上海 E.The Journey of Geor Autumn dp

题目链接思路：长度为n的序列中最小的数必须要放在1-k的位置上，然后最小的数就会把整个序列分成两半，左边可以任意放置，右边等价于一个新的合法序列。那么可以得到一个O(nk)O(nk)O(nk)的dp转移：for(int i=1;i<=n;i++){ for(int j=1;j<=min(i,k);j++){ dp[i]+=dp[i-j]*C(i-1,j-1)*fac[j-1]//[1,j-1]的位置随意放，那么从i-1个数挑j-1个让他们全排列即可 }}那这个数据范围

2020-12-15 15:00:02 710 1

原创 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest A.Flying Squirrel 单调栈+区间最大值+dfs

思路：先预处理出每个元素i的最大值覆盖区间[li,ri][l_i,r_i][li,ri]。然后让i和[li,i),(i,ri][l_i,i),(i,r_i][li,i),(i,ri]中的最大值连边。随后dfs从最大值开始dfs找到每个点的深度和距离所有子节点的最大距离。询问y=0 即找到子节点的最大距离。询问y!=0 ：先判断大的值的区间是否能覆盖到小的值，能覆盖答案显然就是两者的深度之差。细节见代码：#pragma GCC optimize(2)#pragma GCC optimize

2020-12-09 17:21:41 169

原创 Educational Codeforces Round 66 (Rated for Div. 2) F. The Number of Subpermutations hash

题目链接思路：我们给每个数字iii分配两个64位的随机数，构成一个128位的随机串stist_isti。那这样一个长度为kkk的子排列的区间hashhashhash的异或和就等于⊕i=1kst[i]\oplus_{i=1}^kst[i]⊕i=1kst[i]因为1必须被包含进去，那我们以1为左端点l，枚举右端点r，设max⁡lr=k\max_l^r=kmaxlr=k，那么就check一下[r−k+1,r][r-k+1,r][r−k+1,r]是否为一个子排列。再倒着做一遍，正确性显然。特判一下

2020-12-08 23:41:53 101

原创 Educational Codeforces Round 66 (Rated for Div. 2) E - Minimal Segment Cover （倍增）

思路：考虑一个暴力的过程：一定是从r出发取覆盖r且左边界最小的线段，不断重复这个过程。那么可以采取倍增预处理dpijdp_{ij}dpij表示从j开始取了2i2^i2i个线段的左边界。初始dp0,jdp_{0,j}dp0,j等于覆盖j的所有线段中左边界的最小值。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;

2020-12-08 15:05:07 97

原创 2016-2017 ACM-ICPC CHINA-Final G.Pandaria

#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 2e5 + 10;#define fi first#define se second#define pb push_back#define wzh(x) cerr<<#x<<'='<<x<.

2020-12-07 19:21:32 207

原创 G. Forbidden Value 动态开点线段树

题目链接思路：考虑dpijdp_{ij}dpij表示在一个ififif框内，执行到第iii次操作时，获得值为jjj的最小花费。初始只有进入该ififif时的初值有一个代价，其余都是无穷大。那么如果时set y vset ~~y~~vset y v的话，任意不等于yyy的值都必须花费vvv的代价来跳过这一次操作从而不成为yyy，而yyy可以从其他任意值转移过来(注意不能等于xxx)。那么这样就可以用一个线段树来维护一

2020-12-03 23:27:34 170

原创 hdu5528 Count a*b

题目链接#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef unsigned long long LL;const int N = 2e5 + 10;#define fi first#define se second#define pb push_back#define wzh(x) cerr<<#x<<'

2020-12-03 10:22:16 125

原创 hdu6000Wash 贪心

题目链接洗衣和烘干是可以独立考虑的，先计算出n件衣服的最小洗完时间。，然后再让最后洗好的衣服用最快的烘干机烘干。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10;#define fi first#define se second#define pb push_

2020-11-29 11:55:51 116 1

原创 hdu6007 Mr. Panda and Crystal (最短路+完全背包)

题目链接思路：先求出每个道具的最小造价，再跑完全背包即可。我们不停的用当前已得最小造价的道具来更新当前道具可以合成的道具，类似于dij求最短路那样。就能获得每个道具的最小花费了。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 2e5 + 10;#define fi first

2020-11-29 11:50:47 174

原创 hdu5937 Equation爆搜+剪枝

题目连接ps:比赛的时候刚看到题以为是网络流，后来因为建不出来图被推翻了。然后就想不出来怎么做。。根本没往dfs+剪枝的方向想。。思路：答案最多是36，考虑先把能取满36的情况给特判掉。之后在dfs。用可行性和最优性剪枝就能通过此题。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N

2020-11-26 17:59:25 84

原创 hdu 5970 最大公约数

由于数据是随机的，所以每组数据都O(m2c)O(m^2c)O(m2c)来跑就能过…没有想到枚举c来做 …以后遇到这种推式子的多试试枚举几个#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 2e5 + 10;#define fi first#define se second#de.

2020-11-24 00:10:28 126

原创 Educational Codeforces Round 98 (Rated for Div. 2) E. Two Editorials 细节题

题目连接真细节题… 选了一个很复杂的做法。枚举第一个作者AAA选的框，枚举选手iii。你会发现另一个作者BBB选的框对于选手iii来说，会有一些右端点连续的区间比AAA更优。那这样就可以知道作者BBB选哪些框更优并且也能用二次差分统计出优多少。搞完所有选手后，找出作者BBB选哪个框最优即可。二次差分的模板：void add(int l,int r,int op,int d){ //区间[l,r] 加上op为首项，d为公差的等差数列 tw[l]+=d;

2020-11-20 20:46:35 1124 1

原创 2020 China Collegiate Programming Contest Changchun Onsite F. Strange Memory 树上启发式合并

题目链接比赛的时候拆位然后跑了18次dfs。。。然后快乐的tle。思路：对每一个数都开一个二维数组记录二进制位上的信息。开个map存一下每个节点的信息，然后启发式合并的时候就模拟题意即可。。这样的话map的访问次数就是nlognnlog_nnlogn级别的，比跑18次dfs足足少了一个log。。。加上unordered_map的玄学速度。比跑18次不知道快到哪里去了。#include <bits/stdc++.h>using namespace std;#define pb pus

2020-11-14 18:00:29 435

原创 2020 China Collegiate Programming Contest Changchun Onsite J. Abstract Painting 状压dp

题目链接比赛的时候，是对圆心进行考虑的状压，没有写出来…，但其实对圆的左右边界进行考虑的话会容易很多。思路：因为是圆，所以满足条件的必然只有三种位置关系：相切，包含，相离。1.考虑两个圆[l1,r1],[l2,r2][l1,r1],[l2,r2][l1,r1],[l2,r2]，当l2>=r1∥r2>=r1&&l2<=l1l2>=r1\|r2>=r1 \&\& l2<=l1l2>=r1∥r2>=r1&&l2&

2020-11-14 17:49:28 358

原创牛客练习赛62 D.brz的函数

∑i=1n∑j=1nμ(ij)=∑i=1nμ(i)∑j=1nμ(j)[gcd(i,j)=1]=∑i=nnμ(i)∑j=1nμ(j)∑d∣gcd(i,j)μ(d)更改枚举顺序得：∑i=nnμ(i)∑d∣iμ(d)∑j=1⌊nd⌋μ(jd)再次更改枚举顺序得：∑i=1nμ(i)∑j=1⌊ni⌋μ(ij)∑j=1⌊ni⌋μ(ij)设S(n,m)=∑j=1mμ(jn)代入原式得:∑i=1nμ(i)S2(i,ni)通过预处理之后可以O(n)计算每组的答案。但是题目显然是要处理出所有答案。我们观察发现计算答案一定是这样

2020-11-06 22:54:02 154

空空如也

空空如也