C++B组国赛大题个人题解

思路：按ai从小到大排序，看能把前i-1个数变成第i个数，可以则需要手写(a[i-1]-a[i])*(i-1)张，不够的话就前i个每个再分配m/(i-1)张，

同时每个都有b[i]张限制，那我就维护前i-1个中最小的b[i]即可，如果a[i]-a[i-1]大于最小的b[i]，那也不能把前i-1个数变成第i个数

代码如下

#include
using namespace std;

const int N = 2e5+10;

pairp[N];

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i].first);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i].second);
	}
	sort(p+1,p+1+n);
	
	
	int ans=p[1].first;
	int mi=p[1].second;
//	cout<mi)
	  {
	  	//cout<m) ans+=m/(i-1);
	  	else ans+=mi;
	  	m=0;
	  	break;
	  }
	  if(k*(i-1)>m)
	  {
	  	ans+=m/(i-1);
	  	m=0;
	  	break;
	  }
	  ans=p[i].first;
	  m-=k*(i-1);
	  mi=min(mi-k,p[i].second);
	  if(m==0) break;
	}
	if(m>0)
	{
		if(mi*n>m) ans+=m/n;
	  	else ans+=mi;
	}
	printf("%d",ans);
	return 0;
}

思路：dp[i] [j] [k]表示给前i个数分配j个加法，k个减法

那么我就枚举给第i个数分配多少个加法多少个减法

m即为枚举的个数，r[i]表示第i位的数字

dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-m][k]*10+(r[i]+m)%10);

dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-m]*10+((r[i]-m)%10+10)%10);

代码

#include
using namespace std;

typedef long long ll;

const int N = 25,M=110;
ll dp[N][M][M];
ll r[N];

int main()
{
 	string x;
 	int a,b;
 	cin>>x>>a>>b;
 	int n=x.size();
	
	for(int i=0;i 
E.出差 
思路：很明显，建边连图，边权为去的时间+隔离时间，到n边权的不用加隔离时间
 
代码：
 
#include
using namespace std;

const int N = 1010;

int dist[N];
bool st[N];
int g[N][N];
int n,m;
int c[N];

void dijkstra()
{
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		{
			if(!st[j]&&(t==-1||dist[j] 
F.费用报销 
思路：背包，将M作为容量，dp[i][j]表示前i个发票容量为j能拿到的最大钱数，先把发票按日期排序，然后枚举计算每个发票理它最近的有效的发票k，那么1-k都是可以和当前发票一起提交的。
 
那么当前不选第i个发票dp[i][j]=dp[i-1][j],
 
选当前发票的话 dp[i][j]=max(dp[1][j-w]+w,dp[2][j-w]+w,…dp[k][j-w]+w),那么如果我们枚举1-k的话，就复杂度太高了，我们其实只需要知道dp[1][j-w]-dp[k][j-w]的最大值就好了，那么我们再用个数组维护一下就行了
 
#include
using namespace std;

const int N = 1010,M= 5010;

int dp[N][M];
int m[15];

int n,mo,k;

struct node{
	int m,d;
	int val;
}p[N];

int mx[N][M];

unordered_mapmp;

bool cmp(node a,node b)
{
	if(a.m==b.m) return a.dk) return true;
		return false;
	}
	int dd=m[m2]-d2+1+d1;;
	for(int i=m2+1;ik) return true;
	return false;
}
int main()
{
	m[1]=m[3]=m[5]=m[7]=m[8]=m[10]=m[12]=31;
	m[2]=28;
	m[4]=m[6]=m[9]=m[11]=30;
	
	scanf("%d%d%d",&n,&mo,&k);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&p[i].m,&p[i].d,&p[i].val);
	
	sort(p+1,p+1+n,cmp);
	
	for(int i=1;i<=n;i++)
	{
		for(int j=i-1;j>=1;j--)
		{
			if(check(p[i].m,p[i].d,p[j].m,p[j].d))
			{
				mp[i]=j;
				break;
			}			
		}
		//cout<=p[i].val)
			{
				if(!mp.count(i))
			{
				dp[i][j]=max(dp[i][j],p[i].val);
			}
			else
			{
				int k=mp[i];
				dp[i][j]=max(dp[i][j],mx[k][j-p[i].val]+p[i].val);
			}
			}
			mx[i][j]=max(mx[i-1][j],dp[i][j]);
		}
	}
	int ans =0;
	for(int i=mo;i>=1;i--)
	{
		ans=max(dp[n][i],ans);
	}
	printf("%d",ans);
	return 0;
}
 
G.故障 
大写的G，概率论没学好，没看懂题意，会的聚聚教教
 
H. 机房 
菜狗忘记lca的板子了，反复写没写出来，就暴力了，暴力的话很简单，这是个树，直接dfs即可
 
#include

using namespace std;

const int N = 1e5+10;

vectortr[N];
int w[N];
bool st[N];

int bfs(int s,int t,int fa)
{
	if(s==t) return w[t];
	int res=0;
	for(int i=0;i>u>>v;
	printf("%d",bfs(u,v,-1));
	return 0;
}
 
I.齿轮 
思路：看完题意一脸懵逼，怎么提速和减速的啊，看完样例发现只有有个数，之间倍数关系为q就行
 
先把所有数标记一下，然后对每个数x求个约数i，如果i存在，那么就把倍数x/i标记一下，询问就看这
 
个倍数就没有被标记就好了
 
代码
 
#include

using namespace std;

typedef long long ll;
const ll N = 2e5+10;

int r[N];
int res[N];
int ans[N];

int main() 
{
	int n,q;
	scanf("%d%d",&n,&q);
	
	for(int i=1;i<=n;i++)
	{
	  scanf("%d",&r[i]);
	  res[r[i]]=1;	
	}
	for(ll i=1;i 
J.搬砖 
思路:调dp调了挺久，写这道题还有15分钟就直接暴力，不过赛后也没想清怎么贪心，有聚聚会可以教教我，直接暴力，就枚举n个砖头顺序的阶乘，然后求一下价值，记录一个最大值即可
 
代码
 
#include

using namespace std;

const int N = 1010;

int w[N],v[N];
int res[N];
int ans[N];
int n;
int mx=0;
void dfs(int k)
{
	if(k>n)
	{
		int s=0;
		int mv=0;
		for(int i=1;i<=n;i++)
		{
			int j=ans[i];
			if(s>v[j])
			{
				mx=max(mx,mv);
				return ;
			}
			s+=w[j];
			mv+=v[j];
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		if(res[i]) continue;
		res[i]=1;
		ans[k]=i;
		dfs(k+1);
		res[i]=0;
	}
}

int main()
{
	cin>>n;
	
	for(int i=1;i<=n;i++)
	 cin>>w[i]>>v[i];
	dfs(1);
	cout<