not thing
原题链接：69142.e
2025-10-11 19:03:23
发布于：广东
24阅读
0回复
0点赞
辗转相除法
long long g(long long a,long long b){
if(a%b==0){
return b;
}
return g(b,a%b);
}
埃氏质数
int a[11111111]
void s(){
a[1]=1;
for(int i=2;i*i<=11111111;i++){
if(a[i]==0){
for(int j=2*i;j<=11111111;j+=i){
a[j]=1;
}
}
}
}
队列《queue》
创建队列queue<int >q;
q.push(x);入队
q.pop();出队
q.front();队首
q.back();队尾
q.empty();判空
q.size();长度
前缀和
#include<bits/stdc++.h>//5 3 1 2 3 4 5 1 5 2 3 3 5
using namespace std;
int n,a[111111],q,w,r,t,b[111111];
int main(){
cin>>n>>r;
for(int i=1;i<=n;i++){
cin>>a[i];
}
b[1]=a[1];
for(int i=2;i<=n;i++){
b[i]=b[i-1]+a[i];
}
for(int i=1;i<=r;i++){
cin>>q>>w;
cout<<b[w]-b[q-1]<<endl;
}
}
差分
#include<bits/stdc++.h>//5 3 1 2 3 4 5 1 5 2 3 3 5
using namespace std;//6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1
int n,a[111111],q,w,d,r,t,b[111111];
int main(){
cin>>n>>r;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
b[i]=a[i]-a[i-1];
}
for(int i=1;i<=r;i++){
cin>>q>>w>>d;
b[q]+=d;
b[w+1]-=d;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+b[i];
cout<<a[i]<<" ";
}
}
前缀
b[i]=b[i-1]+a[i]//求前缀和数组a[],s[],用i表示某一项
b[w]-b[q-1]//求[l,r]的和
差分
b[i]=a[i]-a[i-1]//差分数组的构建
b[q]+=d;//差分变化
b[w+1]-=d;//差分变化
a[i]=a[i-1]+b[i];//差分还原
文件读取
int main(){
freopen("x.in","r",stdin);
freopen("x.out","r",stdout);
//代码放着
fclose(stdin);
fclose(stdout);
}
深度搜索
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ans,t,sx,sy,fx,fy;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
/////////右下 左上
int mp[111][111];//地图
bool vis[111][111];//标记
bool f=false;
void dfs(int x,int y){//x,y==当前坐标
vis[x][y]=1;
if(x==fx&&y==fy){//当前在不在终点
f=1;
return ;
}
for(int i=0;i<4;i++){
//下一个位置在哪
int nx=x+dx[i];
int ny=y+dy[i];
//判断能不能走
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]==0&&vis[nx][ny]==0){
vis[nx][ny]=1;
dfs(nx,ny);
vis[nx][ny]=0;
}
}
}
int main(){
cin>>n>>m>>sx>>sy>>fx>>fy;
dfs(sx,sy);
}
广度优先
#include<bits/stdc++.h>
using namespace std;
char mp[1111][1111];
bool vis[1111][1111];
int dx[]={0,0,1,-1};
int dx[]={1,-1,0,0};
int n,m;
struct node{
int x,y,step;
};
void bfs(int x,int y){
queue<node>q;
q.push({x,y,0});
vis[x][y]=1;
while(!q.empty()){
node u=q.front();
q.pop();
if(u.x==n&&u.y==m) {
cout<<u.step;
break;
}
for(int i=0;i<4;i++){
node v;
v.x=u.x+dx[i];
v.y=u.y+dy[i];
if(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&mp[v.x][v.y]=='.'&&!vis[v.x][v.y]){
v.step=u.step+1;
vis[v.x[v.y]=1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
}
这里空空如也
有帮助，赞一个