把过程看作是从（0,0）到（c0，c1）的过程，1表示向右走，0表示向下走， maxx【i】【j】表示i个0，j个1的最高得分 minn【i】【j】表示i个0，j个1的最低得分 sum【x】表示标准串s，到第x位置为止共有多少1 满足s与t前缀x1同等价于sum【x】==j，后缀x1+1~n同就等价于sum【n】-sum【x】==c1-j 当t的第pos位是1或者？，maxx【i】【j】可以从maxx【i】【j-1】向右移动得到（minn同） （0或？同） maxx[i][j]=max(maxx[i][j],maxx[i][j-1]+vp*(sum[pos]==j)+vs*(sum[n]-su...

（货仓选址问题）在数轴上选一点，使得该点到其他点的距离和最小 结论：选择该组数字的中位数即可， 一共n个数，当n为奇数时，中位数【（n+1)/2】，当n为偶数时，a【（n+1)/2】~a【（n+1)/2+1】之内的数皆可 这个题目出现至少，八成就是二分 那么证明下天数是分成两段的 设第x天恰好（最少）满足要求，那么第x+1天，有一个苗增高导致不完美，那么我们可以用减一的办法让它恢复 这样x后面的天都可以变成腕足条件的 所以二分天数是可以的 （这个应该是最短的正常c++代码） #include<bits/stdc++.h> using n...

你没有看错，只要用o（1）的时间复杂度就完事了 去博客看大图：https://blog.nowcoder.net/n/fca379b2f44a47e1bb3a40d50fc8a492 创作不易，点个赞呗 #include<bits/stdc++.h> using namespace std; typedef long long ll; const long long mod=23333333333333333; typedef __int128 ii; ll...

十分感谢@Deep_Kevin的部分指导帮助 去博客看大图 点赞再走呗 #include<bits/stdc++.h> using namespace std; const int N=5e4+10; long long t,n,m,x,y,der[N],sum; void init(){ memset(der,0,sizeof der); sum=0; } int main(){ for(cin>>t;t--;){ cin>>n&gt...

去博客看大图 #include<bits/stdc++.h> using namespace std; const int mod=998244353,T=5e3+10,N=1e3+10; typedef long long ll; ll f[T+10][T+10],c[N<<1][N<<1],n,x,y,t,a,b; int main(){ //ios::sync_with_stdio(false); f[0][0]=1; for(in...

用一般的约瑟夫环会超空间 看到m==2 就可能是找规律 #include<iostream> #include<cmath> using namespace std; int num,down; string s; int main(){ while(cin>>s){ if(s=="00e0") break; num=((s[0]-'0')*10+(s[1]-'0'))*pow(10,s[3]-'0'); down=1; while(down*2&l...

i-1字符串是pre， 则第i个是pre+第i字母+pre 明显是dp， 看了下网上用的是递归 这里巧用了char【】存字符，再string+char【】来把字符转化为字符串 #include<bits/stdc++.h> using namespace std; int n; char str[1]; string s,pre; int main(){ cin>>n; s="A";  for(int i=2;i<=n;i++){ pre=s;...

圆邻相异，满足最小 易知如果n个勋章满足，那么n+1+1+....肯定满足 那么我们就要找到最小的满足，二分勋章颜色种数，检查是否满足，从中找到最小的可以满足的勋章数量 这里ma【i】表示第i个将军在与第i-1个将军不冲突的情况下，手中勋章与第1个将军颜色同的最多个数 mi【i】表示第i个将军在与第i-1个将军不冲突的情况下，手中勋章与第1个将军颜色同的最少个数 这样只要mi【n】=0即最后一个将军与第一个将军的勋章颜色的最小个数为0，则这个颜色种数是足够的 mi【i】=a【i】-还能最多提供与第1位将军勋章颜色不同的种数，如果还能最多提供>a【i】，...

一开始想用并查集，如果双方都认为对方是好的就放在一块，最后把最大的块输出 但看了别人的题解发现思维题一道，因为好芯片多，所以只要认为这个芯片好的坏的多，那么这个就是好芯片 #include<bits/stdc++.h> using namespace std; const int N=30; int n,a[N][N],good,bed,istrue[N]; int main(){ cin>>n; for(int i=0;i<n;i++){ for(int j=...

一般涉及卡特兰数的问题就两种： 1.问题可以转化为卡特兰数基本模型 2.dp推出了卡特兰数公式 卡特兰数基本模型 （1）有n个"("和n个")",求排列数，满足每一时刻“（”的数量>=  “）”的数量，【合法栈问题】 （2）从原点（0,0）到点（n,n）的排列数，使得不越过x=y这条线 卡特兰数dp公式 本层是上一层首尾相乘的和 注意公式中相乘的两项和是n-1 题目有下面特征之一的应该考虑卡特兰数 （1）有2n个物品 （2）计算过程出现了第i个*第n-1-i，即相乘...

首先看到2n，两个一组（a2i-1<a2i）可以想到卡特兰数 设奇数组的是（，偶数组的是），这就转化成了卡特兰数模型 这里用 C（2e6,1e6）大概有1e6位，但有mod p 一开始想*逆元（p不一定素数，exgcd）来搞定除数，但是逆元要求a和mod必须互质，显然不能满足所有数据，比如要乘4关于mod=100的逆元是无法求的 所以采用数分解质因数的方法，统计1~x每个质因数的幂，然后答案*=质因数^幂 这里计算从1~t质因数prime【i】总共的幂次 如1~10中3的幂数计算：10/3=3 ——有3个数3,6,9中有1个3 ...

先用dp的想法来思考这个问题 设f【i】表示i层的方法数 如何用x之前的f来表示f【x】 我们可以把阶梯以某一层分成两块，这两块都在x~x-1层之间 所以x层就被分层了i，1，n-1-i三个部分 则f【n】=f【i】+f【n-1-i】（分的方法总和），遍历i：1~n-1-i 这就是卡特兰数的模型 C（2*500，,500）大约500位数字所以用高精度 #include<bits/stdc++.h> using namespace std; typedef vector<int>&nbsp...

n点无根树的选择方法是n^(n-2) 一个无根树有n个点选作根， 方法数=n^(n-2)*n=n^(n-1) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+9; ll t,n; ll qmi(ll a,ll b){ ll res=1; while(b){ if(b&1) res*=a,&nbs...

（2n个点，就要联想到卡特兰数） 从第一个开始操作点开始编号，1,2,3。。。。 我们发现如果如果连接奇数-奇数，那么必定会有一个偶数点没办法满足题目的连接（即必会交叉） 所以我们一定是奇数-偶数这样连 再深挖下，我们发现交叉都是在始点1-终点1中的点中，有始点的终点>终点1就有交叉，比如（1,4）和（2,5） 所以把始点看出左括号，终点看出是右括号，不交叉就是所有情况都是左括号数量大于右括号数量，然后求方法数——卡特兰数 n有点大，但mod是素数 所以用组合除以的公式 #include<bits/stdc++.h> using&...