A - Long Loong
模拟。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x;
cin >> x;
cout << "L";
while (x--)
cout << "o";
cout << "ng" << endl;
return 0;
}
B - CTZ
对自带函数的运用。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x;
cin >> x;
cout << __builtin_ctz(x) << endl;
return 0;
}
C - Even Digits
转五进制,重载一下每一位具体数字。主播在 CF1811E Living Sequence 中做过类似 trick。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
string c = "02468";
void f(ll x, ll m)
{
if (x / m)
f(x / m, m);
cout << c[x % m];
}
int main()
{
ll n;
cin >> n;
f(n - 1, 5);
return 0;
}
D - Pyramid
扫两遍看一下自己最大能装到多大。
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
int n;
int a[200020];
int pre[200020];
int suf[200020];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
pre[i] = min(pre[i - 1] + 1, a[i]);
for (int i = n; i >= 1; i--)
suf[i] = min(suf[i + 1] + 1, a[i]);
int ans = 0;
for (int i = 1; i <= n; i++)
chkmx(ans, min(pre[i], suf[i]));
cout << ans << endl;
return 0;
}
E - Digit Sum Divisible
原题 P4127 [AHOI2009] 同类分布,数位 DP。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[20][200][200];
ll len;
ll a[20];
ll n;
ll p;
ll dp(ll pos, ll sum, ll st, int lim)
{
if (pos > len && sum == 0)
return 0;
if (pos > len)
return st == 0 && sum == p ? 1 : 0;
ll &t = f[pos][sum][st];
if (!lim && ~t)
return t;
ll ret = 0;
ll res = lim ? a[len - pos + 1] : 9;
for (int i = 0; i <= res; i++)
ret += dp(pos + 1, sum + i, (10LL * st + i) % p, i == res && lim);
return lim ? ret : t = ret;
}
ll calc(ll x)
{
len = 0;
while (x)
a[++len] = x % 10, x /= 10;
ll ret = 0;
for (p = 1; p <= 9 * len; p++)
{
memset(f, -1, sizeof(f));
ret += dp(1, 0, 0, 1);
}
return ret;
}
int main()
{
cin >> n;
cout << calc(n) << endl;
return 0;
}
F - Rotation Puzzle
发现每一次只能选择 $4$ 个位置,直接搜复杂度 $4^{20}$ 显然不可行。考虑折半搜索,从头开始搜 $4^{10}$ 个从尾开始搜 $4^{10}$ 个然后合并起来。
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> mtx;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
mtx a, b;
int n, m;
void prt(mtx &a)
{
for (auto i : a)
{
for (int j : i)
cout << j << ' ';
cout << '\n';
}
cout << '\n';
}
void RSZ(mtx &a)
{
a.resize(n);
for (int i = 0; i < n; i++)
a[i].resize(m);
}
bool in(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
void RRT(mtx &a, int x, int y)
{
mtx b;
RSZ(b);
b = a;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (x <= i && i <= n + x - 2 && y <= j && j <= m + y - 2)
a[i][j] = b[n + x - 2 - (i - x)][m + y - 2 - (j - y)];
}
}
}
map<mtx, int> frt;
map<mtx, int> bck;
queue<pair<mtx, int>> q; // {matrix,step}
int main()
{
cin >> n >> m;
RSZ(a);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int x;
cin >> x;
a[i][j] = x;
}
}
q.push({a, 0});
frt[a] = 0;
// RRT(a, 0, 0);
// prt(a);
// RRT(a, 1, 1);
// prt(a);
while (!q.empty())
{
mtx u = q.front().first;
int stp = q.front().second;
q.pop();
if (stp == 10)
continue;
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
mtx v = u;
RRT(v, i, j);
if (!frt.count(v))
frt[v] = stp + 1, q.push({v, stp + 1});
}
}
}
RSZ(b);
int tmp = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
b[i][j] = ++tmp;
q.push({b, 0});
bck[b] = 0;
while (!q.empty())
{
mtx u = q.front().first;
int stp = q.front().second;
q.pop();
if (stp == 10)
continue;
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
mtx v = u;
RRT(v, i, j);
if (!bck.count(v))
bck[v] = stp + 1, q.push({v, stp + 1});
}
}
}
int ans = 21;
for (auto p : frt)
{
mtx M = p.first;
if (bck.count(M))
chkmn(ans, p.second + bck[M]);
}
cout << (ans == 21 ? -1 : ans) << endl;
return 0;
}