Bellman-Ford最短路O（nm)
int INF = 0x3f3f3f3f;
struct edge { int from, to, cost; }edges[12405];
int n,m;
edge es[1000];
int d[2510];
void shortest_path(int s){
for(int i=0;i<=n;i++){
d[i]=INF;
}
d[s]=0;
while(true){
bool update=false;
for(int i=0;i<m*2;i++){
if(d[edges[i].from]!=INF&&d[edges[i].to]>d[edges[i].from]+edges[i].cost){
d[edges[i].to]=d[edges[i].from]+edges[i].cost;
update=true;
}
}
if(!update){
break;
}
}
}
for(i=0;i<m;i++){
cin>>u>>v>>w;
edges[i*2].from=u;
edges[i*2].to=v;
edges[i*2].cost=w;
edges[i*2+1].from=v;
edges[i*2+1].to=u;
edges[i*2+1].cost=w;
}
shortest_path(s);
cout<<d[t]<<endl;
Floyd-Warshall最短路O（n^3)
int INF = 0x3f3f3f3f;
int d[2510][2510];
int n,m;
void warshall_floyd(){
for(int k=0;k<=n;k++){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
for(i=0;i<=n;i++){
for(j=i+1;j<=n;j++){
d[i][j]=INF;
d[j][i]=INF;
}
}
for(i=0;i<m;i++){
cin>>u>>v>>w;
d[u][v]=w;
d[v][u]=w;
}
warshall_floyd();
cout<<d[s][t]<<endl;
gcdO(log a)
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
mod_powO(log n)
ll mod_pow(ll x,ll n,ll mod){
if(n==0) return 1;
ll res=mod_pow(x*x%mod,n/2,mod);
if(n&1) res=res*x%mod;
return res;
}
STL
//vector容器
vector<pair<ll,ll>> a;
for(int i=1;i<=n;i++){
ll c,b;
cin>>c;
b=i;
a.push_back(make_pair(c,b));
}
sort(a.begin(),a.end());
for(auto p:a){
//p为a数组的值
}
//
vector <vector<int >> res(k+1);//res[k+1][]
for(int i=1;i<=n;i++){
cin>>a[i];
res[a[i]].push_back(i);
}
for(int i=0;i<res.size();i++){
cout<<res[i]<<endl;
}
res[i].empty()//true为空,false为非空
//
vector <string > s;
string str;
cin>>str;
s.push_back(str);
//map容器(可做桶用
map<string,bool> s1;
string str;
cin>>str;
s1[str]=1;
并查集
const int max_N=1e5+7;
int par[max_N];
int rank[max_N];
int value[max_N];
//初始化 max_N个元素
void init(int n){
if(n==max_N) n--;
for(int i=0;i<=n;i++){
par[i]=i;
rank[i]=0;
value[i]=1;
}
}
//查询树的根
int find(int x){
if(par[x]==x){
return x;
}else{
return par[x]=find(par[x]);
}
}
//合并x和y所属的集合
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return ;
if(rank[x]<rank[y]){
par[x]=y;
value[y]+=value[x];
}else{
par[y]=x;
value[x]+=value[y];
if(rank[x]==rank[y]) rank[x]++;
}
}
//判断x和y是否属于同一个集合
bool same(int x,int y){
return find(x)==find(y);
}
查找子串find()
std::string s = "This is a sample string. Sample strings are useful for samples.";
std::string str = "sample";
size_t pos = s.find(str);
int count = 0;
while (pos != std::string::npos) {
count++;
pos = s.find(str, pos + 1);
}
二维差分
// 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c
void add(int x1, int y1, int x2, int y2, int c)
{
f[x1][y1] += c;
f[x2 + 1][y1] -= c;
f[x1][y2 + 1] -= c;
f[x2 + 1][y2 + 1] += c;
}
高精度
const int LEN = 1004;
void clear(int a[]) {
for (int i = 0; i < LEN; ++i) a[i] = 0;
}
void read(int a[]) {
static char s[LEN + 1];
scanf("%s", s);
clear(a);
int len = strlen(s);
// 如上所述，反转
for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
// s[i] - '0' 就是 s[i] 所表示的数码
// 有些同学可能更习惯用 ord(s[i]) - ord('0') 的方式理解
}
void print(int a[]) {
int i;
for (i = LEN - 1; i >= 1; --i)
if (a[i] != 0) break;
for (; i >= 0; --i) putchar(a[i] + '0');
putchar('\n');
}
void add(int a[], int b[], int c[]) {
clear(c);
// 高精度实现中，一般令数组的最大长度 LEN 比可能的输入大一些
// 然后略去末尾的几次循环，这样一来可以省去不少边界情况的处理
// 因为实际输入不会超过 1000 位，故在此循环到 LEN - 1 = 1003 已经足够
for (int i = 0; i < LEN - 1; ++i) {
// 将相应位上的数码相加
c[i] += a[i] + b[i];
if (c[i] >= 10) {
// 进位
c[i + 1] += 1;
c[i] -= 10;
}
}
}
void sub(int a[], int b[], int c[]) {
clear(c);
for (int i = 0; i < LEN - 1; ++i) {
// 逐位相减
c[i] += a[i] - b[i];
if (c[i] < 0) {
// 借位
c[i + 1] -= 1;
c[i] += 10;
}
}
}
void mul_short(int a[], int b, int c[]) {
clear(c);
for (int i = 0; i < LEN - 1; ++i) {
// 直接把 a 的第 i 位数码乘以乘数，加入结果
c[i] += a[i] * b;
if (c[i] >= 10) {
// 处理进位
// c[i] / 10 即除法的商数成为进位的增量值
c[i + 1] += c[i] / 10;
// 而 c[i] % 10 即除法的余数成为在当前位留下的值
c[i] %= 10;
}
}
}
void mul(int a[], int b[], int c[]) {
clear(c);
for (int i = 0; i < LEN - 1; ++i) {
// 这里直接计算结果中的从低到高第 i 位，且一并处理了进位
// 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
// 这样做的效果和直接进行上图的运算最后求和是一样的，只是更加简短的一种实现方式
for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];
if (c[i] >= 10) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
}
}
// 被除数 a 以下标 last_dg 为最低位，是否可以再减去除数 b 而保持非负
// len 是除数 b 的长度，避免反复计算
bool greater_eq(int a[], int b[], int last_dg, int len) {
// 有可能被除数剩余的部分比除数长，这个情况下最多多出 1 位，故如此判断即可
if (a[last_dg + len] != 0) return true;
// 从高位到低位，逐位比较
for (int i = len - 1; i >= 0; --i) {
if (a[last_dg + i] > b[i]) return true;
if (a[last_dg + i] < b[i]) return false;
}
// 相等的情形下也是可行的
return true;
}
void div(int a[], int b[], int c[], int d[]) {
clear(c);
clear(d);
int la, lb;
for (la = LEN - 1; la > 0; --la)
if (a[la - 1] != 0) break;
for (lb = LEN - 1; lb > 0; --lb)
if (b[lb - 1] != 0) break;
if (lb == 0) {
puts("> <");
return;
} // 除数不能为零
// c 是商
// d 是被除数的剩余部分，算法结束后自然成为余数
for (int i = 0; i < la; ++i) d[i] = a[i];
for (int i = la - lb; i >= 0; --i) {
// 计算商的第 i 位
while (greater_eq(d, b, i, lb)) {
// 若可以减，则减
// 这一段是一个高精度减法
for (int j = 0; j < lb; ++j) {
d[i + j] -= b[j];
if (d[i + j] < 0) {
d[i + j + 1] -= 1;
d[i + j] += 10;
}
}
// 使商的这一位增加 1
c[i] += 1;
// 返回循环开头，重新检查
}
}
}
树上dp
#include <bits/stdc++.h>
using namespace std ;
const int max_N=2e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
vector<int> g[max_N];
ll dp[max_N];
void dfs(int u,int fa){
if(g[u].size()==1&&u-1){
dp[u]=1;
}
for(auto v : g[u]){
if(v==fa){
continue ;
}
dfs(v,u);
dp[u]+=dp[v];
}
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
g[i].clear();
dp[i]=0;
}
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,0);
int q;
cin>>q;
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
cout<<dp[x]*dp[y]<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
位运算符
0&0=0;
0&1=0;
1&0=0;
1&1=1;
//全1出1
0|0=0;
0|1=1;
1|0=1;
1|1=1;
//有1出1
0^0=0;
0^1=1;
1^0=1;
1^1=0;
//一样出0，不一样出1
逆元（除数取模）
//拓展欧几里得
ll exgcd(ll a, ll b, ll &x, ll &y)// 拓欧
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
ll inv(ll a, ll p)
{
ll x, y;
if (exgcd(a, p, x, y) != 1) // 无解的情形
return -1;
return (x % p + p) % p;
}
//inv(a,p)就是取模p意义下的1/a；
//费马小定理
inline ll qpow(ll a, ll n, ll p)// 快速幂
{
ll ans = 1;
while (n)
{
if (n & 1)
ans = ans % p * a % p;
a = a % p * a % p;
n >>= 1;
}
return ans;
}
inline ll inv(ll a, ll p)
{
return qpow(a, p - 2, p);
}
三维bfs
char g[max_N][max_N][max_N];
const int dx[]={0,0,0,0,-1,1},
dy[]={0,0,-1,1,0,0},
dz[]={-1,1,0,0,0,0};
struct node
{
int x,y,z;
};
int l,r,c;
queue<node>q;
int d[max_N][max_N][max_N];
int bfs(node st){
while(!q.empty()){
q.pop();
}
q.push(st);
d[st.x][st.y][st.z]=0;
while(!q.empty()){
node t=q.front();
q.pop();
g[t.x][t.y][t.z]='#';
for(int i=0;i<6;i++){
int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];
if(x<0||x>=l||y<0||y>=r||z<0||z>=c){
continue;
}
if(g[x][y][z]=='#'){
continue;
}
d[x][y][z]=d[t.x][t.y][t.z]+1;
if(g[x][y][z]=='E'){
return d[x][y][z];
}
g[x][y][z]='#';
node tt;
tt.x=x,tt.y=y,tt.z=z;
q.push(tt);
}
}
return 0;
}
快速幂
#include <iostream>
long long Quick_Power(long long x,long long n)
{
if(n==0)
{
return 1;
}
else if(n%2==1)
{
return Quick_Power(x,n-1)*x;
}
else
{
long long tmp=Quick_Power(x,n/2);
return tmp*tmp;
}
}
using namespace std;
int main()
{
long long x,n;
cin>>x>>n;
cout<<Quick_Power(x,n);
}
long long ksm(long long a, long long b)
{
long long res = 1;
while(b)
{
if(b & 1)
res = res * a % M;
a = a * a % M;
b >>= 1;
}
return res;
}