ABC278 复盘
[ABC278A] Shift
思路解析：用队列模拟即可。
#include<bits/stdc++.h>
using namespace std;
int n, k, a[110];
int main() {
cin >> n >> k;
queue<int> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
q.push(a[i]);
}
for(int i = 1; i <= k; i++) {
q.pop();
q.push(0);
}
while(!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
[ABC278B] Misjudge the Time
思路解析：从现在开始， 往后遍历一天内的每一分钟，这样就不会重复，然后用 \(a,b,c,d\) 四个变量计算当前时间，每过一分钟就加一，同时计算进位，最后判断即可。
#include<bits/stdc++.h>
using namespace std;
int h, m;
bool check(int a, int b, int c, int d) {
return ((a * 10 + b) < 24) && ((c * 10 + d) < 60);
}
int main() {
cin >> h >> m;
int a = h / 10, b = h % 10, c = m / 10, d = m % 10;
for(int i = 1; i <= 1500; i++) {
if(check(a, c, b, d)) {
cout << a * 10 + b << " " << c * 10 + d;
return 0;
}
d++;
c += d / 10;
d = d % 10;
if(c * 10 + d >= 60) {
c = d = 0;
b++;
a += b / 10;
b = b % 10;
if(a * 10 + b >= 24) {
a = b = 0;
}
}
}
return 0;
}
[ABC278C] FF
思路解析：由于 \(n\) 很大 (\(n <= 10 ^ 9\)) ，但是 \(q\) 很小 (\(q <= 2 \times 10 ^ 5\))，所以选择用 map< pair<int, int>, int> 做，每个 map[{a, b}] == 1 代表 \(a\) 关注了 \(b\)，判断就用 find() 操作即可。
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
int n, q;
map< PII , int> mp;
int main() {
cin >> n >> q;
while(q--) {
int op, a, b;
cin >> op >> a >> b;
if(op == 1) {
mp[{a, b}] = 1;
}
else if(op == 2) {
if(mp.find({a, b}) != mp.end()) {
mp.erase({a, b});
}
}
else if(op == 3) {
if(mp.find({a, b}) != mp.end() && mp.find({b, a}) != mp.end()) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
}
return 0;
}
[ABC278D] All Assign Point Add
思路解析：有点思维量。首先可以想到对于操作 1 不需要将整个数组清空，而可以转变成给每个数打上标记，等下一次对这个数修改或查询时判断是否有标记，如果有则说明当前值没有修改过，此时再进行修改就能节省巨量的时间。但是 bool 数组的 memset 操作很浪费时间，于是我们选择用 bitset 的 \(O(1)\) 复杂度的赋值操作
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 10;
ll n, q;
ll a[N];
bitset<N> bs;
int main() {
cin >> n;
for(ll i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> q;
ll lstk = 0;
bs.set();
while(q--) {
ll op, x, k;
cin >> op;
if(op == 1) {
cin >> k;
lstk = k;
bs = 0;
}
else if(op == 2) {
cin >> x >> k;
if(bs[x] == 0) {
a[x] = lstk;
bs[x] = 1;
}
a[x] += k;
}
else if(op == 3) {
cin >> x;
if(bs[x] == 0) {
a[x] = lstk;
bs[x] = 1;
}
cout << a[x] << "\n";
}
}
return 0;
}
[ABC278E] Grid Filling
思路解析：模拟，可以看成二维滑动窗口，从每一行第一个开始，每往右移动一格就同时维护消失的和新出现的两个列的每个颜色的数量，和总数比较即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m, k, h, w;
int a[N][N];
int color[N];
int main() {
cin >> n >> m >> k >> h >> w;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
color[a[i][j]]++;
}
}
int c[N];
for(int i = 1; i <= n - h + 1; i++) {
memset(c, 0, sizeof(c));
for(int k = i; k <= i + h - 1; k++) {
for(int l = 1; l <= w; l++) {
c[a[k][l]]++;
}
}
int ans = 0;
for(int i = 1; i <= k; i++) {
if(c[i] < color[i]) {
ans++;
}
}
cout << ans << " ";
for(int j = 2; j <= m - w + 1; j++) {
for(int k = i; k <= i + h - 1; k++) {
c[a[k][j - 1]]--;
c[a[k][j + w - 1]]++;
}
ans = 0;
for(int i = 1; i <= k; i++) {
if(c[i] < color[i]) {
ans++;
}
}
cout << ans << " ";
}
cout << "\n";
}
return 0;
}
[ABC278F] Shiritori
思路解析：博弈论 + 状压dp，很有思考难度。首先可以根据 \(n <= 16\) 想到状压dp，\(f[i][j]\) 表示还剩下 \(i\) 状态的单词没被选，现在准备选 \(j\) 。然后就是dp，这里我们反向推，因为如果一个状态的后继状态全是必败态，那么当前状态就是必胜态，反之则为必败态，所以我们根据这个道理反向推即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
string str[N];
int sz[N];
bool f[1 << N][N];
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> str[i];
sz[i] = str[i].size();
f[(1 << n) - 1][i - 1] = 1;
}
for(int i = (1 << n) - 1; i >= 0; i--) {
for(int j = 0; j < n; j++) {
if((i >> j) & 1) {
f[i][j] = 1;
for(int k = 0; k < n; k++) {
if(!((i >> k) & 1) && k != j && str[k][sz[k] - 1] == str[j][0]) {
if(f[i ^ (1 << k)][k]) {
f[i][j] = 0;
}
}
}
}
}
}
for(int i = 0; i < n; i++) {
if(f[1 << i][i]) {
cout << "First";
return 0;
}
}
cout << "Second";
return 0;
}