A. Primary Task
枚举所有情况即可
void solve(){
string s;
cin >> s;
if (s.substr(0, 2) != "10" || s.size() < 3 || s[2] == '0' || (s.size() < 4 && s[2] < '2')) {
cout << "NO\n";
}
else {
cout << "YES\n";
}
}
B. Seating in a Bus
简单模拟题
void solve(){
int n;
cin >> n;
vector<int> a(n + 2);
bool ok = true;
for (int i = 1; i <= n; ++i) {
int t;
cin >> t;
if (!ok) {
continue;
}
if (i == 1) {
a[t] = 1;
}
else {
if (a[t - 1] || a[t + 1]) {
a[t] = 1;
}
else {
ok = false;
}
}
}
cout << (ok ? "YES\n" : "NO\n");
}
C. Numeric String Template
一时没想到低空间复杂度解法,直接上了map+并查集
void solve(){
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) {
cin >> x;
}
int m;
cin >> m;
bool ok = false;
map<int, vector<int>> mapp;
for (int i = 0; i < n; ++i) {
mapp[a[i]].push_back(i);
}
Dsu dsu(n + 1);
for (const auto&[x, y] : mapp) {
for (int i = 0; i < (int)y.size() - 1; ++i) {
dsu.unionSet(y[i], y[i + 1]);
}
}
for (int i = 0; i < m; ++i) {
string s;
cin >> s;
if (s.size() != n) {
cout << "NO\n";
continue;
}
mapp.clear();
for (int i = 0; i < n; ++i) {
mapp[s[i]].push_back(i);
}
Dsu dsu2(n + 1);
for (const auto&[x, y] : mapp) {
for (int i = 0; i < (int)y.size() - 1; ++i) {
dsu2.unionSet(y[i], y[i + 1]);
}
}
bool same = true;
for (int i = 0; i < n; ++i) {
if (dsu.findSet(i) != dsu2.findSet(i)) {
same = false;
break;
}
}
cout << (same ? "YES" : "NO") << '\n';
}
}
D. Right Left Wrong
贪心问题,策略应该是让数字尽可能被多次数的操作,于是进行LR匹配即可
void solve(){
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) {
cin >> x;
}
string s;
cin >> s;
long long ans = 0;
vector<pair<int, int>> pairs;
int l = -1;
int r = n;
while (l <= r) {
size_t ll = s.find_first_of('L', l + 1);
size_t rr = s.find_last_of('R', r - 1);
if ((ll == s.npos) || (rr == s.npos)) {
break;
}
if (ll <= rr) {
pairs.emplace_back(ll, rr);
}
l = ll;
r = rr;
}
vector<long long> pref(n + 1);
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + a[i];
}
for (const auto&[x, y] : pairs) {
ans += (pref[y + 1] - pref[x]);
}
cout << ans << '\n';
}
E. Photoshoot for Gorillas
跟D的出题意愿差不多,依然是统计出现次数最多的格子,不过是在二维中
二维差分即可
这里做的时候卡住了,第一次写二维差分,多减了一次权值没有补回来
void solve(){
int n, m, k;
cin >> n >> m >> k;
int q;
cin >> q;
vector<int> a(q);
for (auto& x : a) {
cin >> x;
}
vector<vector<int>> grid(n + 2, vector<int>(m + 2));
for (int i = 1; i + k <= n + 1; ++i) {
for (int j = 1; j + k <= m + 1; ++j) {
grid[i][j] ++;
grid[i][j + k] --;
grid[i + k][j] --;
grid[i + k][j + k] ++;
//for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cout << grid[i][j] << " \n"[j == m];
//cout << endl;
}
}
multiset<int> sett;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
grid[i][j] += (grid[i][j - 1] + grid[i - 1][j] - grid[i - 1][j - 1]);
int t = grid[i][j];
sett.insert(grid[i][j]);
//for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cout << grid[i][j] << " \n"[j == m];
//cout << endl;
}
}
long long ans = 0;
sort(a.rbegin(), a.rend());
auto it = sett.rbegin();
for (int i = 0; i < q; ++i) {
ans += 1ll * a[i] * (*it);
it ++;
if (it == sett.rend()) {
break;
}
}
cout << ans << '\n';
}
标签:966,int,auto,void,cin,VP,vector,solve,Div
From: https://www.cnblogs.com/yxcblogs/p/18360492