AtCoder Beginner Contest 165
https://atcoder.jp/contests/abc165
C - Many Requirements
dfs
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 55;
int n, m, q, ans;
int a[M], b[M], c[M], d[M], A[N];
void dfs (int x) {
if (x > n) {
int sum = 0;
for (int i = 1; i <= q; i++) {
if (A[b[i]] - A[a[i]] == c[i]) sum += d[i];
}
ans = max (ans, sum);
return ;
}
for (int i = A[x - 1]; i <= m; i++) {
A[x] = i;
dfs (x + 1);
A[x] = 0;
}
}
int main () {
cin >> n >> m >> q;
for (int i = 1; i <= q; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
A[0] = 1;
dfs (1);
cout << ans << endl;
}
D - Floor Function
推导:
#include<bits/stdc++.h>
using namespace std;
int main () {
long long a, b, n;
cin >> a >> b >> n;
//for (int i = 1; i <= n; i++) cout << (a * i) / b - a * (i / b) << ' ';
n = min (b - 1, n);
cout << (a * n) / b - a * (n / b);
}
E - Rotation Matching
这题有点看不懂题解。。。
#include<bits/stdc++.h>
using namespace std;
int main () {
int n, m;
cin >> n >> m;
int l = 1, r = m + 1;
for (int i = 0; i < m; i++) {
if (l >= r) l = m + 2, r = 2 * m + 1;
cout << l << ' ' << r << endl;
l++, r--;
}
}
F - LIS on Tree
二分求LIS + 树上dfs 然后回溯
(基础是导弹拦截那题)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = N * 2;
int a[N], ans[N], f[N], n; //f[i]: 长度为i的LIS的结尾最大值
int h[N], e[M], ne[M], idx;
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs (int u, int fa) {
int l = 1, r = ans[fa], lst;
if (fa == 0) ans[1] = 1, f[1] = a[u];
else {
while (l <= r) {
int mid = l + r >> 1;
if (a[u] <= f[mid]) r = mid - 1;
else l = mid + 1;
}
//cout << l << ' ' << r << endl;
lst = f[l], f[l] = a[u], ans[u] = ans[fa];
if (l > ans[fa]) ans[u]++;
}
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs (j, u);
}
f[l] = lst; //回溯
}
int main () {
memset (h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
add (a, b), add (b, a);
}
dfs (1, 0);
for (int i = 1; i <= n; i++) cout << ans[i] << endl;
}
- Beginner AtCoder Contest 165beginner atcoder contest 165 atcoder regular contest 165 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334