A. 小田的01变换

题目类型：分类讨论

思路

• 若n==2且0与1的数量一样，输出-1。

• 若0的数量等于n或1的数量等于n，输出0。

• 若0的数量==1的数量，输出2。

• 若上面的条件都不成立，输出1。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  int main(){
  freopen("change.in","r",stdin);
  freopen("change.out","w",stdout);
  int n,cnt_0=0,cnt_1=0;
  cin>>n;
  string s;
  cin>>s;
  for(int i=0;i<s.size();i++){
  if(s[i]=='0') cnt_0++;
  if(s[i]=='1') cnt_1++;
  }
  if(n==2&&cnt_0==cnt_1) cout<<-1;
  else if(cnt_0==n||cnt_1==n) cout<<0;
  else if(cnt_0==cnt_1) cout<<2;
  else cout<<1;
  return 0;
  }
  

  这题在写的时候把

  freopen("change.in","r",stdin);
  freopen("change.out","w",stdout);
  

写成

freopen("change.in ","r",stdin);
freopen("change.out ","w",stdout);

了

所以下次要仔细检查，一定不能再犯这种低级的错误了，所以freopen还要熟记，连空格都要记。

B. 小田滑雪

题目类型：模拟

思路

• 根据时间与路程排序，再来算总时间，最后输出答案。
• 排序可以将路程转换成时间，或将时间转换成路程，最后输出答案即可。
• 注意：最后的答案要四舍五入，可以先将答案+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> A,B;
int n;
cin>>n;
for(int i=1;i<=n;i++){
char s;
int c;
cin>>s>>c;
if(s=='T') A.push_back(c);
else B.push_back(c);
}
sort(A.begin(),B.end());
sort(B.begin(),B.end());
A.push_back(2e9);
B.push_back(2e9);
double ans=0,dist=0,v=1;
int i=0,j=0;
while(i<A.size()-1||j<B.size()-1){
double x=1/v;
v++;
double p=dist+(A[i]-ans)*x;
if(p<B[j]) {
dist=p;
ans=A[i];
i++;
}
else{
ans=ans+(B[j]-dist)/x;
dist=B[j];
j++;
}
}
ans+=(1000-dist)/(1.0/v);
cout<<(long long)(ans+0.5);
return 0;
}

这题只把%30的数据写了，下次争取写一个AC代码。

C. 小田赶牛

题目类型：排序加模拟

思路

先结构体排序，返回a.first乘b.second<a.second乘b.first，再每次累加每头牛吃花的总数，最后输出答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
PII a[N];
bool cmp(PII a, PII b){
return a.first*b.second<a.second*b.first;
}
int main(){
freopen("cow.in","r",stdin);
freopen("cow.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
sort(a+1,a+1+n,cmp);
long long c=0,ans=0;
for(int i=1;i<=n;i++){
ans+=a[i].second*c;
c+=a[i].first*2;
}
cout<<ans;
return 0;
}

这题不知道怎么累加每头牛吃花的总数，所以就放弃了，下次不能轻易放弃。

D. 拼接最大数

题目类型：栈

思路

• 先枚举i，从第一个序列得到长度为i字典序最大的子序列，再从第二序列得到长度为k-i的字典序最大的子序列。
• 假设a的长度是n，那么也就意味着我们要抛弃n-k1个数，所以我们可以用一个单调栈来维护。
• 写一个能合并两个序列的函数，保证合并的两个序列字典序也是最大的，也就是用归并排序合并部分。
• 最后比较和之前的答案谁大，大就更新。
• 最后输出答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
int cmp(vector<int> A,int ida,vector<int> B,int idb){
	int len1=A.size(),len2=B.size();
	while(ida<len1&&idb<len2){
		if(A[ida]!=B[idb]) return A[ida]>B[idb];
		ida++,idb++;
	}
	if(ida<len1) 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> merge(vector<int> A,vector<int> B){
	int len1=A.size(),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(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;
	vector<int> A,B;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		A.push_back(x);
	}
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		B.push_back(x);
	}
	vector<int> ans(k,0);
	for(int i=0;i<=k;i++){
		int len1=i,len2=k-i;
		vector<int> tmp1=get(A,len1);
		vector<int> tmp2=get(B,len2);
		vector<int> res=merge(tmp1,tmp2);
		if(res.size()==k&&cmp(res,0,ans,0)>0) ans=res;
	}
	for(auto x:ans) cout<<x;
	return 0;
}

这题在写的时候不知道思路，就放弃了，下次要想着将各种算法结合起来写。

E. 小W运水

题目类型：最短路

思路

这道题其实就是最短路算法模版改一点点即可，将int类型改成double类型就好了，最后输出答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
int g[2010][2010];
int n,m,s,e;
double dist[2010]; 
bool st[2010];
void dijkstra(){
	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]=1;
		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;
	memset(g,0x3f,sizeof(g));
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		g[x][y]=z;
		g[y][x]=z;
	}
	cin>>s>>e;
	dijkstra();	
	printf("%.8lf",dist[s]);
    return 0;
}

这道题我实在没想到，下一次要再好好看题。

F. WOW

题目类型：前缀和或DP

思路

如果是前缀和的话，那么我们用一个 𝑎*和𝑏数组，𝑎[𝑖]代表第 𝑖个字符前面有多少个𝑣𝑣，𝑏[𝑖]]则是后面的。那么第𝑖个字符能组成的𝑤𝑜𝑤数就是𝑎[𝑖]∗𝑏[𝑖]，最后输出答案即可。

代码

前缀和

#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 a=0,b=0,c=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='o') b+=a;
		else if(s[i-1]=='v'){
			c+=b;
			a++;
		}
	}
	cout<<c;
	return 0;
}

DP还没有学过，老师说以后会单独开一节课来讲DP。