AtCoder Beginner Contest 304 ABCDEF

Created on June 04, 2023

2023   ·   data structures   graph theory   dynamic programming   algorithm basics   contest

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

操作：

  1. (m) 为 (n) 的正约数，且 (m) 不为 (n)。
  2. 决定前 (m) 天哪些天上班，哪些天不上班。
  3. 排班由多个前 (m) 天的排班拼接而成，例如前 (m) 天排班是 (\text{010})，那么假设有 (9) 天，(n) 天的排班就是 (\text{010010010})。

你构造的排班，和给出的排班，要满足这 (n) 天中每天都有一人上班，不同的m可以构造出相同的排班表，问可以构造出多少不同的排班表满足条件。

对于每个约数 (m), (a) 为排班表， 若 (S_i = \text{.})，则 (a_{i\mod m}) 必须要上班，统计长度为 (m) 的排班表中不用上班的天数，计为 (cnt)，则这个约数都可以对答案产生 (2 ^ {cnt}) 的贡献，因为这 (\text{cnt}) 天中，每天可以上班或不上班。

但有个问题比如样例三：
(m = 3) 和 (m = 6), 构造出来的排版分别是 (\text{##.##.##.##.}) 和 (\text{…##….##.})， 任意放的过程中都可以放出 (\text{#####.##.##.}), 出现了重复的情况。但不难发现，(m = 6) 构造出的排班表可以完全覆盖了 (m = 3) 所构造出的排班表，所以答案不需要记录 (m = 3) 的情况。

也就是对于一个约数 (a)，若有 (b = k \times a)， 只需统计 (b) 对答案的贡献，但直接这样算很麻烦，直接在 (b) 的贡献中减去 (a) 的贡献即可。

ll qmi(ll a, ll b, ll mod)
{
	ll res = 1;
	while(b)
	{
		if(b & 1)	res = res * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return res;
}
ll f[N];
void solve()
{   
	int n;	cin>>n;
	string op;	cin>>op;
	ll res = 0;
	for(int i = 1; i < n; i++)
	{
		if(n % i != 0) continue;
		int a[i + 10]; memset(a, 0, sizeof a);
		int cnt = 0;
		for(int j = 0; j < n; j++)
			if(op[j] == '.')
				a[j % i] = 1;
		for(int j = 0; j < i; j++)
			if(a[j] == 0)
				cnt++;
		f[i] = qmi(2, cnt, mod);
		for(int j = 1; j < i; j++)
			if(i % j == 0)
				f[i] = (f[i] - f[j] + mod) % mod;
	}
	for(int i = 1; i < n; i++)
		res = (res + f[i]) % mod;
	cout<<res<<'\n';
    return;
}