[第八场]题解

it2022-05-06  0

T1

题目描述 我们如何评价科学家的成功?根据发表论文的数量或其引用分数——更准确地说,被引用的次数?这两个要素都很重要。如果一篇论文被其他科学家的论文总共引用了C次,那么这篇论文的引用分数为C。科学家成功的一个可能衡量标准是他们的H指数,它同时考虑了论文数量和引用分数。 科学家的H指数定义为具有以下性质的最大整数H:科学家可以选择H篇论文,满足这H篇论文的引用分数都不小于H。例如,如果一个科学家写了10篇论文,并且每一篇都被引用了至少10次,那么他的H指数(至少)是10。 写一个程序,输入某个科学家所有论文的引用分数,输出他的H指数。 输入 第一行输入包含整数N(1≤N≤5*1e5)。表示论文的数量。 第二行输入包含N个自然数Ci(Ci≤1e6)。表示每篇论文的引用分数。 输出 输出一个整数。表示这名科学家的H指数。 样例 样例输入1 5 1 1 4 8 1 样例输出1 2 样例输入2 5 8 5 3 4 10 样例输出2 4

解题思路

此题比较轻松,和大众做法不同,我并没有排序,我用了一个cnt统计数字出现次数,然后倒着来找符合条件的,即积分为i满足能选i篇积分至少为i的。

代码

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cstdlib> using namespace std; int n,c,cnt[1000005],maxn; int sum; int main(){ //freopen("hindex.in","r",stdin); //freopen("hindex.out","w",stdout); scanf ("%d",&n); for (int i = 1;i <= n;i ++){ scanf ("%d",&c); cnt[c] ++; maxn = max(c,maxn); } for (int i = maxn;i >= 0;i --){ sum += cnt[i]; if (sum >= i){ printf("%d\n",i); return 0; } } }

T2

题目描述 一个房间里有N张桌子,从左到右排成一行。有些桌子上有电话,而有些桌子是空的。所有的电话都坏了,所以当第i个办公桌上的电话响了,第j个办公桌上的电话也会响,如果第j个办公桌和第i个办公桌的距离不超过D。换句话说,j和i满足|j-i|≤D。第一张桌子和最后一张桌子上一定会有电话。开始的时候,最左边的桌子上的电话会响起。求要让最后一个电话响起,至少要在多少张办公桌上放置新电话? 输入 第一行输入包含两个整数N(1≤N≤3e5)和D(1≤D≤N)。分别表示办公桌的数量和题目中提到的距离。 第二行输入包含了N个整数Ai(0≤Ai≤1)。第i个整数Ai表示第i个张桌子的状态。具体来说,如果Ai=1那么第i张桌子上有电话,如果Ai=0那么第i张桌子上没有电话。 输出 输出一个整数。表示需要放置新电话的数量。 样例 样例输入1 4 1 1 0 1 1 样例输出1 1 样例输入2 5 2 1 0 0 0 1 样例输出2 1 样例输入3 8 2 1 1 0 0 1 0 0 1 样例输出3 2

解题思路

感觉就是一道贪心模拟,我们就直接保证放到最远即可,中途有一些电话线的话,我们就重新开始算。

代码

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cstdlib> using namespace std; int n,d,dis,tot; int vis[300005]; int main(){ //freopen("telefoni.in","r",stdin); //freopen("telefoni.out","w",stdout); scanf ("%d%d",&n,&d); for (int i = 1;i <= n;i ++) scanf ("%d",&vis[i]); for (int i = 1;i <= n;i ++){ if (vis[i] == 1) dis = 1; else if (dis == d){ tot ++; dis = 1; } else dis ++; } printf("%d",tot); }

T3

题目描述 年轻的Jozef得到了一个由2的N次方个正整数组成的集合作为礼物。考虑到Jozef经常参加足球锦标赛,他决定为这2的N次方个正整数组织一个锦标赛。 数字锦标赛如下图所示。比赛成对进行,两个数字中较高的一个前进到更高级别。比赛的级别用1到N之间的数字表示,其中最高的级别用数字0表示。 由于Jozef没有时间组织所有的比赛,他想知道,对于集合中的每个数字,在所有的对阵安排中,能达到的最高级别(数字最小的级别)。 输入 第一行输入包含一个整数N(1≤N≤20)。表示题目中提到的N。 第二行输入包含了2的N次方个正整数Ai(Ai≤1e9)。表示集合中2的N次方个正整数。 输出 输出一行包含2的N次方个整数。其中第i个数表示按照输入的顺序集合中的第i个正整数能达到的最高级别。 样例 样例输入1 2 1 4 3 2 样例输出1 2 0 1 1 样例输入2 4 5 3 2 6 4 8 7 1 2 4 3 3 6 4 8 1 样例输出2 1 2 2 1 1 0 1 3 2 1 2 2 1 1 0 3 样例输入3 1 1 1 样例输出3 0 0

解题思路

先说一下题意吧,可能有人觉得样例不对,毕竟当时我一开始也理解错了。 简单来说,他就是让你自己安排,求每一个数最远能到哪。 那我们肯定要排序啊。a的值很大,我们进行离散。 这里有一点是相同的数也可以晋级。所以怎么算其能到达的最远呢。 这里呢,可以找一下规律。 如果i可以到n - 1,那么肯定要有至少2个小于等于i的数。 如果i可以到n - 2,那么肯定要有至少4个小于等于i的数。 如果i可以到n - k,那么肯定要有至少2^k个小于等于i的数。 就这样完了,处理你自己弄一下差不多了。

代码

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cstdlib> using namespace std; struct node{ int x,pos; bool operator < (const node &a)const { return x < a.x; } }s[1500005]; int n,n1,num[1500005],ans[1500005],tot[1500005],sum,cnt; int qkpow(int x,int y){ int ans = 1; while (y){ if (y % 2 == 1) ans = ans * x ; x = x * x; y /= 2; } return ans; } int main(){ //freopen("turnir.in","r",stdin); //freopen("turnir.out","w",stdout); scanf ("%d",&n); n1 = qkpow(2,n); for (int i = 1;i <= n1;i ++){ int a; scanf ("%d",&a); s[i].x = a; s[i].pos = i; } sort(s + 1,s + 1 + n1); for (int i = 1;i <= n1;i ++){ if (s[i].x != s[i - 1].x){ num[s[i].pos] = ++ cnt; tot[cnt] ++; } else { num[s[i].pos] = cnt; tot[cnt] ++; } } for (int i = 1;i <= cnt;i ++){ sum += tot[i]; int j,tot1 = 0; for (j = 1;j <= n1;j *= 2){ if (sum < j) break; tot1 ++; } ans[i] = n - tot1 + 1; } for (int i = 1;i < n1;i ++) printf("%d ",ans[num[i]]); printf("%d\n",ans[num[n1]]); }

T4

题目描述 如果一个数等于它的所有因数(小于自身的)之和,那么这个数就是完美的。例如,28是完美的,因为28=1+2+4+7+14。

基于这个定义,我们数字n的不完美度定为f(n),它等于n与n的所有因数(小于n的)之和的差的绝对值,因此完美数的不完全度为0,其余自然数的不完全度都大于0。 例如:

●f(6)=|6-(1+2+3)|=0 ●f(11)=|11-(1)|=10 ●f(24)=|24-(1+2+3+4+6+8+12)|=|-12|=12

写一个程序,对于正整数A和B,计算A和B之间所有数字的不完美度之和:即f(A)+f(A+1)+…+f(B)。 输入 第一行输入包含两个整数A和B(1≤A≤B≤1e7)。表示题目中的A和B。 输出 输出一个整数。表示f(A)+f(A+1)+…+f(B)。 样例 样例输入1 1 9 样例输出1 21 样例输入2 24 24 样例输出2 12

解题思路

其实这是一道求约数和的模板题,不完美度这玩意你求出约数和你就可以O(1)时间内求解。 约数和应该来说是有两种求法,第一种便是nlog(n)的求法,代码简短。第二种则是欧拉筛法的求法,代码略长一点,时间复杂度为O(n)。 但考试时限3s,好像nlog(n)并不会爆,评测也过了。但OJ上TLE了,所以还是用欧拉筛吧

代码

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cstdlib> using namespace std; int a,b,psum[10000005],cnt,pri[1500005],s[10000005]; bool vis[10000005]; long long ans; int main(){ scanf ("%d%d",&a,&b); /*约数个数 for (int i = 2;i <= b;i ++){ if (!vis[i]){ pri[++ cnt] = i; num[i] = 1; d[i] = 2; } for (int j = 1;j <= cnt && 1ll * i * pri[j] <= b;j ++){ vis[pri[j] * i] = 1; if (i % pri[j] == 0){ num[pri[j] * i] = num[i] + 1; d[pri[j] * i] = d[i] / (num[i] + 1) * (num[i] + 2); break; } d[pri[j] * i] = d[i] * 2; num[i] = 1; } }*/ s[1] = 1; for(int i = 2;i <= b;i ++){ if (!vis[i]){ pri[++ cnt] = i; s[i] = i + 1; psum[i] = i + 1; } for (int j = 1;j <= cnt && 1ll * i * pri[j] <= b;j ++){ vis[pri[j] * i] = 1; if (i % pri[j] == 0){ psum[pri[j] * i] = psum[i] * pri[j] + 1; s[pri[j] * i] = s[i] / psum[i] * psum[pri[j] * i]; break; } s[pri[j] * i] = s[i] * (pri[j] + 1); psum[pri[j] * i] = pri[j] + 1; } } for (int i = a;i <= b;i ++) ans += abs(i * 2 - s[i]); printf("%lld\n",ans); }

T5

题目描述 Daniel有一袋糖果和N张卡片。

每张卡片上都写有一个正整数Pi。丹尼尔在吃糖果的时候,想到了一个有趣的游戏。Daniel可以挑选两张卡片,将它们绑在一起,如果Daniel挑选第a张牌和第b张牌,那么Daniel会马上吃掉min(Pa%Pb,Pb%Pa)个糖果,其中x%y表示x除以y的余数。

Daniel每次会挑选两张卡片将它们绑在一起,最终,当他提起其中一张卡片时,所有其余的卡片也会被提起。他可以多次将同一张卡片和其他卡片绑在一起。Daniel要求你计算他至少要吃多少糖果。 输入 第一行输入包含一个整数N(1≤N≤1e5)。表示卡片的数量。

接下来N行每行包含一个正整数Pi(Pi≤1e7)。第i个整数Pi表示第i张卡片上的正整数。 输出 输出一个整数。表示Daniel至少要吃多少糖果。 样例 样例输入1 4 2 6 3 11 样例输出1 1 样例输入2 4 1 2 3 4 样例输出2 0 样例输入3 3 4 9 15 样例输出3 4

解题思路

一看也知道是一道最小生成树。然而数据太大了,用裸的最小生成树跑不仅会超时还会爆空间,可怕可怕。 正解其实就是最小生成树加优化。 首先,如果存在倍数关系,连边的花费就为0,我们可以缩点,但有一点要注意。不能够强行把这个点删去,我们把它放在一个集合中即可。强行删去会使得答案有误,其它点有可能与另一个点的倍数连边。列如3,11,22. 然后就是删边,我们要保存有意义的边。一些肯定用不上的边一定要删去。 我们定义一个数组q,q[i]则表示大于等于i的最小的数(原数列出现过)。 处理到一个点我们便可以枚举这一个值的倍数,至于那三个数的推导,给个链接但其实还有一个问题,那就是枚举倍数时这样加会有重复的边出现,我们仅仅需要存一个,就需要判断一下,看下一次塞进去的是不是与此相等。还有一点是,先处理判断一下q[p[i] + 1],然后再从2*p[i]开始枚举。

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #define P 10000005 #include<cstdlib> using namespace std; struct node { int u,v,w; node (){}; node (int U,int V,int W){ u = U,v = V,w = W; } bool operator < (const node &a)const { return w < a.w; } }; int n,p[P],cnt,fa[P],q[P],flag[P],maxn,a[P],k,n1; bool vis[P]; vector <node>s; void makeset(int x){ for (int i = 1;i <= x;i ++) fa[i] = i; } int findset(int x){ if (fa[x] != x) fa[x] = findset(fa[x]); return fa[x]; } int main(){ scanf ("%d",&n); for (int i = 1;i <= n;i ++){ scanf ("%d",&p[i]); maxn = max(p[i],maxn); q[p[i]] = p[i]; flag[p[i]] = i; } makeset(maxn); for (int i = maxn;i >= 0;i --) if (!q[i]) q[i] = q[i + 1]; for (int i = 1;i <= n;i ++){ for (int j = p[i] * 2;j <= maxn;j += p[i]){ if (flag[j]){ int t1 = findset(p[i]); int t2 = findset(j); if (t1 != t2){ fa[t2] = t1; k ++; } } } } for (int i = 1;i <= n;i ++){ if (!vis[p[i]]){ vis[p[i]] = 1; int t1 = findset(p[i]); if (p[i] + 1 > maxn || (q[p[i] + 1] != q[p[i] + p[i]] && findset(q[p[i] + 1]) != t1)) s.push_back(node(p[i],q[p[i] + 1],q[p[i] + 1] % p[i])); for (int j = p[i] * 2;j <= maxn;j += p[i]){ if (j + p[i] > maxn || (q[j] != q[j + p[i]] && findset(q[j]) != t1)){ s.push_back(node(p[i],q[j],q[j] % p[i])); } } } else n1 ++; } sort(s.begin(),s.end()); long long mst = 0; for (int i = 0;i < s.size() && k < n - n1 - 1;i ++){ int t1 = findset(s[i].u); int t2 = findset(s[i].v); if (t1 != t2){ if (t1 < t2) fa[t2] = t1; else fa[t1] = t2; mst += s[i].w; k++; } } printf("%lld\n",mst); }

最新回复(0)