A - Count Down (abc281 a)
题目大意
给定\(n\)，输出 \(n\)到 \(1\)。
解题思路
直接输出即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
cout << n << '\n';
while(n--){
cout << n << '\n';
}
return 0;
}
B - Sandwich Number (abc281 b)
题目大意
给定一个字符串\(s\)，问 \(s\)是否为以下形式的字符串：
- 第一个字符是大写字母
- 第一个字符是大写字母
- 最后一个字符是大写字母
- 中间六位是数字，且范围在 \([100000, 999999]\)
解题思路
直接判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
auto check = [&](){
if (s.size() != 8)
return false;
if (!isupper(s[0]) || !isupper(s[7]))
return false;
int qwq = 0;
for(int i = 1; i <= 6; ++ i){
if (!isdigit(s[i]))
return false;
qwq = qwq * 10 + s[i] - '0';
}
return qwq >= 100000 && qwq <= 999999;
};
if (check())
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
C - Circular Playlist (abc281 c)
题目大意
给定一个包含\(n\)首歌及其播放时间的列表。该列表循环播放。问过了 \(t\)时间后，此时播放到第几首歌了，且这首歌播放了多久。
解题思路
对时间取模即可去掉循环播放的影响，然后直接从头遍历播放到哪首歌即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
LL t;
cin >> n >> t;
vector<LL> a(n);
LL sum = 0;
for(auto &i : a){
cin >> i;
sum += i;
}
t %= sum;
int ans = 0;
while(ans < n){
if (a[ans] <= t){
t -= a[ans];
++ ans;
}else {
break;
}
}
cout << ans + 1 << ' ' << t << endl;
return 0;
}
D - Max Multiple (abc281 d)
题目大意
给定\(n\)个数 \(a_i\)，问从中取 \(k\)个数出来，其和是 \(d\)的倍数，问该和最大是多少。
解题思路
数不大，设\(dp[i][j][k]\)表示从前 \(i\)个数取出 \(j\)个数，其和模 \(d\)的余数是 \(k\)时，和的最大值。
转移的时候考虑第 \(i\)个数选或不选即可。
答案就是\(dp[n][k][0]\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e2 + 8;
const LL inf = 1e18;
LL dp[N][N][N];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k, d;
cin >> n >> k >> d;
for(int i = 0; i < N; ++ i)
for(int j = 0; j < N; ++ j)
for(int k = 0; k < N; ++ k)
dp[i][j][k] = -inf;
dp[0][0][0] = 0;
for(int i = 1; i <= n; ++ i){
LL a;
cin >> a;
LL ba = a;
a %= d;
dp[i][0][0] = 0;
for(int j = 1; j <= i; ++ j)
for(int k = 0; k < d; ++ k){
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][(k - a + d) % d] + ba);
}
}
LL ans = dp[n][k][0];
if (ans < 0)
ans = -1;
cout << ans << '\n';
return 0;
}
E - Least Elements (abc281 e)
题目大意
给定\(n\)个数\(a_i\)，有一个长度为 \(m\)的窗口从左到右滑动。问窗口所在的每一个位置中，其里面的 \(m\)个数的前 \(k\)小的数的和。
解题思路
我们拿一个数据结构维护这前\(k\)小的数。当窗口滑动的时候，这里面有一些数可能因为不在窗口里而被踢掉，而有一些可能因为窗口新加进来的数更小而被踢掉（但被踢掉的数还可能拿回来），因此我们把这个窗口里的\(m\)个数用两个数据结构维护。
第一个数据结构维护这 \(m\)个数中前 \(k\)小的数，而第二个数据结构维护剩下的\(m-k\)个数。
第一个数据结构要求能踢掉指定元素（不在窗口内的），还要查询其最大值（与新加进来的数比较），然后实时保证其元素个数为\(k\)。
而第二个数据结构则仅要求查询其最小值（踢掉的话可以在查的时候看下标是不是合法的）
因此第一个数据结构可以用 \(set\)，第二个就用 \(priority_queue\) （\(set\)也行）
然后模拟该过程即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for(auto &i : a)
cin >> i;
priority_queue<pair<int, int>> val;
set<pair<int, int>> pos;
LL ans = 0;
for(int i = 0; i < m - 1; ++ i){
val.push({-a[i], i});
}
for(int i = m - 1; i < n; ++ i){
int l = i - m + 1;
if (l > 0){
auto it = pos.find({a[l - 1], -(l - 1)});
if (it != pos.end()){
pos.erase(it);
ans -= a[l - 1];
}
}
val.push({-a[i], i});
while(pos.size() < k){
auto tmp = val.top();
if (tmp.second >= l){
pos.insert({-tmp.first, -tmp.second});
ans += -tmp.first;
}
val.pop();
}
while(!val.empty()){
auto tmp = val.top();
if (tmp.second >= l && -tmp.first < pos.rbegin() -> first){
val.pop();
auto it = prev(pos.end());
val.push({-it->first, -it->second});
ans -= it->first;
pos.erase(it);
pos.insert({-tmp.first, -tmp.second});
ans += -tmp.first;
}else if (tmp.second < l)
val.pop();
else
break;
}
cout << ans << ' ';
}
return 0;
}
F - Xor Minimization (abc281 f)
题目大意
给定\(n\)个数\(a_i\)，要求选一个数 \(x\)，使得 \(\max_{1 \leq i \leq n}a_i \oplus x\)最小，问该最小值。
解题思路
异或在二进制下位与位独立，我们依次考虑答案二进制下每一位的取值。
假设当前考虑的是第\(i\)位，如果所有数在这一位上的数字都是一样的，那么\(x\)就可以取相反值，答案在该位就是\(0\)。
否则\(x\)在该位上无论取什么，答案在该位的数字都是 \(1\)，然后再考虑当\(x\)取 \(1\)时，有一些\(a_i\)就不会是最大的（异或后该位变成\(0\)，自然小于变成 \(1\)的那些），就仅考虑剩下那些 \(a_i\)之后的情况，同理当\(x\)取\(0\) 也是。
可以对这些数放到\(0/1\)字典数上，这样就分好类，直接搜就可以了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
const int N = 1.5e5 + 8;
LL ans, tmp;
namespace trie {
const int M = 31;
int ch[N * M][2], sz;
void init() { memset(ch, 0, sizeof ch); sz = 2; }
void ins(LL x) {
int u = 1;
FORD (i, M, -1) {
bool b = x & (1LL << i);
if (!ch[u][b]) ch[u][b] = sz++;
u = ch[u][b];
}
}
LL dfs(int u, int deep){
if (deep < 0){
return 0;
}
if (ch[u][0] && ch[u][1]){
return min(dfs(ch[u][0], deep - 1), dfs(ch[u][1], deep - 1)) | (1ll << deep);
}else if (ch[u][0]){
return dfs(ch[u][0], deep - 1);
}else if (ch[u][1]){
return dfs(ch[u][1], deep - 1);
}else{
assert(0);
}
}
LL solve(){
return dfs(1, 31);
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
trie::init();
for(int i = 1; i <= n; ++ i){
int a;
cin >> a;
trie::ins(a);
}
cout << trie::solve() << '\n';
return 0;
}
G - Farthest City (abc281 g)
题目大意
一个包含\(n\)个点的图，边权为 \(1\)。问有多少张这样的图，满足以下条件：
- \(1\)号点到 \(n\)号点的距离严格大于 \(1\)号点到其他所有点的距离
图与图之间的不同就是存在一对点，在一图有连边，另一图没有。
解题思路
初次看此题感觉确实难以入手，主要没想到什么好的着手点，官方题解写的有点抽象，难以知其所以然，然后从一篇日本题解得到了启发。
由于边权是\(1\)，我们考虑从 \(1\)号点进行 \(BFS\)，得到一张分层图，题目要求的就是第一层仅有一个点（即\(1\)号点），最后一层也仅有一个点（即 \(n\)号点），然后问这样的分层图有多少个。
从分层图的角度来看，问题就比较清晰了，主要是解决了最短路的问题。
分析这个分层图，容易发现同一层中的节点的连边是无所谓的，可有可无。然后相邻层之间必有连边，即该层的节点必定会与上一层的某一个节点有连边，但连边不会跨多层。
这样就可以一层一层\(dp\)，设\(dp[i][j]\)表示用了 \(i\)个点，且最后一层的点数是 \(j\)的方案数。
转移的时候考虑最后一层用了多少个点，以及最后一层的连边情况、最后一层和上一层的连边情况、最后一层的点的编号取值情况即可。
即考虑之前的最后一层用了\(k\)个点，那么从 \(dp[i - j][k]\)转移到\(dp[i][j]\)。
- 最后一层的边数共有 \(\tbinom{j}{2}\)条，均为可有可无，因此有\(2^{\tbinom{j}{2}}\)种情况。
- 最后一层每个点都必须与上一层至少连了一条边，则有\(2^{k} - 1\)种情况（排除无边相连的情况），该层有\(j\)个点，故有 \((2^{k} - 1)^{j}\)种情况
- 最后一层的取值编号情况，即从剩下的 \(n - (i - j) - 1\) 个编号（去掉\(n\)）取出 \(j\)个号码 放到最后一层，情况数是 \(\tbinom{n - i + j - 1}{j}\)
这四项相乘加到 \(dp[i][j]\)即可。注意第一层转移和最后一层转移的特殊性。
由于模数不一定是质数，因此组合数得事先预处理出来，而不能用阶乘的方式计算得到。
代码的复杂度是\(O(n^3\log n)\)，主要是转移的时候有幂运算，交换下第二三层循环顺序可以优化该运算，变成 \(O(n^3)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 500 + 8;
int n;
LL m;
LL dp[N][N];
LL C[N][N];
LL pow2[N * N];
long long qpower(long long a, long long b){
long long qwq = 1;
while(b){
if (b & 1)
qwq = qwq * a % m;
a = a * a % m;
b >>= 1;
}
return qwq;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i){
C[i][0] = 1;
for(int j = 1; j < i; ++ j){
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % m;
}
C[i][i] = 1;
}
pow2[0] = 1;
for(int i = 1; i <= n * n; ++ i)
pow2[i] = pow2[i - 1] * 2 % m;
dp[1][1] = 1;
for(int i = 2; i < n; ++ i){
for(int j = 1; j < i - 1; ++ j){
LL cnt = 1ll * j * (j - 1) / 2;
for(int k = 1; k < i - j; ++ k){
LL tmp = (pow2[k] - 1 + m) % m;
dp[i][j] = (dp[i][j] + dp[i - j][k] * pow2[cnt] % m * qpower(tmp, j) % m * C[n - i + j - 1][j] % m) % m;
}
}
dp[i][i - 1] = (dp[i][i - 1] + dp[1][1] * pow2[(i - 1) * (i - 2) / 2] % m * C[n - 1 - 1][i - 1] % m) % m;
}
for(int i = 1; i < n - 1; ++ i){
dp[n][1] = (dp[n][1] + dp[n - 1][i] * ((pow2[i] - 1 + m) % m) % m) % m;
}
cout << dp[n][1] << '\n';
return 0;
}
Ex - Alchemy (abc281 h)
题目大意
<++>
解题思路
<++>
神奇的代码
标签：tmp,AtCoder,Beginner,int,LL,cin,long,281,using From： https://www.cnblogs.com/Lanly/p/16977077.html