[C++知识库]每日思维风暴

一、循环子串

遇到字符串循环时，也就是需要首尾相连时

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(){
	int t;
	cin>>t;
	string s;
	while(t--){
		int n;
		cin>>n;
		cin>>s;
		s+=s;//涉及到循环子串，要将原字符串首尾相连 
		bool f=true;
		for(int len=2;len<=n;len++){
			for(int i=0;i+len<n;i++){//双重循环枚举所有子串 
				string str=s.substr(i,len);
				reverse(str.begin(),str.end());
				if(s.find(str)==s.npos){
					f=false;break; 
				}
			}
			if(!f)break;
		} 
		if(f)cout<<"YES";
		else cout<<"NO";
		if(t)cout<<endl;
	} 
	return 0;
} 

二锦标赛，思维风暴

当题目问有多少种可能，我们可以反过来求不能，“正难则反”），总数减去不可能即可。必胜的必定是最大的，往后遍历看是否出现断层

要最后剩下的选手尽可能多，最大的肯定留下来，要尽可能拿大的和最大的比，小的直接就淘汰了，只是可能获胜的玩家，并不是一局中获胜的玩家

1、最大的那个肯定会留下
2、尽可能让更大的x(仅次于y)和较大的y去比较，因为若x输宇y，
小于x的数和y比较一定牺牲 ，x总要和y比，那么小于y的全部牺牲
但是x不一定输于y，在某一局中就可能取胜，那么小于x的数胜负情况就要 按以上套路重定了

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
int a[N]; 
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int res=0;
	for(int i=n-2;i>=0;i--)
	{
		if(a[i+1]-a[i]<=k)res++;
		else break;//牺牲了此大于a[i+1]的，小于a[i+1]的一定全部牺牲 

	 
	}	
	cout<<res+1;//加上最大的那个 
	return 0;
} 

#include <iostream>
#include <map>
using namespace std;
const int N=105;
int main(){
	map<int,string> mp;
	mp[1]="123";
	mp.insert({2,"222"});
	mp.insert({3,"222"});
	mp.erase(mp.begin());
//	mp.erase(1);效果相同
//	map的erase函数里面，既可以是值也可以是迭代器 
	for(map<int,string>::iterator it=mp.begin();it!=mp.end();it++){
		cout<<it->first<<" "<<it->second<<endl;
	}
	return 0;
} 

三、蒟蒻(map容器的删除操作)

#include <iostream>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
//const int N=1e5+5;
map<int,int> mp1;//既然要按照两个标准分别排序，那就分别用两个容器存
//方便分别找到两个标准下的最小值，删去某个商品时两个容器中都要删去
map<int,int> mp2; 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int op,w,t;
		cin>>op;
		if(op==1){
			cin>>w>>t;
			if(mp1.count(w)==0&&mp2.count(t)==0){
				mp1.insert({w,t});
				mp2.insert({t,w});
			}
		}
		else if(op==2){//删除w最小的商品，在mp1中排在最前 
			mp2.erase(mp1.begin()->second);
			mp1.erase(mp1.begin());
//			mp2.erase(mp1.begin()->second);顺序绝对不能反呀！
//删除了mp1.begin那么下一次访问mp1.begin就不是当初的那个了 
		}
		else if(op==3){
			mp1.erase(mp2.begin()->second);
			mp2.erase(mp2.begin());
//			mp1.erase(mp2.begin()->second);
		}
	}
	int res=0;
//	for(auto x:mp1)res+=x.first;
	for(map<int,int>::iterator it=mp1.begin();it!=mp1.end();it++)res+=it->first;
	cout<<res; 
	return 0;
} 

四、子串分值

子串分值是在子串中只出现一次的的个数总和
子串分值和是在子串中出现的不同字符的个数总和
参考思路

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
int pre[N];//pre[i]表示第i个字符ch前面最近的ch的位置 
int nex[N];
int a[30]; 
int main(){
//枚举所有子串，累计所有子串中 某个只出现一次的字母的个数
//双重循环枚举所有子串超时
//该字符串中每个字母对某些子串的贡献值累加起来
//比如 abcadba,排在第四位的字母a对子串bca,ca,ad,adb这些子串都有贡献
//这个a对结果的贡献就是4，这些子串的个数 
	string s;
	cin>>s; 
	s="0"+s;
	int n=s.size()-1;
	for(int i=1;i<=n;i++){
		char ch=s[i];
		pre[i]=a[ch-'a'];
		a[ch-'a']=i;
//s[i]这个字符(记作ch)的位置，那么下一次碰到j位置的ch这个字符，
//pre[j]=a[s[i]-'a']
	
	}
	for(int i=0;i<26;i++)a[i]=n+1;//假设极端情况，s由n个不同字符组成
//	第i个字符有贡献的子串个数是(i-pre[i])*(nex[i]-i) 
//	由于可能找不到后面最近的一个相同字符，那么nex的值就算做n+1 
	for(int i=n;i>=1;i--){
		char ch=s[i];
		nex[i]=a[ch-'a'];
		a[ch-'a']=i;
//s[i]这个字符(记作ch)的位置，那么下一次碰到j位置的ch这个字符，
//nex[j]=a[s[i]-'a']
	}
	int res=0;
	for(int i=1;i<=n;i++)res+=(i-pre[i])*(nex[i]-i);
	cout<<res;
	return 0;
} 

五、子串分值和

字串分值和同样是从贡献度的角度考虑，只是 只需要考虑前一个相同字符的位置，因为第i个字符能贡献到的子串个数
ababcabc
第i个字符后面与他相同的字符的最近位置、个数有多少个都无所谓，对所有子串的贡献值都是1，但是，要考虑前一个相同字符的位置，因为 如果把前一个最近相同字符也重新算一个子串将重复
比如对于下标为3的字符a，下标为1的字符a有贡献的子串 已经包含所有 a1…a2，a1…a2…a3这些子串，所以a2贡献的子串不能再包含a1
所以贡献的子串个数是(i-pre[i])*(n-i+1)

注意数据范围，贡献综合会爆int

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N=1e6+5;
int pre[N];//pre[i]表示第i个字符ch前面最近的ch的位置 
int a[30]; 
signed main(){
	string s;
	cin>>s; 
	s="0"+s;
	int n=s.size()-1;
	int res=0;
	for(int i=1;i<=n;i++){
		pre[i]=a[s[i]-'a'];
		res+=(i-pre[i])*(n-i+1);
		a[s[i]-'a']=i;
	
	}
	cout<<res;
	return 0;
}