寒假训练2024/1/29
2024/1/28
ABC337(A-E)
A - Scoreboard
思路：
水题，统计加和，最后比较。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
int A = 0, B = 0, a, b;
for (int i = 0; i < n; i++) {
cin >> a >> b;
A += a;
B += b;
}
if(A > B) {
cout << "Takahashi\n";
}
else if(A < B) {
cout << "Aoki\n";
}
else {
cout << "Draw\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
B - Extended ABC
题意：
验证给定的字符串是不是ABC扩展串，这个水题思路很多，但是也有人错，需要注意下。
思路：
我们不用搞花里胡哨的思路，正难则反，想什么时候是不符合条件的，显然，如果A前面有B或者C，B前面有C都是不合法的。特判就行。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
string s;
cin >> s;
bool flag_a = 0, flag_b = 0, flag_c = 0;
bool ok = 1;
for (auto c : s) {
if(c == 'A') {
flag_a = 1;
if(flag_c || flag_b) {
ok = 0;
break;
}
}
else if(c == 'B') {
flag_b = 1;
if(flag_c) {
ok = 0;
break;
}
}
else if(c == 'C') {
flag_c = 1;
}
}
if(ok) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
C - Lining Up 2
题意：
题目给了n个人跟在谁后面，如果是-1就是第一个。
让我们求排队的顺序。
思路：
用数组模拟链表，统计每个人的后继，最后遍历就行。
//数组模拟链表
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int>ne(n + 1);
for (int i = 1, t; i <= n; i++) {
cin >> t;
if(t == -1) {
t = 0;
}
ne[t] = i;
}
for (int i = 0; ne[i]; i = ne[i]) {
cout << ne[i] << " ";
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
D - Cheating Gomoku Narabe
题意：
题录给一个图，o表示有，.表示可以有，代价是1，x是不允许有。
让我们找到连续的横或者竖着的k个字符，求最小代价。
思路：
刚开始我是想着遍历每个点，由上面或者左边延申的长度和代价，在遍历过程中一直最小化这个代价。
struct inf {
//竖
int num1;
int cos1;
//横
int num2;
int cos2;
};
vector<string> arr(r);
for (int i = 0; i < r; i++) {
cin >> arr[i];
}
vector<vector<inf>> v(r, vector<inf>(c));
int m = max(r, c);
vector<int> cnt(m + 1, 1e18);
for (int i =0; i < r; i++) {
for (int j = 0; j < c; j++) {
if(arr[i][j] == 'o') {
if(i - 1 >= 0) {
v[i][j].num1 = v[i - 1][j].num1 + 1;
v[i][j].cos1 = v[i - 1][j].cos1;
}
else {
v[i][j].num1 = 1;
v[i][j].cos1 = 0;
}
if(j - 1 >= 0) {
v[i][j].num2 = v[i][j - 1].num2 + 1;
v[i][j].cos2 = v[i][j - 1].cos2;
}
else {
v[i][j].num2 = 1;
v[i][j].cos2 = 0;
}
}
else if(arr[i][j] == '.') {
if(i - 1 >= 0) {
v[i][j].num1 = v[i - 1][j].num1 + 1;
v[i][j].cos1 = v[i - 1][j].cos1 + 1;
}
else {
v[i][j].num1 = 1;
v[i][j].cos1 = 1;
}
if(j - 1 >= 0) {
v[i][j].num2 = v[i][j - 1].num2 + 1;
v[i][j].cos2 = v[i][j - 1].cos2 + 1;
}
else {
v[i][j].num2 = 1;
v[i][j].cos2 = 1;
}
}
else {
v[i][j].num1 = 0;
v[i][j].cos1 = 0;
v[i][j].num2 = 0;
v[i][j].cos2 = 0;
}
cnt[v[i][j].num1] = min(cnt[v[i][j].num1], v[i][j].cos1);
cnt[v[i][j].num2] = min(cnt[v[i][j].num2], v[i][j].cos2);
}
}
但是最后一个样例没过，我才发现，这个思路的错误在于，只能从最左边和最上边第一个合法的字符（o或者。）开始，但是最优解可能是中间开始，所以这个方法只能用来求最多能形成的长条和竖条有多长，却不一定是最优解。
昨晚没想出来就睡觉了。
今天早晨醒来又想了想，对于每个点我们都要遍历，可以分横竖两次遍历，我们按照横遍历讨论：
我第一想的是尺取法，对于每一行，我们枚举左端点和右端点（长度是k），只要这一段里没有x就是合法的，代价就是这一段里。的数量。取每一段的复杂度是O(r * c).但是比较的复杂度是O（r * c）.这样复杂度就是面积的平方。会超时，所以要优化一下。
我又想到，比较的算法可以向KMP里的比较优化，因为中间可以不回溯：如果上次的横条是合法的，那么我们只需要特判下一个新的元素就行，如果中间遇到x，这次比较就终止，从x的下一个开始新一轮的比较。
其实就是滑动窗口，用双指针实现。
复杂度是O（S）.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int r, c, k;
cin >> r >> c >> k;
vector<string> arr(r);
for (int i = 0; i < r; i++) {
cin >> arr[i];
}
int minm = 1e18;
for (int i = 0; i < r; i++) {
bool ok = 0;
int res = 0;
for (int pb1 = 0; pb1 <= c - k; pb1++) {
if(ok) {
res -= (arr[i][pb1 - 1] == '.');
if(arr[i][pb1 + k - 1] == 'o') {
minm = min(minm, res);
}
else if(arr[i][pb1 + k - 1] == '.') {
minm = min(minm, ++res);
}
else {
ok = 0;
}
}
else {
res = 0, ok = 1;
for (int pb2 = pb1; pb2 < pb1 + k; pb2++) {
if(arr[i][pb2] == 'o') {
continue;
}
else if(arr[i][pb2] == '.') {
res++;
}
else {
ok = 0;
pb1 = pb2;
break;
}
}
if(ok) {
minm = min(minm, res);
}
}
}
}
for (int j = 0; j < c; j++) {
bool ok = 0;
int res = 0;
for (int pb1 = 0; pb1 <= r - k; pb1++) {
if(ok) {
res -= (arr[pb1 - 1][j] == '.');
if(arr[pb1 + k - 1][j] == 'o') {
minm = min(minm, res);
}
else if(arr[pb1 + k - 1][j] == '.'){
minm = min(minm, ++res);
}
else {
ok = 0;
}
}
else {
res = 0, ok = 1;
for (int pb2 = pb1; pb2 < pb1 + k; pb2++) {
if(arr[pb2][j] == 'o') {
continue;
}
else if(arr[pb2][j] == '.') {
res++;
}
else {
ok = 0;
pb1 = pb2;
break;
}
}
if(ok) {
minm = min(minm, res);
}
}
}
}
if(minm == 1e18) {
cout << -1 << endl;
}
else {
cout << minm << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
E - Bad Juice
题意：
又n瓶饮料，只有一瓶有问题，让找到最少的人，对于每个人可以给他喝任意瓶饮料，交互机会给出这几个人的状态，最后要判断是哪一瓶饮料的问题。
思路：二进制状态压缩
之前做过类似的题：
是n瓶饮料，任意瓶饮料有问题，这个是只有一瓶有问题。
异曲同工，上一个问题是需要$2^n$的人能试出来，对于这一瓶我们只需要$\log_{2}{n}$ 就可以。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
int m = log2(n);
if(pow(2, m) < n) {
m++;
}
cout << m << endl;
vector<vector<int>> v(m, vector<int>() );
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if((i >> j) & 1) {
v[j].push_back(i + 1);
}
}
}
for (int i = 0; i < m; i++) {
cout << v[i].size() << " ";
for (auto it : v[i]) {
cout << it << " ";
}
cout << endl;
}
string res;
cin >> res;
int ans = 1;
int pw = 1;
for (int i = 0; i < res.size(); i++) {
ans += (res[i] - '0') * pw;
pw *= 2;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}