对于下面的表格,判断给定的两个整数 是否在同一行。
1 | 2 | 3 |
---|---|---|
4 | 5 | 6 |
7 | 8 | 9 |
#include <bits/stdc++.h>
using namespace std;
int f[10] = {4, 1, 1, 1, 2, 2, 2, 3, 3, 3};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a, b;
cin >> a >> b;
if (f[a] == f[b])
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
给定一个 的网格 , 为 或 。
将边框的所有数顺时针绕一圈后输出。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int n;
char a[MAXN + 5][MAXN + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == 1 && j > 1)
cout << a[i][j - 1];
else if (i == n && j < n)
cout << a[i][j + 1];
else if (j == 1 && i < n)
cout << a[i + 1][j];
else if (j == n && i > 1)
cout << a[i - 1][j];
else
cout << a[i][j];
}
cout << "\n";
}
return 0;
}
有 种药,第 种药需要吃 天,每天吃 片。
从今天开始吃药,问哪天开始需要吃的药小于等于 颗。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 300000;
int n, k, sum;
pair<int, int> a[MAXN + 5];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i].first >> a[i].second;
sum += a[i].second;
}
sort(a + 1, a + n + 1);
if (sum <= k)
{
cout << "1\n";
return 0;
}
for (int i = 1; i <= n; i++)
{
sum -= a[i].second;
if (sum <= k)
{
cout << a[i].first + 1 << "\n";
return 0;
}
}
return 0;
}
给定一个无向图,包含 个点和 条边。
题目保证:
你可以选两个点并连通这两个点,使得 到 的距离尽可能远。
求最远能使它们有多远。
找到原图中距离 最远的点的距离,以及距离 最远的点的距离。答案就是两个距离之和加 .
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150000 * 2;
const int INF = MAXN + 5;
int n1, n2, n, m;
vector<int> e[MAXN + 5];
int dis1[MAXN + 5], disN[MAXN + 5];
queue<int> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n1 >> n2 >> m;
n = n1 + n2;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= n; i++)
dis1[i] = disN[i] = INF;
// 到 1 最远、到 2 最远
int max1 = 0, maxN = 0;
// 1 to other
dis1[1] = 0;
q.push(1);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v : e[u])
if (dis1[u] + 1 < dis1[v])
{
dis1[v] = dis1[u] + 1;
max1 = max(max1, dis1[v]);
q.push(v);
}
}
// n to other
disN[n] = 0;
q.push(n);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v : e[u])
if (disN[u] + 1 < disN[v])
{
disN[v] = disN[u] + 1;
maxN = max(maxN, disN[v]);
q.push(v);
}
}
// ans
cout << max1 + maxN + 1 << "\n";
return 0;
}
有 共 个人,第 个人的父亲是 .
他们买了 次保险,第 次保险保障了 及其 代以内的子孙。
求有多少人被保障了。
建树、从根节点往下搜就好。如果父节点有保障 代的保险,自己只有保障 代的保险,那么相当于自己有保障 代的保险。这样往下优先保留大的覆盖下去就好。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000;
const int MAXM = 300000;
int n, m;
int fa[MAXN + 5];
vector<int> e[MAXN + 5];
int cover[MAXN + 5];
void dfs(int u)
{
for (int v : e[u])
{
cover[v] = max(cover[v], cover[u] - 1);
dfs(v);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 2; i <= n; i++)
{
cin >> fa[i];
e[fa[i]].push_back(i);
}
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
cover[x] = max(cover[x], y + 1);
}
dfs(1);
int cnt = 0;
for (int i = 1; i <= n; i++)
cnt += (cover[i] > 0);
cout << cnt << "\n";
return 0;
}
给定 个盒子,第 个盒子的长宽高分别为 。
问是否存在两个盒子满足,一个盒子的长宽高都严格大于另一个盒子。注意这里看每个盒子的视角都是任意的,即可以任意调换长宽高。
首先每个盒子都可以把长宽高排序。一个盒子如果能装下另一个盒子,就等价于排序后的长宽高分别相等。
现在就是找是否存在严格三位偏序的点对。
可以按照长排序,然后从小到大一个个看过去。这样就很容易找到长小于当前盒子的盒子是哪些。第一维的偏序就天然解决了。
紧接着需要统计这些长小于 的盒子中,每种宽存在的最小的高是多少。
假设当前是第 个盒子,那么宽在 范围内的盒子前两维都满足偏序了,只要看这个区间对应的高度最小值是否小于 即可。
显然离散化后,这就成了一个单点修改、前缀最小值查询的问题。用树状数组或者线段树做就好。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int INF = MAXN * 3 + 5;
int n;
struct Box
{
int h, w, d;
};
bool operator<(const Box &x, const Box &y)
{
if (x.h != y.h)
return x.h < y.h;
if (x.w != y.w)
return x.w < y.w;
return x.d < y.d;
}
Box a[MAXN + 5];
// 不去重离散化
vector<int> temp;
// 前缀最小值树状数组
int lowbit(int x)
{
return x & (-x);
}
int maxNum, t[MAXN * 3 + 5]; // t[离散化后的w] = min(对应的d的最小值)
void update(int x, int y)
{
for (int i = x; i <= maxNum; i += lowbit(i))
t[i] = min(t[i], y);
}
int query(int x)
{
int res = INF;
for (int i = x; i >= 1; i -= lowbit(i))
res = min(res, t[i]);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].h >> a[i].w >> a[i].d;
if (a[i].h > a[i].w)
swap(a[i].h, a[i].w);
if (a[i].h > a[i].d)
swap(a[i].h, a[i].d);
if (a[i].w > a[i].d)
swap(a[i].w, a[i].d);
temp.push_back(a[i].h);
temp.push_back(a[i].d);
temp.push_back(a[i].w);
}
sort(temp.begin(), temp.end());
for (int i = 1; i <= n; i++)
{
a[i].h = lower_bound(temp.begin(), temp.end(), a[i].h) - temp.begin() + 1;
a[i].w = lower_bound(temp.begin(), temp.end(), a[i].w) - temp.begin() + 1;
a[i].d = lower_bound(temp.begin(), temp.end(), a[i].d) - temp.begin() + 1;
maxNum = max(maxNum, a[i].h);
maxNum = max(maxNum, a[i].w);
maxNum = max(maxNum, a[i].d);
}
sort(a + 1, a + n + 1);
// 初始化树状数组
for (int i = 1; i <= maxNum; i++)
t[i] = INF;
// work
int ph = 0; // a[1].h~a[ph].h < a[now].h
for (int now = 1; now <= n; now++)
{
while (ph + 1 < now && a[ph + 1].h < a[now].h)
{
ph++;
update(a[ph].w, a[ph].d);
}
if (ph < 1)
continue;
int minD = query(a[now].w - 1);
if (minD < a[now].d)
{
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
return 0;
}