A - Count Down
先这样，就这样。
点击查看代码
#include<cstdio>
int n;
int main() {
scanf("%d", &n);
for(int i = n; i >= 0; i--) printf("%d\n", i);
return 0;
}
B - Sandwich Number
好好读题
赛时想复杂了，其实就直接判断两边字母和中间数字就好，注意中间数字是否存在前导零！
点击查看代码
#include<cstdio>
#include<cstring>
int n, tot;
char s[20];
bool check(int l) {
for(int i = l; i < l + 6; i ++) {
if(s[i] > '9' || s[i] < '0' || (i == l && s[i] == '0')) return 0;
}
return 1;
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
if(n != 8 || !check(2)) {
puts("No");
return 0;
}
if(s[1] > 'Z' || s[1] < 'A' || s[8] > 'Z' || s[8] < 'A') {
puts("No");
return 0;
}
puts("Yes");
return 0;
}
C - Circular Playlist
前缀和，取模，然后枚举时间段判断。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, t, a[N];
signed main() {
scanf("%lld %lld", &n, &t);
for(int i = 1; i <= n; i ++) {
scanf("%lld", &a[i]);
a[i] += a[i - 1];
}
t %= a[n];
for(int i = 0; i < n; i ++) {
if(t >= a[i] && t < a[i + 1]) {
printf("%lld %lld\n", i + 1, t - a[i]);
return 0;
}
}
return 0;
}
D - Max Multiple
观察数据范围，发现 n,d,k 都不大，
因此可以直接定义状态 dp[i][j][k] 表示 前 i 位中选了 j 位，所选数的和 取模 d 余 k 时能达到的 d 的最大倍数。
然后直接枚举这三维的状态，转移方程即可。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N = 105;
int n, d, K, a[N], dp[N][N][N];
int get_num(int x, int y) {
return ((x - y) % d + d) % d;
}
signed main() {
scanf("%lld %lld %lld", &n, &K, &d);
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
memset(dp, -1, sizeof(dp));
for(int i = 0; i <= n; i ++) dp[i][0][0] = 0;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= i; j ++) {
for(int k = 0; k < d; k ++) {
int tmp = get_num(k, a[i]);
dp[i][j][k] = dp[i - 1][j][k];
if(dp[i - 1][j - 1][tmp] != -1) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][tmp] + (tmp + a[i]) / d * d);
}
}
}
printf("%lld", dp[n][K][0]);
return 0;
}
E - Least Elements
直接用 vector 模拟平衡树修改查询……
点击查看代码
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m, k, a[N], ans;
vector<int> v;
signed main() {
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int i = 1; i <= m; i ++) v.push_back(a[i]);
sort(v.begin(), v.end());
for(int i = 0; i < k; i ++) ans += v[i];
printf("%lld ", ans);
int x;
for(int i = 2; i <= n - m + 1; i ++) {
bool tag = 0;
auto pos = lower_bound(v.begin(), v.end(), a[i - 1]);
if((pos - v.begin()) < k) ans -= a[i - 1], tag = 1;
v.erase(pos);
x = a[i + m - 1];
pos = lower_bound(v.begin(), v.end(), x);
if(pos - v.begin() < k) {
ans += x;
if(!tag) ans -= v[k - 1];
}
else if(tag) ans += v[k - 1];
v.insert(pos, x);
printf("%lld ", ans);
}
return 0;
}
F - Xor Minimization
先建立 trie 树，然后在树上递归查询。
（u1s1，这种二进制异或题真的 trie 树板树）
点击查看代码
#include<cstdio>
#include<algorithm>
#include<algorithm>
using namespace std;
#define int long long
const int N = 150005;
int n, cnt, a[N], tr[N * 30][2];
void ins(int x) {
int now = 0, v;
for(int i = 29; i >= 0; i --) {
v = x >> i & 1;
if(!tr[now][v]) tr[now][v] = ++cnt;
now = tr[now][v];
}
}
int query(int num, int p) {
if(num == -1) return 0;
if(!tr[p][0]) return query(num - 1, tr[p][1]);
if(!tr[p][1]) return query(num - 1, tr[p][0]);
return (1ll << num) + min(query(num - 1, tr[p][0]), query(num - 1, tr[p][1]));
}
signed main() {
int x;
scanf("%lld", &n);
for(int i = 1; i <= n; i ++) scanf("%lld", &x), ins(x);
printf("%lld", query(29, 0));
return 0;
}