- 博客(136)
- 收藏
- 关注
RSS订阅原创 仓库选址（绝对值贪心）
链接分析：若n为奇数，则仓库建在中的商店；若n为偶数，则仓库建在任意中间两个商店#include<bits/stdc++.h>#define ll long longusing namespace std;const int N = 1e5+10;const int M=15100;const ll mod=998244353;int a[N];int main(){ int n; cin>>n; for(int i=0;i<n;i++) cin>
2021-10-12 15:41:16
323
原创 区间贪心问题
1.区间选点2.最大不相交区间数量3.区间分组4.区间覆盖1.区间选点链接分析：先根据左右端点排序，再找到当前最优方案，就是选择右端点上的点作为当前区间的点（1）根据左端点从小到大排序，令第一个选择的点是第一个区间的右端点，如果下一个区间的左端点小于当前点，则更新当前点为下一个区间的右端点和当前点的最小值。否则需要增加点，且这个点的坐标为下一个区间的右端点。#include<bits/stdc++.h>#define ll long longusing namespace std.
2021-10-06 21:15:52
181
原创 整数二分、浮点数二分、三分
目录1.介绍模板2.例题（1）数的范围（整数二分）（2）数的三次方根（浮点数二分）1.介绍模板模板int bsearch_1(int l,int r){ while(l<r) { int mid=l+r+1>>1; //+1 防止死循环 if(chekc(mid)) l=mid; else r=mid-1; } return l;} 模板int bsearch_2(int l,int r){ while(l<r) { int
2021-08-06 13:27:07
167
原创 归并排序（求逆序对）
归并排序/*给定你一个长度为 n 的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。*/#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5+10;int q[N],tmp[N];void merge_sort(int q[],int l,int r){ if(l>=r) return ; int mid=l+r&
2021-08-06 12:15:26
291
原创 快速排序、第k个数
快速排序模板（O（nlogn））/*给定你一个长度为 n 的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。*/#include<bits/stdc++.h>using namespace std;const int N = 100010;int q[N];void quick_sort(int q[],int l,int r){ if(l>=r) return ; int x=q[l+r>>1],i=l-1,j=
2021-08-02 23:25:22
258
原创 博弈论题目
题目1.Nim游戏1.Nim游戏题目链接给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。输入格式第一行包含整数 n。第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。输出格式如果先手方必胜，则输出 Yes。否则，输出 No。数据范围1≤n≤105,1≤每堆石子数≤109输入样例：22 3输出样例：Yes分析：将所有的数异或，
2021-08-02 11:06:30
127
原创 容斥原理题目
题目1.AcWing 890. 能被整除的数1.AcWing 890. 能被整除的数题目链接给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。输入格式第一行包含整数 n 和 m。第二行包含 m 个质数。输出格式输出一个整数，表示满足条件的整数的个数。数据范围1≤m≤16,1≤n,pi≤109输入样例：10 22 3输出样例：7分析：运用容氏原理，加上能被1个质数整除的个数，减去能
2021-08-02 10:40:41
229
原创 卡特兰数例题
例题1.满足条件的01序列1.满足条件的01序列给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。输出的答案对 109+7 取模。输入格式共一行，包含整数 n。输出格式共一行，包含一个整数，表示答案。数据范围1≤n≤105输入样例：3输出样例：5答案 = C2nnn+1\frac{C_{2n}^n}{n+1}n+1C2nn因为1e9+7是质数，所以可
2021-07-31 21:48:17
204
原创 组合数的不同求法
（1）CabC_a^bCab = Ca−1bC_{a-1}^bCa−1b+Ca−1b−1C_{a-1}^{b-1}Ca−1b−1适合a和b数值不大的时候void init(){ for(int i=0;i<N;i++) for(int j=0;j<=i;j++) if(!j) c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}（2）CabC_a^bCab=a!b!(a−b)!\frac{a!}{b!(a
2021-07-30 21:51:16
98
原创 高精度运算
加法和减法#include<bits/stdc++.h>using namespace std;const int N = 1e6+10;// 判断是否有 A >= B bool cmp(vector<int> A,vector<int> B){ if(A.size()!=B.size()) return A.size()>B.size(); for(int i=A.size()-1;i>=0;i--) if(A[i]!=B[i])
2021-07-30 16:21:08
64
原创 （异或）高斯消元
普通高斯消元#include<bits/stdc++.h>using namespace std;const int N = 110;const double eps=1e-6;int n;double a[N][N];int guass(){ int c,r; for(c=0,r=0;c<n;c++) { int t=r; for(int i=r;i<n;i++)//找到r-n行中第c列绝对值最大的行 if(fabs(a[i][c])>fa
2021-07-30 13:00:39
193
原创 扩展欧几里得算法
（1）扩展欧几里得算法裴蜀定理：对于任意正整数a，b，一定存在非零整数x，y，使得ax+by=gcd（a，b）/*给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai ×xi + bi ×yi = gcd(ai,bi)。*/#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;int exgcd(int a,int b,int &x,int &y){ if(!
2021-07-28 12:02:17
92
原创 快速幂（快速幂、快速幂求逆元）
（1）快速幂/*给定 n 组 ai,bi,pi，对于每组数据，求出 ai^bi % pi 的值。*/#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;typedef long long ll;typedef unsigned long long ull;int qmi(int a,int b,int p){ int ans=1; while(b) { if(b&1) ans=(ll
2021-07-27 21:31:10
126
原创 欧拉函数（1-N中与N互质的个数）
欧拉函数（1-N中与N互质的数的个数，记为φ（n））（1）N=p1^a1 * p2^a2 * … pk^ak(pi为N的质因子，ai为指数)，公式：φ（n）= N * （1-1/p1） * (1-1/p2) * . …*(1-1/pk)/*给定 n 个正整数 ai，请你求出每个数的欧拉函数。*/#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;typedef long long ll;type
2021-07-27 20:27:31
754
原创 质数（判断，质因数，筛质数）
质数：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。（1）质数的判定——试除法 O（sqrt（n））bool is_prime(int n) //质数判定 { if(n<2) return false; for(int i=2;i<=n/i;i++) { if(n%i==0) return false; } return true;}（2）分解质因数——试除法 O（sqrt（n））void divide(int x) /
2021-07-23 14:33:23
91
原创 Feel Good(悬线法)
链接Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicatedto studying how good or bad days influent people’s memories about some period of life.A new idea Bill has recently developed assigns a non-negative
2021-07-21 14:44:55
71
原创 SP1805 HISTOGRA - Largest Rectangle in a Histogram（悬线法）
链接题目描述A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with t
2021-07-21 14:06:26
115
原创 送外卖2（Floyd+三进制状压dp）
题目链接链接：https://ac.nowcoder.com/acm/problem/13252来源：牛客网题目描述美团外卖日订单数已经超过1200万，实时调度系统是背后的重要技术支撑，其中涉及很多复杂的算法。下面的题目是某类场景的抽象。一张 nn 个点 mm 条有向边的图上，有 qq 个配送需求，需求的描述形式为( s_i , t_i , l_i , r_isi ,ti ,li ,ri )，即需要从点 s_isi 送到 t_iti ， 在时刻 l_
2021-06-09 10:53:23
267
原创 D. MEX Tree
题目链接outputstandard outputYou are given a tree with n nodes, numerated from 0 to n−1. For each k between 0 and n, inclusive, you have to count the number of unordered pairs (u,v), u≠v, such that the MEX of all the node labels in the shortest path from u t
2021-05-25 19:26:10
215
原创 C. Sequence Pair Weight
题目链接The weight of a sequence is defined as the number of unordered pairs of indexes (i,j) (here i<j) with same value (ai=aj). For example, the weight of sequence a=[1,1,2,2,1] is 4. The set of unordered pairs of indexes with same value are (1,2), (1,5)
2021-05-22 23:51:59
374
原创 B1. Palindrome Game (easy version and hard version)
B1. Palindrome Game (easy version)题目链接The only difference between the easy and hard versions is that the given string s in the easy version is initially a palindrome, this condition is not always true for the hard version.A palindrome is a string that r
2021-05-21 14:43:29
391
2
原创 A. And Then There Were K（思维）
题目链接Given an integer n, find the maximum value of integer k such that the following condition holds:n & (n−1) & (n−2) & (n−3) & … (k) = 0where & denotes the bitwise AND operation.InputThe first line contains a single integer t (1≤t
2021-05-21 13:30:31
404
原创 D. Armchairs(dp)
题目链接There are n armchairs, numbered from 1 to n from left to right. Some armchairs are occupied by people (at most one person per armchair), others are not. The number of occupied armchairs is not greater than n2.For some reason, you would like to tell p
2021-05-18 19:45:14
380
1
原创 C. Robot Collisions(思维)
题目链接outputstandard outputThere are n robots driving along an OX axis. There are also two walls: one is at coordinate 0 and one is at coordinate m.The i-th robot starts at an integer coordinate xi (0<xi<m) and moves either left (towards the 0) or r
2021-05-18 19:12:58
475
原创 A. Potion-making（思维）
You have an initially empty cauldron, and you want to brew a potion in it. The potion consists of two ingredients: magic essence and water. The potion you want to brew should contain exactly k % magic essence and (100−k) % water.In one step, you can pour
2021-05-18 18:39:40
240
原创 「LibreOJ β Round」ZQC 的拼图（二分+dp）
题目链接题目描述ZQC 和他的妹子在玩拼图。她们有 块神奇的拼图，还有一块拼图板。拼图板是一个 的正方形网格，每格边长为 1，如图所示。每块拼图都是直角三角形，正面为白色，反面为黑色，拼图放在拼图板上时，必须正面朝上，直角顶点必须与拼图板上的一个格点重合，两条直角边分别向左和向下。拼图可以重叠在一起。拼图的左下部分可以超过拼图板的边界，如图所示。这些拼图有一个好，就是能伸缩，当然，拼图伸缩是要按基本法来的，具体说来就是：你可以选择一个正整数 ，并使所有拼图的每条边长都变成原来的 倍。妹子摆好拼
2021-05-14 16:07:21
869
3
原创 A. Do you want a date?（思维）
time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLeha decided to move to a quiet town Vičkopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network
2021-05-06 17:46:50
279
原创 1111
#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1<<21;int a[110];int main(){ int T; scanf("%d",&T); while(T--) { int n,x; scanf("%d",&n); if(n%2==0) { x=n/2; int t=sqrt(x); if(t*t=
2021-05-06 11:42:01
125
原创 B. Phoenix and Puzzle（思维）
time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPhoenix is playing with a new puzzle, which consists of n identical puzzle pieces. Each puzzle piece is a right isosceles triangle as shown below.A
2021-05-06 11:35:56
338
原创 C. Vasya and Basketball（思维）
题目描述Vasya follows a basketball game and marks the distances from which each team makes a throw. He knows that each successful throw has value of either 2 or 3 points. A throw is worth 2 points if the distance it was made from doesn’t exceed some value of
2021-04-30 14:12:23
121
原创 小奇采药(搜索)
分析：本来以为是用背包，但是m太大，并且n比较小，所以可以用搜索。将草药根据采摘时间从大到小排序，计算时间和价值的后缀和剪纸：1.如果当前的价值加上后面所有的草药价值还是小于ans，则直接退出2.如果后面的草药都能摘，那么直接当前价值加上后面所有草药的价值，跟ans比较#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1<<21;int n;ll m,h1[.
2021-04-30 13:28:09
201
原创 C. Berland Regional（思维）
time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp is an organizer of a Berland ICPC regional event. There are n universities in Berland numbered from 1 to n. Polycarp knows all competitive pr
2021-04-30 01:25:21
440
原创 B. The Cake Is a Lie（思维）
time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere is a n×m grid. You are standing at cell (1,1) and your goal is to finish at cell (n,m).You can move to the neighboring cells to the right or do
2021-04-30 01:15:54
394
原创 A. Red and Blue Beans(思维)
time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou have r red and b blue beans. You’d like to distribute them among several (maybe, one) packets in such a way that each packet:has at least one red
2021-04-30 01:11:00
323
1
原创 小奇取石子（分类讨论）状压+普通dp
题目描述输入输出样例输入4 3 51 1 2 3样例输出5分析：根据数据范围可以看出对于A和C组数据,可以用简单的dp来解决f[i][j]:表示选择了i堆，所选石子不超过jB组可以用状压来解决，枚举所有状态#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1<<21;ll a[210],f[210][2510];int s[N];ll g[
2021-04-29 16:10:36
121
原创 CF490D Chocolate（思维）
题目链接题目描述Polycarpus likes giving presents to Paraskevi. He has bought two chocolate bars, each of them has the shape of a segmented rectangle. The first bar is a_{1}×b_{1} a1 ×b1 segments large and the second one is a_{2}×b_{2} a2 ×b2 segm
2021-04-29 14:48:53
91
原创 洛谷 P5663 [CSP-J2019] 加工零件（最短路）
题目描述凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 nn 位工人，工人们从 1 \sim n1∼n 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。如果 xx 号工人想生产一个被加工到第 L (L \gt 1)L(L>1) 阶段的零件，则所有与 xx 号工人有传送带直接相连的工人，都需要生产一个被加工到第 L - 1L−1 阶段的零件（但 xx 号工人自己无需生产第 L - 1L−1 阶段的零件）。如果 xx 号工人想生
2021-04-20 18:44:43
726
原创 CF494A Treasure
题目描述Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string s s written on the door consisting of characters ‘(’, ‘)’ and ‘#’. Below there was a manual on how to open the door. After spending
2021-04-20 17:44:19
89
原创 P7072 [CSP-J2020] 直播获奖（桶排序）
题目描述NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%w%，即当前排名前 w%w% 的选手的最低成绩就是即时的分数线。更具体地，若当前已评出了 pp 个选手的成绩，则当前计划获奖人数为 \max(1, \lfloor p * w %\rfloor)max(1,⌊p∗w%⌋)，其中 ww 是获奖百分比，\lfloor x \rfloor⌊x⌋ 表示对 xx 向下取整，\max(x,y)max(x,y) 表示 xx 和 yy 中
2021-04-20 17:26:03
1202
1
原创 poj2001 Shortest Prefixes（trie）
DescriptionA prefix of a string is a substring starting at the beginning of the given string. The prefixes of “carbon” are: “c”, “ca”, “car”, “carb”, “carbo”, and “carbon”. Note that the empty string is not considered a prefix in this problem, but every n
2021-04-15 09:37:54
75
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人