A - Attack
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
signed main()
{
int a, b;
cin >> a >> b;
if (a % b == 0) cout << a / b << endl;
else cout << a / b + 1 << endl;
}B - Find snuke
就是按顺序找到s,n,u,k,e(水平或竖直或对角线)
模拟呗，先找到s再去判断，题目说只有唯一一组满足，那么就枚举所有的s，去找到一组符合要求的s,n,u,k,e
注意：别忘了对角线有两条，主对角线和副对角线，当时做的时候就考虑了主对角线导致没有AC
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 500;
struct node
{
string s;
}q[N];
int main()
{
int h, w;
cin >> h >> w;
for (int i = 0; i < h; i++) cin >> q[i].s;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (q[i].s[j] == 's') {
//水平往左
if (j - 4 >= 0) {
if (q[i].s[j - 1] == 'n' && q[i].s[j - 2] == 'u' && q[i].s[j - 3] == 'k' && q[i].s[j - 4] == 'e') {
for (int k = j; k >= j - 4; k--) cout << i+1 << " " << k+1 << endl;
return 0;
}
}
//水平往右
if (j + 4 < w) {
if (q[i].s[j + 1] == 'n' && q[i].s[j + 2] == 'u' && q[i].s[j +3] == 'k' && q[i].s[j + 4] == 'e') {
for (int k = j; k <= j + 4; k++) cout << i+1 << " " << k+1 << endl;
return 0;
}
}
//竖直向上
if (i - 4 >= 0) {
if (q[i-1].s[j] == 'n' && q[i-2].s[j] == 'u' && q[i-3].s[j] == 'k' && q[i-4].s[j] == 'e') {
for (int k = i; k >= i -4; k--) cout << k+1 << " " << j+1 << endl;
return 0;
}
}
//竖直向下
if (i +4 <h) {
if (q[i + 1].s[j] == 'n' && q[i + 2].s[j] == 'u' && q[i + 3].s[j] == 'k' && q[i +4].s[j] == 'e') {
for (int k = i; k <= i + 4; k++) cout << k+1 << " " << j+1 << endl;
return 0;
}
}
//向左上
if (i - 4 >=0&&j-4>=0) {
if (q[i -1].s[j-1] == 'n' && q[i- 2].s[j-2] == 'u' && q[i - 3].s[j-3] == 'k' && q[i - 4].s[j-4] == 'e') {
for (int k = 0; k <=4; k++) cout << i-k+1 << " " << j-k+1 << endl;
return 0;
}
}
//向右下
if (i + 4 <h && j + 4 <w) {
if (q[i + 1].s[j + 1] == 'n' && q[i + 2].s[j + 2] == 'u' && q[i + 3].s[j + 3] == 'k' && q[i+ 4].s[j + 4] == 'e') {
for (int k = 0; k <= 4; k++) cout << i + k + 1 << " " << j + k + 1 << endl;
return 0;
}
}
//向左下
if (i +4 <h && j - 4 >= 0) {
if (q[i + 1].s[j - 1] == 'n' && q[i + 2].s[j - 2] == 'u' && q[i + 3].s[j - 3] == 'k' && q[i + 4].s[j - 4] == 'e') {
for (int k = 0; k <= 4; k++) cout << i + k + 1 << " " << j - k + 1 << endl;
return 0;
}
}
//向右上
if (i - 4 >= 0 && j + 4 <w) {
if (q[i - 1].s[j + 1] == 'n' && q[i - 2].s[j + 2] == 'u' && q[i - 3].s[j + 3] == 'k' && q[i - 4].s[j + 4] == 'e') {
for (int k = 0; k <= 4; k++) cout << i - k + 1 << " " << j + k + 1 << endl;
return 0;
}
}
}
}
}
return 0;
}C - Almost Equal
大致题意就是n个长度相等的字符串，通过排列它们的顺序，使得所有两两相邻的字符串只有一个字符是不相同的，若可以输出Yes,否则输出No
最多只有8个字符串，可以进行一个dfs，枚举出所有的情况，若能够满足一种的话就输出Yes
类似于蓝桥杯第十届的题目组队，具体见第十届蓝桥杯c++b组_m0_74087709的博客-CSDN博客
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 50;
struct node {
string s;
}q[N];
int n, m;
bool flag[N];
int st[N];
bool flag1;
int cnt1;
void dfs(int x)
{
if (x <= n) {
for (int i = 0; i < n; i++) {
if (!flag[i]) {
st[x] = i;
flag[i] = true;
dfs(x + 1);
flag[i] = false;
}
}
}
else {
flag1 = true;
int cnt;
for (int i = 1; i <= n - 1; i++) {
cnt = 0;
for (int j = 0; j < m; j++)
if (q[st[i]].s[j] != q[st[i + 1]].s[j]) cnt++;
//cout << cnt << endl;
if (cnt != 1) {
flag1 = false;
break;
}
}
if (flag1) {
cnt1++;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> q[i].s;
dfs(1);
//cout << cnt1 << endl;
if (cnt1) puts("Yes");
else puts("No");
return 0;
}D - Impartial Gift
大致题意就是从N个礼物中选择一个礼物给Aoki,从M个礼物中选择一个礼物给Snuke，每个礼物都有相应的价值，求选择的两个礼物的差的绝对值小于等于D，求出它们总和价值的最大值，如果都不能满足差的绝对值小于等于D，就先输出-1
首先，任意选择，和顺序无关，那么可以先排个序，从小到大排序
1 3 3
2 6 7
可以用双指针，对于指针i,j，哪一个指针指的数小，就让另一个指针往右移动，如果大的指针移动不了，就将小的指针往右移动一格，要使得总和价值最大，那么肯定往右走，不会往左退的，每次res都取最大值
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N];
signed main()
{
int n, m, d;
cin >> n >> m >> d;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
sort(a, a + n);
sort(b, b + m);
int res = -1;
int i = 0;
int j = 0;
if (abs(a[0] - b[0]) <= d) res = a[0] + b[0];
while (i < n && j < m) {
if (a[i] < b[j]) {
if (abs(a[i] - b[j+1]) <= d&&j+1<m) j++;
else i++;
}
else {
if (abs(a[i+1] - b[j]) <= d&&i+1<n) i++;
else j++;
}
//cout << a[i] + b[j] << endl;
if (abs(a[i] - b[j]) <= d) res = max(res, a[i] + b[j]);
}
cout << res << endl;
}E - Isolation
大致题意就是有N个点，有q次操作，每次操作要么在两个点之间连一条边，要么删掉一个点的所有边(点不删掉，那么该点就变成孤立点了)，对于每一次操作，输出有多少个点是孤立的
核心在于一共有n个点，然后若知道有几个点是连了边的，用n减去其就可以了
那么如何判断该点是连了边还是没有连边呢？通过操作来看，如果是连边操作，那么将这两个点都标记为true，在标记之前，如果它们为false的话，那么就cnt++，表示连了边的点的个数；
如果是删边操作，那么将该点标记为false，在标记之前，如果它为true,那么cnt--
每次输出n-cnt
试了一下之后，发现思路错误，因为如果一开始只有2，3连了边，那么孤立点有1个，删掉2的边之后，孤立点变成了3个，所以删除2的边操作不能只删除一次
那么问题在于删了一个点的边之后，到底还有几个孤立点
错误代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 3e5 + 10;
int cnt;
bool flag[N];
int main()
{
int n, q;
cin >> n >> q;
while (q--) {
int x;
cin >> x;
if (x == 1) {
int u, v;
cin >> u >> v;
if (!flag[u]) {
cnt++;
flag[u] = true;
}
if (!flag[v]) {
cnt++;
flag[v] = true;
}
}
else {
int y;
cin >> y;
if (flag[y]) {
cnt--;
flag[y] = false;
}
}
cout << n - cnt << endl;
}
return 0;
}可以用set连边，若用数组模拟的话不好删边
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
using namespace std;
const int N = 3e5 + 10;
int n, q;
int op, u, v;
set<int>g[N];
int main()
{
cin >> n >> q;
int res = n;
while (q--) {
cin >> op;
if (op == 1) {
cin >> u >> v;
//如果在连边操作之前,点的边数为0的话,那么说明之前该点是孤立点，但是连边之后就不是了,则孤立点数减1
if (!g[u].size()) res--;
if (!g[v].size()) res--;
//将u,v两个点连起来
g[u].insert(v);
g[v].insert(u);
}
else {
cin >> v;
//利用x遍历并获得v容器中的每一个值,即x表示点v所连的点
for (auto x : g[v]) {
g[x].erase(v);//对于点x,把点v与x之间的边删掉
if (!g[x].size()) res++;//如果删边操作后,点x的边数为0,那么孤立点数+1
}
if (g[v].size()) res++;//在删边操作之前,如果点v的边数不为0，那么孤立点+1
g[v].clear();//删除点v的所有边，清空操作
}
cout << res << endl;
}
return 0;
}
