藍橋杯補題

方法技巧：

1.進行循環暴力騙分，然后每一層的初始進行判斷，如果已經不滿足題意了，那么久直接continue，后面的循環就不用浪費時間了。我們可以把題目所給的等式，比如說有四個未知量，那么我們可以用其他的三個未知量進行確定表示最后一個未知量，這樣我們就可以少一層暴力循環。

2.日期類的問題，我們可以直接枚舉年份，判斷閏年還是平年，然后根據這個選擇二月份的時間。之后根據月份選擇天數。

3.直接bfs或者dfs暴力，要盡可能地剪枝，比如說以后的情況就已經不滿足了就要及時的return

4.記憶化，之前跑過的結果就直接return回之前的答案，不用那么麻煩的糾結是否可以實現。

5.注意一個問題，就是說，要范圍，尤其是二分的時候。

6.注意如果最后一個數據還未進入答案的統計時候，在遍歷完循環，要記得單獨再加一個判斷最后的一個數據是否可以更新答案。

7.充分挖掘，如果說不滿足要求了，就可以提前退出了，寫暴力循環的時候，一定要看能不能盡可能地優化。

【第十四屆藍橋杯考前速成】必考知識點及代碼模板總結，看完至少多拿50分_藍橋杯考前必看-CSDN博客

第八屆：

????????????????????????????????

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,a,b;
int oppo[7]={0,4,5,6,1,2,3};
bool st[7][7];
struct matrix{int c[7][7];matrix(){memset(c,0,sizeof(c));}
}A,res;matrix operator * (matrix &x,matrix &y){matrix t;for(int i=1;i<=6;i++){for(int j=1;j<=6;j++){for(int k=1;k<=6;k++){t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j])%mod;}}}return t;
}
void fastpow(int k)
{for(int i=1;i<=6;i++){res.c[1][i]=4;}for(int i=1;i<=6;i++){for(int j=1;j<=6;j++){if(st[i][oppo[j]]) A.c[i][j]=0;else A.c[i][j]=4;}}while(k){if(k&1) res=res*A;A=A*A;k>>=1;}
}
int main(){cin>>n>>m;while(m--){cin>>a>>b;st[a][b]=st[b][a]=1;}fastpow(n-1);int ans=0;for(int i=1;i<=6;i++){ans=(ans%mod+res.c[1][i]%mod)%mod;}cout<<ans<<"\n";return 0;
}

P8626 [藍橋杯 2015 省 A] 災后重建?

是一個分治問題，還是不太會。目前只是知道暴力。

就是要構建一個生成樹，使他們能給聯通，代價就是構成這個生成樹的最大邊的權值。

每一次詢問都會進行重新更新，也就是init。

#include<bits/stdc++.h>
using namespace std;int N, M, Q;
const int maxM = 2e5;
const int maxN = 5e4 + 5;
int par[maxN];//定義邊 
struct edge {int begin, end, cost;
}edges[maxM];bool cmp(edge x, edge y) {return x.cost<y.cost;
}//并查集
int get_root(int a) {    //求根節點 if(par[a] != a) {par[a] = get_root(par[a]);}return par[a];
}//查詢是否在同一集合中 
bool query(int a,int b) {return get_root(a) == get_root(b);
}//合并兩個結點 
void merge(int a,int b) {par[get_root(a)] = get_root(b);
}//每次詢問都要初始化 
void init() {for(int i = 1;i <= N;i++) {par[i] = i;}
}int solve(int l, int r, int k, int c) {init();for(int i = 0;i < M;i++) {int begin = edges[i].begin;int end = edges[i].end;int cost = edges[i].cost;if(get_root(begin) == get_root(end)) {   //該邊的兩個結點已經在同一個集合中 continue;}else {merge(begin, end);  //合并加邊 }//每添加一條邊都要判斷一下已經滿足條件，是就退出 bool flag = true;int parent = 0;//檢查l到r中模k余c的點是否已經連通 for(int i = l;i <= r;i++) {if(i % k == c) {if(parent == 0) {parent = get_root(i);}else {if(parent != get_root(i)) {   //實際上就是檢查這些結點是不是在同一個集合里 flag = false;break;}}}}if(flag) {cout<<cost<<endl;  //已經在同一個集合，說明已經連通 break;}}return 1;
}int main() {cin>>N>>M>>Q;for(int i = 0;i < M;i++) {cin>>edges[i].begin>>edges[i].end>>edges[i].cost;} sort(edges, edges + M, cmp);   //邊從小到大排序 for(int i = 0;i < Q;i++) {int l, r, k, c;cin>>l>>r>>k>>c;solve(l, r, k, c);}return 0;
}

方格填數問題：

本質上就是一個dfs，然后在dfs過程中。

我們可以直接按照正常的順序進行遍歷，從左到右，在從上到下進行遍歷。這樣就可以滿足我們所有的遍歷情況，在遍歷的過程中，如果check已經是false了那么我們就即使的進行break掉，直接進行下一層的遍歷，同時也不會增加額外的開銷。

#include <bits/stdc++.h>
using namespace std;int mp[10][10];
int ans = 0;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};bool check(int i,int j){    //檢查9宮格 for(int x=i-1;x<=i+1;x++){for(int y=j-1;y<=j+1;y++){if(abs(mp[x][y]-mp[i][j])==1)return false;}}return true;
}int num[10] = {0};
int vis[10][10] = {0};void dfs(int x, int y) {if (x==3&&y==4) {ans++;return;}// 嘗試填充數字for (int j = 0; j < 10; j++) {if(num[j]==0){mp[x][y]=j;  //填數num[j]=1;     if(check(x,y)){if(y==4)dfs(x+1,1);    //換行 elsedfs(x,y+1);}num[j]=0;  mp[x][y]=100; }}
}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);// 初始化地圖for (int i = 0; i <= 5; i++) {for (int j = 0; j <= 6; j++) {mp[i][j] = 100;}}dfs(1, 2);cout << ans << "\n";return 0;
}

寒假作業：

這個也是一個dfs。


#include <bits/stdc++.h>
using namespace std;int ans;
int vis[20]={0};
int mp[100];
int check(int x)
{if(x>=3&&(mp[1]==0||mp[2]==0||mp[3]==0)) return 0;if(x>=6&&(mp[4]==0||mp[5]==0||mp[6]==0)) return 0;if(x>=9&&(mp[7]==0||mp[8]==0||mp[9]==0)) return 0;if(x>=12&&(mp[10]==0||mp[11]==0||mp[12]==0)) return 0;if(x>=3&&(mp[1]+mp[2]!=mp[3])) return 0;if(x>=6&&(mp[4]-mp[5]!=mp[6])) return 0;if(x>=9&&(mp[7]*mp[8]!=mp[9])) return 0;if(x>=12&&(mp[10]!=mp[12]*mp[11])) return 0;return 1;
}
void dfs(int x){if(x==14){if(check(x))ans++;return;}for(int i=1;i<=13;i++){if(vis[i]==0){mp[x]=i;vis[i]=1;if(check(x))dfs(x+1);mp[x]=0;vis[i]=0;}}}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);ans=0;memset(mp,0,sizeof(mp));dfs(1);cout << ans << "\n";return 0;
}

密碼脫落：

在這個問題中。

我們有兩個問題需要考慮，一個是這個種子丟的地方不知道，另外一個丟了幾個也不知道。

那么其實本質上就是說，非連續的子序列相同問題。我們要前后對稱，那么我們就需要找到一個最長的子序列，這個子序列是回文的。如果我們暴力的尋找，會很麻煩時間復雜度一定會炸掉。之后呢我們可以構建一個反串，就是說，這個反串和正串進行尋找最長的公共子序列，那么這樣復雜度就是n2滿足我們的要求。

#include <iostream>
#define ll long long
#include <algorithm>
#include <string>
#include <string.h>
#include <cstdio>using namespace std;
int dp[1010][1010];
int main(){string str1,str2;while(cin>>str1){memset(dp,0,sizeof(dp));str2=str1;int len=str1.size();reverse(str2.begin(),str2.end());		//翻轉串for(int i=1;i<=len;i++){				for(int j=1;j<=len;j++){if( str1[i-1] == str2[j-1] ) dp[i][j]=dp[i-1][j-1]+1;else{dp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}}cout<< len-dp[len][len] <<endl;}return 0;
}

迷宮問題：

這個問題的思路是這個樣子的。

1.從終點方向跑路線，這樣可以直接更新重點到每一點的最短距離。

2.從正向進行構建路線，優選選擇字段序小的字母，這個字母之后進行找到下一個字母，同時這兩個位置之間的距離恰好就是1，這樣就是我們正確的最小路徑。

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
char a[40][60];                                                 //存圖
int nextx[4] = { 1,0,0,-1 }, nexty[4] = { 0,-1,1,0 };           //D<L<R<U      字典序直接把方向數組處理好就可以了
int dist[40][60];                                               //定義一個dist數組，用來存放各點到終點的最短距離
char dir[4] = { 'D','L','R','U' };                             
bool check(int x, int y) {return x > 0 && y > 0 && x <= 50 && y <= 50 && a[x][y] == '0'&&dist[x][y] == -1;
}
void bfs() {                                                    //BFS掃一遍，求出各點到終點的最短距離queue<pair<int, int> >q;memset(dist, -1, sizeof(dist));dist[30][50] = 0;q.push({ 30,50 });while (!q.empty()) {pair<int ,int> t = q.front();q.pop();for (int i = 0; i < 4; i++) {int newx = t.first + nextx[i];int newy = t.second + nexty[i];if (check(newx, newy)) {dist[newx][newy] = dist[t.first][t.second] + 1;q.push({ newx,newy });}}}
}int main() {for (int i = 1; i <= 30; i++)for (int j = 1; j <= 50; j++)cin >> a[i][j];bfs();int x = 1, y = 1;                                                                       //從起點開始遍歷string res;                                                                             //存答案while (x != 30 || y != 50) {for (int i = 0; i < 4; i++) {int newx = x + nextx[i];int newy = y + nexty[i];if (newx > 0 && newy > 0 && newx <= 50 && newy <= 50 && a[newx][newy] == '0'&&dist[newx][newy]==dist[x][y]-1) {x = newx, y = newy;res += dir[i];break;}}}cout << res << "\n";return 0;
}

方格分割：

我們就是從（3，3）中心的位置進行搜索的，然后如果走到了邊界，說明就是一種方案。然后因為我們四個方向如果走到一個點后，那么我們可能是可能會重復的。所以答案是/4.

這個點和對稱點同時要置為1.

#include<bits/stdc++.h>
using namespace std;short a[1005][1005];
int dx[5]={0,0,-1,1};
int dy[5]={1,-1,0,0};
int ans;
void dfs(int x,int y){if(x==0||y==0||x==6||y==6){ans++;return;}for(int i=0;i<4;i++){int xx=x+dx[i];int yy=y+dy[i];if(a[xx][yy]==0){a[xx][yy]=1;a[6-xx][6-yy]=1;dfs(xx,yy);a[xx][yy]=0;a[6-xx][6-yy]=0;}}
}void solve()
{a[3][3]=1;ans=0;dfs(3,3);cout<<ans/4<<"\n";}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;T=1;//cin>>T;while(T--){solve();}
}

正則問題，

我們清晰的發現也是一個dfs問題，直接進行遞歸就行。

#include<bits/stdc++.h>
using namespace std;short a[1005][1005];
int dx[5]={0,0,-1,1};
int dy[5]={1,-1,0,0};
int ans;
void dfs(int x,int y){if(x==0||y==0||x==6||y==6){ans++;return;}for(int i=0;i<4;i++){int xx=x+dx[i];int yy=y+dy[i];if(a[xx][yy]==0){a[xx][yy]=1;a[6-xx][6-yy]=1;dfs(xx,yy);a[xx][yy]=0;a[6-xx][6-yy]=0;}}
}void solve()
{a[3][3]=1;ans=0;dfs(3,3);cout<<ans/4<<"\n";}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;T=1;//cin>>T;while(T--){solve();}
}

包子湊數問題。

首先根據兩個數論定理。

ax+by=z 有解的情況，只能是，gcd（a,b）可以被z整數。

如果ab互質的話，說明了z是任何1的倍數，那么ab就可以表示所有的數。

如果不是互質的話，根據一個定理，他所不能表達的數字一定在 a*b-a-b內。那么我們就直接判斷是否可以得到這個區間的所有數字。這是一個完備空間，我們就直接進行完全背包的暴力。

#include <bits/stdc++.h>
using namespace std;
/**測試用例23 5答案4*/
typedef long long LL;
const int N = 1e6 + 5;LL f[N];  //表示湊出j個包子的方法總數
int a[N]; //每種規格中包子的數量
int ans;  //組裝不出來的包子個數//最大公約數，輾轉相除法
int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);
}int main() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];//賽瓦維斯特定理 :  兩個互質數a,b表示不出來的最大數字是 a?b?a?b//下面排序后找出極小值與次小值，它們的乘積再減去極小和次小，就是極限值sort(a + 1, a + 1 + n);int m1 = a[1], m2 = a[2]; //最小和次小int M = m1 * m2 - m1 - m2;//求出所有數字的最大公約數int g = a[1];for (int i = 2; i <= n; i++) g = gcd(g, a[i]);/*裴蜀定理:如果所有數字的最大公約數大于1，那么必然存在無法表示出的數字。不互質栗子:比如3 和 6      兩種規格，能組裝的就是 3,6,9,12,15,這個變化就是它們的最大公約數3。比如3 和 6 和 9 三種規格, 能組裝的也是 3,6,9,12,15,這個變化就是它們的最大公約數3。此時 ，類似于 1,2,4,5,7,...之類的數字均是無法湊出的，有無窮多個。互質栗子:比如 3 和  4   兩種規格， 能組裝的就是 3,4,6,7,8,9,10,11,12...., 根據賽瓦維斯特定理，我們知道，最大的不能組裝的數字是3*4-3-4=5比如 3 和  4 和 6 三種規格，因為3，4就能組裝出5以上的所有數字，所以我們只需要從最小a[1]到 M 中查找即可。*/if (g > 1) {cout << "INF" << endl; // cout << -1 << endl; //青少組要求輸出-1return 0;}/**完全背包f[j]表示湊出j個包子的方法總數，簡單說就是如果f[j]>0就湊得出，f[j]=0就湊不出。遞推式 f[j]=f[j?第i種蒸籠包子數]+1 (f[j?第i種蒸籠包子數]>=1)當j?第i種蒸籠包子數是可以湊成的，那么只需對其+第i種蒸籠包子數就可以湊成j個包子數。*/f[0] = 1; //  0個包子這個狀態是合法的，是可以到達的狀態。而且只能是一種方案，就是不管是哪種規格，一概不要for (int i = 1; i <= n; i++)for (int j = 1; j <= M; j++)if (j >= a[i] && f[j - a[i]]) f[j]++;//枚舉每個可能的數字，如果這個數字存在1種以上的方案，就是可以湊出，否則就是無法湊出for (int i = 1; i <= M; i++)if (!f[i]) ans++;//輸出答案cout << ans << endl;return 0;
}

油漆面積

其本質就是一個二位差分二位前綴和問題。

那么我們要注意的是，因為他所告訴你的不是格子的坐標，而是坐標系的坐標。

那么就需要進行特殊表示。

#include<bits/stdc++.h>
using namespace std;short a[10005][10005];
void solve()
{int k;cin>>k;for(int i=1;i<=k;i++){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;a[x1][y1]+=1;a[x2][y1]-=1;a[x1][y2]-=1;a[x2][y2]+=1;}int ans=0;for(int i=0;i<=10000;i++){for(int j=0;j<=10000;j++){a[i][j] = (i > 0 ? a[i-1][j] : 0) + (j > 0 ? a[i][j-1] : 0) - (i > 0 && j > 0 ? a[i-1][j-1] : 0) + a[i][j];if(a[i][j]) ++ans;}}cout<<ans<<"\n";
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;T=1;//cin>>T;while(T--){solve();}
}


#include<bits/stdc++.h>
using namespace std;
#define int long 
int run(int x)
{if(x%400==0) return 1;if(x%4==0&&x%100!=0) return 1;return 0;
}
int a[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};signed main() {ios::sync_with_stdio(false);cin.tie(0);int t=6;int ans=0;for(int i=2000;i>=1901;i--){int be=12;int en=1;if(run(i)) a[2]=29;else a[2]=28;for(int j=be;j>=en;j--){int bee=a[j];int enn=1;for(int k=bee;k>=enn;k--){if(t==0){ans++;}t=(t-1+7)%7;}}}cout<<ans<<"\n";
}

乘積尾零

這個問題應該不可以用每次乘完，去除完了末尾0然后進行繼續計算，還是有可能會發生溢出問題。那么我們直接分割，分成有多少個2和5.然后取min，這樣最后的答案就是我們的要的答案。

三體攻擊

一個三維進行的計算問題。最后進行二分判斷，第一個爆炸的飛船。

全球變暖

一個bfs，我們注意要先將下一個點標志城true，這樣的話就不會造成這個點被加入多次，造成時間上的超時。


#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
int n;
int mp[1005][1005]={0};
bool vis[1005][1005];
struct node{int x,y;
};
int bfs(int xxx,int yyy)
{queue<node>q;q.push({xxx,yyy});int flag=1;while(!q.empty()){auto [x,y]=q.front();q.pop();vis[x][y]=true;int num=0;for(int i=0;i<4;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mp[xx][yy]){num++;if(vis[xx][yy]==false) {vis[xx][yy]=true;q.push({xx,yy});}}}if(num==4) flag=0;}return flag;}
int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){char c;cin>>c;if(c=='#') mp[i][j]=1;}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(!vis[i][j]&&mp[i][j]){ans+=bfs(i,j);}}}cout<<ans<<"\n";}

付賬問題：

#include <bits/stdc++.h>
using namespace std;long long a[500010];int main() {int n;long long s;cin >> n >> s;for (int i = 0; i < n; i++) {cin >> a[i];}//開始貪心選擇sort(a, a + n); //排序，從小到大double avg = 1.0 * s / n;double sum = 0.0;for (int i = 0; i < n; i++) {if (a[i] * (n - i) < s) { //把錢全拿出的人sum += (a[i] - avg) * (a[i] - avg);s -= a[i]; //更新還差多少錢} else { //不需要把錢全拿出的人。剩下的人中，錢最少的人都可以達到cur_avgdouble cur_avg = 1ASEE.0 * s / (n - i); //注意這里的s是還差多少錢sum += (cur_avg - avg) * (cur_avg - avg) * (n - i); //如果這個人有錢付，那么后面的人一定也能付，所以直接乘后面的人數(n - i)即可break;}}printf("%.4f", sqrt(sum / n));return 0;
}

顏色平衡樹：求子樹的個數。字數滿足每一個顏色的子節點數量一樣。

直接進行暴力bfs進行計算。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>using namespace std;int main() {int n;cin >> n;vector<int> C(n + 1); // 存儲每個節點的顏色vector<vector<int>> children(n + 1); // 存儲每個節點的子節點列表for (int i = 1; i <= n; ++i) {int ci, fi;cin >> ci >> fi;C[i] = ci;if (fi != 0) {children[fi].push_back(i);}}int ans = 0;for (int u = 1; u <= n; ++u) {unordered_map<int, int> colorCount;queue<int> q;q.push(u);while (!q.empty()) {int node = q.front();q.pop();colorCount[C[node]]++;for (int child : children[node]) {q.push(child);}}bool valid = true;int cnt = -1;for (auto& pair : colorCount) {if (cnt == -1) {cnt = pair.second;} else {if (pair.second != cnt) {valid = false;break;}}}if (valid) {ans++;}}cout << ans << endl;return 0;
}

博弈論

using namespace std;
#include<vector>
#include<iostream>
#include<unordered_map>
typedef long long ll;class Solution {public:unordered_map<string,bool> mp;// 記錄各種狀態的勝利，失敗情況bool check(string s) {// 只剩下一個O，為必輸態int cnt=0;for(const auto &c:s) {if(c=='O') cnt++;}return cnt==1;}// 第二行先下的人是必輸的。// 由于小藍優先下，因為傳入的是XOOO,XXOO,OXOO,OXXO,是小藍已經下棋的狀態// 小藍已經下了棋，所以小喬具有主動權。 // 又因為第二行第一個下棋的人必輸，所以小喬在第一行應該讓自己輸，這樣小喬才會贏 // 因為每一個人都以最優策略下棋，所以小喬會爭取第一行輸// dfs("XOOO")表示以這個棋盤開始下棋，小喬的輸贏（算法默認優先找輸) // 返回true，表示小喬第一行只能贏，那么第二行先手就是小喬，小藍必贏 // 返回false，表示小喬擁有第一行輸的優先權，那么小喬第二行在最優策略下就一定贏，小藍就必輸// 最終可以知道小喬第一行贏對應小藍最終贏（兩行下完)// 小喬第一行可以輸對應小藍最終輸兩行下完）// 最后強調，對于小喬的優先策略就是輸！！！，因為dfs的結果只針對棋盤只有第一行時小喬的輸贏。 bool dfs(string s) {if(mp.count(s)) return mp[s];// 避免重復計算if(check(s)) {// 說明當前這個人只有一個空位下，走到這一步的人必輸mp[s]=false;return false;}int n=s.size();// 下一個for(int i=0; i<n; i++) {if(s[i]=='O') {string temp=s;temp[i]='X';if(dfs(temp)) {mp[s]=false;return false;}}}// 下兩個for(int i=0; i<n; i++) {if(i<n-1&&s[i]=='O'&&s[i+1]=='O') {string temp=s;temp[i]='X';temp[i+1]='X';if(dfs(temp)) {mp[s]=false;return false;}}}// 優先找輸，所以實在不可能輸了，在返回贏 mp[s]=true;return true;}
};char to_char(bool ans) {return ans?'V':'L';
}int main() {Solution solution;// dfs表示小喬能不能在第一行輸掉 bool r1=solution.dfs("XOOO"); bool r2=solution.dfs("XXOO"); bool r3=solution.dfs("OXOO"); bool r4=solution.dfs("OXXO"); cout << to_char(r1) << to_char(r2) << to_char(r3) << to_char(r4);return 0;
}

括號序列

暴力：

al表示還需要多少個左括號 ar表示還需要多少個右括號

l表示已經有了多少個左括號，r表示已經有了多少個右括號

每次往下遍歷的時候，需要保證當前的左括號數一定要大于右括號的數量

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;int n;
string s;
unordered_set<string> ret;void dfs(int l,int r,int al,int ar,int idx,string cur){if(idx==n){if(!al&&!ar)ret.insert(cur);return;}if(al)dfs(l+1,r,al-1,ar,idx,cur+'(');if(ar&&l>r)dfs(l,r+1,al,ar-1,idx,cur+')');if(s[idx]=='(')dfs(l+1,r,al,ar,idx+1,cur+'(');else if(l>r)dfs(l,r+1,al,ar,idx+1,cur+')');
}int main(){cin>>s;n=s.size();int al=0,ar=0,l=0;for(char c:s){if(c=='('){l++;}else if(c==')'){if(l==0)al++;else{l--;}}}ar=l;dfs(0,0,al,ar,0,"");cout<<ret.size();
}

迷宮

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
char a[40][60];                                                 //存圖
int nextx[4] = { 1,0,0,-1 }, nexty[4] = { 0,-1,1,0 };           //D<L<R<U      字典序直接把方向數組處理好就可以了
int dist[40][60];                                               //定義一個dist數組，用來存放各點到終點的最短距離
char dir[4] = { 'D','L','R','U' };                             
bool check(int x, int y) {return x > 0 && y > 0 && x <= 50 && y <= 50 && a[x][y] == '0'&&dist[x][y] == -1;
}
void bfs() {                                                    //BFS掃一遍，求出各點到終點的最短距離queue<pair<int, int> >q;memset(dist, -1, sizeof(dist));dist[30][50] = 0;q.push({ 30,50 });while (!q.empty()) {pair<int ,int> t = q.front();q.pop();for (int i = 0; i < 4; i++) {int newx = t.first + nextx[i];int newy = t.second + nexty[i];if (check(newx, newy)) {dist[newx][newy] = dist[t.first][t.second] + 1;q.push({ newx,newy });}}}
}int main() {for (int i = 1; i <= 30; i++)for (int j = 1; j <= 50; j++)cin >> a[i][j];bfs();int x = 1, y = 1;                                                                       //從起點開始遍歷string res;                                                                             //存答案while (x != 30 || y != 50) {for (int i = 0; i < 4; i++) {int newx = x + nextx[i];int newy = y + nexty[i];if (newx > 0 && newy > 0 && newx <= 50 && newy <= 50 && a[newx][newy] == '0'&&dist[newx][newy]==dist[x][y]-1) {x = newx, y = newy;res += dir[i];break;}}}cout << res << "\n";return 0;
}

RSA加密：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll p,q,e,ans;
ll n = 1001733993063167141,d = 212353;
ll C = 20190324;bool prime(ll x) {for(ll i = 2;i <= sqrt(x); i++) {if(x % i == 0) {return false;}}return true;
}ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;
}ll gcd_Ex(ll a,ll b,ll &x,ll &y) {   //ax+by=c的整數解 if(b==0) {x=1;y=0;return a;}ll x1,y1;ll gcd=gcd_Ex(b,a%b,x1,y1);  //bx+(a%b)y=gcd(a,b)有整數解x1,y1; x=y1;y=x1-a/b*y1;return gcd;
}ll mod_reverse(ll a,ll b) {   //求解ax%b==1 ll d,x,y;d=gcd_Ex(a,b,x,y);   //ax+by=gcd(a,b)有整數解x,yif(d==1) {return (x%b+b)%b;}else {             //無解 return -1;}
}ll fast_mul(ll a, ll b, ll mod){  //快速求解a*b%mod ll ans = 0;while(b) {if(b&1) {ans = (ans + a) % mod;}a=(a<<=1) % mod;b >>= 1;}return ans;
}ll pow_mod(ll a,ll b,ll mod) {   //快速求解a^b%modll res=1,base=a%mod;while(b) {if(b&1) {res=fast_mul(res,base,mod);}base=fast_mul(base,base,mod);b >>= 1;}return res;
}int main() {//求解p,q /*for(ll i=1000;;i++) {if(n%i==0&&prime(i)&&prime(n/i)&&gcd(d,(i-1)*(n/i-1))==1) {p=i;q=n/i;break;}}*/p=891234941,q=1123984201;ll t=(p-1)*(q-1);e=mod_reverse(d,t);ll x=pow_mod(C,e,n);cout<<x;return 0;
}

外賣模擬：

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);priority_queue<int,vector<int>,greater<int>> h[100010]; //為每一家店創造一個優先隊列（小頂對）int n, m, t;cin >> n >> m >> t;for(int i = 1; i<=m; i++){int x, y;cin >> x >> y;h[y].push(x);//把時間點存入這家店的隊列中}int cnt = 0;for(int i = 1; i<=n; i++){int pri = 0; //“優先級”int lastget = 0; //上一次訂單的時間bool in = false; //是否在“優先推薦”中while(!h[i].empty()){int x = h[i].top(); //訂單時間h[i].pop();if(lastget!=x) pri-=(x-lastget-1);//如果不是同一個時間點多個訂單的話，減去沒有訂單的那些時間需要減去的“優先級”if(pri<0) pri = 0; //可能小于零，設置成零if(in&&pri<=3) in = false; //如果在推薦里，但是此時“優先級”小于等于3，踢出推薦中pri+=2; //拿到兩點“優先級”lastget = x; //更新上一次時間if(pri>5) in = true; //如果此時“優先級”大于3，踢出推薦中}//注意的是，這里需要先判斷是否被踢出推薦，然后再加上2，//因為加入的條件是大于5，退出的條件是小于等于3，如果此時小于等于3了，但是加上2之后不小于3了，按照程序，符合“在推薦中+沒有小于等于3”，不會被踢出去，//但是由于在這些空余的時間里，已經出了推薦榜，如果再進，需要大于5，此時沒有達到在加入的條件，沒有在推薦榜中//這里，由于要看的是時間T，但是T有可能不是最后一次收到訂單的時間，需要額外判斷，方法同上if(lastget!=t) pri-=(t-lastget);if(in&&pri<=3) in = false;if(in){cnt++;}} cout << cnt;return 0;
}

修改數組：v

#include<bits/stdc++.h>#define rep(i, a, b) for(int i = a; i < b ; i++)using namespace std;const int N = 1e6 + 10;
int fa[N]; //并查集存儲當前 “節點族” 最大還有哪個節點未用上
int n;int find(int x)
{if(fa[x] != x) fa[x] = find(fa[x]); //向上查找祖先節點，同時進行 “路經壓縮“return fa[x]; //返回最大的可以用的節點
}int main()
{cin >> n;//1.初始化并查集rep(i, 1, N) //注意此時，并查集初始化取決于 數組中元素A的大小fa[i] = i;//2.對于每個節點，加入并查集，更新最大未使用的元素int x;rep(i, 1, n + 1){scanf("%d", &x);x = find(x); //找到當前最大未使用的元素printf("%d ", x);fa[x] = x + 1; //當前節點已經用過了 -> 往后偏移 -//如果是最新的，那么會直接輸出當前元素，反之，輸出之前記錄的可以使用的最大元素}return 0;
}

狀態壓縮：

#include <iostream>
using namespace std;
int n,m,k;long long dp[1<<21],a[105];
int main()
{cin>>n>>m>>k;
for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)
{int x;cin>>x;
a[i]|=(1<<(x-1));
}
for(int i=1;i<(1<<m);i++)dp[i]=1e9;
for(int d=0;d<(1<<m);d++)for(int i=1;i<=n;i++)dp[d|a[i]]=min(dp[d|a[i]],dp[d]+1);long long ans=dp[(1<<m)-1];
cout<<(ans==1e9?-1:ans);return 0;
}

倍數問題：

暴力枚舉

#include <bits/stdc++.h>using namespace std;int main() {int n, k;cin >> n >> k;int nums[n];// 讀取輸入的 n 個整數并存儲到數組中for(int i = 0; i < n; i++) {cin >> nums[i];}// 對數組進行排序sort(nums, nums + n);// 初始化結果變量為 0int ans = 0;// 三重循環遍歷數組中所有可能的三個數的組合for (int i = n - 1; i >= 2; i--) {for (int j = i - 1; j >= 1; j--) {for (int t = j - 1; t >= 0; t--) {// 計算當前三個數的和int sum = nums[i] + nums[j] + nums[t];// 如果當前和是 k 的倍數，更新結果為當前和和原結果中的較大值if (sum % k == 0) {ans = max(ans, sum);}// 如果當前和小于結果，跳出內層循環if (sum < ans) {break;}}// 如果當前三個數的和已經小于結果，跳出內層循環if(nums[i] + nums[j] + nums[j - 1] < ans) {break;}}// 如果當前三個數的和已經小于結果，跳出外層循環if(nums[i] + nums[i - 1] + nums[i - 2] < ans) {break;}}// 輸出結果cout << ans << endl;return 0;
}

盡可能地平均

#include <bits/stdc++.h>
using namespace std;long long a[500010];int main() {int n;long long s;cin >> n >> s;for (int i = 0; i < n; i++) {cin >> a[i];}//開始貪心選擇sort(a, a + n); //排序，從小到大double avg = 1.0 * s / n;double sum = 0.0;for (int i = 0; i < n; i++) {if (a[i] * (n - i) < s) { //把錢全拿出的人sum += (a[i] - avg) * (a[i] - avg);s -= a[i]; //更新還差多少錢} else { //不需要把錢全拿出的人。剩下的人中，錢最少的人都可以達到cur_avgdouble cur_avg = 1.0 * s / (n - i); //注意這里的s是還差多少錢sum += (cur_avg - avg) * (cur_avg - avg) * (n - i); //如果這個人有錢付，那么后面的人一定也能付，所以直接乘后面的人數(n - i)即可break;}}printf("%.4f", sqrt(sum / n));return 0;
}

包子湊數：

#include <bits/stdc++.h>
using namespace std;
/**測試用例23 5答案4*/
typedef long long LL;
const int N = 1e6 + 5;LL f[N];  //表示湊出j個包子的方法總數
int a[N]; //每種規格中包子的數量
int ans;  //組裝不出來的包子個數//最大公約數，輾轉相除法
int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);
}int main() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];//賽瓦維斯特定理 :  兩個互質數a,b表示不出來的最大數字是 a?b?a?b//下面排序后找出極小值與次小值，它們的乘積再減去極小和次小，就是極限值sort(a + 1, a + 1 + n);int m1 = a[1], m2 = a[2]; //最小和次小int M = m1 * m2 - m1 - m2;//求出所有數字的最大公約數int g = a[1];for (int i = 2; i <= n; i++) g = gcd(g, a[i]);/*裴蜀定理:如果所有數字的最大公約數大于1，那么必然存在無法表示出的數字。不互質栗子:比如3 和 6      兩種規格，能組裝的就是 3,6,9,12,15,這個變化就是它們的最大公約數3。比如3 和 6 和 9 三種規格, 能組裝的也是 3,6,9,12,15,這個變化就是它們的最大公約數3。此時 ，類似于 1,2,4,5,7,...之類的數字均是無法湊出的，有無窮多個。互質栗子:比如 3 和  4   兩種規格， 能組裝的就是 3,4,6,7,8,9,10,11,12...., 根據賽瓦維斯特定理，我們知道，最大的不能組裝的數字是3*4-3-4=5比如 3 和  4 和 6 三種規格，因為3，4就能組裝出5以上的所有數字，所以我們只需要從最小a[1]到 M 中查找即可。*/if (g > 1) {cout << "INF" << endl; // cout << -1 << endl; //青少組要求輸出-1return 0;}/**完全背包f[j]表示湊出j個包子的方法總數，簡單說就是如果f[j]>0就湊得出，f[j]=0就湊不出。遞推式 f[j]=f[j?第i種蒸籠包子數]+1 (f[j?第i種蒸籠包子數]>=1)當j?第i種蒸籠包子數是可以湊成的，那么只需對其+第i種蒸籠包子數就可以湊成j個包子數。*/f[0] = 1; //  0個包子這個狀態是合法的，是可以到達的狀態。而且只能是一種方案，就是不管是哪種規格，一概不要for (int i = 1; i <= n; i++)for (int j = 1; j <= M; j++)if (j >= a[i] && f[j - a[i]]) f[j]++;//枚舉每個可能的數字，如果這個數字存在1種以上的方案，就是可以湊出，否則就是無法湊出for (int i = 1; i <= M; i++)if (!f[i]) ans++;//輸出答案cout << ans << endl;return 0;
}

枚舉

#include<bits/stdc++.h>
using namespace std;short a[1005][1005];
int dx[5]={0,0,-1,1};
int dy[5]={1,-1,0,0};
int ans;
void dfs(int x,int y){if(x==0||y==0||x==6||y==6){ans++;return;}for(int i=0;i<4;i++){int xx=x+dx[i];int yy=y+dy[i];if(a[xx][yy]==0){a[xx][yy]=1;a[6-xx][6-yy]=1;dfs(xx,yy);a[xx][yy]=0;a[6-xx][6-yy]=0;}}
}void solve()
{a[3][3]=1;ans=0;dfs(3,3);cout<<ans/4<<"\n";}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;T=1;//cin>>T;while(T--){solve();}
}// #include <iostream>
// using namespace std;// const int to[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//方向數組
// const int N = 6;//邊上的格子數，不是點數，點數要+1
// bool map[N + 1][N + 1];  //表示點
// int ans;       //方法數// void dfs(int x, int y) {
//     if (x == 0 || y == 0 || x == 6 || y == 6) {
//         ans++;
//         return;
//     }
//     for (int i = 0; i < 4; i++) {
//         //注意這里好像只能建臨時的坐標，而不能建全局變量
//         int tx = x + to[i][0];
//         int ty = y + to[i][1];
//         //不用擔心越界，因為到邊界就會return
//         if (map[tx][ty] == false) {
//             map[tx][ty] = true;
//             map[N - tx][N - ty] = true;//由于是關于起點中心對稱的，所以每次搜索會涉及兩個點
//             dfs(tx, ty);
//             map[tx][ty] = false;
//             map[N - tx][N - ty] = false;
//         }
//     }
// }// int main(void) {
//     map[3][3] = true;//起點置為真
//     dfs(3, 3);//開始搜索
//     printf("%d\n", ans/4);
//     return 0;
// }

正則問題：

#include <bits/stdc++.h>
using namespace std;
int re(int ans){char c;while(cin>>c){if(c == '\r' || c == '\n') return ans;else if(c == 'x') ans ++;else if(c == '(') ans += re(0);else if(c == ')') return ans;else if(c == '|') return max(ans, re(0));}return ans;
} 
int main() {cout<<re(0);return 0;
}

方格填數

#include <bits/stdc++.h>
using namespace std;int mp[10][10];
int ans = 0;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};bool check(int i,int j){    //檢查9宮格 for(int x=i-1;x<=i+1;x++){for(int y=j-1;y<=j+1;y++){if(abs(mp[x][y]-mp[i][j])==1)return false;}}return true;
}int num[10] = {0};
int vis[10][10] = {0};void dfs(int x, int y) {if (x==3&&y==4) {ans++;return;}// 嘗試填充數字for (int j = 0; j < 10; j++) {if(num[j]==0){mp[x][y]=j;  //填數num[j]=1;     if(check(x,y)){if(y==4)dfs(x+1,1);    //換行 elsedfs(x,y+1);}num[j]=0;  mp[x][y]=100; }}
}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);// 初始化地圖for (int i = 0; i <= 5; i++) {for (int j = 0; j <= 6; j++) {mp[i][j] = 100;}}dfs(1, 2);cout << ans << "\n";return 0;
}

寒假作業：

#include <bits/stdc++.h>
using namespace std;int ans;
int vis[20]={0};
int mp[100];
int check(int x)
{if(x>=3&&(mp[1]==0||mp[2]==0||mp[3]==0)) return 0;if(x>=6&&(mp[4]==0||mp[5]==0||mp[6]==0)) return 0;if(x>=9&&(mp[7]==0||mp[8]==0||mp[9]==0)) return 0;if(x>=12&&(mp[10]==0||mp[11]==0||mp[12]==0)) return 0;if(x>=3&&(mp[1]+mp[2]!=mp[3])) return 0;if(x>=6&&(mp[4]-mp[5]!=mp[6])) return 0;if(x>=9&&(mp[7]*mp[8]!=mp[9])) return 0;if(x>=12&&(mp[10]!=mp[12]*mp[11])) return 0;return 1;
}
void dfs(int x){if(x==14){if(check(x))ans++;return;}for(int i=1;i<=13;i++){if(vis[i]==0){mp[x]=i;vis[i]=1;if(check(x))dfs(x+1);mp[x]=0;vis[i]=0;}}}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);ans=0;memset(mp,0,sizeof(mp));dfs(1);cout << ans << "\n";return 0;
}

里外世界：

#include <bits/stdc++.h>
using namespace std;
#define int long longconst int INF = 1e18;signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) cin >> b[i];vector<vector<int>> dp(n + 1, vector<int>(2, -INF));dp[1][0] = a[1]; // 初始在表世界1號點for (int i = 2; i <= n; ++i) {// 從表世界i-1到表世界iif (dp[i-1][0] != -INF) {dp[i][0] = dp[i-1][0] + a[i];}// 從里世界i-1到表世界i（躍遷）if (dp[i-1][1] >= k) {dp[i][0] = max(dp[i][0], dp[i-1][1] + a[i] - k);}// 從里世界i-1到里世界iif (dp[i-1][1] != -INF) {dp[i][1] = dp[i-1][1] + b[i];}// 從表世界i-1到里世界i（躍遷）if (dp[i-1][0] >= k) {dp[i][1] = max(dp[i][1], dp[i-1][0] + b[i] - k);}}cout << max(dp[n][0], dp[n][1]) << '\n';return 0;
}

bfs

#include <bits/stdc++.h>
using namespace std;
#define int long longint num;
int n,m;
char mp[1000][1000];
int vis[501][501];
int dis[501][501];
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
int fa[260005];
map<array<int,2>,int>id;int _find(int x){if(x==fa[x]) return x;else{fa[x]=_find(fa[x]);return fa[x];}
}
void _union(int x,int y)
{int fax=_find(x);int fay=_find(y);fa[fax]=fay;
}
void bfs(int bex,int bey)
{queue<array<int,2>>q;q.push({bex,bey});vis[bex][bey]=1;int faa=_find(id[{bex,bey}]);while(q.size()){auto [x,y]=q.front();q.pop();vis[x][y]=1;for(int i=0;i<4;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx<1||xx>n||yy<1||yy>m) continue;if(vis[xx][yy]==1) continue;if(mp[xx][yy]=='#') continue;vis[xx][yy]=1;q.push({xx,yy});_union(id[{bex,bey}],id[{xx,yy}]);}}}
void solve() {cin>>n>>m;num=0;for(int i=1;i<=260000;i++) fa[i]=i;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>mp[i][j];id[{i,j}]=++num;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(vis[i][j]==0&&mp[i][j]=='.'){bfs(i,j);}}}int Q;cin>>Q;while(Q--){int x1,x2,y1,y2,enx,eny;cin>>x1>>y1>>x2>>y2>>enx>>eny;int dis1=abs(x1-enx)+abs(y1-eny);int dis2=abs(x2-enx)+abs(y2-eny);int cnt1=0;int cnt2=0;for(int i=0;i<4;i++){int xx=x1+dx[i];int yy=y1+dy[i];if(xx<1||xx>n||yy<1||yy>m) cnt1++;else if(mp[xx][yy]=='#') cnt1++;}for(int i=0;i<4;i++){int xx=x2+dx[i];int yy=y2+dy[i];if(xx<1||xx>n||yy<1||yy>m) cnt2++;else if(mp[xx][yy]=='#') cnt2++;}if(cnt1==3&&dis1==1&&dis2!=1){cout<<"No\n";continue;}if(cnt2==3&&dis1!=1&&dis2==1){cout<<"No\n";continue;}if(dis1%2==dis2%2&&_find(id[{x1,y1}])==_find(id[{enx,eny}])&&_find(id[{x2,y2}])==_find(id[{enx,eny}])){cout<<"Yes\n";}else{cout<<"No\n";}}}signed main() {int T;T=1;//cin>>T;while(T--) {solve();}
}

組合數問題：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+100;
const int mod=1e9+7;
int n;
int fast_pow_mod(int a,int b,int mod){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int C(int a,int b){if(a<b) return 0;int res=1;for(int i=1,j=a;i<=b;j--,i++){res=res*j%mod;res=res*fast_pow_mod(i,mod-2,mod)%mod;}return res;}
int fact(int a)
{int res=1;for(int i=a;i>=2;i--){res=res*i%mod;}return res;
}
void solve(){int n;cin>>n;int res=C(n/3,n/2-n/3)*C(n-n/3,n/2-n/3)%mod*fact(n/3)%mod*fact(n-n/3)%mod;cout<<res<<"\n";return;
}
signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int t;t=1;//cin >> t;while (t--) {solve();}return 0;
}

小紅的染色期望：

有 nnn 個白色小球排成一排。小紅每次將隨機選擇兩個相鄰的白色小球，將它們染成紅色。小紅將持續這個操作直到無法操作，請你計算小紅操作次數的期望。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e6+100;
const int mod=1e9+7;
int n;
int fast_pow_mod(int a,int b,int mod){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int C(int a,int b){if(a<b) return 0;int res=1;for(int i=1,j=a;i<=b;j--,i++){res=res*j%mod;res=res*fast_pow_mod(i,mod-2,mod)%mod;}return res;}
int fact(int a)
{int res=1;for(int i=a;i>=2;i--){res=res*i%mod;}return res;
}
int dp[maxn]={0};
int pre[maxn]={0};
void solve(){int n;cin>>n;dp[0]=0;dp[2]=1;dp[1]=0;pre[2]=1;for(int i=3;i<=n;i++){int p=fast_pow_mod(i-1,mod-2,mod);dp[i]=(dp[i]+pre[i-2]*2%mod*p%mod)%mod;dp[i]=(dp[i]+1)%mod;pre[i]=(pre[i-1]+dp[i])%mod;}cout<<dp[n]<<"\n";
}
signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int t;t=1;//cin >> t;while (t--) {solve();}return 0;
}

極坐標排序：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e6+100;
const int mod=1e9+7;
int fast_pow_mod(int a,int b,int mod){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int C(int a,int b){if(a<b) return 0;int res=1;for(int i=1,j=a;i<=b;j--,i++){res=res*j%mod;res=res*fast_pow_mod(i,mod-2,mod)%mod;}return res;}
int fact(int a)
{int res=1;for(int i=a;i>=2;i--){res=res*i%mod;}return res;
}
const int N=2e+5+100;
struct point{int x,y;
}P[N],xl[N];
bool cmp(point a,point b){return a.x*b.y>a.y*b.x;
}
int cross(int x1,int y1,int x2,int y2){return x1*y2-x2*y1;
}void solve(){int ans=LONG_LONG_MAX;int n;cin>>n;for(int i=1;i<n;i++){cin>>P[i].x>>P[i].y;}for(int i=0;i<n;i++){int k=0;for(int j=0;j<n;j++){if(i!=j){xl[k].x=P[j].x-P[i].x;xl[k].y=P[j].y-P[i].y;k++;}}sort(xl,xl+k,cmp);for(int j=0;j<k-1;j++){//cout<<abs(xl[j].x*xl[j+1].y-xl[j+1].x*xl[j].y)<<endl;ans=min(ans,abs(xl[j].x*xl[j+1].y-xl[j+1].x*xl[j].y));}}printf("%.3lf",double(ans)/2);
}
signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int t;t=1;//cin >> t;while (t--) {solve();}return 0;
}

想與不是0的可以建立邊：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
const int N = 1e5 + 10,mod=1e9+7;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
int T;
int n;
ll p[N+65],Size[N+65];
int find(int x)
{if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
void merge(int a,int b)
{int pa=find(a),pb=find(b);if(pa!=pb){Size[pb]+=Size[pa];p[pa]=pb;}
}
int main()
{cin>>T;while(T--){cin>>n;for(int i=1;i<=n+64;i++)p[i]=i,Size[i]=1;for(int i=n+1;i<=n+64;i++)Size[i]=0;for(int i=1;i<=n;i++){ll x;cin>>x;for(int j=0;j<=63;j++)if(x>>j&1)merge(i,n+j+1);}ll ans=0;for(int i=n+1;i<=n+64;i++)ans=max(ans,Size[i]);cout<<ans<<endl;}return 0;
}

分解質因數：

//分解質因子 
#include <iostream> 
using namespace std;
int main()
{int num;cin >> num;cout << num << "=";for (int i = 2; i <= num; i++)  //循環查找判斷質因數{while (num % i == 0)    //若i為num的質因數，則輸出i{cout << i;num /= i;    //對num除以i后的數求取質因數if (num != 1)//判斷num是否除盡 cout << "*";}}cout << endl;return 0;
}

質數篩子：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;void sieve(int n) {
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;for (int i = 2; i <= sqrt(n); ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
cout << i << " ";
}
}
cout << endl;
}int main() {
int n;
cout << "請輸入一個數字：";
cin >> n;
sieve(n);
return 0;
}

李白打酒：

(第十三屆藍橋杯省賽)I：李白打酒加強版（動態規劃）_李白打酒動態規劃-CSDN博客