给定一个长度为 的序列 。
按原顺序打印 中的所有偶数。
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, x;
cin >> n;
while (n--)
{
cin >> x;
if (x % 2 == 0)
cout << x << " ";
}
return 0;
}
给定一个 的矩阵 ,仅包含整数 。第 行第 列的元素为 。
打印一个 的字符画,如果 为 就在 第 行第 列打印 .
,否则打印第从 A
开始的第 个大写英文字母。
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int H, W;
cin >> H >> W;
for (int i = 1; i <= H; i++)
{
for (int j = 1; j <= W; j++)
{
int x;
cin >> x;
if (x == 0)
cout << ".";
else
cout << (char)(x - 1 + 'A');
}
cout << "\n";
}
return 0;
}
给定两个严格递增的序列,长度分别为 和 : 和 。对于任意的 ,保证 。
请将两个序列有序合并成新序列 。
然后输出两个序列的每个元素分别是 序列的第几个元素。
合并后二分查找()或者合并时记录()皆可,这题两个做法都能过(虽然后者是复杂度低得多)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 100000;
int n, m;
int a[MAXN + 5];
int b[MAXM + 5];
int c[MAXN + MAXM + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
int pa = 1, pb = 1, pc = 1;
while (pa <= n && pb <= m)
{
if (a[pa] <= b[pb])
c[pc++] = a[pa++];
else
c[pc++] = b[pb++];
}
while (pa <= n)
c[pc++] = a[pa++];
while (pb <= m)
c[pc++] = b[pb++];
for (int i = 1; i <= n; i++)
cout << lower_bound(c + 1, c + pc, a[i]) - c << " ";
cout << "\n";
for (int i = 1; i <= m; i++)
cout << lower_bound(c + 1, c + pc, b[i]) - c << " ";
cout << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 100000;
int n, m;
int a[MAXN + 5];
int b[MAXM + 5];
int c[MAXN + MAXM + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
int pa = 1, pb = 1, pc = 1;
while (pa <= n && pb <= m)
{
if (a[pa] <= b[pb])
{
c[pc] = a[pa];
a[pa] = pc;
pa++, pc++;
}
else
{
c[pc] = b[pb];
b[pb] = pc;
pb++, pc++;
}
}
while (pa <= n)
{
c[pc] = a[pa];
a[pa] = pc;
pa++, pc++;
}
while (pb <= m)
{
c[pc] = b[pb];
b[pb] = pc;
pb++, pc++;
}
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << "\n";
for (int i = 1; i <= m; i++)
cout << b[i] << " ";
cout << "\n";
return 0;
}
编号为 的 个人正在银行排队。
接下来有 次事件,每次事件为下面三种类型之一:
1
:广播通知当前编号最小的、没被通知过的人(来办理业务)。2 x
:已经被通知过的编号为 x
的人来办理业务了。3
:广播再次通知已经被通知过的人中、编号最小的、还没来办理业务的人来办理业务。请输出每次 3
事件广播通知的编号。
开两个普通队列分别按顺序记录还没被叫过号的人,和已经被交过号的人就可以很方便处理。需要额外开一个 bool
数据来判断已经被叫过号的人有没有来办理业务。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, Q;
queue<int> q1; // 还没被叫号的人
queue<int> q2; // 已经被叫过号了的人
bool vis[MAXN + 5]; // 每个人是否已经来处理业务了
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> Q;
for (int i = 1; i <= n; i++)
q1.push(i), vis[i] = false;
while (Q--)
{
int op, x;
cin >> op;
if (op == 1)
{
q2.push(q1.front());
q1.pop();
}
else if (op == 2)
{
cin >> x;
vis[x] = true;
}
else if (op == 3)
{
while (vis[q2.front()])
q2.pop();
cout << q2.front() << "\n";
}
}
return 0;
}
给定一个 行 列的表格。第 行第 列上写了一个数字 。
求有多少个 满足 。
为了增加问题的难度,这里并没有直接给你表格,而是给你关于表格的压缩。
分别被压缩成了长度为 的两个串:
指的是 这个元素在这里重复了 次。
按题意一段段模拟就好。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int L, N1, N2;
int v1[MAXN + 5], l1[MAXN + 5];
int v2[MAXN + 5], l2[MAXN + 5];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> L >> N1 >> N2;
for (int i = 1; i <= N1; i++)
cin >> v1[i] >> l1[i];
for (int i = 1; i <= N2; i++)
cin >> v2[i] >> l2[i];
int ans = 0;
// 当前是从第 i 个数开始
// 第一行的开头是 l1[now1] 个 v1[now1]
// 第二行的开头是 l2[now2] 个 v2[now2]
int i = 1, now1 = 1, now2 = 1;
while (i <= L)
{
// 可以比较的长度
int len = min(l1[now1], l2[now2]);
// 比一比
if (v1[now1] == v2[now2])
ans += len;
// 去掉比过了的部分
l1[now1] -= len;
l2[now2] -= len;
if (l1[now1] == 0)
now1++;
if (l2[now2] == 0)
now2++;
i += len;
}
cout << ans << "\n";
return 0;
}
Taka 和 Aoki 分别有 瓶和 瓶糖水。
Taka 的第 瓶糖水由 克糖和 克水组成。
Aoki 的第 瓶糖水由 克糖和 克水组成。
如果从两个人的糖水中分别各选一瓶混合,那么有 种方案。请找到这 种糖水中浓度第 高的。
这里我们规定:假设有 克糖和 克水,那么浓度是百分之 。
这里不考虑物理中的一些显示情况(比如饱和度概念是不考虑的,一吨糖一克水也能溶)。
考虑二分答案,对于一个确定的浓度 来判断第 大的浓度时小于 还是大于 :
首先预处理: 预处理出每瓶糖水多了多少糖(缺糖就是多了负数的糖)。然后 给 Aoki 的缺糖数量排序。
进阶这枚举 Taka 的每瓶糖水:对于每瓶糖水都可以 找到 Aoki 那有哪些可以组合出超过 浓度的。这样就能 来判断正确答案在 的哪边了。
需要注意,如果一瓶糖水有 克糖, 克水,如果需要 浓度,那么正确的糖数应该满足:,即 ,进而 。那么多的糖就是 。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 50000;
int n, m, k;
struct Suger
{
int p, q; // p/q
double more;
} a[MAXN + 5], b[MAXN + 5];
bool cmpMore(const Suger &a, const Suger &b)
{
// a.p/a.q > b.p/b.q
return a.more > b.more;
}
bool check(double x)
{
for (int i = 1; i <= n; i++)
a[i].more = a[i].p - x * a[i].q / (1 - x);
for (int i = 1; i <= m; i++)
b[i].more = b[i].p - x * b[i].q / (1 - x);
sort(b + 1, b + m + 1, cmpMore);
int cnt = 0; // 有 cnt 种方案浓度大于 x
for (int i = 1; i <= n; i++)
{
double ned = -a[i].more;
int l = 1;
int r = m;
int ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (b[mid].more >= ned)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cnt += ans;
}
return cnt >= k;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
cin >> a[i].p >> a[i].q;
for (int i = 1; i <= m; i++)
cin >> b[i].p >> b[i].q;
double l = 0;
double r = 1;
while (r - l >= 1e-14)
{
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
cout << fixed << setprecision(12) << l * 100 << "\n";
return 0;
}