N Nine Is Greater Than Ten

按字典序比较字符串

1
2
3
4
5
6
7
8
9
10
void solve(){
	string a,b;
	cin>>a>>b;
	int res = a.compare(b);
	if(res == 0){
		cout<<a<<'='<<b<<endl;
	}else if(res < 0){
		cout<<a<<'<'<<b<<endl;
	}else cout<<a<<'>'<<b<<endl;
}

G Gua!

题意：
给你四个参数B R D S,表示枪的一发子弹造成的最大伤害，射速为每分钟射击R次，玩家一共造成了D点伤害，用时S秒，问你这个人是不是挂。
不是很懂为什么签到题出这么细节的模拟……vp爆wa心态都炸了
三个细节，
第一个是由于时间是从0开始算的，打出去的子弹数还要在加上1。
第二个是如果这把武器的射速是0，那么玩家造成伤害了就一定是挂。
第三个是如果武器要对射出去的子弹数向下取整，那么就是R*S/60，注意在这里R/60*S是错的。

1
2
3
4
5
6
7
8
void solve() {
    int b, r, d, s;
	cin >> b >> r >> d >> s;
	if (r == 0 || b == 0) 
		if (d) return cout << "gua!" << endl, void();
	if ((r * s / 60 + 1) * b < d) cout << "gua!" << endl;
	else cout << "ok" << endl;
}

H Heirloom Painting

艺术大师咖波有一个绘画机器人，用来帮助他制作一些精美的艺术品。 这天，咖波画了一个圆环，并将其分割成了 n 个格子。咖波总共调制了 m 种颜色，他希望用这些颜色 给圆环涂上色，从而画成一件新的艺术品。然而，当初出于成本的考虑，他的绘画机器人有很多技术上 的限制，比如的喷嘴是一个年久失修的传家宝，这导致他的机器人每次只能给连续的恰好 k 个格子涂上 颜色。幸好机器人使用的颜料并不会因为重复覆盖同一个格子而混合——后面涂上的颜色将取代此前的 颜色。 现在，咖波想知道他的机器人最少需要涂多少次颜色才能将这个圆环画成他想要的样子。当然，也有可 能他的笨笨机器人其实没法完成任务。
对于每组数据，输出一行包含一个整数，表示机器人最少涂色次数。如果机器人无法完成任务，输出 −1。

大概就是一个模拟，首先考虑什么时候无解：
显然，最终序列如果没有长度为k个的连续的颜色，那么一定是无解的
否则，就把相同颜色的连续位置合并成一个元素，记录连续的块数，然后就贪心的去染色，令连续的数量是cnt，那么喷的次数就是cnt/k + (cnt%k != 0)。
注意因为是一个环，所以要判断最后一个色块的颜色和第一个是不是一样的。

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
void solve(){
	int n,m,k;
	cin>>n>>m>>k;
	vector<int> c(n+1);
	for(int i = 1;i<=n;++i) cin>>c[i];

	vector<array<int,2>>v;	
	int cnt=1;
	for(int i = 2;i<=n;++i){
		if(c[i]!=c[i-1]){
			v.push_back({c[i-1],cnt});
			cnt=1;
		}else cnt++;
	}
	
	v.push_back({c[n],cnt});
	
//	判断最后一个色块的颜色和第一个是不是一样
	if(v.size()>=2 and v[v.size()-1][0]==v[0][0]){
		v[0][1]+=v[v.size()-1][1];
		v.pop_back();
	}
	
	bool havans=false;
	
	for(auto [color,cnt]:v)
		if(cnt>=k)
			havans=true;
	
	if(havans==false)
		return cout<<-1<<endl,void();
	
	int ans=0;
	for(auto [color,cnt]:v)
		ans += cnt/k + (cnt%k != 0);
	cout<<ans<<endl;
}

A Another A+B Problem

逆天枚举模拟，队友代码

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
88
89
90
91
#define per(i, j, k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i, j, k) for(int (i)=(j);(i)>=(k);--(i))

int num[7];//1~6位置上必须是哪些数,-1为不固定
int canot[7];//1~6位置上,不能放

int purple[10];
int black[10];
int leave[10];

void solve() {
    string E, C;
    cin >> E >> C;

    string s = "";
    s += "O", s += C[0], s += C[1], s += C[3], s += C[4], s += C[6], s += C[7];
    C = s;
    s = "";
    s += "O", s += E[0], s += E[1], s += E[3], s += E[4], s += E[6], s += E[7];
    E = s;

    per(i, 1, 6) num[i] = canot[i] = -1;

    per(i, 1, 6) {
        if (C[i] == 'G') {
            num[i] = E[i] - '0';//当前等式确定
            leave[E[i] - '0']++;
        } else if (C[i] == 'P') {
            canot[i] = E[i] - '0';//i位置不能是
            leave[E[i] - '0']++;//等式中一定要有
        } else {//B,当前位置不能是,如果没有leave,则等式中不能有
            canot[i] = E[i] - '0';
            black[E[i] - '0'] = true;//标记为黑色
        }
    }

    vector<array<int, 6>> ans;

    per(i, 0, 9)per(j, 0, 9)per(k, 0, 9)per(l, 0, 9)per(m, 0, 9)per(n, 0, 9) {
                            if (i * 10 + j + k * 10 + l == m * 10 + n) {//是否满足题目要求
                                if (i == canot[1])goto nxt;
                                if (j == canot[2])goto nxt;
                                if (k == canot[3])goto nxt;
                                if (l == canot[4])goto nxt;
                                if (m == canot[5])goto nxt;
                                if (n == canot[6])goto nxt;

                                if (num[1] != -1 and num[1] != i)goto nxt;
                                if (num[2] != -1 and num[2] != j)goto nxt;
                                if (num[3] != -1 and num[3] != k)goto nxt;
                                if (num[4] != -1 and num[4] != l)goto nxt;
                                if (num[5] != -1 and num[5] != m)goto nxt;
                                if (num[6] != -1 and num[6] != n)goto nxt;

                                int now[10];
                                per(o, 0, 9)now[o] = 0;
                                now[i]++, now[j]++, now[k]++, now[l]++, now[m]++, now[n]++;

                                per(o, 0, 9) {
                                    if (black[o] and !leave[o]) {//等式中不能有
                                        if (now[o])goto nxt;
                                    }
                                }

                                per(o, 0, 9) {
                                    if (black[o] and leave[o]) {
                                        if (now[o] != leave[o])goto nxt;
                                    }
                                }

                                per(o, 0, 9) {
                                    if (!black[o] and leave[o]) {
                                        if (now[o] < leave[o])goto nxt;
                                    }
                                }

                                ans.push_back({i, j, k, l, m, n});
                            }
                            nxt:
                            {};
                        }


    cout << ans.size() << endl;
    per(i, 0, ans.size() - 1)cout << ans[i][0] << ans[i][1] << "+" << ans[i][2] << ans[i][3] << "=" << ans[i][4]
                                  << ans[i][5] << endl;
    //11+22=33
    //PBGPPGGP

    //1只能有一个, 2一定有两个, 3有一个
}

E Expenditure Reduction

为了让你的钱更充裕，与其赚更多的钱，不如减少支出。
顺平是一家会员制餐厅的经理。由于受到大流行病的影响，餐厅无法负担过多的美味佳肴。于是，如何在保留特色菜的同时减少菜单就成了一个问题。
菜单可以看作是一个只包含小写英文字母和数字的字符串 $S$ ，而顺平认为餐厅的核心特色是一个字符串 $F$ ，它目前是 $S$ 的子串。为了减少菜单，您可以将 $S$ 减少到其子串 $S’$ 中的一个，同时保留 $F$ 作为 $S’$ 的子串。Junpei 要求你从 $S$ 中找出满足要求的最短子串 $S’$ 。
对于那些可能对子序列和子串的定义感到好奇的人，请考虑两个非空字符串 $A, B$ ：

  • 如果我们说 $A$ 是 $B$ 的子串，那么我们可以找到一组 $|A|$ 指数 $\{i_k\}$ ，其中 $1 \leq i_1 < i_2 < \dots < i_{|A|} \leq |B|$ ，这样就有 $A = B_{i_1}B_{i_2}\dots B_{i_{|A|}}$ 。
  • 如果我们说 $A$ 是 $B$ 的子串，那么我们可以从 $B$ 中删除一个（可能为空）前缀和一个（可能为空）后缀，从而得到 $A$ 。

显然可以开一个数组存储当前位置以后的字符c的最早出现的位置，然后枚举起始位置即可。

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
void solve() {
	string s, t;
	cin >> s >> t;
	int lens = si(s), lent = si(t);
	s = ' ' + s;
	t = ' ' + t;
	vector<vector<int>> nxtchar = vector(lens + 5, vector(26, lens + 1));
	vector<vector<int>> nxtnum = vector(lens + 5, vector(10, lens + 1));
	vector<int> h;
	auto isnum = [&](char c)->bool{	return '0' <= c && c <= '9';};
	auto ischar = [&](char c)->bool{ return 'a' <= c && c <= 'z';};
    // 预处理每个位置的下一个位置上出现字符j的位置
	for (int i = lens; i >= 1; --i) {
		if (s[i] == t[1]) h.push_back(i);
		for (int j = 0; j < 10; ++j) 
			nxtnum[i][j] = nxtnum[i + 1][j];
		for (int j = 0; j < 26; ++j) 
			nxtchar[i][j] = nxtchar[i + 1][j];
		if (ischar(s[i])) nxtchar[i][s[i] - 'a'] = i;
		else nxtnum[i][s[i] - '0'] = i;
	}
	int ans = 1e18, le = 0, ri = 0;
	for (int i = 1; i <= lens; ++i) {
        // 如果当前位置是和t字符串的第一个位置一样
		if (s[i] == t[1]) {
			int k, l = i, cur = i;
			for (int j = 2; j <= lent; ++j) {
				if (isnum(t[j])) {
					k = t[j] - '0';
					cur = nxtnum[cur + 1][k];
				} else {
					k = t[j] - 'a';
					cur = nxtchar[cur + 1][k];
				}
				if (cur == lens + 1) break;
			}
			int r = cur;
			if (r != lens + 1) {
				int res = r - l + 1;
				if (ans > res) {
					le = l, ri = r;
					ans = res;
				}
			}
		}
	}
	cout << s.substr(le, ri - le + 1) << endl;
}

M My University Is Better Than Yours

假设总共有 $n$ 所大学，他收集了 $m$ 个大学排名。为简单起见，所有大学都用一个从 $1$ 到 $n$ 的数字表示。定义，当且仅当存在一个大学排名，使得大学 $x$ 的排名高于大学 $y$ 时，大学 $x$ 直接优于大学 $y$ 。此外，当且仅当存在一个序列 $\{s_1,\ s_2,\ …,\ s_k\}$ ( $k\ge 2$ )，使得大学 $x$ 排名高于大学 $y$ 时，大学 $x$ 就优于大学 $y$ ：

  • $s_1=x,\ s_k=y$
  • $\forall i\in \{1, 2, \dots, k - 1\}$ ，大学 $s_i$ 直接优于大学 $s_{i+1}$ 。

对于每所大学，需要回答这所大学比其他多少所大学好。

可以发现对于这个直接优于是一种有向关系，并且题目的范围保证了nm不会超过1e6，那么这个是一个很明显的提示了，对于每一个排名，都按照直接优于的关系建边，边数是nm，能够存的下。
那么比如第一个样例：

1
2
3
4 2
1 2 3 4
1 3 2 4
1
3 2 2 0

表示1->2,2->3,3->4,1->3,3->2,2->4。画出图形之后再和答案比较，按照图的关系简化一下优于的定义，就是表示如果X优于Y，那么存在一条路径使得X可以到达Y，所以应该和图的连通性有关。

所以只要知道这个有向图中X这个点能够到达哪些点即可。很容易就想到按照强联通分量缩点，并且可以证明的是缩点后的DAG一定是一条链，所以按反图的拓扑序遍历就是答案。

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
struct Tarjan {
	vector<int> e[N];
	int n{}, m{}, idx{}, cnt{};
	int dfn[N] {}, low[N] {}, bel[N] {};
	bitset<N> ins{};
	stack<int> stk;
	vector<vector<int>> scc;

	void dfs(int u) {
		dfn[u] = low[u] = ++idx;
		ins[u] = true;
		stk.push(u);
		for (auto v : e[u]) {
			if (!dfn[v]) dfs(v);
			if (ins[v]) low[u] = min(low[u], low[v]);
		}
		if (dfn[u] == low[u]) {
			++cnt;
			vector<int> c;
			while (true) {
				int v = stk.top();
				c.push_back(v);
				ins[v] = false;
				bel[v] = cnt;
				stk.pop();
				if (v == u) break;
			}
			scc.push_back(c);
		}
	}
};

Tarjan tarjan;

void solve() {
	int n, m;
	cin >> n >> m;
	tarjan.n = n, tarjan.m = m*n;
	for(int i = 1;i<=m;++i){
		int pre;
		cin>>pre;
		int t;
		for(int j = 2;j<=n;++j){
			cin>>t;
			tarjan.e[pre].push_back(t);
			pre = t;
		}
	}	
	for (int i = 1; i <= n; ++i)
		if (!tarjan.dfn[i]) tarjan.dfs(i);
	vector<int> res(n+1);
	int ans = 0;
	for (auto &it : tarjan.scc){
		int tot = si(it);
		ans += tot - 1;
		for(int i : it) res[i] = ans;
		ans++;
	}
	for(int i = 1;i<=n;++i)
		cout<<res[i]<<" \n"[i == n];
}

非常板子的题，去掉tarjan板子只有10行左右是自己写的