A-点赞

观察数据范围，发现任务标签在1~1000范围内，所以可以用桶来存储每个标签的出现次数，最后从1遍历到1000取出出现次数最多的即可。

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n;

scanf("%d",&n);

int b[1001]={0};

for(int i=0;i<n;i++)

{

int m;

scanf("%d",&m);

for(int j=0;j<m;j++)

{

int x;

scanf("%d",&x);

b[x]++;

}

}

int maxx=0;

int maxi;

for(int i=1;i<=1000;i++)

{

if(b[maxx]<=b[i])

{

maxx=i;

maxi=b[i];

}

}

printf("%d %d",maxx,maxi);

return 0;

}

B-月饼

与1750题几乎完全一样，不再赘述。

#include<bits/stdc++.h>

using namespace std;

struct moon //用一个结构体存储月饼的信息

{

double num, price, one;

}cake[1001];//初始化

bool cmp(moon a, moon b) //sort排序要根据月饼单价

{

return a.one > b.one;

}

int main()

{

int N, need;

double ans = 0;//总售价

cin >> N >> need;

for(int i=0; i<N; i++)//先输入每个货量

cin >> cake[i].num;

for(int i=0; i<N; i++)

{

cin >> cake[i].price;//输入每个月饼售价

cake[i].one = cake[i].price/cake[i].num;//顺便把单价计算出来

}

sort(cake, cake+N, cmp);//根据单价把月饼进行排序

for(int i=0; i<N; i++)

{

if(cake[i].num <= need) //需求仍然没有被满足

{

ans += cake[i].price;

}

else //如果需求都被满足了就停止循环

{

ans += cake[i].one*need;

break;

}

need -= cake[i].num;//每一次把仍需要达到的需求量更新

}

printf("%.2f", ans);

return 0;

}

C-完全二叉树

由于是完全二叉树，所以可以根据后序遍历将这棵树构建出来。

具体而言，从后往前遍历这个后序遍历序列，就可以先建立根节点，再建立右子树，最后建立左子树，这个过程可以递归进行。

又因为二叉树可以用数组很方便的存储以及快速找到左右孩子的位置，所以可以一边递归，一边填充存储二叉树的数组。具体见递归函数即可。

最后，将数组从左到右输出，就得到了层序遍历的结果。

#include<bits/stdc++.h>

using namespace std;

int n,hx[31],cx[31],x;

//x表示当前遍历到了后序遍历中的哪个位置

void build(int root)

{

cx[root]=hx[x--];

if(root*2+1<=n) build(root*2+1);

if(root*2<=n) build(root*2);

}

int main()

{

cin>>n;

x=n;

for(int i=1; i<=n; i++) cin>>hx[i];

build(1);

for(int i=1; i<=n; i++) cout<<cx[i]<<' ';

return 0;

}

D-接金币

首先考虑暴力：对于每一个询问，直接模拟，若金币溢出，则枚举找出在当前圆盘下方最近的比当前圆盘大的圆盘，将当前金币量减去当前圆盘的容量，流进下一个圆盘。

所以实际上我们需要快速找到每个圆盘下方最近的比它大的圆盘，这可以使用单调栈解决。又因为金币可能会流多次，所以可以用倍增的思想，找到这个圆盘上的金币流1次、流2次、流4次...流2^n次后能到达的圆盘，并用倍增预处理出流这么多次后会消耗掉的金币数量，然后就可以使用倍增加速查询。

#include<bits/stdc++.h>

#define maxn 100010

#define inf 0x7f7f7f7f

#define ll long long

using namespace std;
 

int n,q;

struct node

{

ll d,c;

} a[maxn];

stack<ll> s;

ll f[maxn][25],u[maxn][25];
 

int main()

{

cin>>n>>q;

for(int i=1; i<=n; i++)

scanf("%lld%lld",&a[i].d,&a[i].c);

//单调栈处理出圆盘上的金币流2^0次后能到哪个圆盘

for(int i=n; i>=1; i--)

{

//出栈，直到栈顶的直径比i大

while(!s.empty()&&a[s.top()].d<=a[i].d) s.pop();

//所以s.top()就是能接住i金币的圆盘

if(!s.empty()) f[i][0]=s.top();

//入栈，始终保证栈中元素单调递增

s.push(i);

}

//倍增得到圆盘上的金币流2^n次后能到哪个圆盘

for(int i=1; i<=23; i++)

for(int j=1; j<=n; j++)

f[j][i]=f[f[j][i-1]][i-1];

//倍增得到圆盘上的金币流2^n次后会消耗掉的金币数量

for(int i=1; i<=n; i++)

if(f[i][0]==0) u[i][0]=inf; //初始化u数组

for(int i=1; i<=n; i++)

u[i][0]=a[f[i][0]].c;

for(int i=1; i<=23; i++)

for(int j=1; j<=n; j++)

u[j][i]=u[j][i-1]+u[f[j][i-1]][i-1];//倍增

//回答询问

while(q--)

{

ll x,v;

scanf("%lld%lld",&x,&v);

if(v<=a[x].c)

{

printf("%lld\n",x);

continue;

}

v-=a[x].c;

// 如果流2^i次后能被接住，则流到对应的圆盘上

for(int i=23; i>=0; i--)

if(u[x][i]<=v) v-=u[x][i],x=f[x][i];

// 如果还剩下金币，就会流到下面一个

if(v) x=f[x][0];

printf("%lld\n",x);

}

return 0;

}