@TOC
比赛链接: Codeforces Round #806 (Div. 4)
A YES or YES?
题目
大意：给你一个有大写和小写的字符串，如果不看是否大小写的话能否等于"YES"
思路：字符串+枚举
将小写转换成大写，在看转换后的字符串是否和"YES"相等也可以枚举的时候忽视大小写，只要是“YES”中的字母的大小写即可
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
void solve()
{
string s;
cin >> s;
if (s.size() != 3)
{
puts("NO");
return;
}
if ((s[0] == 'Y' || s[0] == 'y') && (s[1] == 'E' || s[1] == 'e') && (s[2] == 'S' || s[2] == 's'))
{
puts("YES");
return;
}
puts("NO");
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}B. ICPC Balloons
题目
大意：给你一个由大写英文字母组成的字符串，每个字符第一次出现的时候给你两个气球，其他时候都只给你一个气球，问最后有多少个气球
思路：字符串+枚举
枚举字符串的时候，判断这个字母是否出现过了出现过就加1，没出现过就加2，并且记录出现过了
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
int a[26];
void solve()
{
memset(a, 0, sizeof a);
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
for (int i = 0; i < s.size(); i++)
{
if (a[s[i] - 'A'] == 0)
{
cnt++;
}
cnt++;
a[s[i] - 'A'] = 1;
}
cout << cnt << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}D. Double Strings
题目
题目大意：给你n个字符串(长度不超过8），问每个字符串是否可以由其他的字符串中选两个拼接而成
思路：字符串+hash
如果计算所有可以拼接成字符串来判断一定会超时，所以我们逆向思维一下，由于每个字符串长的超度不超过8，所以可以将某个字符串分解成两个字符串，看这两个字符串是否在集合中出现即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e5 + 10;
int a[N];
string s[N];
void solve()
{
int n;
cin >> n;
map<string, int> ma;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
ma[s[i]] = 1;
a[i] = 0;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < s[i].size(); j++)
{
string a1 = s[i].substr(0, j), b1 = s[i].substr(j);
if (ma.count(a1) && ma.count(b1))
a[i] = 1;
}
}
for (int i = 1; i <= n; i++)
cout << a[i];
cout << '\n';
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}E. Mirror Grid
题目
题目大意：给你一个由0和1构成正方形数组里面，然后将数组向右选择90度，180度，270度。问如何改变原数组中的某些值，使得四种形态的数组里的值都一样。求改变最少次数。我们
思路：思维
原二维数组中的一个位置旋转三次后，总共会出现在四个位置上，所以我们只需要将这四个位置的值都变相同，那么就是最少值了。
a[i][j]==》a[j][n-i+1]==》a[n-i+1][n-j+1]==>a[n-j+1][j]
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e2 + 10;
char a[N][N];
bool st[N][N];
void solve()
{
int n;
cin >> n;
memset(st, 0, sizeof st);
for (int i = 1; i <= n; i++)
scanf("%s", a[i] + 1);
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j && n % 2 == 1)
continue;
if (!st[i][j])
{
int cnt = 0;
if (a[i][j] == '1')
cnt++;
st[i][j] = 1;
if (a[j][n - i + 1] == '1')
cnt++;
st[j][n - i + 1] = 1;
if (a[n - i + 1][n - j + 1] == '1')
cnt++;
st[n - i + 1][n - j + 1] = 1;
if (a[n - j + 1][i] == '1')
cnt++;
st[n - j + 1][i] = 1;
ans += min(cnt, 4 - cnt);
}
}
}
cout << ans << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}F. Yet Another Problem About Pairs Satisfying an Inequality
题目
题目大意：给你一个数组，找到所有的满足
a[i]<i<a[j]<j的索引对数量
思路：二分/树状数组
a[i]范围很大，但是i的范围不大，所以我们著需要保留所有a[i]<i 的索引即可，针对每个满足a[j]<j的元素，我们可以找到在它之前的满足所有a[i]<i<a[j]的全部元素，这里我们可以用二分或者时树状数组来做二分：从前往后依次枚举，我们用一个vector来存满足的下标，枚举到某一位时，只需要在vector中找到比a[i]-1小的有多少个就行了
树状数组：快速查找一个区间内的全部元素，add操作中，我们只需要将
i位置加1即可，因为后面的所有都要比i大，而不是比a[i]大，query查找中，我们只需要查询1-a[j]-1的区间即可
代码：二分：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int a[N];
int n;
void solve()
{
cin >> n;
ll ans = 0;
vector<int> v;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] < i)
{
ans += (ll)(lower_bound(v.begin(), v.end(), a[i]) - v.begin());
v.push_back(i);
}
}
cout << ans << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}代码：树状数组
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int a[N];
int tr[N];
int n;
int lowbit(int x)
{
return x & -x;
}
void add(int x)
{
while (x <= n)
{
tr[x] += 1;
x += lowbit(x);
}
}
ll query(int x)
{
ll ans = 0;
while (x > 0)
{
ans += tr[x];
x -= lowbit(x);
}
return ans;
}
void solve()
{
cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++)
tr[i] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] < i)
{
ans += query(a[i] - 1);
add(i);
}
}
cout << ans << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}G. Good Key, Bad Key
题目
题目大意：有n宝箱，每一个宝箱都有一个价值，只能从小到大依次打开每个箱子，且每个箱子必须打开。可以用两种钥匙打开：
- 好钥匙：花费k元
- 坏钥匙：不花钱，但是后面每个箱子内的价值/2向下取整
思路：动态规划
状态表示：
f[i][j]表示前i个宝箱中用了多少把坏钥匙，我第一次这样想的时候，觉得这样不爆内存了吗，n最大1e5，后来我才发现，每一个宝箱的价值最大是1e9，最多需要用30把坏钥匙后价值就变为0了，不用在管30把钥匙之后的情况了。所以这样很多人写这道题疑惑的一个点吧。状态计算：
- j == 0，表示从1到现在没用过一把坏钥匙，所以
f[i][j] = f[i-1][j] + a[i] - kj != 0 ，表示从1到现在总共用了
j把坏钥匙，但是这里还要分两种情况：- 第i个箱子用了第j把坏钥匙：`f[i][j] = f[i-1][j-1] + a[i]/(2^j) - k` - 第i个箱子没用坏钥匙：`f[i][j] = f[i-1][j] + a[i]/(2^j)` 两个取最大值即可。写动态规划的题就主要在如何将状态转移上。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e5 + 10;
int a[N];
ll f[N][35];
int n, k;
ll p[35];
void solve()
{
cin >> n >> k;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 32; j++)
f[i][j] = -0x3f3f3f3f;
f[0][0] = 0;
for (int i = 1; i <= n; i++)
{
f[i][0] = f[i - 1][0] + a[i] - k;
for (int j = 1; j <= 30; j++)
f[i][j] = max(f[i - 1][j] + (a[i] / p[j]) - k, f[i - 1][j - 1] + a[i] / p[j]);
for (int j = 0; j <= 30; j++)
ans = max(ans, f[i][j]);
}
cout << ans << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
p[0] = 1;
for (int i = 1; i <= 32; i++)
p[i] = p[i - 1] * 2;
int t;
cin >> t;
while (t--)
solve();
return 0;
}
