voidquick_sort(int q[], int l, int r) { if (l >= r) return ; int x = q[l + r >> 1], i = l - 1, j = r + 1; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); quick_sort(q, 0, n - 1); for (int i = 0; i < n; i ++ ) printf("%d ", q[i]); return0; }
# 输入a, b, m,输出m是否能用a, b凑出来 defdfs(a, b, m): if m == 0: returnTrue if m >= a and dfs(a, b, m - a): returnTrue if m >= b and dfs(a, b, m - b): returnTrue
returnFalse
print('a', 'b','m') whileTrue: a, b = map(int, input().split())
ifnot a andnot b: break
res = 0 for m inrange(1, 1000 + 1): ifnot dfs(a, b, m): res = m print(a, b, res)
for i inrange(1, n + 1): for j inrange(1, m + 1): if i == 1and j == 1: f[i][j][1][w[1][1]] = 1 f[i][j][0][0] = 1 for u inrange(0, k + 1): for v inrange(0, 13 + 1): val = f[i][j][u][v] # ! val = (val + f[i - 1][j][u][v]) % mod val = (val + f[i][j - 1][u][v]) % mod if u > 0and w[i][j] == v: for c inrange(0, v): val = (val + f[i - 1][j][u - 1][c]) % mod val = (val + f[i][j - 1][u - 1][c]) % mod f[i][j][u][v] = val # ! 我们可以搞一个延迟更新的“手动引用”,反正在最后改掉了那个位置
高级数据结构
树状数组
在 的时间内
给某个位置上的数加上一个数(单点修改)
快速求前缀和(区间查询)
单点修改、区间查询是树状数组最常用的情况
树状数组与前缀和数组最大的区别在于其支持修改(在线算法)
树状数组的形态:
在二进制表示下的后缀0段长度为k,则位于第k层。
每个 存储原数组中 段的和。
三个基本操作:
lowbit(x):计算 在二进制下末位1所代表的数值
1 2 3 4 5
// cpp version intlowbit(int x) { return x & -x; }
1 2 3
# python version deflowbit(x): return x & -x
add(x, v):欲单点修改原数组中的某一个数时,对树状数组的修改
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// cpp version1 voidadd(int x, int v) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += v; }
// cpp version2 voidadd(int x, int v) { while (x <= n) { tr[x] += v; x += lowbit(x) } }
1 2 3 4 5 6 7 8 9 10 11 12
# python version1 defadd(x, v): i = x while i <= n: tr[i] += v i += lowbit(i)
# python version2 defadd(x, v): while x <= n: tr[x] += v x += lowbit(x)
query(x):查询 段的和( 前缀和)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// cpp version1 intquery(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; }
// cpp version2 intquery(int x) { int res = 0; while (x) { res += tr[x]; x -= lowbit(x); } return res; }
voidquickSort(int q[],int l,int r){ if (l>=r) return ;
int x=q[(l+r)>>1],i=l-1,j=r+1; while (i<j){ while (q[++i]<x); while (q[--j]>x); if(i<j) swap(q[i],q[j]); } quickSort(q,l,j); quickSort(q,j+1,r); } intmain(){ scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&q[i]);
quickSort(q,0,n-1);
for (int i=0;i<n;i++) printf("%d ",q[i]); return0; }
voidmerge_sort(int q[],int l,int r){ if (l>=r) return ;
int mid=l+r>>1; merge_sort(q,l,mid); merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1; while (i<=mid && j<=r) if(q[i]<q[j]) tmp[k++]=q[i++]; else tmp[k++]=q[j++]; while (i<=mid) tmp[k++]=q[i++]; while (j<=r) tmp[k++]=q[j++];
for (i=l,k=0;i<=r;i++,k++) q[i]=tmp[k]; }
intmain(){ scanf("%d", &n); for (int i=0;i<n;i++) scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for (int i=0;i<n;i++) printf("%d ",q[i]); return0; }
#include<iostream> usingnamespace std; using ll=longlong;
constint N=100005;
int n; ll rst; int q[N],tmp[N];
voidmerge_sort(int q[],int l,int r){ if (l>=r) return ;
int mid=l+r>>1; merge_sort(q,l,mid); merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1; while (i<=mid && j<=r) if (q[i]<=q[j]) tmp[k++]=q[i++]; else{ tmp[k++]=q[j++]; rst+=(mid-i+1); } while (i<=mid) tmp[k++]=q[i++]; while (j<=r) tmp[k++]=q[j++];
for (i=l,k=0;i<=r;i++,k++) q[i]=tmp[k]; }
intmain(){ scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&q[i]);
intmain(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
while (m --){ int x; scanf("%d", &x);
int l = 0,r = n-1; while (l < r){ int mid = l + r >> 1; if (q[mid] >= x) r = mid; else l = mid + 1; } if (q[l] != x) cout << "-1 -1" << endl; else{ cout << l << ' ';
int l = 0, r = n - 1; while (l < r){ int mid = l + r + 1 >> 1; if (q[mid] <= x) l = mid; else r = mid - 1; }
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 % 10); t /= 10; }
if (t) C.push_back(t); return C; }
intmain(){ string a, b; cin >> a >> b;
vector<int> A, B; for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
auto C = add(A, B); for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
vector<int> A, B; for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
if (cmp(A, B)){ auto C = sub(A, B); for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]); } else{ auto C = sub(B, A); printf("-"); for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]); } return0; }
vector<int> div(vector<int> &A, int b, int &r){ vector<int> C;
r = 0; for (int i = A.size() - 1; i >= 0; i --){ // for (int i = A.size() - 1, r = 0; i >= 0; i --){ // ERROR r = r * 10 + A[i]; C.push_back(r / b); r %= b; }
intmain(){ scanf("%d%d%d", &n, &m, &x); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]); for (int i = n -1 , j = 0; i >= 0; i -- ){ while (a[i] + b[j] < x) j ++ ; if (a[i] + b[j] == x){ printf("%d %d", i, j); break; } } return0; }
intfind(int x){ int l = 0, r = all_index.size() - 1; while (l < r){ int mid = l + r >> 1; if (all_index[mid] >= x) r = mid; else l = mid + 1; } return r + 1; }
vector<int>::iterator my_unique(vector<int> &a){ int j = 0; for (int i = 0; i < a.size(); i ++ ) if (!i || a[i] != a[i - 1]) // 遍历至 首个元素 或 与前一个元素不同 的元素(选出每个相同段的第一个元素) a[j ++ ] = a[i]; return a.begin() + j; }
intmain(){ cin >> n >> m; for (int i = 0; i < n; i ++ ){ int x, c; cin >> x >> c; add.push_back({x, c}); all_index.push_back(x); } for (int i = 0; i < m; i ++ ){ int l, r; cin >> l >> r; query.push_back({l, r}); all_index.push_back(l); all_index.push_back(r); } sort(all_index.begin(), all_index.end()); all_index.erase(my_unique(all_index), all_index.end()); for (auto item : add){ int x = find(item.first); a[x] += item.second; } for (int i = 1; i <= all_index.size(); i ++ ) s[i] += s[i - 1] + a[i]; for (auto item : query){ int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return0; }
int st = -INF, ed = -INF; for (auto seg : segs){ if (ed < seg.first){ if (st != -INF) res.push_back({st, ed}); // 若淘汰下来的区间不是初始区间则将其加入res st = seg.first, ed = seg.second; } else ed = max(ed, seg.second); }
if (st != -INF) res.push_back({st, ed});
segs = res; }
intmain(){ cin >> n; for (int i = 0; i < n; i ++ ){ int l, r; cin >> l >> r; segs.push_back({l, r}); }
voideval(){ auto b = num.top(); num.pop(); auto a = num.top(); num.pop(); auto c = op.top(); op.pop(); int x; if (c == '+') x = a + b; elseif (c == '-') x = a - b; elseif (c == '*') x = a * b; elseif (c == '/') x = a / b; num.push(x); }
intmain(){ unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; string str; cin >> str; for (int i = 0; i < str.size(); i ++ ) { auto ch = str[i]; if (isdigit(ch)) { int x = 0, j = i; while (isdigit(str[j]) && j < str.size()) x = x * 10 + str[j ++ ] - '0'; i = j - 1; num.push(x); } elseif (ch == '(') op.push(ch); elseif (ch == ')') { while (op.top() != '(') eval(); op.pop(); } else { // while (op.top() != '(' && pr[op.top()] >= pr[ch] && op.size()) eval(); // ERROR while (op.size() && op.top() != '(' && pr[op.top()] >= pr[ch]) eval(); // 还“有”运算符(很关键!),这个运算符不是左括号,然后它的优先级比我高,那就先把它的子树算完 op.push(ch); } } while (op.size()) eval(); cout << num.top() << endl; return0; }
intmain(){ scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < n; i ++ ){ if (!q.empty() && q.front() < i - k + 1) q.pop_front(); while (!q.empty() && a[q.back()] >= a[i]) q.pop_back(); q.push_back(i); if (i >= k - 1) printf("%d ", a[q.front()]); // 当原窗口终点到达起始状态时开始 } puts(""); q = deque<int>(); for (int i = 0; i < n; i ++ ){ if (!q.empty() && q.front() < i - k + 1) q.pop_front(); while (!q.empty() && a[q.back()] <= a[i]) q.pop_back(); q.push_back(i); if (i >= k - 1) printf("%d ", a[q.front()]); } puts(""); return0; }
voidinsert(int x){ int p = 0; for (int i = 30; i >= 0; i -- ) { int u = x >> i & 1; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } }
intquery(int x){ int p = 0, res = 0; for (int i = 30; i >= 0; i -- ) { int u = x >> i & 1; if (son[p][!u]) { res += 1 << i; p = son[p][!u]; } else { res += 0 << i; p = son[p][u]; } } return res; }
intmain(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ) { scanf("%d", &a[i]); insert(a[i]); } int res = 0; for (int i = 0; i < n; i ++ ) res = max(res, query(a[i])); printf("%d", res); return0; }
int n; int h[N], hk[N], kh[N], sz; // hk:堆下标映射到输入下标 kh:输入下标映射到堆下标
voidheap_swap(int a, int b){ swap(kh[hk[a]],kh[hk[b]]), swap(hk[a], hk[b]); // swap(hk[a],hk[b]), swap(kh[hk[a]], kh[hk[b]]); // 先改哪个都行 swap(h[a], h[b]); }
voiddown(int u){ int t = u; if (2 * u <= sz && h[2 * u] < h[t]) t = 2 * u; if (2 * u + 1 <= sz && h[2 * u + 1] < h[t]) t = 2 * u + 1; if (u != t) { heap_swap(u, t); down(t); } }
voidup(int u){ while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u /= 2; } }
intmain(){ int x, y, z; memset(&x, 0, sizeof x); for (int i = 31; i >= 0; i -- ) cout << (x >> i & 1); cout << ' ' << x << endl; memset(&y, -1, sizeof y); for (int i = 31; i >= 0; i -- ) cout << (y >> i & 1); cout << ' ' << y << endl; memset(&z, 0x3f, sizeof z); for (int i = 31; i >= 0; i -- ) cout << (z >> i & 1); cout << ' ' << z << endl; return0; }
int n; int h[N], e[M], ne[M], idx; bool st[N]; int ans = N;
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
intdfs(int u){ st[u] = true; int sz = 1, mxsz = 0; // size:以结点u为根的子树规模 mxsz:删除结点u后所得连通块规模的最大值 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { int s = dfs(j); // s:u子树的规模 mxsz = max(mxsz, s); sz += s; } } mxsz = max(mxsz, n - sz); ans = min(ans, mxsz); return sz; }
intmain(){ memset(h, -1, sizeof h); cin >> n; for (int i = 0; i < n - 1; i ++ ) { int a, b; cin >> a >> b; add(a, b); add(b, a); } dfs(1); cout << ans << endl; return0; }
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
intbfs(){ memset(d, -1, sizeof d); q[ ++ tt] = 1; d[1] = 0; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] == -1) { d[j] = d[t] + 1; q[ ++ tt] = j; } } } return d[n]; }
intmain(){ memset(h, -1, sizeof h); cin >> n >> m; for (int i = 0; i < m; i ++ ) { int a, b; cin >> a >> b; add(a, b); } cout << bfs() << endl; return0; }
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
intbfs(){ memset(d, -1, sizeof d); q.push(1); d[1] = 0; while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] == -1) { d[j] = d[t] + 1; q.push(j); } } } return d[n]; }
intmain(){ memset(h, -1, sizeof h); cin >> n >> m; for (int i = 0; i < m; i ++ ) { int a, b; cin >> a >> b; add(a, b); } cout << bfs() << endl; return0; }
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
booltopsort(){ for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if ( -- d[j] == 0) q[ ++ tt] =j; } } return tt == n - 1; }
intmain(){ scanf("%d%d", &n, &m); memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b); d[b] ++ ; } if (topsort()) for (int i = 0; i < n; i ++ ) printf("%d ", q[i]); elseputs("-1"); return0; }
intdijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int u = -1; // 其实和手算一样,第一个选取的一定是点1,随后也是选取距起始点最小的点。同样地,最后一个点不需要更新。 // 遍历找最近点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (u == -1 || dist[u] > dist[j])) u = j; st[u] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[u] + g[u][j]); } if (dist[n] == INF) return-1; return dist[n]; }
intmain(){ memset(g, 0x3f, sizeof g); scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a][b] = min(g[a][b], c); } int t = dijkstra(); printf("%d\n", t); return0; }
int n, m; int h[N], e[N], w[N], ne[N], idx; // w[i]:e[i]到其对应head的距离 int dist[N]; priority_queue<PII, vector<PII>, greater<PII>> heap; // pair先按first排序后按second排序 bool st[N];
voidadd(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; }
// 堆优化dijkstra,和手算思路很符合 intdijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; heap.push({0, 1}); // 选取点1起始 while (heap.size()) { // 直接取最近点 auto t = heap.top(); heap.pop(); // t:距起始点最近的点 int ver = t.second, distance = t.first; // ver: vertex distance:起始点到下标ver点的距离 if (st[ver]) continue; // 跳过已加入st的点 st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { // 依次更新t的后继结点距st的距离,并将这些后继结点加入最小堆 int j = e[i]; // j:下标为i的结点所存点的号 if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; // w[i]:下标为i的结点所存点到其前趋——下标ver点的距离(图中) heap.push({dist[j], j}); } } } if (dist[n] == INF) return-1; return dist[n]; }
intmain(){ memset(h, -1, sizeof h); scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } int res = dijkstra(); printf("%d\n", res); return0; }
intbellman_ford(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i ++ ) { memcpy(backup, dist, sizeof dist); for (int j = 0; j < m; j ++ ) { auto t = edges[j]; dist[t.b] = min(dist[t.b], backup[t.a] + t.c); // 松弛操作 } } if (dist[n] > INF / 2) return INF; // INF减去一些数也是INF,这里是对C++实现的一种解决方法,INF更精确的下界可以设为INF - k * 10000:从INF走了k步权值为-10000所得距离仍应是INF。另外,此前无负权边使用dijkstra算法时使用-1来代表不可达,这只是一个标记而已,在有赋权边时距离有可能为-1,不能再将其作为标记,因此可以选INF return dist[n]; }
intmain(){ scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); edges[i] = {a, b, c}; } int res = bellman_ford(); if (res == INF) puts("impossible"); elseprintf("%d\n", res); return0; }
int n, m; int h[N], e[N], w[N], ne[N], idx; int dist[N]; bool st[N];
voidadd(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; }
intspfa(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; // highlight for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]){ dist[j] = dist[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } } } return dist[n]; }
intmain(){ memset(h, -1, sizeof h); scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } int res = spfa(); if (res == INF) puts("impossible"); elseprintf("%d\n", res); return0; }
int n, m; int h[N], e[N], w[N], ne[N], idx; int dist[N], cnt[N]; bool st[N];
voidadd(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; }
boolspfa(){ // memset(dist, 0x3f, sizeof dist); // highlight 小明考了第一,就算是全班同学都减100分,小明和其他同学的相对值仍不变。同理dist的值不再重要,所以只要初始化为同一个值就即可。 queue<int> q; for (int i = 1; i <= n; i ++ ) { q.push(i); st[i] = true; } while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) returntrue; if (!st[j]) { q.push(j); st[j] = true; } } } } returnfalse; }
intmain(){ memset(h, -1, sizeof h); scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } if (spfa()) puts("Yes"); elseputs("No"); return0; }
voidfloyd(){ 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]); // dp公式,先背下来吧 }
intmain(){ scanf("%d%d%d", &n, &m, &Q); for (int i = 1;i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); d[a][b] = min(d[a][b], c); } floyd(); while (Q -- ) { int a, b; scanf("%d%d", &a, &b); if (d[a][b] > INF /2) puts("impossible"); elseprintf("%d\n", d[a][b]); } return0; }
intprim(){ memset(dist, 0x3f, sizeof dist); int res = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j; // if (i) // if (dist[t] == INF) return INF; // else res += dist[t]; // 这样确实好看 if (i && dist[t] == INF) return INF; if (i) res += dist[t];
intmain(){ scanf("%d%d", &n, &m); memset(g, 0x3f, sizeof g); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a][b] = g[b][a] = min(g[a][b], c); } int res = prim(); if (res == INF) puts("impossible"); elseprintf("%d\n", res); return0; }
constint N = 100010, M = 200010, INF = 0x3f3f3f3f;
structEdge{ int a, b, w; booloperator < (Edge &e) const { return w < e.w; } }edges[M];
int n, m; int p[M];
intfind(int x){ return p[x] == x ? x : p[x] = find(p[x]); }
intkruskal(){ sort(edges, edges + m); for (int i = 1; i <= n; i ++ ) p[i] = i; int res = 0, cnt = 0; for (int i = 0; i < m; i ++ ) { auto e = edges[i]; int aa = find(e.a), bb = find(e.b); if (aa != bb) { p[aa] = bb; res += e.w; cnt ++ ; } } if (cnt < n - 1) return INF; return res; }
intmain(){ scanf("%d%d", &n, &m); for (int i = 0; i <= m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); edges[i] = {a, b, c}; } int res = kruskal(); if (res == INF) puts("impossible"); elseprintf("%d\n", res); return0; }
int n, m; int h[N], e[M], ne[M], idx; int color[N];
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
booldfs(int u, int c){ color[u] = c; for (int i = h[u]; i != -1; i = ne[i] ){ int j = e[i]; if (color[j] == c) returnfalse; // 放这似乎快一点点点 if (!color[j] && !dfs(j, 3 - c)) returnfalse; // highligh! 二值域可以用他们的和作为被减数来实现转换(不太会表达) } returntrue; }
intmain(){ memset(h, -1, sizeof h); scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b); add(b, a); } bool flag = true; for (int i = 1; i <= n; i ++ ) { if (!color[i] && !dfs(i, 1)) { flag =false; break; } } if (flag) puts("Yes"); elseputs("No"); return0; }
int n1, n2, m; int h[N], e[M], ne[M], idx; int match[N]; // match[i]:女生i的对象 bool query[N]; // bool st[N]; // 男生是否询问过女生
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
intfind(int x){ for (int i = h[x]; i != -1; i = ne[i]) { // 遍历男生x的所有可联系女生 int j = e[i]; // 女生的编号j if (!query[j]) { // 如果没询问过 query[j] = true; // 标记为询问,然后去问她 if (!match[j] || find(match[j])){ // 如果女生j没有对象,或者女生j的对象match[j]可以再找一个。 // highlight:query的作用就在这里,递归产生的find栈不会再去询问match[j]自己的对象j match[j] = x; // 那女生j把男生x作为对象 returntrue; // 男生x成功找到对象(在未询问女生中) } } } returnfalse; // 男生x没找着对象(在未询问女生中) }
intmain(){ memset(h, -1, sizeof h); scanf("%d%d%d", &n1, &n2, &m); for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b); } int res = 0; for (int i = 1; i <= n1; i ++ ) { memset(query, false, sizeof query); // 重复使用query,每个男生最初都没有询问过女生 if (find(i)) res ++ ; } printf("%d\n", res); return0; }
voiddivide(int n) { for (int i = 2; i <= n / i; i ++ ) { if (n % i == 0) { int s = 0; while (n % i == 0) n /= i, s ++ ; cout << i << ' ' << s << endl; } } if (n > 1) cout << n << ' ' << 1 << endl; }
vector<int> get_divisors(int n) { vector<int> res; for (int i = 1; i <= n / i; i ++ ) if (n % i == 0) { res.push_back(i); if (i != n / i) res.push_back(n / i); } sort(res.begin(), res.end()); return res; }
intmain() { cin >> n; while (n -- ) { int x; cin >> x; auto ans = get_divisors(x); for (auto i : ans) cout << i << ' '; cout << endl; } return0; }
intmain() { cin >> n; while (n -- ) { int a; cin >> a; for (int i = 2; i <= a / i; i ++ ) while (a % i == 0) { a /= i; alphas[i] ++ ; } if (a > 1) alphas[a] ++ ; } LL res = 1; for (auto a : alphas) res = res * (a.second + 1) % MOD;
intmain() { cin >> n; while (n -- ) { int a; cin >> a; for (int i = 2; i <= a / i; i ++ ) while (a % i == 0) { a /= i; pas[i] ++ ; } if (a > 1) pas[a] ++ ; } LL res = 1; for (auto pa : pas) { LL p = pa.first, b = pa.second; LL term = 1; while (b -- ) term = (1 + p * term) % MOD; // 等比数列和的递归写法:每一大项都可以拆为 1 + 公比 * 小项 res = res * term % MOD; }
intphi(int x) { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1); return res; }
intmain() { scanf("%d", &n); while (n -- ) { int a; scanf("%d", &a); printf("%d\n", phi(a)); } return0; }
LL qmi(int a, int b, int p) { int res = 1; while (b) { if (b & 1) res = (LL)res * a % p; b >>= 1; a = (LL)a * a % p; } return res; }
intmain() { scanf("%d", &n); while (n -- ) { int a, p; scanf("%d%d", &a, &p); if (a % p == 0) puts("impossible"); // 题目已保证p是质数,那么a, p不互质的唯一情况是a, p均含有公因子p,那么此时a % p == 0 elseprintf("%d\n", qmi(a, p - 2, p)); } return0; }
intexgcd(int a, int b, int &x, int &y) { // return b ? gcd(b, a % b) : a; if (b) { int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } else { x = 1, y = 0; return a; } }
intmain() { scanf("%d", &n); while (n -- ) { int a, b; scanf("%d%d", &a, &b); int x, y; exgcd(a, b, x, y); printf("%d %d\n", x, y); } return0; }
intexgcd(int a, int b, int &x, int &y) { if (b) { int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } else { x = 1, y = 0; return a; } }
intmain() { scanf("%d", &n); while (n -- ) { int a, b, m; scanf("%d%d%d", &a, &b, &m); int x, y; int d = exgcd(a, m, x, y); if (b % d) puts("impossible"); elseprintf("%d\n", (LL)x * b / d % m); } return0; }
intgauss() { int c, r; for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) // 找每列绝对值最大的那行 if (fabs(a[i][c]) > fabs(a[t][c])) t = i; if (fabs(a[t][c]) < eps) continue; // 当前列之前的列不需要进行行交换、也不用陪当前列单位化,因为已经被消成0了 for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 遍历(专业名词忘了)下面的行,将当前列消为0 for (int i = r + 1; i < n; i ++ ) if (fabs(a[i][c]) > eps) for (int j = n; j >= c; j -- ) a[i][j] -= a[r][j] * a[i][c]; r ++ ; } if (r < n) { for (int i =r; i < n; i ++ ) if (fabs(a[i][n] > eps)) // 0 0 ... 0 C这种情况 return2; return1; // 0 0 ... 0 0这种情况 } // 自下至上消掉非对角线元素 for (int i = n - 1; i >= 0; i -- ) for (int j = i + 1; j < n; j ++ ) a[i][n] -= a[i][j] * a[j][n]; return0; }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) for (int j = 0; j < n + 1; j ++ ) scanf("%lf", &a[i][j]); int t = gauss(); if (t == 2) puts("No solution"); elseif (t == 1) puts("Infinite group solutions"); elseif (t == 0) { for (int i = 0; i < n; i ++ ) { if (fabs(a[i][n]) < eps) a[i][n] = 0; printf("%.2lf\n", a[i][n]); } } return0; }
intgauss() { int c, r; for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) if (a[i][c]) t = i; if (a[t][c] == 0) continue; for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); for (int i = r + 1; i < n; i ++ ) if (a[i][c]) // 首一,需要消掉本行1后的元素 for (int j = c; j <= n ; j ++ ) a[i][j] ^= a[r][j]; r ++ ; } if (r < n) // 秩小于行数 { for (int i = r; i < n; i ++ ) if (a[i][n]) // 0 0 ... 0 1 return2; return1; } for (int i = n - 1; i >= 0; i -- ) for (int j = i + 1; j < n; j ++ ) a[i][n] ^= a[j][n] & a[i][j]; return0; }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) for (int j = 0; j < n + 1; j ++ ) scanf("%d", &a[i][j]);
int t = gauss(); if (t == 2) puts("No solution"); elseif (t == 1) puts("Multiple sets of solutions"); elseif (t == 0) for (int i = 0; i < n; i ++ ) printf("%d\n", a[i][n]); return0; }
int n; int fact[N], infact[N]; // factorial, inverse element of factorial
// 只要两个10^9相乘就要转LL防止爆int intqmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; k >>= 1; a = (LL)a * a % p; } return res; }
intmain() { scanf("%d", &n); fact[0] = infact[0] = 1; for (int i = 1; i < N; i ++ ) { fact[i] = (LL)fact[i - 1] * i % mod; infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod; } while (n -- ) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod); } return0; }
intqmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; k >>= 1; a = (LL)a * a % p; } return res; }
intC(int a, int b, int p) { if (b > a) return0; int res = 1; for (int i = b, j = a;i >= 1; i -- , j -- ) { res = (LL)res * j % p; res = (LL)res * qmi(i, p - 2, p) % p; } return res; }
intlucas(LL a, LL b, int p) { if (a < p && b < p) returnC(a, b, p); return (LL)lucas(a / p, b / p, p) * C(a % p, b % p, p) % p; // highlight:这里要递归使用lucas's Theorem以完全分解至p进制! }
intmain() { scanf("%d", &n); while (n -- ) { LL a, b; int p; scanf("%lld%lld%d", &a, &b, &p); printf("%d\n", lucas(a, b, p)); } return0; }
voidget_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } }
intget(int x, int p) { int res = 0; while (x) { res += x / p; x /= p; } return res; }
vector<int> mul(vector<int> &A, int b) { vector<int> res; for (int i = 0, t = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; res.push_back(t % 10); t /= 10; } while (res.back() == 0 && res.size() > 1) res.pop_back(); return res; }
intmain() { int a, b; scanf("%d%d", &a, &b); get_primes(a); for (int i = 0; i < cnt; i ++ ) { int p = primes[i]; sum[i] = get(a, p) - get(b, p) - get(a - b, p); } vector<int> res; res.push_back(1); for (int i = 0; i < cnt; i ++ ) while (sum[i] -- ) // for (int j = 0; j < sum[i]; j ++ ) res = mul(res, primes[i]); for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]); puts(""); return0; }
intqmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; k >>= 1; a = (LL)a * a % p; } return res; }
intmain() { scanf("%d", &n); int a = 2 * n, b = n; int res = 1; for (int i = b, j = a; i >= 1; i --, j -- ) { res = (LL)res * j % mod; res = (LL)res * qmi(i, mod - 2, mod) % mod; } res = (LL)res * qmi(n + 1, mod - 2, mod) % mod; printf("%d\n", res); return0; }
intmain() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) scanf("%d", &p[i]); int res = 0; for (int i = 1; i < 1 << m; i ++ ) // 遍历2 ^ m - 1种状态(除全0,即不选集合) { int t = 1, cnt = 0; // t:选中集合对应质数的积,cnt:选中集合的数量 for (int j = 0; j < m; j ++ ) // 遍历i的每一位二进制数(遍历所有集合的选中状态) if (i >> j & 1) // 若选中集合 { if ((LL)t * p[j] > n) // 若选中集合对应质数的积大于给定整数,说明给定整数中一定没有选中集合对应质数的公倍数。 { t = -1; break; } t *= p[j]; cnt ++ ; } if (t != -1) { if (cnt & 1) res += n / t; // 若选中奇数个集合,自增 else res -= n / t; // 若选中偶数个集合, 自减 } } printf("%d\n", res); return0; }
intmain() { scanf("%d", &n); int res = 0; for (int i = 1; i <= n; i ++ ) { int a; scanf("%d", &a); if (i & 1) res ^= a; } if (res) puts("Yes"); elseputs("No"); return0; }
intsg(int x) { // 记忆化搜索 if (~f[x]) return f[x]; // 遍历x可转移至的所有状态,并将其sg值加入集合 unordered_set<int> set; for (int i = 0; i < m; i ++ ) { int sub = s[i]; if (x >= sub) set.insert(sg(x - sub)); } // 在集合的补集中找到mex(不在集合中的最小数) for (int i = 0; ; i ++ ) if (!set.count(i)) return f[x] = i; // 记忆化搜索 }
intmain() { scanf("%d", &m); for (int i = 0; i < m; i ++ ) scanf("%d", &s[i]); scanf("%d", &n); memset(f, -1, sizeof f); int res = 0; for (int i = 0; i < n; i ++ ) { int a; scanf("%d", &a); res ^= sg(a); } if (res) puts("Yes"); elseputs("No"); return0; }
intsg(int x) { if (~f[x]) return f[x]; unordered_set<int> S; for (int i = 0; i < x; i ++ ) for (int j = 0; j <= i; j ++ ) S.insert(sg(i) ^ sg(j)); for (int i = 0; ; i ++ ) if (!S.count(i)) return f[x] = i; }
intmain() { scanf("%d", &n); memset(f, -1, sizeof f); int res = 0; for (int i = 0; i < n; i ++ ) { int a; scanf("%d", &a); res ^= sg(a); } if (res) puts("Yes"); elseputs("No"); return0; }
intmain() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]); for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) for (int k = 0; k * v[i] <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); printf("%d\n", f[n][m]); return0; }
intmain() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d%d%d", &v[i], &w[i], &s[i]); for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); printf("%d\n", f[n][m]); return0; }
int n, m; int v[N], w[N], cnt; int f[M]; // 注意这里就应该是M,前面是因为N和M同范围
intmain() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int a, b, s; cin >> a >> b >> s; int k = 1; while (k <= s) { cnt ++ ; v[cnt] = k * a, w[cnt] = k * b; s -= k; k <<= 1; } if (s > 0) { cnt ++ ; v[cnt] = s * a, w[cnt] = s * b; } } 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]); cout << f[m] << endl; return0; }
intmain() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) { f[i] = 1; for (int j = 1; j <= i; j ++ ) if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1); } int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, f[i]); printf("%d\n", res); return0; }
intmain() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) { f[i] = 1; for (int j = 1; j <= i; j ++ ) if (a[j] < a[i]) if (f[i] < f[j] + 1) { f[i] = f[j] + 1; g[i] = j; } } int k = 1; for (int i = 1; i <= n; i ++ ) if (f[k] < f[i]) k = i; printf("%d\n", f[k]); for (int i = 0, len = f[k]; i < len; i ++) { printf("%d ", a[k]); k = g[k]; } return0; }
intmin_edit_distance(char a[], char b[]) { memset(f, 0, sizeof f); int la = strlen(a + 1), lb = strlen(b + 1); for (int i = 0; i <= la; i ++ ) f[i][0] = i; for (int j = 0; j <= lb; j ++ ) f[0][j] = j; for (int i = 1; i <= la; i ++ ) for (int j = 1; j <= lb; j ++ ) if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1]; else f[i][j] = 1 + min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])); return f[la][lb]; }
intmain() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%s", str[i] + 1); while (m -- ) { char tar[N]; // target int ub; // upperbound scanf("%s%d", tar + 1, &ub); int res = 0; for (int i = 0; i < n; i ++ ) if (min_edit_distance(str[i], tar) <= ub) res ++ ; printf("%d\n", res); } return0; }
intmain() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]); for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1]; // highlight for (int len = 2; len <= n; len ++ ) for (int i = 1; i + len - 1 <= n; i ++ ) { int l = i, r = i + len - 1; f[l][r] = INF; for (int k = l; k < r; k ++ ) f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); } printf("%d\n", f[1][n]); return0; }
intget_sz(int n) { int res = 0; while (n) { res ++ ; n /= 10; } return res; }
intcount(int n, int x) { int res = 0; int sz = get_sz(n); // 设整数为abc d efg, d为当前遍历到的数,下标为i for (int i = 1; i <= sz; i ++ ) { int p = pow(10, i - 1); // p为efg这几位所能形成的最大值(用来切掉efg段用的) int dl = n / p /10, di = n / p % 10, dr = n % p; // digit_l:切掉efg段得abcd,再切掉1个10进制位得abc // digit_i:切掉efg段得abcd,取最后1个十进制位得成d // digit_r:取efg段得efg // 000 < abc段 <= abc - 1 if (x) res += dl * p; // x != 0,那么abc段遍历000 .. abc-1,efg段遍历000 .. 999,做笛卡尔积得到abc*1000种方案 elseif (!x && dl) res += (dl - 1) * p; // x == 0 且 abc段 != 0,那么abc段遍历001 .. abc-1(没有0000efg这种表示方法),efg段遍历000 .. 999,做笛卡尔积得到(abc - 1) * 1000种方案 // abc段 == abc if (di > x && (x || dl)) res += p; // 第i位数di > x, 那么abc段 = abc, efg段遍历000 .. 999, 做笛卡尔积得到1 * 1000种方案 elseif (di == x && (x || dl)) res += dr + 1; // 第i位数di == x, 那么abc段 = abc,efg段遍历000 .. efg,做笛卡尔积得到1 * (efg + 1)种方案 // 记得限制abc和d不能同时为0 } return res; }
intmain() { while (scanf("%d%d", &a, &b), a || b) { if (a > b) swap(a, b); for (int i = 0; i <= 9; i ++ ) printf("%d ", count(b, i) - count(a - 1, i)); puts(""); } return0; }
int n; int h[N], e[N], ne[N], idx; int has_father[N]; int happy[N]; int f[N][N];
voidadd(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
voiddfs(int u) { f[u][1] = happy[u]; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; dfs(j); f[u][1] += f[j][0]; f[u][0] += max(f[j][0], f[j][1]); } }
intmain() { scanf("%d", &n); memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]); for (int i = 0; i < n - 1; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(b, a); has_father[a] = true; } int root = 1; while (has_father[root]) root ++ ; dfs(root); printf("%d\n", max(f[root][0], f[root][1])); return0; }
intdp(int x ,int y)// 这两个参数其实是行、列 { int& v = f[x][y]; if (~v) return v; v = 1; for (int i = 0; i < 4; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a >= 1 && a <= n && b >= 1 && b <= m && h[x][y] > h[a][b]) // 不知道范围时可以看看下面循环的范围,同一个方向上的新坐标还应在该方向的范围内 v = max(v, dp(a, b) + 1); } return v; }
intmain() { scanf("%d%d", &n, &m); memset(f, -1, sizeof f); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) scanf("%d", &h[i][j]); int res = 0; for (int i = 1; i <= n; i ++ ) // 看这里的范围 for (int j = 1; j <= m; j ++ ) res = max(res, dp(i, j)); printf("%d\n", res); return0; }
int n; structRange { int l, r; booloperator< (const Range &W) const { return r < W.r; } }range[N];
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int a, b; scanf("%d%d", &a, &b); range[i] = {a, b}; } sort(range, range + n); int res = 0; int ed = -INF; // 当前最优区间(右端点被尽可能多的区间包含的区间)的右端点,同时也是最新加的点的坐标 for (int i = 0; i < n; i ++ ) { Range rg = range[i]; if (ed < rg.l) { res ++ ; // 加入一个点 ed = rg.r; // 将该区间选为最优区间,更新最优右端点 } } printf("%d\n", res); return0; }
int n; structRange { int l, r; booloperator< (const Range& W) const { return r < W.r; } }range[N];
intmain() { cin >> n;
for (int i = 0; i < n; i ++ ) { int a, b; cin >> a >> b; range[i] = {a, b}; } sort(range, range + n); int res = 0; int ed = -INF; for (int i = 0; i < n; i ++ ) { if (range[i].l > ed) { res ++ ; ed = range[i].r; } } printf("%d\n", res); return0; }
int n; structRange { int l, r; booloperator< (const Range& W) const { return l < W.l; } }range[N];
intmain() { int st, ed; scanf("%d%d", &st, &ed); scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int l, r; scanf("%d%d", &l, &r); range[i] = {l, r}; } sort(range, range + n); int res = 0; bool success = false; for (int i = 0; i < n; i ++ ) { int j = i, r = -INF; while (j < n && range[j].l <= st) { r = max(r, range[j].r); j ++ ; } if (r < st) break; res ++ ; if (r >= ed) // 只有进入这里才是找到了 { success = true; break; } st = r; i = j - 1; } if (!success) res = -1; printf("%d\n", res); return0; }
int n; priority_queue<int, vector<int>, greater<int>> heap;
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int a; cin >> a; heap.push(a); } int res = 0; while (heap.size() > 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); int c = a + b; res += c; heap.push(c); } printf("%d\n", res); return0; }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); sort(a, a + n); LL res = 0; for (int i = 0; i < n; i ++ ) res += a[i] * (n - i - 1); printf("%lld\n", res); return0; }
intmain() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); sort(a + 1, a + n + 1); LL res = 0; for (int i = 1; i <= n; i ++ ) res += a[i] * (n - i); printf("%lld\n", res); return0; }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); sort(a, a + n); reverse(a, a + n); LL res = 0; for (int i = 0; i < n; i ++ ) res += a[i] * i; // 把要等着i的人放在前面存储,这样表示方便 printf("%lld\n", res); return0; }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); sort(a, a + n); int res = 0; for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]); printf("%d\n", res); return0; }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int w, s; scanf("%d%d", &w, &s); cows[i] = {w + s, s}; } sort(cows, cows + n); int sum = 0, res = -INF; // w前缀和,最大风险值 for (int i = 0; i < n; i ++ ) { auto cow = cows[i]; int s = cow.second, w = cow.first - s; res = max(res, sum - s); sum += w; } printf("%d\n", res); return0; }