敌人的耐力值为 ,每次攻击可以使其耐力值减少 点。问最少多少次攻击可以使敌人的耐力减少到 或更低。
.
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a, b;
cin >> a >> b;
cout << (a / b + (a % b > 0)) << "\n";
return 0;
}
给定一个 行 列的字符画,请判断字符画里面是否存在 snuke
。
如果某个字符为 s
,并且沿着八个方向(上、下、左、右、左上、左下、右上、右下)的某个方向连续 个字符分别为 s,n,u,k,e
。那么就认为存在 snuke
。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int h, w;
char g[120][120];
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> h >> w;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
cin >> g[i + 5][j + 5];
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
{
if (g[i + 5][j + 5] == 's')
{
for (int p = 0; p < 8; p++)
{
string s = "";
for (int k = 0; k < 5; k++)
s += g[i + k * dx[p] + 5][j + k * dy[p] + 5];
if (s == "snuke")
{
for (int k = 0; k < 5; k++)
cout << i + k * dx[p] << " " << j + k * dy[p] << "\n";
return 0;
}
}
}
}
return 0;
}
给定 个字符串互不相同的。问能否重新排列着 个字符串的顺序,使得任意两个相邻的字符串 之间都满足: 可以通过修改不超过一个字符而等于 。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, len;
string s[10];
int p[10];
bool check(string &s1, string &s2)
{
int cnt = 0;
for (int i = 0; i < len; i++)
{
if (s1[i] != s2[i])
{
cnt++;
if (cnt > 1)
return false;
}
}
return true;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> len;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
p[i] = i;
}
do
{
bool flag = true;
for (int i = 1; i <= n - 1; i++)
{
if (!check(s[p[i]], s[p[i + 1]]))
{
flag = false;
break;
}
}
if (flag)
{
cout << "Yes\n";
return 0;
}
} while (next_permutation(p + 1, p + n + 1));
cout << "No\n";
return 0;
}
Taka 想要给 Aoki 和 Snuk 各送一个礼物。
备选的给 Aoki 的礼物有 个,价值分别为
备选的给 Snuk 的礼物有 个,价值分别为
要求给两个人的礼物价值之差不能超过 。问给两个人的礼物价值之和最大为多少?
枚举给 Aoki 送哪个礼物,即可二分找到给 Snuk 送的礼物最大价值为多少。
当然也可以双指针进一步降低时间复杂度。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, d;
int a[212345];
int b[212345];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> d;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
for (int i = n; i >= 1; i--)
{
int p = lower_bound(b + 1, b + m + 1, a[i] + d + 1) - b;
if (p == 1)
continue;
int nowB = b[p - 1];
if (nowB >= a[i] - d)
{
cout << a[i] + nowB << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}
有 个点,初始没有边。有 次操作,分为两类:
1 u v
:給 u,v
之间连上边2 v
: 删掉所有与 v
相连的边求每次操作后,有多少个点是没有与其他点相连的。
记录每个点的度数 D[i]
,对于 1
操作,如果操作之前 D[u]
为 0
,那么操作后答案就要减少 1
。对于 D[v]
也一样。
难点在于 2
操作,如果我们用 vector<int> e[MAXN+5]
存图,那么度 v
这边的修改很简单,e[v].clear(),d[v]=0
即可。重点在于删除的每条边都要给对面的点度数减少 1
。并且给 e[对面]
中删除这条边。这个删除操作显然是比较复杂的,所以我这里采用的是 map<int, int> e[MAXN+5]
来记录两个点之间有几条边相连,这样就可以方便得删边加边和修改度数了。
当然这题也可以直接用 set
存连接关系,就不用想这么多了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, t, ans;
int d[312345];
map<int, int> e[312345];
vector<int> ee[312345];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> t;
ans = n;
while (t--)
{
int op, x, y;
cin >> op;
if (op == 1)
{
cin >> x >> y;
if (d[x] == 0)
ans--;
if (d[y] == 0)
ans--;
d[x]++;
d[y]++;
e[x][y]++;
e[y][x]++;
ee[x].push_back(y);
ee[y].push_back(x);
cout << ans << "\n";
}
if (op == 2)
{
cin >> x;
if (d[x] > 0)
{
ans++;
d[x] = 0;
}
for (int i = 0; i < ee[x].size(); i++)
{
int y = ee[x][i];
if (e[x][y] > 0)
{
e[x][y]--;
e[y][x]--;
d[y]--;
if (d[y] == 0)
ans++;
}
}
ee[x].clear();
cout << ans << "\n";
}
}
return 0;
}
有 个集合 。每个集合里面的数都是在 范围内的。
如果有两个集合包含同一个元素,那么就可以合并这两个集合。
求至少需要几次合并就可以使某个集合同时包含 和 。
首先要看清楚题目,只需要包含 和 这两个元素即可。
抽象建图。把每个数都当作一个点(编号 ),每个集合都看作一个点(编号 )。如果集合 中含有整数 ,那么可以它们对应的点连一条边。
这样图上的路径必然都是点和集合交替(二分图),从点 到点 的最短路径就是集合合并的路径了。 就是最少需要合并的集合数。 就是需要几次合并操作。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[212345];
vector<int> e[412345];
queue<int> q;
bool vis[412345];
int dis[412345];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int ai;
cin >> ai;
for (int j = 1; j <= ai; j++)
{
int x;
cin >> x;
e[x].push_back(i + m);
e[i + m].push_back(x);
}
}
memset(vis, false, sizeof(vis));
memset(dis, -1, sizeof(dis));
q.push(1);
vis[1] = true;
dis[1] = 0;
while (!q.empty() && !vis[m])
{
int u = q.front();
q.pop();
for (auto v : e[u])
{
if (vis[v])
continue;
vis[v] = true;
dis[v] = dis[u] + 1;
q.push(v);
}
}
if (dis[m] == -1)
cout << dis[m];
else
cout << dis[m] / 2 - 1;
return 0;
}
给一个长度为 的序列 。保证 。每次可以任选两个数交换,问最少几次交换可以完成不降的排序。
显然计数后可以知道最终局面的划分,进而知道每个数的范围内有多少个其他的数。
可以用 e[i][j]
表示 i
的范围内有多少个 j
。
显然所有的 e[i][i]
的情况都不用动。
那么 now = min(e[x][y],e[y][x])
实际上就描述了 x,y
构成的二元环有几个,这些二元环每个都只需要依次交换就能完成有序,显然这也是最佳选择。如果存在这样的二元环必然优先处理这样的二元环。
处理完二元环后把三元环四元环依次处理。即可得到答案。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, ans;
int cnt[212345];
int a[212345];
int e[5][5];
// 四连环
void cal(int a, int b, int c, int d)
{
int now = min(min(e[a][b], e[b][c]), min(e[c][d], e[d][a]));
ans += now * 3;
e[a][b] -= now;
e[b][c] -= now;
e[c][d] -= now;
e[d][a] -= now;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
cnt[a[i]]++;
}
cnt[0] = 0;
for (int i = 2; i <= 4; i++)
cnt[i] += cnt[i - 1];
// i: cnt[i-1]+1 ~ cnt[i]
for (int now = 1; now <= 4; now++)
for (int i = cnt[now - 1] + 1; i <= cnt[now]; i++)
e[now][a[i]]++;
/*
for (int i = 1; i <= 4; i++)
{
for (int j = 1; j <= 4; j++)
cout << e[i][j] << " ";
cout << "\n";
}
*/
ans = 0;
// 正确的不管
for (int i = 1; i <= 4; i++)
e[i][i] = 0;
// 一次操作
for (int i = 1; i <= 4; i++)
for (int j = i + 1; j <= 4; j++)
{
int now = min(e[i][j], e[j][i]);
ans += now * 1;
e[i][j] -= now;
e[j][i] -= now;
}
// 两次操作的三连环
for (int i = 1; i <= 4; i++)
for (int j = i + 1; j <= 4; j++)
for (int k = j + 1; k <= 4; k++)
{
int now;
now = min(min(e[i][j], e[j][k]), e[k][i]);
ans += now * 2;
e[i][j] -= now;
e[j][k] -= now;
e[k][i] -= now;
now = min(min(e[i][k], e[k][j]), e[j][i]);
ans += now * 2;
e[i][k] -= now;
e[k][j] -= now;
e[j][i] -= now;
}
// 三次操作的四连环
// 2 3 4 1
// 2 4 3 1
// 3 2 4 1
// 3 4 2 1
// 4 2 3 1
// 4 3 2 1
cal(2, 3, 4, 1);
cal(2, 4, 3, 1);
cal(3, 2, 4, 1);
cal(3, 4, 2, 1);
cal(4, 2, 3, 1);
cal(4, 3, 2, 1);
cout << ans << "\n";
return 0;
}