- 博客(34)
- 收藏
- 关注
RSS订阅
原创 XOR运算
近来做了一些题目和异或运算有关的题目，总结一下Xor按位异或符号在编程语言中通常是 ^数学符号通常用⊕表示X = 0101BY = 1011BXYX⊕B101110000011X^Y = 1110B性质1. 0 ^ 0 = 02.a ^ a = 03.0 ^ 1 ^ 2 … ^ n的性质先观察一下如下的 序列我...
2020-01-12 11:00:31
2323
原创 HDU1024
HDU1024题意:把一个数组分成mmm段,然后使得sum(i1,j1)+sum(i2,j2)....+sum(im,jm)sum(i1,j1)+sum(i2,j2).... + sum(im,jm)sum(i1,j1)+sum(i2,j2)....+sum(im,jm) 每对(i,j)(i,j)(i,j)之间连续思路:dp[i][j]dp[i][j]dp[i][j]代表在选择第jjj个数字的时候,将前jjj个数字分成iii组的最大和情况这个时候dp[i][j]dp[i][j]dp[i][j]由两
2020-07-29 13:16:50
151
原创 Codeforces Round #654 (Div. 2)ABCD题解 E待补
Codeforces Round #654 (Div. 2)A. Magical Sticks题意重述:有nnn个木棍长度分别为1−n1-n1−n,每次操作可以合并两根木棍,得到的新木棍为原来两个木棍的长度求若干次变换后,最多数量的长度相同的木棍思路全部拼出长度为nnn的木棍,答案为⌊(n+1)/2⌋\lfloor (n+1)/2 \rfloor⌊(n+1)/2⌋#include <bits/stdc++.h>using namespace std;void
2020-07-04 10:41:09
276
原创 7月1日 Day1
7月2日中午补111 制定了最近的训练计划,大致方向222 7月1日晚KaTeX parse error: Expected 'EOF', got '#' at position 18: …deforces Round #̲654 (Div. 2)赛时过了四题, EF待补补题:
2020-07-02 12:10:32
126
原创 AtCoder Beginner Contest 158 E - Divisible Substring
Divisible Substring经过参考了各位大哥的代码和题解,我终于大概是了解了这题的思路题意:给定一个字符串,求字符串内任意连续子串组成的数字可以被ppp整除的个数思路:首先我们从字符串的地位进行考虑当p=2orp=5p = 2 or p=5p=2orp=5时,此时我们考虑有最后一位数字可以被整除的必定对答案有贡献所以我们把这种情况单独提出来其次我们考虑这样一个公式: 如果...
2020-06-03 23:58:03
596
原创 Codeforces Round #508 (Div. 2) B. Non-Coprime Partition
python写的这种构造方法真的好简单啊nnn 和 1...n−11...n-11...n−1这样它的和一定是gcd=ngcd = ngcd=nc++写的这种方法是把奇数和偶数分开,这样也一定可以得到答案,有待证明N = int(input())if N <=2: print("No")else: i = 1 sum = 0 while (i &...
2020-06-03 23:57:54
72
原创 Codeforces Round #508 (Div. 2) D. Slime
#include <bits/stdc++.h>using namespace std;const int N = 500010;typedef long long ll;ll ans = 0;int main(){ int n; cin >> n; if(n == 1) { int t;cin >>...
2020-06-03 23:57:30
113
原创 POJ 3268 Silver Cow Party(迪杰斯特拉最短路)
题意:一共NNN个节点,每个节点一头牛,现在每头牛都去XXX处聚会,图是有向图,所以每头牛去和回来的路程不一样,求NNN头牛中走的路程最远的一头的路程.思路:首先我们先跑正着从xxx点跑一次最短路,然后得到的是xxx到每个点的距离,这是每头牛从xxx回去的最短路程.然后就是神奇的一步:把图中所有有向边全部方向反过来,再从xxx跑一次最短路,这个时候得到的是每头牛来参加聚会的最短路程然后把答案一相加,去最大值即可.第一次暴力搜nnn个点的居然也过了//正向求解#include <io.
2020-05-11 23:47:40
120
原创 Codeforces Round #635 (Div. 2) C. Linova and Kingdom
思路:共nnn个城市,要求kkk个industry城市,n−kn-kn−k个tourism城市.容易证明tourism城市的父节点也一定是tourism然后这样只需要统计每个点的贡献值: det[e]=d[e]−Size[e]det[e] = d[e] - Size[e]det[e]=d[e]−Size[e]容易证明这个点的贡献值: 当前点的深度减去子节点个数然后对于每个点都进行统计....
2020-04-20 11:33:57
160
原创 CodeForces 1223 C Save the Nature(二分)
传送门->SaveTheNature自己写的代码实在过于啰嗦,和大佬学习了他的写法这道题先对ppp数组排序然后每次在nnn个数中二分一个midmidmid,然后checkcheckcheck当前的midmidmid看是不是符合ans≥kans \ge kans≥k的条件#include <bits/stdc++.h>typedef long long ll;cons...
2020-04-14 19:57:41
256
原创 Codeforces Round #367 (Div. 2) C Hard problem(dp)
首先看到这道题的时候,我是没有反应过来是dp问题的.但是略微思考一下就发现这题是个dp问题,因为每次选择是否翻转是有两种决策的.然后我们就很容易可以推出递推公式,详见代码.不过我觉得我写的代码略为繁琐.特别要注意≥\geq≥号~因为两个字符串是相等的时候是不影响顺序的,不然容易wa8#include <bits/stdc++.h>using namespace std;t...
2020-04-04 20:48:47
96
原创 实数三分
#include <bits/stdc++.h> using namespace std;const int N = 1e3 + 10; int a[N];int n;int ts(int x){ int l = 0,r = n - 1; while(l <= r) { int L = (r - l) / 3 + l,...
2020-03-26 10:38:08
181
原创 Codeforces Round #628 (Div. 2) D Ehab the Xorcist
传送门首先我们先来谈谈一会异或xorxorxor今天又学习到了一个新的知识a⨁b=a+b−2(a&b)a \bigoplus b=a+b-2(a\&b)a⨁b=a+b−2(a&b) 以及异或和 <= 总和下面来说说题意：给定两个数字uuu,vvv.构造几个数，使他们的异或和为u，和为v如果只有一个构造的序列只有一个数字，那么自然满足，这个时候u==vu==...
2020-03-24 00:20:09
111
原创 二分图判定(染色法模板)
给定一个n个点m条边的无向图，图中可能存在重边和自环。请你判断这个图是否是二分图。这道题是模板啦,并且还有一个性质:** 当且仅当图中不含奇数环时它是二分图. **这个时候染色原理就可以解决这个问题O(m+n)O(m+n)O(m+n)的时间复杂度这里我们用dfsdfsdfs进行染色#include <bits/stdc++.h>using namespace std;c...
2020-03-12 23:42:38
416
原创 Codeforces Round #597 (Div. 2)D: Shichikuji and Power Grid
传送门题意:有nnn个城市,为了使每个城市都有电力供应,你可以选择在任意一个城市建立PowerStationPowerStationPowerStation,或者用线缆将他们连起来,这两个操作都有costcostcost.现在要求你找出一个方法使costcostcost最小,并将电力覆盖所有城市思路:建立一个超级源点,从该原点向每个可建站的位置加入1条边,权值为c[i]c[i]c[i]然...
2020-03-10 17:38:51
73
原创 Codeforces Round #626 (Div. 2) B Count Subrectangles
传送门思路:每一段全为一出现的时候,每个比这一段长度小的长或者宽都会受到这段长度的贡献,然后相乘即可#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 4e4 + 10;vector<ll> count(vector<int> a){ ...
2020-03-09 19:02:16
145
原创 Ozon Tech Challenge 2020 (Div.1 + Div.2) C - Kuroni and Impossible Calculation (鸽巢原理)
传送门->Kuroni and Impossible Calculation题意:nnn个数a1,a2,...,ana_1 ,a_2,...,a_na1,a2,...,an,求∏1≤i<j≤n∣ai−aj∣\prod_{1\le i<j\le n} |a_i - a_j|∏1≤i<j≤n∣ai−aj∣ %mmm2≤n≤2⋅105,1≤m≤10002\le ...
2020-03-05 21:30:48
170
原创 AtCoder Beginner Contest 157 E - Simple String Queries
Simple String Queries题意:一个字符串,给定Q次查询,查询种类两种1 修改某个位置的字符改成另外一个2 是统计l-r区间内不同字符的个数思路:1.26个set维护每个字符出现的位置具体地来说,先将字符串遍历一遍,把每个字符出现的位置全都标记在相应的setsetset中.对于修改操作,我们将这个位置在原字符的setsetset中eraseeraseerase,然后...
2020-03-03 22:19:43
205
原创 AtCoder Beginner Contest 156 E-Roaming
E - Roming解法:我们假定有iii个房间空着，那么这iii个房间对于答案的贡献是CniC_n^iCni，剩下的n−1n-1n−1个房间中有nnn个人，这样我们使用插空法，组合数是Cn−1n−i−1C_{n-1}^{n - i - 1}Cn−1n−i−1而iii可以取到min(k,n−1)min(k,n-1)min(k,n−1)故答案是∑i=0min(k,n−1)(Cni∗Cn−...
2020-02-26 19:37:57
142
原创 AtCoder Beginner Contest 156 DBouquet (Lucas定理)
传送门->Bouquet题意给定n种鲜花，你可以选择其中>=1种花，组成不同的花束，但是不能组成数量为a或数量为b的花束。请问有多少种组成花束的方式解法：这道题的数据范围很大，所以我们使用LucasLucasLucas定理解决这个问题.nnn个元素的集合,有2n−12^n-12n−1个非空子集,然后还需要减去C(a,n)C(a,n)C(a,n)和C(b,n)C(b,n)C(b...
2020-02-26 10:48:30
207
原创 关押罪犯(种类并查集)
关押罪犯//洛谷P1525关押罪犯#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int p[N << 1];struct M{ int a,b,c; bool operator < (const M & T)const { ...
2020-02-23 12:29:01
254
原创 食物链(带权并查集)
食物链并查集维护的每个点到根节点的距离余1表示可以吃掉根节点余2表示可以被根节点吃掉余0表示与根节点同类//食物链(带权并查集)#include <bits/stdc++.h>using namespace std;const int N = 50010;int n,m;int p[N],d[N];int find(int x){ if(p[x] !...
2020-02-23 11:03:52
142
原创 求逆序对个数(归并排序)
逆序对#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 5e5 + 10;int a[N],t[N];inline int read() { static char c= getchar(); int x=0,f=1; for(;c>'9'||c<...
2020-02-20 21:54:23
275
1
原创 算概率
算概率简述题意:牛牛一共做了n道题,他不知道自己到底做对几道题,然而他知道这n道题的正确率分别为p1,p2,p3…pn.求他做对k道题0 <= k <= n的概率输出一行n+1个数表示做对0题,做对1题…做对n题的概率解题思路依旧是dp我们设一个数组为dp[i][j],代表的含义是在前i题中做对j题状态转移方程是dp[i][j]=dp[i][j−1]∗p[i]+(1+...
2020-02-06 22:30:32
151
原创 nico和niconiconi
链接：https://ac.nowcoder.com/acm/contest/3002/Inico平时最喜欢说的口头禅是niconiconi~。有一天nico在逛著名弹幕网站"niconico"的时候惊异的发现，n站上居然有很多她的鬼畜视频。其中有一个名为《让nico为你洗脑》的视频吸引了她的注意。她点进去一看，就被洗脑了:“niconicoh0niconico*^vvniconicoG(v...
2020-02-05 21:30:24
611
原创 均分纸牌(贪心)
均分纸牌题目:有N堆纸牌，编号分别为 1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N−1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。题解对于每第一堆来说如果第一...
2020-02-02 21:05:18
346
原创 楼兰图腾(树状数组)
在完成了分配任务之后，西部314来到了楼兰古城的西部。相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。西部314认为这幅壁画所包含的信息与这N个点的相对位置有关，...
2020-01-30 21:03:11
299
原创 AtCoder Beginner Contest 153 E - Crested Ibis vs Monster
Crested Ibis vs Monster做法使用一个dp[i]代表从0到i所需要最少的cost dp[target] = min(dp[target],dp[j] + b[i]);解法如下#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int&...
2020-01-28 17:52:08
276
原创 高精度
今天在CF vp了一场区域赛,然后第一题的高精度着实让人头痛.然后借此机会学习了一下如何处理高精度问题.传送门------EasyMath当然,不出意外地,我放弃了C++来写这个题目,转而决定使用Java 和Python来解决这个问题.Java的BigDecimal,高精度浮点数类Python的Decimal高精度浮点数类都为这个问题提供了很大的帮助Java为了防止高精度类型的精度...
2020-01-08 19:39:39
198
原创 BinarySearch(二分)
(Binary Search)众所周知，二分法是著名的古希腊数学家芝诺，提出来的二分法悖论，虽然在哲学上是个悖论，但是在当今的计算机科学领域确是非常有效的算法。平日里水群看到各位大佬的解法，感叹道：万物皆可二分！Emmm，下面进入正题。二分搜索，只要一个满足某种性质的序列，可以已某个标准分为两半，那么我们就可以使用二分法来寻找某个具体的条件是否在这个序列中。但是在ACM中使用最多的就是，一...
2019-11-16 16:29:31
152
原创 差分+ICPC2019上海网络赛B题Light Bulbs
差分简单地来说，差分就是前缀和的逆运算。例如 一维差分下面上acwing上的一道模板题: 差分模板每次修改数组内一个区间的每个元素的值加上C，a[N] b[N] ，对a[L]到a[R]内所有值加C这个时候如果遍历一遍则需要O(n)的复杂度了，使用差分则只需O(1)的复杂度。关于如何建立差分数组首先我们可以假设a,b两个数组所有元素全部为0，每次给a中元素赋值的时候就可以认为...
2019-09-20 18:39:04
302
原创 ios::sync_with_stdio(false);
ios::sync_with_stdio(false);今天看了许多博客,很多博主都是被cin卡过时间的人,血的教训告诉我们使用这一行神奇的代码可以获得新世界!有博主测试大概是取消同步之后就cin 和scanf的效率差不多了 ios::sync_with_stdio(false);...
2019-08-16 09:22:41
116
原创 C++STL中的next_premutation
Next_premutation今天写到一个全排列的问题,发现题解中有dalao提到了C++的STL库中有next_premutation这个优秀的全排列函数,在CSDN上找了找了,找到许多优秀的blog,先将其汇集起来以备不时之需.用法总结】C++ STL中 next_permutation函数的用法C++的官方解释具体用法...
2019-08-13 16:03:26
584
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人