比赛链接：https://vjudge.net/contest/341241
E：https://vjudge.net/contest/374548#problem/E
题意：给你一个长度为n的字符串s，问你里面有多少个不重复元素的xtCpc子串（不重复指的是在字符串同一位置上的字母只能使用一次）。
思路：第一步先暴力，那就是遍历一遍字符串每次遇到x就开始向后找t，若匹配成功则把相应字母变成其他非子串字母就好，以此类推。复杂度是O(n^2)。数据范围2e5，不想T了。
我们仔细观察一下子串，xtCpc，五个字母各自不同，那么对于原来的字符串其实也就只有这五个字母及其位置有用，这么一来，长度为n的字符串s就得到了优化。再暴力的想一想，对于s，在第一个x前面的tCpc都没有意义（匹配不到），在第二个x前面的tCpc对第二个x没有用（但对第一个有用），以此类推，得到对于第i个C前面的x，t都没用之类的结论。于是答案就出来，再想想用什么东西来维护呢？很容易想到先进先出的队列，用队列来存子串元素的位置，如果子串中后面元素的位置在前面元素的前方，那么这个元素必定没有意义，就弹出队列，如果在后方，就匹配成功以匹配下一个字母(由于题目说只能用一次，所以匹配成功后也要弹出这个元素)。每次c匹配成功ans就+1。至此代码也就写出来了。
//author CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e5+7;
const double pi=acos(-1);
using namespace std;
queue<int > p[128];
char a[maxn];
int main()
{
ios::sync_with_stdio(false);
int n;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
for(int i=0;i<128;i++)
{
while(!p[i].empty())
{
p[i].pop();
}
}
scanf("%s",a);
for(int i=0;i<n;i++)
{
p[int(a[i])].push(i);
}
char last_char;
ll ans=0;
ll place;
if(!p[int('x')].empty())
{
place=p[int('x')].front();
p[int('x')].pop();
last_char='x';
}
else
{
cout<<0<<endl;
return 0;
}
int f=1;
//xtCpc
while(f)
{
if(last_char=='x')
{
if(p[int('t')].empty())
{
f=0;
break;
}
while(!p[int('t')].empty())
{
if(p[int('t')].front()>place)
{
last_char='t';
place=p[int('t')].front();
p[int('t')].pop();
break;
}
else
{
p[int('t')].pop();
}
}
}
else if(last_char=='t')
{
if(p[int('C')].empty())
{
f=0;
break;
}
while(!p[int('C')].empty())
{
if(p[int('C')].front()>place)
{
last_char='C';
place=p[int('C')].front();
p[int('C')].pop();
break;
}
else
{
p[int('C')].pop();
}
}
}
else if(last_char=='C')
{
if(p[int('p')].empty())
{
f=0;
break;
}
while(!p[int('p')].empty())
{
if(p[int('p')].front()>place)
{
last_char='p';
place=p[int('p')].front();
p[int('p')].pop();
break;
}
else
{
p[int('p')].pop();
}
}
}
else if(last_char=='p')
{
if(p[int('c')].empty())
{
f=0;
break;
}
while(!p[int('c')].empty())
{
if(p[int('c')].front()>place)
{
last_char='c';
place=p[int('c')].front();
p[int('c')].pop();
break;
}
else
{
p[int('c')].pop();
}
}
}
else if(last_char=='c')//其实是说明已经找到一组了
{
ans++;
if(p[int('x')].empty())
{
f=0;
break;
}
else
{
place=p[int('x')].front();
p[int('x')].pop();
last_char='x';
}
}
}
printf("%lld\n",ans);
}
//printf("%lld",ans);
return 0;
}
K:https://vjudge.net/contest/374548#problem/K
参考博客：https://blog.csdn.net/qq_37748451/article/details/90368388
题意：给你十四张牌打麻将，有两种获胜方式，一种是shisanyao，另一种是jiulianbaodeng。我们来具体看下这两种方式背后的条件。
shisanyao：同时拥有东,南,西,北,红中,白板,发财,一条,九条,一万,九万,一筒,九筒这十三张牌，另外一张随意。
jiulianbaodeng：在万、筒、条中的某一种以1112345678999的形式加上1到9其中任意一张成立，注意必须是同一种牌，都是万，都是筒或都是条！
思路：
对于jiulianbaodeng，可以用三个数组来存对应数字，判断的时候看是否满足对应的形式就好。
对于shisanyao，结合jiulianbaodeng的三个数组，再来一个map<string,int>记录东,南,西,北,红中,白板,发财的出现次数。最后看一下是否满足这个条件就好。至此代码也就写出来了。
//author CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
//十三幺是东,南,西,北,红中,白板,发财和一条,九条,一万,九万,一筒,九筒
//万、筒、条中的某一种以1112345678999的形式加上1到9其中任意一张成立
string ss;
map <string,int> pai;
int p[10],w[10],s[10];
int p0,s0,w0;
int shuzi=0;
int jiu=1,shi=0;
int main()
{
ios::sync_with_stdio(false);
for (int i=0;i<14;i++)
{
cin>>ss;
if(ss[1]=='p')
{
p[ss[0]-'0']++;
shuzi++;
p0++;
}
else if (ss[1]=='w')
{
w[ss[0]-'0']++;
shuzi++;
w0++;
}
else if (ss[1]=='s')
{
s[ss[0]-'0']++;
shuzi++;
s0++;
}
else
{
pai[string(ss)]++;
}
}
if(s0==14)
{
if(s[1]<3||s[9]<3)
{
jiu=0;
}
for(int i=2;i<=8;i++)
{
if(s[i]<1)
{
jiu=0;
}
}
}
else if(p0==14)
{
if(p[1]<3||p[9]<3)
{
jiu=0;
}
for(int i=2;i<=8;i++)
{
if(p[i]<1)
{
jiu=0;
}
}
}
else if(w0==14)
{
if(w[1]<3||w[9]<3)
{
jiu=0;
}
for(int i=2;i<=8;i++)
{
if(w[i]<1)
{
jiu=0;
}
}
}
//以上是判断九莲宝灯
else if(s[1]>=1&&s[9]>=1&&p[1]>=1&&p[9]>=1&&w[1]>=1&&w[9]>=1&&pai["dong"]>=1&&pai["nan"]>=1&&pai["xi"]>=1&&pai["bei"]>=1&&pai["zhong"]>=1&&pai["fa"]>=1&&pai["bai"]>=1)
{
shi=1;
}
if(shi)
{
cout<<"shisanyao!"<<endl;
}
else if(jiu)
{
cout<<"jiulianbaodeng"<<endl;
}
else
{
cout<<"I dont know!"<<endl;
}
return 0;
}
L：https://vjudge.net/contest/374548#problem/L
题意：就是对于单词，改变一下它非头尾的字母，你能不能说明这是一样的单词（具体看样例）
如果单词没变化，就输出Equal，如果是一样的单词，输出Yes，如果不一样，输出No。
思路：很容易想到桶排序，毕竟单词里面就是字母，除开头尾，中间部分每个字母次数一样，必然是Yes,再在这种情况下判断一下是不是Equal就好。至此代码也就出来了。
//author CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int tong[26]={0};
int tong2[26]={0};
int main()
{
ios::sync_with_stdio(false);
string a,b;
while(cin>>a>>b)
{
memset(tong,0,sizeof(tong));
memset(tong2,0,sizeof(tong2));
int n,m;
n=a.length();
m=b.length();
if(n!=m)
{
cout<<"No"<<endl;
continue;
}
//判断相等
int f=1;
for(int i=0;i<n;i++)
{
if(a[i]!=b[i])
{
f=0;
break;
}
}
if(f)
{
cout<<"Equal"<<endl;
continue;
}
int f2=1;
if(a[0]==b[0]&&a[n-1]==b[n-1])
{
for(int i=1;i<n-1;i++)
{
tong[int(a[i]-'a')]++;
tong2[int(b[i]-'a')]++;
}
for(int i=0;i<26;i++)
{
if(tong[i]!=tong2[i])
{
f2=0;
cout<<"No"<<endl;
break;
}
}
}
else
{
cout<<"No"<<endl;
continue;
}
if(f2)
{
cout<<"Yes"<<endl;
}
}
return 0;
}
写在最后：
打麻将杀我，考场上看了不知道多久就是没看懂！麻将真难。
这套就补三个，另外的题，根本就没人做出来。
以后可能想起来会补吧。
京公网安备 11010502036488号