河北京电电力建设有限公司网站,庙行网站建设,工厂的网站在哪里做的,wordpress服务器出错第一题#xff1a;最短子串
题目描述
米小游拿到了一个字符串#xff0c;她想截取一个连续子串#xff0c;使得该子串中包含至少k个连续的“mihoyo”。
你可以帮米小游求出最短的子串长度#xff0c;以及对应的子串位置吗#xff1f;
输入描述
第一行输入两个正整数n…第一题最短子串
题目描述
米小游拿到了一个字符串她想截取一个连续子串使得该子串中包含至少k个连续的“mihoyo”。
你可以帮米小游求出最短的子串长度以及对应的子串位置吗
输入描述
第一行输入两个正整数n和k用空格隔开。
第二行输入一个长度为n的、仅由小写字母组成的字符串。1≤k≤n≤200000
22 2
mihoyoyomihoyomimihoyo输出描述
如果不存在这样一个连续子串请输出-1。
否则输出两个正整数lr代表选取的子串的左下标和右下标(整个字符串左下标为0右下标为n-1。
请务必保证选择的连续子串包含至少k个mihoyo且长度是最短的。有多解时输出任意即可。
0 13代码与测试
#includeiostream
#includestring
#includevector
#define NMAX 200000
using namespace std;
int n, k;
string S;
vectorpairint, 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;pairint, 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第二题猜数字
题目描述
米小游心中想了一个正整数她邀请了n个人来猜这个数。每个人会猜一个数ai然后米小游会告诉对方猜的结果大于等于米小游想的数≥或者小于米小游想的数。
猜谜结束后米小游统计了共有x个≥和y个。请你判断米小游初始想的数有多少种不同的可能
输入描述
第一行输入一个正整数n代表猜谜的人数。
第二行输入n个正整数ai代表每个人猜的数字。
第三行输入两个整数x和y用空格隔开。
1≤xyn≤1e51 ≤ ai ≤ 1e9
3
1 5 3
0 3输出描述
如果有无穷多种可能输出infinity
否则输出一个整数代表米小游心中想的数的不同可能数量。
infinity代码与测试
#includeiostream
#includealgorithm
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, numn);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:
12C中的sort 第三题树的连通块
题目描述
米小游有一棵有根树树上共有n个节点。
米小游指定了一个节点x为根然后定义所有相邻的、编号奇偶性相同的节点为一个连通块。
米小游想知道所有子树共有n个子树的连通块数量之和是多少
举个例子 如上图3号节点被指定为根
然后3-1-5作为一个连通块4号节点和2号节点为单独的连通块。
那么1号节点到5号节点每个节点的子树连通块数量分别为2、1、3、1、1总连通块数量是8。
输入描述
5 3
1 2
1 3
3 4
5 1输出描述
8代码与测试
#includeiostream
#includevector
using namespace std;
int n, root;
#define NMAX 100005
int res 0;
struct node{int s 1;vectorint 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原题链接
