2 QQQQQQQ_479

尚未进行身份认证

我要认证

acm底层选手

等级
TA的排名 7w+

Codeforces Round #641 (Div. 2) C. Orac and LCM

题意:给了n个数,让球gcd{ lcm{a[i],a[j]} } (i<j)就是n个数,两两配对求出他们的lcm,对于所有lcm在求出gcd思路:考虑一下gcd和lcm在算术基本定理下的含义。那么容易知道那么对于两两组合求lcm,我们容易知道取的质因数是最大的那个,然后整体求gcd质因数取的是最小的。那么考虑一下。如果对于n个数而言,有n-1个数都含有质因数x,那么最后的所求答案的gcd一定有质因数x,为什么?因为只存在一个数字没有质因子x,那么因为lcm是取最大的,

2020-05-12 23:07:11

Codeforces Round #639 (Div. 2) C. Hilbert's Hotel

C. Hilbert’s Hotel题意:有n个数,现在要求把每个数移动到(a[i]+i)%n的位置,看是不是每个位置都只有一个数。思路:直接暴力每个数改变后的位置塞进map里,看是不是存在某个位置的个数≥2即可。#include<bits/stdc++.h>using namespace std;int main(){ int t;cin>>t; ...

2020-05-07 12:39:16

Codeforces Round #629 (Div. 3) D. Carousel

D. Carousel题意:n个数字围成一个环,现在要求对n个数进行染色。染色要求是,对于相邻的两个数,如果不同的话,要求颜色也要不一样。那么如果相邻两个数相同,颜色可以不同,也可以相同。思路:一、如果所有数字都一样的话,只需要染上同一种颜色即可。二、如果数字的个数有偶数个,那么只需要两种颜色,按照1 2 1 2…1 2 1 2这样染色即可。三、如果数字的个数有奇数个,去看遍历一下这...

2020-05-06 20:21:27

D. Phoenix and Science

D. Phoenix and Science题意:刚开始有一个细菌质量是1,然后从第一天开始,白天你可以选择让任意个细菌分裂,质量为m的细菌可以分裂为两个质量为m / 2的细菌,到了每天晚上每个细菌的质量都会加1,问最少要多少天,细菌的质量总和恰好可以达到n,输出每天分裂的细菌的个数。思路:这是一个构造题。构造的方法应该挺多的。考虑一下,对于细菌分裂而言,只是个数增加了,总质量是不变的,...

2020-05-02 19:44:05

C. Phoenix and Distribution

Phoenix and Distribution题意:给了一个长度为n的字符串,让你将字符串分成k个字符串,这k个字符串不能存在空串,现在想要知道,这k个字符串中 字典序最大的最小的字符串是什么。思路:第一步肯定是对字符串排序。考虑一下,如果前k小的字符不全一样的话,那么肯定是已经有了大小结果。就是第k个字符单独成串这样满足字典序最大的字符串最小。为什么?因为第一个字符久已经可以判断大小...

2020-05-02 15:52:25

C. Yet Another Counting Problem

Yet Another Counting Problem题意很简单,求l到r之间有多少个数x满足 (x%a)%x!=(x%b)%aa和b的范围很小,很容易想到从a、b下手。考虑一下如果x=lcm(a,b) 那么一定满足(x%a)%x==(x%b)%a结果肯定是以周期性呈现出来的其实每lcm(a,b)个就是一个周期所以对于每组数据,预处理出来他一个周期内的答案,对于l到r之间可以计算出...

2020-04-28 14:49:40

C. Linova and Kingdom

n个点的树型结构,选择k个工业城市,其他都是旅游城市,问所有工业城市到1节点的幸福值总和最大多少。幸福值为经过的旅游城市的个数。优先的想法肯定是深度越大越好。但是考虑一下,对于一棵树的内部节点而言,一定要经过根u,如果根被选为工业城市,那么增加的幸福值就是dep[u]-siz[u]什么意思呢?就是如果选了这个节点为工业城市,那么子树内部的工业城市的幸福值都要减少1,之所以减去的是树的大小,...

2020-04-16 14:34:02

Codeforces Round #635 (Div. 2)D. Xenia and Colorful Gems

考虑二分。枚举每个数组为x,然后去二分出来y的值,在二分第三个数组为z的值取最小即可。注意一下这里的二分,我们要二分出来第一个≥x的数为y,在二分出来第一个≥y的数为z这样不一定最优,还要考虑比他小的第一个。假设y的位置为pos z的位置为pos1那么组合的就是 b[pos] c[pos1] b[pos] c[pos1-1]然后改变pos为pos-1 则需要重新二分pos1的位置即...

2020-04-16 14:10:39

Codeforces Round #634 (Div. 3) D - Anti-Sudoku

考虑到数独本身的独特性。即每行、每列、每个3 * 3块内的数字都是不重复的现在让改至少有一个重复,最多改九次。那我们直接考虑把每行的制定一个数改为另一个数即可比如把每行的1都换成2#include<bits/stdc++.h>using namespace std;typedef long long ll;char a[10][10];int main(){ i...

2020-04-14 12:56:44

2019上海ICPC K.Color Graph

K.Color Graph题意:给了n个点和m条无向边,让你删掉一些边,让剩余的边不存在自环和奇数环,求剩余的边的最大值。思路:这个考了一个二分图的性质,很遗憾当然确实不知道这个。就是说 如果一个图不存在奇数环,那么一定是一个二分图那么问题就转化为,选择尽可能多的边使得该图是二分图那么我们对这n个点,用一个二进制串表示二分图的两个部分,第i位二进制位为1,说明在左半部。对于二进制为1...

2020-04-12 13:54:18

2019上海ICPC E.Cave Escape

E.Cave Escape比赛时候过的人很少,感觉应该是都被卡题了没有读这个题,或者榜歪了?题意:就是说给了一个n * m的矩阵,对于位置(i,j)的能量为x_(i-1)*m+j起点在(ex,ey) 终点在(sx,sy) 当你从一个位置第一次走到另一个位置的时候,获得的值就是这两个格子能量相乘,每个点可以多次到达,不限制走的步数,就是说你可以随便走,但获得的值只能是第一次走到才有效计算。...

2020-04-12 13:39:13

牛客 数码

数码给定两个整数 l 和 r ,对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ,把 x 的所有约数全部写下来。对于每个写下来的数,只保留最高位的那个数码。求1~9每个数码出现的次数。思路:求l到r的个数 转换为求1到r的个数 减去 1到l-1的个数可以看到 l和r的长度长达1e9 如果暴力算每个的话 光是枚举x就要1e9可能会想到枚举约数,但是这样也还不够,复杂度还...

2020-04-03 12:35:26

Codeforces Round #630 (Div. 2) D. Walk on Matrix

思路:其实就是一个构造题我们考虑位运算&的性质 二进制位上一样 才能有贡献所以我们可以这样构造q+k q 0k q+k k这样构造的话 题中的图的伪代码的值跑出来就是(q+k)&(q)&(q+k)&(k)=0那么按照我们选择的话就i是 (q+k)&(k)&(q+k)&(k)=k这样就满足要求了其中q为大...

2020-04-01 00:17:07

poj 3190 优先队列

poj3190思路:因为问是最少要多少个地方才能安排好所有牛,所以对于牛按照开始时间升序 开始时间一样按结束时间升序我们考虑把每头牛丢进去,下一头牛进去的话 把第二头牛的开始时间与已经进去的牛的最早结束的时间比较,如果结束时间>最早结束的时间 那么就是一头牛代替另一头牛进去,那么自然所需要的个数就不变,如果结束时间≤最早结束的时间,那么我们需要新开辟一个地方,让这头牛进去。综上所述 我们是...

2020-03-31 14:52:41

poj 2823 滑动窗口 单调队列

poj2823思路:最暴力的做法就是模拟过程,枚举每一个长度为k的区间,然后遍历一遍找最值,复杂度为n^2这题n的范围到了1e6 n^2 在规定时间内是跑不完的 所以这题要用数据结构优化什么样的数据结构呢 对于当前区间为l到r那么往后移动了之后 区间变为了 l+1 到 r+1也就是a[l]被弹出 a[r+1]加入所以我们考虑一个双端队列(双端队列与队列的区别在于 队列是一边只能进 另...

2020-03-30 18:37:42

poj 2479/2593 两个不相交区间的最大子段和 dp

24792593这两题所要求的是一样 只是输入不太一样而已思路:其实这题算是求一个序列的最大子段和的一个拓展延伸对于最大子段和 我们知道dp[i]=max(dp[i-1]+a[i],a[i]) 表示以i结尾的最大子段和那么这题所要求的是要两个不相交的所以我们考虑 开两个数组l,r 分别维护正序和倒序的最大子段和处理完之后,注意我们要的是不相交即可 ,也就是第一个区间的右端点和第二个...

2020-03-27 14:22:45

Rabbit的工作(1)

https://ac.nowcoder.com/acm/problem/21675思路:对于是0的位置直接选择休息,对于是1的位置要么工作,要么休息,二选一的问题,有点像01背包的选或者不选的问题,所以考虑效仿01背包。答案是要求最多共工作了几天,那么开一个维度表示共工作了几天,因为此题跟连续工作的天数有关,所以我们需要加一个维度表示目前为止连续工作的天数。那么也就是三个维度 dp[i][j...

2020-03-25 17:30:02

Educational Codeforces Round 84 (Rated for Div. 2) C. Game with Chips

https://codeforces.ml/contest/1327/problem/C题意:给了个n*m的网格,k个已知点,和k个要到的点,每次可以选择方向让所有点一起动,每个点可以到的次数不限制,最多走不超过2mn步,现在求一种走法让所有要到的点至少做过一次思路:第一眼是想要bfs的,然后公共说是不必要求步数最少 那就是个构造题了我们先考虑极端,就是把一个已知点当成在(1,1)这个位置,...

2020-03-24 01:03:48

牛客小白月赛23 B.阶乘

https://ac.nowcoder.com/acm/contest/4784/B思路:其实就是把p质因数分解,然后对于每一个质因数x,去二分出来最小的一个n!含有x的个数大于等于p中的x的个数 对于每个二分的结果取最大值#include<bits/stdc++.h>using namespace std;typedef long long ll;#define me(a...

2020-03-22 13:32:19

2019上海ICPC B.Prefix Code

https://ac.nowcoder.com/acm/contest/4370/B签到题吧 时限给的足足有5s 所以可以直接用stl里的unordered_map把每个字符串的前缀塞进去,最后遍历一下看是不是有某个字符串塞进去了两次即可复杂度 t * n * len *log如果时限给的比较紧,字典树即可 复杂度t * n * max(log,len)#include<bits...

2020-03-20 15:51:07

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。