说句实话..学的不快,但是忘是忘的快..为什么要回顾ex_gcd呢?因为中国剩余定理要用逆元hh,所以我们要用ex_gcd求下数的逆元~我先把ex_gcd敲一下.. #include <bits/stdc++.h> using namespace std; int x,y;//解这个 ai∗xi+bi∗yi=gcd(ai,bi) void ex_gcd(int a,int b) { if(b==0) { x=1,y=0; return; } ex_gcd(b,a%b); int cx=x,cy=y; x...

看着数据范围直接dp即可,注意题意 #include <bits/stdc++.h> using namespace std; const int N=205; const int M=1005; int dp[M][N][N];//有个人到了第i个指命位子,另外两个分别在j k位子的最小代价. int a[N][N]; int p[M]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) ...

208.开关问题就是个解异或方程的高斯消元~思路:就是你把所有要改变的灯置为1,表示要改变.放在增广矩阵的最后一行.然后把和当前灯有关系的开关置为1.然后进行消元,有k个自由源答案就是2^k..代码如下: #include <bits/stdc++.h> using namespace std; const int N=35; int a[N][N],n; int gauss() { int r,c; for(r=1,c=1;c<=n;c++) { int t=r; for(int i=r+1;i<=n;i++) ...

写两个高斯消元的热身题.主要是熟悉下高斯消元...呜呜呜,当初学的ex_gcd和中国剩余定理都忘了QAQ.刷完进阶指南萌新打算刷kuangbin QAQ水题1:207.球形空间产生器思路:(x1-a[0][0])^2+(x2-a[0][1])^2+(x3-a[0][2])^2+...+(xn-a[0][n-1])^2=xn+1^2 (1)(x1-a[1][0])^2+(x2-a[1][1])^2+(x3-a[1][2])^2+...+(xn-a[1][n-1])^2=xn+1^2 (2)(x1-a[2][0])^2+(x2-a[2][1])^2+(x3-a[2][2])^2+......

emm,刚学,先来写简单的介绍下高斯消元吧QAQ...消元顾名思义,就是解方程,怎么解呢?原理就是消元,我们可以把方程消成一个正方形的形式,然后从最后一个解往后面推,然后推出一组解.代码备注很清晰 #include <bits/stdc++.h> using namespace std; const int N=105; double a[N][N]; const double eps=1e-6; int n; int gauss() { int c,r; for(r=0,c=0;c<n;c++) { int t=r; ...

这是一篇dp的题解.题目是acwing 273.分级.题目描述很简单哈.题目:给定长度为N的序列A，构造一个长度为N的序列B，满足：1、B非严格单调，即B1≤B2≤…≤BN或B1≥B2≥…≥BN。2、最小化 S=∑Ni=1|Ai−Bi|。只需要求出这个最小值S。输入格式第一行包含一个整数N。接下来N行，每行包含一个整数Ai。输出格式输出一个整数，表示最小S值。这个怎么做呢?首先我们得知道符合条件的Bi必定有一组是全部属于Ai的,证明很简单,我们把Ai排序变成Ci,假设我们当前有几组不在Ci,位于Ci~Ci+1因为中间数变成它们并不影响其他数取值,假如当前这段的Ai比Ci+1大的为x,比Ci小的...

具体b站 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[105]; int f[N]; int main() { int n,m; cin>>n>>m; f[0]=1; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=n;i>=1;i--) { for(int j=m;j>=a[i];j--) {f[j]+...

具体b站: #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=32; ll dp[N][N][N][N][N]; int s[7]; int main() { int k; while(cin>>k,k) { memset(s,0,sizeof s); memset(dp,0,sizeof dp); for(int i=1;i<=k;i++) scanf("%d",&s[i]);...

具体b站有. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=65; int n,m,t,acts;//代表n行m列.t时间,act个操作 string ops[10]; string act[10]; ll F[N],A[N][N][N],AA[N][N]; int num(int x,int y) { return (x-1)*m+y; } void mul(ll f[N],ll a[N][N]) { ll c[N]; memset(c,0,sizeo...

具体讲解b站有. #include <bits/stdc++.h> using namespace std; const int mod=10000; void mul1(int f[2],int a[2][2]) { int temp[2]={0}; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { temp[i]=(temp[i]+f[j]*a[i][j])%mod; } } memcpy(f,temp,si...

这题思路比较简单,提前是你得设出来状态. dp(i,j)表示以1~j以b[j]结尾最长公共上升子序列. 转移的条件肯定是a[i]==b[j]. 假如a[i]!=b[j].假如我现在的a[i]<b[j]那么这个a[i]一定不能通过bj转移.因为不满足递增. 假如a[i]>b[j]那么我的a[i]是可以通过现在的dp[i-1][j]+1转移的.我们直接统计下可以转移的最大值是多少就好了代码如下: #include <bits/stdc++.h> using namespace std; const int N=3e3+5; int dp[N][N]; int a[N]; i...

每日三更三更！

这个主要是为了收获更多粉丝,我会认真的讲下单调栈和如何处理这个问题的...下面贴上ac代码: #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1000000007; const int N=1e3+5; char a[N][N]; int cnt[N][N]; int stk[N]; int main() { ll ans=0; int n,m; cin>>n>>m; for(int i=1;i<=n;i++...

#include <bits/stdc++.h> using namespace std; int x,y; void ex_gcd(int a,int b) { if(b==0) { x=1,y=0; return; } ex_gcd(b,a%b); int cx=x,cy=y; x=cy,y=(cx-a/b*cy); } int main() { int a,b; cin>>a>>b; ex_gcd(a,b); cout<<(x...