第一節(jié)
1燎字、鏈表與鄰接表
2、棧與隊(duì)列
3阿宅、Kmp
一候衍、鏈表
1、單鏈表 ： 鄰接表
鄰接表作用 存儲(chǔ)圖和樹
2洒放、雙鏈表 用來優(yōu)化某些問題
e[N] 某個(gè)點(diǎn)的值
ne[N] 某個(gè)節(jié)點(diǎn)的next指針
他們用下標(biāo)關(guān)聯(lián)起來
最后一個(gè)元素的next指針指向空集 ne[n-1]=-1
單鏈表只能找到一個(gè)節(jié)點(diǎn)的下一個(gè)數(shù)蛉鹿，無(wú)法找到上一個(gè)數(shù)
注意：下標(biāo)是從0開始的，0是第一個(gè)插入的點(diǎn)
第k個(gè)插入的點(diǎn)的下標(biāo)是k-1
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
//head 表示頭節(jié)點(diǎn)的next指針
//e[i]表示節(jié)點(diǎn)i的值
//ne[i]表示節(jié)點(diǎn)i的next指針
//idx是指針 表示當(dāng)前已經(jīng)用到了哪個(gè)點(diǎn)的空間
int head,e[N],ne[N],idx;
void init(){
head=-1;
idx=0;
}
//將x插到頭節(jié)點(diǎn)的位置
void add_to_head(int x){
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
//將x插入到下標(biāo)是k的點(diǎn)后面
void add(int k,int x){
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//將下標(biāo)是k的后一個(gè)點(diǎn)刪掉
void remove(int k){
ne[k]=ne[ne[k]];
}
int main()
{
int m;
cin>>m;
init();
while(m--){
char c;
int k,x;
cin>>c;
if(c=='H'){
cin>>x;
add_to_head(x);
}
else if(c=='D'){
cin>>k;
if(k==0)
head=ne[head]; //刪除頭節(jié)點(diǎn)
else remove(k-1);
}
else if(c=='I'){
cin>>k>>x;
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i])
cout<<e[i]<<" ";
cout<<endl;
return 0;
}
二往湿、雙鏈表
l[N] 指向 N 前面的節(jié)點(diǎn)
r[N] 指向 N 后面的節(jié)點(diǎn)
e[N] 表示這個(gè)點(diǎn)的值
讓下標(biāo)是0 的點(diǎn)為head
下標(biāo)為1的點(diǎn)為最后一個(gè)點(diǎn)
#include<bits/stdc++.h>
using namespace std;
int m;
const int N=1e5+10;
int e[N],l[N],r[N],idx;
void init(){
r[0]=1;//0表示左端點(diǎn)妖异，l表示右端點(diǎn)
l[1]=0;
idx=2;
}
//在下標(biāo)為k的右邊插入一個(gè)點(diǎn)x
//若要在下標(biāo)為k的左邊插入一個(gè)點(diǎn)x
//只需要調(diào)用 l[k] c就可以
void add(int k,int c){
e[idx]=c;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
//刪除第k個(gè)點(diǎn)
void remove(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
cin>>m;
init();
while(m--)
{
string op;
cin>>op;
if(op=="L"){
int x;
cin>>x;
add(0,x); //在最左側(cè)的右側(cè)插入一個(gè)點(diǎn)
} //左端點(diǎn)是0
else if(op=="R"){
int x;
cin>>x;
add(l[1],x);//在最右側(cè)的左側(cè)
} //最右側(cè)端點(diǎn)的是1 插入l[1]后面
else if(op=="D"){
int k;
cin>>k;
remove(k+1);//idx從2開始 所以是k+1
}
else if(op=="IL"){
int k,x;
cin>>k>>x;
add(l[k+1],x);//k+1
}
else if(op=="IR"){
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<" ";//左端點(diǎn)不輸出
return 0;//從左端點(diǎn)的右側(cè)輸出
//i！=-1就沒遍歷到右端點(diǎn)
} //i=r[i] i每次變?yōu)橛覀?cè)的點(diǎn)
三领追、鄰接表
n個(gè)單鏈表
把每個(gè)表的所有鄰邊都存起來
四他膳、模擬棧
int stk[N],tt;
stk[++tt]=x;//插入
tt--; //彈出
if(tt>0) not empty
else empty
stk[tt];//棧頂
//int stk[N],tt;
//stk[++tt]=x;//插入
//tt--; //彈出
//if(tt>0) not empty
//else empty
//stk[tt];//棧頂
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int main(){
int stack[N],tt;
int m;
cin>>m;
while(m--){
string op;
cin>>op;
int k,x;
if(op=="push"){
cin>>x;
stack[++tt]=x; //插入x
}
else if(op=="pop"){
tt--;//彈出棧頂元素
}
else if(op=="query"){
cout<<stack[tt]<<endl;//tt是棧頂
}
else if(op=="empty"){
if(tt>0)//tt大于0 則stack不為空
cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
return 0;
}
五、模擬隊(duì)列
////在隊(duì)尾插入元素绒窑，在隊(duì)頭彈出元素
//int q[N],hh,tt=-1;
////插入
//q[++tt]=x;
////彈出
//h++;
////判斷是否為空
//if(hh<=tt)not empty
//else empty
////去除隊(duì)頭元素
//q[hh]; 隊(duì)頭
//q[tt];隊(duì)尾
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int q[N],hh,tt=-1;
int main(){
int m;
cin>>m;
string op;
while(m--){
cin>>op;
int x,k;
if(op=="push"){
cin>>x;
q[++tt]=x; //在隊(duì)尾加入一個(gè)元素
}
else if(op=="pop"){
hh++; //隊(duì)頭++ 就是彈出隊(duì)頭
}
else if(op=="query"){
cout<<q[hh]<<endl; //輸出隊(duì)頭
}
else if(op=="empty"){
if(hh<=tt) //如果隊(duì)頭是小于等于隊(duì)尾的 就非空
cout<<"NO"<<endl;
else cout<<"YES"<<endl;//否則為空
}
}
return 0;
}
六.單調(diào)棧
對(duì)暴力`進(jìn)行優(yōu)化
題型 找到左邊或者右邊,第一個(gè)比它大或者比他小的數(shù)
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N]; //s為棧
int tt=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(tt&&s[tt]>=a[i])tt--;//tt代表?xiàng)２粸榭?
if(tt)cout<<s[tt]<<" "; //s[tt]>=a[i]當(dāng)前棧頂元素大于當(dāng)前元素則把他彈出
else cout<<-1<<' '; //操作后如果棧不為空則棧頂元素就是第一個(gè)小于當(dāng)前元素的元素
s[++tt]=a[i];//再把當(dāng)前元素入棧
}
return 0;
}
七. 單調(diào)隊(duì)列
同樣是對(duì)暴力進(jìn)行優(yōu)化
應(yīng)用: 求滑動(dòng)窗口中的最大值和最小值
棧和隊(duì)列就是刪除沒有用的元素,維護(hù)一個(gè)單調(diào)性
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int tt=-1,hh;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(hh<=tt&&i-k+1>q[hh])hh++;
//隊(duì)列不為空,如果起點(diǎn)>q[hh] 隊(duì)列中存的是下標(biāo)
//則需要將窗口向后移動(dòng)一個(gè) h++;
while(hh<=tt&&a[q[tt]]>=a[i])tt--;
//隊(duì)列不為孔二 且隊(duì)尾下標(biāo)對(duì)應(yīng)元素大于a[i]則彈出
q[++tt]=i;//操作結(jié)束把新下標(biāo)入隊(duì)
if(i-k+1>=1)cout<<a[q[hh]]<<" ";
//從第一個(gè)窗口開始輸出 隊(duì)頭就是最小值
}
cout<<endl;
tt=-1,hh=0;
for(int i=1;i<=n;i++){
if(hh<=tt&&i-k+1>q[hh])hh++;
//隊(duì)列不為空,如果起點(diǎn)>q[hh] 隊(duì)列中存的是下標(biāo)
//則需要將窗口向后移動(dòng)一個(gè) h++;
while(hh<=tt&&a[q[tt]]<=a[i])tt--;
//隊(duì)列不為孔二 且隊(duì)尾下標(biāo)對(duì)應(yīng)元素大于a[i]則彈出
q[++tt]=i;//操作結(jié)束把新下標(biāo)入隊(duì)
//注意先把這個(gè)樹加進(jìn)去再輸出
if(i-k+1>=1)cout<<a[q[hh]]<<" ";
//從第一個(gè)窗口開始輸出 隊(duì)頭就是最小值
}
cout<<endl;
return 0;
}
KMP 算法
S[N] P[M] S長(zhǎng)串 P 短串
尋找原串中包含子串的數(shù)目
next[N];
next[N] 只和字串有關(guān) 預(yù)處理子串
以某一點(diǎn)為中點(diǎn)的后綴和前綴 最長(zhǎng)相等的長(zhǎng)度是多少
1 j i
p[1~j] = p[i-j+1~i];
*/
//7. KMP
//求Next數(shù)組：
// s[]是模式串棕孙，p[]是模板串, n是s的長(zhǎng)度，m是p的長(zhǎng)度
//for (int i = 2, j = 0; i <= m; i++)
//{
// while (j && p[i] != p[j + 1]) j = ne[j];
// if (p[i] == p[j + 1]) j++;
// ne[i] = j;
//}
// 匹配
//for (int i = 1, j = 0; i <= n; i++)
//{
// while (j && s[i] != p[j + 1]) j = ne[j];
// if (s[i] == p[j + 1]) j++;
// if (j == m)
// {
// j = ne[j];
// 匹配成功后的邏輯
// }
//}
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=10010,M=100010;
char p[N],s[M];
int ne[N];
int ans;
int main()
{
cin>>n>>p+1>>m>>s+1;
for(int i=2;i<=n;i++){
while(j&&p[i]!=p[j+1])
j=ne[j];
if(p[i]==p[j+1])
j++;
ne[i]=j;
}
for(int i=1;i<=n;i++){
while(j&&s[i]!=p[j+1])
j=ne[j];
if(p[i]==p[j+1])
j++;
if(j==n){
cout<<i-n+1-1<<endl;
j=ne[j];
}
}
return 0;
}
trie 字典樹
在一個(gè)集合中快速查找和存儲(chǔ)一些字符串
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//son[N][27] 表示一共有N 個(gè)節(jié)點(diǎn) 每個(gè)節(jié)點(diǎn)最多
//有 26 個(gè)兒子 所以二維的值是27
//cnt[N] 表示以某個(gè)字母為結(jié)尾的單詞數(shù)量
//idx 表示當(dāng)前創(chuàng)建的空間
int son[N][27],cnt[N],idx;
int n;
string str;
void Insert() {
int len = str.size();
int p = 0;
for (int i = 0; i < str.size(); i++) {
int u = str[i] - 'a';
//如果沒有這個(gè)字母就創(chuàng)建一個(gè)
if (!son[p][u])son[p][u]=++idx;
//創(chuàng)建后改變p 的值 增加節(jié)點(diǎn)數(shù)
p = son[p][u];
}
//單詞全部存儲(chǔ)完畢 則將cnt++
cnt[p]++;
}
int Que() {
int len = str.size();
int p = 0;
for (int i = 0; i < str.size(); i++) {
int u = str[i] - 'a';
//如果找到某個(gè)字母時(shí)發(fā)現(xiàn)沒有 則return0
if (!son[p][u])return 0;
//將p變成他的兒子
else p = son[p][u];
}
return cnt[p];//返回這個(gè)單詞的數(shù)量
}
int main()
{
cin >> n;
while (n--) {
char c;
cin >> c>>str;
if (c == 'I') {
Insert();
}
else if (c == 'Q') {
int ans=Que();
cout << ans << endl;
}
}
system("PAUSE");
return 0;
}
最大異或?qū)?/h3>
將一個(gè)數(shù)的二進(jìn)制逐個(gè)插入字典樹
從最高位開始找 每次找這個(gè)數(shù)相反的支路
如果沒有相反的支路就走本支路
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M=31e5+10;
int son[M][2],a[N],idx;
int n,ans=-0x3f3f3f3f;
void Insert(int x)
{
int p = 0;
for (int i = 30; i >=0; i--)
{
if (!son[p][x >> i & 1]) {
//x>>i&1 分離出一個(gè)數(shù)的每個(gè)二進(jìn)制位
son[p][x >> i & 1] = ++idx;
//如果沒有則開建立一個(gè)兒子節(jié)點(diǎn)
}
p = son[p][x >> i & 1];
//如果有則p變成他的兒子節(jié)點(diǎn)
}
}
int Search(int x)
{
int p = 0;
long long res=0;
for (int i = 30; i >= 0; i--) {
if (son[p][!(x>>i&1)]) {
//如果有與他相反的那個(gè)支路走這條
p = son[p][!(x>>i&1)];
//結(jié)果加上 1左移動(dòng)i位
res += 1 << i;
}
else p = son[p][x>>i&1];
//如果沒有相反的則走這條相同的路
//異或后為0 res 不變
}
return res;
}
int main()
{
/*int a = 1, b = 2,c;
c = a ^ b;
cout << c << endl;*/
//cout << M << endl;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
Insert(a[i]);//插入字典樹
}
for (int i = 1; i <= n; i++)
{
ans=max(ans,Search(a[i]));
//搜索每個(gè)元素異或最大的支路值
}
cout << ans << endl;
system("PAUSE");
return 0;
}
并查集
1些膨、將兩個(gè)集合合并
2散罕、詢問兩個(gè)元素是否在一個(gè)集合當(dāng)中
基本原理：
用樹的形式來維護(hù)一個(gè)集合。
每個(gè)樹的根節(jié)點(diǎn)的編號(hào)為這個(gè)集合的編號(hào)
每一個(gè)節(jié)點(diǎn)都存儲(chǔ)一下其父親節(jié)點(diǎn)是誰(shuí)P[x]表示x的父節(jié)點(diǎn)
問題1：如何判斷樹根傀蓉？ 若P[X]=x 則x是樹根
問題2：如何求x的集合編號(hào) while(p[x]!=x)x=p[x];
問題3：如何合并兩個(gè)集合：若px是x集合的編號(hào)欧漱，py是y集合的編號(hào)
則 p[x]=y 把x集合合并到y(tǒng)集合當(dāng)中
并查集的優(yōu)化 ： 路徑壓縮
遍歷后 將所有的兒子節(jié)點(diǎn)都指向根節(jié)點(diǎn)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], idx;
int n, m;
int find(int x) {
if (p[x] != x) //如果還沒找到根節(jié)點(diǎn) 則繼續(xù)往上找
p[x]=find(p[x]);//找到后賦值給p[x]并且返回
// 注意找到后·賦值給p[x] 順便做了路勁壓縮
//for (int i = 1; i <= n; i++)
// cout << p[i] << " ";
//cout << endl;
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
p[i] = i; //起初的時(shí)候每個(gè)數(shù)字是一個(gè)集合
//初始化他們的根節(jié)點(diǎn)為本身
}
while (m--)
{
char c;
int a, b;
cin >> c >> a >> b;
if (c == 'M') {
p[find(a)] = find(b); //將a 直接并入b中
}
else if (c == 'Q') {
if (find(a) == find(b))//如果a b的根節(jié)點(diǎn)相同則屬于一個(gè)集合
cout << "Yes" << endl;
else cout << "No" << endl;
}
}
//system("PAUSE");
return 0;
}
連通塊中點(diǎn)的數(shù)量 837
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], cnt[N];
int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
p[i] = i;
cnt[i]++;
}
while (m--) {
string op;
int a, b;
cin >> op;
if (op =="C") {
cin >> a >> b;
if (find(a) != find(b))
{
int num = cnt[find(a)];
p[find(a)] = find(b);
cnt[find(b)] += num;
}
}
else if (op == "Q1") {
cin >> a >> b;
if (find(a) == find(b))
cout << "Yes" << endl;
else cout << "No"<<endl;
}
else if (op == "Q2") {
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
費(fèi)解的開關(guān)
1、 按的順序可以任意
2葬燎、 按偶數(shù)次是不變的所以每個(gè)格子最多按一次按兩次沒用
3误甚、從第一行開始 第一行操作完不改變 則 第二行被第一行唯一確定
核心：每一行開關(guān)的操作完全被上一行燈的亮滅狀態(tài)所決定
問題
1缚甩；如何枚舉第一行的操作
位運(yùn)算二進(jìn)制枚舉
2^5=0~31
00000 00001
....~11111 16+8+4+2+1=31
for(int i=0;i<32;i++)
{
看第k位是否需要操作
i >> K&1;
}
2: turn(x,y)
根據(jù)偏移量 寫開關(guān)變換的狀態(tài)
3：時(shí)間復(fù)雜度
#include<bits/stdc++.h>
using namespace std;
string s[6],back_up[6];
const int N=6;
//char s[N][N],back_up[N][N];
int n;
int dx[5]={0,-1,0,1,0};//枚舉五個(gè)方向
int dy[5]={-1,0,1,0,0};
void turn(int x,int y)
{
for(int i=0;i<5;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0||xx>4||yy<0||yy>4)
continue;
if(back_up[xx][yy]=='0')
back_up[xx][yy]='1';
else back_up[xx][yy]='0';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
while(n--){
string s[5];
for(int i=0;i<5;i++)
cin>>s[i];
int ans=10;
for(int op=0;op<32;op++){ //注意這里枚舉的是操作數(shù)目 而不是第一行的狀態(tài)
//memcpy(back_up,s,sizeof(s));
for(int i=0;i<5;i++)
back_up[i]=s[i]; //用一個(gè)數(shù)組作為拷貝數(shù)組 用來改變?cè)瓟?shù)據(jù)
int step=0;
for(int i=0;i<5;i++){
if(op>>i&1)
{
step++;
turn(0,i);
}
}
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
if(back_up[i][j]=='0'){
step++; //這一行的為0 下一行必須改變
turn(i+1,j);
}
}
}
bool dark=false;
for(int i=0;i<5;i++){
if(back_up[4][i]=='0')
{
dark=true;
break;
}
}
if(!dark)
ans=min(ans,step);
for(int i=0;i<5;i++)
back_up[i]=s[i];
}
if(ans>6)
cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}
飛行員兄弟
- 每個(gè)開關(guān)只按一次
2.順序是沒有關(guān)系的
解題思路
1、枚舉所有方案
2窑邦、按照方案對(duì)所有燈泡進(jìn)行操作
3擅威、判斷是否全亮->記錄方案
#include<bits/stdc++.h>
using namespace std;
const int N = 5;
char g[N][N], backup[N][N];
typedef pair<int, int> PII;
int get(int x, int y) {
return x * 4 + y; // 將 二維數(shù)組下標(biāo) 轉(zhuǎn)化為 0~15
}
void turn_one(int x, int y) {
if (g[x][y] == '+')
g[x][y] = '-';
else g[x][y] = '+';
}
void turn_all(int x, int y) {
for (int i = 0; i < 4; i++) {
turn_one(x, i);// 行操作
turn_one(i, y);//列操作
}
turn_one(x, y);// 由于x y 這個(gè)點(diǎn)操作了 兩次 所以再操作一次 將其恢復(fù)為操作一次
}
int main()
{
for (int i = 0; i < 4; i++)
cin >> g[i];
vector<PII> res; //記錄最終答案res
for (int op = 0; op < (1 << 16); op++) {//枚舉每一種狀態(tài) 一共2^16種 1表示要按下這個(gè)開關(guān)一次
vector<PII> temp;//每次枚舉新建一共存儲(chǔ)方案
memcpy(backup, g, sizeof(g));//拷貝保留原數(shù)據(jù)
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (op >> get(i, j) & 1) { //二維枚舉 每當(dāng)遇到一共1 就是一次操作
temp.push_back(make_pair(i, j));//沒操作一次 記錄再方案中
turn_all(i, j); //進(jìn)行操作
}
}
}
bool has_closed = false; //判斷結(jié)果
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (g[i][j] == '+')
has_closed = true;
}
}
if (has_closed == false) {
//起初的res 是空的 所以要加入這個(gè)條件 讓此時(shí)的res被temp賦值
//后面如果res的操作數(shù)是比temp多的 則更新 res
if (res.empty() || res.size() > temp.size())
res = temp;
}
memcpy(g, backup, sizeof(g));
}
cout << res.size() << endl;
vector<PII>::iterator iter = res.begin(); //迭代器 遍歷輸出res
for (iter; iter != res.end(); ++iter)
cout << iter->first + 1 << ' ' << iter->second + 1 << endl;
return 0;
}
/*
翻硬幣
開始用了DFS 只能過一半
后來發(fā)現(xiàn)了規(guī)律，每個(gè)硬幣反兩次則無(wú)效
只需要從頭到尾枚舉一遍 不一樣就翻一次 就可
*/
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
int len;
int ans = 0x3f3f3f3f;
void turn(int num)
{
if (s1[num] == '*')
s1[num] = 'o';
else s1[num] = '*';
if (s1[num + 1] == '*')
s1[num + 1] = 'o';
else s1[num + 1] = '*';
}
int main()
{
cin >> s1 >> s2;
len = s1.length();
string backup = s1;
int step = 0;
for (int i = 0; i < len - 1; i++)
{
if (s1[i] != s2[i])
{
turn(i);
step++;
}
if (s1 == s2)
break;
}
cout << step << endl;
system("PAUSE");
return 0;
}
食物鏈
余1： 可以吃根節(jié)點(diǎn)
余2： 可以被根節(jié)點(diǎn)吃
余0：與根節(jié)點(diǎn)同類
余2吃余1 余0吃余2
所以%3余數(shù)相同的則是同一類 （關(guān)鍵）
帶權(quán)并查集精髓總結(jié)：只要兩個(gè)元素在一個(gè)集合里面冈钦，通過它們與根節(jié)點(diǎn)的距離就能知道它們的相對(duì)關(guān)系郊丛。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int n,k;
int p[N],d[N];
int find(int x) {
if (p[x] != x) {
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
cin >> n >> k;
int res = 0;
for (int i = 1; i <= n; i++)
p[i] = i;
while (k--)
{
int t, x, y;
cin >> t >> x >> y;
if (x > n || y > n)res++; //如果有的點(diǎn)大于了n 則是假話
else {
int px = find(x), py = find(y);// px 是x的根節(jié)點(diǎn) y同理
if (t == 1) {
if (px == py && (d[x] - d[y]) % 3 != 0)//px==py 則x y 在同一個(gè)集合中
d[x]%3 應(yīng)該 和d[y]%3 相等 這樣x y 才是同類 -> (d[x]-d[y])%3==0
res++;
else if (px != py) {
p[px] = py; //如果不等則x y不在一個(gè)集合中
d[px] = d[y] - d[x];//d[x]+? %3 =d[y]%3 -> ?(d[px])=d[y]-d[x] 要使x y是同類則滿足這個(gè)方程
}//可以畫圖
}
else {
if (px == py && (d[x] - d[y] - 1) % 3)res++;//如果px=py 則x y在同一集合 x吃y 則d[x]%3 -d[y]%3==1 ->(d[x]-d[y]-1)%3=0;
else if (px != py) {
p[px] = py; //如果不在同一集合 則把x并入y集合中 (d[px]+? )%3=d[y]%3+1;
d[px] = d[y] + 1 - d[x];
}
}
}
}
cout << res << endl;
system("PAUSE");
return 0;
}
堆: 手寫堆
一.堆操作
- 插入一個(gè)數(shù)
2.求這個(gè)集合當(dāng)中的最小值
3.刪除最小值
上面三個(gè)是STL 中可以實(shí)現(xiàn)的 - 刪除任意一個(gè)元素
5.修改任意一個(gè)元素
后兩個(gè)操作只有手寫堆才可以實(shí)現(xiàn)
二.堆描述
堆是完全二叉樹 除了最后一層節(jié)點(diǎn)之外 上面所有節(jié)點(diǎn)都是滿的
最后一個(gè)節(jié)點(diǎn)從左到右排布
三.堆的構(gòu)造:
堆的一個(gè)點(diǎn)小于等于左右兒子(左右兒子大小不一定)
根節(jié)點(diǎn)為堆的最小值
注意下標(biāo)從1開始
四.堆存儲(chǔ)
使用一個(gè)一維數(shù)組存儲(chǔ)
x的做兒子: 2x
x的右兒子:2x+1;
五.核心操作
down
up
heap 堆 size 堆的大小
1. 插入操作
heap[++size]=x; up(size);
2.求當(dāng)前堆的最小值
heap[1] ,堆頂一定是最小的
3. 刪除最小值
用整個(gè)堆的最后一個(gè)元素覆蓋掉堆頂元素 size-- 再down
(因?yàn)橐痪S數(shù)組刪除頭非常困難,但是刪除尾部很容易)
heap[1]=heap[size];size--; dowx(1);
4. 刪除任意一個(gè)元素
heap[k]=heap[size];size--;down(k);up(k); //只會(huì)執(zhí)行down up 其中一個(gè)
5.修改任意一個(gè)元素
heap[k]=x;down(k);up(k);
void down(int u){
int t=u;
如果有左兒子 且 左兒子小于頂點(diǎn) 則把左兒子變成頂點(diǎn)
if(u*2<=size&&h[u*2]<h[t])t=u*2;
如果有右兒子 且 右兒子小于頂點(diǎn) 則把右兒子變成頂點(diǎn)
if(u*2+1<=size&&h[u*2+1]<h[t])t=u*2+1;
如果 u改變了 交換當(dāng)前最小值和u的值 便且再down一下t
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
void up(int u)
{
//u/2 同時(shí)包括了左二字和有兒子 2/2=1 3/2=1;
while(u/2&&h[u/2]>h[u]){
swap(h[u/2],h[u]);// 如果大了就交換
u/=2; //每次u往上走
}
}
例1 堆排序
ph[]從下標(biāo)到堆里 hp[]從堆到下標(biāo)里
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],size1;
int n,m;
void down(int u)
{
int t=u;
if(u*2<=size1&&h[u*2]<h[t])t=u*2;
if(u*2+1<=size1&&h[u*2+1]<h[t])t=u*2+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>h[i];
size1=n;
for(int i=n/2;i;i--)
down(i);
while(m--)
{
cout<<h[1]<<" ";
h[1]=h[size1];
size1--;
down(1);
}
return 0;
}
例2: 模擬堆
#include<bits/stdc++.h>
using namespace std;con1
const int N=100010;
int h[N],ph[N],hp[N],cnt;
void heap_swap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int u){
int t=u;
if(u*2<=cnt&&h[u*2]<h[t])t=u*2;
if(u*2+1<=cnt&&h[u*2+1]<h[t])t=u*2+1;
if(u!=t){
heap_swap(u,t);
down(t);
}
}
void up(int u)
{
while(u/2&&h[u]<h[u/2]){
heap_swap(u,u/2);
u/=2;
}
}
int main()
{
int n,m=0;//m當(dāng)前第幾個(gè)插入的數(shù)
cin>>n;
while(n--){
string op
int k,x;
cin>>op;
int k,x;
if(op=="I"){
cin>>x;
cnt++;
m++;
ph[m]=cnt;
hp[cnt]=m;
h[cnt]=x;
up(cnt);
}
else if(op=="PM")cout<<h[1]<<endl;
else if(op=="DM"){
heap_swap(1,cnt);
cnt--;
down(1);
}
else if(op=="D")
{
cin>>k;
k=ph[k];
heap_swap(k,cnt);
cnt--;
up(k);
down(k);
}else {
cin>>k>>x;
k=ph[k];
h[k]=x;
up(k);
down(k);
}
return 0;
}
哈希表 （散列表）
一、 存儲(chǔ)結(jié)構(gòu)
1.開放尋址法
2.拉鏈法
二瞧筛、 字符串哈希方式
大范圍的集合 映射到 從0~N
x mod 1e5 模要取一個(gè)質(zhì)數(shù) （沖突的概率欣魇臁）
可能會(huì)產(chǎn)生沖突
1.拉鏈法：開一個(gè)一維數(shù)組 存儲(chǔ)哈希的值
添加 找h(x) 插入到鏈上
查找 找h(x) 遍歷鏈看有沒有
- 開放尋址法
1.添加 先找到h[k] 如果h[k] 有人 則往后找 直到?jīng)]有人
2.查找 第k個(gè)坑位開始 從前往后找
如果當(dāng)前位置有人，是x 則找到
如果當(dāng)前位置有人较幌，不是x 則繼續(xù)找下一個(gè)
如果當(dāng)前位置沒人揍瑟，則x不存在
hash表的刪除一般不會(huì)直接刪除 一般都是 把刪除的元素做特殊的標(biāo)記
而且一般不會(huì)用到刪除操作
開放尋址法的核心操作
find函數(shù)：如果x在hash表中存在，則返回x的位置
如果x不存在則返回x應(yīng)該存儲(chǔ)的位置
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int mod=2e5+3;
int null =0x3f3f3f3f;
int h[N];
int find(int x)
{
int t=(x%mod+mod)%mod;//為了防止余數(shù)是負(fù)數(shù)
while(h[t]!=null&&h[t]!=x){//如果這個(gè)坑是空了 就不存在x了
//如果這個(gè)坑==x了 那就找到了
t++; //繼續(xù)找下一個(gè)坑
if(t==N) //如果到末尾了 那就從頭開始找
t=0;
}
return t; //返回值是 x應(yīng)該放的位置 或者是找到x的位置
}
int main()
{
int n;
cin>>n;
memset(h,0x3f,sizeof(h));//首先將數(shù)組置為null 作為判斷是否為空的標(biāo)志
while(n--){
string op;
int x;
cin>>op>>x;
if(op=="I"){
// h[x]=find(x);
h[find(x)]=x; // 返回的是x應(yīng)該放的位置 讓哈希表中的這個(gè)位置=x
}
else {
if(h[find(x)]==null)//返回的值如果是空 則沒有找到
cout<<"No"<<endl;
else cout<<"Yes"<<endl;//否則就是找到了 不存在別的情況
}
}
return 0;
}
二. 字符串哈希
字符串前綴哈希法
核心 在p 進(jìn)制的角度將一個(gè)字符串看成是一個(gè)數(shù)字
如何來定義每一個(gè)前綴的哈希
將字符串看成是P進(jìn)制數(shù)
不要某一個(gè)字符映射成0 因?yàn)?的p進(jìn)制還是0
假定不存在沖突 不考慮沖突
經(jīng)驗(yàn)值 p進(jìn)制為 p=131, mod 為2^64;
這里用usigned long long 來實(shí)現(xiàn) 溢出就是對(duì)mod取模
核心操作:
1.hash的處理
h[i]=h[i-1]p+str[i];
2.求 l 到 r 之間的字符串
h[R]-h[L]p^(R-L+1)
R-L+1=R-1-(L-2);
h[L-1] 從 p^0 ~ p^(L-2)
h[R] 從 p^0 ~p^(R-1)
預(yù)處理一個(gè)數(shù)的n次方
int p[N];
p[0]=1; //p的0次方為1;
for(int i=1;i<=n;i++)
p[i]=p[i-1]*p;
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int p=131;// 131 是 經(jīng)驗(yàn)值
const int N=1e5+10;
ull pow1[N],h[N];// unsigned long long 溢出 就是mod 2^64
char str[N];
ull hash1(int l,int r)
{
return h[r]-h[l-1]*pow1[r-l+1]; //核心操作
//求出l~r 區(qū)間內(nèi)的hash值
}
int main()
{
int n,m;
cin>>n>>m>>str+1;//注意從下標(biāo)1開始存儲(chǔ)字符
pow1[0]=1; // p的零次冪等于1
for(int i=1;i<=n;i++)
{
pow1[i]=pow1[i-1]*p;//對(duì)p的次方 進(jìn)行預(yù)處理操作
}
for(int i=1;i<=n;i++)
{
h[i]=h[i-1]*p+str[i];//核心操作 得到每個(gè)字符的hash值
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(hash1(l1,r1)==hash1(l2,r2))//如果兩個(gè)區(qū)間的hash值相等 則兩個(gè)字符串相同
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
重點(diǎn) C++的STL
vector
變長(zhǎng)數(shù)組
倍增的思想
系統(tǒng)為某一程序分配空間時(shí),所需時(shí)間與空間大小無(wú)關(guān)
與申請(qǐng)次數(shù)有關(guān)
#include<vector>
int main()
{
vector<int> a;// 定義一個(gè)vector
vector<int> a(10);//定義一個(gè)長(zhǎng)度為10的vector
vector<int> a(10,3);//長(zhǎng)度為10 每個(gè)元素為3
vector<int> a[10];//定義一個(gè)vector數(shù)組
注意 size();和empty();是所有容器都有的函數(shù)
時(shí)間復(fù)雜度為O(1);
a.size();//vector中元素的個(gè)數(shù)
a.empty();//vector是否為空
并不是所有容器都有clear();比如隊(duì)列就沒有
a.clear(); //清空vector
a.front(); //返回vector的第一個(gè)數(shù) .
a.back();//返回vector的第二個(gè)數(shù)
a.push_back();//向vctor的最后插入一個(gè)樹
a.pop_back();//刪除vector的最后一個(gè)樹
//迭代器
a.begin();// vector的第0個(gè)數(shù) a[0]
a.end();//vector的最后一個(gè)數(shù)的后面一個(gè)數(shù)a[a.size()];
遍歷方式
for(int i=0;i<10;i++)a.push_back(i);
1.for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
cout<<endl;
2.for(vector<int>::iterator iter=a.begin();i!=a.end();i++)
cout<<*i<<" ";
cout<<endl;
3.范圍遍歷(C++11)
for(auto x:a)cout<<x<<' ';
cout<<endl;
vector 同樣支持比較 大于小于等于 按照字典序
vector<int> a(10,3);//長(zhǎng)度為10 每個(gè)元素為3
vector<int> b(10,3);
if(a==b)
cout<<"a=b"<<endl;
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
return 0;
}
pair
pair<int,string> p;
p.first;//取得第一個(gè)元素
p.second;//取得第二個(gè)元素
支持比較運(yùn)算 按照字典序 以 first 為第一關(guān)鍵字,以second為第二關(guān)鍵字
p=make_pair(10,"yxc");
C++11 :p={20,"abc"};
pair<int,pair<int,int> > //有三個(gè)屬性時(shí)
與結(jié)構(gòu)體相比 可以自帶比較函數(shù)
string
字符串
size();
empty();
clear();
length();// 作用和size一模一樣
支持加減
string a="WD";
a+="def";//加上一段字符串
a+="b"; //加上一個(gè)字符
cout<<a.substr(1,3)<<endl;
cout<<substr(1,3)<<endl;
substr(); 功能返回字符串的一個(gè)字串
第一個(gè)參數(shù): 字符串中的一個(gè)下標(biāo)
第二個(gè)參數(shù):從這個(gè)下標(biāo)開始多少長(zhǎng)度
第二個(gè)參數(shù)可以省略,返回到末尾的字串
使用printf輸出
printf("%s\n",a.c_str());
c_str();返回字符串存儲(chǔ)的第一個(gè)地址
queue
隊(duì)列
push();//向隊(duì)尾插入元素
front();//返回隊(duì)頭元素
back();//返回隊(duì)尾元素
pop(); //彈出隊(duì)頭元素
size();
empty();
無(wú)clear();函數(shù)
如果想1清空一個(gè)q 直接重新構(gòu)造一個(gè) q=queue<int>();
priority_queue
優(yōu)先隊(duì)列(堆)
push();//向堆中插入一個(gè)元素
top();//返回堆頂元素
pop();//彈出堆頂元素
一般默認(rèn)大根堆
也無(wú)clear函數(shù)
priority_queue<int> pq;
如果小變成小根堆
1. 插入的時(shí)候直接插入-x
2. 定義直接定義成小根堆
priority_queue<int,vector<int>,greater<int> >pq;
stack
棧
也無(wú)clear 函數(shù)
push();//向棧頂插入一個(gè)元素
top();//返回棧頂元素
pop(); //彈出棧頂元素
deque 加強(qiáng)版的vector
雙端隊(duì)列
隊(duì)頭隊(duì)尾都可以插入刪除
(加強(qiáng)版的vector)
size();
empty();
clear();
front();//查詢第一個(gè)元素
back();//查詢最后一個(gè)元素
push_back();//向隊(duì)尾插入一個(gè)元素
pop_back();//彈出隊(duì)尾元素
push_front();//向隊(duì)首插入一個(gè)元素
pop_front();//彈出隊(duì)首元素
支持隨機(jī)尋址
begin();
end();
deque功能十分強(qiáng)大 但是速度比較慢
set,map,multiset,multimap
基于紅黑樹實(shí)現(xiàn)的,動(dòng)態(tài)的維護(hù)一個(gè)有序的序列
紅黑樹是平衡二叉樹的一種
set<int> s;//不可語(yǔ)有重復(fù)元素
multiset<int> ms; 可以有重復(fù)元素
size();
empty();
clear();
insert();//插入一個(gè)數(shù)
find();//查找一個(gè)數(shù)
count();//返回一個(gè)數(shù)的個(gè)數(shù) set為1
erase():
(1)如果輸入一個(gè)數(shù)x 則刪除所有x
(2)如果輸入一個(gè)迭代器,則刪除這個(gè)迭代器
set的核心操作:
lower_bound();返回大于等于x的最小的迭代器
upper_bound(); 返回大于x的最小的迭代器
如果沒有則返回end();
map
multimap
insert();//輸入的參數(shù)是一個(gè)pair
erase();//輸入的參數(shù)是pair或者迭代器
可像數(shù)組一樣使用map
map<string,int> m;
a["WD"]=1;
cout<<a["WD"]<<endl;
支持lower_bound();upper_bound();
unordered_set
unordered_map
unordered_multiset
unordered_multimap
哈希表實(shí)現(xiàn)
內(nèi)部無(wú)序
和上面操作一樣 時(shí)間復(fù)雜度是o(1),比上面速度快
不支持 lower_bound();upper_bound();
不支持 迭代器的++ --;
bitset 位存儲(chǔ)
壓位
bitset<10000> s;
~,&^|;
>>,<<
==,!=;
[];
count();返回有多少個(gè)1
set(); 把所有為置為1
set(k,v); 把第k位變成v
reset();把所有位置0
