补题报告之S班暑训第六场
成绩
比赛经过
\(\text{A}\) 题，这啥鬼，怎么会有语法题，确认不需要高精度后，秒掉了，但是心里还是有些忐忑（咋会有这么入门的题？）。
\(\text{B}\) 题，原题啊？先想了一个 \(O(n^3)\) 的 \(\text{DP}\)，然后尝试找一找有没有决策单调性，发现关键贪心性质，开始码高精度，花了将近 \(1.5h\)。但是考后爆了，实际上洛谷上可以拿到 \(88\) 分的好成绩（因为 \(\text{MLE}\) 爆的）。
\(\text{C}\) 题，勰码作业题，简单的转换一下问题就秒了。
\(\text{D}\) 题，我去，傻瓜打表题，秒了。
赛后补题+分析
A 求和计算
简要/形式化题意
输入若干个数，求和。
题解
\(\text{while}\) 循环输入即可，语法题。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,sum;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin>>x) {
if(!x) {
cout<<sum;
break;
}
sum+=x;
}
return 0;
}
B 划分
简要/形式化题意
将一个序列分成若干区间，要求区间和不降，求所有区间和的平方的和的最小值。
题解
区间划分问题 \(\text{dp}\) 是第一个想到的，设 \(dp_{i,j}\) 表示最后一段为 \((j,i]\) 的最小值。那么有：
这个显然是 \(O(n^3)\) 的。不妨换个思路。
显然的，由数学归纳法不难证明分的段数越多越好。我们跳出 \(\text{dp}\)。如果我们把 \(dp_i\) 当作前 \(i\) 个数的最小代价，\(optdec_i\) 表示 \(i\) 的最优决策点（这个决策点的应该是满足条件的最大下标），就有：
显然的这是 \(O(n^2)\) 的。对于 \(optdec_i\) 的两个决策 \(k<j\)。对于 \(optdec_{i+1}\) 显然 \(k\) 和 \(j\) 也满足条件，也就是说 \(k\) 不可能成为最优决策。我们可以用单调队列维护 \(optdec\) 数组。然后就是 \(O(n)\) 的了。
考虑到空间问题，我们不用存储 \(dp\) 数组，只要从 \(n\) 利用 \(optdec\) 倒推即可。也不不必存储原数组，只要前缀和数组就好了。
最后是高精度，要用 \(\text{int128}\)。
AC code
#include<bits/stdc++.h>
using namespace std;
const int N=4e7+10;
const int M=1e5+10;
const int mod=1<<30;
int n,type;
int x,y,z,m,val,p[M],l[M],r[M];
long long sum[N],b[N];
int h,t,q[N],opt_dec[N];
__int128 ans,delta;
void print(__int128 x) {
if(x>9) print(x/10);
putchar(x%10+'0');
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>type;
if(!type) {
for(int i=1;i<=n;i++) cin>>x,sum[i]=sum[i-1]+x;
}
else {
cin>>x>>y>>z>>b[1]>>b[2]>>m;
for(int i=1;i<=m;i++) cin>>p[i]>>l[i]>>r[i];
for(int i=3;i<=n;i++) b[i]=(x*b[i-1]+y*b[i-2]+z)%mod;
for(int i=1;i<=m;i++)
for(int j=p[i-1]+1;j<=p[i];j++) sum[j]=sum[j-1]+b[j]%(r[i]-l[i]+1)+l[i];
}
h=t=1;
for(int i=1;i<=n;i++) {
while(h<t&&2*sum[q[h+1]]-sum[opt_dec[q[h+1]]]<=sum[i]) h++;
opt_dec[i]=q[h];
while(h<t&&2*sum[q[t]]-sum[opt_dec[q[t]]]>=2*sum[i]-sum[opt_dec[i]]) t--;
q[++t]=i;
}
int dec=n;
ans=0;
while(dec) {
delta=(__int128)(sum[dec]-sum[opt_dec[dec]]);
delta=delta*delta;
ans=ans+delta;
dec=opt_dec[dec];
}
print(ans);
return 0;
}
C 序列统计
简要/形式化题意
统计长度在 \(1\) 到 \(n\) 之间，元素大小都在 \(l\) 到 \(r\) 之间的单调不降序列的数量。
题解
设 \(i\) 的出现次数为 \(x_i\)。问题等价于求。
的正整数向量 \((x_1,x_2,\dots,x_{r-l+1})\) 的非负整数解的个数。这是个经典结论的变形，答案为：
\(\text{Lucas}\) 定理求解即可。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e6+3;
const int N=1e6+3;
int t,n,l,r,fact[N],inv[N];
void init() {
fact[0]=inv[0]=1;
fact[1]=inv[1]=1;
for(int i=2;i<N;i++) {
fact[i]=fact[i-1]*i%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
}
int C(int n,int m,int p) {
if(n<m) return 0;
return fact[n]*inv[fact[m]]%p*inv[fact[n-m]]%p;
}
int Lucas(int n,int m,int p) {
if(!m) return 1;
return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
init();
while(t--) {
cin>>n>>l>>r;
cout<<(Lucas(r-l+1+n,n,mod)-1+mod)%mod<<endl;
}
return 0;
}
D 最小等式
简要/形式化题意
求 |\(a\) o1 \(b\) o2 \(c\) o3 \(d\)| 的最小值， \(o1,o2,o3\) 均为四则运算符。要求算式的结果为整数。
题解
暴力打 \(64\) 个表排序即可，可以写一个循环打表把程序打出来，就不用人力打表了。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a,b,c,d;
int ans[N],cnt;
void work(double x) {
if(x==(int)(x)) ans[++cnt]=abs(x);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>a>>b>>c>>d;
work(a+b+c+d);
work(a+b+c-d);
work(a+b+c*d);
work(a+b+c*1.0/d);
work(a+b-c+d);
work(a+b-c-d);
work(a+b-c*d);
work(a+b-c*1.0/d);
work(a+b*c+d);
work(a+b*c-d);
work(a+b*c*d);
work(a+b*c*1.0/d);
work(a+b*1.0/c+d);
work(a+b*1.0/c-d);
work(a+b*1.0/c*d);
work(a+b*1.0/c*1.0/d);
work(a-b+c+d);
work(a-b+c-d);
work(a-b+c*d);
work(a-b+c*1.0/d);
work(a-b-c+d);
work(a-b-c-d);
work(a-b-c*d);
work(a-b-c*1.0/d);
work(a-b*c+d);
work(a-b*c-d);
work(a-b*c*d);
work(a-b*c*1.0/d);
work(a-b*1.0/c+d);
work(a-b*1.0/c-d);
work(a-b*1.0/c*d);
work(a-b*1.0/c*1.0/d);
work(a*b+c+d);
work(a*b+c-d);
work(a*b+c*d);
work(a*b+c*1.0/d);
work(a*b-c+d);
work(a*b-c-d);
work(a*b-c*d);
work(a*b-c*1.0/d);
work(a*b*c+d);
work(a*b*c-d);
work(a*b*c*d);
work(a*b*c*1.0/d);
work(a*b*1.0/c+d);
work(a*b*1.0/c-d);
work(a*b*1.0/c*d);
work(a*b*1.0/c*1.0/d);
work(a*1.0/b+c+d);
work(a*1.0/b+c-d);
work(a*1.0/b+c*d);
work(a*1.0/b+c*1.0/d);
work(a*1.0/b-c+d);
work(a*1.0/b-c-d);
work(a*1.0/b-c*d);
work(a*1.0/b-c*1.0/d);
work(a*1.0/b*c+d);
work(a*1.0/b*c-d);
work(a*1.0/b*c*d);
work(a*1.0/b*c*1.0/d);
work(a*1.0/b*1.0/c+d);
work(a*1.0/b*1.0/c-d);
work(a*1.0/b*1.0/c*d);
work(a*1.0/b*1.0/c*1.0/d);
sort(ans+1,ans+cnt+1);
cout<<ans[1];
return 0;
}
考后反思
希望 \(CCF\) 不要在考察选手对时间复杂度常熟系数的的把控（卡常真的很难搞）。当然，以后会尽量优化掉冗余步骤。
结尾
这场比赛感觉有点没质量啊（