kosf_-CSDN博客

原创 [LIS]最长上升子序列

题目思路找第二个数组在第一个数组中出现的下标，然后对下标找最长上升子序列代码#include<bits/stdc++.h>using namespace std;#define int long long#define lowbit(x) x&(-x)int n;int a[100010],b[100010],dp[100010],bit[100010];map<int,int> mp;void add(int x,int d){ for(int i

2022-04-15 20:21:16 332

原创 [容斥定理] 牛客15079

题目题目代码#include<bits/stdc++.h>#define int long longusing namespace std;int a[100];signed main(){ int n; a[1]=2; a[2]=5; a[3]=11; a[4]=13; while(cin>>n){ int ans=n; for(int i=1;i<(1<<4);i++){ int cnt=0,temp=1; for(

2021-10-28 11:51:11 109

原创【组合数学】CF1313D Count the Arrays

题目题目思路首先m>=nm>=nm>=n,有一对数相同，就从mmm中选出n−1n-1n−1个数来，即(n−1m)\binom{n-1}{m}(mn−1),有n−1n-1n−1个数可能会相等。除开两个相等的，一个顶点的数，还剩n−3n-3n−3个数，可以任意放在iii两边，因此为2n−32^{n-3}2n−3.特判$n=2n=2n=2的情况代码#include<bits/stdc++.h>using namespace std;#define int long l

2021-10-21 01:51:56 176

原创【状压dp】icpc网络赛第二场 K-Meal

题目nnn个人，一个人有nnn个菜，依次拿菜，每个菜的喜爱值为aija_{ij}aij，拿走概率为aij∑j=1naij\frac{a_{ij}}{\sum_{j=1}^{n}a_{ij}}∑j=1naijaij，求所有菜被拿走的概率思路状压ans[i][j]ans[i][j]ans[i][j]表示拿了iii种菜，拿到其中jjj类型这个菜的概率f[x]f[x]f[x]表示拿的状态为xxx这种的总概率代码在这里插入代码片#include<cstdio>#include&l

2021-10-03 00:29:32 179

原创 cf D Up the Strip

题目添加链接描述代码D1D_1D1 nsqrtnnsqrtnnsqrtn做法：整除分块：using namespace std;const int INF = 0x3f3f3f3f;int dp[200010];signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; int pre=0; dp[n]=1; for(int i=n;i>

2021-08-25 21:11:20 104

原创 [唯一分解定理]洛谷P1072

题目添加链接描述刚看以为是傻逼题,找了两个小时bug我是傻逼代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<qu

2021-08-09 01:47:32 181

原创 [dp]P2789 直线交点数

题目题目代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stack&g

2021-08-08 22:26:13 126

原创 [大数区间素数]洛谷P1835素数密度

题目题目代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stack&g

2021-08-08 22:25:03 163

原创【SG函数板子】hdu1848

题目题目代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stack&g

2021-08-08 15:44:09 138

原创 [扫描线] 牛客第六场H Hopping Rabbit

题目链接思路代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stac

2021-08-07 01:25:36 76

原创 hdu7029 median

题目长为nnn的数组，把他们分成mmm份，给出每一份的中位数mjm_jmj,请求这养的分法能不能实现，可以不用连续分思路对中位数进行排序，计算每一段连续的非中位数。然后对每一段中位数进行判断，如果这一段减去前面的中位数个数之后的差能和前面的非中位数和后面的非中位数抵消，就合法。全部合法输出YESYESYES代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>

2021-08-06 16:45:04 131

原创 [构造] 牛客2021暑假第六场C

思路枚举两个点i,ji,ji,j，通过k=(2∗n−i−j)%nk=(2*n-i-j)\%nk=(2∗n−i−j)%n计算出kkk代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>

2021-08-06 16:40:39 58

原创 [二分图最小点集覆盖] poj3041

题目题目n∗nn*nn∗n的矩阵，有kkk个子，每次可以消灭一行或者一列求把他们都消灭完的最少次数。思路把kkk个子的行和列连边,找二分图最大匹配代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<

2021-08-04 20:39:13 104

原创 [二分图最大权值匹配KM模板] 牛客2021暑假第五场J

题目题目思路把时间和物品进行二分图最大匹配，因为答案求的最小值，所以是负值情况下的最大值代码#include<bits/stdc++.h>#define int long longusing namespace std;const int INF = 0x3f3f3f3f3f3f3f3f;const int N = 310;int x,y,z,v;int w[N][N];//边权int la[N], lb[N];//左、右部点的顶标bool va[N], vb[N];/

2021-07-31 22:58:31 141 2

原创 [构造] cf

题目题目思路长度为n和n+1n和n+1n和n+1相同的字符满足代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<

2021-07-30 21:47:41 58

原创 hdu6992 Lawn of the Dead

题目题目代码基本和萍姐姐的一模一样#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#inclu

2021-07-30 21:44:45 135

原创 [动态开点]2021牛客暑期4Tree Xor

题目题目思路指路博客：添加链接描述感谢xf不厌其烦地回答我的问题代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include&l

2021-07-29 21:46:28 128

原创 [生成函数]2021牛客第四场 B Sample Game

题目有一个随机数生成器，每次生成iii的概率为pip_ipi,如果现在生成的数不小于之前生成的所有数，继续随机，反之，记上分数为n2n^2n2,nnn为已经生成的数的个数思路设最长答案长度是lenlenlen,设生成函数，设它的系数是len>ilen>ilen>i的概率P(len>i)P(len>i)P(len>i)，得:f(x)=∑i=0∞P(len>i)xif(x)=\sum_{i=0}^{\infin}P(len>i)x^if(x)=∑i=0∞

2021-07-27 03:01:56 151 1

原创 [最小生成树] 牛客第三场B-Black and white

题目不想写了呜呜这篇博客写的相当的好大家快来看这篇->博客代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<

2021-07-25 16:42:00 97

原创 [完全图三元环] 牛客暑假训练营第三场-J Counting Triangles

题目题目一个完全图，有两种不同的边，求相同三条边的三元环个数思路正难反易，完全图一共有n∗(n−1)∗(n−2)6\frac{n*(n-1)*(n-2)}{6}6n∗(n−1)∗(n−2)个三元环，求出颜色不同的环的个数。遍历点，计算这个点连不同边的个数，两个个数相乘除222就是不同环的个数代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include

2021-07-25 14:13:03 290

原创 [int128] hdu 6970 I love permutation

题目题目给一个奇质数ppp，一个数aaa,序列bi=a∗i%pb_i=a*i\%pbi=a∗i%p (1≤i≤p−1)(1\le{i}\le{p-1} )(1≤i≤p−1),求出序列bbb中逆序对个数%2\%2%2的结果思路本篇博客复刻参考这篇->dalao博客1，2，3....,p−1{1，2，3....,p-1}1，2，3....,p−1是ppp的完全剩余系，a,2a,3a,....(p−1)aa,2a,3a,....(p-1)aa,2a,3a,....(p−1)a也是ppp的完

2021-07-25 01:23:11 217

原创 [01背包+分组背包] hdu6968

题目题目有nnn个科目，mmm本书，学习一本书可以让这门课期末分数增加sss分，但是需要ddd天来学习。现在一共有ttt天，最多能够挂ppp门课，求最高分思路先对每门科目进行010101背包，dp[i][j]dp[i][j]dp[i][j]表示第iii门课使用jjj天获得的分数，然后对每门科目的结果进行分组背包，ans[i][j][p]ans[i][j][p]ans[i][j][p]表示到第iii门课一共学习了jjj天，挂了ppp门，最后得出结果代码#include<cstdio>

2021-07-24 23:51:42 96

原创 [莫队]hdu6959zoto

题目题目有一个序列，长度为nnn,序列为（i,fx[i]）（i,fx[i]）（i,fx[i]），mmm次询问，询问以(x1,y1)(x1,y1)(x1,y1)作为左下坐标，(x2,y2)(x2,y2)(x2,y2)作为右上坐标形成的矩形内有几个序列内的点思路莫队，依照垂直xxx轴的最左端和左右端来分块，用树状数组来维护当前存在的点的数量代码#include<cstdio>#include<cstring>#include<cmath>#include&l

2021-07-21 23:12:29 157

原创 [01字典树] hdu6955 Xor sum

题目找出最短的连续子序列，满足异或和不小于k题目思路01字典树可以求数列间任意两数的异或最大值，将两个数换成前缀异或就可以求连续区间的最大异或值。用l、rl、rl、r表示当前的区间，如果这个区间存在异或最大值>=k>=k>=k，就从rrr开始左移，寻找最近的满足条件的lll代码#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn =3e6+5;int ti

2021-07-21 15:58:02 245

原创 [FFT]2021牛客暑假训练营 Hash Function

题目添加链接描述思路刚学先照着打了一遍，明天来补~代码#include<bits/stdc++.h>using namespace std;typedef complex<double> CP;const int lim = 1<<21;double PI = acos(-1.0);CP a[lim],b[lim];bool vis[lim];const int P = 500001;void FFT(CP *x,int lim,int inv

2021-07-21 01:13:22 98

原创 [思维]cf １５４６B. AquaMoon and Stolen String

题目题目链接思路把前ｎ个字符每个位置上字母出现的次数分别保存下来，再把后ｎ－１个字符串每个位置上的字母出现次数减去，最后１～ｍ都剩下了一个字母，即答案代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include&lt

2021-07-12 11:02:58 206

原创 [cf]思维1542B - Plus and Multiply

题目题目代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stack&g

2021-07-11 21:59:46 128

原创 [cf]F2. Guess the K-th Zero (Hard version)

题目题目的询问比easy多，每次问出来之后都要把0变成1。思路用线段树记录一下l到rl到rl到r的sumsumsum。代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#inc

2021-05-07 00:28:52 162

原创 [cf]F1. Guess the K-th Zero (Easy version)

题目交互题，输入"? l r"返回这个区间和，要在20次内找到第kkk个0思路对rrr二分，找到第一个让r−ans=kr-ans=kr−ans=k的位置代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include&l

2021-05-06 22:06:22 282

原创【莫队】 CF D. Cut and Stick

题目题目链接思路用莫队维护l—rl—rl—r区间众数，找到规律如下：代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#includ

2021-04-21 00:19:30 106

原创 [莫队算法] 板子 P2709 小B的询问

理解莫队算法就是通过改变询问的顺序来减少时间复杂度。把数组分成了sqrt(n)sqrt(n)sqrt(n)块，根据块来处理问题。板子#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>

2021-04-20 17:21:22 86

原创【二分图】牛客训练联盟 F.Group Project

题目题目链接题目大意：一班和二班的同学可能会看不顺眼，同班的同学一定不会看不顺眼。现在要给他们分组，每两个为一组，看不顺眼的不能在一组，最多能分成多少组？思路哎又看错题了对不起队友肯定是一个班的先分到一起如果一班的人数xxx,二班的人数yyy都是单数，那么如果x∗y=mx*y=mx∗y=m就构成一个二分图，两个单的人不能在一起组队。求班上的人数：可以利用二分图染色求~代码#include<cstdio>#include<cstring>#include&

2021-04-18 19:08:24 81

原创【种族并查集+01背包回溯】

题目题目代码#include<iostream>#include<queue>#include<vector>#include<map>#include<cstdio>#include<algorithm>#include<string>#include<sstream>#include<list>#include<cstring>#include<stac

2021-04-16 00:49:31 115

原创 [主席树|静态区间第k大]luogu3834

题目题目代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stack&g

2021-04-15 00:58:59 64

原创 [带权并查集] 食物链

题目题目题目sum=0sum=0sum=0代表xxx与fxfxfx为同类sum=1sum=1sum=1代表xxx吃fxfxfxsum=2sum=2sum=2代表fxfxfx吃xxx思路#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostrea

2021-04-14 13:51:07 46

原创 [带权并查集]How Many Answers Are Wrong

题目题目链接代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stack

2021-04-14 00:43:30 62

原创【线段树】Traveling Merchant

题目有nnn个城市，它们在卖同一种物品。每个城市这个物品的起始价v[i]v[i]v[i]，星期一和星期天加个为v[i]v[i]v[i],星期二和星期六价格为v[i]+d[i]v[i]+d[i]v[i]+d[i]，星期三和星期五价格为v[i]+2∗d[i]v[i]+2*d[i]v[i]+2∗d[i]，星期四为v[i]+3∗d[i]v[i]+3*d[i]v[i]+3∗d[i]。有一个人从sss城按顺序走到ttt城，在过程中进行了一次买卖，求最多能赚多少。思路创建七个线段树，分别是反推回去的城市111是星期

2021-04-01 14:39:10 103

空空如也

空空如也