A Many Formulas
思路:二进制枚举
void solve() {
string s;
cin >> s;
int n = s.size();
int m = pow(2, n - 1);
int ans = 0;
for (int i = 0; i < m; ++i) {
int now = 0, sum = 0;
for (int j = 0; j < n; ++j) {
now = now * 10 + (s[j] - '0');
if ((i >> j) & 1) {
sum += now;
now = 0;
}
}
sum += now;
ans += sum;
}
cout << ans;
}
B Tak and Cards
思路:将数分为大于A和小于A的两部分,只去与A的差值,分别对两部分用背包求和的个数,统计答案即可
void print(__int128 num)
{
if(num>9)
print(num/10);
putchar(num%10+'0');
}
void solve() {
int n, a;
cin >> n >> a;
vector<int> b(n + 1);
vector<int> x, y;
__int128 cnt = 0;
for (int i = 1; i <= n; ++i) {
cin >> b[i];
int c = abs(b[i] - a);
if (b[i] < a) x.push_back(c);
else if (b[i] > a) y.push_back(c);
else cnt ++;
}
cnt = pow(2, (int)cnt);
int nx = x.size(), ny = y.size();
int m = 2500;
vector<__int128> fx(m + 5);
vector<__int128> fy(m + 5);
fx[0] = fy[0] = 1;
for (int i = 0; i < nx; ++i) {
for (int j = m; j >= x[i]; --j) {
fx[j] = fx[j] + fx[j - x[i]];
}
}
for (int i = 0; i < ny; ++i) {
for (int j = m; j >= y[i]; --j) {
fy[j] = fy[j] + fy[j - y[i]];
}
}
__int128 ans = 0;
for (int i = 1; i <= m; ++i) {
ans += (fx[i] * fy[i] * cnt);
}
ans += cnt - 1;
print(ans);
}
C Wall
思路:floyd求最短路
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int> > g(10, vector<int> (10));
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
cin >> g[i][j];
}
}
for (int k = 0; k < 10; ++k) {
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int x;
cin >> x;
if (x != -1) {
ans += g[x][1];
}
}
}
cout << ans;
}
D Coloring Edges on Tree
思路:最大的颜色数为最大度数,首先标记度最大的点的边,bfs继续标记每条表,跳过已经标记过得颜色
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 1e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;
struct E {
int x, y;
};
void solve() {
int n;
cin >> n;
vector<E> g(n - 1);
vector<int> st(n + 1), d(n + 1);
vector<vector<int> > ve(n + 1);
map<PII, int> mp;
int ma = -1, p;
for (int i = 0; i < n - 1; ++i) {
cin >> g[i].x >> g[i].y;
mp[{g[i].x, g[i].y}] = -1;
ve[g[i].x].push_back(g[i].y), ve[g[i].y].push_back(g[i].x);
d[g[i].x] ++, d[g[i].y] ++;
if (d[g[i].x] > ma) {
ma = d[g[i].x], p = g[i].x;
}
if (d[g[i].y] > ma) {
ma = d[g[i].y], p = g[i].y;
}
}
vector<int> col(n - 1);
queue<int> q;
// cout << p << '\n';
st[p] = 1e9;
q.push(p);
while (q.size()) {
auto t = q.front();
q.pop();
int idx = 1;
for (auto v:ve[t]) {
if (st[v]) continue;
if (idx == st[t]) idx ++;
mp[{t, v}] = mp[{v, t}] = idx;
st[v] = idx ++;
q.push(v);
}
}
cout << ma << '\n';
for (int i = 0; i < n - 1; ++i) {
cout << mp[{g[i].x, g[i].y}] << '\n';
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
E Fault-tolerant Network
思路:实际上就是要将a1、an、b1、bn都连上边,求出与它们差最小的数,分别考虑每种连接情况
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <climits>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 1e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0,1, 0, -1};
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
int ans = LLONG_MAX;
int x1, x2, x3, x4;
x1 = x2 = x3 = x4 = LLONG_MAX;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) {
cin >> b[i];
x1 = min(x1, abs(a[1] - b[i]));
x2 = min(x2, abs(a[n] - b[i]));
}
for (int i = 1; i <= n; ++i) {
x3 = min(x3, abs(b[1] - a[i]));
x4 = min(x4, abs(b[n] - a[i]));
}
ans = min(ans, abs(a[1] - b[1]) + abs(a[n] - b[n]));
ans = min(ans, abs(a[1] - b[n]) + abs(a[n] - b[1]));
ans = min(ans, abs(a[1] - b[1]) + x2 + x4);
ans = min(ans, abs(a[1] - b[n]) + x2 + x3);
ans = min(ans, abs(a[n] - b[1]) + x1 + x4);
ans = min(ans, abs(a[n] - b[n]) + x1 + x3);
ans = min(ans, x1 + x2 + x3 + x4);
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
F Nearest Excluded Points
思路:
点数不多,若距离一个点为1的位置不存在点,说明该位置可以为该点的答案,考虑用已经标记过答案的点去bfs没有标记过的点,更新答案
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <climits>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 1e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0,1, 0, -1};
struct E {
int x, y;
};
void solve() {
int n;
cin >> n;
vector<E> ve(n + 1), ans(n + 1, {LLONG_MAX, LLONG_MAX});
map<PII, int> id;
for (int i = 1; i <= n; ++i) {
cin >> ve[i].x >> ve[i].y;
id[{ve[i].x, ve[i].y}] = i;
}
queue<E> q;
for (int i = 1; i <= n; ++i) {
for (int k = 0; k < 4; ++k) {
int x = ve[i].x + dx[k], y = ve[i].y + dy[k];
if (!id.count({x, y})) {
// cout << ve[i].x << ' ' << ve[i].y << "|" << x << ' ' << y << '\n';
ans[i] = {x, y};
q.push({ve[i].x, ve[i].y});
break;
}
}
}
while (q.size()) {
auto [x, y] = q.front();
q.pop();
int fa = id[{x, y}];
int fx = ans[fa].x, fy = ans[fa].y;
for (int k = 0; k < 4; ++k) {
int xx = x + dx[k], yy = y + dy[k];
if (id.count({xx, yy}) && ans[id[{xx, yy}]].x == LLONG_MAX) {
ans[id[{xx, yy}]] = {fx, fy};
q.push({xx, yy});
}
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i].x << ' ' << ans[i].y << '\n';
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
G Vacation Query
思路:
线段树维护0和1的最大连续区间长度,若为修改操作,交换0和1维护的线段树即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 5e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;
#define lc k << 1
#define rc k << 1 | 1
string a;
struct tree {
int l, r;
int ans[2], lmx[2], rmx[2];
int lz;
}tr[N * 4];
void pushup(tree & u, tree ll, tree rr) {
u.ans[0] = max({ll.ans[0], rr.ans[0], ll.rmx[0] + rr.lmx[0]});
u.ans[1] = max({ll.ans[1], rr.ans[1], ll.rmx[1] + rr.lmx[1]});
u.lmx[0] = ll.lmx[0];
if (ll.lmx[0] == ll.r - ll.l + 1) u.lmx[0] += rr.lmx[0];
u.lmx[1] = ll.lmx[1];
if (ll.lmx[1] == ll.r - ll.l + 1) u.lmx[1] += rr.lmx[1];
u.rmx[0] = rr.rmx[0];
if (rr.rmx[0] == rr.r - rr.l + 1) u.rmx[0] += ll.rmx[0];
u.rmx[1] = rr.rmx[1];
if (rr.rmx[1] == rr.r - rr.l + 1) u.rmx[1] += ll.rmx[1];
}
void build (int k, int l, int r) {
tr[k] = {l, r};
if (l == r) {
if (a[l] == '0') tr[k].rmx[0] = tr[k].lmx[0] = tr[k].ans[0] = 1;
else tr[k].rmx[1] = tr[k].lmx[1] = tr[k].ans[1] = 1;
return ;
}
int mid = l + r >> 1;
build (lc, l, mid), build(rc, mid + 1, r);
pushup(tr[k], tr[lc], tr[rc]);
}
void swap_(int k) {
swap(tr[k].ans[0], tr[k].ans[1]);
swap(tr[k].lmx[0], tr[k].lmx[1]);
swap(tr[k].rmx[0], tr[k].rmx[1]);
}
void pushdown(int k) {
if (tr[k].lz) {
swap_(lc), swap_(rc);
tr[lc].lz ^= 1;
tr[rc].lz ^= 1;
tr[k].lz ^= 1;
}
}
void modify(int k, int l, int r) {
if (tr[k].l >= l && tr[k].r <= r) {
swap_(k);
tr[k].lz ^= 1;
return ;
}
pushdown(k);
int mid = tr[k].l + tr[k].r >> 1;
if (l <= mid) modify(lc, l, r);
if (r > mid) modify(rc, l, r);
pushup(tr[k], tr[lc], tr[rc]);
}
tree query(int k, int l, int r) {
if (tr[k].l >= l && tr[k].r <= r) return tr[k];
pushdown(k);
int mid = tr[k].l + tr[k].r >> 1;
if (mid >= r) return query(lc, l, r);
if (mid < l) return query(rc, l, r);
tree T;
pushup(T, query(lc, l, mid), query(rc, mid + 1, r));
return T;
}
void solve() {
int n, q;
cin >> n >> q;
cin >> a;
a = ' ' + a;
build(1, 1, n);
while (q --) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
modify(1, l, r);
} else {
cout << query(1, l, r).ans[1] << '\n';
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
标签:Summer,++,SMU,tr,2024,int,vector,include,void From: https://www.cnblogs.com/bible-/p/18316850