http://acm.hdu.edu.cn/showproblem.php?pid=1113 字典查询–感觉挺好的一个学习题目
- kruskal算法--------------------------------下标根据题目，如果是1开始则下标也是1开始
- Floyd—最短路径算法。 ---------------------已经较熟练了。
- 状态压缩DP
- 差分的使用
- //它所处理的图中不能有负权边 dijiktra
- 尺取法—字符串型
- 尺取法—双指针遍历box，寻找最小序列。
- 尺取法精简模板
- 尺取法—求和满足条件版-----复杂度O(n)----虽然我感觉是O(NlogN)
//连通图里搜索最小生成树 且其所有边的权值之和亦为最小 prim
8.简单广搜模板。
9.结构体的构造函数的使用
10.大数加减乘除代码实现
11.树状数组基础版—学习
12.树状数组基础版—学习2 二维模板
13.费马小定理-----逆元。
14.exgcd的使用
15.多重背包问题-----二进制优化代码实现
16.斯特林模板
17.最长子序列O（n^2）算法
18.最长子序列O（logN）算法
19.KMP简单应用
20.KMP next[i]的应用 - KMP二维数组-----模板题
- 矩阵快速幂----模板
- 矩阵乘法优化，将O(n)的递归降到O(logN)
- 状态方程与矩阵乘法的转变。
- [HTML_REMOVED]头文件 stringstream 的用法
- 字典序trie—最基础模板。求前缀个数。 利用记录节点出现次数的方式存储sum[trie[root][id]]
- 马拉车—模板
- 线段树了解----------------------从1开始。
- next数组+KMP 模板
- dijkstra快速版----还是有点没咋理解。有空看。
- 链式向前星+代码
- LCA模板
- 母函数—普通版—砝码问题（组合问题）—【需要从0开始的，因为x0次，我们不能忽略。】–然后ans[0]=1老忘记。
- 母函数—指数版—排列问题
- 莫队—模板题。（重要的是他的思想）—【建议从1开始】
- 离散化使用方法
- unique函数的使用：
- 强连通分量------korasaju算法
- 强连通—tarjan算法
- 树状数组求逆序对。--------------------【建议从1开始】
- 二分图最大匹配—匈牙利算法。---------【可以从1开始】----还是挺简单的，现在自信心爆棚。加油，冲冲冲。
- 二分图最大匹配—染色法。-----在使用前，我们并不知道是否是二分图，因此用染色法进行判断。（也简单，就一个bfs一正一负）
- 快排模板。
- 优先队列默认从大到小，如何从小到大？----模板
- 博弈图模拟。-----|= 是真牛逼。 还有就是记忆化搜索 vis+win数组的组合太棒了
- RMQ模板–nlgn快速求区间【l,r】的最大值/最小值。-----【建议从1开始】----O(N)~O(logN)
- RMQ学习+二维数组传参用法。
- 状态dp模板思考—真的，虽然今天基本能懂一半多，明天可能就完了，多看，多理解。加油。
- 树状数组，区间单点更新+求最大值-----RMQ对于单点更新毫无办法
- 几何概型—就是几何题，只是多了面积相除成概率-----梯形面积的求法还是看不懂
- 几何题—点与向量模板
- 求多边形面积。------结合了点与向量的模板，和叉乘的几何意义
- 几何题—线与线模板
- 几何题—线线求交点
- 几何题知识点思维导图：------之后尽可能的将我所学过的知识通过这样的形式，变的比较系统，好联想。
- 扫描线算法+线段树模板----求覆盖矩形面积。
- 凸包模板—andrew算法—O(NlogN)
- 单调队列模板
- 单调队列应用----------O(N)-----【建议从1开始】
- Floyd求走过第k条边后的最短路----快速矩阵
- 埃筛模板
- 欧拉筛模板-----存素数用欧拉筛，尽量别用埃筛。
- 期望dp入门代码
- 归并排序模板
- 数位dp模板------求区间内，满足要求的数。经典：【0.100】求没有4和62的数有多少个62. 归并排序模板
- 卡特兰数----(组合变排序公式+大数模拟技巧) An=Cnm!n!=(n+m)!*(m+1-n)/(m+1);
- 卡特兰数 简单递归代码
- sg暴力模拟代码参考。
- 滚动数组的使用及思考
- 线段树的一个应用
- 线段树的灵活使用
线段树的灵活使用
《Non-Decreasing Dilemma》
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int maxn=2e5+100;
const int MOD=100;
typedef long long ll;
#define lc (u<<1)
#define rc (u<<1|1)
/*
***
题意：有个数列，操作2：求给定范围的非降序子数列有多少个。 操纵1：把数组的一个数直接变y
******
思考：
直接线段树开起来了。----因为即要修改又要查。---没有涉及到区间修改。
1、先建树。函数一般需要：(当前结点 u，当前结点左范围，右范围)；
2.区间求和和修改其实是同一个代码，前者多了一个合并的函数。
*/
int t,n,q;
ll a[maxn];
struct node
{
int l,r;
ll sub_num;
int llen,rlen;//---这个是要自己思考添加的
}tr[maxn<<2];
//========================================添加============================================
node node_merge(node left,node right){
node ret;
ret.l = left.l,ret.r = right.r;
ret.sub_num = left.sub_num + right.sub_num;//个数为 左边的个数+右边的个数。-------有点dp的思想。
//然后考虑难的
if(a[left.r] <= a[right.l])//如果是连续升。例：1 2 那么就不是2，是3
{
ret.sub_num += 1ll*left.rlen * right.llen;//确实是乘法。---因为我们llen就是上升子数列的长度。
}
if(left.r-left.l+1 == left.llen && a[left.r] <= a[right.l]){//然后我们确定长度。----left.r-left.l+1 == left.llen如果整个都是上升子数列并且右边还是可以接上
ret.llen = left.llen + right.llen;
}else{
ret.llen = left.llen;
}
if(right.r-right.l+1 == right.rlen && a[left.r] <= a[right.l]){
ret.rlen = left.rlen + right.rlen;
}else{
ret.rlen = right.rlen;
}
return ret;
}
//========================================添加============================================
//========================================模板============================================
void build(int u,int l,int r)
{
tr[u].l=l;tr[u].r=r;
if(l==r)//----都为一个时，结束。
{
tr[u].sub_num=tr[u].llen=tr[u].rlen=1;//初始化
return ;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
tr[u] = node_merge(tr[lc],tr[rc]);
}
void update(int u,int index,int val)//单点修改。
{
if(tr[u].l==tr[u].r) {a[index]=val;return ;}
int mid=(tr[u].l + tr[u].r)>>1;
if(index<=mid) update(lc,index,val);
else update(rc,index,val);
tr[u] = node_merge(tr[lc],tr[rc]);
}
node sum(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r) return tr[u];//如果在这个范围里面，那么我只需要它信息就够了。否则
int mid = (tr[u].l+tr[u].r) >> 1;
if(r<=mid) return sum(lc,l,r);//如果都在左边。---注意：左边有等号
else if(l>mid) return sum(rc,l,r);//如果都在右边------右边没等号
else return node_merge(sum(lc,l,mid),sum(rc,mid+1,r));//否则两边都找。----这里就又需要合并。
}
//========================================模板============================================
int main()
{
//std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> q;
for(int i=1;i<=n;++i) cin >> a[i];
build(1,1,n);
int op,x,y;
while(q--){
cin >> op >> x >> y;
if(op == 1){
update(1,x,y);//单点修改。
}else{
cout << sum(1,x,y).sub_num << '\n';
}
}
//system("pause");
return 0;
}
线段树的一个应用
#include<iostream>
using namespace std;
const int maxn=1e6+10;
struct node
{
int l,r,len;
}tree[4*maxn];
int pre[maxn],ans[maxn];
void bulidtree(int ll,int rr,int u)//就是简简单单的建立二叉树。只是多了记录状态这个步骤。
{
tree[u].l=ll,tree[u].r=rr,tree[u].len=rr-ll+1;
if(ll==rr) return ;//就是叶结点。
bulidtree(ll,(ll+rr)/2,u*2);
bulidtree((ll+rr)/2+1,rr,u*2+1);
}
int gettree(int u,int num)
{
tree[u].len--;
if(tree[u].l==tree[u].r) return tree[u].l;
//否则情况1.左子区间内牛的个数不够，则查询右子区间中左起第num-tree[u*2].len个元素。
if(tree[u*2].len<num) return gettree(u*2+1,num-tree[u*2].len);
//情况2.左子区间内牛的个数足够，依旧查询左子区间中左起第num个元素。
if(tree[u*2].len>=num) return gettree(u*2,num);
}
int main()
{
int n,i;
scanf("%d",&n);
pre[1]=0;
for(i=2;i<=n;i++) scanf("%d",&pre[i]);
bulidtree(1,n,1);//建树我们需要给定左 右和结点。
for(i=n;i>=1;i--) ans[i]=gettree(1,pre[i]+1);
for(i=1;i<=n;i++) printf("%d\n",ans[i]);
//system("pause");
return 0;
}
滚动数组的使用及思考
https://codeforces.com/gym/103366/problem/A
#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
const int MOD=998244353;
typedef long long ll;
int n,m,p,q;//p是0的个数
int dp[2][510][1010];
int room[maxn][maxn];
int d;
int main()
{
cin>>n>>m>>p>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&room[i][j]);
if(room[1][1]) dp[1][1][0]=1; else dp[1][1][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1&&j==1) continue;//已经特判过了。
if(room[i][j])
{
for(int k=0;k<1010;k++)
dp[1][j][k]=(dp[0][j][k]+dp[1][j-1][k])%MOD;
}
else
{
dp[1][j][0]=0;//0+任何数等于本身。没有任何意义。只是防止数组越界。
for(int k=1;k<1010;k++)
dp[1][j][k]=(dp[0][j][k-1]+dp[1][j-1][k-1])%MOD;
}
//如果滚动数组放这，那么dp[][][]存放的就是每次j的变化下所有的可能情况。对于状态方程：dp[1][j][k]=(dp[0][j][k-1]+dp[1][j-1][k-1])%MOD;
//你上面的dp[i-1][][],就不在是i行的情况，而是j变化下的所有情况。就不符合我们的dp设计了。
}
for(int j=0;j<=m;j++)//滚动数组都是放在循环第一层下面的。----存的是第i行的所有可能情况。
for(int k=0;k<1010;k++) dp[0][j][k]=dp[1][j][k];//滚动数组
}
int sum=0;
for(int i=p;i<=n+m-1-q;i++) sum=(sum+dp[0][m][i])%MOD;//为什么要减1？n+m-1才是从(1,1)到(n,m)所用的步数
cout<<sum<<endl;
//system("pause");
return 0;
}
二分查找的用法
直接暴力1~1e9搜答案。
https://pintia.cn/problem-sets/1448240493703385088/problems/1448250114312679424
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
/*
我当时的疑惑：这个蛋糕他们是各自独立的，我们要怎么去区分他
(不能简单累加再除，可能会出现一个蛋糕很小的情况，以及如果第一个可以切3块第二个可以切2块，这样要怎么判别？)
---这里一直想不通。
二分暴力搜。---正如上面所说，到底切几块，因为他们都是各自独立，我不能通过这个来判断，
那么还有一个思路是：我暴力猜测一下，这块蛋糕的可能大小。因为要求最大，所以可以通过二分来找到。
然后我们再看一下数据大小，是否符合我们的想法。：最大为1e6. 二分的复杂度是多少？1-1e9.所以是log(1e9)=9;1e7完全足够。
*/
int flag=0;
int a[maxn];
int n,m;
int judge(int w)
{
int sum=0;
for(int i=0;i<m;i++)
{
sum+=a[i]/w;
}
if(sum>=n) return 1;
return 0;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++) scanf("%d",&a[i]);
int l=0,r=1e9;
while(l<r)
{
int mid=l+r+1>>1;//为啥还要+1？
//答：---因为我们用的左开右闭。(0,1]这样的形式。如果不+1：0+1>>1就会=0.而我们知道应该可以取到1.所以0+1+1>>1就可以取到1了。
if(judge(mid)) l=mid;//---为啥不是mid+1:答： ---因为我们用的左开右闭。(1,1]来代表结束。
else r=mid-1;
}
printf("%d",r); //r一定是对的吗？ ----答：是的。因为最终都是(1,1]这样的形式结尾。所以，l或r无所谓。
}
/*
4 3
0 3 1
答案： 1 输出2.
int l=1,r=1e9;
while(l<=r)
{
int mid=l+r>>1;
if(judge(mid)) l=mid+1;
else r=mid-1;
}
普通的二分也没问题。[手动捂脸哭]。 ---普通的二分是闭区间。
*/
sg暴力模拟代码参考。
总思路就是：去找他们、下一跳(用if来判断怎么跳)
跳到之后，就是if有一个是必败态，则该点为必胜态。 if都为必胜态，则该点为必败态。
0代表必败。1代表必胜。
如果我能让对方站在0上，我一定会让它站在0上。所以只要有0就是1.
如果全是1，才是0.
https://acm.hdu.edu.cn/showproblem.php?pid=1079
if(m==2 && d==day[y] || m<12 && mm[m]==d && mm[m+1]>=d)//判断
{
int a=g(y,m+1,d) , b=g(y,m+1,1);//------------------如果是在二月最后一天或者其他月份中最后一天且下个月可以直接跳的时候
if(a==0 || b==0) return sg[y][m][d]=1;
else if(a && b) return sg[y][m][d]=0;
}
卡特兰数 简单递归代码
h[0]=1;
h[1]=1;
for(int i=2;i<40;i++)//长度。
{
for(int j=0;j<i;j++)
h[i]+=h[j]*h[i-j-1];
}
递归写法-->直接卡特兰数的，不需要拐弯抹角的：每一个h[i]都是前面的h[i]
卡特兰数----(组合变排序公式+大数模拟技巧)
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+10;
/*
卡特兰数变种---(涉及大数运算【一般情况是逆元】，组合变排列。)
一般而言，为了降低难度，题目会要求我们计算排列数量，所以对于排列
我们的公式An=Cn*m!*n!----->(m+n)!*[(m+1-n)/m+1];
C(m,m+n)是所有情况的个数。
C(m+1,m+n)是因为不符合条件转过后，才符合条件的个数，所以他也可以代表不符合条件的个数。
两个相减，即可得符合条件的个数。
*/
int m,n;
int fact[205][100];
void multiply(int a[],int b);//大数乘法---辅助。
void divide(int a[],int b);//没办法，1/4 或者 3/4 无法很好的表示。所以只能f()/4 *3.
void Fact()//以字符串的形式求阶乘。
{
fact[0][99]=fact[1][99]=1;
for(int i=2;i<=200;i++)
{
memcpy(fact[i],fact[i-1],100*sizeof(int));//相当于赋值。只是这里是给字符串赋值，有点麻烦。
multiply(fact[i],i);
}
}
int res[100];
void solve()
{
Fact();
memcpy(res,fact[m+n],100*sizeof(int));
//multiply(res,(m+1-n)/(m+1));//---如果这样 3/4就是0了。
multiply(res,m+1-n);
divide(res,m+1);
//multiply(res,m+1-n);//-----------woc，放后面都不行，因为他是整除所以，对于余数而已，我们必须要按顺序来，才能保证答案正确。
//=====输出。
int pos=0;
while(!res[pos]&&pos<100) pos++;
printf("%d",res[pos++]);
//cout<<pos<<endl;
for(int i=pos;i<100;i++) printf("%04d",res[i]);//----大数分4个来拆，如果中间是13则应该输出0013.
puts("");
}
int main()
{
int kase=0;
while(~scanf("%d %d",&m,&n),n+m)//m:+1,n:-1
{
printf("Test #%d:\n",++kase);
if(m<n) puts("0");
else solve();
}
return 0;
}
void multiply(int a[],int b)
{
int box=0;
for(int i=99;i>=0;i--)
{
box+=b*a[i];
a[i]=box%10000;
box/=10000;
}
}
void divide(int a[],int b)
{
int box=0;
for(int i=0;i<100;i++)
{
box=box*10000+a[i];
a[i]=box/b;
box%=b;
}
}
数位dp模板
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e3+10;
/*
数位dp
对每一位进行猜测
*****
dfs(pos-1,-1,0,true);
pos-1:数位 下标
-1：一开始的前导是没有的。
0：前导是-1不是6所以0
true:第一位他是有上界的。
dp:用来记忆化，这种组合有多少中可行方案。
*/
int a[10];//100 0000 最多也就7位。
int dp[10][2];//[2]limit为0时[0-9]的贡献。limit为1时[0-limit]的贡献； 这里用sta是因为如果i为6的话，那么2一点不能要。i不为6，则可能全要。与limit一样的道理。
int dfs(int pos,int pre,int sta,bool limit)
{
if(pos==-1) return 1;//结束标志，代表这样的序列是1个。
if(dp[pos][sta]!=-1&&!limit) return dp[pos][sta];//记忆化搜索。----如果到极限了我们就tmp自己算。
int up=limit?a[pos]:9;//确定上界。
int tmp=0;
for(int i=0;i<=up;i++)
{
if(pre==6&&i==2) continue;
if(i==4) continue;
tmp+=dfs(pos-1,i,i==6,limit&&i==a[pos]);//pos-1这步就是计算他的组合了。---重点
//limit&&i==a[pos]很巧妙。包含了那3个条件
}
if(!limit) dp[pos][sta]=tmp;//如果不是极限，那么这个位置的所有情况就是dp[pos][sta];
return tmp;
}
int solve(int x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,-1,0,true);
}
int main()
{
int l,r;
while(~scanf("%d %d",&l,&r),l+r)
{
memset(dp,-1,sizeof(dp));
printf("%d\n",solve(r)-solve(l-1));
}
return 0;
}
归并排序模板----懂思路和代码意思
#include <bits/stdc++.h>
using namespace std;
int a[100];
int t[100];
void merge_sort(int* a,int l,int r,int*t)
{
if(r-l<=1) return;//一直分。
int m=l+(r-l)/2;//分半的写法、 整除是朝零方向取整。
int l_l=l,r_l=m,i=l;//l_l左端点的第一个，r_l右端点的第一个。 这个i=l非常重要。
merge_sort(a,l,m,t);//m是中点。
merge_sort(a,m,r,t);
while(l_l<m||r_l<r)//对分开两边的高度代码。---如果左边的有值，或者右边的有值
{
if(r_l>=r||(l_l<m&&a[l_l]<=a[r_l])) //如果右段为空值，或者左端非空，且左端比右端小
t[i++]=a[l_l++];//左边的放入数组t中
else t[i++]=a[r_l++];//否则把右边的放入数组t中
}
for(i=l;i<r;i++) a[i]=t[i];
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
merge_sort(a,0,n,t);
for(int i=0;i<n;i++) printf("%d ",t[i]);
system("pause");
return 0;
}
我能学到：
1.字典题目思路
2.string 内的字符排序
3.string 数组的字符排序
4.一个说法：string b[] 存放的是组成单词的字母（这个思想可能很有用）
第一感觉：
我一开始想的是把它们拆成单个字符，然后记录他们的字符个数
可是随机组合怎么可能随机组合啊？肯定实现不了的呀，而且也没有那种多个变量，确定一个值的那一种，反正就是没法做，怎么做呢？
做法：
首先定义两个字符串，把我们要输入的词放到这两个字符串中，其中一个是保存正常的值，另一个则是保存他那个单个字符的排序（代表该单词由这几个字母组成）。这样就能确定它是由哪些字母组合起来的。字典的问题就解决了
接下来就是判断
同样先把我们输入的那个单词进行字母排序，得到这个单词，由什么字母组成。然后逐一去遍历一遍，。如果有，那就把正确的那个值输出来就好了，如果没有，那就是去no嘛
然后他这里还有一个问题，就是如果有多个这样字符组成的单词，我们要从小到大进行输出，那么问题来了，我们该怎样进行排序？比如你试着a排序，b排序，然后再输出，很显然，那是错的，那么对于这种一个真值，又有另一个特征码，我们该如何对真值进行排序？
目前好像确实实现不了，这里的做法是在添加个数组c，把他进行排序。
我的小关卡。
设两次这个数组，这是个技巧
我的下个目标：
我要去了解并查集
队列
深搜
广搜
附代码：
#include<iostream>
#include <algorithm>
#include <string>
using namespace std;
int cmp()
{
}
int main()
{
string a[105];
string b[105];
string s;
int count = 0;
int f=0;
while (cin >> s)
{
if (s == "XXXXXX") break;
a[count] = s;
b[count] = s;
sort(b[count].begin(),b[count].end());
count++;
}
//sort(b,b+count);//他的排序是怎么排的？？？？？
string c[200];//实现从小到大排序
int j=0;
bool have;
while(cin>>s)
{
if (s == "XXXXXX") break;
sort(s.begin(),s.end());
for(int i=0;i<count;i++)
{
if(s==b[i])
{
//cout<<a[i]<<endl;
c[j++]=a[i];
have=true;
//f=1;
}
}
if(have)
{
sort(c,c+j);
for(int i=0;i<j;i++)
{
cout<<c[i]<<endl;
}
}
else
{
cout<<"NOT A VALID WORD"<<endl;
}
cout<<"******"<<endl;
have=false;
j=0;
}
return 0;
}
kruskal算法
二刷：
{
疑问：我是如何判断退出kruskal？
答；不需要判断，全部遍历一遍即可。代码非常简洁。也保证了每个点都能连。
如果判断是否是全部连接成功，我们只需要遍历每个点，如果发现不在同个集合里，那就是没有全部连接成功。
}
题目： 1863
使用前，我们需要知道每条边和每条边的权值，—（会按从小到大排序）接着就是kruskal–找最小边，用并查集维护。
#include<iostream>
#include<algorithm>
using namespace std;
/*
首先：并查集需要什么？
1.初始数组。
然后，krusikal需要什么？
1. 结构体---表示每个节点的关系，即网。
2，sort排序---- 结构体排序需要写cmp函数
点 边。并查集。
要想成网 必须知道起始点，目标点，权值。--结构体。
*/
const int maxn=1000+10;
long long s[maxn];
struct edge
{
int from,to;
long long k;
}E[maxn*maxn];
int M,N;
int cmp(edge a,edge b)
{
return a.k<b.k;
}
int find(int x)
{
return s[x]= s[x]==x?x:find(s[x]);
}
int same(int x,int y)
{
return find(x)==find(y);
}
void nuion_set(int x,int y)
{
x=find(x);//1
y=find(y);
if(x!=y) s[x]=s[y];
}
long long krusikal()
{
long long res=0;
sort(E+1,E+N+1,cmp);
for(int i=1;i<=N;i++)//这边忘记了。----怎么样会退出？
{
if(!same(E[i].from,E[i].to))
{
nuion_set(E[i].from,E[i].to);//
res+=E[i].k;
}
}
return res;//少了return。---wa了一次
}
void init()
{
for(int i=0;i<=M;i++)
{
s[i]=i;
}
}
int main()
{
while(cin>>N>>M,N!=0)
{
init();//
for(int i=1;i<=N;i++)
{
cin>>E[i].from>>E[i].to>>E[i].k;
}
long long res=0;
res=krusikal();//
for(int i=1;i<=M;i++)
{
if(!same(1,i)) {res=-1;break;}//
}
if(res==-1)
{
cout<<"?"<<endl;
}
else
{
cout<<res<<endl;
}
}
return 0;
}
Floyd—最短路径算法。
hdu2544
最短路有三种：1迪杰斯特拉、2.贝尔曼、3.弗洛伊德
弗洛伊德是多源的。就是有多条路可走。
迪杰斯特拉和Berman都是单源的。
弗洛伊德和贝尔曼都可以判断负权，而迪杰斯特拉不行。
有助于理解：
g[i,j]表示i到j的最短距离，K是穷举i,j的断点
#include <iostream>
using namespace std;
const int maxn = 1000 + 10;
const int INF = 0x3f3f3f;
/*
floyd
路径题：有点，有边，有邻接矩阵(要初始化)---没了，然后就是核心思想了。
1.学到了如何剪枝。
解答①的问题：
**结论：题目是从1开始，那么循环都从1开始。**
原理：首先理解，k代表的含义是把k作为一个中转去和直达进行比较。都从1开始。那么0的范围自然取不到。所以不用怕，直接把0改1即可。
*/
int g[maxn][maxn];
int n, e;
void floyd()
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
if(g[i][k]==INF) continue;//学到了这个。---剪枝对于1000内的。
for (int j = 1; j <= n; j++)
{
if (g[i][j] > g[i][k] + g[k][j])
{
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
}
void init()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
g[i][j] = 0;
else
g[i][j] = INF;
}
}
}
int main()
{
while (cin >> n >> e, n + e)
{
int a, b, c;
init();
for (int i = 1; i <= e; i++) //① 这个i是0 是1 这是我思考的一个问题。----因为他们都是从1开始，那么我也从1开始。
{
cin >> a >> b >> c;
g[a][b] = g[b][a] = c;
}
floyd();
cout << g[1][n] << endl;
}
return 0;
}
/*
学习辅助---打印以k为中转事的邻接矩阵。
void floyd()
{
cout << "case" << 0 << endl;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << g[i][j] << " ";
}
cout << endl;
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (g[i][j] > g[i][k] + g[k][j])
{
g[i][j] = g[i][k] + g[k][j];
}
}
}
cout << "case" << k << endl;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << g[i][j] << " ";
}
cout << endl;
}
}
}
3 3
1 2 5
2 3 5
3 1 11
*/
状态压缩DP
题目： hdu1074
状态压缩，就是把状态压缩成二进制，使的每个数字都代表一种状态。
#include<iostream>
#include<cmath>
#include<stack>
#include<cstring>
using namespace std;
const int INF= 0x3f3f3f;
struct p
{
char name[200];
int dead;
int day;
}a[20];
//还不够，我还有定义一个dp，这个dp比较特殊，要用结构体来定义。
struct p1
{
int score;//要扣掉的分数
int time;//做的时间。
int fa;
int kc;//哪门课程
}dp[1<<15];
int main()
{
int t,n,total;//total是所有情况。
cin>>t;
while(t--)
{
cin>>n;
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++) cin>>a[i].name>>a[i].dead>>a[i].day;
total=1<<n;
for(int i=1;i<total;i++)//模板---意思把所有情况都遍历一遍。
{
dp[i].score=INF;//目标：确定001是由谁来的？ 怎么找？---就是没总情况遍历一遍。如果发现满足条件的执行。
for(int j=n-1;j>=0;j--)
{
int index=1<<j;
if(i&index)//发现这个地方 是做完作业的。
{
index=i-index;///很重要，通用的。就是把那个1代表做的，变成了0代表没做。 就可以得到001的上一个状态 即000的状态。
int tt=dp[index].time+a[j].day-a[j].dead;//没做时dp现在的时间+他做的时间-截止时间。
if(tt<0) tt=0;//说明我截止日期的时间比较久，我在截止日期内完成了，
if(tt+dp[index].score<dp[i].score)
{
dp[i].score=dp[index].score+tt;
dp[i].time=dp[index].time+a[j].day;//他的作用，我到现在还没感知出来。
//为了打印路径
dp[i].fa=index;//确实。他的父结点=他自己-他已经完成的点。
dp[i].kc=j;//j是课程？
}
}
}
}
cout<<dp[total-1].score<<endl;
stack<int>q;
int tt=total-1;
while(dp[tt].time)
{
q.push(dp[tt].kc);
tt=dp[tt].fa;
}
while(!q.empty())
{
cout<<a[q.top()].name<<endl;
q.pop();
}
}
return 0;
}
差分的使用
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x3f3f;
const int maxn=100000+10;
int m,n;
int s[maxn];
int a[maxn];
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++) cin>>s[i];
for(int i=1;i<=m;i++) a[i]=s[i]-s[i-1];//差分完成。
while(n--)
{
int a1,b1,c1;
cin>>a1>>b1>>c1;
//是这么区间修改的。
a[a1]+=c1;
a[b1+1]-=c1;
}
for(int i=1;i<=m;i++)
{
a[i]=a[i-1]+a[i];//是这么输出的。
//差分第一个a[1]就是头（第一个输入的数）。
i==1?cout<<a[i]:cout<<" "<<a[i];
}
cout<<endl;
return 0;
}
/*
*/
尺取法思想。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int maxn=10000+10;
int ans;
int a,b;
int k,cnt;
void fun(char str1[],char str2[])
{
int r=-1;//所以需要定义一个r。与l在起始位置等着。
int len=min(strlen(str1),strlen(str1));//--------------所以需要先长度。
for(int l=0;l<len;l++)//我需要知道，目前的最小长度是多少。（如果长度多了，是没有任何用多加时间。）
{
while(r+1<len)//我们要齐头并进。while 要有 r
{
if(str1[r+1]!=str2[r+1])
{
if(cnt+1>k)
{
break;
}
cnt++;
}
r++;
}
ans=max(ans,r-l+1);
//然后开始l的工作，即开始减了。
if(str1[l]!=str2[l]) cnt--;
}
}
int main()
{
int t,n,box,h,r;
cin>>t;
while(t--)
{
cnt=0;
char str1[maxn];
char str2[maxn];
ans=0;
scanf("%d %s %s",&k,str1,str2);
int l=strlen(str1);//拿最大的过来进行取尺
for(int i=0;i<l;i++) fun(str1+i,str2);//取尺开始。
l=strlen(str2);
for(int i=0;i<l;i++) fun(str2+i,str1);
printf("%d\n",ans);
}
return 0;
}
尺取法—双指针遍历box，寻找最小序列。
尺取法。---又名双指针算法。
int l,r,len;
while（r<len）
{
...
if(满足条件)
while(l<r)
{
...
l++;
}
r++;
}
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const long long maxn=100000+10;
const long long INF=0x3f3f3f;
long long a[maxn];
int flag[maxn];
bool vis[maxn];
int b[maxn];
int ans=0,sum=0;
int m,n,x,y;
void init()
{
memset(flag,0,sizeof(flag));
memset(vis,true,sizeof(vis));
}
int main()
{
int t;
while(cin>>n>>m,m+n)
{//n个数，m次询问。
for(int i=0;i<n;i++) cin>>a[i];
while(m--)
{
sum=0;
init();
cin>>t;
for(int i=0;i<t;i++)
{
int n;
cin>>n;
if(flag[n]>=1) continue;
flag[n]++;
sum++;
}
ans=INF;
int len=n,cnt=0;
int r=0,l=0;
while(r<len)
{
if(flag[a[r]]==1) cnt++;
if(flag[a[r]]>=1) flag[a[r]]++;
if(cnt==sum)
{
while(l<r)
{
//vis[i]很重要。可以想象成vis[i]这块区域有亮变暗了。
if(flag[a[l]]==2&&vis[l]==true) {flag[a[l]]--;cnt--;vis[l]=false;break;
}
if(flag[a[l]]>2) flag[a[l]]--;
vis[l]=false;
l++;
}
ans=min(ans,r-l+1);
//cout<<"==="<<r<<l<<endl;
}
r++;
}
cout<<ans<<endl;
}
}
return 0;
}
简单广搜模板。
//广搜---低配：房间，方向、状态记录node、行和列。4个
#include<stdio.h>
#include<queue>
#include<stdlib.h>
const int maxn=1e3+10;
using namespace std;
int m,n;
char room[maxn][maxn];
int dir[8][2]={-1,-1 , -1,0 , -1,1 , 0,-1 , 0,1 , 1,-1 ,1,0 ,1,1};
struct node
{
int x;
int y;
};
int judge(int a,int b)
{
if(a>=0&&b>=0&&a<n&&b<m) return 1;
return 0;
}
int bfs(int a,int b)
{
queue<node> q;
node start,end;
start.x=a,start.y=b;
room[start.x][start.y]='.';
q.push(start);
while(!q.empty())
{
start=q.front();
q.pop();
for(int i=0;i<8;i++)
{
end.x=start.x+dir[i][0];
end.y=start.y+dir[i][1];
if(room[end.x][end.y]=='W'&&judge(end.x,end.y))
{
room[end.x][end.y]='.';
q.push(end);
}
}
}
return 0;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
getchar();//重中之中。分析。
for(int j=0;j<m;j++)
{
scanf("%c",&room[i][j]);
}
}
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
//printf("%c",room[i][j]);
if(room[i][j]=='W') {bfs(i,j);ans++;}//printf("%d %d\n",i,j);
}
}
printf("%d\n",ans);
system("pause");
return 0;
}
/*
不知道错哪？难道没有全部遍历？
1.getchar()。但没解决根本问题。
2.我发现我连输入都有问题。
3 3
WW.
...
..W
2 2
..
.W
2 2
..
W.
*/
结构体的构造函数的使用
课程设计的感悟：了解了结构体的构造函数三种形式。
学会了map与结构体的灵活组合运用。
了解了map的迭代器的使用和原理分析。
map排序那种直接作用在map身上的我还没学会，好像是operator啥的。
但我可以把map的数据放入vector里进行排序（sort方便），然后输出。
//班级成绩管理系统
#include<iostream>
#include<stdlib.h>
#include<string>
#include<map>
#include<algorithm>
const int maxn=1e8+10;
using namespace std;
//在建立结构体数组时,如果只写了带参数的构造函数将会出现数组无法初始化的错误！！！各位同学要牢记呀！
//链接：https://www.cnblogs.com/wlw-x/p/11566191.html
struct student
{
void init(string na,string id,int a,int b,int c)//void 不能与上面同名---------------------自定义初始化函数的调用
{
num = id;
name = na;
YW =a;
SX =b;
YY =c;
}
student(string na,string id,int a,int b,int c)//必须与上面类型一致。---------------------有参数结构体构造函数；
{
num = id;
name = na;
YW =a;
SX =b;
YY =c;
}
student(){}
string num;//学号
string name;//名字
int YW;
int SX;
int YY;
}p;
map<string,student> mp;
map<string,student>::iterator it;
int main()
{
int cz;
while(1)
{
scanf("%d",&cz);
switch(cz)
{
case 1:
//mp["0001"].name="无参默认结构体构造体函数",mp["0001"].num="0001",mp["0001"].SX=1,mp["0001"].YW=1,mp["0001"].YY=1;
mp["0001"]={"无参数结构体构造函数；","0001",1,1,1};//---无参默认结构体构造体函数
break;
case 2:
mp["0001"]=student("有参数结构体构造函数；","0001",12,12,12);
break;
case 3:
mp["0001"].init("自定义初始化函数的调用,通常作为初始化赋值","0001",123,123,123);
break;
}
for(it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<" "<<it->second.name<<" "<<it->second.YW<<" "<<it->second.SX<<" "<<it->second.YY<<endl;
}
}
system("pause");
return 0;
}
树状数组基础版—学习
gwt_sum()实际应用：
在一维下，代表该位置左边值的总和
在二维下，代表该位置左下方区域值的总和
updata(i,1);的妙用：
gwt_sum()实际应用：可以代表当前位置左边小于当前位置的值的个数有几个。
star 里巩固了
map只在插入和删除使比数组快，查询时，还是连续地址的数组更快。------当时就因为 这个超时了
加深了树状数组的性质：有个性质：父节点是它每个左下角的值之和。
二维模板：记住一个原则：先积y再积x(因为你的代码习惯就是这样)，否则，会出现计算错误。
#include<iostream>
#include<cstring>
#include<algorithm>
const int maxn =1e6+10;
using namespace std;
/*
https://blog.csdn.net/u014569598/article/details/42078429
//归并（逆序对）
https://www.cnblogs.com/ECJTUACM-873284962/p/?page=68
跟着大佬做题目
1.把点离散化。==结构体“点” 包括序号，大小，最终位置
*/
struct node//离散化
{
int id;
int val;
int pos;
}a[maxn];
int tree[maxn];
int n;
int cmp1(node a,node b)
{
if(a.val==b.val) return a.id<b.id;//离散化后，这个还是加一句。对于那些价值相等的情况。
return a.val<b.val;
}
int cmp2(node a, node b)
{
return a.id<b.id;
}
int lowbit(int i)
{
return i &-i;
}
void updata(int i,int val)
{
while(i<=n)
{
tree[i]+=val;
i+=lowbit(i);
}
}
long long query(int i)
{
long long sum=0;
while(i>0)
{
sum+=tree[i];
i-=lowbit(i);
}
return sum;
}
int main()
{
while(cin>>n,n!=0)
{
long long sum=0;
memset(a,0,sizeof(a));
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++)
{
cin>>a[i].val;
a[i].id=i;//------------------------离散化的id都是要的。
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
{
a[i].pos=i;//--------------------------最终的顺序应该是这样的。
}
sort(a+1,a+n+1,cmp2);//-----------------------重新回到一开始的顺序
for(int i=1;i<=n;i++)//--------------------------开始修改树状数组。
{
sum+=i-1-query(a[i].pos);//i是 第i个点前面的个数。。所以是大于该数的个数=前面的个数-小于该数的个数 其中，小于该数的个数，我们用树状数组进行保存更新。
updata(a[i].pos,1);
for(int k=1;k<=n;k++) cout<<tree[k]<<" ";
puts("");
}
cout<<sum<<endl;
}
return 0;
}
/*
5
9 1 0 5 4
*/
树状数组基础版—学习1
===============poj星星。了解了树状数组的基本性质。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include<cstdlib>
#include<map>
using namespace std;
const int maxn=32010;
int tree[maxn];
int x,y;
int n;
//map<long long , int>mp;//插入删除map比数组适合
int mp[maxn];//只有写入：数组地址连续，取元素的时间复杂度O(1),map取元素的复杂度O(logn)
/*
如何想到树状数组？有个性质：父节点是它每个左下角的值之和。
*/
int lowbit(int i)
{
return i &-i;
}
void updata(int i,int val)//相当于只是把值放入数组，没有总和的意思。
{
while(i<=maxn)
{
tree[i]+=val;
i+=lowbit(i);
}
}
//这里为什么要加？
long long get_sum(int i)//这个才是总和。
{
long long sum=0;
while(i>0)
{
sum+=tree[i];
i-=lowbit(i);
}
return sum;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
mp[get_sum(++x)]++;
updata(x,1);
}
for(int i=0;i<n;i++)
{
cout<<mp[i]<<endl;
}
system("pause");
return 0;
}
树状数组基础版—学习2 二维模板
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include<cstdlib>
#include<map>
using namespace std;
const int maxn=1030;
long long tree[maxn][maxn];
int n;
int lowbit(int i)
{
return i &-i;
}
void updata(int i,int k,long long val)//k就是j只是为了循环，中间变量。
{
while(i<=n)
{
int j=k;
while(j<=n)
{
tree[i][j]+=val;//先对x积再对y积
j+=lowbit(j);
}
i+=lowbit(i);
}
}
long long get_sum(int i,int k)
{
long long sum=0;
while(i>0)
{
int j=k;
while(j>0)
{
sum+=tree[i][j];
j-=lowbit(j);
}
i-=lowbit(i);
}
return sum;
}
int main()
{
int cz;
while(cin>>cz)
{
switch(cz)
{
case 0:
{
cin>>n;
memset(tree, 0, sizeof(tree));
break;
}
case 1:
{
int x,y;
long long val;
cin>>x>>y>>val;
updata(x+1,y+1,val);
break;
}
case 2:
{
int l,b,r,t;
long long sum=0;
cin>>l>>b>>r>>t;
//按前缀和的那种矩阵方法来即可。
//因为题目是从0开始，但lowbit(0)没有意义，所以我们把整个直角坐标系统一移动了一位，
sum+=get_sum(r+1,t+1);
sum-=get_sum(l,t+1);
sum-=get_sum(r+1,b);
sum+=get_sum(l,b);
//先x后y 和先y后x又关系吗？---有，根据你的更新数据函数，我们都是先积x再积y；所以固定(y,x);
//x再外头，所以x先积、
// sum+=get_sum(t+1,r+1);
// sum-=get_sum(t+1,l);
// sum-=get_sum(b,r+1);
// sum+=get_sum(l,r);
cout<<sum<<endl;
break;
}
case 3:
{
break;
}
}
}
system("pause");
return 0;
}
费马小定理—逆元。
其实就是a的-1次等于a的mod-2次。因为他们同余，所以可以直接替换。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
const int maxn= 45100;
using namespace std;
const int MOD= 9973;
long long ksm(long long a,long long k)
{
long long ans=1;
while(k)
{
if(k&1) ans=ans*a%MOD;
a=a*a%MOD;
k>>=1;
}
return ans%MOD;
}
int main()
{
int t;
cin>>t;
long long n,b;
while(t--)
{
cin>>n;
cin>>b;
cout<<(n*ksm(b,MOD-2)%MOD)%MOD<<endl;
}
}
尺取法精简模板
3步：
1.判断r如何退出。【一般为2个。超过总长度，和满足条件】--------------r<n&&count<cnt
2.如果是因为满足条件退出的，那我们就继续执行。-------------------- if(count<cnt) break;
3.让我们的l跟上。-----------------------------------------------l++
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
using namespace std;
const int maxn=2000001+10;
//第一题
int p[maxn];
set<int> q;
map<int,int>mp;
int cnt=0;
int main()
{
int n;
cin>>n;
cnt=0;
for(int i=0;i<n;i++)
{
scanf("%d",&p[i]);
q.insert(p[i]);//统计个数用的。
//if(mp[p[i]]==0) cnt++,mp[p[i]]++; //不要这样用了。
}
cnt=q.size();
int r=0,l=0;
int count=0;
int ans=99999999;
while(1)//相当于l
{
while(r<n&&count<cnt)//保证两个东西：1.不超过总长，2.还未达到指定要求。r一直更新。
{
if(mp[p[r]]==0) count++;
mp[p[r]]++;
r++;
//熟练后直接： if(mp[p[r++]]++==0) cout++;
}
if(count<cnt) break;//退出条件。
ans=min(ans,r-l);
mp[p[l]]--;
if(mp[p[l]]==0) count--;
l++;
//熟练后直接： if(--mp[p[l++]]==0) cout--;
}
cout<<ans<<endl;
}
exgcd的使用
1.构造ax+by=c的形式（判断a是否大于0，否则变成倒追）
2.用exgcd得到一种解；
3.如果c%exgcd不等于（不是c/gcd不是整数）那么代表无解
4.其他解可以又a（x+kb）+b(y-ka)=c得出
5.最小的解就是 (x0*c/gcd mod b + b) mod b;
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<string>
using namespace std;
const int maxn=2000001+10;
long long x0,y0,tmp,g;
//猜测，g是gcd，tmp是交换变量，x0是转折点第一个值。y0,是另一个。
void exgcd(long long a,long long b)
{
if(!b){x0=1;g=a;return;}//确实，gcd这里就得到了。
exgcd(b,a%b);//-------------------------------这里还是普通的gcd
tmp=x0;x0=y0;y0=tmp-a/b*y0; //得到的值往上更新。
}
int main()
{
long long x,y,m,n,l;
cin>>x>>y>>m>>n>>l;
//在使用exgcd前，需要先把式子写成ax+by=c；的形式。
long long a=m-n,b=l,c=y-x;
if(m-n<0) a=-a,c=-c;
//构造出初始公式后，使用exgcd得到x的值。
exgcd(a,b);
if(c%g) puts("Impossible");//必须清楚条件之一。c/gcd为整数才有解。
else printf("%lld\n",(x0*c/g%(b/g)+b/g)%(b/g));//求最小非负整数解 x=(x*c/gcd(a,b)mod b+b)mod b
}
多重背包问题-----二进制优化代码实现
二刷：
{
合并的思想是什么？-----不熟
例1：
4->1+3 抽离出1，构成一个p[1]与w[1]
3->2+1 抽离出2，构成一个p[2]与w[2]
1->1 剩下1不够4，所以把剩下的构成一个p[3]与w[3];
}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
const int INF = 0x3f3f3f3f;
const int maxn=10000;
using namespace std;
int v;
int p[maxn],w[maxn],s[maxn];
int dp[maxn];
int main()
{
int m,n,t,k;//m是背包容器
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));//少了初始化
memset(w,0,sizeof(w));
memset(p,0,sizeof(p));
cin>>v>>k;
int a,b,c;
int len=1;
for(int i=1;i<=k;i++)
{
cin>>a>>b>>c;
int box=1;
//================================二进制优化开始=============================
while(box<=c)//少了一个等于
{
p[len]=a*box;
w[len++]=b*box;
c-=box;//核心1
box*=2;//核心2
}
if(c)
{
p[len]=a*c;
w[len++]=b*c;
}
//================================二进制优化结束=============================
}
//================================01背包。=============================
for(int i=1;i<=len;i++)
{
for(int j=v;j>=p[i];j--)
{
dp[j]=max(dp[j],dp[j-p[i]]+w[i]);
}
}
cout<<dp[v]<<endl;
}
return 0;
}
斯特林模板
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=10000;
using namespace std;
int dp[maxn][maxn];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=0;i<=n;i++)
{
dp[i][i]=1;//0个人分0个环的组合数有1种。
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j-1]+(i-1)*dp[i-1][j];
}
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
printf("%d ",dp[i][j]);
}
puts("");
}
}
return 0;
}
最长子序列O（n^2）算法
//优点：记忆方便。缺点：效率较低。只能得到最大子序列长度，无法求得该最大子序列长度是什么。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=30000+10;
using namespace std;
int p[maxn];
int dp[maxn];
int main()
{
int n;
while(cin>>n)
{
memset(dp,0,sizeof(dp));
memset(p,0,sizeof(p));
for(int i=0;i<n;i++)
{
cin>>p[i];
}
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(p[i]>p[j]) dp[i]=max(dp[j]+1,dp[i]);//只要我比前面的某个数大，我就在该数后面+1，然后判断是不是当前最大子序列
}
ans=max(dp[i],ans);//每个子序列完成后，都要维护是不是比我们的最大子序列(要输出的答案)要大，如果是，替换。
}
cout<<ans+1<<endl;
}
return 0;
}
最长子序列O（logN）算法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=30000+10;
using namespace std;
int p[maxn];
int dp[maxn];
//优点：滚动数组。 O（NlogN）
int main()
{
int n;
while(cin>>n)
{
memset(dp,INF,sizeof(dp));
memset(p,0,sizeof(p));
for(int i=0;i<n;i++) cin>>p[i];
for(int i=0;i<n;i++) *lower_bound(dp,dp+maxn,p[i])=p[i];
//upper_bound:更新第一个大于p[i]的数
//lower_bound:更新第一个大于等于p[i]的数
//for(int i=0;i<lower_bound(dp,dp+maxn,INF)-dp;i++) cout<<dp[i]<<endl;
cout<<lower_bound(dp,dp+maxn,INF)-dp<<endl;
}
return 0;
}
KMP简单应用
现在回来看这代码太老了。但是对于理解还是有帮助的。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=1000000+10;
using namespace std;
int t;
int n,m;
int s1[maxn],s2[maxn];
int ne[maxn];
//经典问题：在主串种找到第一次出现的完整字串的起始位置。
void getnext()
{
ne[0]=ne[1]=0;
int j;
for(int i=1;i<m;i++)//看字串
{
j=ne[i];//j有什么用？
//=============================开始指引-----------------------------------
while(j&&s2[i]!=s2[j]) //两种情况退出。1.next下标为0.2.或者找到对应的字符串位置。
{
//里面就是这么实现指引。
j=ne[j]; //j代表我的字串下标可能在哪里。
}
//退出后，看我是哪个方式退出的。 如果是找到对应字符串退出。哪我的next下标就是在此基础上加1。（
//这样下次比较就可以从这里开始）否则为0.（0代表我只能从最开始的地方开始）
//=============================完成指引-----------------------------------
if(s2[i]==s2[j])
{
ne[i+1]=j+1;//ne[j]+1;
}
else
{
ne[i+1]=0;
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(s2,0,sizeof(s2));
memset(s1,0,sizeof(s1));
memset(ne,0,sizeof(ne));
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&s1[i]);
for(int i=0;i<m;i++) scanf("%d",&s2[i]);
getnext();
//=============================开始比较-----------------------------------
//一个循环+next数组指引来搞定。
int i,j=0,flag=0;
for(i=0;i<n;i++)
{
while(j&&s1[i]!=s2[j])
{
j=ne[j];
}
if(s1[i]==s2[j])
{
j++;//指针跟着i一起前进。
}
//=============================退出条件判断-----------------------------------
if(j==m)
{
flag=1;
break;
}
//=============================退出条件判断-----------------------------------
}
//=============================比较结束-----------------------------------
if(flag)//输出
{
cout<<i-j+2<<endl;
}
else
{
cout<<-1<<endl;
}
}
return 0;
}
KMP next[i]的应用
//next数组的一种实际应用是：next[n] 表示前n个子串中，前next[n]个和后next[n]个是相等。------可用于得到字符串中子串的循环次数。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=1000100;
using namespace std;
int t;
int n,m;
char a[maxn],b[maxn];
int ne[maxn];
void getnext(char *arr,int len)
{
ne[0]=1,ne[1]=0;
int j=0;
for(int i=1;i<len;i++)
{
j=ne[i];
while(arr[j]!=arr[i]&&j)
{
j=ne[j];
}
if(arr[j]==arr[i])
{
ne[i+1]=j+1;//ne[++i]=++j;
}
else
{
ne[i+1]=0;
}
}
}
int main()
{
int n;
int time=1;
while(cin>>n,n)
{
getchar();
memset(ne,0,sizeof(ne));
for(int i=0;i<n;i++) scanf("%c",&a[i]);
getnext(a,n);
printf("Test case #%d\n",time++);
for(int i=1;i<=n;i++)
{
if(i%(i-ne[i])==0&&i/(i-ne[i])!=1)
{
cout<<i<<" "<<i/(i-ne[i])<<endl;
}
}
cout<<endl;
}
return 0;
}
next数组+KMP 模板—理解的基础上更清晰。
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+10;
//ar arr_c[maxn][maxn],arr_r[maxn][maxn];
int ne[maxn];
void getnext(string arr,int len)
{
int i=0,j=-1;
ne[0]=-1;
while(i<len)
{
if(j==-1||arr[i]==arr[j])
ne[++i]=++j;
else
j=ne[j];
}
}
string ans="";
string s;
// void KMP(string s1, string s2)//-----------------模板
// {
// int i=0,j=0;
// int len1=s1.size();
// int len2=s2.size();//如果不折，s2.size()在进行比较不认负数，贼恶心
// while(i<len1&&j<len2)
// {
// if(s1[i]==s2[j]) i++,j++;
// else j=ne[j];
// }
// }
//==================================结束后，可以返回是否匹配。 可以返回j代表从【0-j】是相同匹配的。
void KMP(string s1)
{
//memset(ne,0,sizeof(ne));
getnext(s1,s1.size());
int len1=ans.size(),len2=s1.size();
int i=0,j=0;
for(i=max(len1-len2,0);i<len1;i++)//因为是和总串比较后缀。如果字符串很长的话会炸，所以用这个方法来取后缀。
{
if(j==-1||ans[i]==s1[j])
{
j++;
}
else
{
j=ne[j];
i--;//注意：如果是for循环。这里没加会出问题。只有在相同的时候才会i++，j++
}
}
ans+=s1.substr(j);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s;
KMP(s);
}
cout<<ans<<endl;
system("pause");
return 0;
}
KMP二维数组-----模板题
1.先把行作为一个整体，求解next_row的数组.
2.通过数组转置后，再进行一次求解next_col的数组.此时，虽然求next的过程和上面完全一致，但因为我们转置过后，其实变成了把列变成了整体进行求解next。【可通过画图理解。】---比较巧妙。
3.求出next__row和next__col后，(row-next__row)和(col-next__col)相乘即是最小覆盖矩阵。（具体实现根据next的性质【前n个字符串中，前缀next[n]与后缀next[n]是一模一样的。】）
4.了解了二维数组传参的写法。
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 20000+10;
char arr_c[maxn][maxn],arr_r[maxn][maxn];
int ne_c[maxn],ne_r[maxn];
void getnext(char arr[][maxn],int len,int ne[])//重点了解哦。二维数组的传参是这样传的 arr[][maxn].---前面可以没有，后面必须有。----地址的话，再问问别人有什么方法。
{
int i=0,j=-1;
ne[0]=-1;
while(i<len){//相当于for循环。
if(strcmp(arr[i],arr[j])==0||j==-1){//相当于那里的判断。
ne[++i]=++j;
}else{
j=ne[j];
}
}
}
int main()
{
int row,col;
while(cin>>row>>col)
{
for(int i=0;i<row;i++)
{
cin>>arr_r[i];
}
getnext(arr_r,row,ne_r);//先是一行一行比较。
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
arr_c[j][i]=arr_r[i][j];//二维数组倒置。
}
}
getnext(arr_c,col,ne_c);//后是一列一列比较
cout<<(row-ne_r[row])*(col-ne_c[col])<<endl;//输出。
}
return 0;
}
矩阵快速幂----模板
具体步骤就是：写个快速幂。然后把原先的数变成矩阵（结构体实现），乘法重定义一下。即可。—假设你已经掌握了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=102;
const int MOD=1e9+7;
struct node
{
long long room[maxn][maxn];
}a,ans;
long long n,k;
node operator*(const node &a,const node &b)
{
node box;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
box.room[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
box.room[i][j]+=a.room[i][k]*b.room[k][j]%MOD;
box.room[i][j]%=MOD;
}
}
}
return box;
}
node ksm(node a,long long k)
{
node ans;
for(int i=1;i<=n;i++) ans.room[i][i]=1;
//===================单位矩阵---类似int ans=0===============
while(k)
{
if(k&1) ans=ans*a;
a=a*a;
k>>=1;
}
return ans;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a.room[i][j];
}
}
ans=ksm(a,k);
//puts("===================");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<ans.room[i][j]<<" ";
//j==1?cout<<ans.room[i][j]:cout<<" "<<ans.room[i][j];
}
puts("");
}
//system("pause");
return 0;
}
矩阵乘法优化，将O(n)的递归降到O(logN)
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int maxn=3+100;
const int MOD=10000;
typedef long long ll;
/*
矩阵乘法优化。
1.学会矩阵乘法。(关系是怎么样的。)
2.学会如何去构造。
他的意义是：将O(N)的递归变成O(logN)---快速幂实现。;
***
学习矩阵快速幂。fibo
总体思路：
用结构体构造矩阵，重定义乘法。
快速幂。
将构造好的矩阵赋初值。
*/
struct node
{
long long room[3][3];
node()//构造函数，初始矩阵。相当于1.
{
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(i==j) room[i][j]=1;else room[i][j]=0;
}
}
}
}f;
node operator*(const node &a,const node &b)
{
node C;//这个初始化都为0.是为了保存A*B的值，相当于累加前，sum=0;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
C.room[i][j]=0;
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
C.room[i][j]+=a.room[i][k]*b.room[k][j];
C.room[i][j]%=MOD;
}
}
}
return C;
}
node ksm(node a,long long k)
{
node ans;
while(k)
{
if(k&1) ans=ans*a;
a=a*a;
k>>=1;
}
return ans;
}
int main()
{
ll n;
while(cin>>n,n>=0)
{
node ans;
f.room[0][0]=1;f.room[0][1]=1;f.room[1][0]=1;f.room[1][1]=0;
ans=ksm(f,n);
cout<<ans.room[0][1]%MOD<<endl;
}
//system("pause");
return 0;
}
[HTML_REMOVED]头文件 stringstream 的用法
string s;
getline(cin,s);
stringstream str(s);
while(str>>s)
{
cout<<s<<endl;
}
字典序—最基础模板。求前缀个数。
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<sstream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 2e6+10;
const int MOD=10000;
int tot;//导航索引
int m,n;
int trie[maxn][30];//trie[i][j]表示节点i的第j个儿子的节点编号。 int类型？----其实char也行，只是我们把a变成了编号0.
int sum[maxn];//与本题有关，记录这个节点访问过的次数。
char s[maxn];
void updata(char *str)
{
int len=strlen(str);//----------------------------------想都不想就打上的。
int root=0;//----------------------------------想都不想就打上的。
for(int i=0;i<len;i++)
{
int id=str[i]-'a';//id 干什么用？----答：其实就是'a'，只是用数字的形式表达。
if(!trie[root][id]) trie[root][id]=++tot;//意思：如果第一次出现，那做个标记，下次来了，可以知道方向。
sum[trie[root][id]]++;//记录节点访问次数
root=trie[root][id]; //能实现每次向下扩展。 类似与导航。确定下一步的方向
}
}
int find(char *str)
{
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++)
{
int id=str[i]-'a';
if(!trie[root][id]) return 0;//以XX为前缀的个数为0个。
root=trie[root][id];//跟着导航走。
}
return sum[root];//返回当前字符串结尾节点的访问次数，也就是作为前缀出现的次数。
}
int main()
{
tot=0;
while(gets(s))
{
if(!strlen(s)) break;
updata(s);//维护字典树。
}
memset(s,0,sizeof(s));
while(~scanf("%s",s))
{
printf("%d\n",find(s));
}
return 0;
}
马拉车—模板
专门来解决大数据的回文字符串。主要还是依靠中心扩散法。
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=220000+10;
const int INF =0x3f3f3f3f;
char str[maxn];
char str1[maxn];
int k=0;
int len=0;
void getstr()//将abab转换成&#a#b#a#b#'\0'
{
k=0;
len=strlen(str);//str的长度。
str1[k++]='&';
for(int i=0;i<len;i++)
{
str1[k++]='#';
str1[k++]=str[i];
}
str1[k++]='#';
len=k;//str1的长度。
str1[k]='\0';
}
int manacher()
{
//第一步；
int mx=0,id,ma=-1;
int p[maxn];//以id为中心的最大半径。
for(int i=1;i<len;i++)//i==1的原因是：str1[0]是&---防止越界用的。
{
if(mx>i) p[i]=min(p[2*id-i],mx-i);else p[i]=1;//如果i在mx范围里。那么一般都是看i的镜像，多大就多大。
//但如果i的镜像半径很大，但是i到mx的距离很小，那么我们的最大半径也只能是i到mx的距离。
//p[i]=1类似半径为0.他本身。 而不写0的原因是str1[0]是&,如果p[i]=0; mx=i+p[i];所确定的mx就会小一个位置。
while(str1[i+p[i]]==str1[i-p[i]]) p[i]++;//每次操作更新p，扩展到最大半径范围。
if(i+p[i]>mx)//如果上面扩展完的半径，比mx的半径要大，则更新。
{
mx=i+p[i];
id=i;//很巧妙的在于，你这里刚确定新的中心，你后面i马上就用了。
ma=max(ma,p[i]);// 与本题有关。因为，我们很多操作是在mx半径里，所以无论如何，都不可大于ma的长度。
//只有在突破ma的边界的时候，才有可能是最大长度。所以我们只要在突破mx的时候比较一下最大值即可。
}
}
return ma-1;
}
int main()
{
while(~scanf("%s",str))
{
getstr();
int len=manacher();
cout<<len<<endl;
}
return 0;
}
线段树了解
线段树 存储的是一个区间。我们是要在线段上找到我们想要的答案。
可以维护修改 以及查询区间上的最值，求和。
任意一个结点k来说，它所在此二叉树的log2（k） 层，则此层共有2log2(k)个结点，同样对于k的左子树那层来说有2log2(k)+1个结点，则结点k和左子树间隔了2*2log2(k)-k + 2*(k-2log2(k))个结点，然后这就很简单就得到k+2*2log2(k)-k + 2*(k-2log2(k)) = 2*k的关系了吧，右子树也就等于左子树结点+1
建树的思路：
3种。
1.如果是叶节点。停止。
2.否则分一个为左子树，分一个右子树。
3.其中的结点：左是u*2，右是u*2+1,区间范围变更为：左【l，m】，右【m+1，r】.其中m是中间值。（l+r）/2
当点更新的思路:
1.如果是叶节点。更新。
2.否则进行选择，分一个为左子树，分一个为右子树。并且每经过的结点都要更新他们的值。
区间查询的思路:
1.一直往下搜。
如果是满足区间，返回（该区间最大值）。
2.否则进行选择，分一个为左子树，分一个为右子树。
查询左和中所包含的区间是否有满足，如果有继续深搜，将放回的结果比较最大那个值
查询中和右所包含的区间是否有满足，如果有继续深搜，将放回的结果比较最大那个值
dijkstra快速版
二刷:
{
打印路径怎么打？
总结思路：加一个pre数组。再每一次执行扩散的时候，他们的目标赋值为u。输出时，使用递归。递归到起点再回溯输出。
疑问：pre不会覆盖之前的路径吗？
答：不会，因为前面的if(vis[u.id]) continue;和if(vis[e[i].to]) continue;我们的最小点不会指向我们那些已经确定的值。所以pre也就不会被覆盖。
dijkstra的思路是什么？
原始思路：首先可以是邻接矩阵、邻接表、链式向前星保存关系。然后将起点放入队列。出队，并把与他关联的点找出来进行比较出最小值。放入ans表。入队。重复操作。直到全部更新结束。
注意1：这里我们用优先队列来简化我们找最小值的过程。
注意2：用vis可以剪枝已经是最小值的ans表。
思路总结：首先可以是邻接矩阵、邻接表、链式向前星保存关系。然后将起点放入队列。出队，并把与他关联的点放入优先队列得到最小值。再根据这个最小的值再一次进行扩散，入队。重复操作，直到队列为空。
}
1.把起点s放到集合A，然后把S的邻居放到B
2.从B中找出最短的结点u，使他到S的距离最短。
3.同理把u的邻居也放到B里，且他到S的距离总是满足dis（s,u）+dis(u,v)最短
4.一直重复2 3过程直到B为空。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f;
//========================第一步构造邻接表===============================
struct edge
{
int to,next,w;
edge(int a,int b,int c){next=a,to=b,w=c;}//对于邻接表而言，next没用。next用于链式向前星。
};
vector<edge> e[maxn];//相当于二维的。
//========================第二步构造优先队列===============================
struct node
{
int id,dis;// 节点。 dis是结点到起点的距离。
node(int b,int c){id=b,dis=c;}//
friend bool operator<(const node &a,const node &b){return a.dis>b.dis;}//变成了优先队列。 ??为什么是>???
};
//=======================第三步，写需要的变量===============================
int n,m;
int dis[105] ;//初始化
bool vis[105];
int pre[maxn];
//=======================第五步，===============================
void dijkstra(int s)
{
memset(vis,false,sizeof(vis));//点的标志，代表是否已经确定。
memset(dis,INF,sizeof(dis));//dis那个数组
dis[s]=0;//到自己的距离为0.
priority_queue<node> q;
q.push(node(s,dis[s]));
while(!q.empty())
{
node u=q.top();//我们拿到的总是这个队列中最小的那个，（快就快在这里。）
q.pop();
if(vis[u.id]) continue;//如果该点已经确定有最小值了，那么舍弃。
vis[u.id]=true;//下面的操作完成后，结点u的最小值就会被确定下来。 加入到所谓的A
for(int i=0;i<e[u.id].size();i++)//遍历结点u的所有邻居 加入到所谓的B
{
edge y=e[u.id][i];
if(vis[y.to]) continue;
if(dis[y.to]>y.w+u.dis) dis[y.to]=y.w+u.dis;
q.push(node(y.to,dis[y.to]));
pre[y.to]=u.id;//对面是通过我u这个节点去的。
}
}
}
void print(int s,int t)//起点，终点
{
if(s==t) {printf("%d",s);return;}
print(s,pre[t]);
printf("%d",t);
}
//=======================第四步，===============================
int main()
{
int i,j;
int a, b, c;
while (cin >> n >> m)
{
if (n == 0 && m == 0)break;
for(i=0;i<n;i++) e[i].clear();//初始化清空。
for (i = 0; i < m; i++)
{
cin >> a >> b >> c;
e[a].push_back(edge(a,b,c));//存入操作
e[b].push_back(edge(b,a,c));
}
dijkstra(1);//我习惯于传我们的起点位置。
cout << dis[n] << endl;
//for(int i=1;i<=n;i++) cout<<dis[i]<<" "<<endl;
//for(int i=1;i<=n;i++) cout<<pre[i]<<" "<<endl;
print(1,n);
}
return 0;
}
/*
对于路径的打印。 和dijstra的流程模拟还不太懂。
用邻接表存图和查找邻居。
在集合B中找距离起点最短的结点。---集合B就队列。
*/
链式向前星+代码
已二刷：
{
一对于图论必须要有的：结构体edge+head+链式向前星。
输入完毕即可直接dijkstra
dijkstra重在贪心策略。寻找当前最短路径(优先队列非常符合)，并且做标记。
在每次进入优先队列的时候，用pre记录它是由谁来到这个位置的。
1.结构体
2.优先队列—(涉及到如何建立！)
3.链式向前星–(涉及到如何建立！)
4.初始化dis，vis，pre，head，cnt等；
5.输入–调用dijkstra
重点6，优先队列取当前点到另一点的最短路。并标记。注意特判“回边”。
7.打印，用递归的方式。
为什么优先队列自定义排序从小到大要>而不是<
答：因为优先队列是先进先出。所以如果<，则队列是12345，最先出列的是5。但如果是>,则54321,最先出列的是1.
}
一刷
与上面的邻接表类似。只是链式向前星能够很好的降低空间冗余。
注意：
构造的写法。
//一开始头结点都是-1
void add(int u,int v,int w)//相当于链接表，不断更新头结点。旧的头结点向下移。
{
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];//我链式u 的下一个指向就是当前的头结点,所以是head[u]；
head[u]=cnt++;//更新当前的cnt是链式u的头节点。
}
理解head[]的意义，next的意义。
理解 for(int i=head[u.id];i!=-1;i=e[i].next)的意义。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f;
//========================第一步构造邻接表===============================
struct edge
{
int to,next,w;
//edge(int a,int b,int c){next=a,to=b,w=c;}//对于邻接表而言，next没用。next用于链式向前星。
}e[maxn];//只用一维来存。
//========================第二步构造优先队列===============================
struct node
{
int id,dis;// 节点。 dis是结点到起点的距离。
node(int b,int c){id=b,dis=c;}//
friend bool operator<(const node &a,const node &b){return a.dis>b.dis;}//变成了优先队列。 ??为什么是>???
};
//=======================第三步，写需要的变量===============================
int n,m;
int dis[105] ;//初始化
bool vis[105];
int pre[maxn];
int head[maxn];
int cnt=0;
//=======================第五步，===============================
void add(int u,int v,int w)
{
e[cnt].w=w;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
//puts("=1=");
}
void dijkstra(int s)
{
cnt=0;
memset(vis,false,sizeof(vis));//点的标志，代表是否已经确定。
memset(dis,INF,sizeof(dis));//dis那个数组
dis[s]=0;//到自己的距离为0.
priority_queue<node> q;
q.push(node(s,dis[s]));
while(!q.empty())
{
node u=q.top();//我们拿到的总是这个队列中最小的那个，（快就快在这里。） -----为什么用优先队列就是这个原因。
q.pop();
if(vis[u.id]) continue;//如果该点已经确定有最小值了，那么舍弃。
vis[u.id]=true;//下面的操作完成后，结点u的最小值就会被确定下来。 加入到所谓的A
for(int i=head[u.id];i!=-1;i=e[i].next)//遍历结点u的所有邻居 加入到所谓的B
{
if(vis[e[i].to]) continue;
if(dis[e[i].to]>e[i].w+u.dis) dis[e[i].to]=e[i].w+u.dis;//如果从u到这里的距离比当前的表里的距离还小，替换成小的那个。
q.push(node(e[i].to,dis[e[i].to]));
pre[e[i].to]=u.id;//记录我是通过u到v的所以是pre[e[i].to]=u.id。
//也就是说用pre记录我是由谁得到的。
}
}
}
void print(int s,int t)//起点，终点
{
if(s==t) {printf("%d",s);return;}
print(s,pre[t]);
printf("%d",t);
}
//=======================第四步，===============================
int main()
{
int i,j;
int a, b, c;
while (cin >> n >> m)
{
if (n == 0 && m == 0)break;
//for(i=0;i<n;i++) e[i].clear();//初始化清空。
memset(e,0,sizeof(e));
memset(head,-1,sizeof(head));
for (i = 0; i < m; i++)
{
cin >> a >> b >> c;
add(a,b,c);
add(b,a,c);
}
dijkstra(1);//我习惯于传我们的起点位置。
cout << dis[n] << endl;
print(1,n);
}
return 0;
}
/*
对于路径的打印。 和dijstra的流程模拟还不太懂。
用邻接表存图和查找邻居。
在集合B中找距离起点最短的结点。---集合B就队列。
3 2
1 2 3
2 3 6
3 3
1 2 3
2 3 6
1 3 2
*/
LCA模板
/LCA问题，需要建树。要个链式向前星->带head数组。要个深度数组d。要个跳跃索引数组p/
dfs初始化个节点的深度d，以及到达的位置p
分两步：
先确定a在上面，b在下面。然后让b同步到a的深度。
ifa==b 返回a的结点（标识），否则a和b一起向上跳，在要a==b的时候停止，输出a的父节点。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=1000000+10;
using namespace std;
int t;
struct edge
{
int v,next;
}e[maxn];
int head[maxn],cnt=0;
int d[maxn],p[maxn][21];
int n,m,s;
void add(int u,int v)
{
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u,int fa)
{
d[u]=d[fa]+1;
p[u][0]=fa;
for(int i=1;(1<<i)<=d[u];i++) p[u][i]=p[p[u][i-1]][i-1];//注意这里i从1开始。和树状数组一样，i=0没有意义
for(int i=head[u];i!=-1;i=e[i].next) if(e[i].v!=fa) dfs(e[i].v,u);
}
/*
*/
int LCA(int a,int b)//结点a，结点b
{
if(d[a]>d[b]) swap(a,b);//始终保持a要比a浅（b要深）。
for(int i=20;i>=0;i--)
{
if(d[a]<=d[b]-(1<<i)) b=p[b][i];//如果b能跳，就让b跳过去。
//注意：要加是<=不是< 只有<=才能保证循环结束后，他们在同一层。
}
//下一步就是 让a和b一起向上跳。
if(a==b) return a;//特判：如果b刚好就和a重合了。直接输出a的结点。
else{
int i;
for(i=20;i>=0;i--)
{
if(p[a][i]==p[b][i]) continue;else a=p[a][i],b=p[b][i];// 让a和b一起向上跳。
}
return p[a][0];//打印a的向上一步的节点（父节点）
}
}
int main()
{
cin>>n>>m>>s;
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++)//i是1的原因：题目保证是树，所以n个节点，至少有n-1个边。才能建树。（才能叫树）
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
dfs(s,0);//通过dfs来初始深度d和位置索引p
for(int j=0;j<m;j++)
{
int a,b;
cin>>a>>b;
cout<<LCA(a,b)<<endl;
}
return 0;
}
母函数—普通版—砝码问题（组合问题）
#include<iostream>
#include<stdio.h>
#include<set>
#include<map>
#include<string.h>
#include<string>
using namespace std;
const int maxn=1e4+10;
typedef long long ll;
ll temp[maxn],ans[maxn]; //都是系数。
int main()
{
int t,s;
ll x;//x代表个数字母。
cin>>t;
while(t--)
{
memset(ans,0,sizeof(ans));
ans[0]=1;//---很重要，一开始价值为0的个数为一个。为后面的累加做铺垫，否则就一直+0；
for(int i=1;i<=26;i++)
{
cin>>x;
for(int j=0;j<=50;j++)//大多项式指数为j的情况。
{
//k<=x;代表最多可以用x个。如果是k<x则只能用x-1个
for(int k=0;k<=x&&k*i+j<=50;k++)//构造的小多项式，开始相乘。k*i+j是模拟小多项式*大多项式指数
{
temp[k*i+j]+=ans[j];
}
}
for(int j=0;j<=50;j++)
{
ans[j]=temp[j],temp[j]=0;
}
}
ll sum=0;
for(int i=1;i<=50;i++)//根据母函数定义：指数代表组成价值大小，系数代表组成价值大小的个数。
{
sum+=ans[i];//所以把满足价值大小的个数的系数相加即可。
}
cout<<sum<<endl;
}
return 0;
}
母函数—指数版—排列问题
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=300+10;
const int INF =0x3f3f3f;
int n,m;
double temp[maxn],ans[maxn],fact[maxn];
//int num[maxn];
int main()
{
int x;
fact[0]=1;
for(int i=1;i<maxn;i++)
{
fact[i]=fact[i-1]*i;
}
while(cin>>n>>m)//n个物品，选m件的组合数。
{
memset(ans,0,sizeof(ans));
ans[0]=1;
for(int i=0;i<n;i++)
{
cin>>x;
for(int j=0;j<=m;j++)//0?1 0.因为大多项式中，也有可能为m为0的情况，即x的0次。
{
for(int k=0;k<=x&&k+j<=m;k++)//这里为什么是k+j 而不是和普通版的一样是k*i+j？
{
temp[k+j]+=ans[j]/fact[k];//因为你的小多项式里的m就是1，2，3，4，5,...,k个，两个构造函数的指数不一样。
}
}
for(int j=0;j<=m;j++)
{
ans[j]=temp[j],temp[j]=0;
}
}
printf("%.0lf\n",ans[m]*fact[m]);//乘fact[m]的原因是：对于构造函数我们把x的m次/m的阶乘看成一个整体，求这个整体的系数，但在程序了，我们把这个阶乘也当作系数算进去了，所以为了还原系数，就只需要在乘一下阶乘m即可。
}
return 0;
}
莫队—模板题
注意：sort(mo+1,mo+m+1);
是对我们的区间进行一个分块排序。如果像2021/7/28今天这样写sort(a+1,a+m+1);-虽然样例过了（这就很致命），但你就是错的。（写的代码功亏一篑）
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<set>
#include<map>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e5+10;
int cnt[maxn];//x出现的次数。
int ans[maxn];
int n,m,k;
int le,ri,block,sum=0;
int a[maxn];//存放序列。
//===========================是个离线算法 ==========================
struct node
{
int l;
int r;
int id;
friend bool operator<(const node &a,const node &b)//分块的思想用在了排序里。 --------很重要的思想、
{
if(a.l/block==b.l/block) return a.r<b.r;
return a.l/block<b.l/block;
}
} mo[maxn];//确实用结构体更好一些，因为区间是有关联的。
void add(int x)
{
cnt[x]++;//把当前位置上的数字x出现次数+1；
sum+=2*cnt[x]-1;//他是化简过的。 原公式：sum=sum-cnt[x-1]^2+cnt[x]^2.
//因为cnt[x-1]=cnt[x]-1;所以cnt[x-1]^2==cnt[x]^2-2cnt[x]+1.代入原式
//sum=sum-(cnt[x]^2-2cnt[x]+1)+cnt[x]^2=sum+2cnt[x]-1;
}
void remove(int x)
{
cnt[x]--;
sum-=2*cnt[x]+1;//同理。
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);//莫队也从1开始，
for(int i=1;i<=m;i++)
{
scanf("%d %d",&mo[i].l,&mo[i].r);
mo[i].id=i; //因为排序后，输出顺序会打乱，所以，id就能确定输出答案的位置。
}
block=sqrt(n);//maxn其实也可以。说不定还更好
sort(mo+1,mo+m+1);
le=1;ri=1;
add(a[1]);//指针一开始就都指向第一位。那么他代表的值，我们也不能落下
for(int i=1;i<=m;i++)
{
while(le<mo[i].l) remove(a[le++]);//先删了再跳。
while(le>mo[i].l) add(a[--le]);//先跳了再加
while(ri<mo[i].r) add(a[++ri]);
while(ri>mo[i].r) remove(a[ri--]);
//for(int j=1;j<=k;j++) ans[mo[i].id]+=cnt[j]*cnt[j];----会超时。以后操作都在add和remove实时修改。
ans[mo[i].id]=sum;
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
//理解1：那么我们Left-1，并且把Left位置上的数字出现次数+1.
//理解2：我们将Left指针逐步更新成新的L
//我还没分块。 分块用再了排序里。
离散化使用方法
简单一点：三步 1：我们需要一个辅组数组b。2.将辅助数组b去重（这里需要排序）3.用二分的办法（lower_bound）赋值到a，此时a的离散化完成。
其实就是用一个辅助的数组把你要离散的所有数据存下来。
然后排序，排序是为了后面的二分。
去重，因为我们要保证相同的元素离散化后数字相同。
再用二分把离散化后的数字放回原数组。
注意事项：
1.去重并不是把数组中的元素删去，而是重复的部分元素在数组末尾，去重之后数组的大小要减一
2.二分的时候，注意二分的区间范围，一定是离散化后的区间
3.如果需要多个数组同时离散化，那就把这些数组中的数都用数组存下来
int a[maxn],b[maxn];
for(int i=1;i<=n;i++) scanf("%lld",&b[i]),a[i]=b[i];
sort(b+1,b+n+1);
int cnt= unique(b+1,b+n+1)-b-1;//离散化后的数组大小
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt_1+1,a[i])-b;//这是a[i]已经离散完成。
unique函数的使用：
删除操作要在动态数组里实现。
1，一定要先排序
2，返回的是“去重”后的尾地址；所以去重后的个数：cnt=unique(b,b+n)-b;
3.只是将重复的元素放置到末尾，总长度不变。
4.属于algorithm头文件。
5.如果真的删除也很容易。b.erase(unique(b,b+n),b.end);
强连通分量------korasaju算法
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=3e3+10;
const int INF =0x3f3f3f3f;
vector<int>G[maxn],rG[maxn];//需要正向图和反向图。
vector<int> s;//存储点的先后顺序。
int vis[maxn],sccno[maxn],cnt; //cnt记录强连通个数,sccno[i]是第i个点所树属的是scc vis[i]记录点i是否被访问过。
//sccno很重要，sccno[i]相同的数连起来，代表该子图的一个最大连通分量。
void dfs1(int u)//第一个dfs1就是配合，把s的顺序记录下来。
{
if(vis[u]) return ;
vis[u]=1;
for(int i=0;i<G[u].size();i++) dfs1(G[u][i]);
s.push_back(u);
}
void dfs2(int u)//第二个就是确定scc的所以强连通分量的线路。记录cnt个数。
{
if(sccno[u]) return ;
sccno[u]=cnt;
for(int i=0;i<rG[u].size();i++) dfs2(rG[u][i]);
}
void kosaraju(int n)//3个步骤，1.先初始化，2弄正图确定顺序，3弄反图确定scc个数。
{
cnt=0;
s.clear();
memset(sccno,0,sizeof(sccno));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) dfs1(i);//标记点的先后顺序。 1~n是编号。 为什么要for循环呢？ 因为可能路会断开。比如数据①
//顺序是从标记大的点开始到最小的点。记。
for(int i=0;i<n;i++) cout<<s[i]<<" ";
for(int i=n-1;i>=0;i--) if(!sccno[s[i]]) {cnt++,dfs2(s[i]);}
//表这个标记点还在（没有被删除）。那么他能连通的就是这个子图的最大强连通分量。
//i为n-1的原因是：我们的一个顺序标志是在s[0]的位置。
}
int main()
{
int n,m,u,v;
while(~scanf("%d %d",&n,&m),n+m)
{
for(int i=0;i<n;i++) G[i].clear(),rG[i].clear();//初始化
for(int i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
G[u].push_back(v);
rG[v].push_back(u);
}
kosaraju(n);//卡沙拉俊
cnt==1?puts("Yes"):puts("No");
}
return 0;
}
/*
数据一：
4 4
1 2
2 3
3 1
4 2
总结：
需要先构成一个正图和反图。
初始化。。。
直接第一个dfs1， 从1开始到n，递归到最底层后，逐渐累加，存放到s中。
直接第二个dfs2， 从s里最大的开始，顺序是从标记大的点开始到最小的点，递归完一条链，就是一个强连通分量。
在
*/
强连通—tarjan算法
#include<vector>
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cstring>
#include<algorithm>
using namespace std;
const int maxn=10005;
int cnt,low[maxn],num[maxn],sccno[maxn],dfn;//cnt是强连通图个数。
vector<int>G[maxn];
int stack[maxn],top;
void dfs(int u)
{
stack[top++]=u;//用数组模拟栈 ，把他们放入栈。
low[u]=num[u]=++dfn;
for(int i=0;i<G[u].size();++i)
{
int v=G[u][i];//u的对边。
if(!num[v])//如果u的对边还每被标记数字过。---也说明还每人联系到他。
{
dfs(v);
low[u]=min(low[v],low[u]);
}
else if(!sccno[v])// 处理回退边？???
{
low[u]=min(low[u],num[v]);
}
}
if(low[u]==num[u])//关键结点。---起始点。
{
cnt++;
while(1)
{
int v=stack[--top];
sccno[v]=cnt;
if(u==v) break;
}
}
}
void tarjan(int n)
{
cnt=top=dfn=0;//个数为0,栈指针在0位置。标志数字为0.
memset(sccno,0,sizeof(sccno));
memset(num,0,sizeof(num));
memset(low,0,sizeof(low));
for(int i=1;i<=n;i++) if(!num[i]) dfs(i);//这里的num是标记数字。 从1到n的，检查更新他们的标记数字。
}
int main()
{
int n,m,u,v;
while(scanf("%d %d",&n,&m),n+m)
{
for(int i=1;i<=n;i++) G[i].clear();
for(int i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
G[u].push_back(v);
}
tarjan(n);//G图有n个点。
cnt==1?puts("Yes"):puts("No");
}
return 0;
}
树状数组求逆序对
for(int i=1;i<=n;i++)
{
//求逆序对：就是求当前位置a[i]前面比a[i]大的个数。----在树状数组里想。
//明确这个box（A[i]）总是从小到大排序的。所以，getsum(a[i])就能求0~a[i]的个数，a[i]~n的个数就是逆序对，所以下面相加即可。
ans+=1ll*i-1-getsum(a[i]);//总个数(i-1,因为一开始是0个不是1个)-比a[i]小的个数，剩下的就是比a[i]大的个数、
cout<<getsum(n)<<" "<<getsum(a[i])<<endl;
updata(a[i],1);
}
二分图最大匹配—匈牙利算法
二刷
{
匈牙利二分代码很好理解。
1.首先两个for循环。一个是待匹配项，一个是匹配项。
2.对 待匹配项 逐一对匹配项进行遍历，两种情况：匹配项为0[还没有配对]那么直接配对。如果匹配项不为0[已被i配对]，你们递归，寻找是否可以为他寻找另一个匹配项。 use就是用于每个待匹配项的记录。line是是否有关系。
}
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+10;
const int INF =0x3f3f3f;
int n,m,k;
bool e[maxn][maxn];
bool use[maxn];//记录当前轮中是否选择
int boy[maxn];//男生i的搭档是 boy[i]
int find(int x)
{
for(int i=1;i<=n;i++)//逐一遍历男生。
{
if(e[x][i]&&!use[i])//use是用在冲突后，调剂用的。
{
use[i]=true;
if(boy[i]==0||find(boy[i]))
{
boy[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int x,y;//x是女，y是男
while(cin>>k,k)
{
cin>>m>>n;
memset(boy,0,sizeof(boy));
memset(e,false,sizeof(e));
for(int i=1;i<=k;i++)
{
cin>>x>>y;
line[x][y]=true;
}
int sum=0;
for(int i=1;i<=m;i++)//从女生里开始匹配。
{
memset(use,false,sizeof(use));
if(find(i)) sum++;
}
cout<<sum<<endl;
}
return 0;
}
/*
*/
快排模板
int a[1000001];
void mysort(int l,int r)
{
int mid=a[(l+r)/2];//找中间的数进行2分
int i=l,j=r;
while(i<=j)
{
while(a[i]>mid)
i++;//找左半部分大于中间数的
while(a[j]<mid)
j--;//找右半部分小于中间数的
if(i<=j)
{
swap(a[i],a[j]);//换位
i++;//左指针右移
j--;//右指针左移
}
}
if(l<j) mysort(l,j);
if(i<r) mysort(i,r);
}
优先队列默认从大到小，如何从小到大？----模板
#include<iostream>
#include<functional>
#include<queue>
using namespace std;
struct node
{
friend bool operator< (node n1, node n2)
{
return n1.priority > n2.priority;//即可改变排序方式。
}
node(int a,int b){priority=a,value=b;
}
int priority;//优先级排序标志
int value;//值。
};
int main()
{
const int len = 5;
int i;
int a[len] = {3,5,9,6,2};
//示例1
priority_queue<node> qi;
for(i = 0; i < len; i++)
qi.push(node(a[i],a[i]))//用构造函数赋值
for(i = 0; i < len; i++)
{
cout<<qi.top().value<<" ";
qi.pop();
}
cout<<endl;
}
二分图最大匹配—染色法
#include<iostream>
#include<functional>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int ,int> PII;
int m,n,x,y;
const int maxn=2000+10;
int color[maxn],boy[maxn];
bool line[maxn][maxn],use[maxn];
struct edge
{
int v,next;
}e[maxn*20];//边还是尽可能的大，在这里就一直卡RE
int head[maxn],cnt;
void add(int u,int v)
{
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
int find(int x)//---模板
{
for(int i=1;i<=n;i++)
{
if(line[x][i]&&!use[i])
{
use[i]=true;
if(boy[i]==0||find(boy[i]))
{
boy[i]=x; return 1;
}
}
}
return 0;
}
int bfs()//染色法 ---确定是否是二分图。
{
int u=1;
memset(color,0,sizeof(color));
queue<int>q;
q.push(u);//从第一个结点开始。
color[u]=1;
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(!color[v])
{
color[v]=color[u]*-1;
q.push(v);
}
else if(color[v]==color[u]) return 0;
}
}
return 1;
}
int main()
{
while(cin>>n>>m)//4个人，4个关系。
{
cnt=0;
memset(head,-1,sizeof(head));
memset(line,0,sizeof(line));
memset(boy,0,sizeof(boy));
for(int i=0;i<m;i++)
{
cin>>x>>y;
add(x,y);
//add(y,x);
line[x][y]=true;
}
if(!bfs())
{
puts("No");
}
else
{
//如果是二分图，那么就直接套二分图最大匹配模板
int sum=0;
for(int i=1;i<=n;i++)
{
memset(use,false,sizeof(use));//要注意的。每次都要重置的原因就是use是用来对出现重复是进行递归调换的。
if(find(i)) sum++;
}
cout<<sum<<endl;
}
}
return 0;
}
博弈图模拟
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=4e5+10;
using namespace std;
int m,n;
string s1;
string s2;
int a[maxn],last[maxn];
bool vis[maxn],win[maxn];
vector<int> G[256];
int dfs(int i)//模拟了一遍博弈图。
{
if(vis[a[i]]) return win[a[i]];//记忆化搜索思想。真假，真假的，最容易记忆化搜索。
vis[a[i]]=1;
bool ok=false;
for(int j=0;j<G[a[i]].size();j++)
{
int v=G[a[i]][j];//a[i]是我们当前查询的这个点，我们遍历他所可以经过的所有数字。
if(last[v]>i)//怎么样退出？
{
ok|=!dfs(last[v]);//实现P\n的核心。 ------ |是or运算。|= 类似+=。
//确实or运算完美实现。 只要有个真，那么我就能到真，只有全为0，我才会是0. 牛逼。
}
}
win[a[i]]=ok;
return ok;
}
int main()
{
for(int i=0;i<256;i++)
{
for(int j=0;j<8;j++)
{
int v=i^(1<<j);//本程序的一个学习重点。
G[i].push_back(v);//博弈图就有了。
}
}
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],last[a[i]]=i;
for(int i=0;i<m;i++)
{
int op,k;
cin>>op>>k;
if(op==1)
{
a[++n]=k;
last[a[n]]=n;//这里wa了一发 ：last[a[n]]=k
}
else
{
if(last[a[k]]!=k)//如果不在最后面，那根据性质，一定都是必胜态。 wa:last[k]!=k
{
cout<<"Grammy\n";
}
else//否则，根据博弈图，模拟一遍。
{
memset(vis,false,sizeof(vis));
memset(win,false,sizeof(win));
bool ok=dfs(k);
cout<<(ok?"Grammy\n":"Alice\n");
}
}
}
return 0;
}
RMQ模板----建议从1开始–因为：算长度，从1开始比较好理解，不会出错。
dp[i][j-1] 左半部分
dp[i+(1<<j-1)][j-1] 右半部分 这里我已经不止一次写成i+(1<<j），分析，改正。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=1e6+10;
using namespace std;
int n,m,l,r;
int Log[maxn]; int a[maxn];int dp[maxn][20];
void getLog()//不容易超时。
{
Log[1]=0;
for(int i=2;i<=maxn;i++) Log[i]=Log[i/2]+1;
}
void init()
{
//for(int i=1;i<=n;i++) dp[i][0]=a[i];//本该要的，这里省了。
for(int j=1;(1<<j)<=n;j++)//这里反了一下，比较特殊。把每个固定区间求出最大值,限制条件是，防止2^(1<<j)长度大于n。
{
for(int i=1;i+(1<<j)-1<=n;i++)//理解：i+(1<<j)-1<=n 第 i 位置加上区间长度是否大于总长度n了。
{
dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]); //否则，我总可以把他拆成左部分和右部分。
//而左部分的长度，我们已经得到了。---（这就表明了为什么j（跳的长度）为外循环。）
}
}
}
int RMQ(int l,int r)
{
int k=Log[r-l+1];//这个其实很好理解，因为我们的dp不是简单的[l][r]，而是[l][j的长度到r],所以我们的k其实就是求j。指数转对数罢了。
return max(dp[l][k],dp[r-(1<<k)+1][k]);//在线的。因为我们给的区间不一定 刚好覆盖(看k就知道)，
//所以，我们就分 从开始l~l+k,和从r-k+1~r; k代表长度，可以证明，这样一定是满足条件的。
//return dp[l][k];//这样做不行，是离线的。 区间一定是左部分和右部分的长度是刚好覆盖的。
}
int main()
{
int t;
cin>>t;
getLog();
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i][0]=a[i];//从1开始吧
cin>>m;
for(int i=0;i<m;i++)
{
init();
cin>>l>>r;
cout<<RMQ(l,r)<<endl;
}
}
return 0;
}
/*
理解：i+(1<<j)-1<=n 第 i 位置加上区间长度是否大于总长度n了。
//整个区间分两步。第一步：i~i+2^(j-1)-1(是长度),第二步是i+2^(j-1)~i+2^j-1;(是长度)
在dp里，我们用另一种表达形式，我们的j-1就是上面两步的总长度除2，一个从i开始走2^ (j-1)步，再从i+ 2^ (j-1)开始，走2^ (j-1)步。
与上面的说法完全等价
}
*/
回顾RMQ：
从题目上看，区间查询 RMQ
我们要的得到区间gcd 也可以用RMQ实现。
RMQ查询需要用到Log函数。所以我们需要构造一个Log函数。
st表可以想象成阶层
那么我们初始化底层，(其实最底层就是a[i]照搬。)然后一步一步合并。
合并：
{
外层定义的是步数，内层定义的是所站的位置。所以外层是j 内层是i。
j:(1<<j)<=n 是防止一跳就过整个区间了。
i：i+(1<<j)-1<=n 就是合并的核心。总长【i,i+(1<<j)-1】。拿【i,i+(1<<j-1)-1】与【i+(1<<j-1)，i+(1<<j)-1】进行比较取值。
for(int i=1;…)这样写的原因就是枚举我i所站的位置，如果我i+(1<<j)-1<=n，那么，后面的i必然也会跳出界，所以我们就提前退出。因此这样写起到了优化剪枝的操作。
}
查询
{
由于所给的范围不一定正好符合我们st表。所以用k=Log[r-l+1];来进行巧妙转换。
保证了st[l][k]的范围与st[r-(1<<k)+1][k]的范围完全包含;
}
RMQ学习+二维数组传参用法
求区间内 最大值-最小值。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=1e6+10;
using namespace std;
int n,m,l,r;
int Q;
int Log[maxn],a[maxn],dp1[maxn][20],dp2[maxn][20];
void init(int dp[][20],int op)//这样竟然可以赋值。
{
for(int i=1;i<=n;i++) dp[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)//这里 i+(1<<j)-1
{
if (op==1) dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);//这里是核心,能独立想明白即可。
else dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
}
}
void getLog()
{
Log[1]=0;
for(int i=2;i<=maxn;i++) Log[i]=Log[i/2]+1;
}
int RMQ(int l,int r,int op)
{
int k=Log[r-l+1];
if(op==1) return max(dp1[l][k],dp1[r-(1<<k)+1][k]);
return min(dp2[l][k],dp2[r-(1<<k)+1][k]);
}
int main()
{
getLog();
cin>>n>>Q;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
init(dp1,1);
init(dp2,2);
for(int i=1;i<=Q;i++)
{
scanf("%d %d",&l,&r);
printf("%d\n",RMQ(l,r,1)-RMQ(l,r,2));
}
return 0;
}
/*
i+(1<<j-1)
学习与总结：
调用二维数组：可以这样。---把数组放外面，然后普通的传参。这样也可以修改。
dp的for循环的限定条件是：j跳的长度不能超过总长度n。 i的位置加上j的长度，不能超过总长度n。
j跳的长度是(1<<j);
*/
状态dp模板思考
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=1e6+10;
using namespace std;
int n,m,sta[65];//sta[i] 可行的方案数
long long dp[105][65][65];
int map[110];//用二进制存下第i行的地图，用十进制保存。
int judge(int x)
{
if((x&(x<<1))!=0||(x&(x<<2))!=0) return 0;//注意优先级。----是状态判断核心之一。---学会分析。
return 1;
}
int sum(int x)//计算状态x放置了多少个炮兵 ,---就是数1的个数。
{
int su=0;
x=sta[x];
for(int i=0;i<m;i++)
{
if(((1<<i)&x)!=0) su++;
}
return su;
}
int main()
{
memset(dp,0,sizeof(dp));
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)//要先这样存二进制吗？
{
char ch;
cin>>ch;
if(ch=='H') map[i]+=(1<<j);
}
}
//======================可以独立开来，求的是m行可行的方案数==================
int tot=0;
for(int i=0;i<(1<<m);i++)//相当于开始枚举所有情况的方案数了--很重要。
{
if(judge(i))//是不是可行方案。
{
tot++;
sta[tot]=i;
}
}
//cout<<tot<<endl;//发现，最多只有60方案。
//===============================================================================
//这里才开始用到map了，上面都是初始操作。
//dp[i][j][k]表示第i行状态为j，且第i-1行状态为k时最多可安放几个炮兵
for(int i=1;i<=tot;i++)//遍历这些方案
{
if((map[1]&sta[i])==0) dp[1][i][1]=sum(i);//(map[1]&&sta[i])==0 这个也很讲究。刚好就是可以把0变1的方案数：----核心之一，分析。
}
for(int i=2;i<=n;i++)//-------从上到下。
{
for(int j=1;j<=tot;j++)// ----看第i-2行，第j个状态
{
if((sta[j]&map[i-2])!=0) continue;//与上面同理，如果i-2行与第i-2的地图条件冲突，剪掉。
for(int k=1;k<=tot;k++)//----看第i-1行，第j个状态下，k的状态。
{
if((sta[k]&sta[j])!=0) continue;//如果第i-1行与第i-2行出现冲突，肯定不对，剪掉。
if((sta[k]&map[i-1])!=0) continue;//并且 如果i-1行与第i-1的地图条件，比如高山啊啥的，冲突也要剪掉。
for(int w=1;w<=tot;w++)//寻找第i行，总共可行的个数。
{
if((sta[w]&map[i])!=0) continue;
if((sta[w]&sta[j])!=0) continue;
if((sta[w]&sta[k])!=0) continue;
dp[i][w][k]=max(dp[i][w][k],dp[i-1][k][j]+sum(w));
//------这里还是要1.再理解dp的状态。2.分析这3重for循环的意义3.结合普通的dp状态转移方程是怎么样的。
// cout<<i<<' '<<w<<' '<<k<<' '<<j<<endl;
// cout<<dp[i][w][k]<<endl;
}
}
}
}
long long ans=0;
for(int i=1;i<=tot;i++)
{
for(int j=1;j<=tot;j++)
{
if ((map[n-1]&sta[i])!=0)continue;
if ((map[n]&sta[j])!=0)continue;
if ((sta[i]&sta[j])!=0)continue;
ans=max(dp[n][j][i],ans);
}
}
printf("%lld\n",ans);
//printf("%lld\n",dp[m][n][]);好像没法直接输出
return 0;
}
/*
总结：一下开朗了很多。
就是从上到下遍历。
然后遍历i-2行情况的状态
再 i-1行情况下的状态
如果上面都满足条件的。
那么再遍历所有方案数去寻找第i行满足条件的最大个数。
总结下来就是4个for循环。 内3个循环都依赖上面求的总方案数，tot。
然后理解状态转移方程式
理解 map[]与sta[]与运算的意义。
judge 和sum两个函数里位运算的使用。
*/
树状数组，区间单点更新+求最大值
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=1000000+10;
using namespace std;
int t,n,m; int a[maxn],c[maxn];
int lowbit(int i)
{
return i&-i;
}
void updata(int i,int val)
{
while(i<=n)
{
c[i]=max(c[i],val);
i+=lowbit(i);
}
}
/*
懂他思想了。
首先，你得清楚树状数组的分块，这些分块到底包含了哪些下标。
因为一段数字可能很长，我们不能逐一遍历。所以我们用分块把他隔开。
每个分块代表着这个下标集合里的最大值。这样就会非常快。
按上面的步骤一直跳着看最大值，直到剩余的长度小于他所属的集合
比如说：1 2 3 4 5 6 7
我要查 2-7，则程序：7所属的分块就是他自己，所以取最大值。然后跳到6
6 包含5 6，所以比较一下取最大值（5-7的最大值），然后跳到4，包含1 2 3 4
如果还是直接取最大值那么就是1-7的最大值了，所以，在这里，我们只能老老实实，一个一个遍历
看看4 是不是最大值，3是不是最大值，2是不是最大值。。结束。-------牛逼。
*/
int getmax(int l,int r)
{
int ans=-1,len=r-l+1;
while(len&&r)//当前还需要判断的范围长度，r是对应区间最大值的下标。
{
if(len<lowbit(r))//长度小于最大值所再的范围。
{
ans=max(ans,a[r]);
r--,len--;
}
else//否则如果范围比r对应的区间要大。
{
ans=max(ans,c[r]);
len-=lowbit(r);
r-=lowbit(r);
}
}
return ans;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
memset(c,0,sizeof(c)); //-----没初始化有wa一发
for(int i=1;i<=n;i++) {scanf("%d",&a[i]);updata(i,a[i]);}
while(m--)
{
getchar();
int x,y;
char op;
scanf("%c %d %d",&op,&x,&y);
if(op=='Q')
{
printf("%d\n",getmax(x,y));
}
else
{
a[x]=y;//这里无所谓吧。-----神TM无所谓，以后还是要记的写上，这里就真用到了。 ---写在后面也wa了一发。
updata(x,y);//x同学，成绩改为y
}
}
}
return 0;
}
几何概型
其中的left right up down 非常的有用，相当于判断是否和这些边有交点。 然后求面积这种的一般都是分类讨论。
/*
题目描述：已知甲在s1到s2时间内各时刻到达车站的概率相等，乙在t1到t2时间内各时刻到达车站的概率相等，
火车将在车站停留w时间，问在火车停靠时间内甲乙见面的概率是多少
方法：典型的几何概型，高中时必修三最常考的，画出x= s1 , x = s2 , y = t1 ,y = t2所围成的区域，再做出直线
y = x + w , 直线 y = x - w，矩形区域夹在两线间的面积与矩形面积比即为答案
直线所夹面积求法：cal（w）函数的含义是求出矩形在y = x + w 下方部分的面积，那么所夹面积可表示为
cal（w）- cal(-w)
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
int s1,s2,t1,t2,w;
double sum;
double cal(int w) //作用：计算y = x + w 直线下方图形的面积
{
//以下四个变量为直线是否与矩形的四条边有交点
bool left , right ,up , down;
//以下四个变量分别为过矩形四个顶点的斜率为1直线的截距
int lu = t2 - s1 , ld = t1 - s1 , ru = t2 - s2 , rd = t1 - s2 ;
double ret;
left = (w >= ld && w <= lu);
right = (w >= rd && w <= ru);
up = (w <= lu && w >= ru);
down = (w <= ld && w >= rd);
if(left && up) ret = sum - 0.5*(t2 - w - s1)*(t2 - w - s1);
else if(left && right) ret = 0.5 * ( 2* w + s1 + s2 - 2 * t1)*(s2 - s1);
else if(up && down) ret = 0.5 * (2 * w + 2*s2 - t1 - t2) * (t2 - t1);
else if(down && right) ret = 0.5 * (s2 - t1 + w)*(s2 - t1 + w);
if(w>=lu) ret = sum;
if(w<=rd) ret = 0;
return ret;
}
int main()
{
// freopen("D:\\professional debugging\\in9.txt","r",stdin);
// freopen("D:\\professional debugging\\out92.txt","w",stdout);
int T , kase = 0;
scanf("%d",&T);
while(T--){
scanf("%d %d %d %d %d",&s1,&s2,&t1,&t2,&w);
sum = 1.0*(s2 - s1) * (t2 - t1);
double area = cal(w) - cal(-w);
double ans = area / sum;
printf("Case #%d: %.8lf\n",++kase,ans);
}
return 0;
}
几何题—点与向量模板
向量的表示方法就是：记录起始点p1(x1,y1)，和终点p2(x2,y2)，所以和node的一样的。
//几何题----与点和向量的。结构体肯定是这样的。
//=====================================点与向量的最基本模板==================================
const double eps=1e-8;//偏差值
double sgn(double x)
{
if(fabs(x)<eps) return 0;//他的绝对值比偏差值eps还小，那就是真的0.
return x>0?1:-1;
}
struct node
{
double x,y;
node(){}
node (double a,double b){x=a;y=b;} //一定要的。
friend node operator+(node a,node b){return node(a.x+b.x,a.y+b.y);}
friend node operator-(node a,node b){return node(a.x-b.x,a.y-b.y);}
friend node operator*(int a,node b){return node(a*b.x,a*b.y);}
friend node operator/(int a,node b){return node(a/b.x,a/b.y);}//p[i]=node(10*node(x,y));
friend bool operator==(node a,node b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}
}p[maxn];//point---点
typedef node Vector;//点和向量其实是一样的结构体。
double cross(Vector a,Vector b) {return a.x*b.y-a.y*b.x;}//叉乘。
double dot(Vector a,Vector b) {return a.x*b.x+a.y*b.y;}//点乘。
//=====================================点与向量的最基本模板==================================
//其他的什么点与线的，我们分开来讲。
求多边形面积。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 10000+10;
const int MOD =10000;
typedef long long ll;
//几何题----与点和向量的。结构体肯定是这样的。
//=====================================点与向量的最基本模板==================================
const double eps=1e-8;//偏差值
double sgn(double x)
{
if(fabs(x)<eps) return 0;//他的绝对值比偏差值eps还小，那就是真的0.
return x>0?1:-1;
}
struct node
{
double x,y;
node(){}
node (double a,double b){x=a;y=b;} //一定要的。
friend node operator+(node a,node b){return node(a.x+b.x,a.y+b.y);}
friend node operator-(node a,node b){return node(a.x-b.x,a.y-b.y);}
friend node operator*(int a,node b){return node(a*b.x,a*b.y);}
friend node operator/(int a,node b){return node(a/b.x,a/b.y);}//p[i]=node(10*node(x,y));
friend bool operator==(node a,node b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}
}p[maxn];//point---点
typedef node Vector;//点和向量其实是一样的结构体。
double cross(Vector a,Vector b) {return a.x*b.y-a.y*b.x;}//叉乘。
double dot(Vector a,Vector b) {return a.x*b.x+a.y*b.y;}//点乘。
//=====================================点与向量的最基本模板==================================
//其他的什么点与线的，我们分开来讲。
int main()
{
int n;
while(cin>>n,n)
{
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
p[i]=node(x,y);
}
double ans=0;
for(int i=2;i<n;i++)
{
ans+=cross(p[i-1]-p[0],p[i]-p[0]);
}
printf("%.1lf\n",ans*0.5);
}
return 0;
}
几何题—线与线模板
记的输出时用.2f不要.2lf
//=============================直线与直线模块=============================
struct line//第一种表示方法：用直线上的两个点来表示
{
node p1,p2;//这条线有两个点。
line(){};
line(node a,node b){p1=a,p2=b;}
}e1,e2;
int p_l_relation(node a,line b) //-----------------点与线的关系
{
int c=sgn(cross(a-b.p1,b.p2-b.p1));
if(c==0)return 0;//直线上
if(c<0) return 1;//左边
if(c>0) return 2;//右边
}
int l_relation(line a,line b)//line_relation--------线与线的关系
{
if(sgn(cross(a.p2-a.p1,b.p2-b.p1))==0)//叉乘为0，说明要么平行要么重合 ---a.p2-a.p1,两个点构成了线/向量。
{
if(p_l_relation(a.p1,b)) return 1;//重合
return 0; //平行
}
return 2;//否则就是相交
}
node getnode(node a,node b,node c,node d)//----------求直线之间的交点
{
double ABD=cross(d-a,b-a);
double ABC=cross(b-a,c-a);
//if(ABC==0||ABD==0) return node(0,0);---如果面积相等
return node((ABD*c.x+ABC*d.x)/(ABD+ABC),(ABD*c.y+ABC*d.y)/(ABD+ABC));
}
//=============================直线与直线模块=============================
几何题—线线求交点
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 1010;
//思路：
//直线与直线之间关系的判断用叉乘。
//直线与直线之间的交点有公式,用叉乘。
//直线与直线的几何模板(在点与向量的基础上)---点与向量是基石
double sgn(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}
struct node
{
double x,y;
node(){};
node (double a,double b){x=a,y=b;}
friend node operator+(node a,node b){return node(a.x+b.x,a.y+b.y);}
friend node operator-(node a,node b){return node(a.x-b.x,a.y-b.y);}
friend node operator*(int a,node b){return node(a*b.x,a*b.y);}
friend node operator/(int a,node b){return node(a/b.x,a/b.y);}
friend bool operator==(node a,node b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}
}p;
typedef node Vector;
double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
//=============================直线与直线模块=============================
struct line//第一种表示方法：用直线上的两个点来表示
{
node p1,p2;//这条线有两个点。
line(){};
line(node a,node b){p1=a,p2=b;}
}e1,e2;
int p_l_relation(node a,line b) //-----------------点与线的关系
{
int c=sgn(cross(a-b.p1,b.p2-b.p1));
if(c==0)return 0;//直线上
if(c<0) return 1;//左边
if(c>0) return 2;//右边
}
int l_relation(line a,line b)//line_relation--------线与线的关系
{
if(sgn(cross(a.p2-a.p1,b.p2-b.p1))==0)//叉乘为0，说明要么平行要么重合 ---a.p2-a.p1,两个点构成了线/向量。
{
if(p_l_relation(a.p1,b)) return 1;//重合
return 0; //平行
}
return 2;//否则就是相交
}
node getnode(node a,node b,node c,node d)//----------求直线之间的交点
{
double ABD=cross(d-a,b-a);
double ABC=cross(b-a,c-a);
//if(ABC==0||ABD==0) return node(0,0);---如果面积相等
return node((ABD*c.x+ABC*d.x)/(ABD+ABC),(ABD*c.y+ABC*d.y)/(ABD+ABC));
}
bool s_s_relation(Line ab,Line cd)//---------------------线段与线段交点，注意要等于0.考虑一个线段的端点在另一个线段上。
{
double f1=cross(cd.p2-ab.p1,ab.p2-ab.p1),f2=cross(cd.p1-ab.p1,ab.p2-ab.p1);
double f3=cross(ab.p2-cd.p1,cd.p2-cd.p1),f4=cross(ab.p1-cd.p1,cd.p2-cd.p1);
if(f1*f2<=0&&f3*f4<=0) return true;
return false;
}
//=============================直线与直线模块=============================
int main()
{
int n;
cin>>n;
puts("INTERSECTING LINES OUTPUT");
for(int i=0;i<n;i++)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
e1=line(node(x1,y1),node(x2,y2));
cin>>x1>>y1>>x2>>y2;
e2=line(node(x1,y1),node(x2,y2));
int flag=l_relation(e1,e2);
if(flag==0) puts("LINE");
else if(flag==1) puts("NONE");
else
{
node p=getnode(e1.p1,e1.p2,e2.p1,e2.p2);
printf("POINT %.2f %.2f\n",p.x,p.y);
}
}
puts("END OF OUTPUT");
return 0;
}
几何题知识点思维导图
希望之后能像这样，系统的学习，总结。
计算几何二维：===================================思维图：点与向量，那么就要构造向量，构造向量需要重构运算，最后就是明确点乘和叉乘的几何意义及应用。【原来思维图，这么有用。】
===========================================思维导图：点与线中，根据题目给的条件求两点来表达直线。在有了点和线后，我们就可以讨论点和直线、点和线段的位置关系，点到直线/线段的距离，以及点在直线上的投影。在有投影又可以得对称点。然后将点变线，则线线之间，我们又可以确定直线与直线的位置关系，直线与直线的交点，线段与线段的交点（线段与线段的相交判断方法要牢记。—将知识点，总结串成一句话，到时只要认真读一下，哪里模糊，就可以直接去看那里了。）
第一大点：点与向量。----关键点：点的构造。
重定义向量的运算--加减乘除 叉乘 点乘 相等。----向量用点来表示【很重要】
点乘的几何意义：A在B上的投影乘以B的长度。
点乘的3个应用：
叉乘的几何意义：求平行四边形的面积。
点乘的5个应用：---------------------------判断向量A与B的方向关系，2.求平行四边形面积，三角形面积4.旋转，求法向量（x,y分别由公式）5.判断向量平行或重合。
点---两点之间的距离。---开根号。
点二大点：点与线-----关键点：线的表示形式（由4种）
3.点和直线的位置关系。
4.点和线段的关系。
5.点到直线的距离。---面积法。
6.点在直线上的投影。---点乘公式。
7.点关于直线的对称点。
8.点到线段的距离---分在与不在。 在，求最小路。不在，求投影。
9.两条直线的位置关系。
10.求两条直线的交点。---公式。
11.判断两个线段是否相交。---叉积。
扫描线算法+线段树模板
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
//===================================从左往右扫，所以要定义每条边的上下两个端点。x是记录这条边的位置。
struct Edge
{
double y1,y2,x;int val;
Edge(){};
Edge(double a,double b,double c,int d){y1=a,y2=b,x=c;val=d;}
friend bool operator<(const Edge &a,const Edge &b){return a.x<b.x;}//保证从左到右，扫到的顺序是正确的。
}a[maxn];
double all[maxn];//与树存的下标有对应关系的。//相当于离散化后所对应的值。
//===================================
//==============================建树==========================================
struct Node
{
int l,r;
int sum;//就是覆盖标志，cover
double len;//记录y1-y2的长度
}tree[maxn<<2];//根节点维护的是[l, r]的区间
void build(int l, int r, int u) {
tree[u].l=l;tree[u].r=r;tree[u].sum=0;tree[u].len=0;
if(r-l==1) return ;
int mid=(l+r)>>1;//线段树从1开始。
build(l,mid,u<<1);
build(mid,r,u<<1|1);//u<<1|1与 u<<1)+1等价
}
//==============================建树==========================================
//==============================计算长度==========================================
void pushup(int u)
{
int l=tree[u].l,r=tree[u].r;
if(tree[u].sum)//这就是上面所说的 只有被覆盖和没被覆盖的区别
{
tree[u].len=all[r]-all[l];//如果这个结点是有被覆盖过的， //右-左就是长度。
}
else
{
tree[u].len=tree[u<<1].len+tree[(u<<1)+1].len;//如果没被扫到 则从以前扫过的线段更新,就是向上更新到tree[1]，给我们调用
}
}
//==============================计算长度结束==========================================
//==============================更新==========================================
void update(double bottom,double top,int val,int u)//当扫描线扫到一条线段 val代表这是入度还是出度
{
int l=tree[u].l,r=tree[u].r;
if(all[r]<=bottom || top<=all[l]) return;//要更新的线段不属于这个线段树节点 算是个剪枝吧
if(bottom<=all[l] && all[r]<=top)//----如果这个结点符合范围，则，区间修改。
{
tree[u].sum+=val;
pushup(u);
return;
}
//由于有剪枝 我们就不用判断了 直接修改子树就好了
update(bottom,top,val,u<<1);
update(bottom,top,val,u<<1|1);
pushup(u);//为了维护线段树长度的。不是下面说的。下面的等我以后想想怎么解决把。
//单个结点，比如说线段树维护【1~6】，则【1~3】可以直接由上面过去，
//但4不行【4~6】不符合，【4~5】不符合。这个时候执行计算长度里的最下条代码
}
//==============================更新结束---这里还是不太模拟清楚。==========================================
int main()
{
int kase=0;
int n;
while(scanf("%d",&n),n)
{
memset(all,0,sizeof(all));
memset(a,0,sizeof(a));
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++)
{
double x1,y1,x2,y2;
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
a[i]=Edge(y1,y2,x1,1);//----------------------核心
a[i+n]=Edge(y1,y2,x2,-1);
all[i]=y1;//离散化
all[i+n]=y2;
}
n<<=1;//入边n个和出边n个共2n
sort(a+1,a+n+1);//对每条边进行排序。这样就能正确的遍历两个相邻的边。
//===================================离散化开始========================
sort(all + 1, all + 1 + n);//
int cnt=unique(all+1,all+n+1)-all-1;//记录不重复个数。
//for(int i=1;i<=cnt;i++) cout<<all[i]<<endl;----由此证明：unique已经把相同的y去掉了。
//===================================离散化结束========================
build(1,cnt,1);
double ans=0;
for(int i=1;i<=n;i++)
{
ans+=tree[1].len*1.0*(a[i].x-a[i-1].x);
update(a[i].y1,a[i].y2,a[i].val,1);
}
printf("Test case #%d\n",++kase);
printf("Total explored area: %.2f\n\n",ans);
}
return 0;
}
凸包模板—andrew算法
#include <iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int maxn = 1010;
int c[maxn];
int n;
int sgn(double x){if(fabs(x)<eps)return 0;else return x>0?1:-1;}
//因为用到了叉乘
struct Node
{
double x,y;
Node(){}
Node(double a,double b){x=a,y=b;}
friend Node operator+(const Node &a,const Node &b){return Node(a.x+b.x,a.y+b.y);}
friend Node operator-(const Node &a,const Node &b){return Node(a.x-b.x,a.y-b.y);}
friend Node operator8(const Node &a,double b){return Node(a.x*b,a.y*b);}
friend Node operator/(const Node &a,double b){return Node(a.x/b,a.y/b);}
friend bool operator==(const Node &a,const Node &b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}
friend bool operator<(const Node &a,const Node &b){return sgn(a.x-b.x)<0||(sgn(a.x-b.x)==0&&sgn(a.y-b.y)<0);}//排序
}p[maxn],all[maxn];
typedef Node Vector;
double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double dis(Node a,Node b) {return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));}
int andrew(Node *p,int n,Node *all)//返回凸包顶点个数
{
sort(p,p+n);//对点排序，按x从小到大，相同 按y从小到大。
n=unique(p,p+n)-p;//去重复点。
int v=0;//求下凸包。
for(int i=0;i<n;i++)
{
while(v>1&&sgn(cross(all[v-1]-all[v-2],p[i]-all[v-2]))<=0) v--;//v>1---p0这个点不能删。 遵循旧线叉乘新线，都从旧线起点出发。。
all[v++]=p[i];//第一个点，一定是凸包上的点。
}
//凸包有个性质：最左边的一定是凸包起点。最右边的，一定是凸包终点。
//所以从左到右遍历，可以求出下部分。从右到左遍历，可以求出上部分。整个就是凸包图。
int j=v; //求上凸包
for(int i=n-2;i>=0;i--)//为什么减2 减1是因为我是从0开始，所以到过来n是要n-1，还有有个是因为右边终点即是起点。
//且起点已经在下部分的时候保存了，所以不需要再保存。
{
while(v>j&&sgn(cross(all[v-1]-all[v-2],p[i]-all[v-2]))<=0) v--;
all[v++]=p[i];
}
if(n>1) v--;//因为v++,每次会比我们的个数多一个，如果上面都是++v就没事了。
return v;
}
int main()
{
int n,l;
while(~scanf("%d",&n),n)
{
for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
int v=andrew(p,n,all);
double ans=0;
if(v==1) printf("%.2f\n",0.00);
else if(v==2) printf("%.2f\n",dis(p[0],p[1]));
else
{
for(int i=0;i<v;i++)
{
ans+=dis(all[i],all[(i+1)%v]);//all存放的就是凸包图点。
}
printf("%.2f\n",ans);
}
}
return 0;
}
单调队列模板
单调队列应用
通过单调队列求连续区间最大值。
通过一些手法，单调队列记录修改的次数。如下代码。----还是要好好分析
hdu
#include <cstdio>
#include<iostream>
#include <algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 1e7+10;
typedef long long ll;
const double eps= 1e-8;
int n,m,k,p,qq,r,mod,t;
int q[maxn];//模拟队列,存放的是arr满足条件的下标。
int main() {
scanf("%d",&t);
while(t--)
{
ll sum1=0,sum2=0;
scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&qq,&r,&mod);
vector<ll> a(n+2);//a(n+2)这样做才能想数组一样可以scanf，否则会报错。
for(int i=1;i<=k;i++) {scanf("%lld",&a[i]);}
for(int i=k+1;i<=n;i++) a[i]=(1ll*p*a[i-1]+1ll*qq*i+1ll*r)%mod;
int head=1,tail=1;
reverse(a.begin(),a.end());//---------------------从后往前。
for(int i=1;i<=n;i++)//--------单调队列从1开始。
{
while(head<tail&&q[head]<=i-m) head++;//i-m是保持范围在m内。当i-m指向了队头的位置，说明该数已不在区间里了。
while(head<tail&&a[q[tail-1]]<=a[i]) tail--;//q[tail-1]分析 因为下面是tail++,即赋值了tail再tail+1.
q[tail++]=i;
// cout<<"===="<<tail<<endl;
if(i>=m)
{
sum1=sum1+(a[q[head]]^(ll)(n+1-i));
sum2=sum2+((n+1-i)^(ll)(tail-head));
}
}
// for(int i=0;i<=n-m;i++) printf("%lld ",Max[i]);
printf("%lld %lld\n",sum1,sum2);
}
system("pause");
return 0;
}
Floyd求走过第k条边后的最短路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e18;
const int maxn=5e5+10;
int t,n,m,q;
struct matrix
{
ll room[60][60];
matrix()
{
for(int i=0;i<60;i++)
for(int j=0;j<60;j++)
room[i][j]=INF;
};
friend matrix operator*(const matrix &a,const matrix &b)
{
matrix box;
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
box.room[i][j]=min(box.room[i][j],a.room[i][k]+b.room[k][j]);
}
}
}
return box;
}
};
matrix mat,box[110],matrix100[110];
void init(){
box[1]=mat;
for (int i=2;i<=101;i++) box[i]=box[i-1]*box[1];//分块前100
matrix100[1]=box[100];
for (int i=2;i<=101;i++) matrix100[i]=matrix100[i-1]*matrix100[1];//分块200 300 400...
for (int k=99;k>=1;k--){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
box[k].room[i][j]=min(box[k].room[i][j],box[k+1].room[i][j]);
matrix100[k].room[i][j]=min(matrix100[k].room[i][j],matrix100[k+1].room[i][j]);
}
}
}
box[0]=box[1];
for (int i=0;i<55;i++){
for (int j=0;j<55;j++){
matrix100[0].room[i][j]=INF;
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
for(int i=0;i<60;i++)
for(int j=0;j<60;j++)
mat.room[i][j]=INF;
for(int i=1;i<=m;i++)
{
int u,v;
ll w;
scanf("%d %d %lld",&u,&v,&w);
mat.room[u][v]=min(mat.room[u][v],w);//??
}
init();
// for(int k=1;k<=10;k++)
// {
// for(int i=1;i<=10;i++)
// {
// for(int j=1;j<=10;j++)
// {
// printf("%d ",box[k].room[i][j]);
// }
// puts("");
// }
// puts("===123===");
// }
scanf("%d",&q);
while(q--)
{
int s,t,k;
scanf("%d %d %d",&s,&t,&k);
ll ans=INF;
ll x=k/100;
ll y=k%100;
for (int i=1;i<=n;i++){
ans=min(ans,matrix100[x].room[s][i]+box[y].room[i][t]);
ans=min(ans,matrix100[x+1].room[s][i]+box[0].room[i][t]);
}
if (x==0) ans=min(ans,box[y].room[s][t]);
if (y==0) ans=min(ans,matrix100[x].room[s][t]);
if (ans==INF) printf("-1\n");
else printf("%lld\n",ans);
}
}
system("pause");
return 0;
}
埃筛模板
void getss()
{
k=0;
vis[0]=vis[1]=1;
for(ll i=2;i*i<maxn;i++)//
{
if(vis[i]==1) continue;
//ss[++k]=i;//用埃筛把素数存在一个数组里，那么必须把上面i*i写成i。血泪史---poj 2739（因为你这样只存到sqrt(i)就停止了，后面的素数直接被省略过去了。）
for(ll j=i*i;j<maxn;j+=i)
{
vis[j]=1;
}
}
}
欧拉筛模板----如果要存入数组的话，是从下标1开始
void getss()
{
//任何一个合数都可以表示成一个质数和一个数的乘积
int num=0;
vis[0]=vis[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i]) ss[++num]=i;
for(int j=1;j<=num&&i*ss1[j]<maxn;j++)//---注意一下：不管i是不是素数都要运行for循环。这是与埃筛不一样的地方。
{
vis[i*ss[j]]=1;//ss[j]是 合数i*prime[j] 的最小素因子
if(!i%ss[j]) break;//即比一个合数 大的质数 和 该合数 的乘积可用一个 比其小的质数 和 更大的合数 相乘得到。
}
}
}
if(!i%ss[j]) break;样例理解：
vis ：1 2 3 4 5 6 7 8 9 10
假设目前ss表：2 3
当i=4时，我们只要把8（即i2的数）去掉就可以直接i=5了。（所以只运行一次）
因为根据证明：假设我们不马上i=5.那么我们执行的操作应该是43=12；但根据证明，我们总能找到一个更小的素数乘一个合数–得到43=223=26=12，所以12已经被我们i=2的时候就去掉了。同理45 47，都是毫无意义的。因此遇到这种情况就直接用这段代码跳i=5了.
尺取法—求和满足条件版
while(~scanf("%d",&n),n)
{
int l=1,r=1;
int sum=0,ans=0;
while(1)
{
while(sum<n&&r<=n)
{
sum+=ss[r++];
}
if(sum<n) break;
if(sum==n) ans++;//计数用的。满足这样的区间有ans个
sum-=ss[l++];
}
cout<<ans<<endl;
}
期望dp入门代码----期望，求平均值
/*题意：有s个系统,有n种bug,bug的数量不限,一位程序员每天可以发现一个bug
现在求发现n种bug存在s个系统中并且每个系统都要被发现bug的平均天数(期望)
分析：在这里有s,n两个变量，假设dp[i][j]表示已经发现i种bug存在j个系统到目标所需要的天数,显然dp[n][s]=0;
从dp[i][j]经过一天后可能得到以下四种情况:
dp[i][j]->dp[i+1][j+1];//在一个新的系统里面发现一个新的bug
dp[i][j]->dp[i+1][j];//在原来已发现过bug的系统里发现一个新的bug
dp[i][j]->dp[i][j+1];//在一个新的系统里面发现一个已被发现过的bug
dp[i][j]->dp[i][j];//在已发现过bug的系统发现已发现过的bug
四种到达的概率分别是:
p1=(n-i)*(s-j)/(n*s);
p2=(n-i)*j/(n*s);
p3=i*(s-j)/(n*s);
p4=i*j/(n*s);
然后根据E(aA+bB+cC+dD+...)=aEA+bEB+....;//a,b,c,d...表示概率,A,B,C...表示状态
所以dp[i][j]=p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i][j]+1;//dp[i][j]表示的就是到达状态i,j的期望
=>dp[i][j]=(p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+1)/(1-p4);
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;
const int MAX=1000+10;
int n,s;
double dp[MAX][MAX],p1,p2,p3,p4;
int main(){
while(cin>>n>>s){
memset(dp,0,sizeof dp);
for(int i=n;i>=0;--i){//期望dp从后往前，概率dp从前往后。
for(int j=s;j>=0;--j){
if(i == n && j == s)continue;
p1=(n-i)*(s-j)*1.0;//我连概率都想不明白。
p2=(n-i)*j*1.0;
p3=i*(s-j)*1.0;
p4=n*s-i*j*1.0;
dp[i][j]=(p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+n*s)/p4;
}
}
printf("%.4lf\n",dp[0][0]);
}
return 0;
}
