A - Count Takahashi
Question：
给你n个单词，要么是Takahashi，要么是Aoki；输出有几个Takahashi即可。
Code：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double eps = 1e-10;
const int N = 5e5 + 10;
const int INF = 1e16;
const ll mod = 1e9 + 7;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n; cin >> n;
int num = 0;
for(int i = 1;i <= n;i++){
string s;
cin >> s;
if(s == "Takahashi")
num++;
}
cout << num << endl;
}
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int TTT = 1;
//cin >> TTT;
while (TTT--)
solve();
return 0;
}
B - Couples
Question：
给定正整数 \(n\) ，代表颜色种类；存在 \(2n\) 个人，每人只能选一种颜色。且保证每种颜色有且只有两个人选择。告诉你每个人选的颜色，求出有几种颜色满足以下条件
- 这种颜色的左右两人中间恰好只有一个人
保证颜色是从 1 到 \(n\) 的
Code:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double eps = 1e-10;
const int N = 5e5 + 10;
const int INF = 1e16;
const ll mod = 1e9 + 7;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int l[N], r[N];
void solve() {
int n; cin >> n;
for(int i = 1;i <= 2 * n;i++){
int num; cin >> num;
if(l[num] == 0)
l[num] = i;
else
r[num] = i;
}
int ans = 0;
for(int i = 1;i <= n;i++){
if(r[i] - l[i] == 2)
ans++;
}
cout << ans << endl;
}
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int TTT = 1;
//cin >> TTT;
while (TTT--)
solve();
return 0;
}
C - Tile Distance 2
Question:
给你起点和终点，问从起点到终点最少只用穿过几块砖头
Solution：
观察发现，我们在往上或者往下移动的同时是可以顺便左右移动的，且此时不用穿过新的砖头，因为这个砖头是1 × 2的，在同一个砖头里可以左右移动。所以我们先观察能否在垂直方向上移动的同时把水平方向的距离补平，如果可以那只用移动垂直方向上的距离即可，否则则要额外加上水平方向上的距离。
还有一个注意点是，我们要先判断起点处于当前砖头的左边还是右边，若是左边且要向右移动，那就可以多一次免费的移动，在右边且要向左边移动也是同理。所以我们以向左移动或者向右移动来进行分类讨论
Code：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double eps = 1e-10;
const int N = 5e5 + 10;
const int INF = 1e16;
const ll mod = 1e9 + 7;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
int ans = abs(sy - ey), cnt = 0;
if(sx < ex){
cnt = abs(sy - ey);
if((sx + sy) % 2 == 0)
cnt++;
if(cnt < ex - sx){
ans += (ex - sx - cnt + 1) / 2;
}
}
else if(sx > ex){
cnt = abs(sy - ey);
if((sx + sy) % 2 == 1)
cnt++;
if(cnt < sx - ex){
ans += (sx - cnt - ex + 1) / 2;
}
}
cout << ans << endl;
}
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int TTT = 1;
//cin >> TTT;
while (TTT--)
solve();
return 0;
}
D - Avoid K Palindrome
Question：
给定\(n\)，k$ 和一个字符串 \(s\)。\(n\) 代表字符串 \(s\)的长度。该字符串仅由 'A' ，'B'， '?'组成，问号可以替换成 'A' 或者 'B'。
一个good string包含以下要求
- 字符串中不存在任何一个长度为 \(k\) 的回文串
问给定的字符串 \(s\)，能有几种good string的种类，取模 998244353
Solution：
我们观察到 \(k\) 的范围非常小，考虑采取状压DP ，首先定义 'A' 代表0，'B'代表1； \(dp[i][msk]\) 代表当前结尾位置为第 i 位且前 k - 1位组成的二进制数为 msk 的情况下good string的数量。那么我们可以想到一个推导公式，假定当前 前 k - 1位是 msk 的话 假如 msk | 当前这位 不是回文串，那么就可以从这一种状态转移过来，否则跳过。那么如何转移呢
\(dp[i][msk] -> dp[i + 1][((msk << 1) | now) mod (1 << (k - 1))]\)
此时保证 \((msk << 1) | now\) 不是回文串才可以转移。 取模是为了保证只留下后面k - 1位 即把溢出的去掉
Code：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double eps = 1e-10;
const int N = 5e5 + 10;
const int INF = 1e16;
const ll mod = 998244353;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int is_hw[1 << 11];
int dp[1010][1 << 11];
void solve() {
int n, k;
cin >> n >> k;
string s; cin >> s;
for(int i = 0;i < (1 << k);i++){
vector<int>p(k);
int num = i;
for(int j = 0; j < k;j++){
p[j] = num & 1;
num = num >> 1;
}
auto pp = p;
reverse(pp.begin(),pp.end());
is_hw[i] = (p == pp);
}
dp[0][0] = 1;
for(int i = 0;i < n;i++){
vector<int>p;
if(s[i] == 'A') p.push_back(0);
if(s[i] == 'B') p.push_back(1);
if(s[i] == '?') p.push_back(0), p.push_back(1);
for(int msk = 0;msk < 1 << (k - 1);msk++){
for(auto v : p){
if(i + 1 >= k && is_hw[(msk << 1) + v])
continue;
int nxt = ((msk << 1) + v ) % (1 << (k - 1));
dp[i + 1][nxt] = (dp[i + 1][nxt] + dp[i][msk]) % mod;
}
}
}
int ans = 0;
for(int i = 0;i < 1 << (k - 1);i++){
ans = (ans + dp[n][i]) % mod;
}
cout << ans << endl;
}
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int TTT = 1;
//cin >> TTT;
while (TTT--)
solve();
return 0;
}
E - Water Tank
Question：
给定正整数 \(n\)，存在 \(n\) 个挡板，从左到右给定挡板的高度 \(H_i\)，从第一个挡板的左边开始到最后一个挡板的右边，总共由n + 1 个水槽，水槽内水的高度记为\(A_i\);一开始\(A_0 = A_1 = ... = A_n = 0\)
对A重复进行以下运算:
- 将\(A_0\)的值增加1。
- 依次对 \(i\) = 1,2,...,N进行以下操作
- 如果\(A_{i - 1}\) > \(A_i\) ;和 \(A_{i - 1}\)> \(H_i\)，则将 \(A_{i - 1}\) 的值减少1，并将 \(A_i\) 的值增加1。
- 求每个 \(i\) = 1,2,...,N 在 \(A_i\) > 0第一次成立之前的运算次数。
Solution：
我们手玩 观察发现，我用 ans 来记录水落到当前这个水槽所花费的时间。那么假如下一个挡板的高度低于当前这个挡板的高度，我只需要 ans + 下一个挡板的高度即可得到水落到下一个水槽所花费时间。假如下一个挡板的高度高于这个挡板的高度，我们把下一个挡板的高度记为 res，那么就需要把所有低于res的水槽高度都提到res的高度。所有我们使用map来记录当前这个高度的水槽有几个。然后在每一次提高度的时候从前往后遍历，将这个高度都提到res然后erase掉。
由于每次都是一批提到一个相同的高度，所以其实map中的数量不会特别多 所以不会超时。
Code：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double eps = 1e-10;
const int N = 5e5 + 10;
const int INF = 1e16;
const ll mod = 1e9 + 7;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int h[N];
map<int,int>mp;
void solve() {
int n; cin >> n;
for(int i = 1;i <= n;i++)
cin >> h[i];
int ans = 0;
for(int i = 1;i <= n;i++){
if(i == 1){
ans += h[i];
mp[h[i]]++;
ans++;
cout << ans << " ";
continue;
}
if(h[i] <= h[i - 1]){
mp[h[i]]++;
ans += h[i];
cout << ans << " ";
}
else{
for(auto it = mp.begin();it != mp.end();){
int u = (*it).first, v = (*it).second;
if(u < h[i]){
mp[h[i]] += v;
ans += v * (h[i] - u);
mp.erase(it++);
}
else{
break;
}
}
ans += h[i];
mp[h[i]]++;
cout << ans << " ";
}
}
}
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int TTT = 1;
//cin >> TTT;
while (TTT--)
solve();
return 0;
}
F - Tree Degree Optimization
Question：
给你一个整数序列 \(A =(A_1,..,A_N)\)。对于一棵有 \(N\) 个顶点的树 \(T\)，定义 \(f(T)\) 如下
设 \(d_i\) 是 \(T\) 中顶点 \(i\) 的度数。那么，\(f(T) = \sum_{i=1}^N d_i^2A_i\)
求 \(f(T)\) 的最小可能值,
约束条件保证答案小于\(2^{63}\)
Solution：
由于是一棵树，所有点的度相加一定是 \(2 * N - 2\)
对每个点都分配 1，剩下\(N - 2\) 需要分配。
对于每个数字，假如加1 那么增加的值就是 \((du + 1)^2 * A_i - du^2 * A_i = (2 * du + 1) * A_i\)
那么只需要用优先队列维护代价值\((2 * du + 1) * A_i\) 然后贪心的去分配最小即可
Code：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double eps = 1e-10;
const int N = 5e5 + 10;
const int INF = 1e16;
const ll mod = 1e9 + 7;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int a[N];
auto cmp = [](const pii &a, const pii &b){
return a.first > b.first; // 从小到大排序
};
priority_queue<pii, vector<pii>, decltype(cmp)> que(cmp);
void solve() {
int n; cin >> n;
int ans = 0;
for(int i = 1;i <= n;i++){
cin >> a[i];
ans += a[i];
que.push({a[i] * 3, 1});
}
sort(a + 1, a + 1 + n);
n = n - 2;
while(n){
pii op = que.top();
que.pop();
ans += op.first;
que.push({(op.first / (2 * op.second + 1)) * (2 * op.second + 3), op.second + 1});
n--;
}
cout << ans << endl;
}
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int TTT = 1;
//cin >> TTT;
while (TTT--)
solve();
return 0;
}