第一題：最短子串

題目描述

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

你可以幫米小游求出最短的子串長(zhǎng)度，以及對(duì)應(yīng)的子串位置嗎？

輸入描述

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

第二行輸入一個(gè)長(zhǎng)度為n的、僅由小寫(xiě)字母組成的字符串。1≤k≤n≤200000

22 2
mihoyoyomihoyomimihoyo

輸出描述

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

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

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

0 13

代碼與測(cè)試

#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;//若為第一個(gè)，記錄下來(lái)p2++;if (p2 == 6) { //若為最后一個(gè)，則直接添加到Res中res.push_back(make_pair(pre, p1));p2 = 0;}}else p2 = 0;//不相等直接略過(guò)}/*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;
}

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

第二題：猜數(shù)字

題目描述

米小游心中想了一個(gè)正整數(shù)，她邀請(qǐng)了n個(gè)人來(lái)猜這個(gè)數(shù)。每個(gè)人會(huì)猜一個(gè)數(shù)ai，然后米小游會(huì)告訴對(duì)方猜的結(jié)果：大于等于米小游想的數(shù)（≥）或者小于米小游想的數(shù)（<）。

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

輸入描述

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

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

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

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

3
1 5 3
0 3

輸出描述

如果有無(wú)窮多種可能，輸出"infinity"

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

infinity

代碼與測(cè)試

#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

第三題：樹(shù)的連通塊

題目描述

米小游有一棵有根樹(shù)，樹(shù)上共有n個(gè)節(jié)點(diǎn)。

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

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

舉個(gè)例子：

如上圖，3號(hào)節(jié)點(diǎn)被指定為根

然后3-1-5作為一個(gè)連通塊，4號(hào)節(jié)點(diǎn)和2號(hào)節(jié)點(diǎn)為單獨(dú)的連通塊。

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

輸入描述

5 3
1 2
1 3
3 4
5 1

輸出描述

8

代碼與測(cè)試

#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

原題鏈接