1.楊輝三角形?

#include<iostream>
using namespace std;
#define ll long long
const int N=2e5+10;
int a[N];
//1 0 0 0 0 0 0
//1 1 0 0 0 0 0
//1 2 1 0 0 0 0
//1 3 3 1 0 0 0
//1 4 6 4 1 0 0
//1 5 10 10 5 1
//前綴和思想
//第一列全為1,第二列為從0開始遞增1的序列,
//可以發現當前列為前面一列的前綴和序列
//N最大是1e9,第三列計算n*(n+1)/2>1e9得到n>44721
//又第三列前面有兩個0,即最小需要44721+2=44723行
//當第三列的值已經大于1e9時,不需要再計算后面的數,
//直接根據第二列規律,找第二列中n的位置即可。
//由于第二列是從0開始的,此時可以確定n是在第n+1行,
//又因為是第二列，所以n的是數列中第n?(n+1)/2+2個。
int main()
{int n;cin>>n;a[0]=1;int k=1;if(n==1)cout<<1<<endl;else{for(int i=1;i<44725;i++)//枚舉行{for(int j=i;j>=1;j--)//從后往前（前綴和）{a[j]+=a[j-1];if(a[j]==n){cout<<k+i-j+1<<endl;return 0;}}k+=(i+1);}cout<<(1+n)*n/2+2<<endl;}return 0;
}

2.迷宮

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define pii pair<int,int>
#define x first
#define y second
string ss[31]={
"                                                   ",
" 01010101001011001001010110010110100100001000101010",
" 00001000100000101010010000100000001001100110100101",
" 01111011010010001000001101001011100011000000010000",
" 01000000001010100011010000101000001010101011001011",
" 00011111000000101000010010100010100000101100000000",
" 11001000110101000010101100011010011010101011110111",
" 00011011010101001001001010000001000101001110000000",
" 10100000101000100110101010111110011000010000111010",
" 00111000001010100001100010000001000101001100001001",
" 11000110100001110010001001010101010101010001101000",
" 00010000100100000101001010101110100010101010000101",
" 11100100101001001000010000010101010100100100010100",
" 00000010000000101011001111010001100000101010100011",
" 10101010011100001000011000010110011110110100001000",
" 10101010100001101010100101000010100000111011101001",
" 10000000101100010000101100101101001011100000000100",
" 10101001000000010100100001000100000100011110101001",
" 00101001010101101001010100011010101101110000110101",
" 11001010000100001100000010100101000001000111000010",
" 00001000110000110101101000000100101001001000011101",
" 10100101000101000000001110110010110101101010100001",
" 00101000010000110101010000100010001001000100010101",
" 10100001000110010001000010101001010101011111010010",
" 00000100101000000110010100101001000001000000000010",
" 11010000001001110111001001000011101001011011101000",
" 00000110100010001000100000001000011101000000110011",
" 10101000101000100010001111100010101001010000001000",
" 10000010100101001010110000000100101010001011101000",
" 00111100001000010000000110111000000001000000001011",
" 10000001100111010111010001000110111010101101111000"};
struct Ch{char ch;pii per;
};
Ch mp[40][60];
bool vis[40][60];
int fx[] = {1,0,0,-1};
int fy[] = {0,-1,1,0};
void bfs(int x,int y)
{queue<pii> q;q.push({x,y});vis[x][y] = true;while(!q.empty()){pii temp = q.front();for(int i = 0;i < 4;i++){pii t ={temp.x + fx[i],temp.y + fy[i]};if(mp[t.x][t.y].ch == '0' && vis[t.x][t.y] == false){mp[t.x][t.y].per = temp;vis[t.x][t.y] = true;q.push(t);}}q.pop();}
}
int main()
{string s;for(int i = 1;i <= 30;i++){for(int j = 1;j <= 50;j++){mp[i][j].ch = ss[i][j];}}bfs(1,1);pii t = {30,50};while(t.x != 1 || t.y != 1){int x = t.x - mp[t.x][t.y].per.x;int y = t.y - mp[t.x][t.y].per.y;int flag;for(int i = 0;i < 4;i++){if(x == fx[i] && y == fy[i]){flag = i;break;}}switch(flag){case 0:s += 'D';break;case 1:s += 'L';break;case 2:s += 'R';break;case 3:s += 'U';break;}t = mp[t.x][t.y].per;}for(int i = s.size() - 1;i >= 0;i--){cout << s[i];}return 0;
}
//Ch記錄這個結點的值和前驅結點的坐標,以便記錄路徑
//字典序最小的方向數組 - DLRU - 最優性剪枝
//求最短路使用BFS
//從終點開始遍歷每個結點的前驅結點，直到起點結束，當兩個坐標都為1的時候，循環結束
//當前結點減去前驅結點得到的值對應的就是前驅節點移動的方向
//使用switch來進行方向判斷，加入答案，最后答案要進行逆序輸出

?3.潛伏者

#include <iostream>
#include <map>
using namespace std;
int check[26];
int notwell[26];
int main()
{string secret;string origin;string need;cin>>secret>>origin>>need;map<char,int>ohp;map<char,int>shp;bool ok=1;for(int i=0;i<origin.size();i++){check[origin[i]-'A']=1;if(!ohp[origin[i]])ohp[origin[i]]=secret[i],shp[secret[i]]=origin[i];else {if(ohp[origin[i]]!=secret[i])notwell[origin[i]-'A']=1;}}for(int i=0;i<26;i++){if(check[i]==0){ok=0;break;}}string ans;for(int i=0;i<need.size();i++){if(!shp[need[i]]||notwell[need[i]-'A']){ok=0;break;}else ans+=(char)shp[need[i]];}if(!ok)cout<<"Failed"<<endl;else cout<<ans<<endl;return 0;
}

?4.滅鼠先鋒

#include <iostream>
using namespace std;
//下第二行
//0000
//第一個人：XX00      X000
//第二個人：XXX0      XXX0
//第一個人：XXXX(輸)  XXXX
//無論第一個人下一個還是兩個，第二個人都會讓它輸
//即誰下滿第一行，誰就贏
//換言之，誰開始下第二行，誰就輸
int main()
{cout<<"LLLV"<<endl;return 0;
}

5.求和

#include <iostream>
using namespace std;
const int N=2e5+5;
#define ll long long
int n;
int a[N];
//a1 a2 a3 a4 a5 .. an
//a1*(a2+a3+...+an)+a2*(a3+a4+...+an)+a3*(a4+a5+...an)+an-1*an
//后綴和
ll suf[N];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];suf[i]=a[i];}for(int i=n-1;i>=1;i--){suf[i]+=suf[i+1];}ll ans=0;for(int i=1;i<=n-1;i++){ans+=(a[i]*suf[i+1]);}cout<<ans<<endl;return 0;
}

?6.爬樹的甲殼蟲

?

#include <iostream>
using namespace std;
#define ll long long
const int p=998244353; 
const int N=1e5+10;
ll E[N];
ll qmi(int a,int k,int p)//a^k%p
{ll res=1;while(k){if(k&1)res=(ll)res*a%p;k>>=1;a=(ll)a*a%p;}return res;
}
//E[n]=E[n-1]+(1-P[n])*1+P[n]*(E[n]+1);
//E[n]=(E[n-1]+1)/(1-P[n])
//對到每層高度的期望，使用對前面的進行累加，以保證可以到達第n層了
//以第n層為例，在第n-1層有（1-P[n]）的概率成功再乘以時間1s則為成功期望時間
//在第n-1層有P[n]的概率失敗則P[n]*(E[n]+1)即失敗概率乘以從頭再爬到n和掉下去的1s則為失敗期望時間
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;E[i]=((E[i-1]+1)%p*(y%p))%p;E[i]*=qmi(y-x,p-2,p);	E[i]%=p;}cout<<E[n]<<endl;return 0;
}

?7.數的拆分

?

#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
//如果能拆一定有以下的方式構造
//設p1和p2為素數或者其中一個為1
//n = p1^n1 * p2^n2
//n1和n2肯定可以被分解為=2+X或者=3+X
//即先判斷此數是不是平方數或者立方數
//如果都不是則接著找質因子,若出現質因子的指數只有1,則肯定不行
//a最大是1e18,質因子找到4000即可
bool flag;
bool cubic(ll n)
{ll x = pow(n, 1.0 / 3);while (x * x * x <= n)//一定要使用while{if (x * x * x == n)return true;++x;}return false;
}
bool square(ll n)
{ll x = sqrt(n);while (x * x <= n)//一定要使用while{if (x * x == n)return true;++x;}return false;
}
int prime[2000];
int idx;
void Prime()
{int st[4005] = { 0 };for (int i = 2; i <= 4000; ++i)if (!st[i])for (int j = 2 * i; j <= 4000; j += i)st[j] = 1;for (int i = 2; i <= 4000; ++i)if (!st[i])prime[idx++] = i;}
ll num[100050];
int t;
int main()
{Prime();scanf("%d", &t);for (int i = 0; i < t; ++i)scanf("%lld", num + i);for (int i = 0; i < t; ++i){ll x = num[i];if (cubic(x) ||square(x)){printf("yes\n");continue;}flag = true;for (int j = 0; j < idx; ++j){int s = 0;while (x % prime[j] == 0){x /= prime[j];++s;}if (s == 1){flag = false;break;}}if (flag && (cubic(x) || square(x)))printf("yes\n");elseprintf("no\n");}return 0;
}

?

8.推導部分和

?

#include <iostream>
using namespace std;
#define ll long long
int n,m,q;
//并查集
int p[200000+10];
ll d[200000+10];
//以一個根結點為參照，l-1到根結點的距離為d[l-1] r到根結點的距離為d[r]
//根據前綴和原理 [l, r] 區間和為 d[r] - d[l - 1]
int find(int x)
{if(x!=p[x]){int t=p[x];p[x]=find(p[x]);d[x]+=d[t];}return p[x];
}
int main()
{scanf("%d %d %d",&n,&m,&q);//初始化并查集for(int i=1;i<=n;i++)p[i]=i;for(int i=1;i<=m;i++){int l,r;ll s;scanf("%d %d %lld",&l,&r,&s);int pl=find(l-1),pr=find(r);p[pl]=pr;d[pl]=d[r]-d[l-1]-s;}for(int i=1;i<=q;i++){int l,r;scanf("%d %d",&l,&r);int pl=find(l-1),pr=find(r);if(pl==pr){printf("%lld\n",d[r]-d[l-1]);}else{printf("UNKNOWN\n");}}return 0;
}

?（參考代碼來自lanqiao1533688980）