1 要无愧于人

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 4w+

AtCoder Beginner Contest 177 D - Friends(并查集求最大环或链的长度)

题目传送题意:给你N个人,这n个人,有些人是朋友,有些人不是朋友(如果1和2是朋友,2和3是朋友,那么1和3也是朋友),现在问,你最少分多少组,使得每一组中的每一个人都不是朋友思路:其实就是求最长的环,或者一条链的最长长度,那么这几个人是肯定不能在一起的,所以这就是最少的分组,用并查集求出即可AC代码#include <bits/stdc++.h>inline int read(){char c = getchar();int x = 0,s = 1;while(c < '

2020-08-29 22:22:49

AtCoder Beginner Contest 177 C.Sum of product of pairs(数学,前缀和)

题目传送题意:给你n个数,要你求模上1e9+7的结果思路:观察一下可得乘法分配律,所以我们把分配律合并一下即可,那么我们求一个前缀和,则每一个数对答案的增值为这个数乘以他后面所有数的和取模得写好,不然爆数据AC代码#include <bits/stdc++.h>inline int read(){char c = getchar();int x = 0,s = 1;while(c < '0' || c > '9') {if(c == '-') s = -1;c =

2020-08-29 22:15:07

01bfs

题目传送题意:一张 n * m 的地图,上面有空地和墙。给定起点和终点,你可以往上下左右相邻的结点走,但是只能走空地,你也可以用魔法跳到以当前点为中心,5 * 5的范围内的任意空地。要求出走到终点使用魔法的最少次数。思路:我最开始的思路是并查集求连通块(块是一个相互连通的方格区,因为这一块的步数一定是一样的),然后判断从起点块到终点块的最小值,我觉得是没有问题,应该是哪里写错了,导致wa了。后来了解到,这个是典型的01bfs我理解的01bfs是,在最短路中,花费的代价为0和1的时候,要求代价最少

2020-08-29 20:15:52

Codeforces Round #665 (Div. 2) B. Ternary Sequence(思维,数学)

题目传送题意:给你a,b俩个数组,数组中只有0,1,2三种元素,a中有x1个0,y1个1,z1个2。b中有x2个0,y2个1,z2个2。现在你可以任意排列俩个数组,然后对应位进行如下操作合成c数组问最大的c数组的和是多少思路:我们先分析,哪些对答案有贡献。2 对 0 ,2 * 0 = 0,无贡献2 对 1 ,2 * 1 = 2,贡献22 对 2 , 贡献01 对 0 , 贡献01 对 1 , 贡献00对任何数也是0所以不难发现,对答案有贡献的只有2和1这一对所以我们贪心匹配:1

2020-08-22 11:27:46

Codeforces Round #665 (Div. 2) A. Distance and Axis(思维,数学)

题目传送题意:给你一个点A(n,0),现在要求你找到一个整数x,使得abs(x - (abs(n-x)) == k,给出n和k,现在你可以进行操作n+1,或者n-1多次,问最少多少次操作使得有非负整数x的存在思路:1.当n都小于k的时候,那么在n前面找一个点使得上述等式成立那是必不可能的,所以我们只有将n一直加到k,然后x选择0即可2.当n大于x的时候,有等式x - (n-x) == k,(因为是对称的,所以这里我们直接假设x大于(n-k))那么化简得到x = (k+n)/2,要x为整数,当(k+

2020-08-22 10:50:58

Codeforces Round #665 (Div. 2) C. Mere Array(数学)

题目传送题意:给你n个元素的数组,现在规定如果gcd(a,b) == Min(数组中的最小值),那么则可以交换a,b的值,现在问,是否能通过这个操作,使得数组不递减思路:1.我们先对改数组排个序,然后进行操作后的数组必须和现在排序后的数组一样。2.然后我们把没排序的数组与排了序的数组相对应,看看相同的位置上,那些数不同,那么不同的数的位置是肯定被交换了的。3.在这些肯定被交换了的数上,我们只需要判断gcd(a,Min) 是否等于Min即可。为什么这样判断呢?假设现在能交换乘不递减的数组,那么

2020-08-22 10:30:44

Codeforces Global Round 10 D. Omkar and Bed Wars(思维,分块)

题目传送题意:n个人站成一圈,每个人有一个朝向(L或R)。每次操作可以改变一个人的朝向。输入每个人初始的朝向,输出至少经过多少次操作。使得一个人只被一个人攻击时,这个人与攻击他的人必须相互攻击,当一个人被俩个人同时攻击时,这个人可以任意攻击一个人思路:分块思想,先把连续的朝向相同的人分成一块一块的。如: RLLLLRRLLRLR分成: R | LLLL | RR | LL | R | L | R每一块的长度为len,则每一块需要改动的次数则为:len/3但是首尾相同的时候,要合并为一块计算

2020-08-18 22:05:58

Codeforces Global Round 10 C. Omkar and Waterslide(思维)

题目传送题意:给你一个大小为n的数组,现在你可以进行操作,使得数组不递增。操作:你可以选择连续的子片段使得,他们的值加一,现在要求你求得最小的使用操作数,使得数组不递减思路:例:10 9 6 3 7 2 4 20我们先考虑这个例子,怎么使得其操作数最少呢?我们肯定是要把 9 6 3 7 2 4这一段变成10就是操作数最少的了再推:我们就要把6 3 7 2 4先变成 9再推:先把6 3 和 2 4变成 7再推:先把 3变成6,把2变成4这样的话我们就可以最大程度上的去利用连续的子段那么上

2020-08-17 11:03:10

Codeforces Global Round 10 B. Omkar and Infinity Clock(数学)

题目传送题意:给你一个大小为n的数组a,还有一个正整数k,问进行k次操作后,数组是什么样,一次操作:对于每一个位置i 用数组中的最大值-ai替换思路:现在的数组中肯定是有一个最大值的,那么在一次操作后,Max(最大值)的位置一定会变成0,然后又会形成一个新的最大值,此时数组中肯定有Max和0的存在,然后进行操作后,Max变成0,0变成Max,继续下去这就是一个循环。例:5 -1 4 2 0第一次变0 6 1 3 5第二次变6 0 5 3 1第三次变0 6 1 3 5…这就是一个循环AC

2020-08-17 10:53:10

Codeforces Global Round 10 A. Omkar and Password(思维)

题目传送题意:给你一个n大小的数组,你每次可以合并俩个不同的数,问最后你能把数组压缩到的最小长度是多少?思路:只有1和n的区别。什么时候为n呢?当所有数都是一样的时候,我们不能进行合并操作,如 5 5 5,那么长度一定只能是n什么时候为1呢?只要一个数组中有俩个数不同,那么一定可以合并到只有一个数,如何证明?证明:既然有不同的数,那么数组中肯定有一个最大值,和一个最小值,且最大值与最小值不等。那么我就先让目前的最大值和最小值合并,就会又形成一个最大值,那么这个最大值现在在数组中肯定是唯一

2020-08-17 10:37:21

2020牛客暑期多校训练营(第九场) E.Groundhog Chasing Death(数论,质因数分解,费马小定理)

题目传送借鉴大佬的博客思路:真的是搞人,一个bug能找俩小时把题意转化求这个等式,其中aa表示的是x中数值为p的质因子的个数,bb表示的是y中数值为p的质因子个数因为求他们的gcd就相当于求其质因数分解后的每个质因子的最小数目的乘积。然后再算每个质因子对答案的贡献。详细看大佬的博客叭,太详细了 Orz这里需要用到:a ^ b % p == a ^ (b%(p-1)) % pAC代码#include <bits/stdc++.h>inline long long read(

2020-08-11 23:35:08

尺取法基础介绍

尺取法模板题:给长度为n的数组和一个整数m,求总和不小于m的连续子序列的最小长度输入n = 10,m = 155 1 3 5 10 7 4 9 2 8输出2尺取法模拟过程:第一步 先找到第一个大于m的区间5 1 3 5 10 7 4 9 2 8第二步 删除第一个元素,再添加后面的元素,直到重新大于m5 1 3 5 10 7 4 9 2 8第三步 以下一直同第二步5 1 3 5 10 7 4 9 2 8第四步5 1 3 5 10 7 4 9 2 8第五步5 1 3 5 10

2020-08-10 20:54:28

2020牛客暑期多校训练营(第九场)

A.Groundhog and 2-Power Representationpy还是香,还得练练py代码的能力eval是可以直接把这个输入的字符串当初数值表达式计算,所以我们把所有的左括号改为 ’ **( ’ 即可,因为 **在py中是乘方的意思print(eval(input().replace('(', '**(')))F.Groundhog Looking Dowdy思路:把每一个数从小到大排序并标好其属于哪一天的。然后用尺取法来解决(不断更新最小值),时间复杂度O(n)AC代码#

2020-08-10 20:45:54

POJ - Permutations(群论,置换群)

题目传送很好的置换群的入门题,题目中已经把上面是置换群是什么讲得很清楚了每一个数都有一个循环节长度,所以要满足要求就求所以循环节的长度的lcm即可。这里要说的是:如果一个数已经出现过了(前面计算循环节的时候记录过),那么在后面遇到这个数的时候,这个数的循环节也和在记录另外一个数的循环节长度一样,所以可以不管(可以减少时间复杂度)AC代码#include <bits/stdc++.h>inline int read(){char c = getchar();int x = 0,s =

2020-08-08 23:10:09

Codeforces Round #662 (Div. 2) C. Pinkie Pie Eats Patty-cakes (思维,分块)

题目传送题意:给你n个数,问你相邻俩个相同的数的最大最小距离是多少思路:我为什么写了个分块在标题上面呢?例:有数 1 1 1 2 2 2 3 3 3 4 4 5 6那么我们是如何分呢?1.我的方法是先统计相同的数的最多出现的次数(Max),和拥有相同Max的数的个数(sum)。2.这里Max = 3,sum = 3,那么我们肯定要使得这些数尽量的错开,也就是1 2 3 1 2 3 1 2 3这种错开(我称为把1 2 3 作为一块)3.这样做可以使得相同的数距离的最远,那么我们发现还有4 4

2020-08-08 22:05:36

Codeforces Round #662 (Div. 2) A.Rainbow Dash, Fluttershy and Chess Coloring (思维)

题目传送思路:说实话想了挺久的。。。。答案为n/2 + 1那么我们来证明:首先:最开始,我们只能填最外围的一圈,而这最外围的一圈,无论n是多少,都要填俩次才能把最外围的填满,而在第二次的时候,我们不仅仅的填了最外围的一层,还往里面又填了一次,但是同理,这一次是填不完的,还需要再填一次,才能把这层填完,然后就依次下去,一层一层的填下去,就只有最外围的一层填了俩次,其他层都只用一次即可填满(而在最后一层,也就是只有一个方格的时候,这一次被上一层填满的时候就能填满了)而每一层之间的差距方格数差距为2,

2020-08-08 20:01:47

Codeforces Round #662 (Div. 2) B.Applejack and Storages(思维)

题目传送题意:给你,n块木板,再q次询问的情况下(询问时会添加或者减少木板),问在当前询问下是否能使用现有的木板构成一个正方形和一个矩形(也可以是正方形)?构成的时候,每一条边是只能用一块木板思路:千万不要读错了,每一条边的构成只能用一块木板的那么我们现在只用记录现在有多少组木板长度一样的(4个为一组记为ans1),在除去前面的一组的情况下,还有多少组长度为一样的(2个为一组,记为ans2)如果ans1 >= 2 (能构成俩个正方形) 或者 ans1 == 1 && ans

2020-08-08 19:50:39

2020牛客暑期多校训练营(第八场)G. Game SET(暴力就完事)

题目传送思路:恶心的暴力…不过多锻炼锻炼自己写代码的能力也还行AC代码#include <bits/stdc++.h>inline long long read(){char c = getchar();long long x = 0,s = 1;while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}while(c >= '0' && c <= '9') {x = x*10

2020-08-06 22:26:11

2020牛客暑期多校训练营(第八场)K.Kabaleo Lite(前缀和,高精)

题目传送题意:有n道菜,第i道菜有bi盘,每盘利润为ai(利润可能为负)。遵循以下规则为每个顾客上菜:● 每位顾客至少有一道菜。● 每位顾客都得到从1开始的连续编号的菜,每道菜只吃一盘。问能容纳的最大的顾客数,已经可赚取的最大利润。思路:首先,最多的人数肯定是第一道菜的人数。其次,要最大利益,那么我们前缀和,贪心先拿最大的利益,依次下去(我不知道暴力会不会t),但是这个东西爆了long long,只有用__int128过,但是奈何cb不支持这个东西,我又不会Dev,就只能用py了。。这里讲

2020-08-05 22:09:53

2020牛客暑期多校训练营(第八场) I.Interesting Computer Game(并查集求连通块以及判环)

题目传送题意:一个游戏有N个回合,每回合提供两个整数ai和bi,每回合只能选以下三个操作之一。不做任何操作。如果ai没被选过(指ai的数值),可以选择ai。如果bi没被选过,可以选择bi。先给出所有a1,a2,…,an与b1,b2,…,bn,求出选择的最多整数数量。思路:我们把每一回合的俩个数连成一条边,那么现在这些边与边互通,我们用并查集记录他现在的根,不断更新,然后求出来,最后有几个连通块,以及在这些连通块中,有几个是环,如果一个连通块是环,那么这里面的数全部都可以选(可以自己画画图来验

2020-08-04 22:25:00

查看更多

勋章 我的勋章
  • 签到王者
    签到王者
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。