#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;


const int N = 100010;

int n;
int a[N];

int main()
{
    cin>>n;

    for (int i = 0; i < n; i ++ ) cin>>a[i];

    for (int i = 0; i < n; i ++ ){
        while(a[i]%2==0) a[i]/=2;
        while(a[i]%3==0) a[i]/=3;
    }

    bool suss=true;

    for (int i = 0; i < n-1; i ++ ){
        if(a[i]!=a[i+1]){
            suss=false;
            break;
        }
    }

    if(suss) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 200010;

typedef long long LL;

LL n,k;
LL a[N];
map<LL,LL> ff,bb; 
LL f[N],b[N];

int main()
{
    cin>>n>>k;

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        f[i]+=ff[a[i]/k];
        ff[a[i]]++;
    }

    for(int i=n;i>=1;i--){
        b[i]+=bb[a[i]*k];
        bb[a[i]]++;
    }

    LL res=0;
    for(int i=2;i<n;i++) if(a[i]%k==0) res+=f[i]*b[i];

    cout<<res<<endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110,M=1010;

int t,n;
bool st[M];
int info[N][M];
int a[N];

int main()
{
    cin>>t;

    while(t--){
        cin>>n;

        memset(st,false,sizeof st);
        memset(info,0,sizeof info);
        int m=0;
        for(int i=1;i<=n;i++) cin>>a[i],st[a[i]]=true,m=max(m,a[i]);;

        int x,maxx=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            info[x][a[i]]++;
            maxx=max(maxx,x);
        }

        for(int i=1;i<=maxx;i++){
            printf("%d={",i);
            for(int j=1;j<M;j++){
                if(st[j]&&j!=m) printf("%d=%d,",j,info[i][j]);
                else if(st[j]&&j==m) printf("%d=%d",j,info[i][j]);
            }
            printf("}\n");
        }
    }

    return 0;
}

O(n^3)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int m;
int a[N];

int main()
{
    scanf("%d", &n);
    while (n -- ){
        scanf("%d", &m);

        for(int i=0;i<m;i++) scanf("%d", &a[i]);

        int res=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<m;k++){
                    if(a[i]+a[j]==a[k]) res++;
                }
            }
        }

        cout<<res<<endl;
    }

    return 0;
}

优化O(n^2)，枚举两个，将另一个存在存在个数存下来

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int m;
int a[N];
int cnt[110];

int main()
{
    scanf("%d", &n);
    while (n -- ){
        scanf("%d", &m);

        memset(cnt,0,sizeof cnt);
        for(int i=0;i<m;i++) scanf("%d", &a[i]),cnt[a[i]]++;

        int res=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                // for(int k=0;k<m;k++){
                    res+=cnt[a[i]+a[j]];
                // }
            }
        }

        cout<<res<<endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

string str;
long long bin[40];

int main(){
    bin[1]=2;
    for(int i=2;i<30;i++) bin[i]=bin[i-1]*2;

    while(cin>>str){
        LL res=0;
        reverse(str.begin(),str.end());
        for(int i=0;i<str.size();i++) res=res+(LL)(bin[i+1]-1)*(str[i]-'0');

        cout<<res<<endl;
    }

    return 0;
}

#include<iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int odd[N],even[N];
int cnto,cnte;

int main(){
    for(int i=0;i<10;i++){
        int x;
        cin>>x;

        if(x%2){
            odd[cnto++]=x;
        }else{
            even[cnte++]=x;
        }
    }

    sort(odd,odd+cnto,greater<int>());
    sort(even,even+cnte);

    for(int i=0;i<cnto;i++) cout<<odd[i]<<' ';
    for(int i=0;i<cnte;i++) cout<<even[i]<<' ';

    return 0;
}

dfs 枚举飞机降落的顺序(枚举所有的情况)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
struct Plane{
    int t,d,l;
}p[N];
bool st[N];

bool dfs(int u,int last){
    if(u==n) return true;

    for(int i=0;i<n;i++){
        int t=p[i].t,d=p[i].d,l=p[i].l;
        if(!st[i]&&t+d>=last){
            st[i]=true;
            if(dfs(u+1,max(last,t)+l)) return true;
            st[i]=false;
        }
    }

    return false;
}

int main()
{
    int t;
    scanf("%d",&t);

    while(t--){
        scanf("%d", &n);
        for(int i=0;i<n;i++){
            int t,d,l;
            scanf("%d%d%d",&t,&d,&l);

            p[i]={t,d,l};
        }

        memset(st,false,sizeof st);

        if(dfs(0,0)) printf("YES\n");
        else printf("NO\n");
    }


    return 0;
}

状态压缩dp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10,M=1<<N,INF=0x3f3f3f3f;

int T,n;
int f[M];
struct Plane{
    int t,d,l;
}p[N];

int main()
{
    scanf("%d", &T);

    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            int t,d,l;
            scanf("%d%d%d",&t,&d,&l);

            p[i]={t,d,l};
        }

        memset(f,0x3f,sizeof f);
        f[0]=0;

        for(int i=1;i<1<<n;i++){
            for(int j=0;j<n;j++){
                int t=p[j].t,d=p[j].d,l=p[j].l;
                if((i>>j)&1){
                    int last=f[i-(1<<j)];
                    if(t+d>=last){
                        f[i]=min(f[i],max(last,t)+l);
                    }
                }

            }
        }

        if(f[(1<<n)-1]!=INF) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

    return 0;
}

考试的时候一定要静下心 实在不会写时间复杂度高的方法也行 考试不要再fw了

O(n) 开一个数组记录以当前数结尾的最长接龙序列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
string str[N];
int f[N];
int cnt[10];

int main()
{
    scanf("%d", &n);

    str[0]="  ";
    for(int i=1;i<=n;i++) cin>>str[i];

    f[1]=1;
    cnt[str[1][str[1].size()-1]-'0']=1;

    int maxx=1;
    for(int i=2;i<=n;i++){
        f[i]=1;
        f[i]+=cnt[str[i][0]-'0'];

        cnt[(str[i][str[i].size()-1])-'0']=max(cnt[str[i][str[i].size()-1]-'0'],f[i]);
    }

    int res=1e7;
    for(int i=1;i<=n;i++) res=min(res,n-f[i]);
    cout<<res<<endl;

    return 0;
}

暴力 使用O(n)的复杂度转移 TLE

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
string str[N];
int f[N];

int main()
{
    scanf("%d", &n);

    str[0]="  ";
    for(int i=1;i<=n;i++) cin>>str[i];

    // for(int i=1;i<=n;i++) cout<<str[i]<<endl;

    f[1]=1;
    int maxx=1;
    for(int i=2;i<=n;i++){
        f[i]=1;
        for(int j=i-1;j;j--){
            if(str[j][str[j].size()-1]==str[i][0]){
                f[i]=max(f[i],f[j]+1);
                maxx=max(maxx,f[i]);
            }
        }
    }

    // for(int i=1;i<=n;i++) res=min(res,n-f[i]);

    cout<<n-maxx<<endl;

    return 0;
}

#include<iostream>

using namespace std;

const int N = 1e5+10;

int n;
int primes[N],cnt;
bool st[N];

void get_prime(int n){
    for(int i=2;i<n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main()
{
    cin>>n;

    get_prime(n+1);


    if(n==2||n==1) cout<<1<<endl;
    else cout<<2<<endl;
    for(int i=2;i<=n+1;i++){
        if(!st[i]) cout<<1<<' ';
        else cout<<2<<' ';
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int k;
string str;

void dfs(){
    if(str[k]=='#'){
        k++;
        return ;
    }

    char r=str[k++];
    dfs();
    cout<<r<<' ';
    dfs();

}

int main(){
    cin>>str;

    dfs();

    return 0;
}