- 博客(91)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 2020多校题目分布与补题计划✔☁⭐
牛客多校2020牛客暑期多校训练营（第一场）——叉姐签到题 F. Infinite String Comparision 半结论半暴力简单题 J. Easy Integration 分部积分，贝塔函数 I. 1 or 2 一般图最大匹配，带花树 H. Minimum-cost Flow 拉格朗日插值 A. B-Suffix Array 后缀数组，论文结论题中档题 A. Infinite Tree 线段树维护质因子分解查询LCA构建虚树跑换根DP D. Quadratic Fo
2020-07-28 22:44:20
363
原创 [新坑]以后做的简单数论题就总结在这了
emm，数学是我心中永远的痛。整除分块CF1263C Everyone is a Winner!UVA1363 约瑟夫的数论问题Joseph’s ProblemCF1263C Everyone is a Winner!题意给定nnn，求对任意正整数kkk，└nk┘\llcorner\dfrac{n}{k} \lrcorner└kn┘存在多少种不同的数值并输出。做法整除分块模...
2019-12-14 21:34:09
237
原创 Codeforces Round #680 div2补题
菜的真实，感觉没救了A.Array Rearrangment//#pragma comment(linker, "/STACK:102400000,102400000")#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>pii;//#define int ll#define ff first#define ss second#define deb
2020-11-02 20:03:23
229
原创 Educational Codeforces Round 96 (Rated for Div. 2)补题
A. Number of Apartments//#pragma comment(linker, "/STACK:102400000,102400000")#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>pii;//#define int ll#define ff first#define ss secondconst int maxn=2e5+
2020-10-17 15:52:14
197
原创 Codeforces Round #674 (Div. 3) F Number of Subsequences
上课打了一下，菜的真实，直接爆零QAQ。并不是很难的一场div3，我甚至觉得一个擅长dp的rating1800+选手这场可以AK。E是一个超简单的最大流问题，可惜当时没看，一直卡D。D题大体方向没错，如果能冷静分析，就能发现贪心的方法了，可惜并没有。C是一个均值不等式，我没看出来。这里补一下F题计数dp，因为F题确实不能自己写出来，立篇博客分析一下。题意给定一个由a、b、c、?符号构成的字符串，你可以用a、b、c替换?，求由给定的字符串sss生成的所有无?字符串中，子序列abc出现的总共次数。
2020-09-29 17:53:34
198
原创 Codeforces Round #672 (Div. 2)补题
上紫之后鸽了好久……也颓了很多。这场的题目A、B、C1、D是不难的。A逆序数，B位运算计数、C1贪心orDP、C2线段树or贪心、D排序组合数学+树状数组or直接扫一遍、E斜率优化DP。这场用Pokémon和Ori做题面，双厨狂喜（嘿我现在就在听Fleeing Kuro (alternate)）。A.Cubes Sorting思路冒泡排序最坏情况为严格单调递减，除了这种情况一定比n×(n−1)2\frac{n\times(n-1)}{2}2n×(n−1)小。代码//#pragma comm
2020-09-25 21:56:08
253
原创 Borůvka算法与异或生成树
Borůvka算法前几天才知道除了primprimprim和kruskalkruskalkruskal以外第三种求无向图MST的算法。适用情况平均 O(V+E)O(V+E)O(V+E)，最坏 O((V+E)logV)O((V+E)logV)O((V+E)logV)。因为没有kruskalkruskalkruskal好写，所以一般不用于MST裸题。相对于其他两种算法，适于处理边权由连接的两个点的点权通过某种计算方式得出的情况。前置知识点并查集、连通块流程对每个连通块，处理出与其他连通块连接
2020-07-29 16:35:26
454
原创 2020 Multi-University Training Contest 2补题
A.Total Eclipse题意给你一个nnn个点，mmm条边的无向图，第iii个点有一个权值bib_ibi，你每次要选择可操作的最大的一个连通子图，并将子图上所有点的权值减111，求出最小操作次数。思路先看正向思路：很明显是选择每一个连通块内最小的点权，并将整个连通块内所有的点都减去这个点权。将操作后bi=0b_i=0bi=0的点删掉，并对新的连通块重复此操作，记录操作次数即为答案。但是删点操作过于麻烦，这里要反向思考。代码//#pragma comment(linker, "/STA
2020-07-24 11:02:53
426
原创 Codeforces Round #657 (Div. 2)补题
被！教！育！了！要学习如何分析问题，仔细分析哪些部分可以优化哪些不可以。A. Acacius and String(1500)题意给你一个由小写字母和?组成的字符串，你可以将?替换为任意字母。问能否使abacaba恰好出现一次。思路很容易拐到KMP上去，因为长度小于50，测试小于5000组，可以考虑O(n2)O(n^2)O(n2)的做法。用KMP统计原串中abacaba的数量，若大于一个则不可能，如果等于一个，则将所有?替换为不相关的字母即可。如果等于0，则枚举起点进行暴力check，看看能
2020-07-21 00:40:19
243
原创 从[SDOI2011]消耗战开始的虚树学习
虚树浓缩信息，把一整颗大树浓缩成一颗小树 。——OIwiki\operatorname{OIwiki}OIwiki用途虚树是在树形dpdpdp中使用的一种特殊优化，适用于树中仅有少量关键节点且普通节点很多的情况。可以将关键点和他们的LCA\operatorname{LCA}LCA拿出来另建一棵树，并在这棵树上另外进行树形dpdpdp。前置技能邻接表或链式前向星存图、任意一种求LCA\operatorname{LCA}LCA的算法、单调栈（这个不会也可以直接学）步骤在原树上进行dfs，.
2020-07-15 01:09:51
164
原创 2020牛客暑期多校训练营（第一场）
先把AC的代码放上来吧，题解慢慢补。赛后总结赛中一人写了4题，有很大水分。F作为签到题也是一个结论，虽然并没有猜出来但是也水过了。J题是伽马函数，（虽然看着像二项式展开），计算了前几项OEIS也水过了，估计现场赛会推给队友吧。I题是HDOJ3551一般图最大匹配的简化版？我用最大流水过了，出题人说最大流做法是错误的。H是拉格朗日插值？我用费用流+map水过了……A. B-Suffix Array//#pragma comment(linker, "/STACK:102400000,1024
2020-07-13 00:57:48
382
1
原创 Codeforces Global Round 9A~F补题
A.Sign Flipping很简单，正负轮流就好//#pragma comment(linker, "/STACK:102400000,102400000")#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>pii;//#define int llconst int maxn=105,inf=0x3f3f3f3f,mod=1000000007;/
2020-07-09 00:20:11
334
1
原创 ACM中一些python3的使用方法
"""for T in range(0,int(input())):#T组数据 N=int(input()) a,b=map(int,input().split()) s=input() s=[int(x) for x in input().split()] for i in range(0,len(s)): a,b=map(int,input().split())"""import math#使用中括号[]定义一个列表# l=[23,'wt
2020-06-11 17:09:17
702
原创 Codeforces Round #645 (Div. 2)补题
好久没写题了……最近好像能做出2D了，不过上分还是困难。比赛传送门本场关键词贪心、找规律、前缀和、二分A.Park Lighting题意给你n×mn\times mn×m的网格，你可以在两个网格之间的边上放一个灯，这个灯将会照亮这两个网格。求出照亮所有的n×mn\times mn×m个格子的最小需要的灯数。思路贪心，只要nnn和mmm中间有一个是偶数，那么答案就是总格子数除以二；如果都为奇数，那么先暂时去掉一行，将这部分如上计算，再对剩下这一行贪心考虑。代码#include<b
2020-05-27 17:14:29
239
原创 牛客算法周周练1补题
阿楚姐骗我们这场只有div2A~C难度比赛传送门题解传送门，目前似乎没有官方题解A.Maximize The Beautiful Value题意给你长度为nnn的数组，$a_1 \delta $
2020-04-11 13:34:26
227
原创 Codeforces Round #629 (Div. 3)补题
这场在3月26日举行的div3，恰好我当时掉青，正好恰波低保。A. Divisibility Problem题意给你两个正数aaa与bbb，求出aaa最少增加多少才能被bbb整除思路显然ab\frac a bba的余数为a%ba \% ba%b，那么将这部分补足即可ans=b−a%b ans=b-a\% bans=b−a%b代码#include<bits/stdc++.h&...
2020-04-03 21:59:50
225
原创 牛客小白月赛23补题
待补完……本场题目难度分布签到题：J.真.签到简单题：E.蒙一发，I.大暴力中等题：B.质因数分解+二分，G.图论+组合数学，H.贪心牛客小白月赛23官方题解A.膜法记录题意nnn行mmm列的矩阵上面有一些点，你最多可以划掉aaa行bbb列，请问是否存在方法划掉网格上所有点。思路nnn范围非常小，考虑二进制状压枚举消灭的行，再暴力统计剩下的列，复杂度o(2nnm)o(2^nn...
2020-03-23 19:37:59
706
原创 Educational Codeforces Round 83 (Rated for Div. 2)补题
最近越打越菜，补题Educational Codeforces Round 83 (Rated for Div. 2)A. Two Regular Polygons思路没什么好说的，当nnn能被mmm整除的时候，mmm边形所有顶点一定可以与nnn边形重合。代码#include<bits/stdc++.h>using namespace std;typedef long ...
2020-03-17 20:00:07
146
原创 Codeforces Round #624 (Div. 3)补题
上场恰好掉到了1600，只能打星，血亏……这场签到手太慢了，C题数组开小了RE了一发，D题范围小了fst了……本场关键字分类讨论、并查集、前缀和、暴力A. Add Odd or Subtract Even(700)分类讨论，手慢了代码#include<bits/stdc++.h>using namespace std;typedef long long ll;con...
2020-02-28 17:32:03
167
原创 牛客小白月赛22补题
牛客小白月赛22比赛界面小白月赛22题解A.操作序列题意给出一个长度无限的数列，初始全部为零，有三种操作：增加操作：给下标为 ttt 的数加 ccc。特别注意，如果在下标[t−30,t+30][t-30,t+30][t−30,t+30]内有不为零的数，增加操作无效。削减操作：让数列中下标最小的不为零数变为零。查询操作：查询数列中下标为ttt的数字是多少。思路STL模拟，用m...
2020-02-23 15:31:25
832
1
原创 Codeforces Round #615 (Div. 3)补题
2020年1月24日，武汉加油。可能是我这三个月以来打的最菜的一场了……Codeforces Round #615 (Div. 3)本场关键词贪心、数学、乱搞、树的直径A. Collecting Coins给你nnn和a,b,ca,b,ca,b,c，问你是否可以将nnn完全分配给a,b,ca,b,ca,b,c，使分配后三者数量相同。#include<bits/stdc++.h&...
2020-01-24 17:28:46
246
原创 Codeforces Round #605 (Div. 3)补题
Rating:1361 → 1418，四题末尾，要是手速快一点就好了本场关键词手速、贪心、递推、DPA. Three Friends模拟题，我居然四发才过……直接GGAC代码#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ ll q,a[3]; cin>...
2019-12-18 11:05:51
291
原创 区间分块的两道例题
今日闲来无事乱翻刷题清单，看见分块这个专题，想起最近频频听人提起，便心血来潮学一波。区间分块十分好学，二十分钟就大概弄清楚基础操作。主要应用于一些区间离奇修改，线段树不好写的情况。核心思想是将长度为n的区间分割为长度为n\sqrt{n}n的n\sqrt{n}n区间。写出构建、修改、查询三个函数就可以了。例题P3870 [TJOI2009]开关题意一排n盏灯，初始都灭。按输入执行...
2019-12-04 22:49:48
285
原创 Codeforces Round #603 (Div. 2)补题
手速场……我们的知识面还不够广……Standing 2438，Rating1394 → 1404三题末尾，能力全方位缺失A. Sweet ProblemB. PIN Codes面向范围编程C. Everyone is a Winner!整除分块，CF上难得一见的模板裸题AC的代码#include<bits/stdc++.h>using namespace std;...
2019-11-30 19:30:30
277
原创 Codeforces Round #601 (Div. 2)补题
Codeforces Round #601 (Div. 2)官方题解A.Changing VolumeB.Fridge LockersC.League of Leesins思路乱搞题，统计每个数字出现次数，找到起点，减去当前三元组数目，再找新产生的cnt为1的数字，一个一个输出就好。D.Feeding Chicken题意r行c列矩阵网格，其中一些网格有水稻，并且在里面养了k只鸡，...
2019-11-28 18:00:51
199
原创 两道线段树入门题
哇，虽然上一篇博客是在十月，但感觉好像有三个月没写博客的样子。主要是之前太菜，不愿面对，加上最近犯懒，没有坚持写。P3372 【模板】线段树 1 题意题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.求出某区间每一个数的和输入格式第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数...
2019-11-06 20:42:24
144
原创 2019.10.2Codeforces Round #590 (Div. 3)补题
这几天CF好像被墙了呀，昨天晚上用m3的分站打的。题解在这A.Equalize Prices Again题意将n个商品设置为统一价格，但总价值不低于当前，求出该价格代码#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<...
2019-10-02 14:18:12
193
原创 2019.8.31Codeforces Round #582 (Div. 3)补题
ICPC银川网络赛办的什么玩意，把去年原题放上来了。宁夏理工真会玩。偷偷溜去补CF。题目官方题解
2019-09-03 20:12:23
171
原创 2019.8.28后缀数组入门...
8月23的CCPC网赛出了神奇的后缀数组。吓死本宝宝了。啃了五天板子，还是没太看懂。那么先用起来，再慢慢体会吧。两个串的最长公共连续子串POJ-2774 Long Long Message题意给你两个字符串，要求输出最长公共子串长度。思路参见大佬的博客字符串的任何一个子串都是这个字符串的某个后缀的前缀。求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。将...
2019-08-28 23:58:49
121
原创 2019.8.17Codeforces Round #579 (Div. 3)补题
这次div3打的有点菜啊题目官方题解又开始了自闭后的补题，这次不把题面复制过来了，我感觉都不会看的，想看就去原网站吧[可怜][委屈][要哭了]A.Circle of StudentsB. Equal Rectangles题意小朋友们是否依次连成了顺/逆的环思路硬写C. Common Divisors题意给你n个数，求出能整除所有这n个数的数的个数。思路求出这n个数的最大...
2019-08-17 23:20:28
205
原创 KMP学习困惑点，自学自闭自问自答
这两天在看KMP算法，也搜了各种解释和博客、视频来看。发现似乎大家的实现方式都不太一样，而且大多没讲到关键点上。（我现在还不是很懂啊哈哈哈哈哈哈哈哈哈尬笑）【经典算法】——KMP，深入讲解next数组的求解先来看道题HDOJ Problem-1686求文本T中单词W的出现次数AC代码#include<iostream>#include<cstdio>#i...
2019-07-27 17:13:47
518
原创 2019.7.26Codeforces Round #575 (Div. 3)补题
开始艰难的补题大业A. Three Piles of Candiestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputAlice and Bob have received three big piles of candies as a...
2019-07-26 15:16:56
431
原创 2019.6.15 HDOJ-2083简易版之最短距离
题目Problem-2083 简易版之最短距离Problem Description寒假的时候，ACBOY要去拜访很多朋友，恰巧他所有朋友的家都处在坐标平面的X轴上。ACBOY可以任意选择一个朋友的家开始访问，但是每次访问后他都必须回到出发点，然后才能去访问下一个朋友。比如有4个朋友，对应的X轴坐标分别为1， 2， 3， 4。当ACBOY选择坐标为2的点做为出发点时，则他最终需要的时间为 ...
2019-06-15 17:13:35
238
原创 2019.6.7HDOJ-1232畅通工程，查并集
哇，今天的CF六一欢乐场我没去诶，队友都去了。看来没打过CF的就我一个了，好自闭。HDOJ-1232题目Problem-1232畅通工程AC的代码#include<iostream>#include<cstdio>using namespace std;typedef long long ll;int city[1005];int findpar(int...
2019-06-07 22:47:30
170
原创 2019.6.4 HDOJ-20XX递推求解专题练习
最近好慌啊东北赛打铁了，虽说是意料之内，但还是好气啊题目地址递推求解专题练习（For Beginner）2044 一只小蜜蜂…/*HDOJ2044 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。其中，蜂房的结构如下所示。*/#include<stdio.h>long long fun(long long x);...
2019-06-04 16:06:45
232
原创 2019.5.14HDOJ-2112HDU Today（单源最短路）,AC率23.90%(10096/42251)
正经写的第一个C++程序，也是写的第一个迪科斯彻算法题题目HDU TodayTime Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 42251 Accepted Submission(s): 10096Problem Descri...
2019-05-14 22:57:40
297
原创 2019.4.1《C Primer Plus》第十三章部分编程练习，一个不想填的坑……
从第十四章滚回来看第十三章，做几道课后题熟悉熟悉……13.11.1/* count.c -- using standard I/O */#include <stdio.h>#include <stdlib.h> // exit() prototype#include<string.h>char *s_gets(char *st,int n);int...
2019-04-14 10:53:25
245
原创 2019.4.11HDOJ-2034人见人爱A-B，AC率27.64%(31104/112552)
今天下午好像被某人出卖给了学长……得找个机会敲打敲打他○( ＾皿＾)っHiahiahia…好久没做题了，把昨天晚上没写完的题补上中午有活动，没吃饱，晚上好好补一顿题目HDOJ-2034人见人爱A-BProblem Description参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个A-B求的是两个集合的差，就是做...
2019-04-11 16:06:06
246
原创 2019.4.5HDOJ-2024C语言合法标识符，AC率37.85%(40374/106656)
忽然发现有一道之前写的差不多但没有通过的题，于是拉出来改一下题目Problem Description输入一个字符串，判断其是否是C的合法标识符。Input输入数据包含多个测试实例，数据的第一行是一个整数n,表示测试实例的个数，然后是n行输入数据，每行是一个长度不超过50的字符串。Output对于每组输入数据，输出一行。如果输入数据是C的合法标识符，则输出"yes"，否则，输出“no...
2019-04-05 17:56:34
239
ACM ICPC World Final 2019题目
2019-04-08
Java 编程思想 第4版-Bruce Eckel
2019-03-30
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人