A Securit

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
#include<bits/stdc++.h>
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main()
{
	std::string s;
	std::cin >> s;
	bool good = true;
  	for(int i = 1; i < s.size(); i++) {
    	good &= s[i] != s[i-1];
  	}
  	if(good) std::cout << "Good\n";
  	else std::cout << "Bad\n";
	return 0;
}

B Bite Eating

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
32
33
34
35
36
37
#include<bits/stdc++.h>
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main()
{
	int n = read(), l = read();
	std::vector<int> a(n);
	for(int i = 0; i < n; i++)
	{
		a[i] = l + i;
	}
	std::function<bool(int, int)> cmp = [&](int x, int y) {
		return std::abs(x) < std::abs(y);
	};
	std::sort(a.begin(), a.end(), cmp);
	int res = 0;
	for(int i = 1; i < a.size(); i++)
		res += a[i];
	std::cout << res << "\n";
	return 0;
}

C Anti-Division

求出$0x$中 $c,d$ 的非$c,d$倍数 的个数，利用前缀和的思想计算$ab$之间的数量
$$
res = n - \frac{n}{c} - \frac{n}{d} + \frac{n}{lcm(c, d)}
$$

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
32
33
34
#include<bits/stdc++.h>
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main()
{
	int a = read(), b = read(), c = read(), d = read();
	auto cal = [&](int x) -> int
	{
		int res = x;
		int t = (c * d) / std::__gcd(c, d);
		res -= x / c;
		res -= x / d;
		res += x / t;
		return res;	
	};
	std::cout << cal(b) - cal(a - 1);
	return 0;
}

D Megalomania

贪心，最短截止时间优先，感觉在考操作系统emmmm

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
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main()
{
	int n = read();
	std::vector<std::pair<int, int>> a(n);
	for(int i = 0; i < n; i++)
	{
		a[i].second = read(), a[i].first = read();
	}
	std::sort(a.begin(), a.end());
	int t = 0;
	for(int i = 0; i < n; i++)
	{
		t += a[i].second;
		if(t > a[i].first) 
		{
			std::cout << "No\n";
			return 0;
		}
	}
	std::cout << "Yes\n";
	return 0;
}

E Friendships

以一个点为中心，其余点全部与这个中心相连，这样是最多的情况点对数为
$$
\frac{(n - 1) * (n - 2)}{2}
$$
这样说明$k$不能超过这个数，否则无解

如果$k$ 小于这个数，小于多少，就在外围点之间连多少边，没连一条对应的点对就少一对

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main()
{
	int n = read(), k = read();
	if(2 * k > (n - 1) * (n - 2)) {
    	std::cout << "-1\n";
    	return 0;
  	}
  	std::vector<std::pair<int, int>> a;
  	int t = (n - 1) * (n - 2) / 2;
  	for(int i = 2; i <= n; i++)
  	{
  		a.push_back({1, i});
  	}
  	for(int i = 2; i < n; i++)
  		for(int j = i + 1; j <= n; j++)
  		{
  			if(t == k)
  			{
  				cout << a.size() << "\n";
  				for(auto x : a)
  				{
  					cout << x.first << " " << x.second << "\n";
  				}
  				return 0;
  			}
  			a.push_back({j, i});
  			t--;
  		}
  	cout << a.size() << "\n";
  	for(auto x : a)
  	{
  		cout << x.first << " " << x.second << "\n";
  	}
	return 0;
}

F Must Be Rectangular!

我也没太弄明白

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 1e5 + 10;

signed main()
{
    int n = read();
    vector<int> p(2 * N + 1);
    for(int i = 1; i <= 2 * N; i++) p[i] = i;
	function<int(int)> find = [&](int x)
    {
        return x == p[x] ? x : p[x] = find(p[x]);
    };
    for(int i = 0; i < n; i++)
    {
        int x = read(), y = read();
        x = find(x), y = find(y + N);
        if(x != y)
        {
            p[x] = y;
        }
    }
    vector<int> r(2 * N + 1), c(2 * N + 1);
    for(int i = 1; i <= N; i++)
        c[find(i)]++;
    for(int i = N + 1; i <= 2 * N; i++)
        r[find(i)]++;
    int res = 0;
    for(int i = 1; i <=  2 * N; i++)
        res += r[i] * c[i];
    std::cout << res - n << "\n";
    return 0;
}