YC001(育才20240824模拟赛)Solution
T1 恋爱入门问题 :
转换一下柿子:
\[\sum_i^n(T_i\times(F_i-f)+B_i) =\sum_i^n(T_i\times F_i-f\times T_i+B_i) =\sum_i^n(a_i\times x+b_i) \]其中 \(x=f,a_i=T_i,b_i=T_i\times F_i+B_i\)。
然后我们强制 \(a_i>0\)。
那么柿子化成:
\[\sum_i^na_i\times |x-b_i/a_i| \]于是这个柿子的几何意义就是在数轴上 \(b_i/a_i\) 的位置放 \(a_i\) 个点,求一个点到其他点的距离。
经典问题,离散化用线段树和树状数组求带权中位数即可。
T2 基环树环长:
考虑枚举环的长度:
设环长为 \(i\),贡献为 \(i^K\),选出 \(i\) 个点的方案数为 \(C_n^i\),这 \(i\) 个点排成环的方法有 \((i-1)!\) 种,剩余 \(N-i\) 个点随便排列的方案有 \(N^{N-i}\),所以:
\[\sum_{i=1}^ni^K\times C_N^i\times (i-1)!\times N^{N-i} \]至于 \(i^K\) 的话考虑用线性筛把这个当积性函数筛出来。
T3 三:
我都懒得说。
发现最终序列对三取模后至多 27 种状态。
直接爆枚前三个对 3 取模后的结果,往后推即可。
T4 序列:
签。
发现最终序列最优一定是在中间插一段数。直接爆枚在那一位后面加,与加什么数即可。注意处理数的范围,具体细节看代码吧。
read(k,n,m);
int op=1;
for(int i=1;i<=k;i++) read(b[i]),op&=(b[i]==1);
if(op && m==1 && n!=k){
puts("-1");
continue;
}
if(n==k){
for(int i=1;i<=n;i++) cout << b[i] << " \n"[i==n];
continue;
}
b[k+1]=m+1;
int fl=0;
for(int i=1;i<=k+1;i++){
for(int j=1;j<b[i];j++){
if(j!=b[i-1]){
for(int p=1;p<=n-k;p++) cout << j << " ";
for(int p=i;p<=k;p++) cout << b[p] << " ";
fl=1;
}if(fl) break;
}if(fl) break;
cout << b[i] << " ";
}
cout << "\n";
标签:个点,sum,YCOJ,柿子,001,序列,times
From: https://www.cnblogs.com/muleaf/p/18377854