A tcdr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string s;
	cin >> s;
	for(int i = 0; i < s.size(); i++)
	{
		if(s[i] == 'a' || s[i] == 'e' || s[i] == 'o' || s[i] == 'u' || s[i] == 'i') continue;
		cout << s[i];
	}
	return 0;
}

B The Middle Day

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
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int a = 1;
	int M, sum = 0;
	cin >> M;
	vector<int> D(M);
	for(int i = 0; i < M; i++) cin >> D[i], sum += D[i];
	sum = (sum + 1) / 2;
	for(int i = 0; i < M; i++)
	{
		if(sum > D[i])
		{
			sum -= D[i];
			a++;
		}
		else break;
	}
	cout << a << ' ' << sum;

	return 0;
}

C Flavors

选两杯，最优方案肯定是更小的除二，然后还有可能是口味相同的，所有按价值排序，然后遍历一遍就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);
	for(int i = 0; i < n; i++) cin >> a[i].second >> a[i].first;
	sort(a.begin(), a.end());
	int res = a[n - 1].first;
	int mx = -1;
	for(int i = n - 2; i >= 0; i--)
	{
		if(a[i].second == a[n - 1].second)
			mx = max(mx, a[i].first / 2);
		else
			mx = max(mx, a[i].first);
	}
	cout << res + mx;
	return 0;
}

D Magical Cookies

赛时没出纯粹的英语问题，全部相同才标记，我读成有就删了。我们统计当前行/列改字符有多少，这样就可以在O(26)次内检查一行或一列中 cookie 的颜色是否全部相同，删除的时候同时维护当前行列数和字符数

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
56
57
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int h, w;
	cin >> h >> w;
	vector<vector<char>> g(h, vector<char>(w));
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++) cin >> g[i][j];
	vector<vector<int>> x(h, vector<int>(26));
	vector<vector<int>> y(w, vector<int>(26));
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++)
		{
			x[i][g[i][j] - 'a']++;
			y[j][g[i][j] - 'a']++;
		}
	int hc = h, wc = w;
	vector<bool> fx(h), fy(w);
	for(int i = 0; i < (h + w) * 2; i++)
	{	
		vector<pair<int, int>> ux, uy;
		for(int j = 0; j < h; j++)
		{
			if(fx[j]) continue;
			for(int k = 0; k < 26; k ++ ) 
				if (x[j][k] == wc && wc >= 2)
					ux.push_back({ j, k });
		}

		for(int j = 0; j < w; j++)
		{
			if(fy[j]) continue;
			for(int k = 0; k < 26; k ++ ) 
				if (y[j][k] == hc && hc >= 2)
					uy.push_back({ j, k });
		}

		for (pair<int, int> p : ux) {
			fx[p.first] = true;
			for(int j = 0; j < w; j++) y[j][p.second]--;
			hc--;
		}
		for (pair<int, int> p : uy) {
			#if 0
			cout << "x\n";
			#endif
			fy[p.first] = true;
			for(int j = 0; j < h; j++) x[j][p.second]--;
			wc--;
		}
	}
	cout << hc * wc << '\n';
	return 0;
}

E Prerequisites

拓扑排序，然后记录入队顺序，反一下输出，还要先遍历一遍，处理出读了的书，因为有些书可以不读

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>

namespace solve {
    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;
    }

    void solve()
    {
        int n = read();
        std::vector<std::vector<int>> g(n, std::vector<int>());
        for(int i = 0; i < n; i++)
        {
            int x = read();
            for(int j = 0; j < x; j++)
            {
                int v = read();
                v--;
                g[i].emplace_back(v);
            }
        }

        auto tosport = [&]() -> std::vector<int> {
            std::vector<int> d(n);
            for(int i = 0; i < n; i++)
                for(auto x : g[i]) d[x]++;
            std::vector<int> res;
            std::queue<int> que;
            for (int i = 0; i < n; i++) if (d[i] == 0) que.push(i);
            while(que.size())
            {
                auto t = que.front();
                que.pop();
                res.push_back(t);
                for(int x : g[t])
                {
                    d[x]--;
                    if(d[x] == 0) que.push(x);
                }
            }
            return res;
        };

        std::queue<int> q;
        q.push(0);
        std::vector<bool> f(n + 1);
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            for (int i : g[t]) {
                if (!f[i]) {
                    f[i] = true;
                    q.push(i);
                }
            }
        }
        std::vector<int> t = tosport();
        std::vector<int> order(n);
        for(int i = 0; i < n; i++) order[t[i]] = i;
        std::sort(t.begin(), t.end(), [&](int x, int y) -> bool {
            return order[x] > order[y];
        });
        for(auto x : t) if(f[x]) std::cout << x  + 1 << " ";
    }


}

int main()
{
    std::ios::sync_with_stdio(0),std::cin.tie(0),std::cout.tie(0);
    solve::solve();
}

F Shortcuts

dp
$$
dp[i][j]，i表示当前是第几个点，j表示当前跳过的点的数目，dp值表示当前最小花费
$$
分析一下题目，当跳过点数变多，没多一个点就要付出成倍的代价，跳全部或者大部分点肯定划不来，所有我们可以控制一下跳过的个数最多为30，不放心可以多放一点，这样可以有效控制时间复杂度
$$
dp[i][j] = min(dp[k][i-k-1]+dis(k, j));
$$

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
56
57
58
59
#pragma GCC optimize(2)
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
namespace solve
{
	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;
    }

    void solve()
    {
    	int n = read();
    	std::vector<std::vector<double>> dp(n, std::vector<double>(30));
    	std::vector<std::pair<int, int>> a(n);
    	for(int i = 0; i < n; i++) a[i].first = read(), a[i].second = read();
    	for(int i = 0; i < n; i++)
    		for(int j = 0; j < 30; j++) dp[i][j] = 1000000000;
    	dp[0][0] = 0;
    	auto cal = [&](std::pair<int, int> x, std::pair<int, int> y) -> double {
    		return std::sqrt((x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second));
    	};
   		for(int  i = 0; i < n; i++)
   			for(int j = 0; j < 30; j++)
   				for(int k = i - 1; k >= i - j - 1 && k >= 0; k--)
   				{
   					dp[i][j] = std::min(dp[i][j], cal(a[k], a[i]) + dp[k][j - (i - k - 1)]);
   				}
    	double res = dp[n - 1][0];
        int cur = 1;
    	for(int i = 1; i < 30; i++)
    	{
    		res = std::min(res, dp[n - 1][i] + cur);
            cur <<= 1;
    	} 
    	printf("%.6f", res);
    }

}

int main()
{
	solve::solve();
	return 0;
}