- 博客(67)
- 收藏
- 关注
RSS订阅原创 关于逆元的一些知识
因为完全搞不懂逆元，所以在这里留一个MOD是质数时O(N)求逆元的板子inv[1]=1; for(int i=2; i<=n; i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
2020-10-26 18:01:28
121
原创 关于组合数的一些知识
昨晚的ATcoder D直接傻掉了，后来看了题解发现是在考察组合数相关知识，麻了，完全不知道这种知识的我只能傻眼，于是就悻悻的来补知识了。。。题目链接
2020-10-25 19:57:37
136
原创 学习笔记~优先队列~
总是记不住优先队列的结构体写法，这次就把它记下来//方法1struct tmp1 //运算符重载<{ int x; tmp1(int a) { x = a; } bool operator<(const tmp1& a) const { return x < a.x; //大顶堆 }};//方法2struct tmp2 //重写仿函数{ bool operator() (t
2020-10-06 18:30:35
133
2
原创 学习笔记~组合数~
之前一直不明白组合数怎么求出来的（指代码），今天顿悟了，写个blog记录一下#include<bits/stdc++.h>#define int long longusing namespace std;const int MOD = 1e9 + 7;int choose[3000][3050];signed main(){ for(int i = 0; i < 3000; i++) { choose[i][0] = choose[i][i]
2020-10-04 20:03:02
109
4
原创 NC13230 合并回文子串
NC13230很好的一道区间DP，写之前一直想的二维怎么写，实在是想不出来了，看了清楚姐姐的题解才知道，哦，是四维DP，DP这东西，真的很奇妙，想得到就是板子题，想不到能卡死人代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>using namespace std;const int N
2020-07-17 12:26:38
145
原创 NC50439 tokitsukaze and Soldier
NC50439思路：一道思维题，其实还是比较好想的，跟CF上某次的C题比较类似，先排个序，再用优先队列暴力一下，一次for循环就能完事儿代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long long#define pb push_back#define p
2020-07-17 09:17:46
107
原创 Nightmare Ⅱ HDU - 3085
HDU - 3085读题太难了，请看这位大神的翻译：大神的中文题意思路：这就是一道暴力BFS模拟啊！！最多再加点A*作为佐料暴力跑就完事儿，最多算一下在当前点会不会被鬼抓到作为剪枝在这里我安利一下一篇优秀的题解：大神的题解嗯？我为什么要在自己的题解里安利别人的题解？因为我的题解是给自个儿看的嗷代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")
2020-07-16 21:57:34
162
原创 DNA sequence HDU - 1560
HDU - 1560题意：给你N个DNA子序列，请求出包含这些子序列的最短DNA序列的长度思路：用IDA*暴力，用指针推进每一个子序列代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long long#define pb push_back#define
2020-07-16 12:36:23
154
原创 I - A计划 HDU - 2102
HDU - 2102思路：水题一个，暴力BFS就能过，注意判断魔法阵对面是否还是传送阵代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long long#define pb push_back#define pf push_frontusing namesp
2020-07-16 11:20:57
111
原创 HDU - 3567 Eight II（IDA*）
HDU - 3567题意：给两个九宫格，你只能让X和与X相邻的格子进行交换，请从状态a得到状态b，要求移动次数最少且答案的字典序最小思路：稍有难度的一道搜索，我们需要用到IDA* 算法（还有其他很多种方法，有兴趣的可以自行尝试，这里使用的是IDA* 进行解答）利用A* 算法来得到最小的移动次数的期望值，然后利用ID算法来进行迭代加深，如果了解 IDA* 算法的话，这道题就是一道板子题（注意：A* 算法得到的最小移动次数是小于等于实际次数的，不理解的话可以查阅一下关于A* 算法的资料）代码附：
2020-07-16 09:32:39
134
原创 1352D Alice, Bob and Candies (1300)
1352D Alice, Bob and Candies题意：N个糖果，每个价值a[i]，A从左吃，B从右吃，A先吃，每人每次吃的糖果总价值都必须比另一个人上一次吃的多，求两个人的总行动次数以及两人分别吃了多少思路：左右指针直接暴力跑一遍for循环，时间复杂度O(n)代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bi
2020-07-11 12:56:56
121
原创 1351C - Skier （1400）
1351C - Skier题意：NSWE代表上下左右4个方向，每次走一个单位，第一次走的路花费时间5，不是第一次走的路花费时间1，求最后所花时间思路：暴力嗷，假设是从原点开始走的，map记录一下就能随便写了代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int lon
2020-07-11 10:32:53
277
原创 1368C - Even Picture（1500）
1368C - Even Picture题意：在一个全是网格的图中，你可以选择一些格子涂灰，请你涂一些格子并且满足以下条件：所有格子必须是连通的对于每一个格子，都有偶数个格子与它相邻有恰好N个格子，它们的上下左右都有格子相邻思路：个人觉得下面这种图形是最完美的每个格子都是偶数个相邻，只要将这种图形的边角不断的重叠就能构造出我们需要的上下左右都相邻的格子一个又一个所以我们需要初始方块4个，和剩下N*3个格子用来构造每一个四边相邻的格子代码附：#pragma GCC optimi
2020-07-10 20:39:55
163
原创 1368D - AND, OR and square sum
1368D - AND, OR and square sum题意：给你N个数，你可以选择任意两个数 i，j ，使得原本a[i]=x,a[j]=y变为a[i]=x&y,a[j]=x|y;，可以做这种操作无数次，请使得这N个数的平方和最大思路：题上已经说得很清楚了，用二进制做，直接把每一个数的二进制位都扣下来，然后每次都去取这些二进制位来组成当前能组成的最大数来算平方和代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#prag
2020-07-10 15:48:02
128
原创 1367B - Even Array (800)
1367B - Even Array题意：通过交换数组中的任意位置的元素，能够使得数组的下标的奇偶校验与元素相同的最小操作次数是？思路：判断错误的奇数与偶数个数是否相同，相同直接输出，否则输出‘-1’代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long l
2020-07-10 15:03:51
187
原创 Codeforces Round #650 (Div. 3) A. Short Substrings (800)
A. Short Substrings题意：给你字符串B，请你猜出字符串A，字符串B=a[0]+a[1]+a[1]+a[2]+a[2]+a[3]+a[3]……+a[n]，其中a[0]和a[n]只出现一次思路：先输出a[0]，剩下的只输出下标为奇数的代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.
2020-07-10 13:13:02
106
1
原创 1369A - FashionabLee (800)
1369A - FashionabLee题意：给你一个N边形，判断他是否存在一条边平行X轴，一条边平行Y轴思路：直接判断N是不是4的倍数，这样上下左右的边才都是平行的代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing namespa
2020-07-10 11:21:04
260
原创 1369B - AccurateLee （1200）
1369B - AccurateLee题意：给一个01串，如果存在‘10’就可以消除其中的‘1’或‘0’任一个，请让该字符串最短并且字典序最小思路：贪心思想，从后往前找‘01’，用stack处理一下即可代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long
2020-07-10 11:15:35
153
原创 1369C - RationalLee (1400)
1369C - RationalLee题意：有N个物品，每个物品价值A[i] ，将这些物品分配给K个人，每个人要W[i]个物品，求每个人得到的物品价值的最大值和最小值之和的最大值思路：贪心思想，先让只要一个物品的人拿价值最大的东西，接着让剩下的人先从价值最大的物品开始每人取走一个，然后再让W小的人从剩下的物品中从最大价值的开始取代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2
2020-07-10 10:31:33
138
原创 Codeforces Round #652 (Div. 2) D. TediousLee （1900）
D. TediousLee题目大意：在树第N次成长后，最多能选出多少颗爪型树，求出这个值*4（点的数量）思路：经过几次推导，能够发现，会新长出来的点的数量a[i]=a[i-1]+2*a[i-2]，因为爪型树的根节点来自a[i-2]，左右两边的点来自a[i]，下面的点来自a[i-1]，能够看出，每当选出一层的根节点为a[i]爪型树，就不能再选根节点层数为a[i-1]和a[i-2]的爪型树，所以能推出递推式ans[i]=ans[i-1]+2*ans[i-2]+(i%3==0);该递推式的意思值的是从最
2020-07-10 09:52:43
96
原创 Codeforces Round #651 (Div. 2) A. Maximum GCD (800)
A. Maximum GCD题意：找到[1,n]中GCD最大的一对数的GCD思路：暴力秒A，直接输出N/2代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing namespace std;const int N = 2e5+10;
2020-07-10 06:09:26
77
原创 1370B - GCD Compression (1100)
1370B - GCD Compression题意：给一个大小为2N的数组A，请你从该数组从丢弃任意两个数，并将剩下（2N-2）个数两两相加，组成一个新的数组B，该数组B的所有元素的GCD>1思路：直接判断奇数奇偶性即可，丢弃两个数后使得奇数的个数为偶数，这样，奇数两两相加，偶数两两相加，GCD==2代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,m
2020-07-10 06:03:23
150
原创 1370C Number Game （1400）
1370C题意：A和F博弈，给一个数字N，可以做一下两种操作：if(N>1)N--;if(x%2==1 && N%x==0 && N>1 && x>1)N/=x;不能进行操作的人会输，A先手思路：可以看出来，如果N>1&&(N&1)或者N==2，A能赢；如果N是偶数，但是N除以它的最大的奇数（大于1）的值大于2的话，A能赢；其他情况F会赢代码附：#pragma GCC optimize("O
2020-07-09 20:45:40
97
原创 1370D - Odd-Even Subsequence（2000）
1370D - Odd-Even Subsequence题意：可以在长度为N的数组中任选K个元素组成一个新的数组，设这个新的数组中下标为奇数的元素中的最大值为K1，下标为偶数的元素中的最大值为K2，求MIN（K1,K2）思路：已知 1≤ai≤1e9，使用二分来寻找一个值X，这个X能够使得在选择了长度>=K的新数组后，在这个新数组中的下标为奇数（或者偶数）的所有元素的最大值<=X代码附：#pragma GCC optimize("Ofast","inline","-ffast-math
2020-07-09 20:01:37
110
原创 1370E Binary Subsequence Rotation （2100）
1370E题意：两个01串，s和t，你能将s的子串顺时针位移一下，请问最少要多少次操作能使得s==t思路：这就是一个思维题，想通了就很简单。不要管位置正确的那些字符，只把位置错误的单独拿出来看，就能发现如果是01010101……这种或者101010……这种就只用一次操作就能把位置修正，所以我们只需要找这样的串一共有多少个就行了代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,
2020-07-09 12:13:50
126
原创 Codeforces Global Round 9 D. Replace by MEX （1900）
D. Replace by MEX题意：存在一个数组A，令该数组中不存在的最小非负数为MEX，每次操作可以让任意a[i]=mex，请在2N的操作次数以内使得数组A非递减思路：让a[i]=i，每次操作完边界a[i]都让边界缩小，如果mex==n就放在a[n-1]代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/s
2020-07-09 09:33:02
107
原创 Codeforces Global Round 9 C. Element Extermination （1400）
C. Element Extermination题意：如果a[i]<a[i+1]，那么可以消除掉a[i]或a[i+1]中的任意一个，给你一个数组，问其最后能不能被消除到只剩一个元素思路：如果a[0]<a[n-1]，那该数组一定能被消除到只剩一个，这是为什么呢？因为大于a[0]的能被a[0]消除，小于a[n-1]能被a[n-1]消除，而且因为只有当a[i]<a[i+1]时，才能消除掉a[i]或a[i+1]中的任意一个，也就是说，左边界不可能比a[0]更小了，右边界也不能比a[n-1]
2020-07-09 09:26:36
163
原创 Codeforces Global Round 9 B. Neighbor Grid（1200）
B. Neighbor Grid题意：一个n×m大的网格里，每个网格里都有一个值，你可以使得任意网格里的数字加一，网格里的数字X代表这个网格附近恰好有X个网格里的值不为0的网格相邻（有相同边才相邻）思路：暴力暴力暴力，全部网格的值全部改为邻近网格数，如果有超过该值的网格存在就输出“NO”代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#inc
2020-07-09 08:43:18
116
原创 Codeforces Global Round 9 A. Sign Flipping（1100）
A. Sign Flipping题意：N 个数，可以随意改变他们的正负，请让n/2对ai+1−ai是非负数，n/2对ai+1−ai是非正数思路：直接暴力正负正负代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing namespace
2020-07-09 08:38:00
80
原创 POJ - 1733 Parity game （带权并查集+离散化）
POJ - 1733题意：有一个长度为N的序列，有M条讯息，会告诉你[a,b]的奇偶性，判断在讯息出现第一次冲突的信息前一共有多少条讯息是可信的思路：带权并查集的板子+离散化操作，又是一道暴力就完事儿的题代码附：#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<set>#include<map>using
2020-07-08 17:41:58
114
原创 [POJ-1984] Navigation Nightmare
[POJ-1984]题意：给出一张无向图，求两点的曼哈顿距离思路：暴力，直接暴力，说白了就是道题意麻烦点的带权并查集板子题代码附：#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 4e4+10;int n,m,q;int fa[N],rx[N],ry[N],ans[N>>2];struct node1{
2020-07-08 16:55:01
83
原创 POJ - 2912 Rochambeau （种类并查集+枚举）
Rochambeau题意：N个人玩剪刀石头布，每个人都只会出固定的一种，所以一共会有3种人，但是这群人里有一个人搞特殊，他能随便出，请找出他思路：枚举每一个人是特殊人的情况，如果排除这个假定的特殊人之后没人再乱出搞事情，那他就有可能是特殊人，把他保存下来。如果最后一个特殊人也没找到，说明有不止一个人在乱搞，输出"Impossible";如果最后找到好几个特殊人，说明没人在乱出搞事情，不确定谁是特殊人，输出"Can not determine";如果最后只找到一个特殊人，就说明真正的特殊人就是
2020-07-08 11:27:16
166
原创 HDU6186 CS Course
HDU6186思路：一开始很SB的一直在想位运算，后来看了一下别人怎么写的，才发现这就是个前缀和后缀和垃圾题P.S.卡多组输入代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing namespace std;const int N =
2020-07-07 11:08:49
106
原创 HDU6185 Covering(矩阵快速幂+数学)
HDU6185递推式思路：知道递推式之后，这就变成了一道矩阵快速幂的板子题，个人认为这道题难就难在一开始的打表推公式代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing namespace std;const int N = 2e5+
2020-07-06 21:22:00
129
原创 学习笔记~矩阵快速幂~
看了好几遍矩阵快速幂的相关入门资料，写的公式漫天飞的，眼睛都花了也没看懂，为了防止这种事再次发生，特把相关心得记下，下次方便查阅矩阵快速幂=快速幂+矩阵乘法矩阵快速幂就是把快速幂的函数内容换成3层循环的矩阵乘法就这样，完事留一个模板方便下次看#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#d
2020-07-06 19:41:57
116
1
原创 HDU6182 A Math Problem
HDU6182题意：问小于等于 n 的pow(i,i)一共有多少个思路：暴力打表代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing namespace std;const int N = 2e5+10;signed main()
2020-07-05 22:57:59
132
原创 HDU6188 Duizi and Shunzi
HDU6188题意：给你 n 张牌，问用这些牌能组成的对子和顺子的总和最大是多少思路：暴力求解，如果当前这张牌能组成顺子里最后那一张，那就组成顺子，然后剩下的牌全部组成对子代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing name
2020-07-05 22:43:50
99
原创 Codeforces Round #653 (Div. 3) E2 - Reading Books (hard version) (2500)
Reading Books (hard version)题意：有 n 本书，每本书有3个属性，int类型的 time，bool类型的a,bool类型的b,现在你需要选择 m 本书，并且满足 a 为 1 的书至少要有 k 本，b 为 1 的书至少要有 k 本，在这个前提下 val 的总和还需要最小思路：暴力模拟，先全选 a==1&&b==1的书，然后再按照 5 种方案加书用一本a==1&&b==0的书和一本a==0&&b==1的书与一本a==1&am
2020-07-03 00:20:23
223
原创 Codeforces Round #653 (Div. 3) F. Cyclic Shifts Sorting (2400)
F. Cyclic Shifts Sorting题意：给你一个长度为 n 的数组，你每一次操作只能选中3个连续的元素将他们右移，即：[ai,ai+1,ai+2] to [ai+2,ai,ai+1]，问能否在 n² 次操作内将该数组按从小到大排序思路：因为是个分值2400的题，一开始以为会很难想，但是看了一下tag，发现里面有 brute force，暴力就暴力，我最会暴力了。n这么小，那就搞双层循环，先是从后往前把小的值往前传，能跳两下就跳两下，不然就检查左右元素，看能不能朝前面至少跳一下没有小
2020-07-02 20:46:31
137
原创 Codeforces Round #654 (Div. 2) A—D 赛后记录
Codeforces Round #654 (Div. 2)A直接看样列输出，样列一看就是要输出(n+1)/2，我也不想想了，直接秒A代码附：#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<bits/stdc++.h>#define int long longusing namespace std;const int
2020-07-02 10:51:28
58
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人