- 博客(653)
- 收藏
- 关注
RSS订阅
原创 关于codeforces访问过慢的问题
因为codeforcescodeforcescodeforces的文本使用的是googlegooglegoogle的关系，中国访问的就极其慢，然后还很容易加载不出来(之前还好，最近就特别崩)，然后上网查了一下，其中有一个方法是修改hostshostshosts的方法，这个方法现在无法使用了，好像是因为360360360的那个停用了，有梯子的话，就可以直接访问主站了，如果没有的话，可以通过国内的镜像访问，网址：https://codeforces.ml/https://codeforces.ml/https:
2020-08-14 15:44:05
2230
原创 PTA 题目集 题解
PTA 乙级 题解 查看题解 PTA 数据结构与算法题目集（中文）题解 查看题解 PTA 基础编程题 题解 查看题解 PTA 天梯赛 题解 查看题解 ...
2020-03-10 23:22:44
3282
1
原创 觉得写的比较好的算法链接总结
有些时候算法很久没用了，容易遗忘，然后想重新学习的时候会忘记一些曾经相通的重要的点，然后翻过去学习的材料，也容易找不到过去学习时候讲的比较好的材料（比如博客之类的），所以写了这个博客记录一下自己觉得写的比较好的大佬的博客（主要是自己懒得写博客），以便于自己复习，读者也可以根据这些博客进行学习。莫队算法 算法 回文自动机 算法（fail指针跳转后的位置尽量能与n构成回文）...
2020-03-02 16:47:43
260
原创 codeforces 题解
1285A Mezo Playing Zoma 查看题解 字符串 1285B Just Eat It! 查看题解 最大连续子序列 1285C Fadi and LCM 查看题解 数论 1285D Dr. Evil Underscores 查看题解 dfs+位运算 ...
2020-01-10 15:42:39
1240
原创 感悟大学一年的成长经历
大一终于随着最后的期末考试结束而结束，经历一年的学习，想把这一年的学习的感悟写下来，以后回看这篇文章的时候会不会想起当年成长的自己（嘻嘻嘻），一年的学习大学就这样过去了1/3（第四年肯定是要么实习，要么考研）也是挺有感触的。 初入大学，对于编程这一块真的就是个小白，连最基本的c语言都不知道，然后通过不断的学习的深入，渐渐也对编程有着不错的兴趣（当初没有报错专业也是挺开心的）。这一年感觉最...
2019-07-11 09:45:49
2830
原创 HDU 题解
1043 Eight 查看题解 八数码 1166 敌兵布阵 查看题解 线段树/树状数组 1285 确定比赛名次 查看题解 拓扑排序 1370 Biorhythms 查看题解 暴力/中国剩余定理 1573 X问题 查看题解 扩展中国剩...
2019-06-11 10:56:09
881
原创 POJ 题解
1000 A+B Problem 查看题解 水题 1002 487-3279 查看题解 水题 1003 Hangover 查看题解 水题 1006 Biorhythms 查看题解 暴力/中国剩余定理 1017 Packets 查看题解 贪...
2019-06-11 00:55:44
1300
原创 Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics) 题解
A. Even Subset Sum Problem题目题意：给定一个由nnn个正整数组成的数组aaa。找到其元素的非空子集，使其和为偶数(即，可被222整除)或确定不存在这样的子集。思路：总共由三种情况：只要出现一个偶数，那么一定有一个子序列就是它自己。出现至少两个奇数，那么和一定为偶数。如果只有一个奇数的情况下，那么此时这个序列才不为偶数。#include <iostream>#include <cstring>#include <cstdio
2020-09-16 14:25:08
355
原创 codeforce D. Stoned Game
题目题意：你有nnn堆石子，然后两个人每一次取一堆中的一个，但是不能同时取同一堆，谁先无法取谁输。思路：因为每次取最优的话，那么也就是取最大的那一堆，所以我们可以分成两种情况：第一种就是有一堆超过了n2\frac{n}{2}2n，那么第一个取的人一直取这一堆能赢了。第二种的话，最后取完肯定会出现1,11,11,1这种情况，因为每一次都取最大的话，然后最大的那堆又小于n2\frac{n}{2}2n，那么每一次最大的那一个经过了一系列的取之后一定会变成次大或者并列最大，如果变成次大的情况下，.
2020-09-10 12:52:20
385
原创 codeforces C. Multiples of Length
题目题意：给你一个序列，你需要将这个序列进行三次操作使得ai=0(1≤i≤n)a_i=0(1\leq i\leq n)ai=0(1≤i≤n)，在操作中你可以选定一个区间(l,r)(l,r)(l,r)，然后对于区间里面的每个数字你可以增加(r−l+1)∗ci(l≤i≤r)(r-l+1) * c_i(l\leq i\leq r)(r−l+1)∗ci(l≤i≤r)，cic_ici可以随意取，请你输出这三次操作中的l,r,c1∗(r−l+1)......l,r,c_1* (r-l+1)......l,r.
2020-09-09 22:47:43
366
原创 codeforces B. Power Sequence
题目题意：给你一个序列aaa，你需要找到min(∑i=1i≤n∣ai−ci∣)min(\sum_{i=1}^{i\leq n} |a_i-c^i|)min(∑i=1i≤n∣ai−ci∣)思路：我们可以暴力出所有的情况，我们假设全部都是1e91e91e9的情况，那么和最多最多是1e5∗1e91e5*1e91e5∗1e9，也就是1e141e141e14，因为n≥3n\geq 3n≥3，所以iii最大的情况就是sqrt(1e14)sqrt(1e14)sqrt(1e14)，所以就是遍历111~1e7.
2020-09-09 14:45:12
253
原创 codeforces A. Juggling Letters
题目题意：我们有nnn个字符串，你可以将这些字符串的字母进行随意移动，问是否能够让这nnn个字符串相等。思路：我们只要将所有的字符串的字母的数量求出来，如果这个字母的数量能够均分给这nnn个字符串，那么就可以相等。#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <queue>#include <vecto.
2020-09-09 13:49:49
262
原创 codeforces D. Zigzags
题目题意：给你一个序列aaa，问你有几个四元组满足i<j<k<l,ai=ak,aj=ali<j<k<l,a_i=a_k,a_j=a_li<j<k<l,ai=ak,aj=al。思路：因为ai=ak,aj=al→ai∗maxn+aj=ak∗maxn+ala_i=a_k,a_j=a_l\to a_i*maxn+a_j=a_k*maxn+a_lai=ak,aj=al→ai∗maxn+aj=ak∗maxn+al，所以我们可以枚举j.
2020-09-01 22:59:16
324
原创 codeforces C. Binary String Reconstruction
题目题意：如果存在wi−x=1,wi+x=1w_{i-x}=1,w_{i+x}=1wi−x=1,wi+x=1其中一个的话，那么此时wi=1w_{i}=1wi=1否则wi=0w_i=0wi=0，给你一个序列，问这个序列是否这个条件。思路：因为出现000的情况说明wi−x=wi+x=0w_{i-x}=w_{i+x}=0wi−x=wi+x=0，所以我们可以通过000将所有的为000的情况都计算出来，然后我们判断wi=1w_{i}=1wi=1的时候，是否出现wi−x=wi+x=1w_{i-x.
2020-09-01 21:50:24
310
原创 codeforces B. RPG Protagonist
题目题意：给你两个数字p,fp,fp,f，还有cnts,cntwcnt_s,cnt_wcnts,cntw，你需要知道ss,ww(ss≤cnts,ww≤cntw)ss,ww(ss\leq cnt_s,ww\leq cnt_w)ss,ww(ss≤cnts,ww≤cntw)并且ss∗s≤p,ww∗w≤fss*s\leq p,ww*w\leq fss∗s≤p,ww∗w≤f，问ss∗s+ww∗wss*s+ww*wss∗s+ww∗w最大是多少。思路：枚举一下ssssss，然后根据ss,ww(ss≤cn.
2020-09-01 21:37:30
264
原创 codeforces A. String Similarity
题目题意：给你一个nnn，现在给你一个010101序列strstrstr，你需要构造一个010101序列sss保证str[1,n]str[1,n]str[1,n]和s[i,i+n]s[i,i+n]s[i,i+n]相似。思路：因为需要保证每一个都需要有一个一样的，那么就是每一个都需要有一个相似的，如果我们设第iii个相似的话，那么也就是在s[i,i+n]s[i,i+n]s[i,i+n]中s[i+i]=str[i]s[i+i]=str[i]s[i+i]=str[i]。#include <ios.
2020-08-31 22:45:14
197
原创 Educational Codeforces Round 94 (Rated for Div. 2) 题解
A. String Similarity 查看题解 构造
2020-08-31 21:21:49
240
原创 codeforces E. Divide Square
题目题意：给你n,mn,mn,m两个整数代表着垂直线和水平线，问这些线可以将这个图形分成几个部分？思路：我们可以发现，如果想要将这个图形分割只有这个线和图形的两条边界有交点或者在正方形中出现交点，因为这个线和正方形的边界一定相交(题目有说)，然后我们以可以确定yyy轴，然后用线段树/树状数组完成扫描，由于树状数组的点是从111开始的，所以这个正方形我们需要000~1e61e61e6变成111 ~1e6+11e6+11e6+1。#include <iostream>#include .
2020-08-28 18:50:15
289
原创 codeforces D. Maximum Distributed Tree
题目题意：给你一棵数，现在你要将这棵树上附上权值并且满足一下条件：每一个权值都是正整数。n−1n-1n−1个数的乘积要等于kkk第三个条件看不懂QAQQAQQAQ，但是应该不太重要…现在设置f(u,v)f(u,v)f(u,v)为节点u→vu\to vu→v的权值，需要你求出最大的∑i=1n−1∑j=i+1nf(i,j)\sum^{n-1}_{i=1}\sum^n_{j=i+1}f(i,j)i=1∑n−1j=i+1∑nf(i,j)思路：我们先通过dfsdfsdfs树求出每一条边会经过.
2020-08-23 15:46:59
457
2
原创 codeforces C. Mere Array
题目题意：给你一个序列，如果这个序列中的两个数满足gcd(ai,aj)=mini=1nagcd(a_i,a_j)=min^n_{i=1}agcd(ai,aj)=mini=1na，那么这两个数字就可以进行置换，问最后能不能通过置换将这个序列变成一个不递减的序列。思路：如果要满足gcd(ai,aj)=mini=1nagcd(a_i,a_j)=min^n_{i=1}agcd(ai,aj)=mini=1na，那么肯定有ai%Min=aj%Min=0a_i\%Min=a_j\%Min=0ai%.
2020-08-23 15:16:54
281
原创 codeforces B. Ternary Sequence
题目题意：给你666个数字分别代表两个序列中的0,1,20,1,20,1,2的数量，然后通过ci={ai∗bi,ai>bi0,ai=bi−ai∗bi,ai<bic_i=\begin{cases} a_i*b_i, & \text{$a_i>b_i$} \\0, & \text{$a_i=b_i$}\\-a_i*b_i, & \text{$a_i<b_i$}\end{cases}ci=⎩⎪⎨⎪⎧ai∗bi,0,−ai∗bi,ai>bi.
2020-08-23 14:54:47
326
原创 codeforces A. Distance and Axis
题目题意：给你两个整数n,kn,kn,k，其中AAA点刚开始的坐标为nnn，现在你要保证∣(B−0)−(A−B)∣=k|(B-0)-(A-B)|=k∣(B−0)−(A−B)∣=k，问BBB的坐标是多少。思路：我们将公式化简一下可以得到∣2∗B−A∣=k|2*B-A|=k∣2∗B−A∣=k，我们假设A>2∗BA>2*BA>2∗B，那么就有(A−k)/2=B(A-k)/2=B(A−k)/2=B即(n−k)/2=B(n-k)/2=B(n−k)/2=B，所以当n<kn<kn&.
2020-08-22 23:31:04
264
原创 codeforces E. Omkar and Duck
题目题意：给你一个数字nnn，现在你需要构造出一个n∗nn*nn∗n的矩阵，然后(1,1)−>(n,n)(1,1)->(n,n)(1,1)−>(n,n)(只能往下或者右走)，最后我们可以得到一个路径和sumsumsum，你需要得到sumsumsum的路径唯一，输入中直接给你这个矩阵的路径和，让你输出这个唯一的路径。思路：要使路径唯一，要使路径和唯一，那么我们就可以想到2x2^x2x，这样当xxx不相同的时候，那么我们不可能会出现两两相加等于第三个的情况，所以我们可以先构造一个矩阵.
2020-08-18 19:53:59
422
原创 codeforces D. Omkar and Bed Wars
题目题意：有一个游戏，把大家围成一个圈，每一个人都可以攻击相邻的人，这样会造成人受到的攻击数为0,1,20,1,20,1,2，当只受到一个人的攻击时，此时你需要反击这个人才算合理，如果没有反击的话，你需要进行纠正，问最少需要纠正多少次。思路：首先有两种情况：全部都为同一个方向的(比如RRRRRR)，当我们需要最少纠正的时候，我们可以每三个纠正一次，因为可以将RRRRRRRRR变成RRLRRLRRL，这样收到攻击数就成了0,2,10,2,10,2,1，符合条件，所以一次性最多能够让333个符合条.
2020-08-17 15:05:17
517
原创 codeforces C. Omkar and Waterslide
题目题意：给你一个序列，你有个操作，可以将连续不递减的区间里面的值都增加111，问最后要使这个序列变成不递减的序列要进行多少次这样的操作。思路：如果出现递减的情况，也就是ai<ai−1a_i<a_{i-1}ai<ai−1，那么我们就需要将aia_iai增加到与ai−1a_{i-1}ai−1一样的高度，如果出现ai+1<aia_{i+1}<a_iai+1<ai的时候，那么只要将ai+!a_{i+!}ai+!增加到aia_iai一样的高度，然后再一起.
2020-08-17 14:30:32
344
原创 codeforces B. Omkar and Infinity Clock
题目题意：给你一个n,kn,kn,k和一个aaa序列，你可以进行操作，计算出aaa中的最大值ddd，然后ai=d−aia_i=d-a_iai=d−ai，进行kkk次这样的操作，求出最后的aaa序列。思路：我们列出操作后的序列：第一次：b1,b2,b3,....bn(max=d)b_1,b_2,b_3,....b_n(max = d)b1,b2,b3,....bn(max=d)第二次：d−b1,d−b2,d−b3,....,d−bn(max=d)d-b_1,d-b_2,d-b_3,.
2020-08-17 14:16:12
343
原创 codeforces A. Omkar and Password
题目题意：给你一个序列，现在这个序列中可以将相邻的不同的元素相加，可以重复若干次，问最后的会剩下几个元素。思路：除非全部相等的话，答案是nnn，否则都是111，因为只要有两个元素是不同的，肯定可以全部消除，比如A=B+CA=B+CA=B+C，那么我们就可以将A+BA+BA+B，这样ans=1ans=1ans=1。#include <iostream>#include <cstring>#include <cstdio>#include <algor.
2020-08-17 12:58:26
389
原创 codeforces E. Two Types of Spells
题目题意：我们总共有两种法术，一个闪电法术，一个火焰法术，闪电法术之后能够将下一个法术的伤害翻倍，现在你有两种操作学习/忘记，问你每一次操作后最大的伤害是多少。我们总共有两种法术，一个闪电法术，一个火焰法术，闪电法术之后能够将下一个法术的伤害翻倍，现在你有两种操作学习/忘记，问你每一次操作后最大的伤害是多少。我们总共有两种法术，一个闪电法术，一个火焰法术，闪电法术之后能够将下一个法术的伤害翻倍，现在你有两种操作学习/忘记，问你每一次操作后最大的伤害是多少。思路：我们可以设一个两个set数组，一个用.
2020-08-16 21:33:17
282
原创 codeforces D. Colored Rectangles
题目题意：给你三个序列，你每次可以选择三个序列中的两个元素，但不能是相同序列的，然后进行相乘，问最后的相乘的和最大是多少。给你三个序列，你每次可以选择三个序列中的两个元素，但不能是相同序列的，然后进行相乘，问最后的相乘的和最大是多少。给你三个序列，你每次可以选择三个序列中的两个元素，但不能是相同序列的，然后进行相乘，问最后的相乘的和最大是多少。思路：我们假设此时三个序列各选了i,j,k个数字ans=dp[i][j][k],那么当我们此时选择第i+1和j+1个数字的时候,那么此时ans=dp[i][.
2020-08-16 00:43:12
226
原创 codeforces C. Good Subarrays
题目题意：在一个序列中，我们需要求出有多少个区间满足∑i=lrai=r−l+1\sum^r_{i=l}a_i=r-l+1∑i=lrai=r−l+1。思路：在这题之前我们应该可以想到一个类似的一题，就是有多少个区间满足∑i=lrai=0\sum^r_{i=l}a_i=0∑i=lrai=0，这个就是计算前缀和，如果某两个前缀和相等，那么也就是说明cnty+x−cntx=0cnt_{y+x}-cnt_x=0cnty+x−cntx=0满足∑i=xx+yai=0\sum^{x+y}_{i=x}a.
2020-08-16 00:14:25
336
原创 codeforces B. Substring Removal Game
题目题意：有两个人，每一次都可以取序列中连续的部分，然后取完的两边会相邻，问先取的那个人最多可以取多少个111，两个人都取最优。思路：我们直接将连续的111个数全部提取出来，先取的是拿最大的，后取的第二大...............直到取完，所以我们取下标为偶数位的就行了（下标000开始）。#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#.
2020-08-15 21:58:44
910
原创 codeforces A. Bad Triangle
题目题意：给你一个序列，问这些序列中取三个数字无法构成三角形的元素，随意一组，如果都可以组成，那么输出−1-1−1。思路：三角形两条边的和必大于第三条边，那么我们直接将两个最小的加起来直接和最大进行相比，如果这个可以构成三角形的话，那么这个里面都可以构成三角形。#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <queu.
2020-08-15 21:48:02
235
原创 Educational Codeforces Round 93 (Rated for Div. 2) 题解
A. Bad Triangle 查看题解 排序
2020-08-15 19:51:05
258
原创 codeforces D. Boboniu Chats with Du
题目题意：给你一个aaa序列，对于每一个aia_iai，如果此时的ai>ma_i>mai>m，那么接下去的ddd个aia_iai将无效，在可以将aaa序列重新排列的情况下，有效的aia_iai的总和最大是多少。思路：我们先将ai≤ma_i\leq mai≤m的数量得出来，记作kkk，那么我们假设选择的ai>ma_i>mai>m的个数为xxx个(x≤n−k)(x \leq n-k)(x≤n−k)，那么最大有效的就是(n−1)/(d+1)+1(n-1)/.
2020-08-14 17:04:51
319
原创 codeforces C. Boboniu and Bit Operations
题目题意：给你两个序列a,ba,ba,b，然后对于让ci=ai&bj(1≤i≤n,1≤j≤m)c_i=a_i \& b_j(1\leq i\leq n,1\leq j\leq m)ci=ai&bj(1≤i≤n,1≤j≤m)，我们需要让最后的c1∣c2∣....∣cnc_1|c_2|....|c_nc1∣c2∣....∣cn最小。思路：因为题目的a,ba,ba,b的范围是292^929，所以我们可以直接cic_ici的最大也不可能超过292^929，那么我们就可.
2020-08-14 16:30:01
277
原创 codeforces B. Boboniu Plays Chess
题目题目：我们有一个起始点，现在你要从这个点出发，然后访问所有的点并且只能访问一次，每一次走可以像车一样，到达一行或一列的任何一个点（经过不算到达），现在你需要打印出路径。思路：因为可以随意到达每一行的任何一个地方，所以我们就可以将每一行每一列看成一个环，然后一行访问完后要确定最后一个点，然后去下一行，这个时候我们就可以确定一个点（起始点最好），然后就以这个点为中心的列，然后遍历一圈（看成环），这样下一个点应该是中心列的前一个或者后一个，然后反方向遍历这样就又回到了中心列了。#include &.
2020-08-14 16:05:21
370
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人