ICPC暑期集训1

ICPC暑期集训1 不重最长子串

题目描述

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

输入

一行，一个字符串s，长度在0∼50000之间，由英文字母、数字和空格组成。

输出

输出一个整数，为不含有重复字符的最长子串的长度。

输入数据1

abcabcbb

输出数据1

提示1

因为无重复字符的最长子串是 “abc”，所以其长度为 3。

输入数据2

bbbbb

输出数据2

提示2

因为无重复字符的最长子串是 “b”，所以其长度为 1。

输入数据3

pwwkew

输出数据3

提示3

因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

分析

这个题目我们明显可以用队列数据结构来模拟：

使用队列存储子串，用mp[i]表示元素i是否在队列中，初始时mp[i]均为false。遍历字符串s，若mp[s[i]]为false，则将其入队，并将其对应的mp值标记为true，队列中的元素个数count加一；否则，比较并更新当前答案ans，并将在队列中与当前遍历到的元素重复的元素以及其之前的所有元素出队，再将新的元素入队，继续遍历。遍历完之后再对当前答案ans进行一次比较更新，最后输出ans。（详见代码1）

回想上述方法及其思路，对于整个队列存放的子串其实我们并不需要得到最长不重子串的具体内容，而是仅仅只需要得到其长度即可。所以有没有什么办法，我们可以把这个入队和出队的过程省略，而只记录一个子串的长度呢？给出优化之后的做法（详见代码2），大致思路如下：

记录下每个数上次出现的位置，然后枚举区间的左端点（先定后配），匹配右端点。遍历字符串，初始时，所有的字符上一次出现的位置均为0，如果当前字符上次出现的位置在左端点的左边，最大值与当前长度比较并更新，否则将左端点向右移一位，遍历过的字符都要在判断过后更新该字符上一次出现的位置。最后输出最大长度即可。

代码1

#include 
#define N 50007
using namespace std;
map mp;//记录某字符是否被用过
queue q;//用来存放子串的队列q
string s;
int main(void)
{
	int i, ans=0, count=0;
	getline(cin, s);
	for(i=0; s[i]; ++i) mp[s[i]]=false;//将mp初始化
	for(i=0; s[i]; ++i)//遍历字符串
	{
		if(!mp[s[i]])//元素s[i]不在队列中
		{
			q.push(s[i]);//让s[i]入队
			++count;
			mp[s[i]]=true;
		}
		else//元素s[i]在队列中
		{
			ans=max(ans, count);//更新ans
			while(mp[s[i]])//s[i]及其之前的元素全部出队
			{
				mp[q.front()]=false;
				q.pop();
				count--;
			}
			q.push(s[i]);//让s[i重新入队
			count++;
			mp[s[i]]=true;
		}
	}
	ans=max(ans, count);//更新ans
	printf("%d", ans);
	return 0;
}

代码2

#include 
using namespace std;
const int N=5e4+7;
char b[N];
int a[130], l=1, mx;//左端点的起点在第一个位置
int main(void)
{
	cin.getline(b+1, N-1);//字符串从第一个位置输入
	for(int i=1; b[i]; ++i)//遍历字符串
	{
		if(a[b[i]] 
小J的加密算法 
题目描述 
上大学了，小J学会了一种加密算法，这种算法可以根据一个行数m，将一个字符串进行重新排列，变成无法读懂的密文。 
例如：给定一个字符串 “PAYPALISHIRING”，行数3，将其进行从上到下，从左到右的Z字形排列如下： 
P   A   H   N
A P L S I I G
Y   I   R
 
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。 
输入 
一个由英文字母及英文标点符号组成的字符串s及一个行数m(1≤m≤1000)，s的长度在1∼1000之间。 
输出 
输出加密字符串 
输入数据1 
PAYPALISHIRING 3
 
输出数据1 
PAHNAPLSIIGYIR
 
输入数据2 
PAYPALISHIRING 4
 
输出数据2 
PINALSIGYAHRPI
 
提示2 
P     I    N
A   L S  I G
Y A   H R
P     I
 
输入数据3 
A 1
 
输出数据3 
A
 
输入数据4 
hello,world! 3
 
输出数据4 
horel,ol!lwd
 
分析 
可以用一个字符数组ch作为密文表格，注意首先特判，当输出只有一行的时候，直接输出整个字符串即可。遍历字符串，按照’Z’形的规律填入字符，随后按行输出。（详见代码1） 
 
 ⚠刚开始拿到这题的思路略显复杂，并且在最后递交的时候出现问题，且尚未找到错误原因，暂且保留： 
 用一个字符数组ch作为表格，初始时表中所有元素为’ '(ASCLL码值为0)。首先特判，当输出只有一行的时候，直接输出整个字符串即可。通过字符串的长度以及重新排列后的表格的行数m确定表格的列数。遍历每一列，将字符串中对应的元素填在对应表格位置上（分别讨论当前列为’Z’的斜边还是直边）。最后按行的顺序输出。（详见代码2） 
 
代码1 
#include 
using namespace std;
const int N=1007;
string s;
char ch[N][N];//密文表格
int m, col=0;//最终的密文表格有m行col列
int main(void)
{
	cin>>s>>m;
	if(m==1)//特判：只有一行时，直接输出整个字符串
	{
		cout< 
代码2 
#include 
#define N 1007
using namespace std;
string s;
char ch[N][N];//ch为字符数组存放重新排列后的密文表格
int main(void)
{
	int m, i, j, n, len, count;//m为数组的行数，n表示数组的列数，len为字符串的长度，count记录已填入表格的元素个数
	cin>>s>>m;
	memset(ch, 0, sizeof(ch));//初始化密文表格所有元素都为0
	len=s.size();
	if(m==1)//特判：只有一行时，直接输出整个字符串
	{
		cout< 
数列的个数 
题目描述 
给出两个整数n, m。问有多少个长度为n的序列A，满足以下条件： 
1≤A_i≤m(i=1, 2, · · · , n)
∀_i∈[1,n−1], A_i+1是A_i的倍数。 
由于答案可能很大，所以你只需要输出答案对998244353取模的结果。 
输入 
输入只有一行，两个整数n,m(1≤n,m≤2×10⁵)。 
输出 
输出只有一行，输出方案数。 
输入数据1 
3 4
 
输出数据1 
13
 
输入数据2 
20 30
 
输出数据2 
71166
 
输入数据3 
200000 200000
 
输出数据3 
835917264
 
代码 
#include 
using namespace std;
const int M=998244353;
int dp[20]={1}, n, m;
int solve(int k)
{
	int ans=1;
	for(int i=2; i*i<=k; ++i)
	{
		if(k%i) continue;
		int c=0;
		while(k%i==0) k/=i, ++c;
		ans=ans*1LL*dp[c]%M;
	}
	if(k>1) ans=ans*1LL*dp[1]%M;
	return ans;
}
int main(void)
{
	int ans=0;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=19; ++j)
			(dp[j]+=dp[j-1])%=M;
	for(int i=1; i<=m; ++i)
		(ans+=solve(i))%=M;
	cout< 
匹配正则表达式 
题目描述 
给你一个字符串s和一个字符规律p，请你来实现一个支持 . 和 * 的正则表达式匹配。 
. 匹配任意单个字符
* 匹配零个或多个前面的那一个元素 
所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。 
输入 
多组测试数据 每组数据一行，两个字符串s(长度小于20)和p(长度小于30)，s只包含小写字母，p包含小写字母以及 . 和 *。 
输出 
每组数据输出一行，如果p能够匹配s，则输出 Yes，否则输出 No。 
输入数据 
aa a
aa aa
aa a.
aa b*aa
aa c*a.
aaaaab a*b
 
输出数据 
No
Yes
Yes
Yes
Yes
Yes
 
分析 
点通配符其实很好实现，s中的任何字符，只要遇到.通配符，直接匹配就完事了。主要是这个*通配符不好实现，一旦遇到*通配符，前面的那个字符可以选择重复一次，可以重复多次，也可以一次都不出现，这该怎么办？ 
如果不考虑*通配符，只考虑.通配符，面对两个待匹配字符s[i]和p[j]，我们唯一能做的就是看它俩是否匹配。 
在加入*通配符后局面就会变得稍微复杂，可以分情况讨论： 
 1 s[i]与p[j]匹配 
  （1）p[j+1]存在并且为*通配符 
    ① p[j]有可能匹配多个字符，比如s=“aaa”, p=“a*”，那么p[j+1]会通过*匹配3个字符"a"。
② p[j]有可能匹配0个字符，比如s=“aa”, p=“a*aa”，那么p[j+1]会通过*匹配0个字符"a"。
 
（2）p[j+1]不存在或者存在但并不为*通配符：老老实实进行下一次匹配。
 
 2 s[i]与p[j]不匹配 
  （1）p[j+1]存在并且为*通配符：让*通配符匹配0次，比如s=“abcd”, p=“aba*cd”，那么p[j+1]会通过*匹配0个字符"a"。
（2）p[j+1]不存在或者存在但并不为*通配符：匹配失败。
  
彼时，思路已经清晰了，但是如何确定在遇到*通配符的时候是匹配0次还是多次呢？这是一个选择问题，我们要把所有的可能都穷举一遍，才能得到最后的结果。动态规划算法的核心就是“状态”和“选择”，“状态”就是i和j这两个指针的位置，“选择”就是p[j]选择匹配几个字符。 
思路1：设计一个dp函数（详见代码1） 
bool dp(string s, int i, string p, int j);
 
 
 函数表示：若dp(s, i, p, j)==true，则s[i]和p[i]匹配成功；若dp(s, i, p, j)==false，则s[i]和p[i]匹配失败。（每次判断s和p匹配与否时都是从i=0, j=0开始） 
 
思路2：使用一个dp数组来实现 
代码1 
#include 
using namespace std;
string s, p;
bool dp(string s, int i, string p, int j)
{
	while(i>s>>p)
	{
		if(match(s, p)) cout<<"Yes"< 
代码2 
#include 
using namespace std;
typedef long long LL;
string s, p;
LL dp[50][50];
bool check(int i, int j)
{
	if(i==0) return false;
	if(p[j-1]=='.') return true;
	return s[i-1]==p[j-1];
}
int main(void)
{
	while(cin>>s>>p)
	{
		int m=s.size();
		int n=p.size();
		memset(dp, 0, sizeof(dp));
		dp[0][0]=1;
		for(int i=0; i<=m; ++i)
			for(int j=1; j<=n; ++j)
			{
				if(p[j-1]=='*')
				{
					dp[i][j]|=dp[i][j-2];
					if(check(i, j-1))
                        dp[i][j]|=dp[i-1][j];
				}
				else if(check(i, j))
                    dp[i][j]|=dp[i-1][j-1];
			}
		if(dp[m][n]) cout<<"Yes"<

ICPC暑期集训1

Java相关栏目本月热门文章