本片博文记录cj第一次ak(尽管是补题ak)
Problem - D
题意:
不过多赘述
思路:
在一段不含白色的区间内,必须同时含有R和B,否则不满足,为了好处理,在头尾分别加上W,否则处理起来很头疼,既要看开头又要看结尾
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
string s, a;
getchar();
getline(cin, s);
s = 'W' + s + 'W';
for (int i = 1; i <= n; i ++)
{
int fb = 0, fa = 0;
if (s[i] == 'B' || s[i] == 'R')
{
while (s[i] == 'B' || s[i] == 'R')
{
if (s[i] == 'B')
fb = 1;
else
fa = 1;
i++;
}
if (!fa || !fb)
{
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
int main()
{
int t;
cin >> t;
while (t --)
solve();
}
Problem - E
思路:
记录所有字符串的一二位,每个字母出现了多少次,然后当前字符可以构成满足的pair数目是第一位字母出现过的次数加上第二位的次数减去当前字符串出现的次数
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
map<string, int> all;
map<int, int> one, two;
void solve()
{
all.clear();
one.clear();
two.clear();
int n;
int res = 0;
cin >> n;
for (int i = 0; i < n; i ++)
{
string s;
cin >> s;
res += one[s[0]];
res += two[s[1]];
res -= (all[s] * 2);
one[s[0]]++;
two[s[1]]++;
all[s]++;
}
cout << res << endl;
}
main()
{
int t;
cin >> t;
while (t --)
solve();
}
Problem - F
思路:
很简单的双指针算法
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++)
cin >> a[i];
int i = 0, j = n - 1;
int t = 0, r = 0;
int si = 0, sj = 0, res = 0;
while (i <= j)
{
if (si <= sj)
{
si += a[i];
i++;
t++;
}
else if (si > sj)
{
sj += a[j];
j--;
t++;
}
if (si == sj)
{
res = si;
r = t;
}
}
if (!res)
{
cout << "0\n";
}
else
cout << r << endl;
}
int main()
{
int t;
cin >> t;
while (t --)
solve();
}
Problem - G
思路:
很简单的搜索,暴力也能过,刚开始自己只搜一遍,就导致多次跌落的石子只跌落一次,循环搜索n次就过了(反正数据范围小)
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int n, m;
char a[N][N];
void dfs(int i, int j)
{
if (i == -1)
return;
if (a[i][j] == '*' && a[i + 1][j] == '.')
{
swap(a[i][j], a[i + 1][j]);
}
dfs(i - 1, j);
}
void solve()
{
memset(a, 0, sizeof a);
cin >> n >> m;
for (int i = 0; i < n; i ++)
cin >> a[i];
int t = n;
while (t --)
for (int i = 0; i < m; i ++)
{
dfs(n - 1, i);
}
for (int i = 0; i < n; i ++)
{
cout << a[i] << endl;
}
cout << endl;
}
int main()
{
int t;
cin >> t;
while (t --)
{
solve();
}
}
Problem - H
思路:
记录每个数字所有位数0出现的次数,从高到低遍历,如果k可以将当前位数的0抵消掉,就将当前位数0的次数变成0,然后遍历所有位数,只要出现次数为0,就在结果加上2的当前位数次方
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, INF = (1 << 31) - 1;
int a[N];
void solve()
{
int n, k;
cin >> n >> k;
int res = INF;
for (int i = 0; i < n; i ++)
{
cin >> a[i];
res &= a[i];
}
deque<int> q;
int idx = 0;
while (res)
{
int t = res & 1;
if (!t)
{
q.push_back(idx);
}
idx++;
res >>= 1;
}
for (int i = 0; i < n; i ++)
{
if (k == 0 || q.empty())
break;
// cout << q.back();
a[i] = (1 << q.back());
q.pop_back();
k--;
}
res = INF;
for (int i = 0; i < n; i ++)
{
res &= a[i];
}
cout << res << endl;
}
int main()
{
int t;
cin >> t;
while (t --)
solve();
}