A - Shift (abc278 a)
题目大意
给定一个有\(n\)个整数的数组\(a\)，要求进行以下 \(k\)次操作，输出操作后的数组。
操作为：将第一个数去掉，在队尾加上一个\(0\)。
解题思路
模拟即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
k = min(n, k);
int x;
for(int i = 0; i < k; ++ i){
cin >> x;
}
for(int i = k; i < n; ++ i){
cin >> x;
cout << x << ' ';
}
for(int i = 0; i < k; ++ i)
cout << 0 << ' ';
return 0;
}
B - Misjudge the Time (abc278 b)
题目大意
定义一个迷惑时间为：交换小时的个位和分钟的十位后，所形成的时间也是有效时间。
给定一个时间\(h:m\)，问该时间（包括该时间）之后第一个迷惑时间是多少。
解题思路
时间数就只有\(24 \times 60 = 1440\)，逐一枚举判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, m;
cin >> h >> m;
auto check = [](int h, int m){
int h1 = h / 10;
int h2 = h % 10;
int m1 = m / 10;
int m2 = m % 10;
int H = h1 * 10 + m1;
int M = h2 * 10 + m2;
return H >= 0 && H <= 23 && M >= 0 && M <= 59;
};
auto add = [](int &h, int &m){
++ m;
if (m >= 60){
m -= 60;
h ++;
}
h %= 24;
};
while(true){
if (check(h, m)){
cout << h << ' ' << m << '\n';
break;
}
add(h, m);
}
return 0;
}
C - FF (abc278 c)
题目大意
一个聊天软件，\(n\)位用户，有 \(q\)次事件，第一个事件为 \(a\)关注 \(b\)，第二个是取关，第三个问 \(a\)和 \(b\)之间是否是互关的关系。
解题思路
因为用户标号达到\(10^9\)，不能直接二维数组，用set或map记录关注信息，直接判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
set<pair<int, int>> qwq;
while(q--){
int t, a, b;
cin >> t >> a >> b;
if (t == 1){
qwq.insert({a, b});
}else if (t == 2){
qwq.erase({a, b});
}else{
if (qwq.find({a, b}) != qwq.end() && qwq.find({b, a}) != qwq.end())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
}
return 0;
}
D - All Assign Point Add (abc278 d)
题目大意
给定一个有\(n\)个整数的数组\(a\)，有 \(q\)次操作，分为三类：
- 给定\(x\)，表示将所有数赋值为 \(x\)
- 给定\(i\)和 \(x\)，将 \(a_i\)增加 \(x\)
- 给定\(i\)，询问 \(a_i\)
解题思路
第一个操作相当于规定基准数，第二个操作我们用一个数组\(add\)来维护增加的数，也就是相对于基准数的值。
这样对于第三个操作，\(a_i\)就是两者的加了。
当再一次操作一时，我们把之前进行过操作二的数据\(add\)对应的位置重置为\(0\)即可。总的时间复杂度就是\(O(q)\)（势能分析的角度，每一次操作二会给操作一带来\(1\)的势能，总的势能不超过 \(O(q)\)）
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<LL> a(n);
set<int> id;
for(int i = 0; i < n; ++ i)
id.insert(i);
LL base = 0;
for(auto &i : a)
cin >> i;
int q;
cin >> q;
while(q--){
int op;
cin >> op;
if (op == 1){
for(auto &i : id){
a[i] = 0;
}
id.clear();
cin >> base;
}else if (op == 2){
int pos;
LL val;
cin >> pos >> val;
-- pos;
a[pos] += val;
id.insert(pos);
}else {
int pos;
cin >> pos;
-- pos;
cout << base + a[pos] << '\n';
}
}
return 0;
}
E - Grid Filling (abc278 e)
题目大意
给定一个矩形，格子上有数。
给定\(h,w\)，意味大小为\(h \times w\)的黑布，该黑布总矩形左上角向右移动，向下移动，直到右下角。问每个位置，将黑布的数遮盖后，剩下未被遮盖的不同的数的个数。
解题思路
暴力即可，黑布往右移动的时候，加上被遮住的一列，减去被遮住的一列。总的时间复杂度为\(O(n^3)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int H, W, N, h, w;
cin >> H >> W >> N >> h >> w;
vector<vector<int>> a(H, vector<int>(W));
vector<int> cnt(N + 1, 0);
int ans = 0;
for(auto &i : a)
for(auto &j : i){
cin >> j;
cnt[j] ++;
if (cnt[j] == 1)
++ ans;
}
vector<int> tmp(cnt.begin(), cnt.end());
int bac = ans;
for(int i = 0; i <= H - h; ++ i){
for(int j = i; j < i + h; ++ j)
for(int k = 0; k < 0 + w; ++ k){
cnt[a[j][k]] --;
if (cnt[a[j][k]] == 0)
-- ans;
}
cout << ans;
for(int j = 1; j <= W - w; ++ j){
for(int k = i; k < i + h; ++ k){
cnt[a[k][j - 1]] ++;
if (cnt[a[k][j - 1]] == 1)
++ ans;
}
for(int k = i; k < i + h; ++ k){
cnt[a[k][j + w - 1]] --;
if (cnt[a[k][j + w - 1]] == 0)
-- ans;
}
cout << ' ' << ans;
}
cout << '\n';
ans = bac;
cnt = tmp;
}
return 0;
}
F - Shiritori (abc278 f)
题目大意
给定\(n\)个字符串\(s\)， \(a\)和 \(b\)在玩。 \(a\)先手。
每个人说出一个\(1\)~\(n\)数字\(i\)，该数字必须是之前未说过的，且\(s_i\)的首字母和\(s_j\)的尾字母相同，其中 \(j\)是上一个人说过的数字。
问两者都是绝顶聪明的情况下，谁赢。
解题思路
设\(dp[s][i]\)表示目前已经选择的数字状态为 \(s\)，且最后说过的数字是 \(i\)，当前状态是必胜还是必输，枚举后继状态，直接搜索即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<vector<int>> edge(n);
vector<pair<int, int>> qwq;
for(int i = 1; i <= n; ++ i){
string s;
cin >> s;
qwq.push_back({s.front(), s.back()});
}
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
if (i == j)
continue;
if (qwq[i].second == qwq[j].first)
edge[i].push_back(j);
}
vector<vector<int>> dp((1 << n), vector<int>(n, -1));
function<int(int, int)> dfs = [&](int s, int la){
if (dp[s][la] != -1)
return dp[s][la];
int ok = 1;
for(auto nxt : edge[la]){
if ((s >> nxt) & 1)
continue;
ok &= dfs(s | (1 << nxt), nxt);
}
return dp[s][la] = (ok ^ 1);
};
int ok = 1;
for(int i = 0; i < n; ++ i){
ok &= dfs((1 << i), i);
}
if (!ok)
cout << "First" << '\n';
else
cout << "Second" << '\n';
return 0;
}
G - Generalized Subtraction Game (abc278 g)
题目大意
<++>
解题思路
<++>
神奇的代码
Ex - make 1 (abc278 h)
题目大意
<++>
解题思路
<++>
神奇的代码
标签：AtCoder,Beginner,int,cin,long,tie,278,using,qwq From： https://www.cnblogs.com/Lanly/p/16907585.html