穷源溯流-CSDN博客

原创 ABBYY Cup 3.0 E3. Summer Homework（线段树+思维+斐波那契）

题目就是要求完成上述操作，每次操作 2，都要输出结果const ll mod=1e9;const int N=2e5+5; int n,m; int i,j,k; int a[N]; ll f[N],sum[N]; struct Node { int l,r,len; ll s1,s2,lazy; void init(int l,int r){ ...

2021-03-15 17:27:30 228

原创 Codeforces Round #558 (Div. 2) B2 - Cat Party (Hard Edition) （思维）

给出 n 个数，找出一个最大的 x，使得前 x 个数中任意删除一个数之后，其余数字的出现个数相同可以利用两个数组，f 数组表示 a[i] 的出现次数，F 数组表示 a[i] 的出现次数的出现次数如果，说明在添加一个数即可成立如果，说明在 i 位置成立const int N=2e5+5; int n,m; int i,j,k; int a[N]; map<int,int> f,F; int main(){ ...

2021-03-10 20:00:17 192

原创 Manthan, Codefest 17 B. Marvolo Gaunt‘s Ring（线段树+思维）

有 n 个数，以及 p，q，r要求找到三个数使得最大，其中由于题目具有后效性，开始没有注意到，枚举 i∈[1,n] 使得 a[i]*p，然后用线段树找到 j∈[i,n] 使得 a[j]*q，再找到 k∈[j,n] 使得 a[k]*r，但是这样的做法是不对的，只能过到 12 个样例因为每一步都是最优的，并不能代表整体最优如果枚举 j，在从区间 [1,j] 和 [j,n]分别找 i 和 k 的话这样是正确的，其余上述的做法不同的是，上述做法没有考虑后效性而缩小了区间范...

2021-03-08 19:59:59 190

原创 Codeforces Round #703 (Div. 2) C2 - Guessing the Greatest (hard version)（二分+思维）

有 n 个数构成一种排列，每次询问一个区间，可以给出区间中第二大数的位置，在 20 次询问中找到区间最大数的位置又是一道交互题，一眼二分一开始想的是对于区间询问其第二大数的位置 pos，然后再查询区间中的第二大数的位置，如果两者相同，那么一定在，否则在中，但是策略被卡，询问次数过多值得注意的是题目一开始就可以得到中的第二大数的位置，利用这个位置与 mid 就可以完成 logN 的复杂度但是中间需要注意区间中第二大数的位置 pos 是固定的，二分过程...

2021-02-20 21:58:43 215

原创 Educational Codeforces Round 103 (Rated for Div. 2) C. Longest Simple Cycle（思维）

有 n 条链，给出这 n 条链的长度 c[i]-1，从第二条链开始，a[i] 表示第 i 条链的头节点 1 链接前一条链的 a[i] 节点，b[i] 表示第 i 条链的尾节点链接前一条链的 b[i] 节点，在整张图中找到一个环，使得换的长度最大题目与图没有任何关系，我们可以发现 a[i]=b[i] 时，之前所形成的链一定要断，即此时的 a[i] 一定是环中度为 2 的节点如果 a[i]!=b[i] 那么就要判断是以之前的链继续，还是从 a[i] b[i] 开始重新建一条链（...

2021-01-31 10:23:06 215

原创 Educational Codeforces Round 100 (Rated for Div. 2) C. Busy Robot(模拟+思维)

给出 n 个操作，t[i] x[i] 表示在 t[i] 时刻开始移动至 x[i] 位置，如果机器人在某一时刻正在移动，那么他将不听当前操作，继续执行原来的操作，如果静止，那么执行当前操作，初始时静止由于题目将时间和空间相关联，思路比较绕；首先要明白如果机器人不动，其位置不改变但是时间一直改变设计四个量 pos,tag 为当前位置和目标位置，cur,next 为当前时间和移动结束时间，这样next=tag-pos+cur 等式成立，将时间和空间关联起来这样就比较容易想...

2021-01-26 15:59:20 297

原创洛谷 P3072 [USACO13FEB]Perimeter S（dfs）

题目保证所有的草堆构成连通块，我们可以用 dfs 很简单的获得各个草堆的相对位置如上图所示，白色的方块为草堆的位置，那么他的外周长是绿色的方块个数，其中红色方块个数的贡献是二，也就是说绕着外周长的外面走一圈，看看当前方格挨着几个草堆，这样通过 dfs 就可以将问题解决了。遍历所有的绿色/红色方块一次且仅以此，搜索到白色那么 ans+1，此方块的任务结束const int N=2e5+5; int n,m; int i,j,k; //int a[N];...

2021-01-17 16:41:09 313

原创 Educational Codeforces Round 101 (Rated for Div. 2) C. Building a Fence（思维+贪心）

题目要求修建栅栏，第一块栅栏和最后一块栅栏必须放在地面上，第 i 个栅栏所处的地面为 h[i] ，那么该栅栏可以放在 [a[i],a[i]+k-1] 的位置，要求每一块栅栏都必须与前一块栅栏相重合至少 1 个单位格子，问是否可以修建这样的栅栏对于每一块栅栏我们可以维护改栅栏最低端所能处的位置，根据当前地形位置与前一个地形位置的关系，判断是否可以修建该栅栏const int N=2e5+5; int i,j,k; int n,m; int a[N];...

2021-01-14 14:57:03 245 1

原创 Educational Codeforces Round 99 (Rated for Div. 2) D. Sequence and Swaps(贪心+枚举)

给出 n 个数，以及数 x ，将这 n 个数变成递增的序列，如果 x 想要于其中的任何一个数 a[i] 交换，那么满足条件 a[i]>x ，问最小交换次数是多少题目数据范围小，可以暴力模拟，但在这里并没有模拟，但复杂度还是 O(n*n)将 x 与 a[i] 交换后，a[i] 之前全都是比 x 要小的数，i 之后没有比 x 大的数，且前面的数必须要单调递增，否则没法操作由于 a[i]>x ，那么经历多次交换之后，那么数组 a 中有一个比 x 大的数被换成 x而且每...

2020-12-24 09:29:49 129

原创洛谷 P5889 跳树（线段树）

题目对于二叉树的知识点的考察直接拉满其实很容易发现对于只有 1，3 的序列是很容易维护的，但是同时要维护右儿子，需要清楚到底要维护什么设当前序列已经有 x 个有效的右儿子，(有效的意思是没有被访问父节点的操作抵消掉)那么其对答案的贡献值应该是剩下的就是找到有多少个有效的右儿子即可，由于这个序列会构成一棵树那么树的根，也就是深度最低的那个节点开始才记录有效的右儿子，不仅仅是右儿子，还有左儿子既然要维护树的根，不妨将维护这个序列转化为维护树的根，与树的右子树的深度...

2020-12-19 13:12:50 385 1

原创洛谷 P5026 Lycanthropy（差分×2）

题目看上去用差分应该不难，一开始的时候打算开两个数组来维护差值的前缀和与后缀和，但是考虑的情况很多，经过化简之后，可以只维护前缀和题意要搞清楚，要考虑到所有点，我就是因为当数组越界的时候不管，一直找不出错来为了防止数组下标是负数，数组从 -3*v 作为原点差分过后，一遍前缀和是点 x 与 x-1 的差值，所以需要再跑一遍前缀和const int N=1e6+5; int i,j,k; int n,m; int a[N]; int d[N&l...

2020-12-03 11:40:03 369

原创洛谷 P2672 推销员（线段树+贪心）

假设走过了 {pi,pj,pk} 家住户，那么疲劳时最大是 max{pi,pj,pk}(最远距离)+sum{pi,pj,pk}(每户人口积累的疲劳值)所以我们只要维护区间最大值与区间和即可，但是现在有一个问题，不知道维护哪一段区间，如果下一步能够想到贪心，这个题应该可以解决了按照 A 的大小降序排序，如果 A 大 S 大，那么毫无疑问如果 A 小 S 大，如果 S 足够的话，也会被选择如果 A 大S 小，只有可能被 2 这种情况取代const int N=1e...

2020-11-30 11:51:38 286

原创洛谷 P2205 [USACO13JAN]Painting the Fence S（差分+思维）

可以利用差分的思想，在区间 [l,r] 的起点 l 处 col+1，在 r+1 处 col-1，这样再根据当前 col 的值与 k 值比较，可以发现当 col 刚刚被加至 =k 时，之后的区间才会对答案有贡献当 col 刚刚被减至 <k 时，之前的区间会产生贡献所有区间遍历完毕，col=0，即不会产生遍历完所有区间还有区间又贡献的情况最后要注意，题目中要求的涂块，而不是涂点const int N=1e5+5; int i,j,k; int n,m;...

2020-11-30 10:43:13 466

原创 Codeforces Round #340 (Div. 2) E. XOR and Favorite Number（莫队+前缀异或）

给出数 n，m，k ，现在有 n 个数，m 此询问，每次询问给出 l,r 代表区间，求任意满足条件的的 l <= i <= j <= r 的 i ，j 使得 a[i]^a[i+1]^……a[j]=k，求可以找出多少对 <i,j> 这样的二元组离线问题，我们采用莫队的方法来求解但是想要求得任意一个区间的异或值比较困难，由异或运算可得 a^b=k ---> k^b=a所以每一次更新莫队时，例如添加一个数时，因为他不是在左端点添加就是在右端点添加，所...

2020-11-22 20:09:53 204

原创训练总结

从两个月之前开始放慢题目进度，不再追求出题量，而是思考如何从题目当中获得解决方法，一道题目在两周之后重新做一遍，这样思路方面不会再有太大的阻挠，而且还会更容易的简化代码。在之前的练习中太追求解题数量，而没有关注题目质量，思维上还只停留在表面，所以 cf， at 的比赛几乎每场都打，遇到自己陌生的专题直接跳过，而相对了解一点的就先去寻找与之相关的题目，然后再去解决此问题。但是也因为如此，题目数量太多，有些补不过来了，就目前的情况来说，就思维方面可以想到一些理所当然的技巧，对于一知半解的题解也懂得取舍，想的也

2021-08-02 18:07:12 339

原创训练总结

最近的的比赛有点多，题目补了一段时间，从最近的训练也可以看出一些问题，队内比较松散，完全没有刚打完比赛之后的斗志。而我也发现了自己最大的弱点，不想思考，由于之前一直陷入题海，完全陷入了错误的决断当中，现在想把之前做过的题在做一遍，自己写的代码和看过别人的代码之后在写出来的代码完全是两份不一样的代码；无论最近做过的 codeforces，还是 atcoder ，我都想提升自己的思维能力，在这周里面，周一做的题目，周六再做感觉还是有些陌生，现在就要多看题，然后回顾之前的题，希望这次我找对了路...

2021-06-06 22:27:59 360

原创洛谷 P2158 [SDOI2008]仪仗队（gcd）

题目描述作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。现在，C君希望你告诉他队伍整齐时能看到的学生人数。输入格式共一个数N 输出格式共一个数，即C君应看到的学生人数。输入输出样例输入 #1 4 输出 #1 9 说明/提示【数据规模和约定】对于 100% 的数据，1 ≤ N ≤ 40000 对拍代码： .

2021-05-26 17:21:31 511

原创洛谷 P3166 [CQOI2014]数三角形（gcd+组合计数）

题目描述给定一个 N×MN\times MN×M 的网格，请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。输入格式输入一行，包含两个空格分隔的正整数 MMM 和 NNN 。输出格式输出一个正整数，为所求三角形数量。输入输出样例输入 #1 2 2 输出 #1 76 说明/提示数据规模与约定对于全部的测试点，保证 1≤N,M≤10001\le N,M\le10001≤N,M≤1000。 const int N=1e6+5; //int n.

2021-05-23 16:45:20 413

原创 Manthan, Codefest 16 A - Ebony and Ivory（扩展欧几里得）

A. Ebony and Ivorytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputDante is engaged in a fight with "The Savior". Before he can fight it with his sword, he needs to break its shields. ...

2021-05-22 17:54:22 222

原创 SGU 106. The equation(扩展欧几里得)

106. The equation time limit per test: 0.25 sec. memory limit per test: 4096 KB There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how many integer roots of this equation are satisfy to the follo...

2021-05-22 16:17:17 428

原创牛客NC19485 Utawarerumono(gcd)

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1048576K，其他语言2097152K 64bit IO Format: %lld题目描述算术是为数不多的会让Kuon感到棘手的事情。通常她会找Haku帮忙，但是Haku已经被她派去买东西了。于是她向你寻求帮助。给出一个关于变量x,y的不定方程ax+by=c，显然这个方程可能有多个整数解。Kuon想知道如果有解，使得p2*x2+p1*x+q2*y2+q1*y最小的一组整数解是什么。为了方便，你只需要输出p2*x2...

2021-05-22 13:29:15 234

原创洛谷 P3398 仓鼠找sugar（LCA）

const int N=1e5+5; int n,m,_; int i,j,k; int a[N]; vector<int> G[N];int dep[N],fa[N],sz[N],son[N];void dfs1(int u,int f){ dep[u]=dep[f]+1; fa[u]=f; sz[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u..

2021-05-17 14:30:30 243

原创洛谷 P1757 通天之分组背包（分组背包）

这应该是分组背包的裸体了分组背包其实就是将每一组看作 01 背包，然后求解，那么对于每一组来说该怎么办是接下来讨论的问题；for(int j=m;j>=0;j--){ for(int k=1;k<=n;k++){ dp[j]=max(dp[j],dp[j-w[k]]+v[k]) }} 上面这段代码需要理解，意思是从 n 件物品中选出 1 件可以容纳下的物品的最大价值，所以分组背包的解决方法也就清楚了const int N=1e3+5; int n,m,.

2021-05-16 15:11:20 493

原创洛谷 P1833 樱花（混合背包+二进制优化）

const int N=1e4+5; int n,m; int i,j,k; //int a[N]; int dp[N]; struct Pack { int w,v,p; void read(){ sddd(w,v,p); if(p==0) p=1e6; } }b[N],a[N<<5]; int tot=0; int...

2021-05-16 13:30:43 283

原创洛谷 P2163 [SHOI2007]园丁的烦恼（主席树）

const int N=5e5+5; int n,m,_; int i,j,k; //int a[N]; struct Node { int l,r; int sz; }t[N<<5]; struct point { int x,y; void read(){ sdd(x,y); } bool operator<(point ...

2021-05-16 10:05:22 244

原创洛谷 P3810 【模板】三维偏序（陌上花开）（cdq分治）

const int N=2e5+5; int n,m,_; //int i,j,k; struct Node { int x,y,z; int w,ans; void read(){ sddd(x,y,z); } }a[N],b[N]; int c[N]; int f[N];bool cmp(Node a,Node b){ if(a.x==b.x){ if(...

2021-05-12 13:36:01 281

原创洛谷 P2345 [USACO04OPEN]MooFest G（树状数组）

const int N=2e4+5; int n,m,_; int i,j,k; //int a[N]; struct Node { int pos; int val; bool operator<(Node o){ return val<o.val; } void read(){ sdd(val,pos); } }a[N];...

2021-05-11 19:00:47 369

原创洛谷 P1095 [NOIP2007 普及组] 守望者的逃离（dp）

const int N=3e5+5; int n,m,_; int i,j,k; int a[N]; int dp[N]; int main(){ //IOS; int t; while(~sddd(m,n,t)){ for(int i=1;i<=t;i++){ if(m>=10){ dp[i]=dp[i-1]+60; ...

2021-05-11 17:14:57 350

原创洛谷 P1020 [NOIP1999 普及组] 导弹拦截（dp）

const int N=2e5+5; int n,m,_; int i,j,k; int a[N]; int dp[N]; bool vis[N]; int main(){ //IOS; n=0; while(~sd(a[++n])){} n--; int maxx=0,ans=0; for(int i=1;i<=n;i++){ dp[i]=1; for...

2021-05-11 16:00:59 531

原创洛谷 P4587 [FJOI2016]神秘数（主席树）

这题竟然是ICPC的原题，哦不，ICPC竟然是福建省的原题M.Stone Gamesconst int N=2e5+5; int n,m,_; int i,j,k; int a[N]; struct Node { int l,r; ll sum; }t[N<<5]; int root[N],tot=0;void update(int &x,int y,int l,i...

2021-05-10 18:42:14 226

原创洛谷 P2633 Count on a tree（树上主席树）

emmmm，题目一直 RE，知道不知道怎么 AC 之后，然后之前 RE 的代码也好了，我是不是把洛谷的测评机玩坏了const int N=2e5+5; int n,m,_; int i,j,k; int a[N]; struct Node { int l,r; int sz; }t[N<<5]; int root[N],tot=0; vector<int> G[N],...

2021-05-10 16:53:42 226

原创关于省赛打铁这件事

这次省赛打铁只能说是意料之外情理之中，在过去的一周训练里，我们队的诟病就是出题全在后两个小时，但是训练的时候毫无压力，也没有将这件事情放在心上；昨天我的状态并没有什么问题，但是在之前的训练中，前几天的思维也很活跃，手速也跟的上，但是后来思路全都交给了 lxh 来负责，自己只是一个无脑的代码打印机，省赛之前我还是信心满满，十几道题应该不会很难，虽然这次的题目应该是没有难的拿不了奖，但是谁也没有预料到正式比赛的紧张程度会让我们乱了阵脚；一开始没有成功签到，其实这个时候就已经慌了，3 个小时之后才拿到第一

2021-05-10 12:26:32 496

codeblocks17.12安装包.zip

空空如也