水题，输出字符串中的大写字符
C++1
2
3
4
5
6
| void solve () {
char c;
while (cin >> c)
if (isupper(c))
cout << c;
}
|
考队列的题目
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void solve () {
int t; cin >> t;
queue<int> q;
while (t--) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
q.push(x);
}
else {
cout << q.front() << endl;
q.pop();
}
}
}
|
# 题目大意
现在有编号从 1 到 n 的 n 种配料，餐厅提供 m 道菜，每道菜使用了 Ki 种配料
初始时，你不喜欢所有的 n 种配料，你不能吃任意一种有你不喜欢的配料的菜
再接下来的 n 天中，每天你都会克服一种你不喜欢的配料，求在第 i 天克服之后，你能吃到多少道菜
# 数据范围
- 1≤N,M≤3×105
# 题解
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| void solve () {
cin >> n >> m;
vector<vector<int>> a(m + 1);
for (int i = 1, k; i <= m; i++) {
cin >> k;
for (int j = 1, b; j <= k; j++) {
cin >> b;
a[i].push_back(b);
}
}
map<int, int> mp;
for (int i = 1, t; i <= n; i++) {
cin >> t;
mp[t] = i;
}
vector<int> cnt(n + 1), cf(n + 1);
for (int i = 1; i <= m; i++) {
int res = 0;
for (int t : a[i])
res = max(res, mp[t]);
cf[res]++;
}
for (int i = 1; i <= n; i++) {
cf[i] += cf[i - 1];
cout << cf[i] << endl;
}
}
|
# 题目大意
一个圆上顺时针标明了等距离的 n 个点，现在有 m 条不同的线，第 i 条线经过了 ai 和 aj 点，问，有多少条相交的线
# 数据范围
- 2≤N≤106
- 1≤M≤3×105
# 题解
![]()
观察有，对于两条平行的线，其 (a + b) % n 是相同的，利用 map 记录
那么就可以遍历所有线，对于第 i 条线，前面有 i−1 条线，而 t = mp[(a + b) % n] 条线是和当前线平行的
故，会有 i - 1 - t 条线与当前这条新的线相交
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve () {
int res = 0;
map<int, int> mp;
cin >> n >> m;
for (int i = 1, a, b; i <= m; i++) {
cin >> a >> b;
int t = mp[(a + b) % n];
res += (i - 1 - t);
mp[(a + b) % n]++;
}
cout << res << endl;
}
|
# 题目大意
现在有 n 个题目，对于第 i 个题目，提交一次需要花费 Ci 元，第 i 个题目的分数是 Si，你解开第 i 个题目的概率是 Pi%
你现在有 x 元，请你计算你得分的期望的最大值是多少
# 数据范围
- 1≤N≤8
- 1≤Si≤2718
- 1≤Ci≤x≤5000
- 1≤Pi≤100
# 题解
