问题标题: c++常见模板---更新(冲150赞！——感谢大家

Question

173

李牧晓

中级天翼

一、双指针判断回文字符串

bool hw2(string s){
    int i=0,j=s.size()-1;
    while(i<=j){
        if(s[i]!=s[j]){
	        return 0;
	    }
	    i++;
	    j--;
    }
    return 1;
}

二、判断质数

bool zs(int n){
	if(n==1){
		return 0; 
	}
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

三、截取单词

s=" "+s+" ";//保证每个单词都被空格包围
for(int i=0;i<s.size();i++){
    if(s[i]==' '){//每遇到一个空格
        word[cnt++]=s.substr(p+1,i-p-1);//利用空格位置截出一个单词
        p=i;
    }
}

四、字符串转数字

int n=0;
for(int i=0;i<s.size();i++){
    n=n*10+s[i]-'0';
}

五、数字转字符串

while(n){
    s=char(n%10+48)+s;
    n/=10;
}

李牧晓在2022-02-08 21:47:39追加了内容

啊啊啊啊，臧老师赞我了！！！

李牧晓在2022-02-09 11:27:51追加了内容

六、最小公倍数

for(int i=max(a,b);i<=a*b;i++){
	if(i%a==0&&i%b==0){
		cout<<i<<" ";
		break;
	}
}

七、最大公约数（辗转相除法）

while(a%b!=0){
	r=a%b;
	a=b;
	b=r;
}
cout<<b;

李牧晓在2022-02-09 11:29:09追加了内容

第六个缩进多了，复制后自己调一下哈~

李牧晓在2022-02-24 22:45:10追加了内容

/*int hs(int n){

int s=1;

for(int i=1;i<=n;i++){

s*=i;

}

return s;

}

1. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k第一次出现时的位置，找不到则返回-1

int BinarySearch(int a[], int k, int l, int r) {

int left = l, right = r, mid;

while(left<right) { //注意不能写等号，否则可能**循环

mid = left+(right-left)/2;

if(a[mid]<k)

left = mid+1;

else

right = mid;

}

if(a[right]==k) return right;

return -1;

}

2. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k最后一次出现时的位置，找不到则返回-1

int BinarySearch(int a[], int k, int l, int r) {

int left = l, right = r, mid;

while(left<right) { //注意不能写等号，否则可能**循环

mid = left+(right-left+1)/2;

if(a[mid]<=k)

left = mid;

else

right = mid-1;

}

if(a[left]==k) return left;

return -1;

}

左：

l+(r-l)/2

右：

l+(r-l+1)/2

二分查找

void mer(int l,int r){

if(l==r)return ;

int mid=(l+r)/2;

mer(l,mid);

mer(mid+1,r);

int i=l,j=mid+1,cnt=l;

while(i<=mid&&j<=r){

if(a[i]<a[j])b[cnt++]=a[i++];

else b[cnt++]=a[j++];

}

while(i<=mid){

b[cnt++]=a[i++];

}

while(j<=r){

b[cnt++]=a[j++];

}

for(int i=l;i<=r;i++){

a[i]=b[i];

}

} 归并排序

int cmp(int x,int y){

return x<y;

}

void qqs(int l,int r){

int i=l,j=r,k=a[(l+r)/2];

while(i<=j){

while(cmp(a[i],k))i++;

while(cmp(k,a[j]))j--;

if(i<=j){

swap(a[i],a[j]);

i++;j--;

}

if(l<j)qqs(l,j);

if(i<r)qqs(i,r);

}

void qs(int l,int r){

int i=l,j=r,k=a[(l+r)/2];

while(i<=j){

while(a[i]<k)i++;

while(a[j]>k)j--;

if(i<=j){

swap(a[i],a[j]);

i++;j--;

}

if(l<j)qs(l,j);

if(i<r)qs(i,r);

}快排

long long f[100000000]

void ss(int n){

f[1]=1;f[0]=1;

for(int i=2;i*i<=n;i++){

if(!f[i]){

for(int j=i;j<=n/i;j++){

f[i*j]=1;

}

int a[10005],b[10005],c[10005],n;

string f[10005];

string ad(string s1,string s2s){

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

a[0]=s1.size();

b[0]=s2.size();

c[0]=max(a[0],b[0]);

for(int i=1;i<=a[0];i++){

a[i]=s1[a[0]-i]-'0';

}

for(int i=1;i<=a[0];i++){

b[i]=s2[b[0]-i]-'0';

}

int jw=0;

for(int i=1;i<=c[0];i++){

c[i]=a[i]+b[i]+jw;

jw=c[i]/10;

c[i]%=10;

}

if(jw>0){

c[0]++;

c[c[0]]=1;

}

string s="";

for(int i=c[0];i>=1;i--){

s+=char(c[i]+'0');

}

return s;

}

int ss(int x){

int i;

if(x<=0)return 0;

if(x==1)return 0;

for(i=2;i*i<=x;i++){

if(x%i==0)return 0;

}

return 1;

}

int dx(int m){

int x=0,y;

y=m;

while(y){

x=x*10+y%10;

y/=10;

}

if(m==x)return 1;

return 0;

}

int gcd(int m,int n){

int r;

while(n){

r=m%n;

m=n;

n=r;

}

return m;

}

int gcd(int a, int b){

return a % b ? gcd(b, a % b) : b;

}

int lcm(int a, int b){

return a * b / gcd(a, b);

}

int fl(int n){

while(n){

int sum+=n%10;

n/=10;

}

return sum;

}

int tgs(int x)

{

int p,r;

if(x<10)

{

p=x*x;

r=p%10;

if (x==r)

{

return 1;

}

else

{

return 0;

}

else if(x<100)

{

p=x*x;

r=p%100;

if (x==r)

{

return 1;

}

else

{

return 0;

}

else if(x<1000)

{

p=x*x;

r=p%1000;

if (x==r)

{

return 1;

}

else

{

return 0;

}

else if(x<10000)

{

p=x*x;

r=p%10000;

if (x==r)

{

return 1;

}

else

{

return 0;

}

else if(x<100000)

{

p=x*x;

r=p%100000;

if (x==r)

{

return 1;

}

else

{

return 0;

}

//

int a[200+10],b[200+10],c[200+10];

string ad(string as,string bs){

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

int al=as.size(),bl=bs.size();

int cl=max(al,bl)+1;

for(int i=1;i<=al;i++){

a[i]=as[as.size()-i]-'0';

}

for(int i=1;i<=bl;i++){

b[i]=bs[bs.size()-i]-'0';

}

string cs;

for(int i=1;i<=cl;i++){

c[i]+=a[i]+b[i];

c[i+1]=c[i]/10;

c[i]%=10;

}

while(c[cl]==0&&cl>1)cl--;

for(int i=cl;i>=1;i--){

cs+=c[i]+'0';

}

return cs;

}

int zis(int n)

{

if(n<=1) return 0;

int num;

for(int i=2;i*i<=n;i++)while(!(n%i))num=i,n/=i;

if(n>1)num=n;

return num;

}

int cmp(const int &x,const int &y){

return x>y;

}

*/

李牧晓在2022-03-12 00:05:21追加了内容

沈老师也赞我了！

李牧晓在2022-03-12 00:05:51追加了内容

拜托！点赞我的老师真的超帅的好吗！？

李牧晓在2022-04-12 22:40:06追加了内容

呜呜呜，真的没有人看了，我真的是小透明了，浅浅顶一下吧

李牧晓在2022-04-13 19:44:12追加了内容

！！！我真的！！！太激动了！！

李牧晓在2022-04-13 19:44:23追加了内容

！！！我真的！！！太激动了！！

李牧晓在2022-04-22 19:17:18追加了内容

赞赞点一点！~

李牧晓在2022-05-23 22:08:25追加了内容

这个帖已经掉到十万八千里之外了

李牧晓在2022-07-04 12:00:21追加了内容

搜索与回溯的框架

void Search(int x,int y){  //从(x,y)处往外搜
    for(int i=1;i<=所有可能;i++){//枚举所有的可能**
        if(到达目的点)return
        if(满足条件){//约束条件
            记录状态
            dfs(下个点的位置)  //递归搜索
            状态恢复
        }
     }
}

李牧晓在2023-01-07 09:15:36追加了内容

路过的就点个赞吧已经没有人看这个贴了吧

李牧晓在2023-02-19 23:34:38追加了内容

标准的Floyd：

memset(dis, 0x3f, sizeof(dis));
for(int i=1; i<=m; i++)
	dis[u][v] = dis[v][u] = w;
for(int k=1; k<=n; k++)
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(dis[i][k]+dis[k][j]<dis[i][j])
				dis[i][j] = dis[i][k]+dis[k][j];

Floyd算法判断两点是否连通：

for(int i=1; i<=m; i++) 
{
  cin >> u >> v;
  f[u][v] = true;
}
for(int k=1; k<=n; k++) 
{
  for(int i=1; i<=n; i++)
  {
    for(int j=1; j<=n; j++)
    {
      f[i][j] = f[i][j] || f[i][k] && f[k][j];
    }
  }
}

李牧晓在2023-02-19 23:37:30追加了内容

并查集:

void init(){
	for(int i=1;i<=n;i++)
    	fa[i]=i;
}//初始化

int find(int x){	//返回x的代表 
	if(fa[x]==x) return fa[x];
	return fa[x]=find(fa[x]);//将find(fa[x]值作为参数传给fa[x] 优化 不然下次再递归到x时，还要继续递归 
}//返回x的集合代表

//将x和y合并
void unit(int x,int y){//将x和y合并 
	x=find(x);
	y=find(y);
	if(x==y) return ;//如果已经相同了不需要再合并了 
	fa[y]=x;//x和y此时已经表示各自集合的代表了 	令y的代表为x 
}

//判断x和y是否属于同一个集合
bool same(int x,int y){//判断x和y是否属于同一个集合 
	return find(x)==find(y);
}

李牧晓在2023-02-19 23:38:13追加了内容

bfs:

//bfs模板
bfs(st){
	q.push(st);//起点入队 
	vis[st]=true;//起点已访问 
	while(!q.empty()){//当队列不为空 
		h=q.front();//取对首元素 
		q.pop();	//对首出队 
		if(h==ed) return ;//找到终点	结束 
		for(int i=1;i<=n;i++){	//枚举当前对首的点能够访问的点 
			if(!vis[nxt]){//如果可以访问 
				q.push(nxt);//入队 
				vis[nxt]=true;//该点已访问 
			}
		}	
	}
}

李牧晓在2023-02-19 23:39:24追加了内容

vector:

//vector相关函数
a.push_back(x);//在末尾添加元素x
a.pop_back();//删去末尾元素
a.size();//数组长度
a.erase();//删除a中间的某个元素，要用迭代器。
a[idx];//引用位置idx元素

李牧晓在2023-02-19 23:40:16追加了内容

queue:

头文件: #include < queue >
定义: queue< 数据类型 > q;//创建 -一个空队列q
出队: q. pop();
入队: q. push(元素);
取队首: q.front();
判断队空: q. empty();

李牧晓在2023-02-19 23:42:24追加了内容

二分查找：

//1. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k第一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) { 
    int left = l, right = r, mid; 
    while(left<right) {   //注意不能写等号，否则可能**循环
	mid = left+(right-left)/2; 
	if(a[mid]<k)
	    left = mid+1;
	else
	    right = mid;
    }
    if(a[right]==k) return right;
    return -1;
}

//2. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k最后一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) { 
    int left = l, right = r, mid; 
    while(left<right) {  //注意不能写等号，否则可能**循环
	mid = left+(right-left+1)/2; 
	if(a[mid]<=k)
	    left = mid;
	else
	    right = mid-1;
    }
    if(a[left]==k) return left;
    return -1;
}

李牧晓在2023-02-19 23:43:29追加了内容

回溯法：

//回溯法框架
void Search(int k) {
    if(到目的地) 输出解                 //边界条件
    else
        for (i=1;i<=算符总数;i++)      //枚举所有可能**
            if (满足条件){             //约束条件
                保存结果和状态
                Search(k+1);          //递归搜索
                恢复保存结果之前的状态  //状态恢复
            }
        }
}

李牧晓在2023-02-19 23:45:08追加了内容

迷宫问题：

//1. 边界条件（递归的终点）
//当到达出口 (tx,ty) 时结束
if(x==tx && y==ty) {
    输出解/计数/标记；    
    return;
}

//2. 枚举所有可能**
//从（x,y）往上、下、左、右分别探索

dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x+1,y-1);

//或

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
for(int i=0;i<4;i++){
    int nx=x+dir[i][0],ny=y+dir[i][1];
    dfs(nx,ny);
}

/*
3. 约束条件
1） 不能走到障碍处
这可通过输入的地图信息来判断。比如将地图信息用一个二维数组map[x][y]来存储，map[x][y] = 1表示障碍，map[x][y] = 0表示道路。

2） 不能走出地图边界
如果地图的大小为m*n，且左上角格子下标为（1,1），则到达的坐标（x,y）要满足1<=x<=m, 1<=y<=n

3） 已经走过的位置不能再走
已经走过的位置我们可以通过一个全局的二维数组vis[x][y]来记录。其中可以用vis[x][y] = 1表示(x, y)这个位置已经走过，vis[x][y] = 0表示(x, y)这个位置未走过。
*/

if(map[x][y]==0 && vis[x][y]==0 && x>=1 && x<=m && y>=1 && y<=n){
    (x,y)可以走;
}

李牧晓在2023-02-19 23:47:14追加了内容

八皇后：

//八皇后代码实现(标准)

#include <iostream>
using namespace std;
int a[10], b[10], c[20], d[20], cnt;
//a行， b列， c主， d副 
void print() {
    for(int i=1; i<=8; i++) {
        cout << a[i] <<' ';
    }
    cout << endl;
}
void dfs(int i) {//给第i层放皇后 
    if(i==9) {
        cnt++;
        if(cnt<=5)
            print();
    }
    for(int j=1; j<=8; j++) {
        if(!b[j] && !c[i-j+8] && !d[i+j]) {
            a[i] = j;
            b[j] = true;
            c[i-j+8] = true;
            d[i+j] = true;
            dfs(i+1);
            b[j] = false;
            c[i-j+8] = false;
            d[i+j] = false;
        } 
    }	
} 
int main() {
    dfs(1);
    cout << cnt;
    return 0;
}

李牧晓在2023-02-19 23:48:33追加了内容

前缀和：

for(int i=1;i<=n;i++)
   sum[i]=sum[i-1]+a[i];

李牧晓在2023-02-24 23:40:29追加了内容

Dijkstra:

int n;
int cost[MAXN][MAXN];
bool found[MAXN];
int dis[MAXN];
void Dijkstra(int s) {
    memset(found, false, sizeof(found));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    while(true) {
        int u = -1;
        for(int i=1; i<=n; i++)
            if(!found[i]&&(u==-1||dis[i]<dis[u])) 
                u = i;
        if(u==-1)   return;
        found[u] = true;
        for(int i=1; i<=n; i++) 
//          if(cost[u][i]<INF) 
                dis[i] = min(dis[i], dis[u]+cost[u][i]);
    }
}

李牧晓在2023-02-24 23:41:16追加了内容

Prim:

int MST_prim(){
    int ans=0;
    memset(dis,0x3f,sizeof(dis));
    memset(found,false,sizeof(found));
    dis[1]=0;
    while(1){
        int u=-1;
        for(int i=0;i<=n;i++){
            if(!found[i]&&(u==-1||dis[i]<dis[u])){
                u=i;
            }
        }
        if(u==-1) break;
        found[u]=true;
        ans+=dis[u];
        for(int i=0;i<=n;i++){
            if(!found[i]&&g[u][i]<dis[i]){
                dis[i]=g[u][i];
            }
        }
    }
    return ans;
}

李牧晓在2023-02-24 23:41:51追加了内容

90赞啦~

感谢大家的支持

冲一冲突破100吧~

李牧晓在2023-03-20 23:01:36追加了内容

顶一下啦

李牧晓在2023-03-21 18:42:24追加了内容

Prim算法模板：

int MST_prim(){
	int ans=0;
	memset(dis,0x3f,sizeof(dis));
	memset(found,false,sizeof(found));
	dis[1]=0;
	while(1){
		int u=-1;
		for(int i=0;i<=n;i++){
			if(!found[i]&&(u==-1||dis[i]<dis[u])){
				u=i;
			}
		}
		if(u==-1) break;
		found[u]=true;
		ans+=dis[u];
		for(int i=0;i<=n;i++){
			if(!found[i]&&g[u][i]<dis[i]){
				dis[i]=g[u][i];
			}
		}
	}
	return ans;
}

李牧晓在2023-03-21 18:43:40追加了内容

拓扑排序算法模板：

int n,m;
vector<int> g[MAXN];
queue<int> q;
int f[MAXN],in[MAXN];

void Topsort(){
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int t=q.front();
		cout<<t<<" ";
		q.pop();
		for(int i=0;i<g[t].size();i++){
			int idx=g[t][i];
			if(--in[idx]==0){
				q.push(idx);
			}
		}
	}
}

在这里道个歉，Prim发了两遍~

李牧晓在2023-03-21 18:45:42追加了内容

十进制数转化为k进制：

#include <iostream>
using namespace std;
string s="0123456789ABCDEFGHIJ";
string ans;
int main(){
    int n,k;
    cin>>n>>k;
    while(n){
        ans=s[n%k]+ans;
        n/=k;
    }
    cout<<ans;
    return 0;
}

李牧晓在2023-03-21 21:03:47追加了内容

纪念一下！~

李牧晓在2023-03-21 21:27:38追加了内容

大家一起努力！

李牧晓在2023-03-28 21:54:56追加了内容

归并排序：

//归并排序在于利用另一个数组进行排序。利用二分查找的思想来实现。一开始二分二分从第一个开始在一个范围里进行排序，使得在这一个区域里所有的数字以升序排列。返回这个序列给上一次调用，然后与上一层调用在以升序。以此类推到最后则调用结束。
#include<iostream>

using namespace std;

int a[101],r[101];

void mergesort (int ,int);

int main(){

   int n,i;

   cin>>n;

   for(i=1;i<=n;i++)

    cin>>a[i];

   mergesort(1,n);

   for(i=1;i<=n;i++)

    cout<<a[i]<<" ";

    return 0;    

}

void mergesort (int s,int t){

   int m,i,j,k;

   if(s==t) return ;

   m=(s+t)/2;

   mergesort(s,m);

   mergesort(m+1,t);

   i=s;

   j=m+1;

   k=s;

   while(i<=m && j<=t){

            if(a[i]<=a[j]){

                     r[k]=a[i];

                     i++;

                     k++;

            }

            else{

                     r[k]=a[j];

                     j++;

                     k++;

            }

   }

   while(i<=m){

            r[k]=a[i];

            i++;

            k++;

   }

   while(j<=t){

            r[k]=a[j];

            j++;

            k++;

   }

   for(i=s;i<=t;i++) a[i]=r[i];

}

斐波那契数列：

F[x]=f[x-1]+f[x-2];

边界条件：f[0]=0,f[1]=1;

前几项数据：0,1,1,2,3,5,8,13,21……

汉罗塔问题：

H[n]=2*H[n-1]+1;

边界：H[1]=1;

前几项数据：1,3,7,15,31,63……

平面分割问题：

A[n]=A[n-1]+2*(n-1);

边界：A[1]=1;

前几项数据：1,3,7,13,21,31……

李牧晓在2023-08-09 10:18:45追加了内容

memset(dp,0x3f,sizeof(dp))//初始dp数组
for(int len=1;len<=n-1;len++){//枚举区间长度
    for(int i=1;i<n;i++){//枚举区间的起点
        int j=i+len;//根据起点和长度得出终点
        if(j>n) break;//符合条件的终点
        for(int k=i;k<j;k++)//枚举最优分割点
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);//状态转移方程
    }
}

区间DP↑

李牧晓在2023-10-05 22:08:30追加了内容

Dijkstra堆优化模板

typedef pair<int,int> P;
int n,m;
struct edge{
    int next,w;
};

vector<edge> g[MAXN];
int dis[MAXN];
priority_queue<P,vector<P>,greater<P> > q;
void dijkstra(int st){
    memset(dis,0x3f,sizeof(dis));
    q.push(P(st,0));
    dis[st]=0;
    while(!q.empty()){
        P h=q.top(); q.pop();
        int u=h.first;
        if(dis[u]<h.second) continue;
// 小根堆里的队首元素 是最小值，如果满足此条件说明已经被更新过了，就不需要再更新。
        dis[u]=h.second;
        for(int i=0;i<g[u].size();i++){
            edge e=g[u][i];
            if(dis[e.next]>dis[u]+e.w){
                dis[e.next]=dis[u]+e.w;
                q.push(P(e.next,dis[e.next]));
            }
        }
    }
}

李牧晓在2023-10-18 22:00:16追加了内容

填满背包的方案总数

01背包：
j<v[i]  第i件物品一件也放不进去  f[i][j]=f[i-1][j];
j>=v[i] 第i件物品只能放进去一个，f[i][j]=f[i-1][j]+f[i-1][j-v[i]];
即第i件物品一个都不放的情况下填满容量为j的背包的方案数，加上第i件物品只放1件填满容量为j的背包的方案总数

完全背包：
j<v[i]  第i件物品一件也放不进去  f[i][j]=f[i-1][j];
j>=v[i] 第i件物品至少能放进去一个，f[i][j]=f[i-1][j]+f[i][j-v[i]];
即第i件物品一个都不放的情况下填满容量为j的背包的方案数，加上第i件物品至少放1件填满容量为j的背包的方案总数
多重背包：
**多重背包在求方案数时，枚举数量必须从1开始**

酷町豆代码分享其他 12条评论 1 年，1 月前

Answer 1

吕梓瑜

初级天翼

吓得我反手就是一个收藏！！！

Answer 2

李显晨

中级启示者

Dijkstra:
int n;
int cost[MAXN][MAXN];
bool found[MAXN];
int dis[MAXN];
void Dijkstra(int s) {
    memset(found, false, sizeof(found));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    while(true) {
        int u = -1;
        for(int i=1; i<=n; i++)
            if(!found[i]&&(u==-1||dis[i]<dis[u])) 
                u = i;
        if(u==-1)   return;
        found[u] = true;
        for(int i=1; i<=n; i++) 
//          if(cost[u][i]<INF) 
                dis[i] = min(dis[i], dis[u]+cost[u][i]);
    }
}

Floyd:
memset(dis, 0x3f, sizeof(dis));
for(int i=1; i<=m; i++)
    dis[u][v] = dis[v][u] = w;
for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(dis[i][k]+dis[k][j]<dis[i][j])
                dis[i][j] = dis[i][k]+dis[k][j];

Prim:
int MST_prim(){
    int ans=0;
    memset(dis,0x3f,sizeof(dis));
    memset(found,false,sizeof(found));
    dis[1]=0;
    while(1){
        int u=-1;
        for(int i=0;i<=n;i++){
            if(!found[i]&&(u==-1||dis[i]<dis[u])){
                u=i;
            }
        }
        if(u==-1) break;
        found[u]=true;
        ans+=dis[u];
        for(int i=0;i<=n;i++){
            if(!found[i]&&g[u][i]<dis[i]){
                dis[i]=g[u][i];
            }
        }
    }
    return ans;
}

bfs:
bfs(st){
    q.push(st);//起点入队 
    vis[st]=true;//起点已访问 
    while(!q.empty()){//当队列不为空 
        h=q.front();//取对首元素 
        q.pop();    //对首出队 
        if(h==ed) return ;//找到终点    结束 
        for(int i=1;i<=n;i++){   //枚举当前对首的点能够访问的点 
            if(!vis[nxt]){//如果可以访问 
                q.push(nxt);//入队 
                vis[nxt]=true;//该点已访问 
            }
        }   
    }
}

dfs:
void dfs(int k){  
    if(到目的地) 输出解
    else{
        for(int i=1;i<=算符总数;i++){
            if(满足条件){
                保存结果和状态
                dfs(k+1);
                恢复保存结果之前的状态
            }
        }
    }
}

Answer 3

薛乘志

初级启示者

你这个最小公倍数太暴力啦，最小公倍数可以用最大公约数算出来

Answer 4

王昱林

高级守护

初学者狂喜！

Answer 5

高乐彤

修练者

建议:

最大公约数可以用 __gcd()函数(头文件<cmath>)

__gcd(a,b);

返回a,b的最大公约数

最小公倍数太暴力了,可以这样:

a*b/__gcd(a,b);

用a和b的积再除以a和b的最大公约数,即可得到a,b的最小公倍数

Answer 6

李醒

新手光能

蒟蒻的我反手按了收藏

Answer 7

潘登

高级天翼

把这些加上

/*int hs(int n){
    int s=1;
    for(int i=1;i<=n;i++){
    s*=i;
    }
    return s;
}

1. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k第一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) { 
    int left = l, right = r, mid; 
    while(left<right) {   //注意不能写等号，否则可能**循环
    mid = left+(right-left)/2; 
    if(a[mid]<k)
        left = mid+1;
    else
        right = mid;
    }
    if(a[right]==k) return right;
    return -1;
}
2. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k最后一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) { 
    int left = l, right = r, mid; 
    while(left<right) {  //注意不能写等号，否则可能**循环
    mid = left+(right-left+1)/2; 
    if(a[mid]<=k)
        left = mid;
    else
        right = mid-1;
    }
    if(a[left]==k) return left;
    return -1;
}
左：
l+(r-l)/2
右：
l+(r-l+1)/2 
二分查找 

void mer(int l,int r){
    if(l==r)return ;
    int mid=(l+r)/2;
    mer(l,mid);
    mer(mid+1,r);
    int i=l,j=mid+1,cnt=l;
    while(i<=mid&&j<=r){
        if(a[i]<a[j])b[cnt++]=a[i++];
        else b[cnt++]=a[j++];
    } 
    while(i<=mid){
        b[cnt++]=a[i++];
    }
    while(j<=r){
        b[cnt++]=a[j++];
    } 
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
} 归并排序

int cmp(int x,int y){
    return x<y;
}
void qqs(int l,int r){
    int i=l,j=r,k=a[(l+r)/2];
    while(i<=j){
        while(cmp(a[i],k))i++;
        while(cmp(k,a[j]))j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;j--;
        }
    }
    if(l<j)qqs(l,j);
    if(i<r)qqs(i,r);
}
void qs(int l,int r){
    int i=l,j=r,k=a[(l+r)/2];
    while(i<=j){
        while(a[i]<k)i++;
        while(a[j]>k)j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;j--;
        }
    }
    if(l<j)qs(l,j);
    if(i<r)qs(i,r);
}快排 

long long f[100000000] 
void ss(int n){
    f[1]=1;f[0]=1;
    for(int i=2;i*i<=n;i++){
        if(!f[i]){
            for(int j=i;j<=n/i;j++){
                f[i*j]=1;
            }
        }
    }
}
int a[10005],b[10005],c[10005],n;
string f[10005];
string ad(string s1,string s2s){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    a[0]=s1.size();
    b[0]=s2.size();
    c[0]=max(a[0],b[0]);
    for(int i=1;i<=a[0];i++){
        a[i]=s1[a[0]-i]-'0';
    }
    for(int i=1;i<=a[0];i++){
        b[i]=s2[b[0]-i]-'0';
    }
    int jw=0;
    for(int i=1;i<=c[0];i++){
        c[i]=a[i]+b[i]+jw;
        jw=c[i]/10;
        c[i]%=10;
    }
    if(jw>0){
        c[0]++;
        c[c[0]]=1;
    }
    string s="";
    for(int i=c[0];i>=1;i--){
        s+=char(c[i]+'0');
    }
    return s;
}
int ss(int x){
    int i;
    if(x<=0)return 0;
    if(x==1)return 0;
    for(i=2;i*i<=x;i++){
    if(x%i==0)return 0;
    }
    return 1;
}
int dx(int m){
    int x=0,y;
    y=m;
    while(y){
        x=x*10+y%10;
        y/=10;
    }
    if(m==x)return 1;
    return 0;
}
int gcd(int m,int n){
    int r;
    while(n){
    r=m%n;
    m=n;
    n=r;
    }
    return m;
}

int gcd(int a, int b){
 return a % b ? gcd(b, a % b) : b;
}

int lcm(int a, int b){
 return a * b / gcd(a, b);
}
int fl(int n){ 
    while(n){ 
    int sum+=n%10;
    n/=10; 
    }
    return sum;
}
int tgs(int x)
{
    int p,r;
    if(x<10)
    {
        p=x*x;
        r=p%10;
        if (x==r)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else if(x<100)
    {
        p=x*x;
        r=p%100;
        if (x==r)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else if(x<1000)
    {
        p=x*x;
        r=p%1000;
        if (x==r)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else if(x<10000)
    {
        p=x*x;
        r=p%10000;
        if (x==r)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else if(x<100000)
    {
        p=x*x;
        r=p%100000;
        if (x==r)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}

// 
int a[200+10],b[200+10],c[200+10];
string ad(string as,string bs){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    int al=as.size(),bl=bs.size();
    int cl=max(al,bl)+1;
    for(int i=1;i<=al;i++){
          a[i]=as[as.size()-i]-'0';
    }
    for(int i=1;i<=bl;i++){
          b[i]=bs[bs.size()-i]-'0';
    }
    string cs;
    for(int i=1;i<=cl;i++){
        c[i]+=a[i]+b[i];  
        c[i+1]=c[i]/10;
        c[i]%=10;
    }
    while(c[cl]==0&&cl>1)cl--;
    for(int i=cl;i>=1;i--){
        cs+=c[i]+'0';
    }
    return cs;
}

int zis(int n)
{
    if(n<=1) return 0;
    int num;
    for(int i=2;i*i<=n;i++)while(!(n%i))num=i,n/=i;
        if(n>1)num=n;
    return num;
}
int cmp(const int &x,const int &y){
    return x>y;
}
*/

我攒了很久的有重复的

Answer 8

李牧晓

中级天翼

ding

Answer 9

李牧晓

中级天翼

ding

Answer 10

李牧晓

中级天翼

ding

Answer 11

朱小川

缔造者

Answer 12

杜承俊

初级守护

ST算法
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a>b?b:a;}
const int N=1e5+10,LOG=22;
struct ST{
    int n,m;
    int a[N],f[N][LOG+10];
    void CIN(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            f[i][0]=a[i];
        }
    }
    void ST_init(){
        for(int j=1;j<=LOG;j++)
            for(int i=1;(i+(1<<j)-1)<=n;i++)
                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
    void COUT(){
        for(int i=1,l,r,x;i<=m;i++){
            scanf("%d%d",&l,&r);
            x=log2(r-l+1);
            printf("%d\n",max(f[l][x],f[r-(1<<x)+1][x]));
        }
    }
}a;
int main(void){
    std::ios::sync_with_stdio(false);
    a.CIN();
    a.ST_init();
    a.COUT();
    return 0;
}

树链剖分算法
#include<bits/stdc++.h>
#define int long long
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a>b?b:a;}
const int N=3*1e4+10,INF=0x3f3f3f3f;
struct Tree_Chain_Partition_And_Segment_Tree{
    int n,m;
    int w[N];
    int size[N],Heavy_son[N],dep[N],fa[N];
    int top[N],id[N],rev[N],cnt;
    int mx[N<<2],sum[N<<2];
    vector<int>G[N];
    void DFS_Search_Heavy_son(int u){
        size[u]=1;
        dep[u]=dep[fa[u]]+1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(fa[u]==v)continue;
            fa[v]=u;
            DFS_Search_Heavy_son(v);
            size[u]+=size[v];
            if(size[Heavy_son[u]]<size[v])
                Heavy_son[u]=v;
        }
    }
    void DFS_Mapping(int u,int tp){
        top[u]=tp;
        id[u]=++cnt;
        rev[cnt]=u;
        if(Heavy_son[u])
            DFS_Mapping(Heavy_son[u],tp);
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(fa[u]==v)continue;
            if(Heavy_son[u]==v)continue;
            DFS_Mapping(v,v);
        }
    }
    void Up(int p){
        mx[p]=max(mx[p<<1],mx[p<<1|1]);
        sum[p]=sum[p<<1]+sum[p<<1|1];
    }
    void Build(int p,int l,int r){
        if(l==r){
            mx[p]=sum[p]=w[rev[l]];
            return;
        }
        int mid=(l+r)>>1;
        Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
        Up(p);
    }
    void Update(int p,int l,int r,int x,int v){
        if(x<l||x>r)return;
        if(l==r){
            mx[p]=sum[p]=v;
            return;
        }
        int mid=(l+r)>>1;
        Update(p<<1,l,mid,x,v),Update(p<<1|1,mid+1,r,x,v);
        Up(p);
    }
    int Query_Max(int p,int l,int r,int x,int y){
        if(x>r||y<l)return -INF;
        if(x<=l&&r<=y)return mx[p];
        int mid=(l+r)>>1,ans=-INF;
        ans=max(ans,Query_Max(p<<1,l,mid,x,y));
        ans=max(ans,Query_Max(p<<1|1,mid+1,r,x,y));
        return ans;
    }
    int Query_Sum(int p,int l,int r,int x,int y){
        if(x>r||y<l)return 0;
        if(x<=l&&r<=y)return sum[p];
        int mid=(l+r)>>1,ans=0;
        ans+=Query_Sum(p<<1,l,mid,x,y);
        ans+=Query_Sum(p<<1|1,mid+1,r,x,y);
        return ans;
    }
    int Answer_Max(int u,int v){
        int ans=-INF;
        while(top[u]!=top[v]){
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            ans=max(ans,Query_Max(1,1,n,id[top[u]],id[u]));
            u=fa[top[u]];
        }
        if(id[u]>id[v])swap(u,v);
        ans=max(ans,Query_Max(1,1,n,id[u],id[v]));
        return ans;
    }
    int Answer_Sum(int u,int v){
        int ans=0;
        while(top[u]!=top[v]){
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            ans+=Query_Sum(1,1,n,id[top[u]],id[u]);
            u=fa[top[u]];
        }
        if(id[u]>id[v])swap(u,v);
        ans+=Query_Sum(1,1,n,id[u],id[v]);
        return ans;
    }
    void Init(){
        DFS_Search_Heavy_son(1);
        DFS_Mapping(1,1);
        Build(1,1,n);
    }
    void MAIN(){
        scanf("%lld",&n);
        for(int i=1,u,v;i<n;i++){
            scanf("%lld%lld",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
            scanf("%lld",&w[i]);
        Init();
        scanf("%lld",&m);
        while(m--){
            char opt[10];int u,v;
            scanf("%s%lld%lld",opt,&u,&v);
            if(opt[0]=='C')
                Update(1,1,n,id[u],v);
            else
                if(opt[1]=='M')
                    printf("%lld\n",Answer_Max(u,v));
                else
                    printf("%lld\n",Answer_Sum(u,v));
        }
    }
};
Tree_Chain_Partition_And_Segment_Tree a;
signed main(void){
    std::ios::sync_with_stdio(false);
    a.MAIN();
    return 0;
}

// Problem:线段树** 
// Author: 杜承俊
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
namespace get_out{
    char B[1<<20],*S=B,*T=B;char op;
    inline void read_(int &x){x=0;int fi(1);op=getchar();while((op<'0'||op>'9')&&op!='-') op=getchar();if(op=='-') op=getchar(),fi=-1;while(op>='0'&&op<='9') x=(x<<1)+(x<<3)+(op^48),op=getchar();x*=fi;return;}
    inline void read_(long long &x){x=0;int fi(1);op=getchar();while((op<'0'||op>'9')&&op!='-') op=getchar();if(op=='-') op=getchar(),fi=-1;while(op>='0'&&op<='9') x=(x<<1)+(x<<3)+(op^48),op=getchar();x*=fi;return;}
    inline void read_(double &x){x=0.0;float fi(1.0),sm(0.0);op=getchar();while((op<'0'||op>'9')&&op!='-') op=getchar();if(op=='-') op=getchar(),fi=-1.0;while(op>='0'&&op<='9') x=(x*10.0)+(op^48),op=getchar();if(op=='.') op=getchar();int rtim=0;while(op>='0'&&op<='9') sm=(sm*10.0)+(op^48),++rtim,op=getchar();while(rtim--) sm/=10.0;x+=sm,x*=fi;return;}
    inline void read_(string &s){char c(getchar());s="";while(!isgraph(c)&&c!=EOF) c=getchar();for(;isgraph(c);c=getchar()) s+=c;}
    inline void read_(char &c){for(c=op;c==' '||c=='\n'||c=='\r'||c=='\t';c=getchar());op=c;}
    template<typename Head,typename ...Tail>
    inline void read_(Head& h,Tail&... t){read_(h),read_(t...);}
    inline void write_(){}
    inline void postive_write(unsigned x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(unsigned long long x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(int x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(long long x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void postive_write(short x){if(x>9) postive_write(x/10);putchar(x%10|'0');}
    inline void write_(const char* ss) {while(*ss) putchar(*ss++);}
    inline void write_(char c) {putchar(c);}
    inline void write_(string s) {for(unsigned i=0;i<s.size();++i) putchar(s[i]);}
    inline void write_(short x){if(x<0) putchar('-'),postive_write(-x);else postive_write(x);}
    inline void write_(int x){if(x<0) x=-x,putchar('-');postive_write(x);}
    inline void write_(long long x){if(x<0) x=-x,putchar('-');postive_write(x);}
    inline void write_(unsigned x) {postive_write(x);}
    inline void write_(ull x) {postive_write(x);}
    template<typename Head,typename ...Tail>
    inline void write_(Head h,Tail ...t) {write_(h),write_(t...);}
}
using get_out::read_;using get_out::write_;
const int N=2*1e5+10;
struct node{
    int l,r;
    ll val;
};
struct Segment_Tree_Splitting{
    int n,m;
    int cnt=0,root[N];
    node sgt[N*40];
    void modify(int l,int r,int &k,int p,int x){
        if(!k)k=++cnt;
        sgt[k].val+=x;
        if(l==r)return;
        int mid=(l+r)>>1;
        if(p<=mid)modify(l,mid,sgt[k].l,p,x);else modify(mid+1,r,sgt[k].r,p,x);
    }
    void merge(int &x,int &y){if(!x||!y)x|=y;else{sgt[x].val+=sgt[y].val;merge(sgt[x].l,sgt[y].l),merge(sgt[x].r,sgt[y].r);}}
    void push_up(int k){sgt[k].val=sgt[sgt[k].l].val+sgt[sgt[k].r].val;}
    int split(int l,int r,int &k,int x,int y){
        int n=++cnt;
        if(x<=l&&y>=r){sgt[n]=sgt[k];k=0;}
        else{
            int mid=(l+r)>>1;
            if(x<=mid)sgt[n].l=split(l,mid,sgt[k].l,x,y);
            if(y>mid)sgt[n].r=split(mid+1,r,sgt[k].r,x,y);
            push_up(k),push_up(n);
        }
        return n;
    }
    ll query(int l,int r,int k,int x,int y){
        if(x<=l&&y>=r)return sgt[k].val;
        int mid=(l+r)>>1;ll sum=0;
        if(x<=mid)sum+=query(l,mid,sgt[k].l,x,y);
        if(y>mid)sum+=query(mid+1,r,sgt[k].r,x,y);
        return sum;
    }
    ll query(int l,int r,int k,int kth){
        if(l==r)return l;
        int mid=(l+r)>>1;
        if(kth<=sgt[sgt[k].l].val)return query(l,mid,sgt[k].l,kth);
        else return query(mid+1,r,sgt[k].r,kth-sgt[sgt[k].l].val);
    }
    void CIN_COUT(){
        read_(n,m);
        for(int i=1,x;i<=n;i++){
            read_(x);
            modify(1,n,root[1],i,x);
        }
        int last=1;
        for(int i=1,opt,x,y,z;i<=m;i++){
            read_(opt,x,y);
            if(opt==0){read_(z);root[++last]=split(1,n,root[x],y,z);}
            else if(opt==1)merge(root[x],root[y]);
            else if(opt==2){read_(z);modify(1,n,root[x],z,y);}
            else if(opt==3){read_(z);write_(query(1,n,root[x],y,z),"\n");}
            else{
                if(y>sgt[root[x]].val)write_(-1);
                else write_(query(1,n,root[x],y));
                write_("\n");
            }
        }
    }
}a;
signed main(void){
    std::ios::sync_with_stdio(false);
    a.CIN_COUT();
    return 0;
}

// Problem:舞蹈链（DLX）
// Author:杜承俊
#include<bits/stdc++.h>
#define int long long
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a>b?b:a;}
const int N=500+10,M=6000+10;
struct Linked_List{
    int Left,Right;
    int Up,Down;
    int Row,Col;
};
struct DLX{
    int n,m;
    Linked_List a[M];
    int Row[N],ans[N],cnt[N];
    int tot;
    void Init(){
        for(int i=0;i<=m;i++){
            a[i].Left=i-1,a[i].Right=i+1;
            a[i].Up=i,a[i].Down=i;
            cnt[i]=0;
        }
        a[0].Left=m,a[m].Right=0;
        tot=m;
    }
    void Add(int r,int c){
        a[++tot].Row=r,a[tot].Col=c;
        a[tot].Up=a[c].Up,a[tot].Down=c;
        a[a[tot].Up].Down=tot,a[c].Up=tot;
        if(!Row[r]){
            a[tot].Left=a[tot].Right=tot;
            Row[r]=tot;
        }else{
            a[tot].Left=a[Row[r]].Left,a[tot].Right=Row[r];
            a[a[tot].Left].Right=tot,a[a[tot].Right].Left=tot;
        }
        cnt[c]++;
    }
    void Remove(int c){
        for(int i=a[c].Down;i!=c;i=a[i].Down)
            for(int j=a[i].Right;j!=i;j=a[j].Right){
                a[a[j].Down].Up=a[j].Up;
                a[a[j].Up].Down=a[j].Down;
                cnt[a[j].Col]--;
            }
        a[a[c].Left].Right=a[c].Right,a[a[c].Right].Left=a[c].Left;
    }
    void Resume(int c){
        a[a[c].Left].Right=c,a[a[c].Right].Left=c;
        for(int i=a[c].Down;i!=c;i=a[i].Down)
            for(int j=a[i].Right;j!=i;j=a[j].Right){
                a[a[j].Down].Up=j;
                a[a[j].Up].Down=j;
                cnt[a[j].Col]++;
            }
    }
    bool Dance(int cur){
        if(a[0].Right==0){
            for(int i=1;i<cur;i++)
                cout<<ans[i]<<" ";
            return true;
        }
        int c=a[0].Right;
        for(int i=a[0].Right;i;i=a[i].Right)
            if(cnt[i]<cnt[c])
                c=i;
        Remove(c);
        for(int i=a[c].Down;i!=c;i=a[i].Down){
            ans[cur]=a[i].Row;
            for(int j=a[i].Right;j!=i;j=a[j].Right)
                Remove(a[j].Col);
            if(Dance(cur+1))return true;
            for(int j=a[i].Right;j!=i;j=a[j].Right)
                Resume(a[j].Col);
        }
        Resume(c);
        return false;
    }
    void MAIN(){
        cin>>n>>m;
        Init();
        for(int i=1;i<=n;i++)
            for(int j=1,x;j<=m;j++){
                cin>>x;
                if(x==1)Add(i,j);
            }
        if(!Dance(1))cout<<"No Solution!";
    }
}t;
signed main(void){
    std::ios::sync_with_stdio(false);
    t.MAIN();
    cout<<endl;
    return 0;
}

Kosaraju
#include<bits/stdc++.h>
#define int long long
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a>b?b:a;}
const int N=1e4+10;
struct Kosaraju{
    int n,m,cnt,color_num;
    int a[N],color[N];
    vector<int>G[N],RG[N];
    bool vis[N],Rvis[N];
    void init(){
        cnt=0,color_num=0;
        memset(color,0,sizeof(color));
        for(int i=1;i<=n;i++)
            G[i].clear(),RG[i].clear();
        memset(vis,false,sizeof(vis));
        memset(Rvis,false,sizeof(Rvis));
    }
    void Add(int u,int v){
        G[u].push_back(v);
        RG[v].push_back(u);
    }
    void CIN(){
        cin>>n>>m;
        init();
        for(int i=1,u,v;i<=m;i++){
            cin>>u>>v;
            Add(u,v);
        }
    }
    void DFS(int u){
        vis[u]=true;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(!vis[v])
                DFS(v);
        }
        a[++cnt]=u;
    }
    void DFS_first(){
        for(int i=1;i<=n;i++)
            if(!vis[i])
                DFS(i);
    }
    void RDFS(int u,int k){
        Rvis[u]=true;
        color[u]=k;
        for(int i=0;i<RG[u].size();i++){
            int v=RG[u][i];
            if(!Rvis[v])
                RDFS(v,k);
        }
    }
    void RDFS_first(){
        for(int i=cnt;i>=1;i--)
            if(!Rvis[a[i]])
                RDFS(a[i],++color_num);
    }
    void COUT(){
        for(int i=1;i<=n;i++)
            cout<<i<<" "<<color[i]<<endl;
    }
}a;
signed main(void){
    std::ios::sync_with_stdio(false);
    a.CIN();
    a.DFS_first();
    a.RDFS_first();
    a.COUT();
    cout<<endl;
    return 0;
}

点分治
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=100+10,K=1e8+10;
struct Edge{
    int to,w;
};
vector<Edge>G[N<<1];
int n,m;
int root,sum,cnt;
int tmp[N],size[N],dis[N],mx[N],q[M];
bool Judge[K],ans[M],vis[N];
void Get_root(int u,int fa){
    size[u]=1,mx[u]=0;
    for(int i=0;i<G[u].size();i++){
        Edge v=G[u][i];
        if(fa==v.to||vis[v.to])continue;
        Get_root(v.to,u);
        size[u]+=size[v.to];
        if(size[v.to]>mx[u])
            mx[u]=size[v.to];
    }
    mx[u]=max(mx[u],sum-size[u]);
    if(mx[u]<mx[root])
        root=u;
}
void Get_dis(int u,int fa){
    tmp[++cnt]=dis[u];
    for(int i=0;i<G[u].size();i++){
        Edge v=G[u][i];
        if(fa==v.to||vis[v.to])continue;
        dis[v.to]=dis[u]+v.w;
        Get_dis(v.to,u);
    }
}
void Solve(int u){
    queue<int>Q;
    for(int i=0;i<G[u].size();i++){
        Edge v=G[u][i];
        if(vis[v.to])continue;
        cnt=0;
        dis[v.to]=v.w;
        Get_dis(v.to,u);
        for(int j=1;j<=cnt;j++)
            for(int k=1;k<=m;k++)
                if(q[k]>=tmp[j])
                    ans[k]|=Judge[q[k]-tmp[j]];
        for(int j=1;j<=cnt;j++){
            Q.push(tmp[j]);
            Judge[tmp[j]]=true;
        }
    }
    while(!Q.empty()){
        Judge[Q.front()]=false;
        Q.pop();
    }
}
void Divide_Conquer(int u){
    vis[u]=Judge[0]=true;
    Solve(u);
    for(int i=0;i<G[u].size();i++){
        Edge v=G[u][i];
        if(vis[v.to])continue;
        root=0;
        mx[root]=sum=size[v.to];
        Get_root(v.to,0);
        Get_root(root,0);
        Divide_Conquer(root);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<=n-1;i++){
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back(Edge{v,w});
        G[v].push_back(Edge{u,w});
    }
    for(int i=1;i<=m;i++)
        scanf("%d",&q[i]);
    mx[0]=sum=n;
    Get_root(1,0);
    Get_root(root,0);
    Divide_Conquer(root);
    for(int i=1;i<=m;i++)
        if(ans[i])
            printf("AYE\n");
        else
            printf("NAY\n");
    return 0;
}

Answer 13

宋子墨

新手天翼

66666666666666666666666666

Answer 14

王牌工作室官方

新手光能

3)错了，用这个样例试一下

abc     def  ddg hh

王牌工作室官方在2022-02-21 12:56:58追加了内容

#include<bits/stdc++.h>
using namespace std;
string word[1024];
int main()
{
	string s;
	int cnt=0,p=0;
	getline(cin,s);
	s=" "+s+" ";//保证每个单词都被空格包围
	for(int i=0;i<s.size();i++){
		if(s[i]==' '){//每遇到一个空格
		    word[cnt++]=s.substr(p+1,i-p-1);//利用空格位置截出一个单词
		    p=i;
		}
	}
	for(int i=0;i<cnt;i++)
	{
		cout<<word[i];
		cout<<endl;
	}
	return 0;
}

Answer 15

郑嘉豪

资深守护

Answer 16

丁炳瑜

高级光能

ding（这种好文章，不算挖坟吧）

Answer 17

万韧山

初级天翼

ding

大佬6666

Answer 18

叶宝锴

新手光能

你这个贴可以置顶了，haha！

Answer 19

曹博扬

初级天翼

你二分的方法不严谨

Answer 20

刘意阳

初级天翼

DING

Answer 21

张家宇

初级光能

帮你顶

Answer 22

张家宇

初级光能

ding

Answer 23

丁梓豪

新手天翼

ding

Answer 24

程一凡

初级光能

Answer 25

张家宇

初级光能

ding

Answer 26

李雨彤

资深光能

ding

针不**

Answer 27

刘意阳

初级天翼

大佬NB

Answer 28

朱睿辰

资深守护

针不**~~~

Answer 29

刘瑾瑜

新手天翼

shui

Answer 30

裴浩铭

初级光能

Answer 31

李牧晓

中级天翼

ding

Answer 32

李牧晓

中级天翼

ding

Answer 33

李牧晓

中级天翼

ding

Answer 34

王耀斌

高级守护

子好是长时间空白卷哈哈哈查看客户考核表

Answer 35

刘风翔

新手启示者

我要豆！！！

Answer 36

贾若曦

资深天翼

66

一看就是大佬

Answer 37

李牧晓

中级天翼

ding

Answer 38

汪宇航

新手启示者

赞一个

还不龊

Answer 39

汪宇航

新手启示者

把图论搜索加上去

Answer 40

连想

资深光能

你一顶不就有了吗........

Answer 41

李牧晓

中级天翼

ding

Answer 42

蔡俊豪

高级守护

ding

Answer 43

冯章轩

初级光能

《论学霸的肝帝夜晚》

Answer 44

钟子然

初级光能

刚看，吓得我反手点赞收藏，6666666666666666666666666,但会不会有些新生抄袭

Answer 45

李牧晓

中级天翼

ding

Answer 46

许公铭

初级天翼

6

Answer 47

钟子然

初级光能

我现在还在奇怪，为什么不是精品贴

Answer 48

吴轲

中级守护

ding

Answer 49

熊智晖

高级天翼

ding

Answer 50

张铭睿

中级光能

666，反手收藏，大佬666

问题标题: c++常见模板---更新(冲150赞！——感谢大家

85 个回答: