devbox
人工智能uu
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

9.27 p.m.小结_给定一个十进制自然数的范围和进制的范围,十进制自然数范围在1~44700 之间,进制的

作者：人工智能uu | 2024-07-20 02:10:12

赞

踩

给定一个十进制自然数的范围和进制的范围,十进制自然数范围在1~44700 之间,进制的

T1：问题 A: 完全平方回文数

题目描述

    给定一个十进制自然数的范围和进制的范围，十进制自然数范围在1~44700之间,进制的范围在2~36之间。给定范围里的数中,有些数的平方,在某进制下既是完全平方数又是回文数。本题的任务是统计给定范围内有多少个数的平方满足下列条件:仅在某一进制下既是完全平方数又是回文数。
    说明:32=9,因为它在十进制和十一进制中都是回文数,所以9不能算;同样, 262=676也不算。

输入

    一行四个整数,分别表示给定的十进制自然数的范围和进制的范围。

输出

    一行一个正整数,表示给定范围内满足条件的数的个数。

样例输入

1 100 9 11

样例输出

12

提示

【样例说明】

62=36=33 base 11

102= 100= 121 base9

112=121= 121 base 10

122= 144= 121 base 11

202 = 400 = 484 base 9

222= 484 = 484 base 10

242= 576 = 484 base 11

722= 5184 = 3993 base 11

822= 6724= 10201 base 9

842= 7056= 5335 base 11

912= 8281 = 12321 base 9

1002= 10000= 14641 base 9

题解

这是一道无脑的模拟题。只用枚举每一个数，判断这个数在规定的所有进制中是回文数的个数，如果个数为1，表示可以ans+1，否则枚举下一个数。转进制其实很简单，想象一下一个很大的数5546435635664554，把它转化成10进制是怎样做的？

每一步模10再除以10，就是4,5,5,4,6,6,5,3,6,5,3,4,6,4,5,5。然后倒过来就是这个数了。

如果是11进制呢？那么就是模11再除以11.

也就是：4,0,8,5,6,0,4,6,1,1,10,2,7,6,3,1.倒过来就是一个11进制的数了。注意，这里的10表示的是数字，一般在16进制中会用A来表示。

判断是不是回文数，就看第i位数字与第n-i+1位数字是否都是相等。可以先用一个a数组存一下每位数字，然后for循环判断即可。判断回文数的效率也是不可计算的，平均下来大概是一个5左右的常数。

参考代码

  1. #include<cstdio>
  2. using namespace std;
  3. int l,r,lowest,highest,ans=0,a[1000],len;
  4. bool check(int p,int q)
  5. {
  6. 	len=0;
  7. 	while(p)
  8. 	{
  9. 		a[++len]=p%q;
  10. 		p/=q;
  11. 	}
  12. 	for(int i=1;i<=len/2;i++)
  13. 	if(a[i]!=a[len-i+1]) return false;
  14. 	return true;
  15. }
  16. int main()
  17. {
  18. 	scanf("%d%d%d%d",&l,&r,&lowest,&highest);
  19. 	for(int i=l;i<=r;i++)
  20. 	{
  21. 		int num=0;
  22. 		for(int j=lowest;j<=highest;j++)
  23. 		{
  24. 			if(check(i*i,j)) num++;
  25. 			if(num==2) break;
  26. 		}
  27. 		if(num==1) ans++;
  28. 	}
  29. 	printf("%d",ans);
  30. 	return 0;
  31. }

T2:问题 B: 均分纸牌

题目描述

    有n堆纸牌,编号分别为1，2, ... ,n。每堆上有若干张,但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌,然后移动。
    移牌规则为:在编号为1的堆上取的纸牌,只能移到编号为2的堆上;在编号为n的堆上取的纸牌,只能移到编号为n-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。
    现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。
    例如n=4,4 堆纸牌数分别为:①9 ②8 ③17 ④6
    移动3次可达到目的:
    从③取4张牌放到④(9 8 13 10) -> 从③取3张牌放到②(9 11 10 10) -> 从②取1张牌放到①(10 10 10 10)。

输入

n(n堆纸牌,1 <=n<=100)
a1 a2 ... an (n堆纸牌,每堆纸牌初始数,I<=ai <= 10000)

输出

所有堆均达到相等时的最少移动次数。

样例输入

4

9 8 17 6

样例输出

3

题解

这道题是一个贪心。可以这样来想：对于最左边的牌，如果没有能达到平均数，那么必然需要与它右边的牌进行交换（可能获得也可能舍去），因此只用记录正负即可。同样的，这个操作能够使最左边的牌数达到平均数（如果第二堆不够可以先欠着，或者说可以从大的牌堆开刀）。然后第二堆就变成了最左边的一堆了，就接着进行以上操作。如果这个堆的牌数已经达到了平均数，就跳过。如此就可以O(n)的完成本题。搜索的话可能会超时一些点。

参考代码

  1. #include<cstdio>
  2. using namespace std;
  3. int n,a[200],sum=0,ans=0;
  4. int main()
  5. {
  6. 	scanf("%d",&n);
  7. 	for(int i=1;i<=n;i++) 
  8. 	{
  9. 		scanf("%d",&a[i]);
  10. 		sum+=a[i];	
  11. 	}
  12. 	sum/=n;
  13. 	for(int i=1;i<n;i++)
  14. 	{
  15. 		if(a[i]==sum) continue;
  16. 		ans++;
  17. 		a[i+1]+=a[i]-sum;
  18. 	}
  19. 	printf("%d",ans);
  20. 	return 0;
  21. }

T3：问题 C: 打击犯罪

题目描述

某个地区有 n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为 1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为 n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过 n/2。为达到最好的效果，他们将按顺序打击掉编号 1 到 k 的犯罪团伙，请编程求出 k 的最小值。

输入

第一行一个正整数 n。接下来的 n 行每行有若干个正整数，第一个整数表示该行除第一个外还有多少个整数，若第 i 行存在正整数 k，表示 i，k 两个团伙可以直接联系。

输出

一个正整数，为 k 的最小值

样例输入

7

2 2 5

3 1 3 4

2 2 4

2 2 3

3 1 6 7

2 5 7

2 5 6

样例输出

1

提示


【提示】
输出 1（打击掉犯罪团伙）

 

题解

第一眼看到还以为是找割点，结果想了半天才看到要按照顺序打击范围（-无语-），由于数据范围才1000，直接O(n)枚举k，然后对于每一种情况重新dfs计算连通块的大小，知道第一个小于等于n/2就可以输出答案退出了。注意，已经端掉的犯罪集团VIS应该定为0，然后直接从i+1开始dfs每一块即可。

参考代码 

  1. #include<cstdio>
  2. using namespace std;
  3. struct tree
  4. {
  5. 	int nxt,to;
  6. }tr[2001000];
  7. int head[2001000],vis[2000],cnt=0,ans=0;
  8. int n,m;
  9. void build_tree(int u,int v)
  10. {
  11. 	tr[++cnt].nxt=head[u];
  12. 	tr[cnt].to=v;
  13. 	head[u]=cnt;
  14. }
  15. void dfs(int k)
  16. {
  17. 	for(int i=head[k];i;i=tr[i].nxt)
  18. 	{
  19. 		int to=tr[i].to;
  20. 		if(vis[to]) continue;
  21. 		vis[to]=1;
  22. 		ans++;
  23. 		dfs(to);
  24. 	}
  25. }
  26. bool check(int k)
  27. {
  28. 	for(int i=1;i<=k;i++) vis[i]=1;
  29. 	for(int i=k+1;i<=n;i++) vis[i]=0;
  30. 	for(int i=k+1;i<=n;i++)
  31. 	{
  32. 		if(vis[i]) continue;
  33. 		ans=1;vis[i]=1;dfs(i);
  34. 		if(ans>n/2) return false;
  35. 	}
  36. 	return true;
  37. }
  38. int main()
  39. {
  40. 	scanf("%d",&n);
  41. 	for(int i=1;i<=n;i++)
  42. 	{
  43. 		scanf("%d",&m);
  44. 		for(int j=1;j<=m;j++)
  45. 		{
  46. 			int v;scanf("%d",&v);
  47. 			build_tree(i,v);
  48. 			build_tree(v,i);
  49. 		}
  50. 	}
  51. 	int l=1,r=n;
  52. 	for(int i=1;i<=n;i++)
  53. 	{
  54. 		if(check(i))
  55. 		{
  56. 			printf("%d",i);
  57. 			return 0;
  58. 		}
  59. 	}
  60. 	printf("%d",l);
  61. 	return 0;
  62. }

T4：问题 D: 农场派对

题目描述

N(1≤N≤1000) 头牛要去参加一场在编号为 x(1≤x≤N)的牛的农场举行的派对。有 M(1≤M≤100000)条有向道路，每条路长 Ti(1≤Ti≤100)；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这 N 头牛的最短路径（一个来回）中最长的一条的长度。 特别提醒：可能有权值不同的重边。

输入

第 1 行：3 个空格分开的整数 N,M,X；
第 2…M 行：3 个空格分开的整数 Ai,Bi,Ti ，表示有一条从 Ai 到 Bi 的路，长度为 Ti 。

输出

一行一个数，表示最长最短路的长度。

样例输入

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

样例输出

10

题解

由于一头牛从本家通向x，走的是最短距离，再从x回家，走最短距离。因此可以想象都是由x出发，建一个正图，一个反图，代表来回，然后直接以x作为初始节点求一个单源最短路，然后对于每一个非x的点，求一下两个最小值的和，然后取max就可以了。

参考代码

  1. #include<cstring>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. queue<int>q;
  6. int n,m,x;
  7. struct tree
  8. {
  9. 	int nxt,to,dis;
  10. };
  11. tree tr1[100100],tr2[100100];
  12. int head1[100100],cnt1=0,vis1[2000],di1[2000],ans=0;
  13. int head2[100100],cnt2=0,vis2[2000],di2[2000];
  14. void build_tree(int u,int v,int d)
  15. {
  16. 	tr1[++cnt1].nxt=head1[u];
  17. 	tr1[cnt1].to=v;
  18. 	tr1[cnt1].dis=d;
  19. 	head1[u]=cnt1;
  20. 	tr2[++cnt2].nxt=head2[v];
  21. 	tr2[cnt2].to=u;
  22. 	tr2[cnt2].dis=d;
  23. 	head2[v]=cnt2;
  24. }
  25. int main()
  26. {
  27. 	memset(di1,127/3,sizeof(di1));
  28. 	memset(di2,127/3,sizeof(di2));
  29. 	scanf("%d%d%d",&n,&m,&x);
  30. 	while(m--)
  31. 	{
  32. 		int u,v,d;
  33. 		scanf("%d%d%d",&u,&v,&d);
  34. 		build_tree(u,v,d);
  35. 	}
  36. 	q.push(x);vis1[x]=1;di1[x]=0;
  37. 	while(!q.empty())
  38. 	{
  39. 		int pt=q.front();q.pop();
  40. 		vis1[pt]=0;
  41. 		for(int i=head1[pt];i;i=tr1[i].nxt)
  42. 		{
  43. 			int to=tr1[i].to,dis=tr1[i].dis;
  44. 			if(di1[to]>di1[pt]+dis)
  45. 			{
  46. 				di1[to]=di1[pt]+dis;
  47. 				if(!vis1[to])
  48. 				{
  49. 					vis1[to]=1;
  50. 					q.push(to);
  51. 				}
  52. 			}
  53. 		}
  54. 	}
  55. 	q.push(x);vis2[x]=1;di2[x]=0;
  56. 	while(!q.empty())
  57. 	{
  58. 		int pt=q.front();q.pop();
  59. 		vis2[pt]=0;
  60. 		for(int i=head2[pt];i;i=tr2[i].nxt)
  61. 		{
  62. 			int to=tr2[i].to,dis=tr2[i].dis;
  63. 			if(di2[to]>di2[pt]+dis)
  64. 			{
  65. 				di2[to]=di2[pt]+dis;
  66. 				if(!vis2[to])
  67. 				{
  68. 					vis2[to]=1;
  69. 					q.push(to);
  70. 				}
  71. 			}
  72. 		}
  73. 	}
  74. 	for(int i=1;i<=n;i++)
  75. 	{
  76. 		if(i==x) continue;
  77. 		if(di1[i]+di2[i]>ans) ans=di1[i]+di2[i];
  78. 	}
  79. 	printf("%d",ans);
  80. 	return 0;
  81. }

T5：问题 E: 树的统计

题目描述

一树上有 n 个节点，编号分别为 1 到 n，每个节点都有一个权值 w。我们将以下面的形式来要求你对这棵树完成一些操作：
1. CHANGE u t ：把节点 u 权值改为 t；
2. QMAX u v ：询问点 u 到点 v 路径上的节点的最大权值；
3. QSUM u v ：询问点 u 到点 v 路径上的节点的权值和。
注意：从点 u 到点 v 路径上的节点包括 u 和 v 本身。

输入

第一行为一个数 n，表示节点个数；
接下来 n-1 行，每行两个整数 a,b，表示节点 a 与节点 b 之间有一条边相连；
接下来 n 行，每行一个整数，第 i 行的整数 wi 表示节点 i 的权值；
接下来一行，为一个整数 q ，表示操作总数；
接下来 q 行，每行一个操作，以 CHANGE u t 或 QMAX u v 或 QSUM u v的形式给出。

输出

对于每个 QMAX 或 QSUM 的操作，每行输出一个整数表示要求的结果。

样例输入

4

1 2

2 3

4 1

4 2 1 3

12

QMAX 3 4

QMAX 3 3

QMAX 3 2

QMAX 2 3

QSUM 3 4

QSUM 2 1

CHANGE 1 5

QMAX 3 4

CHANGE 3 6

QMAX 3 4

QMAX 2 4

QSUM 3 4

样例输出

4

1

2

2

10

6

5

6

5

16

提示

【数据范围与提示】

对于 100% 的数据，有 1≤n≤3×104 ,0≤q≤2×105 。

中途操作中保证每个节点的权值 w 在 -30000 至 30000 之间。

题解

树链剖分板题有没有？这里就是一个。写一个能单点修改、查询区间最值、查询区间和的线段树，然后写一个树链剖分进行更改即可。如果不知何为“线段树”、何为“树链剖分”，可查查百度。（特别注意：debug了一个小时，结果是top[x]!=top[y]我把while写成了if，导致样例能对，但是只能过20分，特别要小心！！）

参考代码

  1. #include<cstdio>
  2. #define lc (x<<1)
  3. #define rc (x<<1|1)
  4. #define MAXN 100001
  5. #define LL long long
  6. using namespace std;
  7. struct tree1
  8. {
  9. 	int nxt,to;
  10. }tr[MAXN*2];
  11. struct tree2
  12. {
  13. 	int l,r;LL sum,mx;
  14. }ask[MAXN*4];
  15. char s[200];
  16. LL a[MAXN];
  17. int head[MAXN*2],cnt=0,tot=0,n,m;
  18. int son[MAXN],fa[MAXN],dep[MAXN],size[MAXN];
  19. int seg[MAXN],rev[MAXN],top[MAXN];
  20. LL max1(LL p,LL q) { return p>q?p:q; }
  21. int swap1(int & p,int & q) 
  22. { int c=p;p=q;q=c; }
  23. void make_tree(int x,int l,int r)
  24. {
  25. 	ask[x].l=l;ask[x].r=r;
  26. 	if(l==r)
  27. 	{
  28. 		ask[x].mx=ask[x].sum=a[rev[l]];
  29. 		return;
  30. 	}
  31. 	int mid=(l+r)/2;
  32. 	make_tree(lc,l,mid);
  33. 	make_tree(rc,mid+1,r);
  34. 	ask[x].sum=ask[lc].sum+ask[rc].sum;
  35. 	ask[x].mx=max1(ask[lc].mx,ask[rc].mx);
  36. }
  37. void update(int x,int pos,LL k)
  38. {
  39. 	if(ask[x].l==ask[x].r)
  40. 	{
  41. 		ask[x].mx=ask[x].sum=k;
  42. 		return ;
  43. 	}
  44. 	int mid=(ask[x].l+ask[x].r)/2;
  45. 	if(pos<=mid) update(lc,pos,k);
  46. 	else update(rc,pos,k);
  47. 	ask[x].sum=ask[lc].sum+ask[rc].sum;
  48. 	ask[x].mx=max1(ask[lc].mx,ask[rc].mx);
  49. }
  50. LL query_sum(int x,int l,int r)
  51. {
  52. 	if(ask[x].l>r||ask[x].r<l) return 0;
  53. 	if(ask[x].l>=l&&ask[x].r<=r) return ask[x].sum;
  54. 	return query_sum(lc,l,r)+query_sum(rc,l,r);
  55. }
  56. LL query_max(int x,int l,int r)
  57. {
  58. 	if(ask[x].l>r||ask[x].r<l) return 1ll<<63;
  59. 	if(ask[x].l>=l&&ask[x].r<=r) return ask[x].mx;
  60. 	return max1(query_max(lc,l,r),query_max(rc,l,r));
  61. }
  62. void build_tree(int u,int v)
  63. {
  64. 	tr[++cnt].nxt=head[u];
  65. 	tr[cnt].to=v;
  66. 	head[u]=cnt;
  67. }
  68. void dfs1(int k,int f)
  69. {
  70. 	size[k]=1;
  71. 	for(int i=head[k];i;i=tr[i].nxt)
  72. 	{
  73. 		int to=tr[i].to;
  74. 		if(to==f) continue;
  75. 		fa[to]=k;
  76. 		dep[to]=dep[k]+1;
  77. 		dfs1(to,k);
  78. 		size[k]+=size[to];
  79. 		if(size[to]>size[son[k]])
  80. 		son[k]=to;
  81. 	}
  82. }
  83. void dfs2(int k,int f)
  84. {
  85. 	seg[k]=++tot;
  86. 	rev[tot]=k;
  87. 	if(son[k])
  88. 	{
  89. 		top[son[k]]=top[k];
  90. 		dfs2(son[k],k);
  91. 	}
  92. 	for(int i=head[k];i;i=tr[i].nxt)
  93. 	{
  94. 		int to=tr[i].to;
  95. 		if(to==f) continue;
  96. 		if(top[to]==0)
  97. 		{
  98. 			top[to]=to;
  99. 			dfs2(to,k);	
  100. 		} 
  101. 	}
  102. }
  103. LL ask_sum(int x,int y)
  104. {
  105. 	LL ans=0;
  106. 	while(top[x]!=top[y])
  107. 	{
  108. 		if(dep[top[x]]<dep[top[y]])
  109. 		swap1(x,y);
  110. 		ans+=query_sum(1,seg[top[x]],seg[x]);
  111. 		x=fa[top[x]];
  112. 	}
  113. 	if(dep[x]>dep[y]) swap1(x,y);
  114. 	ans+=query_sum(1,seg[x],seg[y]);
  115. 	return ans;
  116. }
  117. LL ask_max(int x,int y)
  118. {
  119. 	LL maxn=1ll<<63;
  120. 	while(top[x]!=top[y])
  121. 	{
  122. 		if(dep[top[x]]<dep[top[y]])
  123. 		swap1(x,y);
  124. 		maxn=max1(maxn,query_max(1,seg[top[x]],seg[x]));
  125. 		x=fa[top[x]];
  126. 	}
  127. 	if(dep[x]>dep[y]) swap1(x,y);
  128. 	maxn=max1(maxn,query_max(1,seg[x],seg[y]));
  129. 	return maxn;
  130. }
  131. int main()
  132. {
  133. 	scanf("%d",&n);
  134. 	for(int i=1;i<n;i++)
  135. 	{
  136. 		int u,v;
  137. 		scanf("%d%d",&u,&v);
  138. 		build_tree(u,v);
  139. 		build_tree(v,u);
  140. 	}
  141. 	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
  142. 	fa[1]=top[1]=dep[1]=1;
  143. 	dfs1(1,0),dfs2(1,0);
  144. 	make_tree(1,1,n);
  145. 	scanf("%d",&m);
  146. 	while(m--)
  147. 	{
  148. 		scanf("%s",s);
  149. 		if(s[1]=='M')
  150. 		{
  151. 			int l,r;
  152. 			scanf("%d%d",&l,&r);
  153. 			printf("%lld\n",ask_max(l,r));
  154. 		}
  155. 		else if(s[1]=='S')
  156. 		{
  157. 			int l,r;
  158. 			scanf("%d%d",&l,&r);
  159. 			printf("%lld\n",ask_sum(l,r));
  160. 		}
  161. 		else if(s[1]=='H')
  162. 		{
  163. 			LL k;int pos;
  164. 			scanf("%d%lld",&pos,&k);
  165. 			update(1,seg[pos],k);
  166. 		}
  167. 	}
  168. 	return 0;
  169. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/854643
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号