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）
