#include<bits/stdc++.h>using namespace std;#define int long long#define endl '\n'int n,m,p;const int N=1e5;int fa[N];void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}int find(int x){if(fa[x]==x)return x;int t=find(fa[x]);fa[x]=t;return fa[x];}void merge(int a,int b){int x=find(a),y=find(b);if(x==y)return;fa[x]=y;}signed main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>m>>p;init(n);while(m--){int a,b;cin>>a>>b;merge(a,b);}while(p--){int a,b;cin>>a>>b;if(find(a)!=find(b))cout<<"No"<<endl;elsecout<<"Yes"<<endl;}return  0;}

n < 200, 可以选择复杂度为O(n^3)的算法。例：dp, floydn < 5000, 可以选择复杂度为O(n^2)的算法。例：dp, Dijkstra, 朴素版Primn < 1e6, 可以选择复杂度为O(nlogn)或者O(n^2logn)的算法。例：sort, 线段树, 树状数组, set, mmap, spfa, 凸包, 二分n < 1e7, 可以选择复杂度为O(n)的算法。例：哈希, 双指针, kmp, AC自动机, 部分sort, 树状数组, spfan < 1e8, 可以选择复杂度为O(n)的算法。例：双指针, kmp, AC自动机, 线性筛n < 1e9, 可以选择复杂度为O(√n)的算法。例：判断质数n < 1e18, 可以选择复杂度为O(logn)的算法。例：二分, 欧几里得算法, 幂运算此外128MB开int数组约1e7~1e8；二维数组最大4000*4000

1.dijkstra（无法求负边）#include<bits/stdc++.h>using namespace std;#define endl '\n'const int N = 3e5;int n, m, s, t;vector<pair<int, int> > g[N];int dis[N];int st[N];void dij() {memset(dis,0x3f,sizeof(dis));priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;pq.push({0,s});while (pq.size()){int  d = pq.top().first;int  u = pq.top().second;pq.pop();if (st[u])continue;st[u] = 1;for (auto i : g[u]){int v = i.first;int w = i.second;if (dis[v] > d + w){dis[v] = d + w;pq.push({dis[v],v});}}}cout << dis[t];}signed main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m >> s >> t;for (int i = 0;i <m;i++){int u, v, w;cin >> u >> v >> w;g[u].push_back({v,w});g[v].push_back({u,w});}dij();return  0;}2.贝尔特佛特（可以求负边）int n, m;       // n表示点数，m表示边数int dist[N];        // dist[x]存储1到x的最短路距离struct Edge     // 边，a表示出点，b表示入点，w表示边的权重{int a, b, w;}edges[M];// 求1到n的最短路距离，如果无法从1走到n，则返回-1。int bellman_ford(){memset(dist, 0x3f, sizeof dist);dist[1] = 0;// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。for (int i = 0; i < n; i ++ ){for (int j = 0; j < m; j ++ ){int a = edges[j].a, b = edges[j].b, w = edges[j].w;if (dist[b] > dist[a] + w)dist[b] = dist[a] + w;}}if (dist[n] > 0x3f3f3f3f / 2) return -1;return dist[n];}3.Floyd（dp思想）for (k = 1; k <= n; k++) {for (x = 1; x <= n; x++) {for (y = 1; y <= n; y++) {f[x][y] = min(f[x][y], f[x][k] + f[k][y]);}}}上述算法，dijkstra时间复杂度最低，Floyd最好n的三次方，但是可以求图上连通点之间的最短距离

#include <iostream>#include <vector>#include <algorithm>using namespace std;// 定义边的结构体struct Edge {int u, v, w; // 边的起点、终点和权重};// 比较函数，用于排序边bool operator<(const Edge& a, const Edge& b) {return a.w < b.w;}// 并查集的父节点数组int parent[100005];// 查找根节点int find(int x) {return parent[x] = find(parent[x]);}// 合并两个集合void merge(int x, int y) {int px = find(x), py = find(y);if (px != py) parent[px] = py;}int main() {int n, m; // n为顶点数，m为边数cin >> n >> m;// 读取所有边vector<Edge> edges(m);for (int i = 0; i < m; i++) {cin >> edges[i].u >> edges[i].v >> edges[i].w;}// 按照边的权重排序sort(edges.begin(), edges.end());// 初始化并查集for (int i = 0; i <= n; i++) parent[i] = i;long long ans = 0; // 最小生成树的总权重int cnt = 0; // 已经加入最小生成树的边数// 遍历所有边for (auto& e : edges) {int pu = find(e.u), pv = find(e.v);if (pu != pv) {merge(pu, pv);ans += e.w;cnt++;}if (cnt == n - 1) break; // 如果已经加入 n-1 条边，停止}// 输出结果if (cnt == n - 1) {cout << ans << endl;} else {cout << "IMPOSSIBLE" << endl; // 如果无法形成最小生成树}return 0;}

vector<int> get(const vector<int>& arr){vector<int> tmp = arr;sort(tmp.begin(), tmp.end());tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());unordered_map<int, int> mp;for (int i = 0; i < tmp.size(); i + ){mp[tmp[i]] = i;}vector<int> res(arr.size());for (int i = 0; i < arr.size(); i + ){res[i] = mp[arr[i]];}return res;}适合用于数据很少，但是数值很大，且不涉及数值计算的题目

可以通过循环拆解合数的所有质因子，代码如下while(vis[i]!=i){……i=i/vis[i];}

(1)01背包#include<bits/stdc++.h>using namespace std;#define int long long#define endl '\n'const int N=1e7;int dp[105][1005];signed main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int n,t;cin>>n>>t;int w[n+1],v[n+1];for(int i=1;i<=n;i++)cin>>w[i]>>v[i];for(int i=1;i<=n;i++)for(int j=1;j<=t;j++){if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);这一行不同elsedp[i][j]=dp[i-1][j];}cout<<dp[n][t];return  0;}(2)完全背包for(int i=1;i<=n;i++)for(int j=1;j<=t;j++){if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);这一行不同，可以取多个elsedp[i][j]=dp[i-1][j];}

1.费马小定理int qmi(int a,int k,int mod){//快速幂 算a的k次方Int res=1;while(k){if(k&1/*判断是否为奇数 */) res=(int)res*a%mod;a=(int)a*a%mod;k>>=1/*实际上将K除以2*/;}return res;}Int inv(int a){Return qmi(a,M-2,M);}2.扩展欧几里得LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法{if(b==0){x=1,y=0;return a;}LL ret=exgcd(b,a%b,y,x);y-=a/b*x;return ret;}LL getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1{LL x,y;LL d=exgcd(a,mod,x,y);return d==1?(x%mod+mod)%mod:-1;}3.线性递推inv[1] = 1;for(int i=2;i<=n;i++){inv[i] = p - (p / i * inv[p % i] % p) % p;}

#include<bits/stdc++.h>using namespace std;#define int long long#define endl '\n'signed main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);string a,b;a="nihao";int t=a.find("c");cout<<t;return  0;}

#include<bits/stdc++.h>using namespace std;#define int long long#define endl '\n'const int dx[]={0,0,1,-1};const int dy[]={1,-1,0,0};int g[5][5];vector<pair<int, int> > ans;queue<pair<int,int> > q;vector<pair<int,int> >last;void bfs(void){for(int i=0;i <5;i++)for(int j=0;j<5;j++){cin>>g[i][j];if(i==0&&j==0)g[i][j]=0;else if(g[i][j]==1)g[i][j]=0x3f3f3f3f;elseg[i][j]=-1;}q.push({0, 0});while(q.size()){int x=q.front().first,y=q.front().second;q.pop();for(int i=0;i<4;i++){int nx=dx[i]+x;int ny=dy[i]+y;if(nx>=0&&ny>=0&&nx<5&&ny<5&&g[nx][ny]==-1){g[nx][ny]=g[x][y]+1;q.push({nx,ny});last.push({nx,ny});}}}}signed main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);bfs();for(int i=0;i<5;i++){for(int j=0;j<5;j++)cout<<setw(10)<<g[i][j];cout<<endl;}reverse(last.begin(),last.end())for(int i=0;i<ans.size(),i++){}return  0;}

#include <iostream>#include <cstdio>using namespace std;int main(){int year,month,day;cin>>year>>month;if(month==2){if(year%4==0&&year%100!=0||year%400==0){day=29;}else{day=28;}}else if(month==4||month==6||month==9||month==11){day=30;}else{day=31;}cout<<day;return 0;}

可以引入一个新的变量，与if语句结合进行赋值#include <stdio.h>int main(){int a,b,c,d,t;scanf("%d%d%d%d",&a,&b,&c,&d);if(a<b) {t=a;a=b;b=t;}if(c<d) {t=c;c=d;d=t;}if(a<c) {t=a;a=c;c=t;}if(b<d) {t=b;b=d;d=t;}if(b<c) {t=b;b=c;c=t;}printf("%d %d %d %d\n",d,c,b,a);return 0;}

#include<iostream>using namespace std;int main(){int a;cin>>a;if(a!=2&&a%2==0)cout<<"YES, you can divide the watermelon into two even parts."<<endl;elsecout<<"NO, you can't divide the watermelon into two even parts."<<endl;return 0;}a

#include<stdio.h>int main(){int a,c,d,e,f,g,h,l,z;char b;printf("请输入您想要打印的字符：");b=getchar();printf("请输入您想要打印菱形的行数（必须为正奇数）：（输入q表示终止程序）");while(scanf("%d",&z)==1){if(z%2==0){printf("请检查输入的是否为正奇数并重新输入：");continue;}else{for(a=1;a<=z/2+1;a++){for(c=1;c<=z/2+1-a;c++)printf(" ");for(d=1;d<=2*a-1;d++)putchar(b);printf("\n");}for(f=1;f<=z/2;f++){for(g=0;g>-f;g--)printf(" ");for(h=1;h<=z-2*f;h++)putchar(b);printf("\n");}}}return 0;}