• Codeforces Round #811 (Div. 3)补题（A-G）

    A. Everyone Loves to Sleep

    题目链接：Problem - A - Codeforces

    题意：有n个闹钟在不同时间想起，如果在某个时间睡觉，在下一个闹钟响起前睡几小时几分。

    思路：将所有闹钟时间转化成分钟，与当前时间计算，注意考虑当前时间可以和第二天的闹钟有联系，因此有可能会被第二天最早的闹钟吵醒。 

    代码实现：

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int maxn=1e5+10;
    5. int a[maxn];
    6. int main()
    7. {	
    8. 	ios::sync_with_stdio(false);
    9. 	cin.tie(0);
    10. 	int t;
    11. 	cin>>t;
    12. 	while(t--)
    13. 	{
    14. 		int n;
    15. 		cin>>n;
    16. 		int h,m;
    17. 		cin>>h>>m;
    18. 		int st=h*60+m;//当前睡觉时间 
    19. 		for(int i=1;i<=n;i++)
    20. 		{
    21. 			cin>>h>>m;
    22. 			a[i]=h*60+m;
    23. 		}
    24. 		sort(a+1,a+1+n);//排序 
    25. 		int ans=-1;
    26. 		for(int i=1;i<=n;i++)
    27. 		if(a[i]>=st)
    28. 		{
    29. 		ans=a[i]-st;
    30. 		break;	
    31. 		}
    32. 		if(ans==-1)//如果今天不再有闹钟吵醒 
    33. 		ans=24*60-st+a[1];
    34. 		cout<60<<' '<60<<'\n';
    35. 	}
    36. 	return 0;
    37. }

    B. Remove Prefix

    题目链接：Problem - B - Codeforces

    题意：有一个数组，可以进行操作：将首个元素删除。问至少进行多少次操作，才能让数组元素互不相同.

    思路：记录数字的种类数量，当数组的长度等于种类数时，条件即成立，每增加一个数字时，如果原本这种数字的数量为0，那么种类数就会加1，减少一个数字时，如果减少这个数字后数字的数量为0，那么种类数就会减1。遍历一遍即可。

    代码实现： 

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int maxn=2e5+10;
    5. int a[maxn];
    6. int cnt[maxn];
    7. int main()
    8. {	
    9. 	ios::sync_with_stdio(false);
    10. 	cin.tie(0);
    11. 	int t;
    12. 	cin>>t;
    13. 	while(t--)
    14. 	{
    15. 		int sum=0;//记录种类数 
    16. 		int n;
    17. 		cin>>n;
    18. 		for(int i=1;i<=n;i++)
    19. 		cnt[i]=0;
    20. 		for(int i=1;i<=n;i++)
    21. 		{
    22. 			cin>>a[i];
    23. 			if(cnt[a[i]]++==0)
    24. 			sum++;
    25. 		}
    26. 		int i=1;
    27. 		if(sum==n)//如果当前种类数等于n 
    28. 		{
    29. 			cout<<0<<'\n';
    30. 			continue;
    31. 		}
    32. 		int ret=n;//剩余数字 
    33. 		for(i=1;i<=n;i++)
    34. 		{	
    35. 			if(--cnt[a[i]]==0)
    36. 			sum--;
    37. 			ret--;	
    38. 			if(ret==sum)
    39. 			break;
    40. 		}
    41. 		cout<'\n';
    42. 	}
    43. 	return 0;
    44. }

    C. Minimum Varied Number

    题目链接：Problem - C - Codeforces

    题意：给一个数，将其分解成若干个互不相同的0-9的数字，再将这些数字拼接成最小的数字。

    思路：优先选取更大的数字，因为这样可以使拼接后的数字位数，且高位数字也会因为低位数字选取大了而变小。

    代码实现： 

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int maxn=2e5+10;
    5. int a[maxn];
    6. int cnt[maxn];
    7. int main()
    8. {	
    9. 	ios::sync_with_stdio(false);
    10. 	cin.tie(0);
    11. 	int t;
    12. 	cin>>t;
    13. 	while(t--)
    14. 	{
    15. 		int s=0;
    16. 		int n;
    17. 		cin>>n;
    18. 		for(int i=9;i>=1&&n;i--)//0不需要考虑 
    19. 		{
    20. 			if(n>=i)
    21. 			{
    22. 				a[++s]=i;
    23. 				n-=i;
    24. 			}
    25. 		}
    26. 		for(int i=s;i>=1;i--)
    27. 		cout<
    28. 		cout<<'\n';
    29. 	}
    30. 	return 0;
    31. }

    D. Color with Occurrences

    题目链接：Problem - D - Codeforces

     题意：给一个字符串t和n个字符串s1...sn，每次可以进行染色操作，选取一个si，寻找t的与之相同的子串将其染成红色，问最少要多少次染完，并且依次输出每次用了哪个字符串和从哪开始染。

    思路：设某字符串si可以给t染色，从l到r，那么假设l前面全都染完了。那么染完r的最少次数就是染完l-1到r-1其中一个最小操作数加1，利用动态规划，设dp[r]为染到r所花费的最小次数，那么根据上面所说转移方程就是dp[r]=min(dp[r],d[i]+1)  (l-1<=i<=r-1)，当一个dp值有所更新是，用nx数组保存该状态是从哪个状态转移过来的，（比如刚刚转移方程，nx[r]=i），还需要记录当前字符串si的编号以及其实位置l，最后，从t的末尾往前遍历输出即可。

    代码实现：

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int maxn=2e4+10;
    5. const int inf=0x3f3f3f3f;
    6. int dp[maxn];
    7. int ansl[maxn];
    8. int ansid[maxn];
    9. int nx[maxn];
    10. char t[maxn],s[11][maxn];
    11. int main()
    12. {	
    13. 	int w;
    14. 	cin>>w;
    15. 	while(w--)
    16. 	{
    17. 		int n;
    18. 		scanf("%s",t+1);
    19. 		cin>>n;
    20. 		for(int i=1;i<=n;i++)
    21. 		scanf("%s",s[i]+1);
    22. 		int m=strlen(t+1);//记录字符串的长度 
    23. 		for(int i=1;i<=m;i++)//初始化 
    24. 		dp[i]=inf;
    25. 		for(int i=1;i<=m;i++)//遍历t的1-m的位置 
    26. 		{
    27. 			for(int j=1;j<=n;j++)//对于每个位置，使用s中的字符串尝试转移 
    28. 			{
    29. 				int len=strlen(s[j]+1);
    30. 				int k=0;//记录t从i-len+1到i的子串和sj是否匹配 
    31. 				while(i-k>=1&&len-k>=1&&t[i-k]==s[j][len-k])
    32. 				k++;
    33. 				if(k!=len)
    34. 				continue;
    35. 				for(int q=i-1;i-len<=q;q--)//从l-1到r-1进行转移，也就是i-len到i-1 
    36. 				{
    37. 					if(dp[i]>dp[q]+1)//如果成功更新 
    38. 					{
    39. 						dp[i]=dp[q]+1;
    40. 						nx[i]=q;//i状态从q状态转移来的 
    41. 						ansid[i]=j;
    42. 						ansl[i]=i-len+1;
    43. 					}
    44. 				}
    45. 			}
    46. 		}
    47. 		if(dp[m]==inf)//如果未更新 
    48. 		cout<<-1<<'\n';
    49. 		else
    50. 		{
    51. 			cout<'\n';
    52. 			for(int i=m;i;i=nx[i])
    53. 			cout<' '<'\n';
    54. 		}
    55. 	}
    56. 	return 0;
    57. }

    E. Add Modulo 10

    题目链接：Problem - E - Codeforces

     题意：给n个数字，对于每个数字可以进行任意次加上它的个位数的操作(x+x%10)，问是否能让n个数字相等。

    思路：当个位数为奇数时，进行操作必定变成偶数，所以只要研究个位数为偶数即可

    0:0

    2:2 4 8 16 22

    4:4 8 16 22 24

    6:6 12 14 18 26

    8 16 22 24 28

    先考虑0的情况，0无法改变数值了，因此当存在0时，要么此时数字全相等，要么就No，然后就是248，可以发现6所处的高位数字的奇偶性和2 8不同（(x/10)%2），也就数说6和这两个数字的高位奇偶性不能相同。更近一步，把每个数字的个位变成2，判断高位奇偶性是否相同即可

    代码实现：

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int maxn=2e5+10;
    5. ll a[maxn];
    6. int pos[20];
    7. int main()
    8. {	
    9. 	ios::sync_with_stdio(false);
    10. 	cin.tie(0);
    11. 	int t;
    12. 	cin>>t;
    13. 	while(t--)
    14. 	{
    15. 		int n;
    16. 		cin>>n;
    17. 		int cnt=0;//记录是否有个位为0的情况 
    18. 		for(int i=0;i<=10;i++)
    19. 		pos[i]=-1;
    20. 		for(int i=1;i<=n;i++)
    21. 		{
    22. 		cin>>a[i];
    23. 		while(a[i]%10!=2&&a[i]%10)//将所有数字个位变成0或2 
    24. 		a[i]+=a[i]%10;
    25. 		if(a[i]%10==0)
    26. 		cnt++;	
    27. 		}
    28. 		bool f=1;
    29. 		if(cnt!=0)//若有0，判断是否都相等 
    30. 		{
    31. 			for(int i=1;i
    32. 			if(a[i]!=a[i+1])
    33. 			{
    34. 				f=0;
    35. 				break;
    36. 			}
    37. 		}
    38. 		else//个位都是2 
    39. 		{
    40. 			for(int i=1;i
    41. 			{
    42. 				if((a[i]/10)%2!=(a[i+1]/10)%2)//判断所有高位奇偶性是否都相同 
    43. 				{
    44. 					f=0;
    45. 					break;
    46. 				}
    47. 			}
    48. 		}
    49. 		if(f)
    50. 		cout<<"Yes\n";
    51. 		else
    52. 		cout<<"No\n";
    53. 	}
    54. 	return 0;
    55. }

    F. Build a Tree and That Is It

    题目链接：Problem - F - Codeforces

     题意：给n个点，以及1到2,2到3,3到1的距离(d12,d23,d31)，问是否能建出一棵树，能建就输出一棵树。

    思路：1 2 3能形成两种情况，第一种三个点在同一条链上，那么就是dxy+dyz=dxz，此时将中间的点作为根节点，向左右两边建链即可。当三个点不在同一条链上，那么就是dxy+dyz>dxz，肯定有一个交界点，将这个交界点作为根节点，伸出三条链，要求这个根节点到三点距离:

    dis1=(d12+d13-d23)/2

    dis2=(d12+d23-d13)/2

    dis3=(d13+d23-d12)/2

    其中dis不能有0.5的形式，因此括号内的值必须为偶数，此外，dis1+dis2+dis3+1为当前建出的树的节点数，不能超过n。

    建完基本的树后，如果总节点数没到n，额外随便建点

    不能存下dxy+dyzdxy+dyz+dxz

    代码实现：

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int maxn=2e5+10;
    5. int d[4];//记录d12 d23 d31 
    6. int dis[4];
    7. int i=4;//i为新建的点，从4开始 
    8. void print(int root,int u)//建立根节点到该点的链 
    9. {
    10. 	int d=dis[u];
    11. 	if(d==1)//如果中间没有新建立的点 
    12. 	cout<' '<'\n';
    13. 	else
    14. 	{
    15. 		d-=2;
    16. 		cout<' '<'\n';
    17. 		i++;
    18. 		for(;d>0;d--)//中间新点形成链 
    19. 		{
    20. 			cout<-1<<' '<'\n';
    21. 			i++;
    22. 		}
    23. 		cout<-1<<' '<'\n';//建立新点和目标点的链 
    24. 	}
    25. }
    26. int main()
    27. {	
    28. 	ios::sync_with_stdio(false);
    29. 	cin.tie(0);
    30. 	int t;
    31. 	cin>>t;
    32. 	while(t--)
    33. 	{
    34. 		i=4;
    35. 		int n;
    36. 		cin>>n;
    37. 		for(int i=1;i<=3;i++)
    38. 		dis[i]=0;
    39. 		for(int i=1;i<=3;i++)
    40. 		cin>>d[i];
    41. 		if(d[1]>=n||d[2]>=n||d[3]>=n)//当某两点距离大于n-1时 
    42. 		{
    43. 			cout<<"NO\n";
    44. 			continue;
    45. 		}
    46. 		int sum=0;
    47. 		for(int i=1;i<=3;i++)//寻找三点距离之间的关系 
    48. 		sum+=d[i];
    49. 		int root=0;
    50. 		int link=0;
    51. 		bool f=0;
    52. 		for(int i=1;i<=3;i++)
    53. 		{
    54. 			if(sum==d[i]*2)//一条链 
    55. 			{
    56. 				link=i;//记录这条链的编号 
    57. 				root=i-1;
    58. 				if(root==0)
    59. 				root=3;
    60. 			}
    61. 			if(sum2)//其中一个距离比另外两个和大 
    62. 			f=1;
    63. 		}
    64. 		if(f)
    65. 		{
    66. 		cout<<"NO\n";
    67. 		continue;	
    68. 		} 
    69. 		if(root!=0)//成了一条链 
    70. 		{
    71. 			int da,db,a,b;//与另外两点的距离的编号和两点的编号 
    72. 			//d12  d23  d31
    73. 			//若d12为链的总长,那么3为根节点,a为2,b为1,da=2,db=3 
    74. 			//若d23为链的总长,那么1为根节点,a为3,b为2,da=3,db=1
    75. 			//若d31为链的总长,那么2为根节点,a为1,b为3,da=1,db=2
    76. 			da=(link+1)%3;
    77. 			db=(link+2)%3;
    78. 			a=(root+2)%3;
    79. 			b=(root+1)%3;
    80. 			if(da==0)
    81. 			da=3;
    82. 			if(db==0)
    83. 			db=3;
    84. 			if(a==0)
    85. 			a=3;
    86. 			if(b==0)
    87. 			b=3;
    88. 			dis[a]=d[da];//加入dis数组，方便在print取出 
    89. 			dis[b]=d[db];
    90. 			cout<<"YES\n";
    91. 			print(root,a);
    92. 			print(root,b);
    93. 		}
    94. 		else
    95. 		{
    96. 			int d1=d[1]+d[3]-d[2];
    97. 			int d2=d[2]+d[1]-d[3];
    98. 			int d3=d[3]+d[2]-d[1];
    99. 			if(d1%2||d2%2||d3%2)//若不为偶数 
    100. 			{
    101. 				cout<<"NO\n";
    102. 				continue;
    103. 			}
    104. 			d1/=2;
    105. 			d2/=2;
    106. 			d3/=2;
    107. 			if(d1+d2+d3+1>n)//所需点大于n 
    108. 			{
    109. 				cout<<"NO\n";
    110. 				continue;
    111. 			}
    112. 			dis[1]=d1;
    113. 			dis[2]=d2;
    114. 			dis[3]=d3;//方便print取出 
    115. 			root=i;//根节点为新建一个4 
    116. 			i++;
    117. 			cout<<"YES\n";
    118. 			print(root,1);
    119. 			print(root,2);
    120. 			print(root,3);
    121. 		}
    122. 		if(i1)//如果还缺，新增一条链 
    123. 		{
    124. 			cout<' '<'\n';
    125. 			i++;	
    126. 			for(;i<=n;i++)
    127. 			{
    128. 			cout<-1<<' '<'\n';
    129. 			}	
    130. 		}
    131. 	}
    132. 	return 0;
    133. }

    G. Path Prefixes

    题目链接：Problem - G - Codeforces

    题意：有一棵以1为根节点的树，一条边有两个边权a和b，定义r为从根节点到节点u的路径最长的前缀，这个前缀由1到u前面若干个边构成，但是其b值的和不能超过1到u整条路径a的和。问2-n每个点的r值。

    思路：进行dfs，记录到达当前点a的和从0到dep深度的b的所有前缀和，pre[dep]=pre[dep-1]+b[to]，因为前缀和是从小到大，并且已知a的和以及1到u选取边的情况的所有b值的和，就可以根据前缀和数组进行二分查找，然后每个点都二分查找记录答案即可

    代码实现

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int maxn=2e5+10;
    5. vector<int>vv[maxn];//存图 
    6. ll a[maxn],b[maxn];
    7. ll pre[maxn];//记录前缀和 
    8. int ans[maxn];//记录答案 
    9. void add(int u,int v)
    10. {
    11. 	vv[u].push_back(v);
    12. }
    13. int search(ll num,int r)//二分查找 
    14. {
    15. 	ll l=0;//保证l肯定能满足条件 
    16. 	while(l
    17. 	{
    18. 		int mid=(l+r+1)>>1;
    19. 		if(pre[mid]<=num)
    20. 		l=mid;
    21. 		else
    22. 		r=mid-1;
    23. 	}
    24. 	return l;
    25. }
    26. void dfs(int u,ll now,ll nowpre,int dep)
    27. {
    28. 	pre[dep]=nowpre;//记录到达当前深度的前缀和 
    29. 	ans[u]=search(now,dep);
    30. 	for(int to:vv[u])
    31. 	dfs(to,now+a[to],nowpre+b[to],dep+1);
    32. }
    33. int main()
    34. {	
    35. 	ios::sync_with_stdio(false);
    36. 	cin.tie(0);
    37. 	int t;
    38. 	cin>>t;
    39. 	while(t--)
    40. 	{
    41. 		int n;
    42. 		cin>>n;
    43. 		for(int i=1;i<=n;i++)
    44. 		vv[i].clear();
    45. 		for(int i=2;i<=n;i++)
    46. 		{
    47. 			int fa;
    48. 			cin>>fa>>a[i]>>b[i];//因为是一棵树，所有点都只会有一条指向它的边，因此可以直接将ab当成点权 
    49. 			add(fa,i);
    50. 		}
    51. 		dfs(1,0,0,0);//1节点深度为0，前缀和为0，a的和为0 
    52. 		for(int i=2;i<=n;i++)
    53. 		if(i==n)
    54. 		cout<'\n';
    55. 		else
    56. 		cout<' ';
    57. 	}
    58. 	return 0;
    59. }

  • 相关阅读:
    【Audio音频开发】音频基础知识及PCM技术详解
    Python 完美诠释"高内聚"概念的 IO 流 API 体系结构
    Windows11环境下安装Vmware Workstation 16的方法
    二叉树的概念、存储及遍历
    其他重要协议(DNS,ICMP,NAT,交换机)
    redis 主从复制
    27.【C/C++ 最全vector数组的用法 （详解）】
    【进程间通信IPC】- 信号量的学习
    C语言学习教程
    留意差距：弥合网络安全基础设施的挑战
  • 原文地址：https://blog.csdn.net/m0_63737271/article/details/126152258