A. Bear and Displayed Friends
这是 Div2 的题，不写。
B. Bear and Forgotten Tree 3
这种东西怎么评蓝的？
Description
给定 \(n,d,h\)，构造一棵有 \(n\) 个点，直径为 \(d\)，高度为 \(h\) 的树。
\(n\le 10^5\)。
Solution
首先 \(d>2h\) 是无解的，\(d=h=1\) 且 \(n>2\) 的时候也无解。
对其它情况，先从根构造两条长度分别为 \(h\) 和 \(d-h\) 的链。
剩下的点如果 \(d=h\) 就随便挂在除根和叶子以外的位置上，\(d\neq h\) 就挂在根上。
Code
const int N=1e5+5;
int n,d,h;
int main()
{
n=read(),d=read(),h=read();
if(d>2*h) {printf("-1\n");return 0;}
if(d==1&&h==1&&n>2) {printf("-1\n");return 0;}
for(int i=2;i<=h+1;i++) cout<<i-1<<" "<<i<<endl;
for(int i=h+2;i<=d+1;i++) cout<<((i==h+2)?1:i-1)<<" "<<i<<endl;
for(int i=d+2;i<=n;i++) cout<<((d==h)?2:1)<<" "<<i<<endl;
return 0;
}
C. Bear and Polynomials
Description
定义一个多项式合法，当且仅当它满足：
- 系数是整数
- 任意项系数的绝对值小于等于 \(k\)
- 最高次项系数不为 \(0\)
给你一个 \(n\) 次多项式 \(P(x)=\sum\limits_{i=0}^n a_i x^i\)，保证其合法且 \(P(2)\neq 0\)。
现在你可以改变 \(P(x)\) 其中一项的系数，设新得到的多项式为 \(Q(x)\)。要求 \(Q(x)\) 合法，且 \(Q(2)=0\)。求可能得到多少种不同的 \(Q(x)\)。
Solution
发现我们只关心 \(P(2)\) 和 \(Q(2)\)，不妨直接把 \(2\) 代入原式，\(P(2)=\sum\limits_{i=0}^n a_i 2^i\)。
这个形式长得像个二进制，那么我们就把每个 \(a_i\notin [0,1]\) 的系数向后进位，转换为一个二进制数。令 \(P(2)=\sum\limits_{i=0}^{n+1} b_i 2_i\)，其中除 \(b_{n+1}\) 外的 \(b_i\) 均为 \(0\) 或 \(1\)。
那么只改一个系数 \(a_i\) 使之变合法，即当前的 \(P(2)\) 是 \(2^i\) 的倍数。这在二进制下等价于 \(<i\) 的 \(b_j\) 均为 \(0\)。
找到第一个 \(b_i\neq 0\) 的位置，从这里开始依次考虑答案，维护 \(P(2)\) 是它的几倍。如果倍数已经 \(>2k\) 就 break 掉即可。
Code
#define int long long
const int N=3e5+5;
int n,k,a[N],y[N];
signed main()
{
n=read(),k=read();
for(int i=0;i<=n;i++) a[i]=y[i]=read();
for(int i=0;i<=n;i++)
{
if(a[i]>0) a[i+1]+=a[i]/2,a[i]=a[i]%2;
else
{
if(a[i]%2) a[i+1]+=a[i]/2-1,a[i]=1;
else a[i+1]+=a[i]/2,a[i]=0;
}
}
int st=n;
for(int i=0;i<=n;i++) if(a[i]) {st=i;break;}
int now=0;
for(int i=n+1;i>st;i--)
{
now=(now<<1)+a[i];
if(abs(now)>2*k) break;
}
int ans=0;
for(int i=st;i>=0;i--)
{
if(abs(now)>2*k) break;
now=(now<<1)+a[i];
if(abs(y[i]-now)<=k&&(i!=n||y[i]!=now)) ans++;
}
printf("%lld\n",ans);
return 0;
}
D. Bear and Contribution
Description
有 \(n\) 个贡献值 \(v_1,v_2,\dots,v_n\)，将其中一个贡献值 \(+5\) 需要花费 \(b\)，将其中一个贡献值 \(+1\) 需要花费 \(c\)。
求需要使其中的 \(k\) 个贡献值相等的最小花费。
\(2\le n,k\le 2\times 10^5\)，\(1\le b,c\le 2000\)，\(|v_i|\le 10^9\)。
Solution
将 \(v_i\) 升序排序，从小到大枚举 \(k\) 个数相等后的值 \(x\)。
发现如果没有第一种操作，那么每个数增加到 \(x\) 的代价是单调的，令至少 \(k\) 个数变成 \(a_i\) 的最优方案一定是修改 \(a_{i-k+1}\) 到 \(a_i\) 这一段。
而第一种操作会对单调性造成影响。但是可以发现，对于所有 \(\bmod\ 5\) 的值相同的 \(v_i\)，它们之间不会被 \(+5\) 的操作改变单调性。
同理，我们也可以得到 \(+5\) 操作对可能成为答案的数的影响：所有 \(v_i+j(j\in [0,4])\) 都可能成为最后的答案。
把 \(v_i\) 按 \(\bmod\ 5\) 的值分组，同时把询问也按此分组。那么同组的 \(v_i\) 之间单调；同组的询问之间也单调。
对每组分别维护属于答案的队列，每次新增元素时删除 \(5\) 组中代价最大的那个队首即可。
时间复杂度 \(O(n\log n)\)，瓶颈在排序。
Code
#define int long long
const int N=2e5+5,inf=1e18;
int n,k,b,c,v[N];
vector<int> a[5],q[5];
int ans=inf,st[5],ed[5];
il int get(int x,int y) {return (y-x)/5*b+(y-x)%5*c;}
void solve(int id)
{
for(int i=0;i<5;i++) st[i]=0,ed[i]=-1;
int sum=0,now=0;
for(int I=0;I<q[id].size();I++)
{
int x=q[id][I],lst=I?q[id][I-1]:id;
now+=sum*((x-lst)/5)*b;
for(int i=0;i<5;i++)
{
while(ed[i]+1<a[i].size()&&a[i][ed[i]+1]<=x)
{
if(sum==k)
{
int mx=0;
for(int j=0;j<5;j++)
if(st[j]<=ed[j]) mx=max(mx,get(a[j][st[j]],x));
if(mx>get(a[i][ed[i]+1],x))
for(int j=0;j<5;j++)
if(st[j]<=ed[j]&&get(a[j][st[j]],x)==mx) {now-=mx,sum--,st[j]++;break;}
}
if(sum<k) sum++,ed[i]++,now+=get(a[i][ed[i]],x);
else break;
}
}
if(sum==k) ans=min(ans,now);
}
}
signed main()
{
n=read(),k=read(),b=read(),c=read();
b=min(b,5*c);
for(int i=1;i<=n;i++) v[i]=read();
sort(v+1,v+n+1);
int mn=abs(v[1]);
for(int i=1;i<=n;i++) v[i]+=mn;
for(int i=1;i<=n;i++)
{
a[v[i]%5].push_back(v[i]);
for(int j=0;j<5;j++) if(i==n||v[i]+j<v[i+1]) q[(v[i]+j)%5].push_back(v[i]+j);
}
for(int i=0;i<5;i++) solve(i);
printf("%lld\n",ans);
return 0;
}