• The 2022 ICPC Asia Regionals Online Contest (II)

    A Yet Another Remainder

    题目链接：PTA | 程序设计类实验辅助教学平台

     样例输入：

    1. 1
    2. 9
    3. 47
    4. 27 20
    5. 14 18 15
    6. 16 13 11 7
    7. 13 12 13 5 4
    8. 12 14 11 2 4 4
    9. 14 12 8 2 4 4 3
    10. 12 9 8 2 4 4 3 5
    11. 9 9 8 2 4 4 3 5 3
    12. 5
    13. 3
    14. 7
    15. 31
    16. 67
    17. 97

    样例输出：

    1. 2
    2. 1
    3. 23
    4. 30
    5. 87

    题意：给定一个n位数，然后给定一个二维数组a[][],a[i][j]代表从第j位（高位开始的第j位）开始每隔i位加上该位数字和所得的一个数位和，i>=j，且给定的二维数组大小不能超过100，对于每次询问给定一个p，输出这个n位数对p取余的结果。

    分析：我一开始一直没搞明白p是一个质数且不等于5是什么意思，后来看了题解发现是用费马小定理来做的，但是我在考试时想到的思路是不需要这个限制的，下面来说一下我在考场上想出来的思路：

    由于p是小于100的，那么对p取余的结果就是0~99之间的一个，那么假设P[i]表示10^i对p取余的结果，然后我们能够知道，一定存在一个最小周期k，满足P[i]%p=P[i+k]%p，而且k<100,因为P[i+1]=P[i]*10%p,也就是说每次得到下一个值的方法都是固定的，所以一定会存在循环，而P[i]代表的就是第i+1位的权重，那么对于每一些%p相同的位我们直接求其系数和然后乘以其对应的权重对p取余的结果即可知道这些位对p取余的结果，而这样的系数和正是题目中所给出的那种形式，所以我们处理出来所有的情况然后相加对p取余即可。

    细节见代码：

    1. #include<cstdio>
    2. #include<iostream>
    3. #include<algorithm>
    4. #include<cstring>
    5. #include<map>
    6. #include<queue>
    7. #include<vector>
    8. #include<cmath>
    9. using namespace std;
    10. const int N=103;
    11. int a[N][N];
    12. int P[N];//P[i]记录10^i对p取余得到的结果 
    13. int main()
    14. {
    15. 	int T;
    16. 	cin>>T;
    17. 	while(T--)
    18. 	{
    19. 		int n;
    20. 		scanf("%d",&n);
    21. 		for(int i=1;i<=min(100,n);i++)
    22. 		for(int j=1;j<=i;j++)
    23. 			scanf("%d",&a[i][j]);
    24. 		int q;
    25. 		scanf("%d",&q);
    26. 		while(q--)
    27. 		{
    28. 			int p;
    29. 			scanf("%d",&p);
    30. 			P[0]=1;
    31. 			int id=1;
    32. 			for(;id<=100;id++)
    33. 			{
    34. 				P[id]=(P[id-1]*10)%p;
    35. 				if(P[id]==P[0]) break;
    36. 			}
    37. 			int ans=0;
    38. 			for(int i=1;i<=min(id,n);i++)
    39. 				ans=(ans+1ll*a[min(id,n)][i]*P[(n-i)%id])%p;
    40. 			printf("%d\n",ans);
    41. 		} 
    42. 	}
    43. 	return 0;
    44. }

    B Non-decreasing Array

    样例输入：

    1. 5
    2. 1 2 3 4 5

    样例输出：

    1. 10
    2. 16
    3. 16
    4. 16
    5. 16

    给定一个长度为n的非递减数组，我们可以对其进行k次操作，每次操作可以选择一个数删除，然后再选择一个数将其的值变成任意值，但是要保证每次操作后的数组还是一个非递减数组，而且删除或者修改的数不能是数组的开头或者结尾。让我们求对于所有的操作次数在1~k的情况下\sum_{i=2}^{m}(a[i]-a[i-1])^2的最大值，其中m是最后数组中剩余的元素个数。

    分析：数据范围是100，比较小，通过简单模拟我们能够发现让这些数两两之间相差尽可能地大是我们想要得到的最优解，而且能够发现删除一个数和修改一个数为任意值是等价的，为什么这么说呢？首先我们要操作的数的区间不包括开头和结尾，也就是我们操作的数后面一定还有数，那么我们删除了这个数和把这个数变成其后面的数就没有什么区别了，因为两两之间的差值不变（两个相等的数之间默认为没有差值），所以操作k次的问题就转化为我们删除不超过2*k个数的情况下所能得到的最大值，这个直接用动态规划做就行，枚举倒数第二个数然后直接三重for循环枚举即可。

    细节见代码：

    1. #include<cstdio>
    2. #include<iostream>
    3. #include<algorithm>
    4. #include<cstring>
    5. #include<map>
    6. #include<queue>
    7. #include<vector>
    8. #include<cmath>
    9. using namespace std;
    10. const int N=1e2+10;
    11. long long f[N][N];//f[i][j]表示前i个数删除了j个数且保留了第i个数的最大值 
    12. long long a[N];
    13. int main()
    14. {
    15. 	int n;
    16. 	cin>>n;
    17. 	for(int i=1;i<=n;i++)
    18. 		scanf("%lld",&a[i]);
    19. 	f[2][0]=(a[2]-a[1])*(a[2]-a[1]);
    20. 	for(int i=2;i<=n;i++)//当前遍历到的数 
    21. 	for(int j=1;j<i;j++)//所要保留的倒数第二个数 
    22. 	for(int k=i-j-1;k<n-1;k++)//枚举删的次数 
    23. 		f[i][k]=max(f[i][k],f[j][k-(i-j-1)]+(a[i]-a[j])*(a[i]-a[j]));
    24. 	int cnt=n;
    25. 	for(int i=2;i<=n-2;i+=2)
    26. 		printf("%lld\n",f[n][i]),cnt--;
    27. 	while(cnt--)
    28. 		printf("%lld\n",(a[n]-a[1])*(a[n]-a[1]));
    29. 	return 0;
    30. }

    E An Interesting Sequence

    样例输入： 

    2 5

    样例输出：

    7

    题意：给定一个长度为n的数组的第一个元素值，让我们构造一个数组使得整个数组的元素和最小且每两个相邻的数的最大公约数是1（所有元素值均大于1）.

    分析：直观想象就是通过2，3，2，3，……这样的方法进行构造，这样显然是最优的，我们只需要找到与给定的第一个数互质的最小的数，然后分类讨论第三个数枚举2还是3即可。

    1. #include<cstdio>
    2. #include<iostream>
    3. #include<algorithm>
    4. #include<cstring>
    5. #include<map>
    6. #include<queue>
    7. #include<vector>
    8. #include<cmath>
    9. using namespace std;
    10. int main()
    11. {
    12. 	int n,k;
    13. 	cin>>n>>k;
    14. 	int id=2;
    15. 	while(__gcd(id,k)!=1) id++;
    16. 	int ans=k+id;
    17. 	if(id&1)
    18. 	{
    19. 		for(int i=3;i<=n;i++)
    20. 			if(i&1) ans+=2;
    21. 			else ans+=3;
    22. 	}
    23. 	else
    24. 	{
    25. 		for(int i=3;i<=n;i++)
    26. 			if(i&1) ans+=3;
    27. 			else ans+=2;
    28. 	}
    29. 	printf("%d",ans);
    30. 	return 0;
    31. }

    F Infinity Tree

    样例输入：

    1. 3
    2. 2 6 7
    3. 2 4 5
    4. 3 20 2

    样例输出：

    1. 2
    2. 1
    3. 2

    题意：一开始有一个节点1，然后每秒每个节点产生k个节点，节点编号依次递增，一轮之后会有k+1个节点，然后下一轮次每个节点再产生k个节点，编号小的节点先产生。接下来有若干询问，对于每组询问，给定两个节点u和v，求lca(u,v)

    分析：容易发现每一次扩展后总结点的个数就是k+1的一个幂次，也就是第i次扩展后的节点总个数就是(k+1)^i，那么我们很容易求得第i次扩展得到的节点编号就是(k+1)^(i-1)+1~(k+1)^i，那么我们很容易求得位于该层的节点的父节点是哪个，直接除以k上取整即可，于是我们可以类似于求解lca的那种暴力跳的方法，每次选择一个节点编号大的节点找其父亲节点直至两个节点相同。注意可能会爆long long，建议直接开__int128

    细节见代码：

    1. #include<cstdio>
    2. #include<iostream>
    3. #include<algorithm>
    4. #include<cstring>
    5. #include<map>
    6. #include<queue>
    7. #include<vector>
    8. #include<cmath>
    9. using namespace std;
    10. const int N=103;
    11. __int128 p[N];//存储k+1的幂次 
    12. __int128 k;
    13. long long x,y;
    14. int mx;
    15. __int128 qpow(__int128 a,int b)
    16. {
    17. 	__int128 ans=1;
    18. 	while(b)
    19. 	{
    20. 		if(b&1) ans*=a;
    21. 		b>>=1;
    22. 		a*=a;
    23. 	}
    24. 	return ans;
    25. }
    26. int log(long long x)//返回log(k+1)(x)的上取整 
    27. {
    28. 	int l=0,r=mx;
    29. 	while(l<r)
    30. 	{
    31. 		int mid=l+r>>1;
    32. 		if((long long)p[mid]>=x) r=mid;
    33. 		else l=mid+1;
    34. 	}
    35. 	return l;
    36. }
    37. int main()
    38. {
    39. 	int T;
    40. 	cin>>T;
    41. 	while(T--)
    42. 	{
    43. 		long long t;
    44. 		scanf("%lld%lld%lld",&t,&x,&y);
    45. 		k=t;
    46. 		if(x==1||y==1)
    47. 		{
    48. 			puts("1");
    49. 			continue;
    50. 		} 
    51. 		p[0]=1;
    52. 		for(int i=1;;i++)
    53. 		{
    54. 			p[i]=p[i-1]*(k+1);
    55. 			if(p[i]>1e18)
    56. 			{
    57. 				mx=i;
    58. 				break;
    59. 			}
    60. 		}
    61. 		while(x!=y)
    62. 		{
    63. 			if(x<y) swap(x,y);
    64. 			int c=log(x);//找到x节点的层
    65. 			long long id=qpow(k+1,c-1)+1;//找到x节点所在层的第一个节点的编号
    66. 			x=ceil(1.0*(x-id+1)/k); 
    67. 		}
    68. 		printf("%lld\n",x);
    69. 	}
    70. 	return 0;
    71. }

    G Good Permutation

    样例输入： 

    1. 5 3
    2. 1 5
    3. 1 4
    4. 1 3

    样例输出：

    24

    题意：现在有一个长度为n的1~n的全排列，定义

    定义一个区间是好区间当且仅当这个区间中的最大值减去最小值就是区间长度减1，现在给定若干个限制，每个限制以一个区间[l,r]的形式给出，代表这个区间是好区间，保证所有的限制是不相交的，问满足这样性质的排列个数。

    分析：先来给出好区间的另一个通俗定义，就是这个区间内的数是连续的，这是显然的，假如在区间[l,r]内有n个不相互包含的限制，那么对于这种情况下的方案数就是每个区间长度的全排列数目相乘再把每个区间看成一个点然后和所有的孤立点一起进行一次全排列的方案数乘积，这是显然的，所以我们就转化为求出所有的不包含区间的情况，因为对于每一个区间我们都可以直接算出其内不包含子区间的方案数，然后用树形DP直接求解即可，每个区间的父节点就是第一个包含这个区间的区间，那么现在的问题就转化为如何建树，我们先对所有的区间按照左区间为第一关键字从小到大排序，右区间为第二关键字从大到小排序，然后现在对于每个区间我们都找他左边的且第一个右区间比当前区间右区间大的区间，这个可以用单调栈解决。

    细节见代码：

    1. #include<cstdio>
    2. #include<iostream>
    3. #include<algorithm>
    4. #include<cstring>
    5. #include<map>
    6. #include<queue>
    7. #include<vector>
    8. #include<cmath>
    9. using namespace std;
    10. const int N=1e6+10,mod=1e9+7;
    11. long long fac[N];
    12. long long f[N];//f[i]代表第i个区间的贡献 
    13. int len[N];//len[i]记录第i个区间的长度 
    14. vector<int>p[N];
    15. struct node
    16. {
    17. 	int id,l,r;
    18. };
    19. bool cmp(node a,node b)
    20. {
    21. 	if(a.l!=b.l) return a.l<b.l;
    22. 	return a.r>b.r;
    23. }
    24. vector<node>q;
    25. int n,m;
    26. void dfs(int x)
    27. {
    28. 	long long ans=1;
    29. 	long long l=0;
    30. 	for(int i=0;i<p[x].size();i++)
    31. 	{
    32. 		int j=p[x][i];
    33. 		dfs(j);
    34. 		ans=ans*f[j]%mod;
    35. 		l+=len[j];
    36. 	}
    37. 	f[x]=ans*fac[len[x]-l+p[x].size()]%mod;
    38. }
    39. int st[N],tt;//用单调栈求左边第一个大于当前区间右边界r的区间编号 
    40. int main()
    41. {
    42. 	cin>>n>>m;
    43. 	fac[0]=1;
    44. 	for(int i=1;i<=n;i++)
    45. 		fac[i]=fac[i-1]*i%mod;
    46. 	q.push_back(node{0,1,n});
    47. 	len[0]=n;
    48. 	for(int i=1;i<=m;i++)
    49. 	{
    50. 		int l,r;
    51. 		scanf("%d%d",&l,&r);
    52. 		q.push_back(node{i,l,r});
    53. 		len[i]=r-l+1;
    54. 	}
    55. 	sort(q.begin(),q.end(),cmp);
    56. 	st[++tt]=0; 
    57. 	for(int i=1;i<=m;i++)
    58. 	{
    59. 		while(q[st[tt]].r<q[i].r) tt--;
    60. 		int fa=q[st[tt]].id;
    61. 		st[++tt]=i;
    62. 		p[fa].push_back(q[i].id);
    63. 	}
    64. 	dfs(0);
    65. 	printf("%lld",f[0]);
    66. 	return 0;
    67. }

    J A Game about Increasing Sequences

     样例输入：

    1. 3
    2. 1 3 2

    样例输出：

    Bob

    题意：Alice和Bob进行游戏，给定n个数排成一排，Bob和Alice轮流操作，每次操作可以从最左边或者最右边取一个数，前提是当前取的数要大于上一次另一人取的数，谁最后不能操作谁输，让我们输出获胜者。

    分析：通过简单模拟我们可以发现其实我们原来的数组并不是全部都是有用的，比如第一个数是5，第二个数是3，那么只有第一个数是有用的，为什么这么说呢？因为我们取的数一定是递增分布的而且要按照顺序取，取3之前必须取5，但是取了5就没办法取3，所以我们可以从前往后预处理出来单调递增序列的长度，同理从后往前也需要预处理出来。这两个长度不妨记为len1和len2.

    那么就有如下结论：只有当len1和len2同为偶数时才会有Bob获胜否则一定为Alice获胜。

    我们先来看一下偶数和偶数的情况吧：Alice选择一个数，然后Bob可以在相同的一端选择Alice后面的那个数，如果Alice换了方向，那么Bob也跟着换方向，所以Bob必胜。

    如果要是奇数+偶数的情况，Alice取奇数端的第一个数，如果这个数大于等于偶数端的第一个数，那么顺序就固定了，Alice必胜，否则我们可以发现当Alice取完第一个奇数后变成了偶数+偶数的情况，这个时候Bob取哪个数Alice就跟着即可，所以Alice必胜。

    偶数+奇数的情况同理

    最后一种情况就是奇数+奇数的情况，那么Alice选择两端较大的那个数，那么这个顺序就固定了，Alice直接赢。

    1. #include<cstdio>
    2. #include<iostream>
    3. #include<algorithm>
    4. #include<cstring>
    5. #include<map>
    6. #include<queue>
    7. #include<vector>
    8. #include<cmath>
    9. using namespace std;
    10. const int N=1e5+10;
    11. int a[N];
    12. int main()
    13. {
    14. 	int n;
    15. 	cin>>n;
    16. 	for(int i=1;i<=n;i++)
    17. 		scanf("%d",&a[i]);
    18. 	int lmid=1,rmid=n;
    19. 	while(lmid<n&&a[lmid]<a[lmid+1]) lmid++;
    20. 	while(rmid>1&&a[rmid]<a[rmid-1]) rmid--;
    21. 	if((lmid%2==0)&&(n-rmid+1)%2==0) puts("Bob");
    22. 	else puts("Alice");
    23. 	return 0;
    24. }

  • 相关阅读:
    【BOOST C++ 12 函数式编程】（2） Boost.Function库
    APK构建过程-命令行编译
    2023-10-12 LeetCode每日一题（找出数组的串联值）
    【C++】STL04 适配器-stack
    MongoDB从入门到实战之.NET Core使用MongoDB开发ToDoList系统（8）-Ant Design Blazor前端框架搭建
    7_画图常用代码
    C++/Qt获取屏幕尺寸和放大比例
    [职场] 求职如何设置预期 #笔记#经验分享
    CopyOnWriteArrayList源码分析
    微软：我已把显存优化做到了极致，还有谁？
  • 原文地址：https://blog.csdn.net/AC__dream/article/details/127091112