• Codeforces Round #816 (Div. 2)补题（A-E）

    A. Crossmarket

    题目链接：Problem - A - Codeforces

     题意：小红和小蓝走网格，小红从左下角走到右上角，小蓝从左上角走到右下角，小红经过的网格会产生传送门，小蓝可以通过传送门一次行动次数在小红走过的路上任意传送，走一格也需要花一次行动次数，求最少行动次数。

    思路：让小红先走完（先向上走，在向右走），此时固定花费n+m-2次行动次数，此时小蓝脚上有传送门，可以传送到同列最底部或者同行最右部，因此肯定传送max(n-1,m-1)的路程最赚（此时花费1行动次数），然后走min(n-1,m-1)次数。

    结论：当n=m=1时，输出0，否则输出m+n-2+min(n-1,m-1)+1

    代码实现：

    1. #include 
    2. #define ll long long
    3. using namespace std;
    4. signed main()
    5. {
    6.        ios::sync_with_stdio(0);
    7.        cin.tie(0);
    8.        cout.tie(0);
    9.        int t;
    10. 	   cin>>t;
    11. 	   while(t--)
    12. 	   {
    13. 	   	int n,m;
    14. 	   	cin>>n>>m;
    15. 	   	if(n==1&&m==1)
    16. 	   	cout<<0<<'\n';
    17. 	   	else
    18. 	   	cout<-2+min(m,n)<<'\n';
    19. 		} 
    20. }

    B. Beautiful Array

    题目链接：Problem - B - Codeforces

    题意：给n,k,b,s，要寻找一个长度为n的数组，每个元素除以k向下取整的和等于b，数组元素的和等于s，如果没有就输出-1。

    思路：给定的b，初步假设有b个k，分配到数组的各位置中，若此时数组和小于s，就对数组中元素增加大小，但每个元素增加的量不能超过k-1，因为超过的话k的数量就大于b了，因此一个数组增加的量最大为(k-1)*n，可以将b*ki的值全部放在一个位置，然后所有位置增加大小，将数组和变为s。

    代码实现：

    1. #include 
    2. #define ll long long
    3. using namespace std;
    4. const int maxn=1e5+10;
    5. ll ans[maxn];
    6. ll vis[maxn];
    7. signed main()
    8. {
    9.         ios::sync_with_stdio(0);
    10.         cin.tie(0);
    11.         cout.tie(0);
    12.         int t;
    13. 	    cin>>t;
    14. 	   	while(t--)
    15. 		{	
    16. 	   	ll n,k,b,s;
    17. 	   	cin>>n>>k>>b>>s;
    18. 	   	for(int i=1;i<=n;i++)
    19. 	   	ans[i]=0;
    20. 	   	ans[n]=b*k;//全放一起 
    21. 	   	ll temp=s-b*k;//此时数组和与s的差距 
    22. 		if(temp<0)
    23. 		{
    24. 			cout<<-1<<'\n';
    25. 			continue;
    26. 		 } 
    27. 	   		for(int i=1;i<=n&&temp;i++)
    28. 	   		{
    29. 	   			if(temp<=k-1)
    30. 	   			{
    31. 	   				ans[i]+=temp;
    32. 	   				temp=0;
    33. 				}
    34. 	   			else
    35. 			   {
    36. 					ans[i]+=k-1;
    37. 					temp-=k-1;	   	
    38. 			   }	
    39. 			}
    40. 		if(temp)//如果差距依旧存在，那么就找不到 
    41. 		cout<<-1<<'\n';
    42. 		else
    43. 		{
    44. 			for(int i=1;i<=n;i++)
    45. 			cout<' ';
    46. 			cout<<'\n';
    47. 		}
    48. 		} 
    49. }

    C. Monoblock

    题目链接：Problem - C - Codeforces

    题意：给一个数组，有一个函数g(l,r)，返回数组[l,r]之间相邻相同元素组成的块的数量，进行m次操作，每次修改一个元素，并且要求输出此时对于所有(l,r)形成的g(l,r)的和。

    思路：l,r的区间的个数总共为n*(n+1)/2，一个区间至少有一块，假设一开始数组元素都相同，那么所有区间g的和就为n*(n+1)/2，在此基础上，当出现两个相邻的元素不相同时，那么某些区间的g的值就会加1，考虑每个相邻的不同元素对产生贡献的区间的数量，假设i和i-1元素不同，那么产生贡献的区间的l可以在[1,i-1]中选择，r可以在[i,n]中选择，因此g的和增加(i-1)*(n-i+1)，由此计算出未修改前的答案。

    进行一次修改，考虑修改前后，该元素和相邻元素的关系，先撤销原来该元素与相邻元素对答案产生的贡献（当原来的元素和其相邻的元素不相同时），在结算修改后与相邻元素对答案的贡献（现在的元素与其相邻的元素不相同时）。

    1. #include 
    2. #define ll long long
    3. using namespace std;
    4. const int maxn=1e5+10;
    5. ll a[maxn];
    6. signed main()
    7. {
    8.         ios::sync_with_stdio(0);
    9.         cin.tie(0);
    10.         cout.tie(0);
    11.         int n,m;
    12.         cin>>n>>m;
    13.         for(int i=1;i<=n;i++)
    14.         cin>>a[i];
    15.         ll ans=0;
    16.         ans+=(ll)(n+1)*n/2;//每个区间的g至少大于1 
    17.         for(int i=2;i<=n;i++)
    18.         if(a[i]!=a[i-1])
    19.         ans+=(ll)(i-1)*(n-i+1);//相邻两个不同元素产生的贡献 
    20.         while(m--)
    21.         {
    22.         	int x,y;
    23.         	cin>>x>>y;
    24.         	if(x>1&&a[x]!=a[x-1])//撤销该元素与前一个元素的贡献 
    25.         	ans-=(ll)(x-1)*(n-x+1);
    26.         	if(x1])//撤销该元素与后一个元素的贡献 
    27.         	ans-=(ll)x*(n-x);
    28.         	a[x]=y;
    29.         	if(x>1&&a[x]!=a[x-1])//结算该元素与前一个元素的贡献 
    30.         	ans+=(ll)(x-1)*(n-x+1);
    31.         	if(x1])//结算该元素与后一个元素的贡献
    32.         	ans+=(ll)x*(n-x);
    33.         	cout<'\n';
    34. 		}
    35. }

    D. 2+ doors

    主要思路来源：Codeforces Round #816 (Div. 2) A - D - 知乎 (zhihu.com)

    （大佬写的太好了）

    题目链接：Problem - D - Codeforces

    题意：n个元素的数组，给q个按位或的等式，要求寻找一个满足条件且字典序最小的数组。

    思路：对于a|b=c，考虑c二进制形式上每一位的数字，如果c在第i位的数字为0，那么a和b对应位置必定都为0，如果c在第i位元素为1，那么a与b之间至少有1个数字对应位置要有1，目前不考虑之后的情况，假设只放1个1，为了追求字典序最小，这个1肯定放在后面一个元素上，但是对于一个式子a|b=c，a和b可能都要放1，这考虑起来就非常的麻烦。

    将a|b=c对应建一条连接a和b权值为c的无向边，记录其关系，存完图后，对于一个c，0对应的a与b的位置必定为0，而1的位置，先两个都放1，进行双重循环，外循环遍历二进制位数，内循环1-n从前往后遍历。假设当前元素为ai，对于当前位数j是否放1，若此时已经为0了，就跳过，如果此时为1，考虑图中和他相邻的点，并且边的权值的第j位是1（对于j位和ai有关系，两者之间至少要有一个1），这些点的第j位的数字都是1的话，那么ai的第j位的1就不需要了，变为0。

    存在a|a=c的情况，此时a=c，不需要再将1改成0。

    代码实现

    1. #include 
    2. #define ll long long
    3. using namespace std;
    4. const int maxn=1e5+10;
    5. struct node{
    6. 	int to,v;
    7. }; 
    8. vectorvv[maxn];
    9. inline void add(int u,int v,int w)
    10. {
    11. 	vv[u].push_back({v,w});
    12. 	vv[v].push_back({u,w});
    13. }
    14. ll ans[maxn];
    15. signed main()
    16. {
    17.         ios::sync_with_stdio(0);
    18.         cin.tie(0);
    19.         cout.tie(0);
    20.         int n,m;
    21.         cin>>n>>m;
    22.         for(int i=1;i<=m;i++)
    23.         {
    24.         	int u,v,w;
    25.         	cin>>u>>v>>w;
    26.         	add(u,v,w);
    27. 		}
    28. 		for(int i=1;i<=n;i++)//初始都是1 
    29. 		ans[i]=(1<<30)-1;	
    30. 		for(int i=1;i<=n;i++)
    31. 		{
    32. 			for(int j=0;jsize();j++)
    33. 			{
    34. 				int v=vv[i][j].v;
    35. 				ans[i]&=v;//a|b=c中，c的0的a和b对应位置也位0，而a和b其他位若不为0，那么就定为1 
    36. 			}
    37. 		}
    38. 		for(int j=30;j>=0;j--)
    39. 		{
    40. 			for(int i=1;i<=n;i++)
    41. 			{
    42. 				if((1<
    43. 				{
    44. 					bool f=1;
    45. 					for(int k=0;ksize();k++)
    46. 					{
    47. 						int to=vv[i][k].to;
    48. 						if(((1<0||to==i)//如果与之相连的点的对应位置为0或者有自己与自己按位或的式子（此时固定了） 
    49. 						{
    50. 							f=0;
    51. 							break;
    52. 						}
    53. 					}
    54. 					if(f)
    55. 					ans[i]-=(1<//将j位的1变为0 
    56. 				}
    57. 			}
    58. 		}
    59. 		for(int i=1;i<=n;i++)
    60. 		cout<' ';
    61. }

    E. Long Way Home

    题目链接：Problem - E - Codeforces

    题意：n个城市，m条路，可以坐k次飞机，花费(u-v)*(u-v)时间，问从1到1-n所有城市的最短时间。

    思路：首先考虑不坐飞机，那么就是简单的最短路问题，计算出每个点的dis后，考虑坐飞机。定义数组dp，用于记录先走一段路（坐飞机或者走路），最后坐飞机（可能不坐）到目的地，概念有点绕，主要是为了转移方程dp[u]=min(dp[u],dis[v]+(u-v)^2)（先到v，最后坐飞机（或者不坐）），然后再将dp的值传给dis，基于当前dis再进行最短路（飞机不一定只有最后坐，跑最短路寻求走路和坐飞机相间的最短时间）,此时遇到一个问题，u和v要暴力遍历的话，一个点要遍历n次，那么时间复杂度就会达到n^2.

    考虑斜率优化，首先推导公式：

    temp1=dis[a]+(u-a)^2      temp2=dis[b]+(u-b)^2

    我们要选择时间少的那个temp去和dp[u]作比较

    假设temp1>temp2,那么

    dis[a]+u^2-2ua+a^2>dis[b]+u^2-2ub+b^2

    2u>((dis[b]+b^2)-(dis[a]+a^2))/(b-a)

    右边式子形如k=(y2-y1)/(x2-x1)

    对于一个点v，那么就将v定义成x，dis[v]+v^2定义成y。

    将n个点都定义出对应的x和y画在坐标系上，横坐标x都是从1-n从小到大，对于两个点a,b：

    当2u>k时（上面推的），b优于a，反之a优于b。但是此时u是(1-n)中的任意一个数，因此目前不能根据2u判断前后的优劣性。

    对于三个点a,b,c形成的两个线段，考虑几种情况：

    当前面的斜率k1>k2时，后期根据u结算时，若2u>k1，b优于a，那么2u>k2，此时c优于b，b点没有任何作用，若2u

    当k1k1，b优于a，不能确定2u>k2，无法确定b和c优劣性，若2u

    因此利用先单调队列，建立斜率逐渐递增的坐标系，此时单调队列的head先不动，因为u不确定。

    坐标系建完之后，遍历1-n所有的点，此时u是从小到大排序的，2u也是从小到大，因此对于一个u，可以直接根据其2u删除单调队列的首个元素(若开头两个点形成的斜率小于2u)。对于此时的u，最适合进行状态转移的点就为删除后的首个元素（斜率优化一般都这样）。

    概要：求最短路->建立斜率递增的单调队列->根据从小到大的u删除队首元素->根据队首元素进行状态转移

    按照以上步骤，进行k次循环

    代码实现：

    1. #include 
    2. #define ll long long
    3. #define int ll
    4. #define double long double
    5. using namespace std;
    6. const int maxn=1e5+10;
    7. const int inf=0x3f3f3f3f3f3f3f3f;
    8. ll dp[maxn],dis[maxn];
    9. bool vis[maxn];
    10. int n,m,k;
    11. struct edge{
    12. 	int to,v;
    13. };
    14. vectorvv[maxn];
    15. inline void add(int u,int v,int w)
    16. {
    17. 	vv[u].push_back({v,w});
    18. 	vv[v].push_back({u,w});
    19. }
    20. struct node{
    21. 	int id,dis;
    22. 	friend bool operator<(const node&a,const node&b)
    23. 	{
    24. 		return a.dis>b.dis;
    25. 	}
    26. };
    27. void dij()//最短路板子 
    28. {
    29. 	for(int i=1;i<=n;i++)
    30. 	vis[i]=0;
    31. 	dis[1]=0;
    32. 	priority_queueq;
    33. 	for(int i=1;i<=n;i++)//唯一要注意的点，要把所有点放进队列，因为初始的dis不一定是inf 
    34. 	q.push({i,dis[i]});
    35. 	while(!q.empty())
    36. 	{
    37. 		node p=q.top();
    38. 		q.pop();
    39. 		int u=p.id;
    40. 		if(vis[u])
    41. 		continue;
    42. 		vis[u]=1;
    43. 		for(int i=0;isize();i++)
    44. 		{
    45. 			int to=vv[u][i].to;
    46. 			int w=vv[u][i].v;
    47. 			if(dis[to]>dis[u]+w)
    48. 			{
    49. 				dis[to]=dis[u]+w;
    50. 				q.push({to,dis[to]});
    51. 			}
    52. 		}
    53. 	}
    54. }
    55. //斜率优化部分 
    56. double x[maxn],y[maxn];//存储x和y 
    57. int que[maxn],head=1,tail=0;//单调队列 
    58. inline double slope(int x1,int x2)//得到斜率 
    59. {
    60. 	return (y[x2]-y[x1])/(x[x2]-x[x1]);
    61. }
    62. void solve()
    63. {
    64. 	head=1;//初始化单调队列 
    65. 	tail=0;
    66. 	for(int i=1;i<=n;i++)
    67. 	{
    68. 		x[i]=i;
    69. 		y[i]=dis[i]+i*i;
    70. 		dp[i]=dis[i];
    71. 	}
    72. 	//head
    73. 	for(int i=1;i<=n;i++)
    74. 	{
    75. 		while(headslope(que[tail-1],que[tail])>slope(que[tail],i))//建立斜率单调递增的坐标系 
    76. 		tail--;
    77. //		也可以这么写（可以画个图，两个互通的）：
    78. //		while(headslope(que[tail-1],i)) 
    79. //		tail--; 
    80. 		que[++tail]=i;
    81. 	}
    82. 	for(int i=1;i<=n;i++)
    83. 	{
    84. 		while(headslope(que[head],que[head+1])<2*i)//根据2i删掉队首元素 
    85. 		head++;
    86. 		int j=que[head];
    87. 		dp[i]=min(dp[i],dis[j]+(j-i)*(j-i));//根据队首元素状态转移 
    88. 	}
    89. 	for(int i=1;i<=n;i++)
    90. 	dis[i]=dp[i];//记录答案 
    91. }
    92. signed main()
    93. {
    94.         ios::sync_with_stdio(0);
    95.         cin.tie(0);
    96.         cout.tie(0);
    97.         cin>>n>>m>>k;
    98.         for(int i=1;i<=m;i++)
    99.         {
    100.         	int u,v,w;
    101.         	cin>>u>>v>>w;
    102.         	add(u,v,w);
    103. 		}
    104. 		for(int i=1;i<=n;i++)
    105. 		dis[i]=dp[i]=inf;
    106. 		dp[1]=0;
    107. 		dis[1]=0;
    108. 		dij();
    109. 		for(int i=1;i<=k;i++)
    110. 		{
    111. 			solve();
    112. 			dij();
    113. 		}
    114. 		for(int i=1;i<=n;i++)
    115. 		cout<' ';
    116. }

  • 相关阅读:
    混合专家模型 (MoE) 详解
    JavaWeb---实验课---第8章 EL-JSTL
    传统 IAM 已成为企业增长桎梏，下一代身份基础设施如何帮助企业破局？
    USB复合设备构建CDC+HID鼠标键盘套装
    CrossOver 23 正式发布：可在 Mac 上运行部分 DX12 游戏
    vscode登录同步打开vscode.dev失败解决方法
    google abseil c++ Tip of the Week #65: Putting Things in their Place 把对象放入容器的方式
    CH06_第一组重构（上）
    【控制】模型预测控制 model predictive control 简介
    R语言数据分析-线性代数基础
  • 原文地址：https://blog.csdn.net/m0_63737271/article/details/126607608