- 博客(283)
- 收藏
- 关注
RSS订阅原创 蓝桥杯历届真题 杨辉三角形【第十二届】【省赛】【B组】
蓝桥杯历届真题 杨辉三角形【第十二届】【省赛】【B组】题目链接-蓝桥杯历届真题 杨辉三角形题目大意将杨辉三角形按照从上到下、从左至右的顺序排成一个数列。输入一个正整数NNN，请你判断该数列中第一次出现NNN是数列中第几个数。解题思路思路一找规律找规律找规律附上代码#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long long#define lo
2022-04-07 15:48:46
1949
原创 2020 China Collegiate Programming Contest Weihai Site H.Message Bomb
H.Message Bomb题目链接-H.Message Bomb题目大意输入sss行数据，如果t=1t=1t=1，则表示第x个学生加入了第yyy个组。可以肯定的是，这个学生以前不在这个小组里。如果t=2t=2t=2，则表示第x个学生退出了第yyy个组。可以肯定的是，这名学生目前就在这个组里。如果t=3t=3t=3，则表示第xxx个学生在第yyy个组中发送了一条消息，可以肯定的是，那个学生现在就在小组里消息将广播给当前在同一组中的所有其他成员，求最后每个人各自收到的消息总数解题思路
2020-10-29 01:44:15
309
原创 Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
D. Minimal Height Tree题目链接-D. Minimal Height Tree题目大意有一棵树，其子节点都是按照升序摆列，现在给出广度优先搜索的访问次序，请你求出该树的最小深度解题思路bfs思想+贪心bfs思想+贪心bfs思想+贪心刚开始开始我们易得mp[0]=1，每次用mp[ans]++记录每一深度的可用的节点数目，对于一段严格单增的区间，必然是放在同一个父节点下面最好从第二个节点开始遍历，当a[i]<a[i-1]时，说明a[i]和a[i-1]不能连在同一
2020-10-29 01:03:40
222
原创 AcWing 145. 超市
145. 超市题目链接-145. 超市解题思路优先队列+贪心优先队列+贪心优先队列+贪心我们可以根据商品的过期时间对商品进行排序，然后创建一个优先队列，然后遍历排序后的商品对于每一个商品，我们把它的利润放入优先队列，如果此时该队列里的商品的数目大于该商品的过期时间，我们就可以把队首的商品弹出(因为队顶的元素利润是最小的)，此时队列中所有元素都满足条件且是该时刻利润最大的选择，重复该操作直至扫完所有商品为止最后我们统计一下队列中商品利润之和，即为最后要输出的答案具体操作见代码附上代码#
2020-10-23 00:34:52
131
原创 洛谷 P2261 [CQOI2007]余数求和
P2261 [CQOI2007]余数求和题目链接-P2261 [CQOI2007]余数求和解题思路附上代码#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long long#define lowbit(x) (x &(-x))#define endl '\n'using namespace std;const int INF=0x3f3f3f
2020-10-06 03:11:33
143
原创 2020牛客暑期多校训练营（第七场）D.Fake News
D.Fake News题目链接-D.Fake News题目大意判断12+22+…+n21^2+2^2+…+n^212+22+…+n2的和是否是一个平方数解题思路通过打表得出只有n=1n=1n=1或n=24n=24n=24的时候，12+22+…+n21^2+2^2+…+n^212+22+…+n2的和才是平方数附上代码#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define
2020-08-03 00:08:06
159
原创 2020牛客暑期多校训练营（第六场）G.Grid Coloring
G.Grid Coloring题目链接-G.Grid Coloring题目大意请你绘制一个尺寸为nnn的网格图。她可以用一个1～k1～k1～k对每个边都着色一次，要求如下：所有颜色的出现次数应该相同图形不应包含任何单色环图形的每一整条水平或垂直线应至少包含两种颜色解题思路我们首先判断没有解的情况，当n==1时一定一整条垂直线和平行线都只能有一种颜色，不满足要求333，当k==1时，肯定会存在单色环，不满足要求222，当(2*n*(n+1))%k!=0时，说明颜色不能平均分配，不满
2020-08-01 04:00:42
192
原创 2020牛客暑期多校训练营（第六场）B.Binary Vector
B.Binary Vector题目链接-B.Binary Vector题目大意每天RoundgodRoundgodRoundgod从维度为n，每一位由01组成的所有向量的集合中随机选择一个二进制向量，现在他想知道nnn天中选取nnn个线性独立向量的概率，答案如果是PQ（P,Q互质）\frac{P}{Q}（P,Q互质）QP（P,Q互质），就输出P⋅Q−1(mod 109+7)P \cdot Q^{-1} (\textrm{mod}\ 10^9+7 )P⋅Q−1(mod 109+
2020-07-30 02:41:28
222
原创 2020牛客暑期多校训练营（第六场）C.Combination of Physics and Maths
C.Combination of Physics and Maths题目链接-C.Combination of Physics and Maths题目大意一个矩阵的底面积SSS 定义为最后一行的数的和，重量FFF定义为所有数的和。现给你一个正整数矩阵，找一个p=FSp=\frac{F}{S}p=SF最大的可非连续子矩阵，输出ppp的最大值解题思路贪心贪心贪心假设ab>cd\frac{a}{b}>\frac{c}{d}ba>dc，那么ab−cd>0⇨ad−bcb
2020-07-29 18:53:15
141
原创 2020牛客暑期多校训练营（第五场）D.Drop Voicing
D.Drop Voicing题目链接-D.Drop Voicing题目大意给定一个1−n1-n1−n的排列ppp，有两种操作：将倒数第二个数放到开头将第一个数放到最后如果是连续的第一种操作，则只花费1，第二种操作不花费，求最少的花费使得ppp变成一个升序的排列解题思路LISLISLIS连续的操作111我们可以看成是前n−1n-1n−1个元素执行若干个循环移位，而连续的操作222我们可以看成是整个数组执行若干次循环移位因为第二种操作是免费的，所以我们可以把排列ppp看成一个环，
2020-07-29 02:38:47
126
原创 2020牛客暑期多校训练营（第五场）I.Hard Math Problem
I.Hard Math Problem题目链接-I.Hard Math Problem题目大意
2020-07-28 23:04:47
241
原创 2020牛客暑期多校训练营（第六场）E.Easy Construction
E.Easy Construction题目链接-E.Easy Construction题目大意构造一个长度为nnn的排列PPP，使得对于1−n1-n1−n中的每个iii，PPP都存在一个长为iii的连续子序列，而每个子序列的和模nnn都余kkk，如果有解就输出排列PPP，无解则输出−1-1−1解题思路首先sum1−n% n=(n(n+1)/2)%n≠ksum_{1-n}\%\ n=(n(n+1)/2)\%n≠ksum1−n% n=(n(n+1)/2)%n=k时，肯定
2020-07-28 03:17:04
172
原创 2020 Multi-University Training Contest 2-1001.Total Eclipse
1001.Total Eclipse题目链接-1001.Total Eclipse题目大意nnn个点mmm条边的无向图，每个点有一个正点权，每次选择一个连通子图，将里面的权值都减111，求所有点权为000的最小操作次数解题思路贪心+并查集贪心+并查集贪心+并查集常规思路就是每次选择一个最大的连通块，将里面的数同时减小，知道最小值变为000，然后将变成零的点删除，再分裂多个联通块继续执行上述操作但是这样操作明显会超时，那么我们就可以把操作顺序倒过来，用并查集反向处理连通块，先把大的点权值减
2020-07-28 01:34:59
211
原创 2020牛客暑期多校训练营（第五场）F.DPS
F.DPS题目链接-F.DPS题目大意请你编写一个程序，输出显示对敌人造成伤害的直方图，其中空格的长度为si=50dimaxi dis_i=50\frac{d_i}{max_i\ d_i}si=50maxi didi(向上取整)，必须通过将最后一个空格替换为‘∗’‘*’‘∗’来标记对敌人造成最大伤害的玩家，如果有多个最大值，则将其全部标记解题思路按照题目模拟，注意sis_isi向上取整，再特判一下输出*的情况即可，具体操作见代码附上代码#pragma GCC
2020-07-26 03:31:31
240
原创 2020牛客暑期多校训练营（第四场）F.Finding the Order
F.Finding the Order题目链接-F.Finding the Order题目大意有两条平行的线ABABAB和CDCDCD，给出ACACAC,ADADAD, BCBCBC, BDBDBD 的长度，分别为a,b,c,da, b, c, da,b,c,d。问是AB//CDAB//CDAB//CD，还是AB//DCAB//DCAB//DC解题思路如上图左侧图形，我们根据三角形两边之和大于第三边可得：OA+OC>AC,OB+OD>BDOA+OC>AC,OB+OD>
2020-07-26 03:07:38
161
原创 2020牛客暑期多校训练营（第四场）B.Basic Gcd Problem
B.Basic Gcd Problem题目链接-B.Basic Gcd Problem题目大意解题思路附上代码
2020-07-26 02:17:34
155
原创 2020牛客暑期多校训练营（第四场）H.Harder Gcd Problem
H.Harder Gcd Problem题目链接-H.Harder Gcd Problem题目大意集合AAA和BBB都是集合{1,2,.....,n}\{1,2,.....,n\}{1,2,.....,n}的子集，且A∩B≠∅A∩B≠∅A∩B=∅。问AAA和BBB最多有多少对数满足gcd(Ai，Bj)>1gcd(A_i，B_j)>1gcd(Ai，Bj)>1解题思路所有gcd>1gcd>1gcd>1的两个数肯定是倍数关系，最小也就是222倍，所以大于
2020-07-25 03:39:06
134
原创 2020牛客暑期多校训练营（第三场）E.Two Matchings
E.Two Matchings题目链接-E.Two Matchings题目大意定义序列 ppp，满足如下要求：是长度为nnn的排列满足ppi=i且pi≠ip_{p_i}=i且p_i≠ippi=i且pi=i定义一个字符串的费用为(p=∑n=1Nabs(ai−api))/2(p = \sum\limits_{n=1}^Nabs(a_i-a_{pi}))/2(p=n=1∑Nabs(ai−api))/2，aaa为给出的权值数组现求两个满足上述描述的序列p,qp,qp,q ，同时
2020-07-24 22:30:55
159
原创 2020牛客暑期多校训练营（第三场）C.Operation Love
C.Operation Love题目链接-C.Operation Love题目大意上图给出爱丽丝的右手，由二十个点组成，已知她的左手和右手对称，现给出二十个点，给你判断这些点组成的手是左手还是右手解题思路叉积叉积叉积我们知道可以利用叉积判断点和线的关系，逆正顺负所以可以计算长度为666和999这两个向量的叉积，如果相乘为正数，则为逆时针，为右手，反之是左手或者计算长度为888和999这两个向量的叉积，如果相乘为负数，则为逆时针，为右手，反之是左手具体操作见代码附上代码#pragm
2020-07-24 17:52:34
146
原创 2020牛客暑期多校训练营（第三场）A.Clam and Fish
A.Clam and Fish题目链接-A.Clam and Fish题目大意一个游戏包含nnn个阶段，每个阶段有四种类型：类型000：没有鱼也没有蛤。类型111：只有一只蛤。类型222：只有一条鱼。类型333：有一条鱼和一只蛤在每个阶段都可以执行四种操作之一：用一只蛤换一包鱼饵。如果有一条鱼，可以无需鱼饵抓到这条鱼。无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。跳过该阶段请你求出每局游戏中能抓到鱼的最大条数解题思路贪心贪心贪心用ans记录抓到鱼的个数，cn
2020-07-24 03:02:30
270
原创 2020牛客暑期多校训练营（第三场）B.Classical String Problem
B.Classical String Problem题目链接-B.Classical String Problem题目大意给你一个字符串sss，有qqq次操作，输入MMM xxx，表示将字符串最左边的xxx个字符移动到字符串最右边，MMM −x-x−x，表示将字符串最右边的xxx个字符移动到最左边。AAA xxx，表示询问当前字符串第xxx个位置的字符解题思路设置一个头指针head=0h
2020-07-24 01:08:54
145
原创 2020牛客暑期多校训练营（第三场）L.Problem L is the Only Lovely Problem
L.Problem L is the Only Lovely Problem题目链接-L.Problem L is the Only Lovely Problem题目大意当且仅当字符串sss以单词lovelylovelylovely开头时（不区分大小写），认为这个字符串sss是可爱的，请你判断字符串sss是否可爱解题思路因为不区分lovelylovelylovely的大小写，所以我们可以先用tolower()函数把前六个字符化为小写字母，然后再判断s.substr(0,6)是否 为lovely
2020-07-23 16:56:47
135
原创 2020智算之道初赛第二场 - 高校组 C.情报战
C.情报战题目链接-C.情报战解题思路并查集+虚根并查集+虚根并查集+虚根附上代码#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<stdio.h>#include<ctype.h>const int N=3e5+10;inline void read(int &x){ char t=getchar(); while(!isdigit(t)) t=getchar();
2020-07-23 15:51:49
151
原创 Codeforces Round #658 (Div. 2) D. Unmerge
D. Unmerge题目链接-D. Unmerge题目大意定义两个数组的合并merge(a，b)merge(a，b)merge(a，b)，每次将数组aaa第一个元素和数组bbb第一个元素中最小的那个放到序列sss中，同时删除那个最小的元素，现在给你一个长度为2n2n2n的序列，问该序列是否能由两个长度为nnn的数组合并而成解题思路分段+01背包分段+01背包分段+01背包因为每次都是选a,ba,ba,b中较小的那个放到数组sss中，所以我们可以得出如果b[i]>max(a[l…r])
2020-07-23 14:35:51
136
原创 Codeforces Round #658 (Div. 2) C1+C2. Prefix Flip
C1+C2. Prefix Flip题目链接-C1. Prefix Flip (Easy Version)字符串长度n<=1000n<=1000n<=1000，可操作次数k<=3nk<=3nk<=3n题目链接-C2. Prefix Flip (Hard Version)字符串长度n<=100000n<=100000n<=100000，可操作次数k<=2nk<=2nk<=2n题目大意给你两个二进制字符串a,ba,ba,b，每次
2020-07-23 02:28:09
112
原创 Codeforces Round #658 (Div. 2) B. Sequential Nim
B. Sequential Nim题目链接-B. Sequential Nim题目大意给 nnn 堆石子的数量，两人轮流从最左端的非空堆中取任意数量(>0)(>0)(>0)的石子，无法再取者输，假设两人都会采取最佳策略，判断谁会赢解题思路因为每堆石子只有ai=1a_i=1ai=1和ai>1a_i>1ai>1这两种情况，当ai=1a_i=1ai=1时是没有决策权的，该该堆只能一次取完，而当ai>1a_i>1ai>1时，可以选择一次
2020-07-22 21:38:09
145
原创 Codeforces Round #658 (Div. 2) A. Common Subsequence
A. Common Subsequence题目链接-A. Common Subsequence题目大意给出两个数组，请你找出二者最短的公共子序列解题思路如果两个数组中没有一样的数字，那说明没有公共子序列，直接输出NO即可如果有相同的数字，最短公共子序列肯定为111，任意输出一个相同的数字即可具体操作见代码附上代码#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#def
2020-07-22 20:56:11
114
原创 2020智算之道初赛第二场 - 高校组 B.构造字符串
B.构造字符串题目链接-B.构造字符串解题思路因为要保证nnn个串的公共前缀最长，所以只要同种字母数量每满nnn，公共前缀长度就+1+1+1即可注意题目数据范围，结果ansansans可能会爆int具体操作见代码附上代码#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<stdio.h>#include<ctype.h>inline void read(long long &x
2020-07-20 01:02:24
196
原创 2020智算之道初赛第二场 - 高校组 A.声控灯
A.声控灯题目链接-A.声控灯解题思路当m=1m=1m=1时，说明只有一层楼，这时小明一定在一楼当n=2n=2n=2时，不管小明在一楼还是二楼，两层的灯始终是亮着的，所以此时无法判断小明在几楼当m=3m=3m=3时，小明一定在中间那个楼层，输出a[2]即可当m=2m=2m=2时，说明是1,21,21,2层或n−1,nn-1,nn−1,n层亮灯，如果是前者说明小明在第一层，后者则说明小明在第n−1n-1n−1层，否则就输出−1-1−1具体操作见代码附上代码#pragma GCC o
2020-07-20 00:41:45
291
原创 Codeforces Round #656 (Div. 3) B. Restore the Permutation by Merger
B. Restore the Permutation by Merger题目链接-B. Restore the Permutation by Merger题目大意有一种排列ppp，将第二个p的元素插入到第一个保持相对顺序的元素中，结果是长度为2n的序列aaa，现给你插入后的序列aaa，请你求出原序列ppp解题思路因为是保持相对顺序插入的，所以我们直接遍历序列aaa找排列即可因为排列中不能有重复的元素，为了方便我们可以将已经输出的元素存入set，用s.count(a[i])判断已经确定的pp
2020-07-18 03:13:01
231
原创 Codeforces Round #656 (Div. 3) A. Three Pairwise Maximums
A. Three Pairwise Maximums题目链接-A. Three Pairwise Maximums题目大意给你三个正整数x、y和z，请你找到正整数a，b和c，使得x=max(a，b)，y=max(a，c)x=max(a，b)，y=max(a，c)x=max(a，b)，y=max(a，c)且z=max(b，c)z=max(b，c)z=max(b，c)，或者确定不可能找到这样的a，ba，ba，b和ccc(你可以以任意顺序输出a,b,ca,b,ca,b,c)解题思路因为x=max(
2020-07-18 02:52:43
1396
原创 Educational Codeforces Round 91 (Rated for Div. 2) A. Three Indices
A. Three Indices题目链接-A. Three Indices题目大意给你一个1−n1-n1−n的排列，请你找出三个下标i、ji、ji、j和kkk，使得：1≤i<j<k≤n1≤i<j<k≤n1≤i<j<k≤npi<pj且pj>pkp_i<p_j且p_j>p_kpi<pj且pj>pk如果没有满足条件的下标就输出NO解题思路如果该序列是按照顺序排列，即递增或递减的，显然没有答案否则必定满
2020-07-17 03:04:20
269
原创 洛谷 P1091 合唱队形
P1091 合唱队形题目链接-P1091 合唱队形解题思路DPDPDP因为需要保证队形是先升后降的，最少的同学出列即是留下最多的同学，所以我么可以正向(1→n)(1→n)(1→n)和反向(n→1)(n→1)(n→1)分别求一次最长递增子序列，然后再枚举以aia_iai作为最高同学队列中的人数，取最大值即可dp[0][i]表示正向时以第iii个人结尾最长递增子序列，dp[1][i]表示反向时以第iii个人结尾最长递增子序列，那么以aia_iai作为最高同学队列中的人数就为dp[0][i]+
2020-07-15 02:21:52
261
原创 2020智算之道初赛第一场 - 高校组 C.字符串
C.字符串题目链接-C.字符串解题思路如果字符串sss的长度大于字符串ttt的长度，那么sss的任何排列都不可能是ttt的子串，直接输出000即可因为要求sss的不同排列有多少种是ttt的子串，将sss的不同排列全部求出来肯定会超时，我们可以直接计算sss中每个字母的个数，那么ttt中如果有子串中各个字符个数与sss相同则说明是该子串是sss的一种排列ttt中满足条件的子串可能会有排列相同的情况，这时我们就可以将每个满足条件的子串放入set容器中去重，最后输出set中元素个数即可在i>
2020-07-14 02:01:49
387
原创 2020智算之道初赛第一场 - 高校组 B.开关
B.开关题目链接-B.开关解题思路我们只需判断有几对相邻的开关状态不同即可，也就是判断该字符串由几段区间组成比如1001该区间，有cnt=2cnt=2cnt=2对相邻的开关状态不同，我们需要先翻转第一个开关0，等于翻转一次后跟后面的1合并成一个区间，翻转222次后，该字符串中的所有字符一定全部相同因为我们是要把开关全部关闭(即全为000)，这时只需判断最后一个字符是否为111即可，如果为111说明需要整个区间在翻转一次(cnt++)，如果为000则说明已经全部关闭，无需再翻转具体操作见代码
2020-07-14 01:42:37
365
原创 2020智算之道初赛第一场 - 高校组 A.排队
A.排队题目链接-A.排队解题思路暴力暴力暴力对于每个窗口的aia_iai，我们可以for(int j=a[i];j<=n;j+=a[i])循环枚举1−n1-n1−n范围内aia_iai的倍数，然后用vis[j]vis[j]vis[j]标记已经出队的人，以免后面重复计算对于枚举到的aia_iai的倍数且未被标记的编号，我们用cnt++记录，最后n−cntn-cntn−cnt即为队伍中剩下的人数具体操作见代码附上代码#pragma GCC optimize("-Ofast"
2020-07-14 01:28:16
409
原创 Codeforces Round #655 (Div. 2) C. Omkar and Baseball
C. Omkar and Baseball题目链接-C. Omkar and Baseball题目大意给定一种操作可以使得某区间内所有数字任意排列，但是要满足排列后该区间所有数字都不能在自己原来的位置上，问最少需要多少次操作可以将原本的序列变为递增排列解题思路我们可以找位置不对的区间有多少个：如果有000个，显然该序列本身就是升序的，不需要操作如果只有111个，那么直接一次操作就行如果位置不对的区间大于111个，我们可以通过一次操作先把中间正确位置的元素换换位置，这样就把序列转化为
2020-07-13 02:05:56
210
原创 Codeforces Round #655 (Div. 2) B. Omkar and Last Class of Math
B. Omkar and Last Class of Math题目链接-B. Omkar and Last Class of Math题目大意解题思路附上代码#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long long#define lowbit(x) (x &(-x))#define endl '\n'using namespace
2020-07-13 01:06:59
300
1
原创 Codeforces Round #652 (Div. 2) C. RationalLee
C. RationalLee题目链接-C. RationalLee题目大意给你nnn个数，有kkk个朋友，每个朋友要拿其中wiw_iwi个数，每个人获得的贡献是他拿的数的最大值+最小值，请求出所有人能获得的最大贡献解题思路双指针+贪心双指针+贪心双指针+贪心我们先对数组a[],b[]a[],b[]a[],b[]排序，当wi=1w_i=1wi=1时，最大值等于最小值，所以我们要保证wi=1w_i=1wi=1时，拿剩下数中最大的因为每个人获得的贡献是他拿的数的最大值+最小值，所以最大值
2020-07-12 02:13:20
197
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人