统计单词数（模拟）

思路

如果找到了这个单词，判断是否是独立的单词。也要把大小写转成一致的。

这里科普一下：C++有转换大小写的函数。

• 转换成大写：toupper；
• 转换成小写：tolower。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("cal.in","r",stdin);
	freopen("cal.out","w",stdout);
    string dc,jz;
    getline(cin,dc);
    getline(cin,jz);
    int i=0;
	int j=0;
    int cnt=0,res=0;
    for(i=0;i<jz.size();++i){
        for(j=0;j<dc.size();++j){
            if(toupper(dc[j])!=toupper(jz[i+j])){
            	break;
			}
            if(i>0&&jz[i-1]!=' '){
            	break;
			}
        }
        if(j==dc.size()&&(i+j==jz.size()||jz[i+j]==' ')){
            cnt++;
            if(cnt==1){
            	res=i;
			}
        }
    }
    if(cnt!=0){
		cout <<cnt<<" "<<res;
	}else{
		cout <<"-1";
	}
    return 0;
}

瑞士轮（模拟）

思路没想到的原因

只考虑了暴力的写法（虽然没有得分），没有考虑优化情况。

思路

我们会发现，每次$sort$排序都很耗时，但胜者和败者相对的位置不会变，所以可以用归并排序来合并。

例如，一个字符串$s$，我们可以把$s$分成胜组（$s1$）与败组（$s2$）。最后合并成$s1s2$这一个字符串。

代码

#include <bits/stdc++.h>
using namespace std;

struct qwerty{
	int ans,num,w;
};

const int tt=2e5+10;
qwerty s[tt],a[100010],b[100010];
int n,r,q;

bool cmp(qwerty a,qwerty b){
	if(a.ans==b.ans){
		return a.num<b.num;
	}
	return a.ans>b.ans;
}

int main(){
	freopen("ruishi.in","r",stdin);
	freopen("ruishi.out","w",stdout);
	int t=1,z=1;
	int res=1;
	cin>>n>>r>>q;
	for(int i=1;i<=n*2;i++){
		cin >>s[i].ans;
		s[i].num=i;
	}
	for(int i=1;i<=n*2;i++){
		cin >>s[i].w;
	}
	sort(s+1,s+1+n*2,cmp);
	while(r--){
		t=1,z=1;
		for(int i=1;i<n*2;i+=2){
			if(s[i].w>s[i+1].w){
				s[i].ans++;
				a[t++]=s[i];
				b[z++]=s[i+1];
			}else{
				s[i+1].ans++;
				a[t++]=s[i+1];
				b[z++]=s[i];
			}
		}
		t=1,z=1;
		int i=1;
		while(t<=n&&z<=n){
			if(cmp(a[t],b[z])){
				s[i++]=a[t++];
			}else{
				s[i++]=b[z++];
			}
		} 
		while(t<=n){
			s[i++]=a[t++];
		}
		while(z<=n){
			s[i++]=b[z++];
		}
	}
	cout <<s[q].num;
	return 0;
}

表达式的值（栈&哈希）

思路没想到的原因

当时没有思路，被题面劝退了，应该以后对自己有信心。

思路

列举样例总结规律后，可发现这其实是中缀表达式求值，但需要分结果为零的数量和分结果为一的数量两种情况。

代码

#include <bits/stdc++.h>
using namespace std;

const int mod=1e4+7;
stack<vector<int>> num;
stack<char> op;

void eval(){
	auto c=op.top();
	op.pop();
	auto a=num.top();
	num.pop();
	auto b=num.top();
	num.pop();
	if(c=='+'){
		num.push({a[0]*b[0]%mod,(a[0]*b[1]+a[1]*b[0]+a[1]*b[1])%mod});
	}else{
		num.push({(a[0]*b[1]+a[1]*b[0]+a[0]*b[0])%mod,a[1]*b[1]%mod});
	}
}

unordered_map<char,int> pr{{'(',0},{'+',1},{'*',2}};

int main(){
	freopen("bds.in","r",stdin);
	freopen("bds.out","w",stdout);
	int l;
	cin >>l;
	string str;
	cin >>str;
	num.push({1,1});
	for(auto ch:str){
		if(ch=='(') op.push(ch);
		else if(ch==')'){
			while(op.top()!='(') eval();
			op.pop();
		}else{
			while(op.size()&&op.top()!='('&&pr[ch]<=pr[op.top()]){
				eval();
			}
			num.push({1,1});
			op.push(ch);
		}
	}
	while(!op.empty()) eval();
	cout <<(num.top()[0]+mod)%mod;
	return 0;
}

数列（递归）

思路

通过打标可以发现： 0,1,0+1,2,0+2,1+2,0+1+2,3

2后面的式子是通过前面的加上一个2得到的。

举个例子，3后面的是： 0+3,1+3,0+1+3,2+3,0+2+3,1+2+3,0+1+2+3，

是前面的式子0,1,0+1,2,0+2,1+2,0+1+2全都加上一个3得到的。

所以只需枚举加上快速幂即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e5+10;
int f[tt];

int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a;
		a=a*a;
		b=b>>1;
	}
	return res;
}

signed main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	int k,n;
	cin >>k>>n;
	int cnt=2;
	int ans=1;
	f[1]=1;
	for(int i=1;cnt/2<=n;ans*=2,cnt*=2,i++){
		f[cnt]=qmi(k,i);
		for(int j=cnt-1;j>=ans;j--){
			int w=f[j-ans];
			f[j]=qmi(k,i-1)+w;
		}
	}
	cout <<f[n];
	return 0;
}

谢谢