张家宁的博客
2024暑期集训（DAY1）
张家宁 LV1 筑基期 LV 5 @ 2024-7-8 21:04:04

DAY1

本次考试AC率：6/1（13.33…%）主要是因为没有深度思考，只想到了暴力。

A 小田的宝石镇

是暴力，也是唯一一题AC的题。这个虽然看着是dijstal但是路线是固定的，所以只用判断两条路。唯一要注意的是long long因为int存不下。题解：

#include<bits/stdc++.h>
using namespace std;
long long n,a,b; //int存不下
int main(){
freopen("gem.in", "r", stdin);
freopen("gem.out", "w", stdout);//考试需要，自测试不用
cin>>a>>b;
if(a*2<=b){//判断两条路
n=a*11;
cout<<n;
}else {
n=b;
cout<<n*5+a;
}
return 0;
}

B 小田的好数组

当时没理解：不完全相同的意思，以后不再呆板，就可以避免。其实不是0就是n，0就是本来是排好序的数组，n就是其他的情况题解：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int op[N],n,ans;
int main(){
freopen("hsz.in","r",stdin);
freopen("hsz.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>op[i];
if(op[i-1]<=op[i]){
ans++;
}
}
if(ans==n){
cout<<0;
return 0;
}
cout<<n;
return 0;
}

C 小田的数字合并

这时乍一眼看是要求最大值与最小值的差；但最小的不一定是在左和右。但可以进一步推导，可以枚举中点，也就是断点。计算出左右两边的值，取最大再减去中点，与之前的ans取最大值。这一题错了的原因是：原本max(s[i-1],s[n]-s[i])-a[i];写成了：max(s[i-1],s[n]-a[i])-a[i]; 题解：

#include<bits/stdc++.h>
using namespace std;
int a[200010];
long long s[200010],ans=0;
bool op=0;
int main(){
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++){
ans=max(ans,max(s[i-1]-a[i],s[n]-s[i]-a[i]));
}
cout<<ans;
return 0;
}

D. 化学式的原子数

一道表达式求值，用哈希栈做，难的点无非是在判断括号这：

遇到左括号新建一个哈希表。
遇到右括号找到右边的值，在记录下是什么原子，之后就加上去

代码

#include<bits/stdc++.h>
using namespace std;
stack<map<string,int>> stk;
string s;
int i,len;
int getint(){
	if(!isdigit(s[i])||i==len){
		return 1;
	}
	int num=0;
	while(isdigit(s[i])&&i<len){
		num=num*10+s[i]-'0';
		i++;
	}
	return num;
}
string getstr(){
	string us;
	us+=s[i++];
	while(s[i]>='a'&&s[i]<='z'&&i<len){
		us+=s[i++];
	}
	return us;
}
int main(){
	freopen("atom.in", "r", stdin);
	freopen("atom.out","w",stdout);
	cin>>s;
	len=s.size();
	stk.push({});
	while(i<len){
		if(s[i]=='('){
			i++;
			stk.push({});
		}else if(s[i]==')'){
			i++;
			int num=getint();
			auto sd=stk.top();
			stk.pop();
			for(auto &is:sd){
				string u=is.first;
				int v=is.second;
				stk.top()[u]+=v*num;
			}
		}else{
			string u=getstr();
			int v=getint();
			stk.top()[u]+=v;
		}
	}
	auto un=stk.top();
	for(auto &is:un){
		string u=is.first;
		int v=is.second;
		cout<<u<<" "<<v<<endl;
	}
	return 0;
}

E小W挖宝藏

深搜，但是得用f[i][j]来表示可以获得的宝藏数，用来杜绝重复搜降低时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int a[110][110],ans=0,sx,sy;
int f[110][110];
int n,m;
int dvs(int x,int y){
	if(f[x][y]!=0){
		return f[x][y];
	}
	int sd=0;
	for(int i=0;i<4;i++){
		int nowx=x+dx[i],nowy=y+dy[i];
		if(a[nowx][nowy]>=a[x][y]){
			continue;
		}
		if(nowx<1||nowx>n||nowy<1||nowy>m){
			continue;
		}
		int z=dvs(nowx,nowy);
		f[x][y]=max(f[x][y],z+1);
	}
	return f[x][y];
}
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=dvs(i,j)+1;
			if(ans<x){
				ans=x;
				sx=i;
				sy=j;
			}	
		}
	}
	cout<<sx<<" "<<sy<<endl;
	cout<<ans;
	return 0;
}

F 小z的等待时间

一道简单的DP；主要没发现可以同时减少，所以思路错了。我长得比你高，可以不受你指挥，相同的，长得比你矮才会。所以我们将长得比前面矮的来累加。

题解：

#include<bits/stdc++.h>
using namespace std;
int f[100010];
int main(){
freopen("flowers.in", "r", stdin);
freopen("flowers.out", "w", stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>f[i];
}
for(int i=n-1;i>=1;i--){
if(f[i]<=f[i+1]){
f[i]=f[i+1]+1;
}
}
cout<<f[1];
return 0;
}

DAY2

小田的消消乐游戏

思路

本题是一道思考题，没有包含什么算法。如果仔细思考，就会发现：

如果可以三步消除的那么两步也可以消除。
在这里，答案不是1，0就是2。
我们可以枚举节点，如果a[1]与a[i]相等&&a[n]==a[i+1],那么这个节点就可以删掉（2步）
做个特判：如果a[1]==a[n]那么就可以1步删除
那不可以删除的呢？如果没找到就是不可以删除的。

题型

思考

注意的点

无

代码

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

小田的气球爆炸啦

思路

这题有很多情况，因为是分类讨论所以需要将下面情况来一一解决

如果n只有2，且2个数都是相等的，那么只能输出0。
如果有一个数比其他的加起来都大，那么就只剩下一种情况。
如果所有数之和是奇数个，那么就有n种情况。
如果所有数之和是偶数个，那么只要一种的数量大于1，就可以算作一种情况。

题型

分类讨论

注意的点

分清楚先后顺序。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100010];
long long s;
int main(){
	freopen("balloon.in", "r", stdin);
	freopen("balloon.out", "w", stdout);
	int n,o=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		o=max(o,a[i]);
		s+=a[i];
	}
	if(a[1]==a[2]&&n==2){
		cout<<0;
		return 0;
	}
	if(o>=s-o){
		cout<<1;
		return 0;
	}
	if(s%2!=0){
		cout<<n;
		return 0;
	}else{
		int ans=0;
		for(int i=1;i<=n;i++){
			if(a[i]>=2){
				ans++;
			}
		}
		cout<<ans;
		return 0;
	}
	return 0;
}

小k的加减游戏

思路

暴力枚举所有情况

注意的点

不要出错

题型

无

代码

#include<bits/stdc++.h>
using namespace std;
char st[100010];
int main(){
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	int n,a,b,c;
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++){
		char o[3];
		cin>>o[1]>>o[2];
		if(o[1]=='A'){
			if(o[2]=='B'){
				if(a==b&&b==0){
					cout<<"No"<<endl;
					return 0;
				}
				if(a>=b){
					b++;
					a--;
					st[i]='B';
				}else{
					a++;
					b--;
					st[i]='A';
				}
			}else{
				if(a==c&&c==0){
					cout<<"No"<<endl;
					return 0;
				}
				if(a>=c){
					c++;
					a--;
					st[i]='C';
				}else{
					a++;
					c--;
					st[i]='A';
				}
			}
		}else if(o[1]=='B'){
			if(o[2]=='A'){
				if(a==b&&b==0){
					cout<<"No"<<endl;
					return 0;
				}
				if(a>=b){
					b++;
					a--;
					st[i]='B';
				}else{
					a++;
					b--;
					st[i]='A';
				}
			}else{
				if(c==b&&b==0){
					cout<<"No"<<endl;
					return 0;
				}
				if(c>=b){
					b++;
					c--;
					st[i]='B';
				}else{
					c++;
					b--;
					st[i]='C';
				}
			}
		}else{
			if(o[2]=='A'){
				if(c==a&&a==0){
					cout<<"No"<<endl;
					return 0;
				}
				if(a>=c){
					c++;
					a--;
					st[i]='C';
				}else{
					a++;
					c--;
					st[i]='A';
				}
			}else{
				if(c==b&&c==0){
					cout<<"No"<<endl;
					return 0;
				}
				if(b>=c){
					c++;
					b--;
					st[i]='C';
				}else{
					b++;
					c--;
					st[i]='B';
				}
			}
		}
	}
	cout<<"Yes"<<endl;
	for(int i=1;i<=n;i++){
		cout<<st[i]<<endl;
	}
	return 0;
}

蓬莱山仙峰台

思路

将所有山都当作仙峰台，然后根据题目来进行处理。结果遍历一遍数组，统计还剩多少仙峰台

题型

标记

注意的点

无

代码

#include<bits/stdc++.h>
using namespace std;
bool st[100010];
int a[100010];
int main(){
	freopen("penglai.in", "r", stdin);
	freopen("penglai.out", "w", stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		st[i]=1;
	}
	for(int i=1;i<=m;i++){
		int x,v;
		cin>>x>>v;
		if(a[x]>=a[v]){
			st[v]=0;
		}
		if(a[v]>=a[x]){
			st[x]=0;
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(st[i]==1){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

数学题1

这道数学题只要推得够深，时间复杂度就少。

我们知道，a+b是bXgcd(a,b)的倍数，bXgcd(a,b)就是b的倍数，所以a+b也是b的倍数。那么a也是b的倍数，所以公式就变成了

a+b=x*b*b

x是一个不定值 a最大可以取n,所以我们只要枚举b，将所有可能记录下来就可以了

公式

ans+=(n+b)/b/b。

优化成：

ans+=(n/b+1)/b。

记得ans最后要减去重复的1

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("math1.in", "r", stdin);
	freopen("math1.out", "w", stdout);
	long long n,m;
	cin>>n>>m;
	long long ans=0;
	for(long long i=1;i<=m;i++){
		ans+=(n+i)/i/i;	
	}
	cout<<(long long)(ans-1);
	return 0;
}

小z的徒步旅行

思路

我们先算出所有路径，然后减去都是长路线的，最后将所有的都加上

代码

#include<bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
long long l[110],s[110],r[110],dp[1010][110];
int main(){
	freopen("walk.in", "r", stdin);
	freopen("walk.out", "w", stdout);
	long long n,m;
	cin>>m>>n;
	for(long long i=1;i<=m;i++){
		cin>>s[i];
	}
	for(long long i=1;i<=m;i++){
		cin>>l[i];
		r[i]=s[i]+l[i];
	}
	dp[0][1]=1;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			long long sum=0;
			for(int q=1;q<=m;q++){
				sum+=(r[j]*r[q]-l[j]*l[q])*dp[i-1][q];
				sum%=MOD;
			}
			dp[i][j]=sum;
		}
	}
	long long cnt=0;
	for(long long i=1;i<=m;i++){
		cnt+=dp[n][i];
		cnt%=MOD;
	}
	cout<<cnt;
	return 0;
}

DAY3

小田的01变换

思路

本题是分类讨论，情况如下：

如果n==2&&a[1]!=a[2]则无解
如果全是1或0那么就不用步数了
如果是1的数量大于0的数量，或0的数量大于1的数量，那么只用一步
如果数量相等，那么就只用两步。

注意的点

顺序不要弄反

题型

分类讨论

代码

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

小田滑雪

思路

本题有些复杂，请耐心观看。

我们用一个vector<int>来存距离，另一个存时间
将两个数组排好序。
为了方便，将两个数组末尾插入一个永远无法更新的点。
新建两个int,标记两个数组的进度，再新建三个double来存上一个的距离，上一个的时间，以及速度
用double来计算所花时间、距离
更新距离，时间，速度。
输出结果

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> t,d;
int main(){
	freopen("snow.in", "r", stdin);
	freopen("snow.out", "w", stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		char u;
		int x;
		cin>>u>>x;
		if(u=='T'){
			t.push_back(x);
		}else{
			d.push_back(x);
		}
	}
	sort(t.begin(),t.end());
	sort(d.begin(),d.end());
	t.push_back(2e9);
	d.push_back(2e9);
	double tim=0,di=0,v=1;
	int i=0,j=0;
	while(i<t.size()-1||j<d.size()-1){
		double vi=1/v;
		v++;
		double tmp=di+(t[i]-tim)*vi;
		if(tmp<d[j]){
			di=tmp;
			tim=t[i];
			i++;
		}else{
			tim=tim+(d[j]-di)/vi;
			di=d[j];
			j++;
		}
	}
	tim+=(1000-di)*v;
	cout<<(long long)(tim+0.5);
	return 0;
}

小田赶牛

思路

本题是一道排序题，要是判断谁先，就得编写cmp，由于先后顺序取决于损失花朵的数量，那我们就这样排a.T*b.D<a.D*b.T

代码

#include<bits/stdc++.h>
using namespace std;
struct P{
	int T,D;
};
P a[100010];
long long s[100010];
bool cmp(P a1,P b1){
	return a1.T*b1.D<b1.T*a1.D;
}
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].T>>a[i].D;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=n;i>0;i--){
		s[i]=s[i+1]+a[i].D;
	}
	long long sum=0;
	for(int i=1;i<=n-1;i++){
		sum+=a[i].T*s[i+1]*2;
	}
	cout<<sum;
	return 0;
}

拼接最大数

思路

其实就是表达式求值：

cmp用来求那个数组从idx开始字典序最大。
而axm就是模拟单调栈，d来表示最多删除几个，
megt来求两个数组合并起来最大值。

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> a,b;
int cmp(vector<int> as,int idxa,vector<int> bs,int idxb) 
{  
	int f;  
	while(idxa<as.size()&&idxb<bs.size())  
	{  
		f=as[idxa++]-bs[idxb++];  
		if (f!=0) return f;  
	}  
	return (as.size()-idxa)-(bs.size()-idxb);  
}  
vector<int> axm(vector<int> as,int k){
	vector<int> res;
	int n=as.size();
	if(n<=k){
		return as;
	}
	int d=n-k;
	for(int i=0;i<n;i++){
		while(!res.empty()&&as[i]>res.back()&&d>0){
			res.pop_back();
			d--;
		}
		if(res.size()<k){
			res.push_back(as[i]);
		}
		else{
			d--;
		}
	}
	return res;
}
vector<int> megt(vector<int> as,vector<int> bs){
	int lena=as.size();
	int lenb=bs.size();
	if(lena==0){
		return bs;
	}if(lenb==0){
		return as;
	}
	vector<int> res;
	int i=0,j=0,k=0;
	while(k<lena+lenb){
		if(cmp(as,i,bs,j)>0){
			res.push_back(as[i++]);
		}else{
			res.push_back(bs[j++]);
		}
		k++;
	}
	return res;
}
int main(){
	freopen("big.in", "r", stdin);
	freopen("big.out", "w", stdout);
	int n,m,k;
	cin>>n>>m>>k;
	vector<int> ans(k,0);
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		a.push_back(x);
	}
	for(int i=0;i<m;i++){
		int y;
		cin>>y;
		b.push_back(y);
	}
	for(int i=0;i<=k;i++){
		vector<int> stka,stkb;
		vector<int> res;
		stka=axm(a,i);
		stkb=axm(b,k-i);
		res=megt(stka,stkb);
		if (res.size()==k&&cmp(res,0,ans,0)>0){
			ans=res;
		}  
	}
	for(int i=0;i<k;i++){
		cout<<ans[i];
	}
	return 0;
}

小王运水

思路

从终点开始，Dijkstra求最短路，在求得过程中算出来。

代码

#include<bits/stdc++.h>
using namespace std;
int arr[2010][2010],x,y,n,m;
double dist[4010];
bool st[2010];
void f(){
	for(int i=1;i<=n;i++){
		dist[i]=0x3f3f3f3f;
	}
	dist[y]=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(arr[t][j]<=100&&dist[t]/(1-(double)(arr[t][j]*0.01))<dist[j]){
				dist[j]=dist[t]/(1-arr[t][j]*0.01);
			}
		}
	}
}
int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	memset(arr,0x3f,sizeof arr);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		arr[x][y]=min(arr[x][y],z);
		arr[y][x]=min(arr[y][x],z);
	}
	cin>>x>>y;
	f();
	printf("%.8lf",dist[x]);
	return 0;
}

WOW

思路

DP做是最简单的：

新建三个int：(f0)一个表示'vv'的个数，(f1)一个表示'vvo'的个数，(f2)一个表示'vv'的个数。
当新出现一个'vv'时，f0定是要+1的，f2就要+f1,因为每个'vvo'都可以和新出现的'vv'组合。
当新出现一个'o'时，之前所有'vv'都可以和它组合，所以f1+f0.

代码

#include<bits/stdc++.h>
using namespace std;
long long ans=0,f0=0,f1=0,f2=0;
int main(){
	freopen("wow.in","r",stdin);
	freopen("wow.out","w",stdout);
	string a;
	cin>>a;
	for(int i=0;i<a.size();i++){
		if(a[i]=='o'){
			f1+=f0;
		}
		if(a[i]=='v'&&a[i+1]=='v'){
			f0++;
			f2+=f1;
		}
	}
	cout<<f2;
	return 0;
}

DAY4

总结

难度：

简单（暴力做出来），基础（优化做出来），中等（算法做出来），困难（没做出来，有算法），CPU炸裂（用DP等四个以上高阶算法且特难）

小田的四则运算(基础）

思路

本题因为只有三个数，所以只是判断三种格式：（A+B)xC,A+B+C,AxBxC。但只要仔细想就知道，只有1是不能用乘的，因为Ax1=A 所以是（1加上剩下的最小值)乘以最大值。如果全是1，干脆全加上！

题目传送门，启动！

题解

注意！abc在题目中是排好序的，所以不用那么多min,max函数！

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	int a,b,c;
	cin>>a>>b>>c;
	int n=min(a,min(b,c));
	if(a==1&&b==1&&c==1){
		cout<<1*3;
		return 0;
	}
	if(n==1){
		if(a==1){
			cout<<(1+min(b,c))*max(b,c);
			return 0;
		}else if(b==1){
			cout<<(1+min(a,c))*max(a,c);
			return 0;
		}else{
			cout<<(1+min(a,b))*max(a,b);
			return 0;
		}
	}else{
		cout<<a*b*c;
		return 0;
	}
	return 0;
}

B.小田的gcd构造（基础上等）

思路（普通，60分左右）

从这里经过简单的推理，能明显地知道a和b是z的倍数，也会知道那个绝对值不用管，无非只是交换了下顺序。所以可以求出来。

思路（最终，AC）

但是可能会超出范围，所以要进一步优化。范围是5x10的18次方。而a,b,z的范围只是10的18次方，加上之前的经验，只需要求出在5x10的18次方中最接近且不超过它的z的倍数就可以了，另一个就是z。

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	long long a,b,c;
	cin>>a>>b>>c;
	cout<<c<<" "<<(long long)5e18/c*c;
	return 0;
}

题目传送门，启动

反思

当时虽然推了许多公式，但都没往极限值上面靠。应该是之前没做过这类在极限边缘的题，之前虽然去考虑了上限，但是在远离。所以不太能做出来

C.小田的山峰数组（困难）

思路

本题要用前缀和与双指针做。

首先，我们要推导出来双指针的变化规律。总不能直接套两个for循环吧！

先判断一个特殊情况：当（s为前缀和数组） $s[i]>=s[n]-s[i]$ 的时候，就没有山峰数组了。因为 $i$ 是第1段的底坐标， $j$ 是第3段的顶坐标。如果第1段大于或等于后两段之和，那么怎么选中间的第2段啊！
找到 $i$ 为这个值时 $j$ 符合规则最小是多少。
剩下的都可以贡献一个数组。

由于我们是枚举i，所以也可以用 $for$ 循环

题目传送门，启动

代码

#include<bits/stdc++.h>
using namespace std;
int a[200010];
long long s[200010],res=0;
int main(){
	freopen("mountain.in", "r", stdin);
	freopen("mountain.out", "w", stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	int i=1,j=3;
	while(i<n-1&&j<=n){
		if(s[i]>=s[n]-s[i]) break;
		while(s[j-1]-s[i]<=s[n]-s[j-1]||s[j-1]-s[i]<=s[i]){
			j++;
		}
		res+=n-j+1;
		i++;
	}
	cout<<res;
	return 0;
}

反思

本题主要就是对双指针掌握不熟，忘记该怎么优化双重循环，应该尽量从“不走回头路上面想”对于怎么判断双指针一般从“三证”入手：是否要求区间特殊值，是否可以用双重循环走，是否可以用二分写。😊

D. Dota2参议院

思路

我们可以用两个队列 $r$ 和 $d$ 来表示Radiant（天辉）和 Dire（夜魇）

我们将队列里可不是放充数的一，是放 $i$ ，

为什么？因为我们要确定该谁发言了。
为什么不用字符串？如果用了那么“丢失”的队员会对字符串产生影响
在每一轮，我们都要将那个值+ $s.size()$ 为了防止不是这一层的牵扯进来。

~~不要问我怎么知道的，因为我试过~~

题目传送门，启动！

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		string s;
		queue<int> a,b;
		cin>>s;
		for(int i=0;i<s.size();i++){
			if(s[i]=='D'){
				a.push(i);
			}else{
				b.push(i);
			}
		}
		for(int i=0;a.size()&&b.size();i+=2){
			
		
			if(a.front()<b.front()){
				int now=a.front();
				a.push(now+s.size());
				
			}else{
				int now=b.front();
				b.push(now+s.size());
				
			}
			a.pop(),b.pop();
		}
		if(a.empty()){
			cout<<"Radiant"<<endl;
		}else{
			cout<<"Dire"<<endl;
		}
	}
	return 0;
}

反思

我当时看这个题目觉得怪吓人的，所以没做。第二次做的时候，将队列里面的 $i$ 写成了 $1$ ，用字符串判断先后，却疏忽了删除一个字符后字符串会有变化。以后当先思考这样做有无后效性，就是会不会对顺序等造成影响。

E. 小W走迷宫

思路

就是广搜求最短路，这个模板我已经背好了，不用做解释（模板）

代码

#include<bits/stdc++.h>
using namespace std;
struct P{
	int x,y,steep;
};
int st[30][30],n,m,e,d,ed,dn,dx[5]={1,0,-1,0},dy[5]={0,1,0,-1};
char a[30][30];
queue<P> q;
void f(){
	q.push(P{e,d,0});
	st[e][d]=1;
	while(!q.empty()){
		P now=q.front();
		q.pop();
		if(now.x==ed&&now.y==dn){
			cout<<now.steep;
			return ;
		}
		for(int i=0;i<4;i++){
			int x=now.x+dx[i],y=now.y+dy[i];
			//cout<<x<<" "<<y<<" "<<i<<" "<<er[i][1]<<" "<<er[i][0]<<endl;
			if(x>n||y>n||x<1||y<1){
				continue;
			}
			if(st[x][y]==1||a[x][y]=='#'){
				continue;
			}
			q.push(P{x,y,now.steep+1});
			st[x][y]=1;
		}
	}
	cout<<-1;
}
int main(){
	freopen("mg.in", "r", stdin);
	freopen("mg.out", "w", stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@'){
				e=i;
				d=j;
			}
			if(a[i][j]=='*'){
				ed=i;
				dn=j;
			}
		}
	}
	f();
	return 0;
}

反思

当时思路以及模板没背熟，所以没做出来。总想着深搜。这模板我已经背熟，下次遇到我一定能做出来！

小W去旅游

思路

本题用floyd写更好，因为没法提前知道去哪里。

代码

#include<bits/stdc++.h>
using namespace std;
int d[30][30],mp[30][30],n,m,a,b,l,x,y;
void dije(){
	memcpy(mp,d,sizeof mp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int q=1;q<=n;q++){
				mp[j][q]=min(mp[j][q],mp[j][i]+mp[i][q]);
			}
		}
	}
}
int main(){
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	memset(d,0x3f,sizeof d);
	cin>>n>>m;
	while(m--){
		cin>>a>>b>>l;
		d[a][b]=l;
		d[b][a]=l;
	}
	dije();
	cin>>x>>y;
	if(mp[x][y]>=0x3f3f3f3f-5e6){
		cout<<"No path";
	}else{
		cout<<mp[x][y];
	}
	return 0;
}

反思

模板没背好，要熟记，不然还以为是dijkstra，本质要搞明白：floyd求不知道起点与终点，dijkstra求1~n

2024暑期集训（DAY1）

DAY1

A 小田的宝石镇

B 小田的好数组

C 小田的数字合并

D. 化学式的原子数

代码

E小W挖宝藏

代码

F 小z的等待时间

DAY2

小田的消消乐游戏

思路

题型

注意的点

代码

小田的气球爆炸啦

思路

题型

注意的点

代码

小k的加减游戏

思路

注意的点

题型

代码

蓬莱山仙峰台

思路

题型

注意的点

代码

数学题1

代码

小z的徒步旅行

思路

代码

DAY3

小田的01变换

思路

注意的点

题型

代码

小田滑雪

思路

代码

小田赶牛

思路

代码

拼接最大数

思路

代码

小王运水

思路

代码

WOW

思路

代码

DAY4

总结

难度：

小田的四则运算(基础）

思路

题目传送门，启动！

题解

B.小田的gcd构造（基础上等）

思路（普通，60分左右）

思路（最终，AC）

题目传送门，启动

反思

C.小田的山峰数组（困难）

思路

题目传送门，启动

代码

反思

D. Dota2参议院

思路

题目传送门，启动！

代码

反思

E. 小W走迷宫