T1小田的01变换（暴力 分类讨论）

题目传送门

问题

PS：好像没有，一眼秒的😄

思路

一道很简单的思考题，对于每一个数据 如果0和1数量不相等，则一次就可以消掉，如果相等，则两次可以消掉

这也很好证明（作者的思路），因为此时01数量一定相等，所以我们选定区间a[1],a[2],...,a[n−1]a[1],a[2],...,a[n-1]，一定有一个0或1被排出去，所以此时0和1一定不相等，所以改变这个区间之后还剩1个异类（改变后的那个种类一定是多的，也就是被排出的那个数的对立面），所以还要1次操作

附AC代码：

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

T2小田滑雪（模拟）

题目传送门

总结（自己）

代码太长了 要改变自己的码风

思路

比较时间和路程的失误哪个先来，最后以当前速度走完1000米就行

附AC代码

#include<bits/stdc++.h>
using namespace std;
int n,jt=1,st=1,x;
double sj[10010],ss[10010],su=1.0,j,idx=1,s;
char c;
void zj()
{
	s+=(sj[jt]-j)/su;
	j=sj[jt];
	idx++;
	jt++; 
	su=1/idx;
}
void zs()
{
	j+=(ss[st]-s)*su;
	s=ss[st];
	idx++;
	st++; 
	su=1/idx;
}
int main()
{
	freopen("snow.in","r",stdin);
	freopen("snow.out","w",stdout);
	cin>>n;
	int sidx=0,jidx=0;
	for(int i=1;i<=n;i++)
	{
		cin>>c>>x;
		if(c=='T')
		{
			ss[++sidx]=x; 
		}
		else
		{
			sj[++jidx]=x;
		}
	}
	sort(sj+1,sj+jidx+1);
	sort(ss+1,ss+sidx+1); 
	/*
	for(int i=1;i<=jidx;i++)
	{
		cout<<sj[i]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=sidx;i++)
	{
		cout<<ss[i]<<" ";
	}
	*/
	while(st<=sidx&&jt<=jidx)
	{
		int xs=ss[st]-s;
		if(xs*su+j==sj[jt])
		{
			zs();
			idx++;
			jt++;
			su=1/idx;
		}
		else if(xs*su+j<sj[jt]) zs();
		else zj();
	}
	while(st<=sidx) zs();
	while(jt<=jidx) zj();
	if(j<1000)###
	{
		s+=(1000-j)/su;
	}
	cout<<int(s+0.5);
	return 0;
}

T3小田赶牛（贪心）

题目传送门

总结（自己）

手搓快排的时候错了[哭] 要多复习基础知识

思路

很简单的结构体排序（pair也行），将每只牛的性价比(赶回这头牛会被吃的花数)排序并计算即可

附AC代码

#include<bits/stdc++.h>
using namespace std;
long long n;
long long hz,ans;
struct cowH
{
	long long c,h;
}chch[200010];
bool cmp(cowH a,cowH b)
{
	return a.c*b.h<a.h*b.c;
}
int main()
{
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	cin>>n;
	for(long long i=1;i<=n;i++)
	{
		cin>>chch[i].c>>chch[i].h;
		hz+=chch[i].h;
	}
	sort(chch+1,chch+n+1,cmp);
	for(long long i=1;i<=n;i++)
	{
		ans+=(hz-chch[i].h)*chch[i].c;
		hz-=chch[i].h;
	}
	cout<<ans*2;
	return 0;
}

T4 拼接最大数（枚举）

题目传送门

总结（自己）

这题可以骗分的，但没时间了www，要合理分配时间

思路

思路简单，代码一言难尽 先要定义三个函数分别是取一个数组长度为k的最大的数 合并和比较

然后枚举一个长度分界点i 那么两个区间一定会分别取ii和n−in - i的长度的数 用第一个函数得到 然后用第二个函数合并再用第三个函数比较就行

附AC代码

#include<bits/stdc++.h>
using namespace std;
vector<int> dx(vector<int> a,int k)
{
	int n=a.size();
	if(n<=k) return a;
	int c=n-k;
	vector<int> res;
	for(int i=0;i<n;i++){
		while(res.size()>0&&res.back()<a[i]&&c>0){
			res.pop_back();
			c--; 
		}
		if(res.size()<k) res.push_back(a[i]);
		else c--;
	}
	return res;
}
bool bhz(vector<int> a,int ac,vector<int> b,int bc)
{
	int l1=a.size(),l2=b.size();
	while(ac<l1&&bc<l2){
		if(a[ac]!=b[bc]) return a[ac]>b[bc];
		ac++;
		bc++;
	}
	if(ac<l1) return 1;
	else return 0;
}
vector<int> hb(vector<int> a, vector<int> b)
{
	int l1=a.size(),l2=b.size();
	vector<int> res;
	int i=0,j=0;
	while(i<l1&&j<l2){
		if(a[i]>b[j]) res.push_back(a[i++]);
		else if(a[i]<b[j]) res.push_back(b[j++]);
		else{
			if(bhz(a,i,b,j)==1) res.push_back(a[i++]);
			else res.push_back(b[j++]);
		}
	}
	while(i<l1) res.push_back(a[i++]);
	while(j<l2) 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 c;
		cin>>c;
		a.push_back(c);
	}
	for(int i=1;i<=m;i++)
	{
		int c;
		cin>>c;
		b.push_back(c);
	}
	vector<int> ans(k,0);
	for(int i=0;i<=k;i++)
	{
		vector<int> s1=dx(a,i);
		vector<int> s2=dx(b,k-i);
		vector<int> res=hb(s1,s2);
		if(bhz(res,0,ans,0)==1&&res.size()==k) ans=res;
	}
	for(auto x:ans) cout<<x;
	return 0;
}

T5小W运水(最短路)

题目传送门

总结（自己）

模板忘了（以后考试前要先复习模板）

思路

dijkstra模板题，只要改个小数，从终点开始走即可

附AC代码

#include<bits/stdc++.h>
using namespace std;
bool b[1005];
int n,m,q,z;
int l[2005][2005];
double d[2005];
void dd(){
	for(int i=1;i<=n;i++){
		d[i]=0x3f3f3f3f;
	}
	d[z]=100;
	for(int i=1;i<=n;i++)
	{	
		int zx=-1;
		for(int j=1;j<=n;j++)
		{
			if(!b[j]&&(zx==-1||d[j]<d[zx]))
			{
				zx=j;
			}
		}
		b[zx]=1;
		for(int j=1;j<=n;j++)
		{
			if(l[zx][j]<200&&d[zx]/(1-l[zx][j]*0.01)<d[j])
			{
				d[j]=d[zx]/(1-l[zx][j]*0.01);
			}
		}
	}
}
int main()
{
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	cin>>n>>m;
	memset(l,0x3f,sizeof(l));
	for(int i=1;i<=n;i++) l[i][i]=0;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		l[x][y]=z;
		l[y][x]=z;
	}
	cin>>q>>z; 
	dd();
	printf("%.8lf",d[q]);
	return 0;
}

T6WOW(dp)

题目传送门

总结（自己）

虽然比较难（在当时）但是也可以骗分www*2

思路

状态机dp 要将很多状态一并转移 同样dp三要素

f[i][0]定义：从1到 i vv的数量

f[i][1]定义：从1到 i vvo的数量

f[i][2]定义：从1到 i vvovv的数量

初始化： 全部为0

递推式：

如果a[i]是v且a[i-1]也是v则 f[i][0]++ f[i][2]+=f[i-1][1](vvo后面可以接)

否则f[i][1]+=f[i-1][0]（o前面可以接vv）

随便A了现在

附AC代码

#include<bits/stdc++.h>
using namespace std;
long long f[1000010][3];
string s;
int main()
{
	freopen("wow.in","r",stdin);
	freopen("wow.out","w",stdout);
	cin>>s;
	s=" "+s;
	for(int i=1;i<s.size();i++)
	{
		f[i][0]+=f[i-1][0];
		f[i][1]+=f[i-1][1];
		f[i][2]+=f[i-1][2];
		if(s[i]=='o') f[i][1]+=f[i-1][0];
		else if(s[i-1]=='v'){
			f[i][0]++;
			f[i][2]+=f[i-1][1];
		}
	}
	cout<<f[s.size()-1][2];
	return 0;
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 11ms
  4. Powered by Hydro v5.0.0-beta.13 Community