小田的01变换（暴力）

思路没想到的原因

又双叒叕是没有想到特判情况，具体见思路。

思路

因为数字只由 $0$和$1$组成，所以只有以下几种情况：

• $n$是$1$,输出$0$；（没想到）
• 都是$0$或都是$1$，输出$0$;（没想到）
• $0$的数量不等于$1$的数量，输出$1$;
• $0$的数量$>1$或 $1$的数量$>1$，输出$2$;
• 其他输出$-1$。

代码

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

int main(){
	freopen("change.in","r",stdin);
	freopen("change.out","w",stdout);
	int n;
	string s;
	cin >>n>>s;
	if(n==1){
		cout <<0;
		return 0;
	}
	int a=0,b=0,c=0;
	for(int i=0;i<s.size();i++){	
		if(s[i]=='0') a++;
		if(s[i]=='1') b++;
		if(a!=b&&(a>1||b>1)) c=1;
	}
	if(a==n||b==n) cout <<0;
	else if(a!=b) cout <<1;
	else if(c) cout <<2;
	else cout <<-1;
	return 0;
}

小田滑雪（模拟）

思路没想到的原因

我对模拟的题目还不够熟练，以后要多积累。

思路

根据时间与路程排序，再来算总时间。 排序可以将路程转换成时间，或将时间转换成路程。

最后的答案要四舍五入，可以先将答案$+0.5$，再转$long$ $long$类型。

代码

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

int main(){
	freopen("snow.in","r",stdin);
	freopen("snow.out","w",stdout);
	vector<int> d,t;
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		string s;
		int a;
		cin >>s>>a;
		if(s=="T") t.push_back(a);
		else d.push_back(a);
	}
	sort(t.begin(),t.end());
	sort(d.begin(),d.end());
	d.push_back(2e9);
	t.push_back(2e9);
	double ans=0,dist=0,v=1;
	int i=0,j=0;
	while(i<t.size()-1||j<d.size()-1){
		double m=1/v;
		v++;
		double tmp=dist+(t[i]-ans)*m;
		if(tmp<d[j]){
			dist=tmp;
			ans=t[i];
			i++;
		}else{
			ans=ans+(d[j]-dist)/m;
			dist=d[j];
			j++;
		}
	}
	ans+=(1000-dist)/(1.0/v);
	cout <<(long long)(ans+0.5);
	return 0;
}

小田赶牛（pair排序+模拟）

思路没想到的原因

当时做的时候是在想结构体，但是我不知道怎样来排序，所以放弃了。以后要多琢磨一下。

思路

首先要$pair$排序，再每次累加每头牛吃花的总数，最后输出。

代码

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

const int N=1e5+10;
pair<int,int> f[N];

bool cmp(pair<int,int> a,pair<int, int> b){
	if(a.first*b.second<a.second*b.first){
		return true;
	}else{
		return false;
	}
}

int main(){
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>f[i].first>>f[i].second;
	}
	long long t=0,ans=0;
	sort(f+1,f+1+n,cmp);
	for(int i=1;i<=n;i++){
		ans=ans+f[i].second*t;
		t+=f[i].first*2;
	}
	cout <<ans;
	return 0;
}

拼接最大数（单调栈）

思路没想到的原因

做的时候感觉太难了，就放弃了。以后要多想一想。

思路

1. 枚举$i$，表示从第一个序列得到长度为$i$字典序最大的子序列，从第二序列得到长度为$k-i$的字典序最大的子序列；
2. 写一个求序列$a$长度为$k1$，字典序最大的子序列的函数；
3. 写一个能合并通过$2$得到的两个序列的函数，保证合并的两个序列字典序也是最大的；
4. 更新答案，比较和之前的答案谁大，大就更新。

代码

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

vector<int> a,b;

int cmp_n(vector<int> a,int id_a,vector<int> b,int id_b){
	int len_a=a.size();
	int len_b=b.size();
	while(id_a<len_a&&id_b<len_b){
		if(a[id_a]!=b[id_b]){
			return a[id_a]>b[id_b];
		}
		id_a++;
		id_b++;
	}
	if(id_a<len_a){
		return 1;
	}else{
		return 0;
	}
}

vector<int> get(vector<int> a,int k){
	int n=a.size();
	if(n<=k){
		return a;
	}
	int t=n-k;
	vector<int> stk;
	for(int i=0;i<n;i++){
		while(stk.size()>0&&stk.back()<a[i]&&t>0){
			stk.pop_back();
			t--;
		}
		if(stk.size()<k){
			stk.push_back(a[i]);
		}else{
			t--; 
		}
	}
	return stk;
}

vector<int> hb(vector<int> a,vector<int> b){
	int len1=a.size();
	int len2=b.size();
	vector<int> res;
	int i=0,j=0;
	while(i<len1&&j<len2){
		if(a[i]>b[j]){
			res.push_back(a[i++]);
		}
		else if(a[i]<b[j]){
			res.push_back(b[j++]);
		}
		else{
			if(cmp_n(a,i,b,j)>0){
				res.push_back(a[i++]);
			}else{
				res.push_back(b[j++]);
			}
		}
	}
	while(i<len1){
		res.push_back(a[i++]);
	}
	while(j<len2){
		res.push_back(b[j++]);
	}
	return res;
}

int main(){
	freopen("big.in","r",stdin);
	freopen("big.out","w",stdout);
	int n,m,k;
	cin >>n>>m>>k;
	for(int i=1;i<=n;i++){
		int z;
		cin >>z;
		a.push_back(z);
	}
	for(int i=1;i<=m;i++){
		int z;
		cin >>z;
		b.push_back(z);
	}
	vector<int> ans(k,0);
	for(int i=0;i<=k;i++){
		int len_1=i;
		int len_2=k-i;
		vector<int> ans1=get(a,len_1);
		vector<int> ans2=get(b,len_2);
		vector<int> cmp=hb(ans1,ans2);
		if(cmp.size()==k&&cmp_n(cmp,0,ans,0)>0){
			ans=cmp;
		}
	}
	for(auto i:ans){
		cout <<i;
	}
	return 0;
}

小W运水（Dijkstra最短路）

思路没想到的原因

会写$Dijkstra$模板，但我不知道怎样去改。以后我要灵活变通。

思路

$Dijkstra$模板题，只需加几个特述条件就行。

• 从后往前搜；
• 记得计算水量，如果满足$g[t][j]<200$与$dist[t]/(1-g[t][j]*0.01)<dist[j]$，那么$dist[j]=dist[t]/(1-g[t][j]*0.01);$

代码

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

int g[2010][2010];
int n,m,s,e;
double dist[2010]; 
bool st[2010];

void f(){
	for(int i=1;i<=n;i++){
		dist[i]=0x3f3f3f3f;
	}
	dist[e]=100;
	for(int i=1;i<=n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[j]<dist[t])){
				t=j;
			}
		}
		st[t]=true;
		for(int j=1;j<=n;j++){
			if(g[t][j]<200&&dist[t]/(1-g[t][j]*0.01)<dist[j]){
				dist[j]=dist[t]/(1-g[t][j]*0.01);
			}
		}
	}
}

int main(){
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
	cin>>n>>m;
	int x,y,z;
	memset(g,0x3f,sizeof(g));
	while(m--){
		cin>>x>>y>>z;
		g[x][y]=z;
		g[y][x]=z;
	}
	cin>>s>>e;
	f();
	printf("%.8lf",dist[s]);
    return 0;    
}

WOW（前缀和）

思路没想到的原因

在考试时认为剩下的时间已经不够做出这道题了，所以没有去想。以后即使时间很少，也要认真去思考。

思路

对于每一个 $o$，我们只要统计这个$o$前面$vv$的数量和后面$vv$的数量，那么这个$o$能组成$vvovv$的数量就是前面的$vv$数 *后面的$vv$数。

那么我们用一个 $a$和$b$数组，$a[i]$代表第 $i$个字符前面有多少个$vv$，

$b[i]$则是后面的。那么第$i$个字符能组成的$wow$数就是$a[i]*b[i]$。

当$s[i]=='v'$时，如果$s[i-1]=='v'$,说明多了一个新的$vv$,$a[i]=a[i-1]+1$。$b$ 数组同理。

代码

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

int main(){
	freopen("wow.in","r",stdin);
	freopen("wow.out","w",stdout);
	string s;
	cin >>s;
	long long f0=0,f1=0,f2=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='o'){
			f1+=f0;
		}
		else if(s[i-1]=='v'){
			f2+=f1;
			f0++;
		}
	}
	cout <<f2;
	return 0;
}

谢谢