CSP-S2019 JX
注：使用了 IOI 赛制。
赛时：\(100+70+64+0+0=234\)，目测上了 JX 1=。
补题：\(100+100+100+0+100=400\)。
T1
分数变动：\(73 \to 64 \to 73 \to 73 \to 100\)。
首先判定月份是否合法，若不合法则可以 保留个位 或者 把十位变成 \(1\)（\(73\) 分寄因：未考虑后者情况）。
如果合法，则保留原来的月份（\(64\) 分寄因：合法时没有保留原来月份）。
然后判断日期是否在上述两种情况其中一种的月份区间之内，若是则不用改日期，否则保留个位就行。
code
#include<bits/stdc++.h>
using namespace std;
int m,d;
int m1,m2;
const int q[12][2]={{1,31},{1,28},{1,31},{1,30},{1,31},{1,30},{1,31},{1,31},{1,30},{1,31},{1,30},{1,31}};
char op;
int main(){
cin>>m>>op>>d;
int ans=0;
if(m<1||m>12){
ans++;
m1=m%10;
m2=10+m%10;
}
else
m1=m2=m;
if((d<q[m1-1][0]||d>q[m1-1][1])&&(d<q[m2-1][0]||d>q[m2-1][1]))
ans++;
cout<<ans;
return 0;
}
总结：想题时，一定要将所有情况列出在草稿纸上，并多问自己是否全想到了。
涉及的知识点：分类讨论，模拟。
T2
分数变动：\(70\)。
\(70\) 分做法：令 \(sa_i=\sum_{j=1}^i a_j,sb_i=\sum_{j=1}^i b_j\)，枚举每对 \((l,r)\)，令 \(ans \leftarrow ans+(sa_r-sa_{l-1}) \times (sb_r-sb_{l-1})\) 即可。
考虑枚举其中右端点 \(r\)，令 \(ans_r\) 表示以 \(r\) 为右端点的区间的贡献之和，则答案为 \(\sum_{i=1}^n ans_i\)。
接着推式子：
\[ans_r=\sum_{l=1}^r (sa_r-sa_{l-1}) \times (sb_r-sb_{l-1}) \\ =\sum_{l=1}^r sa_r \times sb_r-sa_r \times sb_{l-1}-sa_{l-1} \times sb_r+sa_{l-1} \times sb_{l-1} \\ =r \times sa_r \times sb_r-r \times sa_r \times \sum_{l=0}^{r-1} sb_l-r \times sb_r \times \sum_{l=0}^{r-1} sa_l+\sum_{l=0}^{r-1} sa_l \times sb_l \]于是，我们在计算每个 \(ans_r\) 之后顺便维护 \(\sum_{l=0}^{r-1} sa_l,\sum_{l=0}^{r-1} sb_l,\sum_{l=0}^{r-1} sa_l \times sb_l\) 即可 \(O(1)\) 计算，总时间复杂度 \(O(n)\)。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n;
int ans[N];
int a[N],b[N];
int sa[N],sb[N];
const int MOD=1e9+7;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
int ans1=0,ans2=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sa[i]=(sa[i-1]+a[i])%MOD;
}
for(int i=1;i<=n;i++){
cin>>b[i];
sb[i]=(sb[i-1]+b[i])%MOD;
}
int ssa=0,ssb=0,ssasb=0;
for(int r=1;r<=n;r++){
ans[r]=(((r%MOD*sa[r]%MOD*sb[r]%MOD-sa[r]%MOD*ssb%MOD+MOD)%MOD-sb[r]%MOD*ssa%MOD+MOD)%MOD+ssasb)%MOD;
ssa=(ssa+sa[r])%MOD;
ssb=(ssb+sb[r])%MOD;
ssasb=(ssasb+sa[r]%MOD*sb[r]%MOD)%MOD;
}
int Ans=0;
for(int i=1;i<=n;i++)
Ans=(Ans+ans[i])%MOD;
cout<<Ans;
return 0;
}
总结：看到这种式子比较多的题，考虑推式子，推到将每个部分都可以直接计算或维护了为止。
涉及的知识点：数学。