526互联

AtCoder Beginner Contest 304 ABCDE

发布时间 2023-06-04 12:12:08作者: magicat

AtCoder Beginner Contest 304

image
感觉手速场，后 \(80\) 分钟纯纯坐牢，

A - First Player

一些人坐成一个环，从年龄最小开始输出名字

const int N = 2e5 + 10;

int n;
string s[N];
int a[N];
void solve()
{   
    int m = 1e9 + 2, p = 1;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>s[i]>>a[i];
        if(m > a[i])
            m = a[i], p = i;
    }
    for(int i = p; i <= n; i++)
        cout<<s[i]<<'\n';
    for(int i = 1; i <= p - 1; i++)
        cout<<s[i]<<'\n';

    return;
}

B - Subscribers

对在范围内的数，将后几位变为0

void solve()
{   
    int n;
    cin>>n;
    if(n <= 1e3 - 1)
        cout<<n<<endl;
    else if(n <= 1e4 - 1)
        cout<<n / 10 * 10<<endl;
    else if(n <= 1e5 - 1)
        cout<<n / 100 * 100<<endl;
    else if(n <= 1e6 - 1)
        cout<<n / 1000 * 1000<<endl;
    else if(n <= 1e7 - 1)
        cout<<n / 10000 * 10000<<endl;
    else if(n <= 1e8 - 1)
        cout<<n / 100000 * 100000<<endl;
    else if(n <= 1e9 - 1)
        cout<<n / 1000000 * 1000000<<endl;
    return;
}

C - Virus

染病毒的点可以传染给欧几里得距离小于等于 \(d\) 的点，并查集 + 暴力dfs即可

int n, d, fa[N];
vector<pair<int, int>> a(2001);
int find(int x)
{
    if(fa[x] != x)      fa[x] = find(fa[x]);
    return fa[x];
}

void dfs(int u)
{
    int fu = fa[u];
    for(int i = 1; i <= n; i++)
    {
        int fv = find(i);
        int dis = (a[u].first - a[i].first) * (a[u].first - a[i].first) +
        (a[u].second - a[i].second) * (a[u].second - a[i].second);
        if(fu != fv && i != u && dis <= d)
        {
            fa[fv] = fu;
            dfs(i);
        } 
    }
}
 
void solve()
{   
    cin>>n>>d;
    d = d * d;
    for(int i = 1; i <= n; i++)
    {
        fa[i] = i;
        int x, y;	cin>>x>>y;
        a[i] = {x, y};
    }
    dfs(1);
    for(int i = 1; i <= n; i++)
        if(find(i) == 1)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    return;
}

D - A Piece of Cake

如何确定这块蛋糕有没有草莓，草莓左边的竖直方向切了一刀，上边的水平方向切了一刀，通过二分查找出分别是哪刀切的,通过竖直的刀和水平的刀确定这个蛋糕块，用个map<array<int, 2>, int> mp;记录，并将贡献加1。最后判断 \(\text{map.size()} = (A + 1) \times(B + 1)\)， 若相等，最小值为map中 \(\min\text{key}\)，否则为 \(0\)，最大值为 \(\max\text{key}\)

int n, m, k, a, b;
map<array<int, 2>, int> mp;
vector<pair<int, int>> p;
vector<int> A, B;
void solve()
{   
    cin>>n>>m>>k;
    for(int i = 1; i <= k; i++)
    {
        int x, y;   cin>>x>>y;
        p.push_back({x, y});
    }
    cin>>a;
    A.push_back(0), A.push_back(n);
    for(int i = 1; i <= a; i++)
    {
        int x;  cin>>x;
        A.push_back(x);
    }
    cin>>b;
    B.push_back(0), B.push_back(m);
    for(int i = 1; i <= b; i++)
    {
        int x;  cin>>x;
        B.push_back(x);
    }
    sort(A.begin(), A.end());	sort(B.begin(), B.end());
    for(auto &it : p)
    {
        int p1 = *lower_bound(A.begin(), A.end(), it.first);        
        int p3 = *lower_bound(B.begin(), B.end(), it.second);        
        array<int, 2> q = {p1, p3};
        mp[q]++;
    }
    int r1 = 1e9, r2 = 0;
    if((ll)mp.size() < (a + 1) * 1ll * (b + 1))
        r1 = 0;
    else
        for(auto &it : mp)
            r1 = min(r1, it.second);
    for(auto &it : mp)
        r2 = max(r2, it.second);
    cout<<r1<<" "<<r2<<'\n';
    return;
}

E - Good Graph

已给出好图，通过并查集确定各个连通块集合及编号。给出约束，两点不能有路径到达，用 \(\text{set}\) 记录两点分别属于哪个连通块。给出询问 \(u\), \(v\)；若 \(find(u)\) 与 \(find(v)\) 在 \(\text{set}\) 出现过，则输出\(\text{No}\) ，否则输出\(\text{Yes}\)。

int n, m, k, q, fa[N];
vector<int> e[N];
set<pair<int, int>> S;
 
int find(int x)
{
 	if(fa[x] != x)      fa[x] = find(fa[x]);
 	return fa[x];
}
 
void solve()
{   
	cin>>n>>m;
	for(int i = 1; i <= n; i++)
		fa[i] = i;
 
	for(int i = 1; i <= m; i++)
	{
		int u, v;	cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
		int fu = find(u), fv = find(v);
		if(fu != fv)
			fa[fu] = fv;
	}
 
	cin>>k;
	for(int i = 1; i <= k; i++)
	{
		int u, v;	cin>>u>>v;
		int fu = find(u), fv = find(v);
		S.insert({fu, fv});	S.insert({fv, fu});
	}
 
	cin>>q;
	for(int i = 1; i <= q; i++)
	{
		int u, v;	cin>>u>>v;
		int fu = find(u), fv = find(v);
		if(S.count({fu, fv}))
			cout<<"No\n";
		else
			cout<<"Yes\n";
    }
    return;
}

F - Shift Table

等等