- 博客(404)
- 收藏
- 关注
RSS订阅
原创 存东西
有用的板子：学长们整理的模板算法合集：各种认识和不认识、会或不会的算法自己乱整的初赛：。。。常用网址蒟蒻上路。。。洛谷SSLOJssl板子里的网址Visualgo：算法可视化学算法的时候对于理解很有用公式编辑器写博客的时候可能要用到流程图制作1流程图制作2流程图序列查找器用于各种找规律OI中转站优秀的东西NOI官网...
2018-11-02 20:35:04
418
2
原创 【期望】单选错位
解手推可以发现，选对第i道题的期望为1/max(第i−1道题的选项数，第i道题的选项数)1/max(第i-1道题的选项数，第i道题的选项数)1/max(第i−1道题的选项数，第i道题的选项数)累计起来即可代码#include<bits/stdc++.h>using namespace std;int n;long long A, B, C, lll, az, aq, lllaq, lllaz;double ans;int main(){ scanf("%d%lld%...
2021-10-14 10:02:21
153
原创 【堆】膳食搭配
解逆向思维。将时间线倒过来，变成xxx时间点出现某种食物。然后每次吃最少的那种食物即可。代码#include<bits/stdc++.h>using namespace std;int n, c, rs, ans, bhh, X[200005];long long tt, lt, lll;struct asdf{ int t; long long k; int bh;} F[200005];struct foood{ long long num; int bh..
2021-10-13 12:53:29
128
原创 【STL】Map、Set、Bitset、堆。一些操作
Mapmap<int,int> mp; //定义类型(会按第一维关键字自动排序mp[x] = y; //赋值，x可以赋较大，y为映射值mp.size(); //里面元素的多少map<int,int>::iterator k; //定义迭代器map.find(x); //找位置，返回迭代器，找不到返回map.end()for(k = mp.begin(); k != mp.end(); k++)//遍历。（注意mp.end()只相当于结束符号，不代表存入的东西） c
2021-10-12 13:10:58
197
原创 【离散】【差分】不同数字
题目大意给出一个 h×w 的矩阵，矩阵中每个元素的大小介于 1 到 256 之间。现在请你遮去一个面积不超过 s 的矩形，使得未被遮住的部分中不同的数字个数尽可能的少。然后输出这个剩余的不同数字的个数。满足1<=h,w<=10001 <= h, w <= 10001<=h,w<=10001<=ai,j<=2561 <= a_{i,j} <= 2561<=ai,j<=2561<=s<=h∗w1<=s<
2021-10-10 14:55:04
119
原创 【暴力】【二分】（优化）最大余数
题目大意给定n个整数, 从中选出若干个数字（每个数字最多选一次），使得它们的和取余m最大,求最大的余数。输入第一行输入两个整数 n(1≤n≤35)n(1 \le n \le 35)n(1≤n≤35) 和 m(1≤m≤109)m(1 \le m \le 10^9)m(1≤m≤109)第二行输入n个整数，这些整数属于区间 [1,109][1, 10^9][1,109]解由于 mmm 很大，所以不可能用桶。nnn 较大，用不了纯暴力搜索。我们可以发现 35 拆分成两半后的搜索复杂度可以接受。
2021-07-02 10:06:06
350
1
原创 【2013-DG特长生】总结（2021.4.24模拟赛
成绩差一点就能反杀TJH了——！(差个数组开大R=无法运行T=超时M=超内存Y=运行时错误B=崩溃A=正确W=错误的答案P=得部分分*=程序无输出[=缺标准输入]=无标准输出?=无程序^=自定义评测错误-=编译错误题与解T1散步（题解）水水。T2项目问题（题解）DFS+剪枝。…不会。就打了个暴力DFS。后来发现跟11年某题一模一样。T3游戏（题解）写了DFS。结果数组开小了只有40分，开大80分。（用DFS会炸内存）需要将DFS写成循环。。T4文档修
2021-05-15 11:39:37
147
原创 海岸线
泰拉大陆！（bu（画不出那样的图题目一个王国分成 n*m 个六边形区域，每个区域内是陆地或者是水。如果一条边两侧为陆地和水，则该条边成为海岸线，求这个王国海岸线的长度。以下 n 行，每行 m 个字符，.表示水，#表示陆地。偶数行需要向右移半格，具体见样例。输入3 6..#.##.##.#.#.#...输出19题目的图（瞎几把乱画图ing）解对于每一个，判断与它相连的格子是否与它相同。不相同ans++；代码#include<cstdio>int n,
2021-05-15 11:39:28
176
原创 【模拟】投票统计
解模拟。注意细节。代码#include<cstdio>#include<cstring>#include<iostream>#include<cmath>using namespace std;int n, m, suki[1005][1005], now[1005], tikt[1005], minn, in[1005];int main(){ freopen("vote.in","r",stdin); freopen("vote..
2021-05-15 11:39:15
196
原创 【DG特长生2019】文档恢复
题目大意ABC教授是XYOI的负责人，有一天他竟然发现自己的计算机染上了一种不常见的病毒这种病毒的名字叫做ALPHABETVIRUS，当它发作的时候，它会将字母用其它的字母代替，但它不会将单词的顺序交换。病毒将计算机中的所有文档都作了相对应的改变，很幸运，ABC教授的计算机上有一个字典，而我们都知识字典单词是按字母顺序排列的，当然，这个字典也被病毒改变了。因此，要利用字典原来的有序性，找到病毒替换字母的规律，再用以恢复其它文档。由于XYOI是不可缺少ABC的文件的，所以文档必须恢复。但是由于ABC教授有
2021-05-14 15:18:41
235
原创 【DG特长生2019】游戏
某校科技节到了，有???? 个同学（编号为1到????）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为???? 的同学的信息传递对象是编号为????????的同学。 游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？解????≤200000。D
2021-05-14 15:07:57
95
原创 【DG特长生2019】散步
李四是一个很会利用时间的学生，他经常晚上吃过饭后一边思考问题一边散步，由于要思考问题，并且思考问题的内容越来越多，所以他在散步时也是越来越慢的，他自己总结出一个规律，他散步时第一步走N厘米，第二步走N-1厘米，以后每步比前一步少1厘米，最后一步是0时就停下来了。现在给出你李四第一步走的长度N厘米，请你算出李四这次散步一共走了多少厘米。如：李四第一步走3厘米，则第二步走2厘米，第三步走1厘米，然后就停下来了，则李四这次散步共走了3+2+1=6（厘米）。解？那个高斯速算1+2+3+…100的故事听说过吗—
2021-05-14 15:00:51
119
原创 【2013-DG特长生】总结（2021.5.4模拟赛
成绩表格from TJHT4的SPFA居然没打转移。淦。题与解T1成绩排序（题解）sort。水水。T2数对（题解）桶。T3数字编码（题解）DP。T4廉价最短路径（题解）这不SPFA？
2021-05-14 10:02:35
91
原创 【SPFA】【DG特长生2013】廉价最短路径
图是由一组顶点和一组边组成的。一条边连接两个顶点。例如，图1表示了一个有4个顶点V、5条边的图。图中，每条边e是有方向的，方向从起点到终点，并且每条边都有价值。用整数0,1,…,m-1可以表示一个有m个顶点的图。一条路径连接了一个点Vi和另一个点Vj，其方向与经过的一系列边的方向一致。路径的长度是途经边的条数，路径的费用是边价值的总和。对于一个给定的图，你的任务是在所有最短路径中，找出需要最少费用的连接V0和V1的路径。一个需要最少费用的最短路径称之为廉价最短路径。解spfa多加点一条条件即可。代
2021-05-14 09:58:02
71
原创 【DG特长生2013】数字编码
一列有顺序的非负整数，需要把它们编码成一个0、1字符串进行传送。设这一列数为P={P1，P2，…，Pn}，其中0<=Pi<32767，具体的编码方法为：把P分成k个段 S1，S2，…，Sk，在第i个段Si 中有a(i)个数字，且该段中每个数字都用b(i)位0、1串来编码表示，另外为了正确解码，还要在该段前面附加上一个消息头，用来指出该段有多少个数字以及每个数字的编码位数，消息头的格式规定如下：首先用8位二进制位表示a(i)，这导致0<a(i)<256，另外由于0<=Pi<
2021-05-14 09:56:38
96
原创 【DG特长生2013】数对
考虑一组n个不同的正整数a1,a2,…,am，它们的值在1到1000000之间。给定一个整数x。写一个程序sumx计算这样的数对个数(ai,aj)，1<=i<j<=n并且ai+aj=x。解sort肯定是跑不过的，考虑a[i]的值再1到1000000之间，可以用桶排，也方便处理。(加了个快读)代码#include<cstdio>int n, k, f[1000003], sum;long long ans;int read(){ char c = getch
2021-05-14 09:47:50
340
原创 【DG特长生2013】成绩排序
？大概就是排序。解&代码sort单核。#include<cstdio>#include<algorithm>#include<iostream>using namespace std;long long a[502];int n;int main(){ freopen("score.in","r",stdin); freopen("score.out","w",stdout); scanf("%d", &n); for(int
2021-05-14 09:45:36
53
原创 【2012-DG特长生】总结（2021.5.4模拟赛
成绩烤了TJH的表…我还是不会剪枝。。。题与解T1安全密码（题解）水水。T2农场主（题解）很清晰的一个DP。T3栅栏的木料（题解）不会剪枝。瞎搞搞。T4营救（题解）金典BFS。
2021-05-14 09:28:31
59
原创 【DFS】【剪枝】【DG特长生2012】栅栏的木料
农民John准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状，但是他在木料方面有些问题。当地的杂货储存商扔给John一些木板，而John必须从这些木板中找出尽可能多所需的木料。当然，John可以切木板。因此，一个9英尺的木板可以切成一个5英尺和一个4英尺的木料 (当然也能切成3个3英尺的，等等)。John有一把梦幻之锯，因此他在切木料时，不会有木料的损失。所需要的木料规格都已经给定，每种规格的木材最多需要1块（注意：如果给定的规格值相同，则也各要一块），当然也有可能某些规格的木料无法切出。解D
2021-05-14 09:18:05
203
原创 【2011-DG特长生】总结（2021.5.13模拟赛
卧 ！槽 ！三题 全 炸 了！！！！！！啊！2011tcs = 2011特差生awsl。（但凡我稍稍检查一下也不止于此）成功诠释什么叫失误了就无了。下！次！一！定！要！检查！检查检查检查检查检查检查检查检查检查检查…成绩ranknamescoreT1T2T3T4111TJHTJHTJH370370370100100100707070100100100100100100222FYFYFY250250250100100100101010
2021-05-13 21:10:08
70
原创 【DFS】【剪枝】【DG特长生2011】民生问题
某市政府非常关注民生，最近对民生问题作了调研，提出了最近要解决的n个民生问题，政府的专家顾问组有w人，每一个专家都有自己的特长，政府知道每专家能解决哪些问题,现在政府想知道至少请多少位专家,才能把所有的问题都解决?解DFS+优化。如果一个专家可以解决的任务，某一个专家全都可以解决，那么删掉前面一个专家…如果某个任务只有一个专家可以解决，那么这个专家必然被选择。瞎搞。代码瞎几把优化，居然加起来有50行左右…#include<cstdio>#include<cmath>
2021-05-13 20:44:24
148
原创 【DP】【DG特长生2011】花店布置
题目解设f[i][j]为第i朵花插到第j个花盆的最大美观度。代码#include<cstdio>#include<iostream>#include<cmath>#include<cstring>using namespace std;int ff, v, w[1001][1001], f[1001][1001], ans;int main(){ freopen("flower.in","r",stdin); freopen("f
2021-05-13 20:42:01
120
原创 【DG特产公司2011】裁缝师
老李是某布行资深的裁缝师傅，他经常要将一块布裁剪成若干块小布。他是这样裁剪布料的：一刀下去，不管布有多长，都是沿直线剪开它为止。当然，他还可以一次剪多层布料，至于一次能剪多少层，则依赖于该布料的类型。例如：对于某种布料来说，一次只能剪一层布，那么要把一块2X3的布料剪成6块1X1的小布，总共需要剪5刀,如下图；但是，对于另外一种不同的布料来说，如果这种布料一次可以剪两层布，那么只需要三刀就可以剪开布料了（剪完第一刀后，把剪开的两块布叠在一起，再剪第二、第三刀）。显然，在剪的过程中，叠放在一起剪的几块布料是
2021-05-13 20:36:23
79
原创 【DG特长生2011】工具软件
给你个m进制数要你转换为n进制数。(2<=m,n<=10)解先转换为10进制，再转换成其它。代码#include<cstdio>int m, n, t, w[1001];long long x, X, kkk;int main(){ freopen("tool.in","r",stdin); freopen("tool.out","w",stdout); scanf("%lld%d%d", &x, &m, &n); if(m !=
2021-05-13 20:34:56
63
原创 【DG特长生2012】营救
题目给你个有0和1组成的地图。0代表可以通行，1代表不可以。再给你两艘船的坐标，一艘船可以向上下左右四个方向移动。求到另一艘船的坐标的距离。解经典BFS。代码#include<cstdio>#include<iostream>#include<queue>#define fr(i,x,y) for(int i = x; i <= y; ++i)using namespace std;int n, x1, y1, x2, y2, bs[1010
2021-05-12 21:07:54
54
原创 【DG特长生2012】农场主
题目有n匹白色或是黑色的马。农场主要把马分成k份放入马房，每一份中必须是连续的马。一个马房的“不高兴系数”为 (白马数量*黑马数量) 。使所有马房的“不高兴系数”和最小。求这个和。解DP。预处理black为从一到i的黑马数量。然后设f[i][j]为到第i匹马，分为j份最小的和。代码#include<cstdio>#include<cstring>#include<iostream> #define fr(i,x,y) for(int i = x; i
2021-05-12 21:04:47
72
原创 【DG特长生2012】安全密码
题目大意给你 aaa ， bbb ， ccc 三个数。求 aba^bab modmodmod ccc 。解标准的快速幂。代码#include<cstdio>#define LL long longLL a, b, c;LL ksm(LL k){ if(k == 0) return 1 % c; if(k == 1) return a; LL l = ksm(k>>1); if(k % 2 == 0) return l * l % c; return
2021-05-12 20:01:06
75
原创 【DFS】数独游戏
数独游戏只有一个规则：将 9×99\times99×9 的矩阵填满，使得每一行，每一列，和每一个小的九宫格恰好包含 1∼91\sim91∼9 这 999 个数字。你需要编写一个程序填写不完整的数独。解代码
2021-05-09 16:42:27
137
原创 【单调队列】经典 LIS
给出一个长度为 nnn 的整数序列 {ai}\{a_i\}{ai}，求它包含的最长不下降子序列。解对于每个数选就是选，不选就是在前面比它小的数中选到它最大的。找这个最大用单调队列。代码#include<cstdio>#include<iostream>#include<cmath>using namespace std;int n, t, ans, a[500005], q[500005];int main(){ freopen("love.i
2021-05-09 15:54:00
109
原创 【模拟】程序翻译
在 Java 中，由多个单词组成的标识符的命名规则如下：第一个单词是以小写字母开头，接下来的每一个单词以大写字母开头，分隔符不允许使用。其他字母都是小写的。在 C++ 中，只用小写字母命名标识符。用下划线 _ 来分隔单词（每个单词长度至少为 111）。当只有一个单词时，用 Java 和 C++ 是统一的。现在需要写一个程序来相互翻译 Java 和 C++ 的程序。翻译后的标识符必须符合它的命名规则。如果这个标识符既不是 Java 标识符也不是 C++ 标识符，你的程序需要报告错误。解判断是 C+
2021-05-09 15:45:22
72
原创 【DFS】水库选址
有 mmm 条枢纽管道，每一条管道连接着两个村庄，使得水源流通。有 nnn 个村庄,只有一个水库，水从有水库的村庄通过这些枢纽管道流向向其它村庄。而且水只能往低处流（同海拔之间不能相互流水），需要让所有村庄都能得到水库的供水。想要知道水库应该建设在哪一个村庄，请你给出答案。存在方案则输出 Yes 和建在的村庄编号，否则输出 No。解水库当然是建在最高的地方。然后就 DFS 跑，看能否到达所有点。代码#include<cstdio>int n, m, ans1, ans2,
2021-05-09 15:33:05
119
原创 【SPFA】【二分】通信线路
在郊区有 NNN 座通信基站，PPP 条双向电缆，第 iii 条电缆连接基站 AiA_iAi 和 BiB_iBi。农场主希望对通信线路进行升级，其中升级第 iii 条电缆需要花费 LiL_iLi。电话公司正在举行优惠活动。农场主可以指定一条从 111 号基站到 NNN 号基站的路径，并指定路径上不超过 KKK 条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱能完成升级。解二分。二分最贵的电缆，然后比它贵的就需要免费，
2021-05-09 15:27:32
91
原创 【DP】晨练计划
每天小明都会进行 NNN 分钟的晨跑。有一个疲劳度，不论何时，疲劳度都不能超过 MMM。在第 iii 分钟时，小明可以选择：跑步。跑 DiD_iDi 米，并且疲劳度会增加 111。休息。疲劳度会每分钟减少 111，但必须休息到疲劳度为 000 为止，若在疲劳度为 000 时休息，疲劳度不会变。开始时，小明的疲劳度为 000，结束时，小明的疲劳度也必须恢复到 000。请你计算一下，在满足所有条件下，小明最多能跑多少米。解DP。设 f[i][j]f[i][j]f[i][j] 为前 iii
2021-05-09 15:13:18
139
原创 【数】约数个数和
求 l~r 的数的约数个数的和。1<=l<=r<=1071<=l<=r<=10^71<=l<=r<=107解先是前缀和，变成求 1~r 和求 1~l-1 的。然后就枚举约数，看这个区间有多少数有这个约数，然后加在一起就行了。代码#include<cstdio>int l, r;long long ans1, ans2;int main(){ freopen("sum.in","r",stdin); freopen("s
2021-05-09 14:57:03
106
原创 【Sort】寻找数字
给出一个长度为 nnn 的数组 ，你需要寻找数组中出现次数超过 n/4n/4n/4 的数。如果没有出现次数超过 n/4n/4n/4 的数，请输出 No number.。解。直接排序，统计每个数出现的次数。代码#include<cstdio>#include<iostream>#include<algorithm>using namespace std;long long n, a[10005];long long now, countt, ans;
2021-05-09 14:49:39
201
原创 【2020-DG特长生】总结（2021.5.5模拟赛
过程这次可没跟人开黑打比赛哼哼~T1数学题（题解）居然…是高精。还有负数，那岂不是还要处理减法。…结果刚敲完发现给的两个数要么都是整数，要么都是负数，根本不用减法。浪费我30min。啧啧。T2流星雨（题解）标准BFS？虽然数据不大，但是应该有坑。于是留了个心眼，将数组在可控范围内开大了些许。T3K星人的语言（题解）？首先单词匹配原串肯定是要做的…然后发现：其实可以优化匹配，还可以预处理单词匹配的位置以及需要删字母的个数，然后DP。？好耶！T4星座图（题解）嘶…45min。粗
2021-05-05 17:07:14
97
原创 【DG特长生2020】星座图
给你一棵树。树上的每一个点有一个权值 WWW。你需要找到所有距离为 222 的点对 (i,j)(i,j)(i,j) ，它们的“星座权值”为 Wi∗WjWi*WjWi∗Wj。求最大的“星座权值”和所有“星座权值”的和。解60pts：逐个枚举点。走一步，再走一步，处理。或者DFS。？各种数组乱套。70pts：加个快读。？100pts：逐个枚举点，它相连的点间处理权值。再化简式子，优化，用sum。代码#include<cstdio>#include<iostrea
2021-05-05 16:43:04
74
原创 【DG特长生2020】K星人的语言
K星人说话奇怪。比如他们说：“nicedgidrl” 其实是 “nicegirl” 。中间会穿插很多奇怪的小写英文。大概是噪音。并且他们没有空格这种东西。给你一条长度为L的消息。再给你W个K星人的合法单词。让你求，删掉最少多少个小写英文后，消息由合法单词构成。解预处理下消息包含合法单词的情况。（这里作过了优化，实际上直接暴力也可）处理出字符串某一段删成某个单词所需删掉英文数。再使用DP。设 f[i] 为使该串起始位置到i这一段都为合法文章的最小删除数。详见代码。代码#include&l
2021-05-05 16:35:51
130
原创 【DG特长生2020】流星雨
（自改题目背景）…“天灾降临，我们并非无计可施。”天灾降临。天灾信使朝坐标 (0,0)(0,0)(0,0) 的移动城市切尔诺伯格发送紧急情报:一共有 MMM 颗流星将降落到该块区域，其落点坐标为 (Xi,Yi)(Xi,Yi)(Xi,Yi)，会在第 TiTiTi 个时间点落至地面。流星的力量会将它所在的位置，以及周围4个相邻的位置都化为焦土。生物无法再在这些位置上行走/生存。请尽快移入安全区域。（乌萨斯刁民，别看流星雨啦！！）难民从第 000 个时间点开始移动，每次花费 1s1s1s 向周围四格移
2021-05-05 16:21:57
87
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人