2022年第十三届蓝桥杯大赛软件类决赛C/C++大学B组（国赛）题解

刷题链接：
https://www.dotcpp.com/oj/train/1038/

看网上更多的是使用的二分，我是自己模拟的，先用大致的模拟思路写，然后再考虑能不能优化
1.对序列进行从小到大排序后，每次抽出一套牌前几个数总会减小，直到减小为0，然后再对前几个牌数为0的牌进行增加，前几个个数为0的牌肯定是同时增加的
2.不进行优化，每次对序列的前几个已经为0的数加一，每次对序列所有数减一，会导致超时
3.优化（贪心）：就是想办法每次不加一减一，每次减尽可能最多（减去最小的即排序后的第一个），每次加尽可能最多（满足三个条件：1.bi>0 2.m足够前几个均分 3.最多加到第一个不为0的个数 ）
AC代码：

#include
#include
#include 
using namespace std;
typedef long long LL;
int n;
LL m;         //注意这个数据范围 
const int N=200005;
typedef pairPII;       //第一维存ai,第二维存下标，便于通过这个下标找对应的bi，就不需要自己写排序函数了 
PII a[N];
int b[N];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) 
	{
		int data;
		scanf("%d",&data);
		a[i].first=data;
		a[i].second=i;
	}
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	sort(a+1,a+n+1);    //pair排序默认是按照first进行升序排列的 
	LL ans=0;
	while(true)         //m最后不一定为0，可能会有剩余，不适合用于循环结束判断 
	{
		int end=0;
		int t=a[1].first;    //每次减少尽可能的多，减去数列中最小的 
		for(int i=1;i<=n;i++)
		{
			a[i].first-=t;
			if(a[i].first==0) end=i;
		}
		ans+=t;
		int minb=b[a[1].second];   //每次加回去尽可能多,前几个为0的同时加，满足三个条件：1.bi>0  2.m足够前几个均分  3.最多加到第一个不为0的数的数据 
		for(int i=1;i<=end;i++)
		{
			if(b[a[i].second]=1;j--)
		{
			if(m>=end*j) break;
		}
		if(j==0) break;    //有边界情况就要考虑特殊判断一下，所有的ai都一样时 
		if(end
			if(b[a[i].second]==0) 
			{
				m=0;
				break;
			}
			a[i].first+=j;
			b[a[i].second]-=j;
			m-=j;
		}
	}
	printf("%lld",ans);
	return 0;
}

1.简单的dp问题，因为序列满足局部最优解，前i个数字构成的数最大其实是前i-1个数字构成的最大数加上最大化的第i个数字，前i个数字构成最大数的状态可以从前i-1个数构成最大数转移过来，但是要保存一下对前i-1个数字进行操作用了多少加和减操作
2.dp[i][j][k] 前i个数字最多进行j次加和最多进行k次减得到的最大数，然后考虑最后一步，第i个数字会进行多少次加和减操作，进行一下枚举

#include
using namespace std;
typedef long long LL;
int n,A,B;
int num[20];
LL dp[20][105][105];
int Now(int i,int s,int x)     //对第i位数字进行s次加和x次减后得到的数字
{
	int tmp=num[i]+s-x;
	if(tmp<0) 
	{
		tmp=-tmp;
		return (10-tmp%10)%10;
	}
	else return tmp%10;
}
LL Add(LL pre,LL now)        //将第i个数字拼到后面
{
	return pre*10+now;
} 
int main()
{
	char h=cin.get();
	int ind=1;
	while(h!=' ')
	{
		num[ind++]=h-'0';
		h=cin.get();
	}
	cin>>A>>B;
	dp[0][0][0]=0;
	dp[1][0][0]=num[1];
	
	int n=ind-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=A;j++)
		{
			for(int k=0;k<=B;k++)
			{
				for(int s=0;s<=j;s++)
				{
					for(int x=0;x<=k;x++)
					{
						dp[i][j][k]=max(Add(dp[i-1][j-s][k-x],Now(i,s,x)),dp[i][j][k]);
					}
				}
			}
		}
	}
	cout< 
题目三：E题 出差 
简单的单源最短路径，隔离天数和路径天数是同等级别的，直接将到达某个目的地的隔离天数加到路径权值上
 int类型的无穷大设置为0x3f3f3f3f (4个)
 longlong类型的无穷大设置为0x3f3f3f3f3f3f3f3f（8个）
 
#include
using namespace std;
const int N=1010;
const int INFI=0x3f3f3f3f;   //这个记住了，一定要设置为最大的，1e8都不行 ，
int n,m;
int graph[N][N];
int geli[N];
int dist[N];
int visited[N];
int Findmin()
{
	int min_i=-1,min=INFI;
	for(int i=1;i<=n;i++)
	{
		if(!visited[i]&&dist[i]
			min=dist[i];
			min_i=i;
		}
	}
	return min_i;
}
void Dijistra(int s)
{
	for(int i=1;i<=n;i++)
	{
		dist[i]=graph[s][i];
	}
	visited[s]=1;
	
	while(true)
	{
		int min_i=Findmin();
		if(min_i==-1) break;
		
		visited[min_i]=1;
		for(int i=1;i<=n;i++)
		{
			if(!visited[i]&&graph[min_i][i]!=INFI&&dist[min_i]+graph[min_i][i]
				dist[i]=dist[min_i]+graph[min_i][i];
			}
		}
	}	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>geli[i];
	geli[1]=0;
	geli[n]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) 
		{
			if(i==j) graph[i][j]=0;
			else graph[i][j]=INFI;
		}
	}
	for(int i=0;i
		int v1,v2,w;cin>>v1>>v2>>w;
		if(v1==v2)    //要注意考虑自环的情况，这道题多重边的好像没有涉及
		{
			graph[v1][v2]=0;
			graph[v2][v1]=0; 
		}
		else
		{
			graph[v1][v2]=w+geli[v2]; 
			graph[v2][v1]=w+geli[v1]; 
		}
		
	}

	Dijistra(1);
	cout< 
题目四：F题 费用报销 
简单的0/1背包变题
 dp[i]表示前i张票据能凑成的最大费用
 题目说的面值尽可能接近M其实就是面值最大
 判断最后一个票据能不能要不要，如果不能要：dp[i][j]=dp[i-1][j];
 如果能要（必须满足第i张票据的面值小于实际费用），再考虑要了和更大还是不要和更大
 并且前一个票据必须与当前票据时间相差大于等于k天 dp[i][j]=max(dp[i][j],dp[h][j-w[num[i]]]+w[num[i]]);
 错误思想：求与当前票据相差大于等于k天的所有dp[h][j-w[num[i]]]的最大值，再加上w[num[i]]
 只需要从前一个状态转移过来，即dp[j]，j就是前一个状态，j满足与与当前票据时间相差大于等于k天
 dp[i]不是看最后一个选的哪一个，而是前个（与最长递增子序列的问题区别开）
 AC代码：
 
#include
#include
using namespace std;
int n,m,k;
const int N=1005;
int num[N];
int dp[N][5005];
int w[N];
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		int y,d,wi;cin>>y>>d>>wi;
		for(int j=1;j<=y-1;j++)
		num[i]+=month[j];  //将日期转换为距离1月1日的天数 
		num[i]+=d;
		w[num[i]]=max(w[num[i]],wi);   //按照日期存储当天的面值，如果有当天的重复票据，选最大的那个 
	}
	sort(num+1,num+n+1);   //将日期从小到大排序 
	for(int i=1;i<=n;i++)
	{
		int h=i-1;
		while(h>0&&num[i]-num[h]
			dp[i][j]=dp[i-1][j];    
			if(w[num[i]]<=j)  //第i天的费用没有超过实际费用，可以选择是否要
			{
				dp[i][j]=max(dp[i][j],dp[h][j-w[num[i]]]+w[num[i]]);
			}
		} 
	} 
	cout<