Gurenge

题解

ATCoder(1)

/ 注册

全部文章 / 题解（共7篇）

起床困难综合症（位运算）

前言太菜了，参考了大佬的思路。题意给定一些位运算操作，对于[0,m]中的整数，求经过运算后的最大值。解题思路先考虑暴力怎么做，对于[0,m]中的每一个数，分别计算他们经过运算后的值，取最大值。复杂度O(mn),显然会超时。发现按位与，按位或，异或这种位运算，对于一个二进制位，只会影响...

2021-05-13

0 601

Lost Cows（模拟）

题意有n（2<=n<=8000)只奶牛，每只奶牛都有一个1到n的编号；站成一排，对于第i只奶牛，给出在它之前且编号小于它的奶牛的数量，求这一排每只奶牛的编号。（由于第一只奶牛前面一定没有奶牛，故输入仅给出n-1个数）解题思路看到dalao们在用主席树，二分+树状数组，我只能说...

2021-03-27

2 867

CCA的搬运

题目描述解题思路每次操作需要将一个球拿出来然后放在最上面，观察一下，我们发现按照题目中给出的顺序排列即消耗体力最少，因为若在第一次操作的小球上面还有球，则在移动第一次操作的小球时，就会另加上最上面的小球的重量，同理在给出的序列的其他地方插入小球，也会使消耗体力增加。顺序有了，模拟一...

2021-03-19

0 641

IOI周赛23D 小L的数列（dp优化）

前言比赛的时候只得了80分，想不出怎么优化，看了榜1大佬的思路明白了一些东西，才有了这篇题解(⊙﹏⊙) 题目描述解题思路 1.容易看出，我们可以将数组排序后，进行dp，假设当前位置是第i个数，可以枚举前i-1个数，取与i的最大公约数大于1的数j，则f[i]=max(f[i],f[j]+1)....

2021-03-06

3 696

一群小青蛙呱蹦呱蹦呱数论

解题思路 1.只有有两个及以上不同质因子的数才会有贡献2.对于最小公倍数，若将每个数质因数分解，最小公倍数即为每一个质因子的最高幂次相乘，可用线性筛筛取素数3.如何确定每一个质因子的最高幂次，因为该数要有两个及以上不同质因子，可将其乘以除他之外最小的素数确定，如：确定2的最高幂次可乘以3，最高幂次为...

2021-02-22

0 700

【每日一题】6月23日Forsaken喜欢数论线性筛

解题思路求每一个数的最小质因子，想到了雨巨讲的线性筛。借这个题存一下线性筛模板 int v[maxn]; //存放每个数的最小质因子 int prime[maxn]; //存放素数 int cnt; //素数个数 for(int i=2;i<=n;i++){ if(v[i...

2021-02-22

0 683

珂朵莉的数列

题意珂朵莉给了你一个序列，求出每个子区间的逆序对个数，然后加起来输出对于100%的数据，n <=1000000 ,0 <= 序列中每个数 <= 1000000000 解题思路树状数组+离散化先考虑简单的问题，如果是单独求逆序对，即离散化之后，边往树状数组中插元素边统计逆序对该题...

2021-02-13

1 1011