第一題：最短子串

題目描述

米小游拿到了一個字符串，她想截取一個連續(xù)子串，使得該子串中包含至少k個連續(xù)的“mihoyo”。

你可以幫米小游求出最短的子串長度，以及對應的子串位置嗎？

輸入描述

第一行輸入兩個正整數(shù)n和k，用空格隔開。

第二行輸入一個長度為n的、僅由小寫字母組成的字符串。1≤k≤n≤200000

22 2
mihoyoyomihoyomimihoyo

輸出描述

如果不存在這樣一個連續(xù)子串，請輸出-1。

否則輸出兩個正整數(shù)l，r，代表選取的子串的左下標和右下標(整個字符串左下標為0，右下標為n-1）。

請務必保證選擇的連續(xù)子串包含至少k個"mihoyo"，且長度是最短的。有多解時輸出任意即可。

0 13

代碼與測試

#include<iostream>
#include<string>
#include<vector>
#define NMAX 200000
using namespace std;
int n, k;
string S;
vector<pair<int, int>> res;
string standard = "mihoyo";
int main() {cin >> n >> k >> S;int p1 = 0, p2 = 0, pre = 0;for (; p1 < n; p1++) {if (S[p1] == standard[p2]) {if (!p2) pre = p1;//若為第一個，記錄下來p2++;if (p2 == 6) { //若為最后一個，則直接添加到Res中res.push_back(make_pair(pre, p1));p2 = 0;}}else p2 = 0;//不相等直接略過}/*for (int i = 0; i < res.size(); i++) {cout << res[i].first << " " << res[i].second << endl;}*/int size = NMAX;pair<int, int> ret;for (int i = 0; i < res.size(); i++) {if (i + k > res.size()) break;if (res[i + k -1].second - res[i].first < size) {size = res[i + k -1 ].second - res[i].first;ret.first = res[i].first;ret.second = res[i + k -1].second;}}if (size == NMAX) cout << -1 << endl;else cout << ret.first << " " << ret.second << endl;
}

測試用例:
In:
53 2
hsuimihoyomsmihoyoshdusicmihoyomihoyomimimishudmihoyo
Out:
25 36In：
65 3
hsuimihoyomsmihoyomihoyomihoyoshdusicmihoyomihoyomimimishudmihoyo
Out:
12 29

第二題：猜數(shù)字

題目描述

米小游心中想了一個正整數(shù)，她邀請了n個人來猜這個數(shù)。每個人會猜一個數(shù)ai，然后米小游會告訴對方猜的結果：大于等于米小游想的數(shù)（≥）或者小于米小游想的數(shù)（<）。

猜謎結束后，米小游統(tǒng)計了共有x個≥和y個<。請你判斷米小游初始想的數(shù)有多少種不同的可能？

輸入描述

第一行輸入一個正整數(shù)n，代表猜謎的人數(shù)。

第二行輸入n個正整數(shù)ai，代表每個人猜的數(shù)字。

第三行輸入兩個整數(shù)x和y，用空格隔開。

1≤x+y=n≤1e5，1 ≤ ai ≤ 1e9

3
1 5 3
0 3

輸出描述

如果有無窮多種可能，輸出"infinity"

否則輸出一個整數(shù)，代表米小游心中想的數(shù)的不同可能數(shù)量。

infinity

代碼與測試

#include<iostream>
#include<algorithm>
using namespace std;
#define NMAX 100005
int n, x, y;
int num[NMAX];
int main() {cin >> n;for (int i = 0; i < n; i++) cin >> num[i];cin >> x >> y;sort(num, num+n);if (x == n) cout << num[0];else if (y == n) cout << "infinity";else cout << num[y] - num[y - 1];
}

In:
3
1 5 3
0 3
Out:
infinityIn:
9
12 32 21 902 12 90 129 12 90
4 5Out:
58In:
9
12 32 21 902 12 90 129 12 90
9 0
Out:
12

C++中的sort

第三題：樹的連通塊

題目描述

米小游有一棵有根樹，樹上共有n個節(jié)點。

米小游指定了一個節(jié)點x為根，然后定義所有相鄰的、編號奇偶性相同的節(jié)點為一個連通塊。

米小游想知道，所有子樹（共有n個子樹）的連通塊數(shù)量之和是多少？

舉個例子：

如上圖，3號節(jié)點被指定為根

然后3-1-5作為一個連通塊，4號節(jié)點和2號節(jié)點為單獨的連通塊。

那么1號節(jié)點到5號節(jié)點，每個節(jié)點的子樹連通塊數(shù)量分別為：2、1、3、1、1，總連通塊數(shù)量是8。

輸入描述

5 3
1 2
1 3
3 4
5 1

輸出描述

8

代碼與測試

#include<iostream>
#include<vector>
using namespace std;
int n, root;
#define NMAX 100005
int res = 0;
struct node{int s = 1;vector<int> adj;
}T[NMAX];
void dfs(int r, int fa) {int leaf = 1;for (int i = 0; i < T[r].adj.size(); i++) {int son = T[r].adj[i];if (son == fa) continue;else {leaf = 0;dfs(son, r);if (son % 2 == r % 2) T[r].s += (T[son].s - 1);else T[r].s += T[son].s;}}if (leaf) T[r].s = 1;res += T[r].s;
}
int main() {int x, y;cin >> n >> root;for (int i = 0; i < n - 1; i++) {cin >> x >> y;T[x].adj.push_back(y);T[y].adj.push_back(x);}dfs(root,0);cout << res;
}

In:
5 2
1 2 
1 3
3 4
5 1
Out:
9In:
5 3
1 2 
1 3
3 4
5 1
Out:
8

原題鏈接