网站开发建设价格,曲周县建设局网站,庆阳网约车,工作计划怎么写文章目录 A题目AC Code#xff1a; B题目AC Code#xff1a; C题目AC Code#xff1a; D题目AC Code#xff1a; E题目思路做法时间复杂度AC Code#xff1a; F题目思路AC Code#xff1a; A
题目
模拟即可#xff0c;会循环都能写。
AC Code#xff1a;
#include … 文章目录 A题目AC Code B题目AC Code C题目AC Code D题目AC Code E题目思路做法时间复杂度AC Code F题目思路AC Code A
题目
模拟即可会循环都能写。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
int a, b, d;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin a b d;for (int i a; i b; i d) cout i ;return 0;
}B
题目
这个也是根据题面模拟存一下序列的长度即可。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
int q, a[100100];
int n;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin q;while (q --) {int op, x;cin op x;if (op 1) {n;a[n] x;}else {cout a[n - x 1] \n;}}return 0;
}C
题目
可以用递归加优化来完成此题。我们让 f ( x ) f(x) f(x) 表示要擦除 x x x 和擦除它产生的数的代价。然后得到 f ( x ) f ( x / 2 ) f ( x − x / 2 ) x f(x) f(x/2) f(x - x / 2) x f(x)f(x/2)f(x−x/2)x
然后为了避免重复计算用 map 存储 f ( x ) f(x) f(x) 的值。如果这个答案没有被计算就计算这个答案否则直接返回之前存储的答案。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
long long n;
maplong long, long long m;
long long f(long long x) {if (x 2) return 0;if (!m[x]) {if (x % 2) {long long tmp1 f(x / 2), tmp2 f(x - x / 2);m[x] tmp1 tmp2 x;}else {long long tmp f(x / 2);m[x] tmp tmp x;}}return m[x];
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;cout f(n);return 0;
}D
题目
把游戏抽象化为一个图每一个阶段就是一个点那么连接 i i i 和 i 1 i 1 i1 的边的权值就是 A i A_i Ai连接 i i i 和 X i X_i Xi 的边的权值就是 B i B_i Bi然后跑一遍最短路即可。如果没有负权边就不要用 SPFA容易被卡。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
int n, a[200100], b[200100], x[200100];
struct edge{int u, v, w, nxt;
};
edge ed[400100];
int edcnt, head[200100];
void addedge(int u, int v, int w){edcnt;ed[edcnt].u u;ed[edcnt].v v;ed[edcnt].w w;ed[edcnt].nxt head[u];head[u] edcnt;
}
long long dis[200100];
struct node {int x;long long dis;node(int x_, long long dis_) {x x_;dis dis_;}
};
bool operator (node a, node b) {return a.dis b.dis;
}
bool vis[514114];
void dijkstra() {priority_queuenode pq;pq.push(node(1, 0));while (!pq.empty()) {int now pq.top().x;pq.pop();if (vis[now]) {continue;}if (now n) break;vis[now] 1;for (int j head[now]; j; j ed[j].nxt) {int v ed[j].v;if (dis[v] dis[now] ed[j].w) {dis[v] dis[now] ed[j].w;pq.push(node(v, dis[v]));}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;for (int i 1; i n; i ) {cin a[i] b[i] x[i];addedge(i, i 1, a[i]);addedge(i, x[i], b[i]);}memset(dis, 0x3f, sizeof(dis));dis[1] 0;dijkstra();cout dis[n];return 0;
}E
题目
思路
我们发现如果序列头尾相连那么我们每次要放的都是一个连续的区间可以看题目的 GIF 图自行理解。那么这个题就是区间修改单点查询一个典型的线段树或树状数组维护差分数组我用的线段树。
做法
首先如果我们的球数大于等于 n n n那么就可以先放 k n kn kn 个球将每一个盒子都放 k k k 个对于剩下不足 n n n 个球设有 p p p 个球如果往后 p p p 个盒子没有超过 n n n就把后 p p p 个盒子每一个盒子放一个球否则一直放到第 n n n 个盒子再从第一个盒子开始放完剩下的球。
时间复杂度 O ( n log 2 ( n ) ) O(n\log_2(n)) O(nlog2(n))合格。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
long long n, m, a[200100], b[200100];
struct node{long long l, r;long long sum;
};
node t[1600100];
long long maketree(long long l, long long r, long long p) {t[p].l l;t[p].r r;if (l r) {t[p].sum maketree(l, (l r) / 2, p * 2);t[p].sum maketree((l r) / 2 1, r, p * 2 1);}else {if (l) t[p].sum a[l] - a[l - 1];else t[p].sum 0;}return t[p].sum;
}
void add(long long i, long long k, long long p) {if (t[p].l i t[p].r i) t[p].sum k;else return;add(i, k, p * 2);add(i, k, p * 2 1);
}
long long get(long long l, long long r, long long p) {if (l t[p].l t[p].r r) return t[p].sum;if (l t[p].r || t[p].l r) return 0;return get(l, r, p * 2) get(l, r, p * 2 1);
}
void add1(long long l, long long r, long long k) {add(l, k, 1);if (r 1 n) add(r 1, -k, 1);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n m;for (long long i 1; i n; i) cin a[i];for (long long i 1; i m; i) cin b[i];for (long long i 1; i m; i) b[i];maketree(1, n, 1);for (long long i 1; i m; i ) {long long tmp get(1, b[i], 1);add1(b[i], b[i], -tmp);long long tmp1 tmp / n;add1(1, n, tmp1);long long tmp2 tmp % n;if (tmp2 n - b[i]) {add1(b[i] 1, n, 1);add1(1, tmp2 - (n - b[i]), 1);}else {add1(b[i] 1, b[i] tmp2, 1);}}for (long long i 1; i n; i ) {cout get(1, i, 1) ;}cout \n;return 0;
}F
题目
如果你知道了以 ( 0 , 0 ) , ( A , B ) , ( C , D ) (0, 0), (A, B), (C, D) (0,0),(A,B),(C,D) 为顶点的三角形的面积为 ∣ A D − B C ∣ 2 \frac{|AD - BC|}{2} 2∣AD−BC∣那么这个问题就很好解决了。
思路
题目给定了 X , Y X,Y X,Y然后吧唧吧唧一大堆就是想让我们求出一个 A , B A, B A,B使得 ∣ A Y − B X ∣ 2 \frac{|AY-BX|}{2} 2∣AY−BX∣ 为 1 1 1转换一下就是 ∣ A Y ( − B ) X ∣ 1 |AY(-B)X| 1 ∣AY(−B)X∣1这不就是典型的扩展欧几里得吗
我们设 g g g 为 gcd ( X , Y ) \gcd(X, Y) gcd(X,Y)如果 g ≥ 3 g \ge 3 g≥3 那么说明无解因为当 A X B Y gcd ( A , B ) AX BY \gcd(A,B) AXBYgcd(A,B) 时该方程才有解。将 − Y , X -Y, X −Y,X 带入上述方程求出 A , B A, B A,B将 A , B A, B A,B 分别乘上 2 g \frac2g g2 就可以得到正确的答案。因为我们要求 A X B Y 2 AX BY 2 AXBY2而现在是 A X B Y g AX BY g AXBYg左右两边同时乘上 2 g \frac2g g2 即可。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
long long x, y;
long long e_gcd(long long a, long long b, long long x, long long y) {if (!b) {x 1ll;y 0ll;return a;}long long gcd e_gcd(b, a % b, y, x);y - a / b * x;return gcd;
}
long long a, b;
long long gcd(long long x, long long y) {if (y 0ll) return x;return gcd(y, x % y);
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin x y; long long g gcd(x, y);e_gcd(y, -x, a, b);if (abs(g) 3ll) {cout -1ll;return 0;}a * 2ll / g, b * 2ll / g;cout a b;return 0;
}
