- 博客(40)
- 收藏
- 关注
RSS订阅原创 CSP2019-S AFO的预备赛经历和思考
真的考炸了。真的很废。真的梦。Day1第一题 格雷码一看发现可用类似二分模拟，看数据范围发现要开long long(自己默认long long刚好包括范围（-5）)，然后怕加法暴掉，判断了一下，自以为非常圆满，但是存ans的数组开小了（-15）。第二题括号树觉得可以树上dp,如果是“）”又满足情况就再+1，然而第二组样例没过（改了一会儿就想先打第三题的骗分，心情真的很着急，因...
2019-11-20 16:03:30
226
原创 线段树与树状数组的详解及区别
线段树Segment Tree理解：线段树，一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间，每个单元区间对应线段树中的一个叶结点。可用于区间求和，区间最大值，区间修改，单点修改等操作。时间复杂度：修改、查询、统计：O（log(n)）具体操作再写空间复杂度：O（4*n）解决问题：但是，可以用线段树维护的问题必须满足区间加法。e.g....
2019-11-14 22:35:47
1034
原创 电网 Electric Fences
题目Electric FenceDon PieleIn this problem, `lattice points' in the plane are points with integer coordinates.In order to contain his cows, Farmer John constructs a triangular electric fence by st...
2019-11-05 20:43:21
341
原创 家的范围 Home on the Range【USACO 3.3 】
首先，我要声泪俱下地控诉USACO的暴行，是它让一个幼小的心灵受到一次次残忍的伤害。题目Farmer John grazes his cows on a large, square field N (2 <= N <= 250) miles on a side (because, for some reason, his cows will only graze on prec...
2019-11-01 16:38:42
327
原创 CF589div2C. Primes and Multiplication
题面Let's introduce some definitions that will be needed later.Letprime(x) be the set of prime divisors ofx. For example,prime(140)={2,5,7},prime(169)={13}.Let g(x,p)be the maximum possible i...
2019-10-03 14:32:32
183
原创 19.9.14反思
毫无疑问，睡眠的确是一个很重要的东西，毫无疑问，健康的确也是一个很重要的东西。早上我的大脑刚开始是不工作的，但看完题后，我就开始打代码了，先打的第二题，打的二分答案，打完之后就知道有问题找到反例，但是不想打了，就开始打第三题，但是题目读错了，没有注意每个点只会有一个父节点，最后那道题我打了一个暴力，但是一测样例就过不了，时间也差不多了，我又突然改了第二题，当时不太清醒，就直接把第二题改了一部分...
2019-09-14 23:52:41
89
原创 9.7多校联考
四个质数的和【题目描述】给定了一个正整数 N。有多少种方法将 N 分解成为四个质数 a,b,c,d 的和。例如：9 = 2 + 2 + 2 + 3 = 2 + 2 + 3 + 2 = 2 + 3 + 2 + 2 = 3 + 2 + 2 + 2，故共有 4 种方法将 9 分解成为四个整数。【输入格式】本题多组数据测试：第一行读入一个整数 T 表示数据组数。接下来共 T 行，每行包...
2019-09-09 21:42:44
476
1
原创 D10：洪水&&[COCI2006-2007#1] Slikar+邦德I
1235. 洪水(Standard IO)Time Limits:1000 msMemory Limits:65536 KBDescription一天， 一个画家在森林里写生，突然爆发了山洪，他需要尽快返回住所中，那里是安全的。森林的地图由R行C列组成，空白区域用点“.”表示，洪水的区域用“*”表示，而岩石用“X”表示，另画家的住所用“D”表示，画家用“S”表示。有...
2019-08-10 21:21:13
235
原创 D9题解
1035. 粉刷匠(Standard IO)Time Limits:5000 msMemory Limits:65536 KBGoto ProblemSetDescriptionwindy有 N 条木板需要被粉刷。每条木板被分为 M 个格子。每个格子要被刷成红色或蓝色。windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉...
2019-08-09 21:59:22
369
原创 D5题解
我真的不知道为什么，我石油管道和数码都有想到正解（尤其是数码）可是我为什么只有大概一半多分，悲伤+不解……1432. 输油管道(Standard IO)Time Limits:1000 msMemory Limits:65536 KBGoto ProblemSetDescription 请你帮忙设计一个从城市M到城市Z的输油管道，现在已经把整个区域划分为R行C列，...
2019-08-05 21:20:30
229
原创 D4题解
3403. 数列变换(Standard IO)Time Limits:1000 msMemory Limits:524288 KBGoto ProblemSetDescription小X 看到堆成山的数列作业十分头疼，希望聪明的你来帮帮他。考虑数列A=[A1,A2,...,An],定义变换f(A,k)=[A2,A3,,,,.Ak,A1,Ak+2,Ak+3,,,,A2k,A...
2019-08-04 17:04:05
264
原创 D3学习dp(联赛难度)
我的天哪，今天因为QQ被冻结，CSDN也登不起，只能先用Word文档写博客再腾上去，突然发现QQ好有用哦o(〃'▽'〃)o，苦中作乐ing。今天上午主要讲了dp(联赛难度)中间比较特别的共同点(感觉病句)是斜率优化，有些题还涉及到矩阵加速。虽然之前学过，可是忘得差不多了，就重新再学一遍啦 (๑•̀ㅂ•́)و。斜率优化学习5935. 【NOIP2018模拟10.29】小凯学数学嗖嗖嗖...
2019-08-03 19:29:35
127
原创 最长上升子序列LIS的算法
复杂度O（n*log(n)）求a[i]的最长不下降子系列的长度d[i]:表示长度为i的最末位的最小值我画了好好好好久，就是如果a[i]不小于d[cnt]时，d[++cnt]=a[i],反之就用二分找到那个刚好大于当前a[i]的d[k]值把d[k]替换成a[i];for(int i=1;i<=n;i++) if(a[i]>=d[cnt])d[++cnt]=a...
2019-08-02 21:23:33
138
原创 外培D2题解
我我我我真的好好好好好瞎+蠢，居然没把语言改成C++，弄成CE爆零，想一巴掌抽死自己╮(╯﹏╰)╭，但是真实分数190也不是很好，只能安慰自己——这样我进步会很大(ノへ￣、)，加油(๑•̀ㅂ•́)و✧。1420. 佳肴(Standard IO)——暴搜Time Limits:1000 msMemory Limits:65536 KBGoto ProblemSetDescr...
2019-08-02 15:56:56
420
原创 准备开始完成自闭（广东中山纪中外培游记）
Day 0（7.31）由CQ到珠海的旅途只有在飞上天时与雨断了联系，在起飞和降落中的折磨人的耳鸣让我大脑一片混沌，好在困倦袭来我沉沉睡去，否则我大概会矫情好一阵子。云是一层一层的棉絮又厚又软，攀上一层云，而又毫无预料地遇见更高更辽远的云，曾闻天外天，今识云上云。————————————————到目前为止都还很好，一切正常。出机场就看见一颗被凌乱了枝叶的大树（不知其名）在狂风中立得很心酸，怎...
2019-08-01 21:49:33
192
原创 外培D1题解
今天的题我说实话好像模拟都可以过好多，可是我……自闭了……下午的时候，信竞的老师转换成专业人生导师，自动鸡汤灌溉（什么要保持良好健康乐观积极向上的心态呀，跟吴老师上次说的不要跟别人比要跟自己比真的有异曲同工之妙）（而且还说有些同学没过多少但仍然开开心心的）（感觉说的就是我）。2642. 游戏(Standard IO)——博弈sg函数Time Limits:2000 msMemory...
2019-08-01 20:17:00
227
原创 "红色病毒"问题 HDU - 2065让我不想升高中的指数型母函数
"红色病毒"问题 HDU - 2065题目医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。现在有一长度为N的字符串,满足一下条件:(1) 字符串仅由A,B,C,D四个字母组成;(2) A出现偶数次(也可以不出现);(3) C出现偶数次(也可以不出现...
2019-07-10 11:32:35
120
原创 Kronican
描述Mislav有N个无限体积的杯子，每一个杯子中都有一些水。Mislav想喝掉所有的水，但他不想喝超过K杯水。Mistrav能做的就是将一个杯子中的水倒入另一个杯子中。不幸的是，挑选哪两个杯子进行倒水操作对Mislav来说很重要，因为并非所有的杯子都离他一样远。更准确地说，从i号杯子向j号杯子倒水所付出的代价为Cij。帮助Mislav找到他需要付出的总代价的最小值。输入第一行...
2019-07-03 15:18:48
183
原创 读《杀死一只知更鸟To Kill a Mocking Bird》有感
自西安归来，我在无情的代码压迫下中挤出一丝丝，一丝丝缝隙，将生命的希望攥紧，一周有余才读完《To Kill a Mocking Bird杀死一只知更鸟》。一句拾起了我久忘的于书之爱。回味后，别是一般滋味在心头。我在这几个点上有些许思考：知更鸟到底是什么？1、你射多少蓝鸟都没关系，但要记住，杀死一只知更鸟就是一桩罪恶。知更鸟唱歌给我们听，什么坏事也不做。它们不吃人们园...
2019-07-02 17:29:30
2773
原创 拓扑排序
……我表示在遇到day1的3题前我认为我学过拓扑排序，好吧，我错了于是从头再来.拓扑序列：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列...
2019-06-24 15:28:47
105
原创 6.23 d2 2、3、4题
2、Tavan描述小 Zeljko 一直在阁楼里读他奶奶的旧信， 并且发现了一个长度为 N 的单词 。不幸的是，由于溢出的墨水，他不知道单词的内容。他把看不清的 M 个字母每个字母都用一个字符'＃'替换后，在一张纸上重写了这个词。他把那张纸递给了他的奶奶 ， 对于每个看不清的字母 ， 奶奶给了他 K 个不同的可能 。 在那之后 ，Zeljko 在笔记本中写下了所有可能的单词，并...
2019-06-24 10:29:23
615
原创 6.22 d1 2、3、4题
样例输入 111.....XX...X....XX...XX...XX...XX................XXX....................X.........XX...X....XX...XX....X...XX..样例输出 1 121 47 2样例输入 220X..................X.X..........
2019-06-23 10:53:45
145
原创 二元一次不定方程的整数解（扩展欧几里得算法）
二元一次不定方程的整数解（扩展欧几里得算法）（不得不说这是一堂数学*信竞课）整数解解法c(mod b)或ax+by=c有整数解当且仅当（a,b）|c一般意义下的解法：欧拉函数扩展欧几里得算法代码实现exgcd返回值为（a,b）int exgcd(int a,int b,int &x,int &y){ if(!b) { x=...
2019-02-17 21:27:03
5298
原创 欧拉函数
内容在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler's totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。——摘自百度百科通式性质代码实现1int phi(int n){...
2019-02-17 20:58:45
253
原创 反素数 Anti-prime number知识总结
定义对于任何正整数x，其约数的个数记作g(x)。 e.g. g(1)=1、g(6)=4。 如果某个正整数x满足：g(x) &gt; g(i) (0 &lt; i &lt; x)，则称x为反质数。————摘选自《百度百科》性质一个反素数的质因子必然是从2开始连续的质数。p=2^t1*3^t2*5^t3*7^t4……必然t1≧t2≧t3≧t4≧……证明（p为约数个数一定...
2018-08-17 12:20:59
538
原创 UVA1626 - Brackets sequence括号序列 DP（输入输出好坑）
题目Let us define a regular brackets sequence in the following way:1. Empty sequence is a regular sequence.2. If S is a regular sequence, then (S) and [S] are both regular sequences.3. If A and B a...
2018-08-13 17:44:49
329
原创 Rain and Umbrellas CodeForces - 988F（DP）
题目（无聊可以往下看大意(～￣▽￣)～） ExamplesInput10 2 43 78 100 103 48 11 2Output14Input10 1 10 90 5Output45Input10 1 10 91 5Output-1大意一段路【0，a】,这段路有部分区间下雨【此时必须携带一把伞】，路旁有一些点上有伞，可以捡...
2018-07-27 17:35:51
156
原创 2 3 5 7的倍数 51Nod - 1284
2 3 5 7的倍数 51Nod - 1284 基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题给出一个数N，求1至N中，有多少个数不是2 3 5 7的倍数。 例如N = 10，只有1不是2 3 5 7的倍数。Input输入1个数N(1 <= N <= 10^18)。Output输出不是2 3 5 7的倍数的数共有多少。Input示例10Output示例...
2018-02-26 13:49:22
156
原创 n^n的末位数字 51Nod - 1004
n^n的末位数字 51Nod - 1004给出一个整数N，输出N^N（N的N次方）的十进制表示的末位数字。Input一个数N（1 <= N <= 10^9）Output输出N^N的末位数字Sample Input13Sample Output3思路这道题的方法很简单，我们发现所有的末尾数的幂最多都是四个一循环，所以找规律就可以了。代码#include<cstdio>int...
2018-02-23 08:27:54
294
原创 数论四·扩展欧几里德
数论四·扩展欧几里德 描述小Hi和小Ho周末在公园溜达。公园有一堆围成环形的石板，小Hi和小Ho分别站在不同的石板上。已知石板总共有m块，编号为 0..m-1，小Hi一开始站在s1号石板上，小Ho一开始站在s2号石板上。小Hi：小Ho，你说我们俩如果从现在开始按照固定的间隔数同时同向移动，我们会不会在某个时间点站在同一块石板上呢？小Ho：我觉得可能吧，你每次移动v1块，我移动v2块，我们看能不能遇...
2018-02-02 12:12:38
158
原创 NOIP普及组总结
一些感想考试，好也罢坏也罢，已经过去，只能反思，不能再来……题目：问题 A(3502): [NOIP2017普及组]成绩题目描述牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：总成绩 = 作业成绩× 20% + 小测成绩× 30% + 期末考试成绩× 50%牛牛想知道，这门课程自己最终能得到多少分。输入只有1 行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测...
2017-11-23 13:21:52
859
原创 NOIP普及组考前总结（要取一个严肃点的名字(・-・*)）
有点紧张==其实还好；半期考试刚刚结束，noip就蹦哒蹦哒着来了:)，其实还好，就是有点紧张+慌张。一听到总结我就满脸懵逼，然后努力回想，发现——大脑中什么都没有……说重点！1.贪心算法（我的最爱）贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都
2017-11-10 18:24:58
265
原创 7624:山区建小学
7624:山区建小学总时间限制: 1000ms内存限制: 65536kB描述政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 输入第1行为m和n，其间用空格间隔第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。
2017-09-28 13:07:51
298
原创 最长上升子序列
问题 I(2486): 最长上升子序列时间限制: 1 Sec 内存限制: 128 MB题目描述给出一个长度为N的整数序列，求出包含它的第K个元素的最长上升子序列。输入第一行两个整数N, K第二行N个整数输出如题目所说的序列长度。样例输入Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)8 6
2017-08-25 22:08:48
240
原创 【USACO TRAINING】子集的和
问题 E(1046): 【USACO TRAINING】子集的和时间限制: 1 Sec 内存限制: 64 MB题目描述对于从1到N (1 举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的： {3} and {1,2} 这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能
2017-08-24 08:47:05
307
原创 【基础算法】采药
问题 B(1329): 【基础算法】采药时间限制: 1 Sec 内存限制: 64 MB题目描述辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这
2017-08-24 08:36:14
564
原创 【基础算法】 书的复制
问题 D(1233): 【基础算法】 书的复制时间限制: 1 Sec 内存限制: 64 MB题目描述现在要把m本有顺序的书分给k给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。 现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。输
2017-08-22 11:49:00
328
原创 河中跳房子
问题 C(2979): 【NOIP2015】跳石头时间限制: 1 Sec 内存限制: 128 MB题目描述输入输出样例输入25 5 2211141721样例输出4提示10:河中跳房子查看提交统计提问总时间限制
2017-06-11 18:54:46
421
原创 膨胀的木棍
总时间限制: 1000ms 内存限制: 65536kB描述当长度为L的一根细木棍的温度升高n度，它会膨胀到新的长度L'=(1+n*C)*L，其中C是热膨胀系数。当一根细木棍被嵌在两堵墙之间被加热，它将膨胀形成弓形的弧，而这个弓形的弦恰好是未加热前木棍的原始位置。你的任务是计算木棍中心的偏移距离。输入三个非负实数：木棍初始长度（单位：毫米），温
2017-05-20 20:03:42
1173
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人