微网站建设市场分析,网页设计html代码大全居中,网上代做论文的网站,百度下载正版题目#xff1a; 1000#xff1a;入门测试题目 时间限制: 1000 ms 内存限制: 32768 KB 提交数: 262857 通过数: 158152 【题目描述】 求两个整数的和。 【输入】 一行#xff0c;两个用空格隔开的整数。 【输出】 两个整数的和。 【输入样例】 2 3 【输出样例】…题目 1000入门测试题目 时间限制: 1000 ms 内存限制: 32768 KB 提交数: 262857 通过数: 158152 【题目描述】 求两个整数的和。 【输入】 一行两个用空格隔开的整数。 【输出】 两个整数的和。 【输入样例】 2 3 【输出样例】 5 算法一、DFS一号 #include bits/stdc.h using namespace std; int n 2, a[5], s; int dfs(int x, int sum) { if (x n) return sum; int i dfs(x 1, sum); int j dfs(x 1, sum a[x]); if (i s) return i; if (j s) return j; return -1; } int main() { for (int i 1;i n; i) scanf(%d, a[i]), s a[i]; cout dfs(1, 0) endl; return 0; } 算法二、DFS二号 #include bits/stdc.h using namespace std; int a, b; int dfs(int x) { if (x 5) return x; return dfs(x / 2) dfs(x - x / 2); } int main() { scanf(%d%d, a, b); printf(%d\n, dfs(a) dfs(b)); return 0; } 算法三、BFS #include bits/stdc.h using namespace std; int n 2, a[5], s; queueint q; void bfs() { q.push(0); int c 0; while (q.size()) { c; int f q.front(); q.pop(); if (f s) {printf(%d\n, f); exit(0);} q.push(f a[c]); q.push(f); } } int main() { for (int i 1;i n; i) scanf(%d, a[i]), s a[i]; bfs(); return 0; } 算法四、直接算咯 #include bits/stdc.h using namespace std; int a, b; int main() { scanf(%d%d, a, b); printf(%d\n, a b); return 0; } 算法五、二分 #include bits/stdc.h using namespace std; int a, b; int main() { scanf(%d%d, a, b); int l 0, r 200000000; while (l r) { int mid l r 1; if (mid a b) {printf(%d\n, mid); return 0;} if (mid a b) l mid 1; if (mid a b) r mid - 1; } cout l endl; return 0; } 算法六、稍微有点暴力的枚举 但是还是1892ms 1892 卡过了欸
#include bits/stdc.h using namespace std; int a, b; int main() { scanf(%d%d, a, b); for (int i 0;i 200000000; i) if (a b i) {printf(%d\n, i); break;} return 0; } 算法七、最短路之dijkstra 思路定义节点1到节点2路径长度为a节点2到节点3路径长度为b 则答案为节点1到节点3的最短路也就是ab
#include bits/stdc.h using namespace std; int w[5][5], d[5], v[5]; int n 3; void dijkstra() { memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[1] 0; for (int i 1;i n; i) { int x 0; for (int j 1;j n; j) if (!v[j] (x 0 || d[j] d[x])) x j; v[x] 1; for (int y 1;y n; y) d[y] min(d[y], d[x] w[x][y]); } } int main() { int a, b; scanf(%d%d, a, b); memset(w, 0x3f, sizeof w); w[1][2] a; w[2][3] b; dijkstra(); printf(%d\n, d[3]); return 0; } 算法八、最短路之SPFA 思路同上
#include bits/stdc.h using namespace std; int a, b, n 3; int w[5][5], d[5], v[5]; queueint q; void spfa() { memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[1] 0, v[1] 1; q.push(1); while (q.size()) { int x q.front(); q.pop(); v[x] 0; for (int i 1;i n; i) { // if (w[x][i] 0x3f) continue; if (d[i] d[x] w[x][i]) { d[i] d[x] w[x][i]; if (!v[i]) q.push(i), v[i] 1; } } } } int main() { scanf(%d%d, a, b); memset(w, 0x3f, sizeof w); w[1][2] a; w[2][3] b; spfa(); printf(%d\n, d[3]); return 0; } 算法九、最短路之Floyd 思路同上
#include bits/stdc.h using namespace std; int d[5][5], n 3; int main() { int a, b; scanf(%d%d, a, b); memset(d, 0x3f, sizeof d); d[1][2] a; d[2][3] b; for (int k 1;k n; k) for (int i 1;i n; i) for (int j 1;j n; j) d[i][j] min(d[i][j], d[i][k] d[k][j]); printf(%d\n, d[1][3]); return 0; } 算法十、高精 #includebits/stdc.h using namespace std; string a0, b0; int a[1005], b[1005]; int main(){ cin a0 b0; int l1 a0.size(), l2 b0.size(); for (int i 0;i l1; i) a[l1 - i] a0[i] - 48; for (int i 0;i l2; i) b[l2 - i] b0[i] - 48; l1 max(l1, l2); for (int i 1;i l1; i) { a[i] b[i]; if (a[i] 9) a[i 1] 1, a[i] % 10; } if (a[max(l1, l2) 1] 0) l1; for (int i l1;i 1; i--) printf(%d, a[i]); return 0; } 算法十一、最小生成树之kruskal 思路其实和最短路的一样只是改成用最小生成树的方法求罢了
#include bits/stdc.h using namespace std; struct rec { int x, y, z; } edge[5];
int fa[5], m 2, ans 0;
int get(int x) { if (x fa[x]) return x; return fa[x] get(fa[x]); } int cmp(rec a, rec b) { return a.z b.z; }
int main() { int a, b; scanf(%d%d, a, b); edge[1] (rec){1, 2, a}; edge[2] (rec){2, 3, b}; for (int i 1;i m 1; i) fa[i] i; sort(edge 1, edge 1 m, cmp); for (int i 1;i m; i) { int x get(edge[i].x); int y get(edge[i].y); if (x y) continue; fa[x] y; ans edge[i].z; } printf(%d\n, ans); return 0; } 算法十二、最小生成树之prim 思路同上
#include bits/stdc.h using namespace std; int w[5][5], d[5], n 3, ans, v[5];
void prim() { memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[1] 0; for (int i 1;i n; i) { int x 0; for (int j 1;j n; j) if (!v[j] (x 0 || d[j] d[x])) x j; v[x] 1; for (int y 1;y n; y) if (!v[y]) d[y] min(d[y], w[x][y]); } } int main() { int a, b; scanf(%d%d, a, b); memset(w, 0x3f, sizeof w); w[1][2] a; w[2][3] b; prim(); int ans 0; for (int i 2;i n; i) ans d[i]; printf(%d\n, ans); return 0; } 算法十三、前缀和 #include bits/stdc.h using namespace std; int a[5], s[5]; int main() { for (int i 1;i 2; i) scanf(%d, a[i]), s[i] a[i] s[i - 1]; printf(%d\n, s[2]); return 0; } 算法十四、后缀和 #include bits/stdc.h using namespace std; int a[5], s[5]; int main() { for (int i 2;i 1; i--) scanf(%d, a[i]), s[i] a[i] s[i 1]; printf(%d\n, s[1]); return 0; } 算法十五、位运算 #include bits/stdc.h using namespace std; int add(int a, int b) { if (b 0) return a; return add(a ^ b, (a b) 1); } int main() { int a, b; scanf(%d%d, a, b); printf(%d\n, add(a, b)); return 0; } 算法十六、树的直径——BFS emmm……思路继续和最短路的一样。。。
#include bits/stdc.h using namespace std; const int maxn 1e5 10;
int head[maxn * 2],edge[maxn * 2],Next[maxn * 2],ver[maxn * 2]; int vis[maxn], dist[maxn]; int n 3, p, q, d; int tot 0; int maxd 0;
void add(int u,int v,int w) { ver[ tot] v,edge[tot] w; Next[tot] head[u],head[u] tot; }
int BFS(int u) { queueintQ; while(!Q.empty()) Q.pop(); memset(vis, 0, sizeof vis); memset(dist, 0, sizeof dist); Q.push(u); int x, max_num 0; while(!Q.empty()) { x Q.front(); Q.pop(); vis[x] 1; for(int i head[x]; i ; i Next[i]) { int y ver[i]; if(vis[y]) continue; vis[y] 1; dist[y] dist[x] edge[i]; if(dist[y] maxd) { maxd dist[y]; max_num y; } Q.push(y); } } return max_num; } int main(void) { int a, b; scanf(%d%d, a, b); add(1, 2, a); add(2, 1, a); add(2, 3, b); add(3, 2, b); BFS(BFS(1)); int ans 0; for (int i 1;i n; i) ans max(ans, dist[i]); printf(%d\n, ans); return 0; } 算法十七、树的直径——DFS 思路同上
#includebits/stdc.h #define maxn 100000 using namespace std; struct node { int u, v, w, nex; } edge[2 * maxn 10]; int n 3, d[maxn 10], head[maxn 10], f_num, cnt 0, ans; inline void add(int x,int y,int z) { edge[cnt].u x; edge[cnt].v y; edge[cnt].w z; edge[cnt].nex head[x]; head[x] cnt; } inline void dfs(int x, int fa) { if(ans d[x]) { ans d[x]; f_num x; } for (int i head[x]; i ! -1; i edge[i].nex) { int j edge[i].v; if (j fa)continue; d[j] d[x] edge[i].w; dfs(j, x); } } int main() { memset(head, -1, sizeof(head)); int a, b; scanf(%d%d, a, b); add(1, 2, a); add(2, 1, a); add(2, 3, b); add(3, 2, b); dfs(1, 0); ans 0; d[f_num] 0; dfs(f_num, 0); for (int i 1;i n; i) ans max(ans, d[i]); printf(%d, ans); return 0; } 算法十八、树的直径——树形DP 还是一样咯
#include bits/stdc.h using namespace std; int f[5], n 3, cnt, h[5], ans, dis[5]; struct edge { int to, next, vi; } e[5]; void add(int u, int v, int w) { e[cnt].to v; e[cnt].vi w; e[cnt].next h[u]; h[u] cnt; } void dp(int u, int fa) { for (int i h[u]; ~i; i e[i].next) { int v e[i].to; if (v fa) continue; dp(v, u); ans max(ans, dis[v] dis[u] e[i].vi); dis[u] max(dis[u], dis[v] e[i].vi); } } int main() { memset(h, -1, sizeof h); int a, b; scanf(%d%d, a, b); add(1, 2, a); add(2, 1, a); add(2, 3, b); add(3, 2, b); dp(1, 0); printf(%d\n, ans); return 0; } 算法十九、网络流 从别的大佬那边搞过来的但是一点都看不懂┭┮﹏┭┮
#includebits/stdc.h using namespace std; #define set(x) Set(x) #define REP(i,j,k) for (int i(j),_end_(k);i_end_;i) #define DREP(i,j,k) for (int i(j),_start_(k);i_start_;--i) #define mp make_pair #define x first #define y second #define pb push_back templatetypename T inline bool chkmin(T a,const T b){ return a b ? a b, 1 : 0; } templatetypename T inline bool chkmax(T a,const T b){ return a b ? a b, 1 : 0; } typedef long long LL; typedef pairint,int node; const int dmax 1010, oo 0x3f3f3f3f; int n, m; int a[dmax][dmax] , ans; int d[dmax], e[dmax]; priority_queue node q; inline bool operator (node a,node b){ return a.yb.y; } bool p[dmax]; void Set(int x){ p[x] 1; } void unset(int x){ p[x] 0; } bool check(int x){ return x ! 1 x ! n !p[x] e[x] 0; } void preflow(){ e[1] oo; d[1] n - 1; q.push(mp(1, n - 1)); set(1); while (!q.empty()) { bool flag 1; int k q.top().x; q.pop(), unset(k); DREP(i, n, 1) if ((d[k] d[i] 1 || k 1) a[k][i] 0){ flag 0; int t min(a[k][i], e[k]); e[k] - t; a[k][i] - t; e[i] t; a[i][k] t; if (check(i)) { q.push(mp(i, d[i])); set(i); } if (e[k] 0) break; } if (flag) { d[k] oo; REP(i, 1, n) if (a[k][i] 0) chkmin(d[k], d[i] 1); } if (check(k)) { q.push(mp(k, d[k])); set(k); } } ans e[n]; } int main() { n 2, m 2; int x, y; scanf(%d%d, x, y); a[1][2] x y; preflow(); printf(%d\n, ans); return 0; } 算法二十、线段树 转化为区间求和问题
#include bits/stdc.h #define l(x) tree[x].l #define r(x) tree[x].r #define sum(x) tree[x].sum #define add(x) tree[x].add using namespace std; struct SegmentTree { int l, r; //区间左右端点 long long sum, add; //sum 区间和 add 延迟标记 } tree[400010]; int a[100010], n 1, m 2; void build (int p, int l, int r) { l(p) l, r(p) r; if(l r) {sum(p) a[l]; return;} int mid l r 1; build(p * 2, l, mid); build(p * 2 1, mid 1, r); sum(p) sum(p * 2) sum(p * 2 1); } void spread(int p) { if(add(p)) { //节点p有标记 sum(p * 2) add(p) * (r(p * 2) - l(p * 2) 1); //更新左子节点信息 sum(p * 2 1) add(p) * (r(p * 2 1) - l(p * 2 1) 1); //更新右子节点 add(p * 2) add(p); //给左子节点打延迟标记 add(p * 2 1) add(p); //给右子节点打延迟标记 add(p) 0; //清除p的标记 } } void change(int p, int l, int r, int d) { if(l l(p) r r(p)) { //完全覆盖 sum(p) (long long) d * (r(p) - l(p) 1); //更新节点信息 add(p) d; //给节点打延迟标记 return; } spread(p); //下传延迟标记 int mid l(p) r(p) 1; if(l mid) change(p * 2, l, r, d); if(r mid) change(p * 2 1, l, r, d); sum(p) sum(p * 2) sum(p * 2 1); } long long ask(int p, int l, int r) { if(l l(p) r r(p)) return sum(p); spread(p); int mid l(p) r(p) 1; long long val 0; if(l mid) val ask(p * 2, l, r); if(r mid) val ask(p * 2 1, l, r); return val; } int main() { a[1] 0; build(1, 1, n); while(m--) { int d 0; scanf(%d, d); change(1, 1, 1, d); } printf(%lld\n, ask(1, 1, 1)); return 0; } 算法二十一、树状数组 思路一样区间求和
#includebits/stdc.h using namespace std; const int SIZE 100010; int a[SIZE], n 1, m 2; long long c[2][SIZE], sum[SIZE];
long long ask(int k, int x) { long long ans 0; for(; x ; x - x -x) ans c[k][x]; return ans; }
void add(int k,int x,int y) { for(; x n; x x -x) c[k][x] y; }
int main() { a[1] 0; while(m--) { int d 0; scanf(%d, d); add(0, 1, d); add(0, 2, -d); add(1, 1, d); add(1, 2, -2 * d); } long long ans sum[1] 2 * ask(0, 1) - ask(1, 1); ans - sum[0] 1 * ask(0, 0) - ask(1, 0); printf(%lld\n, ans); return 0; } 算法二十二、分块 思路一样区间求和
#includebits/stdc.h using namespace std; long long a[50000010], sum[50000010], add[50000010]; int L[50000010], R[50000010]; int pos[50000010]; int n 1, m 2, t;
void change(int l, int r, long long d) { int p pos[l], q pos[r]; if (p q) { for (int i l; i r; i) a[i] d; sum[p] d*(r - l 1); } else { for (int i p 1; i q - 1; i) add[i] d; for (int i l; i R[p]; i) a[i] d; sum[p] d*(R[p] - l 1); for (int i L[q]; i r; i) a[i] d; sum[q] d*(r - L[q] 1); } }
long long ask(int l, int r) { int p pos[l], q pos[r]; long long ans 0; if (p q) { for (int i l; i r; i) ans a[i]; ans add[p] * (r - l 1); } else { for (int i p 1; i q - 1; i) ans sum[i] add[i] * (R[i] - L[i] 1); for (int i l; i R[p]; i) ans a[i]; ans add[p] * (R[p] - l 1); for (int i L[q]; i r; i) ans a[i]; ans add[q] * (r - L[q] 1); } return ans; }
int main() { a[1] 0; t sqrt(n*1.0); for (int i 1; i t; i) { L[i] (i - 1)*sqrt(n*1.0) 1; R[i] i*sqrt(n*1.0); } if (R[t] n) t, L[t] R[t - 1] 1, R[t] n; for (int i 1; i t; i) for (int j L[i]; j R[i]; j) { pos[j] i; sum[i] a[j]; } while (m--) { int d; scanf(%d, d); change(1, 1, d); } printf(%lld\n, ask(1, 1)); } 算法二十三、LCT 来自洛谷
#includebits/stdc.h using namespace std; struct node { int data,rev,sum; node *son[2],*pre; bool judge(); bool isroot(); void pushdown(); void update(); void setson(node *child,int lr); }lct[233]; int top,a,b; node *getnew(int x) { node *nowlct top; now-datax; now-prenow-son[1]now-son[0]lct; now-sum0; now-rev0; return now; } bool node::judge() { return pre-son[1]this; } bool node::isroot() { if(prelct)return true; return !(pre-son[1]this||pre-son[0]this); } void node::pushdown() { if(thislct||!rev)return; swap(son[0],son[1]); son[0]-rev^1; son[1]-rev^1; rev0; } void node::update() { sumson[1]-sumson[0]-sumdata; } void node::setson(node *child,int lr) { this-pushdown(); child-prethis; son[lr]child; this-update(); } void rotate(node *now) { node *fathernow-pre,*grandfafather-pre; if(!father-isroot()) grandfa-pushdown(); father-pushdown(); now-pushdown(); int lrnow-judge(); father-setson(now-son[lr^1],lr); if(father-isroot()) now-pregrandfa; else grandfa-setson(now,father-judge()); now-setson(father,lr^1); father-update(); now-update(); if(grandfa!lct) grandfa-update(); } void splay(node *now) { if(now-isroot())return; for(; !now-isroot(); rotate(now)) if(!now-pre-isroot()) now-judge()now-pre-judge()?rotate(now-pre):rotate(now); } node *access(node *now) { node *lastlct; for(; now!lct; lastnow,nownow-pre) { splay(now); now-setson(last,1); } return last; } void changeroot(node *now) { access(now)-rev^1; splay(now); } void connect(node *x,node *y) { changeroot(x); x-prey; access(x); } void cut(node *x,node *y) { changeroot(x); access(y); splay(x); x-pushdown(); x-son[1]y-prelct; x-update(); } int query(node *x,node *y) { changeroot(x); node *nowaccess(y); return now-sum; } int main() { scanf(%d%d,a,b); node *Agetnew(a); node *Bgetnew(b); connect(A,B); cut(A,B); connect(A,B); printf(%d,query(A,B)); return 0; } 算法二十四、Splay 来自洛谷
#include bits/stdc.h #define ll long long #define N 100000 using namespace std; int sz[N], rev[N], tag[N], sum[N], ch[N][2], fa[N], val[N]; int n, m, rt, x; void push_up(int x){ sz[x] sz[ch[x][0]] sz[ch[x][1]] 1; sum[x] sum[ch[x][1]] sum[ch[x][0]] val[x]; } void push_down(int x){ if(rev[x]){ swap(ch[x][0], ch[x][1]); if(ch[x][1]) rev[ch[x][1]] ^ 1; if(ch[x][0]) rev[ch[x][0]] ^ 1; rev[x] 0; } if(tag[x]){ if(ch[x][1]) tag[ch[x][1]] tag[x], sum[ch[x][1]] tag[x]; if(ch[x][0]) tag[ch[x][0]] tag[x], sum[ch[x][0]] tag[x]; tag[x] 0; } } void rotate(int x, int k){ int y fa[x], z fa[fa[x]]; int kind ch[y][1] x; if(y k) k x; else ch[z][ch[z][1]y] x; fa[x] z; fa[y] x; fa[ch[x][!kind]] y; ch[y][kind] ch[x][!kind]; ch[x][!kind] y; push_up(y); push_up(x); } void splay(int x, int k){ while(x ! k){ int y fa[x], z fa[fa[x]]; if(y ! k) if(ch[y][1] x ^ ch[z][1] y) rotate(x, k); else rotate(y, k); rotate(x, k); } } int kth(int x, int k){ push_down(x); int r sz[ch[x][0]]1; if(k r) return x; if(k r) return kth(ch[x][0], k); else return kth(ch[x][1], k-r); } void split(int l, int r){ int x kth(rt, l), y kth(rt, r2); splay(x, rt); splay(y, ch[rt][1]); } void rever(int l, int r){ split(l, r); rev[ch[ch[rt][1]][0]] ^ 1; } void add(int l, int r, int v){ split(l, r); tag[ch[ch[rt][1]][0]] v; val[ch[ch[rt][1]][0]] v; push_up(ch[ch[rt][1]][0]); } int build(int l, int r, int f){ if(l r) return 0; if(l r){ fa[l] f; sz[l] 1; return l; } int mid l r 1; ch[mid][0] build(l, mid-1, mid); ch[mid][1] build(mid1, r, mid); fa[mid] f; push_up(mid); return mid; } int asksum(int l, int r){ split(l, r); return sum[ch[ch[rt][1]][0]]; } int main(){ //总共两个数 n 2; rt build(1, n2, 0);//建树 for(int i 1; i n; i){ scanf(%d, x); add(i, i, x);//区间加 } rever(1, n);//区间翻转 printf(%d\n, asksum(1, n));//区间求和 return 0; } 算法二十五、LCA 来自洛谷
#includecstdio //头文件 #define NI 2 //从来不喜欢算log所以一般用常数 不知道算不算坏习惯 因为3个节点 所以log3(当然以2为底)上取整得2 struct edge { int to,next,data; //分别表示边的终点下一条边的编号和边的权值 }e[30]; //邻接表点少边少开30是为了浪啊 int v[10],d[10],lca[10][NI1],f[10][NI1],tot0; //数组开到10依然为了浪 //数组还解释嘛v表示第一条边在邻接表中的编号d是深度lca[x][i]表示x向上跳2^i的节点f[x][i]表示x向上跳2^i的距离和 void build(int x,int y,int z) //建边 { e[tot].toy; e[tot].dataz; e[tot].nextv[x]; v[x]tot; e[tot].tox; e[tot].dataz; e[tot].nextv[y]; v[y]tot; } void dfs(int x) //递归建树 { for(int i1;iNI;i) //懒所以常数懒得优化 f[x][i]f[x][i-1]f[lca[x][i-1]][i-1], lca[x][i]lca[lca[x][i-1]][i-1]; //建树的同时进行预处理 for(int iv[x];i;ie[i].next) //遍历每个连接的点 { int ye[i].to; if(lca[x][0]y) continue; lca[y][0]x; //小技巧lca[x][0]即为x的父亲~~向上跳2^01不就是父节点嘛 f[y][0]e[i].data; d[y]d[x]1; dfs(y); //再以这个节点为根建子树【这里真的用得到嘛】 } } int ask(int x,int y) //询问也是关键 { if(d[x]d[y]) {int tx;xy;yt;} //把x搞成深的点 int kd[x]-d[y],ans0; for(int i0;iNI;i) if(k(1i)) //若能跳就把x跳一跳 ansf[x][i], //更新信息 xlca[x][i]; for(int iNI;i0;i--) //不知道能不能正着循环好像倒着优反正记得倒着就好了 if(lca[x][i]!lca[y][i]) //如果x跳2^i和y跳2^j没跳到一起就让他们跳 ansf[x][i]f[y][i], xlca[x][i],ylca[y][i]; return ansf[x][0]f[y][0]; //跳到LCA上去每步跳的时候都要更新信息而且要在跳之前更新信息哦~ } int main() { int a,b; scanf(%d%d,a,b); build(1,2,a); build(1,3,b); //分别建1 2、1 3之间的边 dfs(1); //以1为根建树 printf(%d,ask(2,3)); //求解2 3到它们的LCA的距离和并输出 } 算法二十六、字典树 来自洛谷
#includecstdio #includecstring #includecstdlib #includealgorithm using namespace std; struct node{ int str[26]; int sum; }s[1000]; char str1[100]; int t0,tot0,ss0; bool f1; void built() { t0; for(int i0;istrlen(str1);i) { if(str1[i]-){ f1true;continue; } if(!s[t].str[str1[i]-0]) s[t].str[str1[i]-0]tot; ts[t].str[str1[i]-0]; s[t].sumstr1[i]-0; } } int query() { int t0;int s10; for(int i0;istrlen(str1);i) { if(str1[i]-) continue; if(!s[t].str[str1[i]-0]) return s1; ts[t].str[str1[i]-0]; s1s1*10s[t].sum; } return s1; } int main() { for(int i1;i2;i) { f1false; scanf(%s,str1); built(); if(f1) ss-query(); else ssquery(); } printf(%d,ss); return 0; } 嘿嘿洛谷的没有啦~
算法二十七、Bellman-Ford 思路和别的最短路解法一样~
#include bits/stdc.h using namespace std; int dis[50], u[50], v[50], w[50], n, m; void bellman(int start) { for (int i 1;i n; i) dis[i] 0x3f3f3f3f; dis[start] 0; for (int i 1;i n; i) for (int j 1;j m; j) if (dis[v[j]] dis[u[j]] w[j]) dis[v[j]] dis[u[j]] w[j]; } int main() { n 3; m 2; for (int i 1;i m; i) cin w[i], u[i] i, v[i] i 1; bellman(1); printf(%d\n, dis[3]); return 0; } 算法二十八、可耻的打表 #include bits/stdc.h using namespace std; int a, b; int main() { scanf(%d%d, a, b); if (a 3 b 4) printf(7); if (a 45 b 55) printf(100); if (a 123 b 321) printf(444); if (a 91086199 b 18700332) printf(109786531); if (a 42267194 b 60645282) printf(102912476); if (a 69274392 b 10635835) printf(79910227); if (a 5710219 b 85140568) printf(90850787); if (a 75601477 b 24005804) printf(99607281); if (a 70597795 b 90383234) printf(160981029); if (a 82574652 b 22252146) printf(104826798); return 0; //hh这个len没加上return 0还是我加的…… } 算法二十九、SPFA求最短路之SLF优化 呃呃呃就是加了个SLF优化而已
#includebits/stdc.h using namespace std; const int maxn 100000 10; const int INF 0x7FFFFFFF;
int pre[maxn], dis[maxn], path[maxn]; bool vis[maxn]; int head[maxn], n, m;
int tot, cnt; struct node { int v, w, next; } E[2 * maxn]; void add(int u, int v, int w) { E[tot].v v; E[tot].w w; E[tot].next head[u]; head[u] tot; } void init() { tot 0; memset(vis, 0, sizeof vis); memset(head, -1, sizeof head); } void spfa(int st) { for (int i 1;i n; i) vis[i] false, dis[i] INF; int now, next; dis[st] 0; vis[st] 1; dequeint q; q.push_back(st); pre[st] -1; while(!q.empty()) { now q.front(); q.pop_front(); vis[now] 0; for (int i head[now]; i ! -1;i E[i].next) { next E[i].v; if(dis[next] dis[now] E[i].w) { dis[next] dis[now] E[i].w; pre[next] now; if(!vis[next]) { vis[next] 1; if (q.empty() || dis[next] dis[q.front()]) q.push_back(next); else q.push_front(next); } } } } } void print(int x) { if(pre[x] -1) return; print(pre[x]); printf(%d , x); } int main() { init(); n 3; m 2; int w; for (int i 1;i m; i) {scanf(%d, w); add(i, i 1, w);} spfa(1); if(dis[n] INF) puts(-1); else printf(%d\n, dis[n]); return 0; } 算法三十、SPFA之LLL优化 #includebits/stdc.h #define MAXN 10010 #define MAXM 500010 #define MAX 2147483647 using namespace std; int n, m, t, c 1; int head[MAXN], path[MAXN]; bool vis[MAXN]; struct node { int next, to, w; }a[MAXM 1]; inline int relax (int u, int v, int w) { if (path[v] path[u] w) { path[v] path[u] w; return 1; } return 0; } inline void add(int u, int v, int w) { a[c].to v; a[c].w w; a[c].next head[u]; head[u] c; } void spfa() { int u, v, num 0; long long x 0; listint q; for (int i 1;i n; i){path[i] MAX; vis[i] 0;} path[1] 0; vis[1] 1; q.push_back(1); num; while (!q.empty()) { u q.front(); q.pop_front(); num--; x - path[u]; while (num path[u] x / num){ q.push_back(u); u q.front(); q.pop_front(); } vis[u] 0; for (int i head[u]; i ; i a[i].next) { v a[i].to; if (relax(u, v, a[i].w) !vis[v]) { vis[v] 1; if(!q.empty() path[v] path[q.front()]) q.push_front(v); else q.push_back(v); num; x path[v]; } } } } int main() { n 3; m 2; for (int i 1;i m; i) { int w; scanf(%d, w); add(i, i 1, w); } spfa(); printf(%d\n, path[n]); return 0; } 算法三十一、SPFA之SLFLLL优化算法 #include bits/stdc.h using namespace std; const int INF 1 30; const int gg 200000 11; int head[gg], dis[gg], n, m, cnt; bool vis[gg]; int sum, tot; struct node{ int net, to, w; } a[gg];
inline void add(int i, int j, int w) { a[cnt].to j; a[cnt].net head[i]; a[cnt].w w; head[i] cnt; }
inline void spfa(int s) { dequeint q; for (int i 1;i n; i) dis[i] INF; dis[s] 0; vis[s] 1; q.push_back(s); tot 1; while(!q.empty()) { int u q.front(); q.pop_front(); vis[u] false; tot--; sum - dis[u]; for (int i head[u]; ~i ; i a[i].net) { int v a[i].to; if (dis[v] dis[u] a[i].w) { dis[v] dis[u] a[i].w; if(!vis[v]) { vis[v] 1; if (q.empty() || dis[v] dis[q.front()] || dis[v] * tot sum) q.push_back(v); tot; sum dis[v]; } } } } }
int main() { memset(head, -1, sizeof head); n 3; m 2; for (int i 1;i m; i) { int w 0; scanf(%d, w); add(i, i 1, w); } spfa(1); if (dis[n] INF) puts(-1); else printf(%d\n, dis[n]); return 0; } 算法三十二、只用一个变量跑AB 把一个long long拆成两个int 指针啊
#includeiostream using namespace std; long long a; int main() { scanf(%d%d, (int*)(a), (int*)(a1)); printf(%d\n, *((int*)a) *((int*)(a1))); return 0; } 算法三十三、矩阵乘法 #includebits/stdc.h using namespace std; int a, b; int x[2][2] { {0, 1}, {1, 1} }; void mo(int f[]) { int ans[2] {0}; for(int i 0; i 2; i) for(int j 0; j 2; j) ans[i] f[j] * x[i][j]; for(int i 0; i 2; i) f[i] ans[i]; } int main() { cin a b; int f[3] {a, b}; mo(f); cout f[1]; return 0; } 算法三十四、STLdijkstra #include iostream #include cstdio #include cstdlib #include cmath #include cctype #include climits #include algorithm #include map #include queue #include vector #include ctime #include string #include cstring using namespace std; const int N405; struct Edge { int v,w; }; vectorEdge edge[N*N]; int n; int dis[N*N]; bool vis[N*N]; struct cmp { bool operator()(int a,int b) { return dis[a]dis[b]; } }; int Dijkstra(int start,int end) { priority_queueint,vectorint,cmp dijQue; memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); dijQue.push(start); dis[start]0; while(!dijQue.empty()) { int udijQue.top(); dijQue.pop(); vis[u]0; if(uend) break; for(int i0; iedge[u].size(); i) { int vedge[u][i].v; if(dis[v]-1 || dis[v]dis[u]edge[u][i].w) { dis[v]dis[u]edge[u][i].w; if(!vis[v]) { vis[v]true; dijQue.push(v); } } } } return dis[end]; } int main() { int a,b; scanf(%d%d,a,b); Edge Qpush; Qpush.v1; Qpush.wa; edge[0].push_back(Qpush); Qpush.v2; Qpush.wb; edge[1].push_back(Qpush); printf(%d,Dijkstra(0,2)); return 0; } 算法三十五、数学表达式 #include bits/stdc.h using namespace std; long long a, b; int main() { cin a b; cout a - b (a * 2) - (a - b) - a (a (b - a)) endl; return 0; } 算法三十六、define大法 #include bits/stdc.h #define ___ int #define $$$ main #define _$_$_ return #define _ cin #define $ cout #define __ using #define $$ namespace #define o_o std __ $$ o_o; ___ $$$(){ ___ _$o$_,$o_o$; _ _$o$_ $o_o$; $ _$o$_ $o_o$; _$_$_ 0; } 算法三十七、压位高精度加法 奇怪的知识又增加了
#include bits/stdc.h using namespace std; const int mod 100000000; vectorint add(vectorint A, vectorint B) { vectorint C; int t 0; for (int i 0; i A.size() || i B.size(); i) { if (i A.size()) t A[i]; if (i B.size()) t B[i]; C.push_back(t % mod); t / mod; } if (t) C.push_back(t); return C; } int main() { string a, b; cin a b; vectorint A, B, C; for (int i a.size() - 1, s 0, j 0, t 1; i 0; i--) { s (a[i] - 0) * t; j; t * 10; if (j 8 || i 0) A.push_back(s), s 0, j 0, t 1; } for (int i b.size() - 1, s 0, j 0, t 1; i 0; i--) { s (b[i] - 0) * t; j; t * 10; if (j 8 || i 0) B.push_back(s), s 0, j 0, t 1; } C add(A, B); cout C.back(); for (int i C.size() - 2; i 0; i--) printf(%08d, C[i]); return 0; } 算法三十八、加一大堆东东…… 听说手动开O3优化……
虽然好像没优化多少 #pragma GCC diagnostic error -stdc11 #pragma GCC target(avx) #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(Ofast) #pragma GCC optimize(inline) #pragma GCC optimize(-fgcse) #pragma GCC optimize(-fgcse-lm) #pragma GCC optimize(-fipa-sra) #pragma GCC optimize(-ftree-pre) #pragma GCC optimize(-ftree-vrp) #pragma GCC optimize(-fpeephole2) #pragma GCC optimize(-ffast-math) #pragma GCC optimize(-fsched-spec) #pragma GCC optimize(unroll-loops) #pragma GCC optimize(-falign-jumps) #pragma GCC optimize(-falign-loops) #pragma GCC optimize(-falign-labels) #pragma GCC optimize(-fdevirtualize) #pragma GCC optimize(-fcaller-saves) #pragma GCC optimize(-fcrossjumping) #pragma GCC optimize(-fthread-jumps) #pragma GCC optimize(-funroll-loops) #pragma GCC optimize(-fwhole-program) #pragma GCC optimize(-freorder-blocks) #pragma GCC optimize(-fschedule-insns) #pragma GCC optimize(inline-functions) #pragma GCC optimize(-ftree-tail-merge) #pragma GCC optimize(-fschedule-insns2) #pragma GCC optimize(-fstrict-aliasing) #pragma GCC optimize(-fstrict-overflow) #pragma GCC optimize(-falign-functions) #pragma GCC optimize(-fcse-skip-blocks) #pragma GCC optimize(-fcse-follow-jumps) #pragma GCC optimize(-fsched-interblock) #pragma GCC optimize(-fpartial-inlining) #pragma GCC optimize(no-stack-protector) #pragma GCC optimize(-freorder-functions) #pragma GCC optimize(-findirect-inlining) #pragma GCC optimize(-fhoist-adjacent-loads) #pragma GCC optimize(-frerun-cse-after-loop) #pragma GCC optimize(inline-small-functions) #pragma GCC optimize(-finline-small-functions) #pragma GCC optimize(-ftree-switch-conversion) #pragma GCC optimize(-foptimize-sibling-calls) #pragma GCC optimize(-fexpensive-optimizations) #pragma GCC optimize(-funsafe-loop-optimizations) #pragma GCC optimize(inline-functions-called-once) #pragma GCC optimize(-fdelete-null-pointer-checks) #include bits/stdc.h using namespace std; int main() { int a, b; scanf(%d%d, a, b); printf(%d, a b); return 0; } 算法三十九、暴力枚举优化版 和算法六区别“不大”但是时间优化了300ms…… 时间1567ms 1567
就是在 min(2×a,2×b) ( 2 × , 2 × ) 到 max(2×a,2×b) ( 2 × , 2 × ) 之间枚举效率高了“亿”点点
#include bits/stdc.h using namespace std; int main() { int a, b; scanf(%d%d, a, b); for (int i min(2 * a, 2 * b);i max(2 * a, 2 * b); i) if (a b i) { printf(%d, i); //注意要输出i不然如果输出ab循环就没意义了…… return 0; } } 算法四十、矩阵DP 就是和方格取数之类的这些同样的思维~
#include bits/stdc.h using namespace std; int a[110][110], n 2; int main() { for (int i 1;i n; i) for (int j 1;j n; j) scanf(%d, a[i][j]); for (int i 1;i n; i) for (int j 1;j n; j) if (max(a[i - 1][j], a[i][j - 1]) -1) a[i][j] max(a[i - 1][j], a[i][j - 1]); printf(%d\n, a[n][n]); return 0; } 算法四十一、拖延时间大法 yyds!永远的拖延时间
3176 ms天哪 #include algorithm //STL 通用算法 #include bitset //STL 位集容器 #include cctype //字符处理 #include cerrno //定义错误码 #include cfloat //浮点数处理 #include ciso646 //对应各种运算符的宏 #include climits //定义各种数据类型最值的常量 #include clocale //定义本地化函数 #include cmath //定义数学函数 #include complex //复数类 #include csignal //信号机制支持 #include csetjmp //异常处理支持 #include cstdarg //不定参数列表支持 #include cstddef //常用常量 #include cstdio //定义输入输出函数 #include cstdlib //定义杂项函数及内存分配函数 #include cstring //字符串处理 #include ctime //定义关于时间的函数 #include cwchar //宽字符处理及输入输出 #include cwctype //宽字符分类 #include deque //STL 双端队列容器 #include exception //异常处理类 #include fstream //文件输入输出 #include functional //STL 定义运算函数代替运算符 #include limits //定义各种数据类型最值常量 #include list //STL 线性列表容器 #include locale //本地化特定信息 #include map //STL 映射容器 #include memory //STL通过分配器进行的内存分配 #include new //动态内存分配 #include numeric //STL常用的数字操作 #include iomanip //参数化输入输出 #include ios //基本输入输出支持 #include iosfwd //输入输出系统使用的前置声明 #include iostream //数据流输入输出 #include istream //基本输入流 #include iterator //STL迭代器 #include ostream //基本输出流 #include queue //STL 队列容器 #include set //STL 集合容器 #include sstream //基于字符串的流 #include stack //STL 堆栈容器 #include stdexcept //标准异常类 #include streambuf //底层输入输出支持 #include string //字符串类 #include typeinfo //运行期间类型信息 #include utility //STL 通用模板类 #include valarray //对包含值的数组的操作 #include vector //STL 动态数组容器 //头文件拖延编译时间虽然不能拖延运行时间但能拖一点编译时间也很不错了hh using namespace std; int main(){ int a; int b; //不用int a, b;拖延运行时间 cin a b; //cin拖延运行时间 int ans 1 * 10000 / 10 / 10 / 10 / 10 * 5 * 2 / 10 - 1; //ans表达式拖延编译和运行时间 for (int i 1;i a; i) ans 5, ans - 4; //拖延时间 for (int i 1;i b; i) ans 5, ans - 4; //拖延时间 ans ans - ans ans ans - ans; //表达式拖延时间 cout ans endl; //cout和多输出回车拖延时间 return 0; } 算法四十二、极限卡点 卡到了9970ms……
#include bits/stdc.h using namespace std; int st clock(); int main() { int a, b; scanf(%d%d, a, b); while (clock() - st 995000) {} printf(%d, a b); return 0; } 算法四十三、快读快写 #includebits/stdc.h using namespace std; int read() { int s 0, f 1; char ch getchar(); while(!isdigit(ch)) { if(ch -) f -1; ch getchar(); } while(isdigit(ch)) { s s * 10 ch - 0; ch getchar(); } return s * f; } void write(int x) { if(x 0) { putchar(-); x -x; } if(x 9) write(x / 10); putchar(x % 10 0); return; } int main() { int a, b; a read(); b read(); write(a b); return 0; } 算法四十四、终极大杀器快读快写 #includebits/stdc.h using namespace std; static char buf[100000], *pa buf, *pd buf; #define gc pa pd (pd (pa buf) fread(buf, 1, 100000, stdin), pa pd) ? EOF : *pa inline int read() { register int x(0); register char c(gc); while (c 0 || c 9) c gc; while (c 0 c 9) x (x 1) (x 3) (c ^ 48), c gc; return x; } void write(int x) { if(x 0) { putchar(-); x -x; } if(x 9) write(x / 10); putchar(x % 10 0); return; } int main() { int a, b; a read(); b read(); write(a b); return 0; } 算法四十五、sort大大大大大大大大大法 sort yyds!
#include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, a[MAXN]; int main(){ n 2; for (int i 1;i n; i) scanf(%d, a[i]); sort(a 1, a 1 n); int ans 0; for (int i 1;i n; i) ans a[i]; printf(%d, ans); return 0; } 算法四十六、冒泡排序 E……
#include bits/stdc.h using namespace std; const int MAXN 1e8 10; int a[MAXN], n; int main(){ n 2; for (int i 1;i n; i) scanf(%d, a[i]); for (int i n;i 1; i--) for(int j 1;j i; j) if(a[j] a[j 1]) swap(a[j], a[j 1]); int ans 0; for (int i 1;i n; i) ans a[i]; printf(%d, ans); return 0; } 算法四十七、选择排序 ………………
#include bits/stdc.h using namespace std; const int MAXN 1e8 10; int a[MAXN], n; int main(){ n 2; for (int i 1;i n; i) scanf(%d, a[i]); for (int i 1;i n; i) { int w i, Min a[i]; for (int j i;j n; j) if(Min a[j]) w j, Min a[j]; //寻找最小数和它的位置 swap(a[i], a[w]); } int ans 0; for (int i 1;i n; i) ans a[i]; printf(%d, ans); return 0; } 算法四十八、插入排序 #include bits/stdc.h using namespace std; const int MAXN 1e8 10; int a[MAXN], n; int main(){ n 2; for (int i 1;i n; i) { scanf(%d, a[i]); int x i - 1; while(a[x] a[x 1] x 0) swap(a[x], a[x 1]), x--; } int ans 0; for (int i 1;i n; i) ans a[i]; printf(%d, ans); return 0; } 算法四十九、希尔排序 azzzzzzzzzzzzzzzzzz
#include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, a[MAXN]; int main(){ n 2; for (int i 0;i n; i) scanf(%d, a[i]); for (int step n / 2; step 0; step / 2) for (int i 0;i step; i) for (int j i step;j n; j step) if(a[j] a[j - step]) { int temp a[j]; int k j - step; while (k 0 temp a[k]) { swap(a[k step], a[k]); k - step; } } int ans 0; for (int i 0;i n; i) ans a[i]; printf(%d , ans); return 0; } 算法五十、归并排序 #include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, a[MAXN], T[MAXN]; void Mergesort(int l, int r) { if (l r) return; //区间内只有一个数返回 int mid l r 1; //相当于(l r) / 2 Mergesort(l, mid); //递归左半部分 Mergesort(mid 1, r); //递归右半部分 int i l, j mid 1, k l; while (i mid j r) //合并 if (a[i] a[j]) T[k] a[i]; else T[k] a[j]; while (i mid) T[k] a[i]; while (j r) T[k] a[j]; for (int q l; q r; q) a[q] T[q]; //转移 } int main() { n 2; for (int i 1; i n; i) scanf(%d, a[i]); Mergesort(1, n); int ans 0; for (int i 1; i n; i) ans a[i]; printf(%d, ans); return 0; } 算法五十一、快速排序 #include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, a[MAXN]; void quickSort(int l, int r) { if (l r) return; int i l, j r, base a[l]; //base取最左边的数为基准数 while(i j) { while (a[j] base i j) j--; while (a[i] base i j) i; if (i j) swap(a[i], a[j]); } a[l] a[i]; a[i] base; //基准数归位 quickSort (l, i - 1); //递归左边 quickSort (i 1, r); //递归右边 } int main() { n 2; for (int i 1; i n; i) scanf(%d, a[i]); quickSort(1, n); int ans 0; for (int i 1; i n; i) ans a[i]; printf(%d, ans); return 0; } 算法五十二、堆排序 #include bits/stdc.h using namespace std; int n; const int MAXN 1e8 10; int h[MAXN], s; void down(int u) { int t u; // t记录最小值 if (2 * u s h[2 * u] h[t]) t 2 * u; // 左儿子 if (2 * u 1 s h[2 * u 1] h[t]) t 2 * u 1; // 右儿子 if (t ! u) { //需要调整 swap(h[t], h[u]); down(t); //递归 } } int main() { n 2; for (int i 1; i n; i ) scanf(%d, h[i]); s n; for (int i n / 2; i 1; i--) down(i); //初始化堆j int ans 0; while (n--) { ans h[1]; h[1] h[s]; s--; down(1); } printf(%d, ans); return 0; } 算法五十三、计数排序 #include bits/stdc.h using namespace std; const int MAXN 1e8 10; long long n, cnt[MAXN]; int main() { n 2; int x 0, Max -0x3f3f3f, Min 0x3f3f3f; //初始化最大值和最小值 for (int i 1; i n; i ) { scanf(%d, x); cnt[x]; //统计 Max max(Max, x); Min min(Min, x); //更新最大值和最小值 } int ans 0; for (int i Min;i Max; i) while(cnt[i]) cnt[i]--, ans i; printf(%d, ans); return 0; } 算法五十四、桶排序 #include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, Min MAXN, Max 0, sum[MAXN], ans; bool f[45]; vectorint bucket[45];//定义桶这里定义40个桶 void insertsort(int s) { for (int i 0;i bucket[s].size(); i) for (int j i;j 1; j--) if(bucket[s][j - 1] bucket[s][j]) swap(bucket[s][j], bucket[s][j - 1]);//这里是从小到大排序 for (int i 0;i bucket[s].size(); i) ans bucket[s][i]; } void bucketsort() { for (int i 1;i n; i) bucket[int((sum[i] - Min) / ((Max - Min 1) / 40.0))].push_back(sum[i]), f[int((sum[i] - Min) / ((Max - Min 1) / 40.0))] 1;//运用最大最小值来合理分配桶 for (int i 0;i 40; i) if(f[i]) insertsort(i); //如果当前桶有数值则对桶内的数进行排序这里用选择排序 } int main() { n 2; for (int i 1;i n; i) { scanf(%d, sum[i]); Min min(Min, sum[i]), Max max(Max, sum[i]); //为了能够合理利用空间确保第一个桶和最后一个桶都有数所以存储最大最小值 } bucketsort(); printf(%d, ans); return 0; } 算法五十五、基数排序 #include bits/stdc.h using namespace std; int maxbit(int data[], int n) { int d 1, p 10; //d保存最大的位数 for (int i 0;i n; i) while(data[i] p) p * 10, d; return d; } void radixsort(int data[], int n) { //基数排序 int d maxbit(data, n); int tmp[n]; int cnt[15], i, j, k, radix 1; for (i 1;i d; i) { //进行d次排序 memset(cnt, 0, sizeof(cnt)); //清空计数器 for (j 0;j n; j) { k (data[j] / radix) % 10; cnt[k]; } for (j 1;j 10; j) cnt[j] cnt[j - 1]; for (j n - 1;j 0; j--) { k (data[j] / radix) % 10; tmp[cnt[k] - 1] data[j]; cnt[k]--; } for (j 0;j n; j) data[j] tmp[j]; radix * 10; } } const int MAXN 1e8 10; int n, a[MAXN]; int main(){ n 2; for (int i 0;i n; i) scanf(%d, a[i]); radixsort(a, n); int ans 0; for (int i 0;i n; i) ans a[i]; printf(%d, ans); } 算法五十六、鸡尾酒排序 #include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, a[MAXN]; int main() { n 2; for (int i 1;i n; i) scanf(%d, a[i]); int cnt 0; while (1) { int f 0; cnt; if(cnt 1) for (int i 1;i n; i) if(a[i] a[i 1]) swap(a[i], a[i 1]), f 1; else for (int i n;i 1; i--) if(a[i] a[i - 1]) swap(a[i], a[i - 1]), f 1; if(!f) break; } int ans 0; for (int i 1;i n; i) ans a[i]; printf(%d, ans); return 0; } 算法五十七、二叉排序树排序 怎么还是排序hh
#includebits/stdc.h #define LL long long #define INF 0x7FFFFFFF using namespace std; const int N 1e8 10; int n, idx, rt, ans; int a[N], t[N]; int ch[N][2]; void insert(int x, int val) { if (!x) { x idx; t[x] val; return; } else { if(val t[x]) insert(ch[x][0], val); else insert(ch[x][1], val); } } void dfs(int x) { //中序遍历二叉排序树 if(!x) return; dfs(ch[x][0]); ans t[x]; dfs(ch[x][1]); } int main() { n 2; for (int i 1;i n; i) scanf(%d, a[i]); for (int i 1;i n; i) insert(rt, a[i]); dfs(rt); printf(%d, ans); return 0; } 算法五十八、侏儒排序 #include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, a[MAXN]; int main() { n 2; for (int i 1;i n; i) scanf(%d, a[i]); int s 1; while(s n) { if(a[s - 1] a[s] || s 0) s; else swap(a[s], a[s - 1]), s--; } int ans 0; for (int i 1;i n; i) ans a[i]; printf(%d, ans); return 0; } 算法五十九、猴子排序 虽然在排序上理论会TLE……但是AB还是能AC的…… 排序终于结束了……hh
#include bits/stdc.h using namespace std; const int MAXN 1e8 10; int n, a[MAXN]; int check() { for (int i 1;i n; i) if(a[i] a[i 1]) return 0; return 1; } int main() { n 2; for (int i 1;i n; i) scanf(%d, a[i]); while (1) { random_shuffle(a 1, a 1 n); //随机打乱数组的系统函数 if(check()) break; } int ans 0; for (int i 1;i n; i) ans a[i]; printf(%d, ans); return 0; } 算法六十、快速幂 #includebits/stdc.h using namespace std; int qmi(int m, int k, int p) { int res 1 % p, t m; while (k) { if (k 1) res res * t % p; t t * t % p; k 1; } return res; } int main() { int a, b; scanf(%d%d, a, b); printf(%d, qmi(a, 1, 100000010) qmi(b, 1, 100000010)); return 0; } 算法六十一、差分 #include bits/stdc.h using namespace std; int n 2, m 5, b[10]; int main() { for (int i 1;i n; i) { int x; scanf(%d, x); b[1] x; b[m 1] - x; } int ans 0, x 0; for (int i 1;i m; i) { x b[i]; ans max(ans, x); } printf(%d, ans); return 0; } 算法六十二、模拟人工计算 当然这注释是和人工计算最接近的hh #include bits/stdc.h using namespace std; int a, b; int main() { scanf(%d%d, a, b); //人眼看见数据 if (a 0) {printf(%d, b); return 0;} //大脑瞬间“打表”被老师发现了血量减少50…… if (b 0) {printf(%d, a); return 0;} //大脑瞬间“打表”被老师发现了血量减少50…… int f1 0, f2 0; //大脑申请了两个空间……还好没炸掉 if (a 0) f1 1; //大脑正在判断请勿打扰…… if (b 0) f2 1; //大脑正在判断请勿打扰…… a abs(a); b abs(b); //哇大脑使用了去掉负号的大法 int ans 0; //大脑申请了一个空间 if (f1) ans - a; //大脑正在艰难地判断着…… //大脑指挥手拿起笔在草稿纸上划来划去…… //大脑感到烦躁 //眼睛看到老师转了一下身子立刻反馈给大脑 //大脑指挥手在计算器键盘上写下了算式…… //眼睛看到答案反馈给大脑大脑立刻指挥手关掉了计算器…… //眼睛看到老师转回来了 else ans a; //大脑正在艰难地判断着…… if (f2) ans - b;//大脑正在艰难地判断着…… //大脑指挥手拿起笔在草稿纸上划来划去…… //大脑感到烦躁 //眼睛看到老师转了一下身子立刻反馈给大脑 //大脑指挥手在计算器键盘上写下了算式…… //眼睛看到答案反馈给大脑大脑立刻指挥手关掉了计算器…… //眼睛看到老师转回来了 else ans b;//大脑正在艰难地判断着…… //眼睛观察到老师正在身后冷冷地看着…… //大脑感到紧张 //大脑让身体不由自主地颤抖起来 //大脑差点死机 //大脑复活 //立刻写下答案 printf(%d, ans); //大脑又死机了…… //耳朵听到老师在叫自己起来 //大脑指挥身体起来了 //开始下一题……下一个数据 return 0; } 算法六十三、二进制 额……好像有点不太正常
#includebits/stdc.h using namespace std; int a, b, s, s1, i, na, nb; int main() { scanf(%d%d, a, b); if (a 0) na 1, a abs(a); while(a) { if ((a 1) ! 0) s pow(2, (a 1) * i); a 1; i; } i 0; if (na 1) s abs(s); if (b 0) nb 1, b abs(b); while(b) { if ((b 1) ! 0) s1 pow(2, (b 1) * i); b 1; i; } if (nb 1) s1 abs(s1); printf(%d, s s1); return 0; } 算法六十四、ST表 区间最小值加区间最大值 AB
#include bits/stdc.h using namespace std; int n, a[10], st1[10][17], st2[10][17]; void ST_work1() { for (int i 1; i n; i) st1[i][0] a[i]; int t log(n) / log(2) 1; for (int j 1; j t; j) { for (int i 1; i n - (1 j) 1; i) st1[i][j] max(st1[i][j - 1], st1[i (1 (j - 1))][j - 1]); } } int ST_query1(int l, int r) { int k log(r - l 1) / log(2); return max(st1[l][k], st1[r - (1 k) 1][k]); } void ST_work2() { for (int i 1; i n; i) st1[i][0] a[i]; int t log(n) / log(2) 1; for (int j 1; j t; j) { for (int i 1; i n - (1 j) 1; i) st1[i][j] min(st1[i][j - 1], st1[i (1 (j - 1))][j - 1]); } } int ST_query2(int l, int r) { int k log(r - l 1) / log(2); return min(st1[l][k], st1[r - (1 k) 1][k]); } int main() { n 2; for (int i 1; i n; i) scanf(%d, a[i]); ST_work1(); int ans1 ST_query1(1, 2); ST_work2(); int ans2 ST_query2(1, 2); printf(%d, ans1 ans2); return 0; } 算法六十五、01背包 #include bits/stdc.h using namespace std; int c[1010], w[1010], dp[1010], n, m; int main() { n 2; m 2; //2个物体背包容积2 for (int i 1;i n; i) c[1] 1, scanf(%d, w[i]); //设体积为1读入价值 for (int i 1;i n; i) for (int j m; j c[i]; j--) dp[j] max(dp[j], dp[j - c[i]] w[i]); printf (%d\n, dp[m]); return 0; } 算法六十六、完全背包 #include bits/stdc.h using namespace std; int c[1010], w[1010], dp[1010], n, m; int main() { n 2; m 3; for (int i 1;i n; i) scanf(%d, w[i]); for (int i 1;i n; i) for (int j c[i]; j m; j) dp[j] max(dp[j], dp[j - c[i]] w[i]); printf (%d\n, dp[m]); return 0; } 算法六十七、多重背包之暴力拆分法 #include bits/stdc.h using namespace std; int c[110], w[110], s[110], dp[1010], n, m; int main() { n 2; m 2; for (int i 1;i n; i) scanf(%d, w[i]), c[i] s[i] 1; for (int i 1;i n; i) for (int x 1;x s[i]; x) for (int j m; j c[i]; j--) dp[j] max(dp[j], dp[j - c[i]] w[i]); printf (%d\n, dp[m]); return 0; } 算法六十八、多重背包之二进制拆分 #include bits/stdc.h using namespace std; int n, m, v[10010], w[10010], f[2010]; int main() { n 2; m 2; int cnt 0; for (int i 1; i n; i) { int a 1, b, s 1, k 1; scanf(%d, b); while (k s) { cnt; v[cnt] a * k; w[cnt] b * k; s - k; k 1; } if (s 0) { cnt; v[cnt] a * s; w[cnt] b * s; } } n cnt; for (int i 1; i n; i ) for (int j m; j v[i]; j -- ) f[j] max(f[j], f[j - v[i]] w[i]); printf(%d\n, f[m]); return 0; } 算法六十九、二维费用背包问题 #include bits/stdc.h using namespace std; int N, V, M; int v[1010], m[1010], w[1010], f[1010][1010]; int main () { N V M 2; for (int i 1; i N; i) scanf(%d, w[i]), v[i] m[i] 1; for (int i 1; i N; i) for (int j V; j v[i]; j--) for (int k M; k m[i]; k--) f[j][k] max(f[j - v[i]][k - m[i]] w[i], f[j][k]); printf(%d\n, f[V][M]); return 0; } 算法七十、分组背包问题 #include bits/stdc.h using namespace std; int f[110][110], v[110][110], w[110][110], s[110]; int n, m, k; int main() { n m 2; for (int i 1; i n; i) { s[i] 1; for (int j 0; j s[i]; j) scanf(%d, w[i][j]), v[i][j] 1; } for (int i 1; i n; i) { for (int j 0; j m; j) { f[i][j] f[i - 1][j]; for (int k 0; k s[i]; k) if (j v[i][k]) f[i][j] max(f[i][j], f[i - 1][j - v[i][k]] w[i][k]); } } printf(%d, f[n][m]); return 0; } 算法七十一、有依赖的背包问题 #include bits/stdc.h using namespace std; int n, m, v[110], w[110]; int h[110], e[110], ne[110], idx; int f[110][110];
void add(int a, int b) { e[idx] b, ne[idx] h[a], h[a] idx; } void dfs(int u) { for (int i h[u]; ~i; i ne[i]) { // 循环物品组 int son e[i]; dfs(e[i]); // 分组背包 for (int j m - v[u]; j 0; j -- ) // 循环体积 for (int k 0; k j; k ) // 循环决策 f[u][j] max(f[u][j], f[u][j - k] f[son][k]); } // 将物品u加进去 for (int i m; i v[u]; i -- ) f[u][i] f[u][i - v[u]] w[u]; for (int i 0; i v[u]; i ) f[u][i] 0; } int main() { n m 2; memset(h, -1, sizeof h); int root; for (int i 1; i n; i) { int p; v[i] 1; scanf(%d, w[i]); if (i 1) p -1; else p 1; //AB中的特判 if (p -1) root i; else add(p, i); } dfs(root); printf(%d, f[root][m]); return 0; } 算法七十二、多重背包队列优化 #include bits/stdc.h using namespace std; int n, m; int f[20010], g[20010], q[20010]; int main() { n m 2; for (int i 1; i n; i ) { int v 1, w, s 1; scanf(%d, w); memcpy(g, f, sizeof f); for (int j 0; j v; j ) { int hh 0, tt -1; for (int k j; k m; k v) { if (hh tt q[hh] k - s * v) hh ; //剔除超出长度元素 if (hh tt) f[k] max(f[k], g[q[hh]] (k - q[hh]) / v * w); //更新当前答案 while (hh tt g[q[tt]] - (q[tt] - j) / v * w g[k] - (k - j) / v * w) tt -- ; //维持单调性 //这里也可以这样写更易理解 //while (hh tt g[q[tt]] g[k] - (k - q[tt]) / v * w) tt -- ; q[tt] k; } } } printf(%d, f[m]); return 0; } 算法七十三、istream _iterator 还是大佬们厉害我没看懂……
#include iostream #include cstring #include algorithm #include numeric #includeiterator using namespace std; int main() { istream_iteratorint in(cin), eof; cout accumulate(in, eof ,0) endl; return 0; } 算法七十四、进制转换 我本来想要十进制转二进制一个算法十进制转三进制一个算法……然后发现甚至可以到十进制转108 10 8 进制…… 而且它们都属于进制转换所以我决定直接写一个通用的进制转换程序。 然后随机进制转换在那个进制下加法再转化为十进制存储下来如果所有的答案都一样则输出这个答案。 我是不是很无聊
#include bits/stdc.h using namespace std; int A[30], B[30], a, b; int check(int mod) { int x a, y b, ta 0, tb 0; while (x) { A[ta] x % mod; x / mod; } while (y) { B[tb] y % mod; y / mod; } for (int i 1; i max(ta, tb); i) { A[i] B[i]; if (A[i] mod) A[i 1] A[i] / mod, A[i] % mod; } if (A[ta 1]) ta; int Ans 0; for (int i ta; i 0; i--) Ans Ans * mod A[i]; return Ans; } int main() { scanf(%d%d, a, b); int ans[100010]; for (int i 1; i 100000; i) { srand((unsigned)time(NULL)); int o (int) rand() % 1000000 2; //取随机进制 ans[i] check(o); } bool f 1; for (int i 2; i 100000; i) if (ans[i] ! ans[i - 1]) { f 0; break; } if (f) printf(%d\n, ans[1]); else puts(老子不干了WA就WA吧一行WA上西天); //誓死不AC逃 return 0; } 算法七十五、指针算法 #include bits/stdc.h using namespace std; int main() { int a, b; cinab; int *c a, *d b, ans; ans *c *d; cout ans endl; } 算法七十六、vector #include bits/stdc.h using namespace std; vectorint v; int main() { int x 0; while (cinx) v.push_back(x); int ans 0; for (int i 0; i v.size(); i) ans v[i]; cout ans; return 0; } 算法七十七、queue #include bits/stdc.h using namespace std; queueint q; int main() { int x; while (cinx) q.push(x); int ans 0; while (q.size()) ans q.front(), q.pop(); cout ans; return 0; } 算法七十八、deque #include bits/stdc.h using namespace std; dequeint a, b; int main() { int x; while (cinx) a.push_front(x); int ans 0; while (a.size()) ans a.back(), b.push_back(a.back()), a.pop_back(); int res 0; while (b.size()) res b.front(), b.pop_front(); if (ans res) cout (ans res) / 2; return 0; } 算法七十九、list #include bits/stdc.h using namespace std; listint a, b; int main() { int x; while (cinx) a.push_front(x); int ans 0; while (a.size()) b.push_back(a.back()), ans a.back(), a.pop_back(); int res 0; while (b.size()) res b.front(), b.pop_front(); if (ans res) cout (ans res) / 2; return 0; } 算法八十、map #include bits/stdc.h using namespace std; mapint, string m; int main() { int x 0; while (cinx) m[x] 老子不会老子WA行了吧; int ans 0; for (auto iter m.begin(); iter ! m.end(); iter) { ans iter-first; } cout ans; return 0; } 算法八十一、set #include bits/stdc.h using namespace std; setint s; int main() { int x 0; while (cinx) s.insert(x); int ans 0; for (auto iter s.begin(); iter ! s.end(); iter) { ans *iter; } cout ans; return 0; } 算法八十二、pair #include bits/stdc.h using namespace std; int main() { pairint, int a[110]; int x 0, c 0, t 1; while (cinx) { if (c 0) a[t].first x, c 1; else a[t].second x, t, c 0; } int ans 0; for (int i 1; i 100; i) { ans a[i].first a[i].second; } cout ans; return 0; } 算法八十三、stack #include bits/stdc.h using namespace std; stackint s; int main() { int x 0; while (cinx) s.push(x); int ans 0; while (s.size()) ans s.top(), s.pop(); cout ans; return 0; } 算法八十四、priority _queue #include bits/stdc.h using namespace std; priority_queueint q; int main() { int x 0; while (cinx) q.push(x); int ans 0; while (q.size()) ans q.top(), q.pop(); cout ans; return 0; } 算法八十五、不用变量 感谢JcWing
#include iostream using namespace std;
int main () { cin *new int () *new int (); cout *(new int () - 16) *(new int () - 16); return 0; } 懵了没 搞了那么久我们来个正常的吧…… 满足某人的需求 观众们你是认真的吗
C代码
#include stdio.h
int main() { int a,b; scanf(%d%d, a, b); printf(%d\n, a b); return 0; } C代码
#include iostream #include cstdio
using namespace std;
int main() { int a,b; cin a b; cout ab endl; return 0; } Pascal代码
var a, b: longint; begin readln(a,b); writeln(ab); end. Python代码
import sys
for line in sys.stdin: print sum(map(int, line.split())) Python2代码
s raw_input().split() print int(s[0]) int(s[1]) Python3代码
print(sum(map(int, input().split()))) Java代码
import java.io.*; import java.util.*; public class Main { public static void main(String args[]) throws Exception { Scanner cinnew Scanner(System.in); int a cin.nextInt(), b cin.nextInt(); System.out.println(ab); } } JavaScript代码Node.js
const fs require(fs) const data fs.readFileSync(/dev/stdin) const result data.toString(ascii).trim().split( ).map(x parseInt(x)).reduce((a, b) a b, 0) console.log(result) process.exit() // 请注意必须在出口点处加入此行 Ruby代码
a, b gets.split.map(:to_i) print ab PHP代码
?php $input trim(file_get_contents(php://stdin)); list($a, $b) explode( , $input); echo $a $b; Rust代码
use std::io;
fn main(){ let mut inputString::new(); io::stdin().read_line(mut input).unwrap(); let mut sinput.trim().split( ); let a:i32s.next().unwrap() .parse().unwrap(); let b:i32s.next().unwrap() .parse().unwrap(); println!({},ab); } Go代码
package main
import fmt
func main() { var a, b int fmt.Scanf(%d%d, a, b) fmt.Println(ab) } C# Mono代码
using System;
public class APlusB{ private static void Main(){ string[] input Console.ReadLine().Split( ); Console.WriteLine(int.Parse(input[0]) int.Parse(input[1])); } } Visual Basic Mono代码
Imports System
Module APlusB Sub Main() Dim ins As String() Console.ReadLine().Split(New Char(){ c}) Console.WriteLine(Int(ins(0))Int(ins(1))) End Sub End Module Kotlin代码
fun main(args: ArrayString) { val (a, b) readLine()!!.split( ).map(String::toInt) println(a b) } Haskell代码
main do [a, b] - (map read . words) fmap getLine print (ab) Scala代码
object Main extends App { println(scala.io.StdIn.readLine().split( ).map(_.toInt).sum) } Perl代码
my $in STDIN; chomp $in; $in [split /[\s,]/, $in]; my $c $in-[0] $in-[1]; print $c\n; FoxPro代码
use replace all c with ab
作者封禁用户 链接https://www.acwing.com/solution/content/69403/ 来源AcWing 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
