$T1$

考试错误：无。

思路：挨个查找就行了，只要注意将大写转为小写即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	freopen("cal.in","r",stdin);
	freopen("cal.out","w",stdout);
	string d;
	getline(cin,d);
	string s;
	getline(cin,s);
	string t="";
	int cnt=0,ans=0;
	for(int i=0;i<d.size();i++){
		if(d[i]>='A'&&d[i]<='Z') d[i]+=32;
	}
	for(int i=0;i<s.size();i++){
		if(s[i]!=' '){
			int I=i;
			t="";
			while(s[i]!=' '&&i<s.size()){
				if(s[i]>='A'&&s[i]<='Z'){
					s[i]+=32;
				}
				t.push_back(s[i]);
				i++;
			}
			if(t==d){
				cnt++;
				if(cnt==1) ans=I;
			} 
		}
	}
	if(cnt==0){
		cout << -1;
		return 0;
	}
	cout << cnt << " " << ans;
}

$T2$

考试错误：暴力骗了$60$分，没想到用归并去优化。

思路：每次将胜利的人和失败的人分到两个组，再归并到一起即可，时间复杂度变为$O(nr)$。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct PII{
	int first,second,num;
};
const int N=5e5+50;
PII a[N],win[N],lose[N];
bool cmp(PII a,PII b){
	if(a.first==b.first) return a.num<b.num;
	return a.first>b.first;
}
signed main(){
	freopen("ruishi.in","r",stdin);
	freopen("ruishi.out","w",stdout);
	int n,r,q;
	cin >> n >> r >> q;
	for(int i=1;i<=n*2;i++){
		cin >> a[i].first;
		a[i].num=i;
	}for(int i=1;i<=n*2;i++){
		cin >> a[i].second;
	}
	sort(a+1,a+2*n+1,cmp);
	while(r--){
		int x=1,y=1;
		for(int i=1;i<=2*n;i+=2){
			if(a[i].second<a[i+1].second) a[i+1].first++,win[x++]=a[i+1],lose[y++]=a[i];
			else a[i].first++,win[x++]=a[i],lose[y++]=a[i+1];
		}
		int i=1,j=1;
		x=1;
		while(i<=n&&j<=n){
			if(cmp(win[i],lose[j])) a[x++]=win[i++];
			else a[x++]=lose[j++];
		}
		while(i<=n) a[x++]=win[i++];
		while(j<=n) a[x++]=lose[j++];
	}
	cout << a[q].num;
}

$T3$

考试错误：不会。

思路：

$DP$:

本题要用到stack<vector>

初始化：s.push({1,1})

状态转移方程 :

+:s.push({a[0]*b[0]%mod,a[0]*b[1]+a[1]*b[0]+a[1]*b[1])%mod})

*:s.push({(a[0]*b[1]+a[1]*b[0]+a[0]*b[0])%mod,a[1]*b[1]%mod})

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=10007;
stack<char> o;
stack<vector<int> > s;
void eval(){
	auto c=o.top();
	o.pop();
	auto a=s.top();
	s.pop();
	auto b=s.top();
	s.pop();
	if(c=='+'){
		s.push({a[0]*b[0]%mod,(a[0]*b[1]+a[1]*b[0]+a[1]*b[1])%mod});
	}else{
		s.push({(a[0]*b[1]+a[1]*b[0]+a[0]*b[0])%mod,a[1]*b[1]%mod});
	}
}
signed main(){
	freopen("bds.in","r",stdin);
	freopen("bds.out","w",stdout);
	int n;
	string q;
	cin >> n >> q;
	map<char,int> pr;
	pr['(']=0,pr['+']=1,pr['*']=2;
	s.push({1,1});
	for(auto c:q){
		if(c=='(') o.push(c);
		else if(c=='+'||c=='*'){
			while(o.size()&&pr[c]<=pr[o.top()]&&o.top()!='(') eval();
			s.push({1,1});
			o.push(c);
		}else{
			while(o.size()&&o.top()!='(') eval();
			o.pop();
		}
	}
	while(o.size()) eval();
	cout << s.top()[0]%mod;
}

$T4$

考试错误：无。

思路：递推题，每次先让$a_{2^i}=k_i$，然后把除了$a_i$以外的部分复制一份并加上$a_i$，最后把更改后的数组接在后面。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5050;
int a[N];
int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1) res*=a;
		b/=2;
		a*=a;
	}
	return res;
}
signed main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	int n,k;
	cin >> k >> n;
	a[1]=1;
	int x=2,y=1;
	for(int i=1;x/2<=n;i++,x*=2,y*=2){
		a[x]=qmi(k,i);
		for(int j=x-1;j>y;j--){
			a[j]=qmi(k,i-1)+a[j-y];
		}
	}
	cout << a[n];
}