Atcoder ABC402游记

Atcoder ABC399游记（A~D）

66 你们D都用余数性质 只有我画图死推两个端点十八

A.CBC

题目描述

给你一个字符串，把它的大写字母维持原来的顺序输出。

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		if (isupper(s[i])) {
			cout << s[i];
		}
	}
	return 0;
}

B.Ranking with Ties

题目描述

给你$Q$次操作，每次操作分两种：

1. 1 x 将编号为$x$的人插入到队尾

2. 2 输出队首并弹出

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	queue<int> que;
	int T;
	cin >> T;
	while (T--) {
		int ch;
		cin >> ch;
		if (ch == 1) {
			int x;
			cin >> x;
			que.push(x);
		} else {
			cout << que.front() << '\n';
			que.pop();
		}
	}
	return 0;
}

C.Make it Forest

题目描述

餐厅使用 $N$ 种食材，编号从 $1$ 到 $N$ 。

餐厅提供 $M$ 道菜，编号从 $1$ 到 $M$ 。菜肴 $i$ 使用了 $K_i$ 种食材，即 $A_ {i,1}, A_ {i,2}, \ldots, A_{i,K_i}$ 。

一个人目前不喜欢所有的 $N$ 食材。他不能吃使用了一种或多种他不喜欢的食材的菜肴，但他可以吃不使用任何不喜欢的食材的菜肴。

在接下来的 $N$ 天里，他将每天克服一种不喜欢的食材。在第 $i$ 天，他克服了第 $B_ i$ 种配料，从此他就不再不喜欢这种配料了。

求每种 $i=1,2,\ldots,N$ 的数量：

• 在第$i$天克服食材 $B_i$ 后，他可以立即在餐厅吃到的菜肴的数量。

思路

我说不是哥们，这$N$和$M$都可以到3e5，你让我怎么跑进2秒

然后我就对样例干瞪眼半天，又试了各种方法都不行，不能跑进2秒

直到我看到：K的总和不会超过3e5

想攻击出题人

代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> a;
int cnt[333333];
vector<int> v[333333];
int main()
{
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		vector<int> tp;
		int x;
		cin >> x;
		cnt[i] = x;
		while (x--) {
			int ttp;
			cin >> ttp;
			tp.push_back(ttp);
			v[ttp].push_back(i);
		}
		a.push_back(tp);
	}
	int ans = 0;
	while (m--) {
		int x;
		cin >> x;
		for (int i = 0; i < v[x].size(); i++) {
			cnt[v[x][i]]--;
			if (cnt[v[x][i]] == 0) {
				ans++;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

D. Line Crossing

题目描述

在一个顺时针标为 $1,2,\ldots,N$ 的圆上有 $N$ 个等距点。

有 $M$ 条不同的线，其中 $i$ 条线经过两个不同的点 $A_i$ 和 $B_i$ 。 $(1 \leq i \leq M)$ .

求满足条件的线对 $(i,j)$ 的个数：

• 1 \le i < j \le M ，且
• $i$ 线与 $j$ 线相交。

思路

第一眼数学题，算斜率，然后在tld上推了半天公式，连三角函数都想到了，结果样例过不了，一堆分讨

第二眼想到可以对于每个线算出与其平行的线数量，然后就想到可以把两个端点一直往同一个方向推，得到的不能推的作为这一类线的代表线

看似很好写，然后去tld上画了半天，发现偶数简单，奇数简直比上一个还要难写，对着样例发愣半天（主要是没有办法画精确，所以有一大堆误判的平行，找到错误的规律又过不了样例）

还剩几分钟的时候发现同一类线段两个端点编号之和模$N$居然相等，然后就过了

啊啊啊啊啊不是哥们

布什戈门

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> cnt(n, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int sum = a + b;
        int r = sum % n;
        cnt[r]++;
    }
    int ans = m * (m - 1) / 2;
    int tp = 0;
    for (int i = 0; i < n; i++) {
        int c = cnt[i];
        tp += c * (c - 1) / 2;
    }
    
    cout << (ans - tp);
    return 0;
}

F.Path to Integer

记忆化得了mvp，dp就是躺赢狗

啊啊啊我怎么没看f啊