- 博客(373)
- 收藏
- 关注
RSS订阅原创 【思维+树状数组】ZOJ-4117 BaoBao Loves Reading
题目链接：传送门参考博客：2019山东省赛 zoj 4117 E BaoBao Loves Reading 思维+树状数组【题意】：如果你学过操作系统，其实你就知道这个就是经典的调度算法的FIFO，先进先出算法。如果你没有学过操作系统，这个就是说有N本书在书架，然后书桌只能容纳K本书，然后先进先出，请问当K取值为[1,n]时，每次拿书的次数为多少。【题解】：参考博客小喵的做...
2019-05-16 21:04:12
542
原创 【数论】ZOJ-4123 Happy Equation
题目链接：传送门参考博客：HDU 6189 Law of Commutation（数论）Happy Equation ZOJ - 4123 （数论）【题意】：给一个式子，求符合x的个数：然后这个题目可以通过奇偶数找规律得出答案。这个规律也挺不好弄的。首先：a 为 奇数时：为奇数b有两种情况1、b 为偶数时：明显是一个偶数（不符合）2、b...
2019-05-16 13:22:02
705
原创 【矩阵】求01矩阵中,只含1的子矩阵的个数
例题：P5300 [GXOI/GZOI2019]与或和题解：参考资料有一个显然的结论：以（n,m）为右下角的所有子矩阵之和 = n*m枚举每一个点，我们来计算以它为右下角的子矩阵个数 对于一般情况，在2处，A区域就没有意义，4处，B区域就没有意义所以我们要维护一个单调栈，栈中元素k要满足s[i][k]单调递增（栈顶s[i][k]最大）每次有元素出栈时，说明有部分答...
2019-05-16 11:17:57
4590
原创 【DP】ZOJ - 4114 Flipping Game
参考博客：2019山东省赛 ZOJ - 4114 Flipping Game dp题目链接：传送门【题意】：有两个串，每次改变m个字符，改变k轮，把a变成b有多少种方法改变 ： 0 -> 1 , 1 -> 0必须改变m个，然后k轮之后的结果是什么？【题解】：看了别人的博客才知道原来是一个状态转移。dp[i][j]，指的是 在第i轮改变后，有j...
2019-05-14 14:23:06
508
原创 【连通矩阵】ZOJ_4124 Median
题目链接：传送门【题意】： 对于一个包含n个数的（n为奇数）序列val[ ]，排序后的 val[ (n+1) / 2 ] 定义为 median； 有 n 个数，并有 m 组关系，对于第 i 组关系 ai,bi代表第 val[ai] > val[bi]； 但并没有给出具体的数值； 输出一个包含 n 个元素的数组 s[ ] ； 让你判断第 i 个数 val[ ...
2019-05-14 11:06:56
1094
原创 【MST】最小生成树prim 算法原理及实现
以下参考《信息学竞赛一本通 提高篇》前置知识点：1、生成树：在一个|V| 个点的无向联通图中，取其中|V|-1条边，并链接所有的顶点，所得到的子图称为原图的一颗生成树。2、树的属性:树是图的一种特殊形态。图G是树当且仅当一下任意一个条件成立1、G有|V|-1条边，无环。2、G有|V|-1条边，连通。3、任意两点之间只有唯一的简单路径4、G连通，但任意删除一条边后...
2019-05-10 19:26:58
1217
原创 【洛谷P3390】 【模板】矩阵快速幂
题目链接：P3390 【模板】矩阵快速幂题目描述给定n*n的矩阵A，求A^k输入输出格式输入格式：第一行，n,k第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素输出格式：输出A^k共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7输入输出样例输入样例#1：2 11 ...
2019-05-06 21:27:13
241
原创 【递推+矩阵快速幂】poj3240
题目链接：Quad Tiling参考博客：poj 3420 Quad Tiling 矩阵乘法+快速求幂题意：给4*n的矩形，用1*2的矩形填充，请问有多少种方案？上面的情况是：在第i+1行处，已经处理完第i行了，剩下来的结果通过上面的情况进行递推。a[n] = a[n-1] + b[n-1] + c[n-1] + dx[n-1] + dy[n-1];b[n] = a[n-...
2019-05-06 13:09:41
232
原创 【位运算】Winner Winner
Winner Winner题目描述The FZU Code Carnival is a programming competetion hosted by the ACM-ICPC Training Center of Fuzhou University. The activity mainly includes the programming contest like ACM-ICPC ...
2019-05-05 20:22:03
247
原创 【转载】Linux C语言：main函数的命令行传参
原文地址：Linux C语言：main函数的命令行传参https://www.tomorrow.wiki/【转载目的】真的非常感谢这位博主，解决了我一个大问题！！！在大学里面，老师一般会这样教，定义main 函数应该是这样的：甚至是这样的：但是其实在 Linux 下，一个正确的main 函数应该被定义为如下：大家可以看到，main 函数中有两个参数，分别是 ...
2019-05-04 17:13:24
1578
1
原创 【找规律】hdu6267 Master of Random
Master of Random题目描述Hakase provides Nano with a problem. There is a rooted tree with values on nodes. For each query,you are asked to calculate the sum of the values in the subtree. However, Nano ...
2019-05-03 20:32:34
318
原创 【类欧几里得】推导过程
参考博客：类欧几里得算法小结例题：HDU 6275Mod, Xor and Everything题目描述You are given an integer n.You are required to calculate (n mod 1) xor (n mod 2) xor ... xor (n mod (n - 1)) xor (n mod n).The “xor” operat...
2019-05-03 08:48:35
627
原创 【单调栈】【附上模板题】单调栈原理和应用
参考博客：单调队列与单调栈用法详解单调栈原理及应用 详解 附各种类型的题目练习参考：[洛谷日报第9期]浅谈单调队列其中有两幅图片是从上面的博客中获取的！！！请尊重原创，大家可以点击上面链接找到对应的博客学习。我只不过是借用两幅图片罢了【单调栈】：解决问题：可以获取左边第一个或者右边第一个比当前位大或者小的数。具体表现为：1.最基础的应用就是给定一组数，...
2019-04-30 11:33:32
970
原创 【CF】【每日一练】1140C+755C+511C+1154E
题目链接：传送门【题意】：给你n首歌，每首歌都有各自的长度length和美感beauty。然后让你选择出最多k首出来，使得观赏度达到最大值。观赏度 = （选择的歌曲 的长度 ）× （在所选歌曲中美感最低的）【题解】：其实一开始以为简单的排序，美感降序，然后选择之前的歌曲即可。但是怎么确保前面K-1首，一定是时间总和最长呢？？？这就用Set来维护，一直把时间最短的...
2019-04-23 15:30:35
260
原创 【2019中山】【二维前缀和】Monitor
【题意】：这个题目的意思是：有一个监视器管辖的范围用二维坐标的左下角和右上角来表示，然后有一个小偷在某个位置活动，请问能否把小偷给活动范围全部监视到。【题解】：1、二维差分数组维护监视器 d[][]2、然后恢复原来的监视范围 a[][]3、恢复后，把对应的位置置一，然后进行二维前缀和来统计 sum[][]4、把小偷的活动范围面积求出来 与 前缀和 对比一下判断YES或...
2019-04-21 22:23:20
177
原创 【19南昌网络赛-K】【找规律】MORE XOR
题目链接：题库链接【题意】：给出了很多定义式子出来，f(x,y)=下标从x到y异或和。g(x,y)是[x,y]区间所有的区间的f(tx,ty) 的异或和，(x<=tx<=ty<=y)w(x,y)是[x,y]区间所有的区间的g(tx,ty) 的异或和，(x<=tx<=ty<=y)推导：g(x,y)是有规律可言的。因为所有区间和，也可...
2019-04-21 22:10:56
209
原创 【19南昌网络赛-M】【公共子序列】Subsequence
【题意】：给你S原串，然后有T次询问，给一个T匹配串，请判断T是否为S的子序列。【分析】：这个题目真的厉害，只能线性的复杂度，多了也不行！！！因为S串长度为1e5，T次询问分别为1e5，还有匹配串的长度1e3。一开始以为用二分来解决，后来发现不行。这样会超时。但是在比赛最后的想到可以提前预处理。。。But过，不能从前往后处理，这样还是有log复杂度。只能从后往前来处理。...
2019-04-21 21:26:26
197
原创 【19南昌网络赛-H】【规律】Coloring Game
【题意】：给你2×N的方格图。从左上角开始走，走到某一个格子上面就会变黑，然后问，共有多少种情况。其实说句老实话，打表都不好打表。其实看出来是一个规律题目了。打表之后得到结果结果是：4×3^(n-2)/*#include <cstdio>#include <queue>#include <algorithm>#includ...
2019-04-21 21:17:34
212
原创 【ZOJ浙大校赛19】【模拟】Robot Cleaner I
题目链接：传送门【题意】：一个打扫机器人（说到机器人，恭喜LDU在2019-04-21 Robocup中获得全国冠军，为自己的学校及飞哥感到骄傲）。然后执行指令，在一个指令条中根据当前格子的4联通即当前格子，用3进制来运算，得到的数字进行执行指令。所以这个题目就是一个大模拟，上下左右的走（U，D，L，R），同时有一个不工作偷懒（I），还有捡起垃圾（P）。但是捡起垃圾后会清空当...
2019-04-21 21:02:10
240
原创 【19南昌网络赛】A-PERFECT NUMBER PROBLEM
参考博客：WSY大佬的做法【题解】：其实看到题目我就知道这个结论了，这个是我们小学课本上面的一个“完美数”。没有规律可言。（当时比赛时候我是直接上网找到，其实不太道德，主要是看到太多人在10分钟内过了）主要是看了WSY对于这个题目的执着，我自己也写了一遍。【基本思想】1、Euler把所有素数筛选出来2、用唯一分解定理把所有的 质因数 与其 对应的 个数挑出来。3、...
2019-04-21 20:43:06
288
原创 【洛谷P2010 】回文日期
题目描述在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。牛牛习惯用8位数字表示一个日期，其中，前44位代表年份，接下来2位代表月 份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现 在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存...
2019-04-19 15:36:43
668
原创 【归并排序】【洛谷P1309】 瑞士轮
题目背景在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长。题目描述2×N名编号为...
2019-04-18 20:53:19
347
原创 【线段树】【根号】花神游历各国
题目链接【题解】：由于这个1e8的数字最多只能开根号6次，复杂度就是O(6*n)直接进行开根号到叶子节点，然后不断更新。复杂度并不高，但是注意的是，如果当前节点已经是1或者0那么就不要处理了，在更新的过程中多加一个判断修改一下这个题目就可以AC了。#include<bits/stdc++.h>using namespace std;typedef l...
2019-04-18 13:35:35
423
原创 【线段树】【AHOI 2009】维护序列
题目链接：传送门题目描述老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：(1)把数列中的一段数全部乘一个值;(2)把数列中的一段数全部加一个值;(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。输入输出格式第一行两个整数N和P(1≤P≤10000000...
2019-04-18 13:31:02
282
原创 【线段树 | ST表】最大数
题目描述给定一个正整数数列a1,a2,a3……an，每一个数都在 0~p-1之间。可以对这列数进行两种操作：添加操作：向序列后添加一个数，序列长度变成 n+1； 询问操作：询问这个序列中最后 L个数中最大的数是多少。程序运行的最开始，整数序列为空。写一个程序，读入操作的序列，并输出询问操作的答案。输入格式第一行有两个正整数 m,p，意义如题目描述；接下来 m 行，每一行表...
2019-04-16 12:43:38
1378
原创 【最小支配集】开会
题目描述开会，是对所有人时间的浪费，是对集体的谋杀。山区学校的一些学生之间的关系似乎好得有点过头，以至于传出了一些(在风纪委员们看来)不好的绯闻。具体地，有n个学生，n-1条绯闻，每条绯闻的主角都是俩学生。记者们的恶趣味保证任意两个学生，可以通过若干条绯闻直接或间接地联系在一起。于是学校打算邀请一些学生参加座谈会。校长相信，假如邀请了某位学生x来开会，那么就能够震慑到x本人，以及和x在同...
2019-04-15 22:02:07
212
原创 【树状数组|线段树】hdu_6464免费送气球
免费送气球Problem Description又到了GDUT一年一度的程序设计竞赛校赛的时间啦。同学们只要参加校赛，并且每解出一道题目就可以免费获得由ACM协会和集训队送出的气球一个。听到这个消息，JMC也想参加免费拿气球。可是，由于JMC太菜了而被禁止参赛，于是他找到你想让你帮忙参加比赛，可以通过执行...
2019-04-11 22:14:19
210
原创 【二分】hdu_6469 故事
Problem Description这是一个极其老套的故事，无论怎样的描述都会因为故事本身的古老而显得陈词滥调。这个故事究竟有多古老呢？你需要调用你的一切想象力，沿着时间线回溯，穿过麦田，穿过绿林，穿过那铺着大理石的长廊，来到那金碧辉煌的宫殿大堂前，来到那体态臃肿的国王面前。你将看见那神情激动的国王，将手一挥，只留下回荡在肃穆的大堂里的一句话――“去吧！消灭恶龙！拯救公主！”。好吧，其实这...
2019-04-10 22:17:21
406
原创 【洛谷】【线段树】P1438 无聊的数列
题目背景无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）题目描述维护一个数列{a[i]}，支持两种操作：1、1 L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。即：令a[L]=a[L]+K，a[L+1]=a[L+1]+K+D，...
2019-04-10 21:01:26
259
原创 【贪心+优先队列】Working Plan
题目链接：传送门题目描述ICPC manager plans a new project which is to be carried out for n days. In this project, m persons numbered from 1 to m are supposed to work. Each day j (1 ≤ j ≤ n) requires dj persons...
2019-04-08 20:58:41
589
原创 【单调队列】poj2823_Sliding Window
题目链接http://poj.org/problem?id=2823【题解】这个题目就是纯模板题，但是这个题目有很多坑点，首先这个题目是多组输入的，然后这个输出还卡我们时间#include<stdio.h>#include<iostream>using namespace std;const int N = 1e6+10;int IM[N],Im[...
2019-04-07 23:52:15
187
原创 【ST表|线段树】与众不同
题目链接题目描述A 是某公司的 CEO，每个月都会有员工把公司的盈利数据送给 A，A 是个与众不同的怪人，A 不注重盈利还是亏本，而是喜欢研究「完美序列」：一段连续的序列满足序列中的数互不相同。A 想知道区间 [L,R]之间最长的完美序列长度。输入格式第一行两个整数 N，M 表示连续 N 个月，编号为0 到N-1， M 表示询问的次数；第二行 N 个整数，第...
2019-04-06 10:55:18
1156
原创 【洛谷P1311】【递推|St】选择客栈
题目传送门题目描述丽江河边有nn家很有特色的客栈，客栈按照其位置顺序从11到nn编号。每家客栈都按照某一种色调进行装饰（总共kk种，用整数00~k-1k−1表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位...
2019-04-06 10:47:34
480
原创 【Floyd】【Hrbust】距离
Description 秒速 5 厘米,那是樱花飘落的速度,那么怎样的速度才能走完我与你之间的距离? 如果有其他阻碍的话，撕毁就可以了吧？ 给定一张 N 个点的完全图，每条边都是有向带权的。 N 轮操作，操作会对之后的图产生影响。 定义 Dis(x,y)表示 x 到 y 的最短距离 第 i 轮删掉点 Si，询问当前...
2019-04-06 10:31:00
179
原创 【Hrbust】合唱队形
Description 一年一度的清明节又要到了（？） 学校决定开个晚会庆祝一下（？） 由于泥工男孩子实在太多啦，跳舞是不可能跳舞的。于是他们决定站成一排唱歌。 众所周知的，音乐老师往往都是有强迫症的人。他想要让最终队形的身高序列从左到右先严格不减再严格不增。比如（1,2,3,2,1），(1,4,4,2),(1,2,3)都是合法序列，但是(8,...
2019-04-06 10:27:03
310
原创 【高斯消元|线性变换】hdu6465-水题
题目链接【题意】：给了3个点，转变成3个点，然后问，给你一个点，能否直接转化为某个位置上的一个点。【题解】：只要把a00,a01,b00,a10,a11,b10全部求出来，然后按照对应的线性变换转化即可。#include<bits/stdc++.h>using namespace std;int main(){ double a00,a...
2019-03-25 21:35:30
295
原创 【分块】余数求和
传送门【题目】：给你n,k; 【题解】：根据多个人的博客，我终于看懂了，其实就很简单，大家认真分析即可。首先对这个式子进行一系列地化简：发现每一个位置i，整除k都会得到不同的值。然后对于不同的值，进行分块处理。对于每一块来说，都有左右端点。左端点L=i，那么右端点呢？？？∵k/L=k/R∴R=k/(k/L)可能会出现k/L=...
2019-03-25 20:47:03
297
原创 【对称矩阵】Find Symmetries
题目链接【题意】：这个就是一个矩阵，然后问，这个矩阵通过往下移动或者往右移动可以有对称矩阵。最多可以移动(n*m)次。【题解】：看了很多人的博客，然后还是胜营兄告诉我的结论我才恍然大悟的。这个结论首先是：(x,y)等价于(x+t,y+t)(x+t,y+t)指的是整个矩阵移动，这个移动是循环的，就是说往右移动，左边的的补过来。如果(x,y)当前位置的矩阵是对称的，...
2019-03-25 20:14:34
271
原创 【CF_GYM101911】2018-2019 ACM-ICPC, NEERC, Southern Subregional Contest
参考博客：10月19日训练记录 CF GYM 101911A_Coffee Break【题意】：一个打工仔，想工作时候放松一下，但是又担心老板说他偷懒。他就有n杯卡布奇洛，然后想尽快喝完，每天工作m分钟，每次喝咖啡需要1分钟。然后问最少天数喝完，还要第i杯咖啡第几天喝。第i杯咖啡，a[i]指的是在a[i]这一个时刻休息，喝上这一杯咖啡。【题解】：需要用贪心的想法，就是把最小...
2019-03-25 19:58:44
425
原创 【数论】【AtCoder Beginner Contest 121D】异或前缀和
参考博客：Atcoder Beginner Contest 121 D - XOR World(区间异或和)结论1：[ 0 , 2^k ] 区间异或和为01、若n为奇数，那么最高位出现了n+1n+1次为偶数，可以去掉f(2k,n)=f(0,n−2k)，可以发现n−2k与n具有相同的奇偶性，可以利用同样的推导去掉最后f(0,n)的就取决于<4的部分，即mod 4后的异或和那么我...
2019-03-23 22:22:52
348
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人