A. 统计单词数

题目类型：字符串

思路

对于这道题目我们可以发现，字符串是没法完全对齐的，所以字符串的前面与后面都要加上一个空格，那在这篇文章中，我们会展示两种字符串的前面与后面加上一个空格后的思路。

第一种思路

直接遍历。

第二种思路

用find函数，在这道题目中需要用到两种技巧，学会这两个技巧便可AC本题。

技巧一

(int)a.find(s);

在a字符串中查找等于s的第一个下标。

技巧二

(int)a.find(s,i);

在a字符串中从i开始，查找等于s的第一个下标。

代码

这一份代码是思路二的代码。

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("cal.in","r",stdin);
	freopen("cal.out","w",stdout);
	int cnt=0;
	string s;
	getline(cin,s);
	s=" "+s+" ";
	string a;
	getline(cin,a);
	a=" "+a+" ";
	int last=1;
	for(int i=1;i<s.size();i++) if(s[i]>='a'&&s[i]<='z') s[i]-=32;
	for(int i=1;i<a.size();i++) if(a[i]>='a'&&a[i]<='z') a[i]-=32;
	for(int i=1;i<a.size();i++){
		last=(int)a.find(s,last);
		if(last==-1) break;
		cnt++;
		last=last+1;
		i=last;
	}
	if(cnt==0) cout<<-1;
	else cout<<cnt<<" "<<(int)a.find(s); 
	return 0;
}

这道题目在考试的时候没有考虑包含与空格的情况，导致只得了20分，下次还是要再仔细看一下题目。

B. 瑞士轮

题目类型：排序

思路

我们先想暴力解法，但会发现超时了，因为排序费了时间，我们再看，发现赢的人是有序的，输的人也是有序的，所以可以用两个数组来分别表示赢的人与输的人，再回归到数组里。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=1e5+10;
struct P{
	int f,s,idx;
};
P a[N],b[M],c[M];
bool cmp(P a1,P a2){
	if(a1.f==a2.f) return a1.idx<a2.idx;
	else return a1.f>a2.f;
}
int main(){
	freopen("ruishi.in","r",stdin);
	freopen("ruishi.out","w",stdout);
	int n,r,q;
	cin>>n>>r>>q;
	for(int i=1;i<=2*n;i++){
		cin>>a[i].f;
		a[i].idx=i;
	}
	for(int i=1;i<=2*n;i++) cin>>a[i].s;
	sort(a+1,a+1+2*n,cmp);
	while(r--){
		int x=1,y=1;
		for(int i=1;i<2*n;i+=2){
			if(a[i].s>a[i+1].s){
				a[i].f++;
				b[x++]=a[i];
				c[y++]=a[i+1]; 
			}
			else{
				a[i+1].f++;
				b[x++]=a[i+1];
				c[y++]=a[i]; 
			} 
		}
		x=1,y=1;
		int i=1;
		while(x<=n&&y<=n){
			if(cmp(b[x],c[y])) a[i++]=b[x++];
			else a[i++]=c[y++];
	    }
	    while(x<=n) a[i++]=b[x++];
	    while(y<=n) a[i++]=c[y++];
    }
    cout<<a[q].idx;
	return 0;
}

这道题目在写的时候写了暴力，超时了，下次要想一想AC的写法。

C. 表达式的值

题目类型：栈

思路

列举样例总结规律后，可发现这其实可总结为中缀表达式求值，但需分为结果为零和结果为一两种情况，计算法则与×和⊕相同，×为：

res.f0=(a.f0*b.f0)%10007;
res.f1=(a.f1*(b.f1+b.f0)+a.f0*b.f1)%10007;

⊕为：

res.f0=(a.f0*(b.f0+b.f1)+a.f1*b.f0)%10007;
res.f1=(a.f1*b.f1)%10007;

代码

#include<bits/stdc++.h>
using namespace std;
map<char,int> mp={{'+',1},{'*',2}};
struct P{
	int f0,f1;
};
stack<P> num;
stack<char> op;
void calc(){
	P b=num.top();num.pop();
	P a=num.top();num.pop();
	P res;
	char c=op.top();op.pop();
	if(c=='+'){
		res.f0=(a.f0*b.f0)%10007;
		res.f1=(a.f1*(b.f1+b.f0)+a.f0*b.f1)%10007;
	}
	else{
		res.f0=(a.f0*(b.f0+b.f1)+a.f1*b.f0)%10007;
		res.f1=(a.f1*b.f1)%10007;
	}
	num.push(res);
}
int main(){
	freopen("bds.in","r",stdin);
	freopen("bds.out","w",stdout);
	int l;
	string s;
	cin>>l>>s;
	num.push({1,1});
	for(int i=0;i<l;i++){
		if(s[i]=='(') op.push('(');
		else if(s[i]==')'){
			while(op.top()!='(') calc();
			op.pop();
		}
		else{
			while(op.size()!=0&&mp[s[i]]<mp[op.top()]) calc();
			num.push({1,1});
			op.push(s[i]);
		}
	}
	while(op.size()) calc();
    cout<<num.top().f0;
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。

D. 数列

题目类型：数学

思路

对于这道题目我们可以发现，i其实就是k进制下的i，用数组存储k的正幂次即可快速计算。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a(int a,int b){
	int sum=1;
	for(int i=1;i<=b;i++) sum*=a;
	return sum;
}
signed main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	int k,n,res=0;
	cin>>k>>n;
	for(int i=0;i<=20;i++) if(n>>i&1) res+=a(k,i);
	cout<<res;
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。