verdin黄大锤-CSDN博客

原创 2022牛客寒假算法基础集训营5 K造梦小孩

题目：造梦小孩众所周知，九峰喜欢玩造梦西游。孙悟空是造梦西游工作室的宠儿，从七魔王到上古天帝篇最强的角色都是孙悟空，九峰在用悟空通关了造梦西游1-5后决定重新玩一遍唐僧，希望能磨练自己的技术，而不是啥boss都无脑火魔斩就行了。于是他对唐僧的技能做了一些研究：唐僧的攻击技能只有三种：1.冰龙波，这是个废物技能，我们不会去用它2.水魔爆，进行对点打击，破坏力巨大3.玄冰阵，以人物为中心进行范围伤害，在左右一定距离处从地面向上穿出两颗冰刺，然后能量传递到两倍距离远处穿出同样的冰刺，三倍，四倍，以此

2022-02-22 22:34:20 259

原创 2022牛客寒假算法基础集训营6 G迷宫2

题目：迷宫2有一个n*m的迷宫，迷宫第i行第j列上标着一个方向ci,j∈{L,R,U,D}，牛妹站在格子(1,1)，出口在格子(n,m)(n,m)，牛妹想要走出迷宫，但牛妹只会按以下策略走：设牛妹当前在格子(x,y)(x,y)，则若cx,y=L，则牛妹下一步走到格子(x,y-1)(x,y−1)若cx,y=R，则牛妹下一步走到格子(x,y+1)(x,y+1)若cx,y=U，则牛妹下一步走到格子(x-1,y)(x−1,y)若c_{x,y}=D，则牛妹下一步走到格子(x+1,y)(x+1,y)

2022-02-18 23:07:17 306

原创 cf1628 C. Grid Xor

Note: The XOR-sum of set {s1,s2,…,sm} is defined as s1⊕s2⊕…⊕sm, where ⊕ denotes the bitwise XOR operation.After almost winning IOI, Victor bought himself an n×n grid containing integers in each cell. n is an even integer. The integer in the cell in the i.

2022-01-23 21:52:59 710 2

原创 cf1617D. Too Many Impostors

D1. Too Many Impostors (easy version)D2. Too Many Impostors (hard version)这是一道交互题。有n个人，分为0、1两类，二者的数量均大于 n/3 小于 2n/3 。一次询问可以询问三个人(a,b,c)中0的数量多还是1的熟练多，最多进行 2n (easy version) / n+6 (hard version)次询问，要求输出这n个人中所有的0。easy version:先做n次询问 (1,2,3), (2,3,4),

2021-12-19 20:10:09 203 1

原创 cf1609E. William The Oblivious

William The Oblivious题意：给一个仅含abc的字符串，每次操作可以修改某一位的字符。每次操作后，要求输出最少删除多少个数可以使字符串中不含有子序列abc。建立一个线段树，a[],b[],c[],ab[],bc[],abc[]a[],b[],c[],ab[],bc[],abc[]a[],b[],c[],ab[],bc[],abc[]代表使得区间中没有子序列a,b,c,ab,bc,abc最少删除的字符数。a[o]=a[lson]+a[rson];b[o]=b[lson]+b[

2021-12-08 20:23:49 276

原创 cf1614C. Divan and bitwise operations

C. Divan and bitwise operations题意：有一个长度为n的序列，有m条信息 l r k ，指该序列从l到r所有元素或(or) 起来为k。求该序列所有子序列的异或和(xor)的代数和。思路：对于每一位，若区间或为000，那么一定每个元素都为000。序列做差分，如果该区间为或1，那么c[l]+1c[l]+1c[l]+1，c[r+1]−1c[r+1]-1c[r+1]−1。如果为0，c[l]+infc[l]+infc[l]+inf，c[r+1]−infc[r+1]-infc

2021-11-28 20:26:14 476

原创几道斜率优化

见注释，注意一下由于要移项，所以x一定要是大减小！任务安排 1 2 3#include<bits/stdc++.h>using namespace std;#define read(x) scanf("%d",&x)#define inf (1LL<<60)#define maxn 5000 #define maxS 50#define maxw 100#define ll long longint n,S;int t[maxn+5],c[maxn+

2021-11-20 20:40:37 240

原创换根dp 2021江西 gym103366I. Homework

I. HomeworkTsiying has a sequence of positive integers with a length of n and quickly calculates all the factors of each number. In order to exercise his factor calculation ability, he has selected q consecutive subsequences from the sequence and found a

2021-11-10 15:38:13 317

原创 2021江西 gym103366G. Magic Number Group

Magic Number GroupTsiying has a sequence of positive integers with a length of n and quickly calculates all the factors of each number. In order to exercise his factor calculation ability, he has selected q consecutive subsequences from the sequence and

2021-11-08 21:27:17 128

原创 2021年中国大学生程序设计竞赛女生专场 gym103389F 地图压缩

F. 地图压缩你正在参与一款2D游戏的地图绘制，你拥有的美术素材是一张 n×n 的像素图片，从上到下依次编号为第 1 行到第 n 行，从左往右依次编号为第 1 列到第 n 列，其中第 i 行第 j 列的像素坐标为 (i,j)，它的内容可以用一个小写字母 pi,j 来表示。你希望从这张素材中裁剪出一个连续的矩形区域作为游戏的地图。你进行了 q 次尝试，每次尝试中你将会选择以 (x1,y1) 为左上角、(x2,y2) 为右下角的矩形部分（包括端点）作为游戏的地图。通过不断地尝试，你发现可以通过应用"四方连

2021-11-02 20:50:39 2782 3

原创 2021年中国大学生程序设计竞赛女生专场 gym103389C 连锁商店

C. 连锁商店比特山是一个旅游胜地，它一共有 n 个景点，按照海拔高度从低到高依次编号为 1 到 n。为了更好地帮助游客们欣赏这里的风景，人们在上面搭建了 m 条缆车路线。每条缆车路线只可能把游客们从某个海拔较低的景点运送到另一个海拔较高的景点。在每个景点都有一家纪念品连锁商店，其中第 i 个景点的商店隶属第 ci 号公司，两家连锁店 (i,j) 隶属同一公司当且仅当 ci=cj。每家公司都有新客优惠活动，其中第i家公司对于新客的优惠红包为 wi 元，一旦领取了隶属该公司的某家连锁店的一份红包，就不能

2021-11-02 20:40:55 653

原创 CF607B. Zuma

Zuma给一个序列，每次操作可以取出一个回文串，两侧的数字会向中间合并。问最少操作次数。区间dp，f[i][j]f[i][j]f[i][j]代表取完区间[i,j][i,j][i,j]的操作次数。f[i][j]=min(f[i][k]+f[k+1][j])f[i][j]=min(f[i][k]+f[k+1][j])f[i][j]=min(f[i][k]+f[k+1][j])。a[i]==a[j]a[i]==a[j]a[i]==a[j]时，f[i][j]=f[i+1][j−1]f[i][j]=f[i+

2021-10-28 20:52:25 116

原创 P2656 采蘑菇（卡精度）

P2656 采蘑菇一个强连通分量里的所有蘑菇都可以被采完。先缩点，得到一个DAG，拓扑排序，然后DP。要注意拓扑排序的起点不是题目给的起点。WA四个点的原因是精度不够，可以把恢复系x10用int存储，计算时再除以10。#include<bits/stdc++.h> using namespace std;#define read(x) scanf("%d",&x)#define maxn ((int)8e4) #define inf 2147483647stru

2021-10-22 23:21:38 126

原创两道区间dp

P3146 [USACO16OPEN]248 Gf[i][j]f[i][j]f[i][j]为完全合并[i,j][i,j][i,j]获得的最大数，当f[i][k]==f[k+1][j]f[i][k]==f[k+1][j]f[i][k]==f[k+1][j]时可以合并,f[i][j]=f[i][k]+1f[i][j]=f[i][k]+1f[i][j]=f[i][k]+1。#include<bits/stdc++.h>using namespace std;#define read(x) s

2021-10-21 20:09:16 73

原创 CF1592C Bakry and Partitioning

给出一颗n个节点的无根树，和每个点的点权。现在可以切开最少一条，最多K-1条边，使该数变成几棵子树。问能否通过操作使每棵子树内点权的异或和相等。先求出所有点的异或和，设为m。如果m==0，那么任意切开一条边，获得的两棵子树的异或和都相等。（a xor a == 0）如果m!=0，如果存在划分方案，则这些子树的异或和一定都为m，且为基数个。（m xor m xor m xor … xor m == m）#include<bits/stdc++.h>using namespace st

2021-10-08 21:00:02 88

原创 CF1580A Portal

Portal给一个01矩阵，求一个需要修改次数最小的子矩阵（长度至少为4，高度至少为5）的修改次数。一次修改可以把单个0改为1或者1改为0。修改后的矩阵需满足，中间全为0，四边为1，四个角随意。枚举子矩阵的上下界和右边界，左边界动态维护。f[k]：以i，j为上下界，k为右边界的修改次数。（不考虑右边界）f[k]=min(f[k−1]+加入第k行需要的修改次数，以i、j、k−3、k为边界的矩阵的修改次数)f[k]=min(f[k-1]+加入第k行需要的修改次数，以i、j、k-3、k为边界的矩阵的修

2021-10-07 21:01:27 193

原创 cf1579

A. Casimir’s String Solitaire给定一个只存在ABC的字符串，一次操作可以同时删除任意位置的‘A’和‘B’或‘B’和‘C’，问能否删完。只需判断B的数量是否等于A+C的数量。#include<bits/stdc++.h>using namespace std;#define read(a) scanf("%d",&a)#define maxn 50int main() { int T; read(T); while(T--) {

2021-10-03 11:51:37 168

原创 acoj 12467. 资源运输

题目：资源运输思路：其实，离线并查集和普通并查集是一样的吖iwi……离线的方法和莫队的思路也差不离吖……排序不说。带权并查集维护节点个数。在循环处理询问时，用一个指针处理边权在这一个询问和上一个询问之间的边，把块儿连起来。更新的答案就是当前连通块，除了自己的点的个数。代码：#include<bits/stdc++.h>using namespace std;...

2019-05-19 15:39:33 431

原创 201905/16 膜你赛关联点

题目：【问题描述】二叉树是一种常用的数据结构，一个二叉树或者为空，或者由根节点、左子树、右子树构成，其中左子树和右子树都是二叉树. 每个节点 a 可以存储一个值 va.显然，如果一个点 a 的左子树或右子树内有一个点 b，那么存在唯一的路径从 a 出发，每次往左子树或右子树走，经过一系列节点访问到 b. 我们把从 a 到 b 经过除 a 以外的节点数称为节点 a 到节点 b 的距离....

2019-05-16 21:03:27 212

原创 201905/16 膜你赛日程表

题目：【问题描述】放暑假了，小 C 准备了一个日程表来安排他的暑假生活.一共有 n 件事情，编号为 1; 2; :::; n，第 i 件事情的难度为 i. 小 C 将整个暑假划分为m 个时刻，并设定了三个正整数 a; b; c. 然后，小 C 定义了一个数列 fxig，满足：x0 = 0; xi = (axi−1 + b) mod 2nc (1 ≤ i ≤ m)即从 x1 开始，数列的...

2019-05-16 21:01:18 351

原创洛谷 P1712 [NOI2016]区间

题目：[NOI2016]区间思路：将区间离散化，并按照长度从小到大排序。考虑将区间按顺序加入，如果当加入区间 [L,R] 时，存在一个点使被覆盖次数==M，那么，可以用这条线段的长度减去覆盖这个点的第一条线段的长度更新答案，并弹出第一条线段。用线段树维护这个过程即可。代码：#include<bits/stdc++.h>using namespace std;#defi...

2019-05-13 16:33:22 218

原创洛谷 P3332 [ZJOI2013]K大数查询

题目：K大数查询思路：整体二分。维护两个区间[L,R]和[l,r]，分别代表二分的答案区间，和可以满足答案的询问区间。在[L,R]上二分M。对于1操作，如果v小于M，在[q.l,q.r]上用线段树实现区间加一，值赋1，否则赋0。对于2操作，询问[q.l,q.r]上的数的个数s，若v小于等于s，值赋1，否则赋0。注意long long的使用，以及线段树打标记清空。代码：#inclu...

2019-05-06 23:23:06 196

原创莫队总结

T1 [国家集训队]小Z的袜子(普通莫队模板)设在询问区间中，不同颜色袜子的数量为 a,b,c,..,za,b,c,..,za,b,c,..,z，和为n。P=a∗(a−1)+b∗(b−1)+c∗(c−1)+...+z∗(z−1)n∗(n−1)=a2+b2+c2+...+z2−a−b−c−...−zn∗(n−1)=a2+b2+c2+...+z2−nn∗(n−1)P=\frac{a*(a-1...

2019-04-29 17:23:01 144

原创【19/04/18 膜赛】大逃亡(escape)

题目：题目描述给出数字N（1<=N<=10000），X（1<=x<=1000），Y（1<=Y<=1000）,代表有N个敌人分布一个X行Y列的矩阵上，矩形的行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少,以及...

2019-04-18 20:34:47 270

原创【19/04/18 膜赛】土豪聪要请客(stol)

题目：题目描述众所周知，聪哥(ndsf)是个土豪，不过你们不知道的是他的MZ和他的RMB一样滴多…… 某天土豪聪又赚了10^10000e的RMB，他比较开心，于是准备请客。他在自己在XX星上的别墅里面大摆酒席，想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅，并且桌子的边必须与别墅的边界平行。给...

2019-04-18 20:32:13 258

原创【19/04/18 膜赛】 Jams倒酒(pour)

题目：题目描述Jams是一家酒吧的老板，他的酒吧提供2种体积的啤酒，a ml 和 b ml，分别使用容积为a ml 和 b ml的酒杯来装载。酒吧的生意并不好。Jams发现酒鬼们都很穷，不像他那么土豪。有时，他们会因为负担不起a ml 或者 b ml酒的消费，而不得不离去。因此，Jams决定出手第三种体积的啤酒(较小体积的啤酒)。 Jams只有两种杯子，容积分别为 a ml 和 b ml，而...

2019-04-18 20:29:52 364

原创洛谷 P4168 [Violet]蒲公英

题目：蒲公英思路：分块。把所有数分成n\sqrt{n}n个块，在每个块里分别求解。代码：#include<bits/stdc++.h>using namespace std;#define maxn 40000#define maxq 200#define read(x) scanf("%d",&x)int n,m;int a[maxn+5];m...

2019-04-16 17:39:06 170

原创洛谷 P4768 [NOI2018]归程

题目：归程&归程+思路：1、一种海拔 30’求最短路。询问时，海拔==0，输出0；否则输出dist[v]。2、链 15’离散化。预处理出不同海拔、每个点开始到起点的答案，查表输出。3、树 10树上倍增。4、kruskal重构树+树上倍增。做kruskal时，在并查集路径压缩时，同时存下树的心态。即，在最小生成树连边时，新建一个节点，权为边权，作为两节点的父节点。...

2019-04-14 18:20:12 255

原创洛谷 P1486 [NOI2004]郁闷的出纳员

题目：郁闷的出纳员思路：平衡树的题，可以用vector模拟。因为A和S操作很小，所以直接循环一遍不会超时。代码：#include<bits/stdc++.h>using namespace std;#define maxn 100000#define read(x) scanf("%d",&x)int m;vector<int> vec;in...

2019-03-27 21:16:28 225

原创 noip 2018 洛谷 P5021 赛道修建

题目：赛道修建思路：二分答案。judge时，令节点1为根节点，dfs求解。安利代码：#include<bits/stdc++.h>using namespace std;#define maxn 50000#define read(x) scanf("%d",&x)int cnt[maxn+5],f[maxn+5];struct Edge{ int...

2019-03-26 18:13:37 244

原创这一题的题号其实是回文串 (题目来自洛谷 uid105496 @KevinYu)

题目：题目背景在网上搜题解会有惊喜。题目描述XX国的城市道路网可以抽象为一个n*mn∗m的网络。XX国交通委提醒您：道路千万条，转向仅kk条。乱闯红绿灯，车祸两行泪。你在这一条路上可以横着走，可以竖着走，但是你一旦走了就不能转向。当然，为了方便，有kk个十字路口是可以转向的。但是为了安全，转向时要等红绿灯。规定无论是横着走，竖着走都耗费pp个单位的时间，在指定路口转向，都需耗费...

2019-03-26 15:26:36 193

原创洛谷 P1283 平板涂色

题目：平板涂色思路：裸的状压dp。代码：#include<bits/stdc++.h>using namespace std;struct sqr{ int x1,y1,x2,y2,c; sqr(){}};#define maxn 16#define maxc 20#define read(x) scanf("%d",&x)int n;sqr a...

2019-03-25 17:16:26 337

原创洛谷 P1041 noip2003 传染病控制

题目：传染病控制思路：搜索。先预处理出每个点的深度。然后对于每一层，枚举割掉的子边，向下一层搜索。注意单支树的情况。代码：#include<bits/stdc++.h>using namespace std;#define maxn 300#define read(x) scanf("%d",&x)int n;vector<int> g...

2019-03-25 16:15:58 268

原创洛谷 P1441 砝码称重

题目：砝码称重思路：一个裸的状压枚举加上一个裸的dp。代码：#include<bits/stdc++.h>using namespace std;#define maxn 20#define read(x) scanf("%d",&x)int n,m;int a[maxn+5];int f[100*maxn+5];int find(int x) {...

2019-03-18 17:02:52 258

原创洛谷 P1514 引水入城

题目：引水入城思路：一次dfs求出第一排每个点建蓄水场可以覆盖的点。然后求最小区间覆盖。代码：#include<bits/stdc++.h>using namespace std;#define maxn 500#define read(x) scanf("%d",&x)struct Pair{ int x,y; Pair(){} bool oper...

2019-03-18 16:13:40 179

原创探险

题目：题目描述小林和亮亮来到森林中探险，森林中有一条长度为 S 的小路（编号从 1 到 S），且在小路上时常会起雾，亮亮也可以用神光让雾消散。小林则关心在某一位置的视野。若位置 x 有浓雾，则位置 x 的视野为 0。若从 x 一直到 S 或从 x 一直到 1 全都没有浓雾，则视野为INF。其他情况下，位置x的视野为maxR−L+1maxR−L+1 要满足这个区间内没有浓雾的产生. ...

2019-03-14 20:37:05 337

原创方格纸与直线

题目：题目描述小林有一张 n 行 m 列的方格纸，如下所示。Luogu该方格纸黑白相间，且第一行第一列为黑色。顽皮的亮亮在方格纸上画了一条连接左上角和右下角的线段。小林看到方格纸后，马上算出了位于黑色区域的线段的长度之和占整条线段长度的比值。现在，他想考考你会不会算。输入输出格式输入格式：一行两个整数 n 和 m。输出格式：输出一个分数，即题目中所求的比值，用两个由’...

2019-03-14 20:31:30 919

原创洛谷 P2286 [HNOI2004]宠物收养场

题目：宠物收养场思路：由于同一时间不可能同时有人和狗，所以只需要建立一棵平衡树，赋予一个属性代表人或狗。然后对于领养操作，查找前驱后继，取差的绝对值最小，删除即可。代码：#include<bits/stdc++.h>using namespace std;#define maxn 80000#define read(x) scanf("%d",&x)#def...

2019-03-12 21:39:18 156

原创洛谷 P2770 航空路线问题

题目：航空路线问题思路：按每个点拆成xix_ixi和yiy_iyi，并从yiy_iyi向xix_ixi连一条流量为1费用为0的边。由S向x1x_1x1连一条流量为2费用为0的边，由yny_nyn向T也连一条流量为2费用为0的边。再根据到达关系，把每个xux_uxu和yvy_vyv间连一条流量为1费用为-1的边（由于求的是最大费用，所以设费用为-1）。然后在图上求一下最小费...

2019-03-10 16:44:57 163

原创 cubes

题目：题目描述约翰和贝西在叠积木。共有30000块积木，编号为1到30000。一开始，这些积木放在地上，自然地分成N堆。贝西接受约翰的指示，把一些积木叠在另一些积木的上面。一旦两块积木相叠，彼此就再也不会分开了，所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作，操作分为两种：第一种是移动操作，格式为“移动X到Y的上面”。X和Y代表两块积木的编号，意思是将X所的那堆积木，整体叠...

2019-03-07 21:22:17 760

空空如也

关于splay的分裂与合并问题