算法总结知识点
时间优化
阶乘和
//阶乘和，用打表法，预处理所有的阶乘mod1e9+7;
#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
const int maxn=1e5+9;
const int mod=1e9+7;
long long a[maxn];
int main()
{
long long ans=1;
for(int i=1;i<maxn;i++)
{
ans*=i;//可以写成a[i]=a[i-1]*i,a[1]=1;
ans%=mod;
a[i]=ans;
}
int n;
scanf("%d",&n);
long long sum=0;
for(int i=1;i<=n;i++)
{
int temp;
scanf("%d",&temp);
sum+=a[temp];
sum%=mod;
}
printf("%lld\n",sum);
return 0;
}
前缀和应用!
///求一段序列有多少是9的倍数
///1≤T≤10,1≤n≤100000,1≤Q≤100000,1≤l,r≤n,1≤a[i]≤32768
1≤T≤10,1≤n≤100000,1≤Q≤100000,1≤l,r≤n,1≤a[i]≤32768
#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
const int maxn=1e5+9;
const int mod=1e9+7;
int a[maxn],sum[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
memset(sum,0,sizeof(sum));
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
int temp;
scanf("%d",&temp);
if(temp%9==0) a[i]=1;
}
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",sum[r]-sum[l-1]);
}
}
return 0;
}
注意减法的前缀和，出现负数，要加上一个数，为被取模的数；
///两种写法！
///1，每次都取模，但是最后时候，要注意加上被取模的数，否则容易出现负数！
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
long long sum[maxn][109];
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
long long temp;
scanf("%lld",&temp);
for(int j=1;j<=100;j++)
{
long long tem=temp*temp;
sum[i][j]=sum[i-1][j]+tem;
sum[i][j]%=j;
}
}
while(q--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%lld\n",(sum[r][k]-sum[l-1][k]+k)%k);
}
return 0;
}
///2，就空间允许的话就最后一次取模！
///用前缀和一定要保证序列是递增的！
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
long long sum[maxn][109];
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
long long temp;
scanf("%lld",&temp);
for(int j=1;j<=100;j++)
{
long long tem=temp*temp;
sum[i][j]=(sum[i-1][j]+tem)%j;
}
}
while(q--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%lld\n",(sum[r][k]-sum[l-1][k]+k)%k);
}
return 0;
}
双指针扫描
///双指针扫描类似于快速排序！ https://codeforces.com/contest/1605/problem/B
while(l < r)
{
while(l < r && s[l] == '0') l++;
while(l < r && s[r] == '1') r--;
if(l >= r) break;
st.insert(l);
st.insert(r);
l++, r--;
}
///双指针扫描，用while()循环！
///
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
int a[maxn],b[maxn];
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
int l=1,r=m;
int cnt=0;
while(l<=n&&r>=1)
{
if(a[l]+b[r]>k) r--;
else if(a[l]+b[r]<k) l++;
else cnt++,l++,r--;
}
printf("%d\n",cnt);
return 0;
}
///双指针扫描，l与r指针可以从一头扫描，也可以从两头跑！
///给你一个有序序列(大小为n)，让你去找到一个区间
///[i,j] , 区间内所有数的和 sum >= m 求出满足这样要
///求的最小的区间长度
//代码部分，应该对的！
#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
const int maxn=2e5+9;
int a[maxn];
int sum[maxn];
inline int read()
{
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
int main()
{
int n=read();
int m=read();
for(int i=1;i<=n;i++) a[i]=read();
int l=1,r=1;
int sum=a[1];
int minx=inf;
while(l<=r&&r<=n) ///更改一下循环条件
{
if(sum<m)
{
r++;
sum+=a[r];
}
else
{
minx=min(minx,r-l+1);
l++;
sum-=a[l-1];
}
}
printf("%d\n",minx);
return 0;
}
标记数组
///对于给n个数字，随便挑两个数，使得成为7的倍数!
///分别找余数为0，1，2，3，4，5，6； 这样可以凑成7；
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+9;
long long vis[maxn];
int main()
{
int n;
scanf("%d",&n);
long long sum=0;
for(int i=1; i<=n; i++)
{
long long temp;
scanf("%lld",&temp);
vis[temp%7]++;
}
sum+=vis[0]*(vis[0]-1)/2;
sum+=vis[1]*vis[6];
sum+=vis[2]*vis[5];
sum+=vis[3]*vis[4];
printf("%lld\n",sum);
return 0;
}
///标记数组求前k个大小的数的和，时间比较卡，用快读优化后！
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
int vis[maxn];
inline int read()
{
int x=0;
char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
int main()
{
int n,k,op;
int temp;
n=read(),k=read(),op=read();
for(int i=1; i<=n; i++)
{
temp=read();
vis[temp]++;
}
long long ans=0,cnt=k;
if(op>0)
{
for(int i=5000000; i>=1; i--)
{
if(cnt>0)
{
if(cnt>=vis[i])
{
ans+=i*vis[i];
cnt-=vis[i];
}
else
{
ans+=cnt*i;
break;
}
}
else break;
}
}
else
{
for(int i=1; i<=5000000; i++)
{
if(cnt>0)
{
if(cnt>=vis[i])
{
ans+=i*vis[i];
cnt-=vis[i];
}
else
{
ans+=cnt*i;
break;
}
}
else break;
}
}
printf("%lld\n",ans);
return 0;
}
差分
离线算法
//把t组数据全部读入进去，然后利用结构体排序看是否，有些情况已经算过
//如阶乘把最大的算出来，那么小的阶乘就已经算过了！
贪心
活动安排，结构体排序，末尾时间降序！
//活动安排！
#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
const int maxn=1e6+9;
struct node
{
int st;
int en;
}; struct node e[maxn];
int cmp(node a,node b)
{
return a.en<b.en;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&e[i].st);
scanf("%d",&e[i].en);
}
sort(e+1,e+n+1,cmp);
int cnt=1,ans=1;
for(int i=2;i<=n;i++)
{
if(e[cnt].en<=e[i].st)
{
ans++;
cnt=i;
}
}
printf("%d\n",ans);
return 0;
}
二分
// 严谨的二分！
#include<bits/stdc++.h>
using namespace std;
#define N 2001010
int a[N];
int main()
{
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
int q;
cin >> q;
while(q--)
{
int k;
cin >> k;
int l = 1,r = n;
int ans;
while(l <= r)
{
int mid = l+r>>1;
if(a[mid] >= k) ans = mid,r = mid - 1;
else l = mid + 1;
}
if(a[ans] == k) cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}
///手写的二分还不知道够不够严谨，相同元素第一个！
int q=read();
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
if(q<=a[mid]) r=mid;
else l=mid+1;
}
if(a[r]==q) printf("%d ",r);
else printf("-1 ");
///还是用万能二分吧，好像有点问题！
///二分求函数零点!
#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double f(double x)
{
return a*x*x*x+b*x*x+c*x+d;
}
int main()
{
int t=read();
while(t--)
{
double l=-1000000000000,r=1000000000000;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
while(r-l>=0.0000001)
{
double mid=(l+r)/2;
if(f(mid)*f(l)<=0) r=mid;
else l=mid;
}
printf("%f\n",r);
}
return 0;
}
///改进写法！
while(r-l>1e-8)
{
double mid=(l+r)/2;
if(f(mid)==0)
{
ans=mid;
break;
}
else if(f(mid)*f(r)<0)
{
l=mid;
ans=mid;
}
else r=mid,ans=mid;
}
printf("%.6f\n",ans);
///P1873 [COCI 2011/2012 #5] EKO / 砍树;
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+9;
long long a[maxn];
long long n,m;
bool check(int mid)
{
long long ans=0;
for(int i=1;i<=n;i++)
{
if(a[i]-mid>0) ans+=a[i]-mid;
}
if(ans>=m) return true;
else return false;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
int ans=0;
int l=0,r=1e9+7;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
快速幂
typedef long long ll;
long long fpow(ll a,ll b,ll c)
{
ll ans=1;
a%=c;
while(b)
{
if(b&1) ans=(ans*a)%c;
a=(a*a)%c;
b>>=1;
}
return ans;
}
//判断b是否为奇数，2进制最后一位为1，则为奇数，&1，即可1
//b/=2,b>>=2;
dp
/// dp的时候要格外注意边界怎样的处理！
#include<iostream>
using namespace std;
int n,m,px,py;
const int dir[9][2] = {0,0,-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
long long dp[30][30];
int vis[30][30];
int main()
{
cin >> n >> m >> px >> py;
for(int i=0; i<9; i++)
{
int xx = px + dir[i][0];
int yy = py + dir[i][1];
if(xx <= n && xx >= 0 && yy <= m && yy >= 0) vis[xx][yy] = 1;
}
dp[0][0] = 1;
for(int i=1; i<=n; i++) if(!vis[i][0]) dp[i][0] = dp[i-1][0];
for(int j=1; j<=m; j++) if(!vis[0][j]) dp[0][j] = dp[0][j-1];
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(!vis[i][j]) dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
cout<<dp[n][m]<<endl;
return 0;
}
DFS
P1464 Function
#include<iostream>
using namespace std;
typedef long long ll;
ll f[30][30][30];
ll w(ll a,ll b,ll c)
{
if(a <= 0 || b <= 0 || c <= 0) return 1;
else if(f[a][b][c]) return f[a][b][c];
else if(a > 20 || b > 20 || c > 20)
{
f[a][b][c] = w(20,20,20);
}
else if(a < b && b < c) f[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else f[a][b][c] = w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
return f[a][b][c];
//w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1);
}
int main()
{
ll a,b,c;
while(cin >> a >> b >> c)
{
if(a == - 1 && b == -1 && c == -1) break;
ll a1 = a,b1 = b,c1 = c;
if(a > 20) a1 = 21;
if(b > 20) b1 = 21;
if(c > 20) c1 = 21;
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a1,b1,c1));
}
return 0;
}
P1157 组合的
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5+9;
int a[N],vis[N];
int n,k;
void dfs(int u,int last)
{
if(u == k+1)
{
for(int i=1; i<=k; i++) printf("%3d",a[i]);
putchar('\n');
return;
}
for(int i=last + 1; i<=n; i++)
{
if(!vis[i])
{
vis[i] = 1;
a[u] = i;
dfs(u+1,i);
vis[i] = 0;
}
}
}
int main()
{
cin >> n >> k;
dfs(1,0);
return 0;
}
//DFS遍历树!
#include<iostream>
#include<vector>
using namespace std;
vector<int> ve[100];
void dfs(int n)
{
cout<<n<<endl;
for(int i=0; i<ve[n].size(); i++) dfs(ve[n][i]);
//for(auto v : ve[n]) dfs(v);
}
int main()
{
ve[1].push_back(2);
ve[1].push_back(7);
ve[2].push_back(3);
ve[2].push_back(6);
ve[3].push_back(4);
ve[3].push_back(5);
ve[7].push_back(8);
ve[7].push_back(11);
ve[8].push_back(9);
ve[8].push_back(10);
dfs(1);
cout<<"-----------"<<endl;
return 0;
}
//BFS遍历树！
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> ve[100];
queue<int> qu;
void bfs()
{
while(!qu.empty())
{
int now = qu.front();
cout<<now<<endl;
qu.pop();
for(auto v : ve[now]) qu.push(v);
}
}
int main()
{
ve[1].push_back(2);
ve[1].push_back(7);
ve[2].push_back(3);
ve[2].push_back(6);
ve[3].push_back(4);
ve[3].push_back(5);
ve[7].push_back(8);
ve[7].push_back(11);
ve[8].push_back(9);
ve[8].push_back(10);
qu.push(1);
bfs();
return 0;
}
//八连通水渠！
//有两种方法有一点差别，不用标记数组，直接把地图'W'->'.';
//用标记数组每次都把搜索过的区域标记vis=1；
//https://www.luogu.com.cn/problem/P1596
//不用标记数组！
#include<bits/stdc++.h>
using namespace std;
const int maxn=109;
char mp[maxn][maxn];
int n,m;
int dir[8][2]={-1,0,1,0,0,-1,0,1,-1,-1,1,1,-1,1,1,-1};
void dfs(int x,int y)
{
//if(x==n&&y==m) return;
int nowx,nowy;
for(int i=0;i<8;i++)
{
nowx=x+dir[i][0];
nowy=y+dir[i][1];
if(nowx>=1&&nowx<=n&&nowy<=m&&nowy>=1)
{
if(mp[nowx][nowy]=='W')
{
mp[nowx][nowy]='.';
dfs(nowx,nowy);
}
}
}
return; //当dfs无处可去时会自动回溯，这个return写不写是一样的！
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='W')
{
ans++;
mp[i][j]='.';
dfs(i,j);
}
}
}
printf("%d\n",ans);
return 0;
}
//-----------------------------标记数组
#include<bits/stdc++.h>
using namespace std;
const int maxn=109;
char mp[maxn][maxn];
int vis[maxn][maxn];
int n,m;
int dir[8][2]={-1,0,1,0,0,-1,0,1,-1,-1,1,1,-1,1,1,-1};
void dfs(int x,int y)
{
//if(x==n&&y==m) return;
int nowx,nowy;
for(int i=0;i<8;i++)
{
nowx=x+dir[i][0];
nowy=y+dir[i][1];
if(nowx>=1&&nowx<=n&&nowy<=m&&nowy>=1)
{
if(mp[nowx][nowy]=='W'&&!vis[nowx][nowy])
{
mp[nowx][nowy]='.';
dfs(nowx,nowy);
}
}
}
return;//当dfs无处可去时会自动回溯，这个return写不写是一样的！
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='W')
{
ans++;
vis[i][j]=1;
dfs(i,j);
}
}
}
printf("%d\n",ans);
return 0;
}
//洛谷p1331 海战！
//先判断是否合法在深搜！
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+9;
int n,m;
bool f;
char mp[maxn][maxn];
int dir[4][2]= {-1,0,1,0,0,1,0,-1};
int vis[maxn][maxn];
bool check(int x,int y)
{
int cnt=0;
if(mp[x][y]=='#') cnt++;
if(mp[x+1][y]=='#') cnt++;
if(mp[x][y+1]=='#') cnt++;
if(mp[x+1][y+1]=='#') cnt++;
if(cnt==3) return false;
return true;
}
void dfs(int x,int y)
{
if(x==n&&y==m) return;
int nowx,nowy;
for(int i=0; i<4; i++)
{
nowx=x+dir[i][0];
nowy=y+dir[i][1];
if(nowx<=n&&nowx>=1&&nowy<=m&&nowy>=1)
{
if(mp[nowx][nowy]=='#'&&!vis[nowx][nowy])
{
vis[nowx][nowy]=1;
dfs(nowx,nowy);
}
}
}
}
int main()
{
memset(vis,0,sizeof(vis));
f=true;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%s",mp[i]+1);
int ans=0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(!check(i,j))
{
f=false;
break;
}
}
}
if(f==true)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(mp[i][j]=='#'&&!vis[i][j])
{
ans++;
vis[i][j]=1;
dfs(i,j);
}
}
}
printf("There are %d ships.\n",ans);
}
else printf("Bad placement.\n");
return 0;
}
对于DFS标记数组的微小差距
思路先对于边界跑一次dfs,把边界0,改变，然后对于每个0，再跑一次dfs；
//P1162 填涂颜色
//ac代码
//1 1 1
//1 0 1
//1 1 1
//对于此样例由于只有一个待搜索的区域，所以应该是 if(a[i][j]==0&&!vis[i][j]) vis[i][j]=1,a[i][j]=2,dfs(i,j);
// 若if(a[i][j]==0&&!vis[i][j]) dfs(i,j);
//1 1 1 因为对于此样例，除了本身没法走了，所以结果第二个，没有改变，不对，否则没有差别（no
//1 0 1
//1 1 1
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=100;
int a[maxn][maxn];
int vis[maxn][maxn];
int n;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void dfs1(int x,int y)
{
int nowx,nowy;
for(int i=0;i<4;i++)
{
nowx=x+dir[i][0];
nowy=y+dir[i][1];
if(nowx<=n&&nowx>=1&&nowy<=n&&nowy>=1)
{
if(a[nowx][nowy]==0&&!vis[nowx][nowy])
{
a[nowx][nowy]=-1;
vis[nowx][nowy]=1;
dfs1(nowx,nowy);
}
}
}
return;
}
void dfs2(int x,int y)
{
int nowx,nowy;
for(int i=0;i<4;i++)
{
nowx=x+dir[i][0];
nowy=y+dir[i][1];
if(nowx<=n&&nowx>=1&&nowy<=n&&nowy>=1)
{
if(a[nowx][nowy]==0&&!vis[nowx][nowy])
{
vis[nowx][nowy]=1;
a[nowx][nowy]=2;
dfs2(nowx,nowy);
}
}
}
return;
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
{
if(a[i][1]!=1&&!vis[i][1]) dfs1(i,1);
if(a[1][i]!=1&&!vis[1][i]) dfs1(1,i);
if(a[n][i]!=1&&!vis[n][i]) dfs1(n,i);
if(a[i][n]!=1&&!vis[i][n]) dfs1(i,n);
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// {
// printf("%d ",a[i][j]);
// }
// cout<<endl;
// }
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==0&&!vis[i][j])
{
a[i][j]=2;
vis[i][j]=1;
dfs2(i,j);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==-1) printf("0 ");
else printf("%d ",a[i][j]);
}
printf("\n");
}
/*
1 1 1 1 0
1 1 1 0 1
1 1 0 0 1
1 1 1 1 1
1 0 1 0 0
*/
return 0;
}
///01背包问题，dfs过不去，但有两个剪枝的操作！
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;
int v[N],w[N];
int T,M;
int ans;
void dfs(int i,int V,int W)
{
if(i == M+1)
{
if(V <= T) ans = max(ans,W);
return;
}
if(V > T) return;///可行性剪枝；
int s = W;
for(int j=i; j<=M; j++) s += w[j];
if(s < ans) return; ///最优性剪枝；
dfs(i+1,V+v[i],W+w[i]);
dfs(i+1,V,W);
}
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T >> M;
for(int i=1; i<=M; i++) cin >> v[i] >> w[i];
dfs(1,0,0);
cout<<ans<<endl;
return 0;
}
BFS
//luogu P1141 01迷宫
//对于结构体的不命明 是一个类型，q.push({i,j});
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+9;
char mp[maxn][maxn];
bool vis[maxn][maxn];
int n,m;
int ans[maxn][maxn];
struct node
{
int x,y;
};
queue<node> q;
vector<node> ve;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void bfs()
{
ve.clear();
int cnt=1;
while(!q.empty())
{
node now=q.front();
q.pop();
ve.push_back(now);
for(int i=0;i<4;i++)
{
int xx=now.x+dir[i][0];
int yy=now.y+dir[i][1];
if(xx<=n&&xx>=1&&yy>=1&&yy<=n)
{
if(!vis[xx][yy]&&mp[xx][yy]!=mp[now.x][now.y])
{
vis[xx][yy]=true;
q.push({xx,yy});
cnt++;
}
}
}
}
int Size=ve.size();
for(int i=0;i<Size;i++)
{
int x=ve[i].x,y=ve[i].y;
ans[x][y]=cnt;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!vis[i][j])
{
vis[i][j]=true;
q.push({i,j});
bfs();
}
}
}
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",ans[x][y]);
}
return 0;
}
// make_pair(),以及pair的使用
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> ve[100];
queue<pair<int,int>> qu;
///typedef pair<int,int> Points; 类
///queue<Points> qu;
int main()
{
qu.push(make_pair(1,1));
qu.push({2,2});
while(!qu.empty())
{
cout<<qu.front().first<<" "<<qu.front().second<<endl;
qu.pop();
}
return 0;
}
//ly的代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1004;
typedef pair <int, int> points;
bool vis[maxn][maxn];
char mp[maxn][maxn];
int n, m, ans[maxn][maxn], dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
queue <points> q;
vector <points> ve;
inline bool check(int xx, int yy) {
return xx >= 1 && xx <= n && yy >= 1 && yy <= n;
}
void bfs() {
ve.clear();
int cnt = 1;
while(!q.empty()) {
points now = q.front();
ve.push_back(now);
q.pop();
int x = now.first, y = now.second;
for(int i = 0; i < 4; i++) {
int xx = x + dir[i][0], yy = y + dir[i][1];
if(check(xx, yy) && (mp[x][y] ^ mp[xx][yy]) && !vis[xx][yy]) {
q.push(make_pair(xx, yy));
vis[xx][yy] = true;
cnt++;
}
}
}
int Size = ve.size();
for(int i = 0; i < Size; i++) {
int x = ve[i].first, y = ve[i].second;
ans[x][y] = cnt;
}
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> mp[i] + 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(!vis[i][j]) {
q.push(make_pair(i, j));
vis[i][j] = true;
bfs();
}
while(m--) {
int x, y;
cin >> x >> y;
cout << ans[x][y] << endl;
}
return 0;
}
//luogu p1451 dfs和bfs都过了！
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e2+9;
int n,m;
int ans;
char mp[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
int x,y;
};
queue<node> q;
void bfs()
{
ans++;
while(!q.empty())
{
node now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=now.x,y=now.y;
int xx=x+dir[i][0],yy=y+dir[i][1];
if(xx<=n&&xx>=1&&yy>=1&&yy<=m)
{
if(mp[xx][yy]!='0'&&!vis[xx][yy])
{
vis[xx][yy]=1;
q.push({xx,yy});
}
}
}
}
}
int main()
{
ans = 0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]!='0'&&!vis[i][j])
{
q.push({i,j});
vis[i][j]=1;
bfs();
}
}
}
printf("%d\n",ans);
return 0;
}
//luogu https://www.luogu.com.cn/problem/AT1350
//BFS与DFS都过了!
//DFS
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e3+9;
int n,m;
char mp[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
bool check(int x,int y)
{
return x<=n&&x>=1&&y<=m&&y>=1;
}
void dfs(int x,int y)
{
int xx,yy;
for(int i=0;i<4;i++)
{
xx=x+dir[i][0];
yy=y+dir[i][1];
if(check(xx,yy)&&mp[xx][yy]!='#'&&!vis[xx][yy])
{
vis[xx][yy]=1;
if(mp[xx][yy]=='g') return;
dfs(xx,yy);
}
}
return;
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='s')
{
vis[i][j]=1;
dfs(i,j);
}
if(mp[i][j]=='g') x=i,y=j;
}
}
if(vis[x][y]) printf("Yes\n");
else printf("No\n");
return 0;
}
//BFS
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e3+9;
int n,m;
char mp[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
int x,y;
};
queue<node> q;
bool check(int x,int y)
{
return x<=n&&x>=1&&y<=m&&y>=1;
}
void bfs()
{
while(!q.empty())
{
node now = q.front();
q.pop();
int x=now.x,y=now.y;
int xx,yy;
for(int i=0;i<4;i++)
{
xx=x+dir[i][0];
yy=y+dir[i][1];
if(check(xx,yy)&&mp[xx][yy]!='#'&&!vis[xx][yy])
{
vis[xx][yy]=1;
q.push({xx,yy});
}
}
}
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='g') x=i,y=j;
if(mp[i][j]=='s')
{
q.push({i,j});
vis[i][j]=1;
bfs();
}
}
}
if(vis[x][y]==1) printf("Yes\n");
else printf("No\n");
return 0;
}
对于BFS一些问题
#include<iostream>
using namespace std;
int main()
{ /// 部分代码而已，对于这个结构体的值不能更改！
while(!q.empty())
{
node now;
now=q.front();
q.pop();
if(now.a==b) return now.b;
now.b++;
for(int i=0;i<6;i++)
{
now.a=now.a+dir[i];//这个值更改会影响以前的值，所以方法为从新定义一个结构体q.push(newnode)，或者q.push({xx,yy})
q.push(now);
}
}
return 0;
}
快速排序
//随机值快排！
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
int a[maxn];
int __rand(int l,int r)
{
return rand()%(r-l+1)+l;
}
void Quick_sort(int l,int r)
{
if(l>=r) return;//这里l==r 有问题还不知道！
int i=l,j=r;
int k=a[__rand(l,r)];//k=a[(l+r)/2],也很快！
while(i<=j) //这里l<r 好像也可以！
{
while(i<=j&&a[j]>k) j--;
while(i<=j&&a[i]<k) i++;
if(i>j) break;
swap(a[i],a[j]);
i++,j--;
}
Quick_sort(l,j),Quick_sort(i,r);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Quick_sort(1,n);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
cout<<endl;
return 0;
}
//这里效率最好的快排组合 是：三数取中+插排+聚集相等元素,它和STL中的Sort函数效率差不多
//传入数组地址，已知道对那个进行排序！
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
int a[maxn],b[maxn];
int __rand(int l,int r)
{
return rand()%(r-l+1)+l;
}
void Quick_sort(int b[],int l,int r)
{
if(l>=r) return;
int i=l,j=r;
int k=b[__rand(l,r)];
while(i<=j)
{
while(i<=j&&b[j]>k) j--;
while(i<=j&&b[i]<k) i++;
if(i>j) break;
swap(b[i],b[j]);
i++,j--;
}
Quick_sort(b,l,j),Quick_sort(b,i,r);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
Quick_sort(a,1,n);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
printf("\n");
Quick_sort(b,1,n);
for(int i=1;i<=n;i++) printf("%d ",b[i]);
printf("\n");
cout<<endl;
return 0;
}
归并排序
桶排序，插入排序
///桶排序！
#include<bits/stdc++.h>
using namespace std;
int a[1009];
int cnt[1000009];
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
int maxx = 0;
for(int i=1; i<=n; i++)
{
cnt[a[i]]++;
maxx = max(maxx,a[i]);
}
for(int i=0; i<=maxx; i++) ///i=min；i<=max；i++； 这里枚举待排序数字的值域！
{
while(cnt[i])
{
cout<<i<<" ";
cnt[i]--;
}
}
cout<<endl;
return 0;
}
///插入排序！
void Insert_sort(int a[],int n)
{
for(int i=1; i<=n; i++) /// i=1,i=2,都可以！
{
for(int j=i-1; j>=1; j--)
{
if(a[j] <= a[j+1]) break;
else
{
swap(a[j],a[j+1]);
}
}
}
}
重载运算符
///sort 重载 < ;
struct node
{
int a,b;
int len2()
{
return a*a+b*b;
}
bool operator < (node o)
{
return len2() < o.len2();
}
// bool operator < (node o)
// {
// return a*a + b*b < o.a*o.a + o.b*o.b;
// }
} e[1009];
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define N 10010
struct node
{
int x,y,z;
bool operator < (const node & b) const
{
// bool operator < (const node & b) const
// {
// if(x != b.x) return x > b.x;
// else if(y != b.y) return y < b.y;
// return z < b.z;
// }
if(x == b.x && y == b.y) return z < b.z;
else if(x == b.x) return y < b.y;
return x > b.x;
}
}e[N];
///第一个数小的优先，第二个数大的优先，第三个数大的优先！
priority_queue<node> qu;
int main()
{
qu.push(node{3,2,1});
qu.push(node{1,2,3});
qu.push(node{1,3,2});
qu.push(node{1,3,1});
while(!qu.empty())
{
node now = qu.top();
qu.pop();
cout<<now.x<<" "<<now.y<<" "<<now.z<<endl;
}
///1 3 2;
///1 3 1;
///1 2 3;
///3 2 1;
return 0;
}
并查集
//刚开始每个元素祖先就是自己！
for(int i=1; i<=n; i++)
rt[i] = i;
xx = fin(x);
yy = fin(y);
//若xx与yy不相等，则x，y祖先不为同一个！
//令yy成为xx的祖先
if(xx != yy)
rt[xx] = yy;
//查询时若两个人为同一个祖先则证明有亲戚关系，否则不具有！
if(fin(x) == fin(y))
printf("YES\n");
else printf("NO\n");
//查询有多少个集合就找有多少个祖先即可！
//rt[i] = i;
//无路径压缩！ 添边与查询均为O（n）；
int fin(int n)
{
if(rt[n]==n)
return n;
return fin(rt[n]);
}
//有路径压缩！添边与查询均为O（1）；
int fin(int n)
{
if(rt[n]==n)
return n;
return rt[n]=fin(rt[n]);
}
st倍增表
https://www.jianshu.com/p/19a2cf1af279
//倍增表左闭右开！
st[i][0] = a[i];
st[i][j] = max(st[i][],)
#define rep(i,a,b) for (int i = a;i <= b;i ++)
int n,m;
void init() { ///预处理!
// 定义 st[i][j] 是从i开始，到i + 2^j这一段，即[i,i + 2^j]这一段中的最大/小值
rep(i,1,n) st[i][0] = a[i];
for (int j = 1;(1 << j) <= n;j ++) { // 遍历所有的j，j是一个很小的数字，最大值=log2(n)
rep(i,1,n - (1 << j) + 1) { // 在[1,n]区间范围内，确定j的情况下，把所有的i都遍历求值一遍
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); // 套公式
}
}
}
int query(int l, int r) ///查询！
{
int x = log2(r - l + 1); //以2为底，(r - l + 1)的对数！默认以e为底!
return max(st[l][x],st[r - (1 << x) + 1][x]);///由于下取整，所以保证区间不漏，故取两段的最大值！
}
///https://www.luogu.com.cn/problem/P3865
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9; /// 这里开成2倍！
int a[N];
int st[N][20];
#define INT_INF 0x7fffffff
int read()
{
int x = 0,f = 1;char c = getchar();
while(c<'0' || c>'9') {if(c == '-') f = -1;c = getchar();}
while(c>='0'&& c<='9') {x = (x << 3) + (x << 1) + (c ^ 48),c = getchar();}
return x*f;
}
int main()
{
int n = read(),m = read();
for(int i=1; i<=n; i++) a[i] = read(),st[i][0] = a[i];
for(int j=1; (1 << j) <=n; j++)
{
for(int i=1; i<=n-(1<<j)+1; i++) // i <= n,若数组开为原来2倍！
{
st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
while(m--)
{
int l = read(),r = read();
int x = log2(r - l +1);
int ans = max(st[l][x],st[r-(1<<x)+1][x]);
printf("%d\n",ans);
}
return 0;
}
线段树
离散化
树状数组
///树状数组 tree[i]管辖范围为2进制末尾0的个数的2次幂
///然后查询1101 是逐步去掉末尾1
///http://acm.hdu.edu.cn/showproblem.php?pid=1166 树状数组板子，可以用线段树！
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;
int tree[N];
char s[100];
inline void update(int pos,int x)
{
for(int i=pos; i<=N; i+=(i&-i)) ///lowbit(i) ?
{
tree[i] += x;
}
}
inline int query(int n)
{
int ans = 0;
for(int i=n; i; i-=(i&-i))
{
ans += tree[i];
}
return ans;
}
int main()
{
int t;
int cnt = 0;
scanf("%d",&t);
while(t--)
{
cnt++;
printf("Case %d:\n",cnt);
memset(tree,0,sizeof(tree));
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
int temp;
scanf("%d",&temp);
update(i,temp);
}
while(~scanf("%s",s+1))
{
if(s[1] == 'E') break;
if(s[1] == 'A')
{
int a,b;
scanf("%d%d",&a,&b);
update(a,b);
}
if(s[1] == 'S')
{
int a,b;
scanf("%d%d",&a,&b);
update(a,-b);
}
if(s[1] == 'Q')
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",query(b) - query(a-1));
}
}
}
return 0;
}
O(2)优化
#pragma GCC optimize(2)
图论
https://atcoder.jp/contests/abc225/tasks/abc225_d 火车那道题目！
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+9;
int fro[N],beh[N];
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
while(m--)
{
int op;
cin >> op;
int x,y;
if( op == 1)
{
cin >> x >> y;
beh[x] = y;
fro[y] = x;
}
else if(op == 2)
{
cin >> x >> y;
beh[x] = 0;
fro[y] = 0;
}
else if(op == 3)
{
int x;
cin >> x;
int cnt = 0;
///while(x != 0) x = fro[x],不对！;
while(fro[x] != 0) x = fro[x];
int car_front = x;
while(beh[x] != 0) x = beh[x],cnt++; //这里写成 x != 0,就不用循环结束后cnt++了！
cnt++; //循环里面 两种写法 x != 0 或 beh[x] != 0;
cout<<cnt<<" "<<car_front<<" ";
x = car_front;
while(beh[x])
{
x = beh[x];
cout<<x<<" ";
}
cout<<endl;
}
}
return 0;
}
//scanf("%d", &x);
//while (pre[x]) x = pre[x]; // pre数组储存的是x前面的车辆，suc后面的车辆！,找到车头！
//int cnt = 0, cur = x;
//while (cur) cnt++, cur = suc[cur];
//printf("%d ", cnt);
//printf("%d", x);
//while (suc[x]) x = suc[x], printf(" %d", x);
//printf("\n");
STL
//STL的嵌套！
//ATcoder B - Counting Arrays
//set< vector<int> > st;
#include<bits/stdc++.h>
using namespace std;
set<vector<int>>st;
vector<int> ve;
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N,L;
cin >> N;
while(N--)
{
ve.clear();
cin >> L;
for(int i=1; i<=L; i++)
{
int temp;
cin >> temp;
ve.push_back(temp);
}
st.insert(ve);
}
int ans = st.size();
cout<< ans <<endl;
return 0;
}
map<string,map<string,int>>mp;
cin >> n;
while(n--)
{
cin >> a >> b >> c;
mp[b][a] += c;
}
for(auto x=mp.begin(); x!=mp.end(); x++)
{
cout<<x -> first<<endl;
for(auto y=x->second.begin(); y!=x->second.end(); y++)
cout<< y -> first <<' '<<y -> second<<endl;
}
for(auto x : mp) //map自动类型遍历！
{
cout<<x.first<<endl;
for(auto y : x.first)
cout<<y.first<<' '<<y.second<<endl;
}
本篇文章为自己对于STL
1，首先是set
set有自动排序去重功能！
set里面插入元素用insert函数，对于t组数据要用clear()清零！
int a=s.size(),知道set容器元素个数！
set 遍历
set<int> :: iterator it;
for(it=st.begin();it!=st.end();it++)
{
printf("%d\n",*it);
cout<<*it<<endl;
}
2，map
可以想象一下映射，箭头->
map[a]++ a->1;
map[a]=1 a->1;
map[a]=b a->b;
map可以直接输出map中的元素如:map[2];
正常的map插入和查询都是logn的时间复杂度！
对于unordered_map <int, int> mp; 由于无序所以插入元素为o（1）查询为o（n）；
对于判断a[]数组与b[]数组是否完全相等的方法
map：
首先把b数组的每个数存进map然后循环遍历a把map[a[i]]--
如果map中不存在a[i]就不相等
用map来制作账号，与密码对应比结构体时间复杂度小,结构体方法就是从头到尾遍历一遍，而map查询时间复杂度是log(n)！
map中查询某个元素的个数mp.count(xx);
map<int,int> :: iterator it;
it->first it->second
mp.size();//map的尺寸大小！
#include<bits/stdc++.h>
using namespace std;
map<string,string> mp;
string s1,s2;
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
cin>>s1>>s2;
mp[s1]=s2;
}
while(q--)
{
string temp;
cin>>temp;
if(mp.count(temp)) cout<<mp[temp]<<endl;
else printf("-1\n");
}
return 0;
}
3，string与char的差别好处
1,char s[10] 在求长度上用 len=strlen(s);
而string 为 int len=s.length();
读入一整行字符串时候不同
char [10] cin.getline(s,10);
string s getline(cin,s);
string t; t = s; t == s ?;
4，vector
vector<int> ans,ve;
向vector中加入元素 ve.push_back(n),n为你要加入的元素如 ve.push_back(a[i] ^ b[j]);
也可以 cin >> ve[i];
vector的去重写法
先对于vector排序:
sort(ve.begin(), ve.end());
ve.erase(unique(ve.begin(), ve.end()), ve.end());
先对ve中的元素排序如 1 2 2 2 3 3 4 4
那么unique会返回不重复元素的下一个下标，然后用erase进行擦除即可
过程 1 2 3 4 2 2 3 4；
vecotr存边的理解如：
ve[u].push_back(v);
ve[v].push_back(u);
如：u=3,v=2;
即，ve[3]中添加元素2，用Size=size[3](),即可知道，ve[3]中元素的个数；
对于二维vector的清空，每第一维度的每个容器都要清空,即用多少清多少！
eg; vector<int> ve[maxn];
for(int i=1;i<=n;i++) ve[i].clear();
vector与数组的区别还不太清楚
以后再说：如
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ve[cnt++]=a[i]^b[j];
与 ve.push_back(a[i]^b[j]) 有着细微的差别！
对于next_permutation函数a+1,a+n+1,bool类型，若存在新的排列，会排列然后返回true，否则返回false！
#include<bits/stdc++.h>
using namespace std;
int main()
{
for(int i=1;i<=8;i++) a[i]=i;
for(int i=1;i<=8;i++) printf("%d ",a[i]);
cout<<endl;
while(next_permutation(a+1,a+9))
{
for(int i=1;i<=8;i++)
{
printf("%d%s",a[i],i==8?"\n":" ");
}
}
return 0;
}
c++
for(auto a:b)中b为一个容器，效果是利用a遍历并获得b容器中的每一个值，但是a无法影响到b容器中的元素。
for(auto &a:b)中加了引用符号，可以对容器中的内容进行赋值，即可通过对a赋值来做到容器b的内容填充。
//set 的 遍历，auto，简化了！
for(auto it = s.begin(); it != s.end(); it++)
{
cout<<*it<<endl;
}
class类
#include<cstdio>
#include<iostream>
using namespace std;
class point
{
public:
void setpoint(int x,int y)
{
posx = x;
posy = y;
}
void printpoint()
{
printf("%d %d\n",posx,posy);
}
private:
int posx,posy;
};
int main()
{
point m;
m.setpoint(20,19);
m.printpoint();
cout<<m.posx<<" "<<m.posy<<endl;//私人的无法访问，只能在poin
return 0;
}
[(1条消息) c++笔记：类class及相关知识点_空名_Noname的博客-CSDN博客](https://blog.csdn.net/qq_45764251/article/details/113784167?ops_request_misc=&request_id=&biz_id=102&utm_term=class 里面取反&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-5-113784167.pc_search_result_hbase_insert&spm=1018.2226.3001.4187)
查看26道真题和解析
