CSP-S 2019 游记
update 2019.11.18 考完后的第一感受
update 2019.11.24 我校
某优秀学子把全SD的选手程序全测了一遍（太狠了，于是就知道了大概的惨淡成绩，大概是可怜的省二选手了update 2019.12.13 因为
某些原因又回来写gu掉的部分，然后并没写完update 2019.12.19 考完期中回来继续补锅，期中爆炸
然后学校的12.9活动被gu成12.20
（因为太菜，所以港真是去玩了
感觉这次CSP真的发挥上巨差无疑了。
考场的机子巨巨巨巨巨差，32位机不说，且配置巨低，试机的时候A+B Problem+快读+freopen用了4s多（当场自闭，好像不止我一个人这样？巨影响做题体验(虽然做题体验这东西与没带脑子相比已经不重要了；
旁边是一个青岛二中的神仙小姐姐，还来LCEZ参加过数学夏令营，对我校女生的短发留有深刻的印象。
考试的两天过的还好，day1考前总担心自己会CE，后来看上去应该是没有。考完day1之后整个人心情平静，day2考的毫无波澜（反正不会就不会了
(mathcal{Day 1}:)
day1考前还是很焦虑的，生怕自己CE（现在想想十分迷惑,考完之后吃了午饭，和yrq一起出去逛了逛校园，排解了一下郁闷的心情
回来以后看了day 1 T1 T2的题解。
update:回来指从csp考场回到学校，并不是day1考完的下午
T1:格雷码
看上去好像T1思路是对了的叭？没敢仔细看细节和代码，害怕发现自己代码写锅了然后整个人崩溃掉；不出意外的话大概是可以拿到至少95pts的（对于ull的那5pts好多人说过不去，就很玄乎;只能跪求老天保佑我
update：从学长测得的分数是100pts，大概是qbzt的数据没有卡ull，当我交到luogu上才意识到，原来ull的数据范围是(0 o 2^{64}-1),于是如果最后一个点给的是(2^{64}-1)的话，我就很愉快的挂了（因为我加了1
(mathbb{SOLUTION}):
我属于优秀的打表找规律型人才，于是这道题也是通过打表找到的规律：
并没有按照题目所给的生成方式找规律，而是自成一派
可以观察：
从最高位开始填，
(mathbb{A}.)如果上一个区间是上上个区间的左半区间：
(mathfrak{a}.)如果这一项在它所在当前区间的左半侧（小于等于区间长度的一半，那么在这一位填0，
(mathfrak{b}.)如果在右半侧，填1；
(mathbb{B}.)如果上一个区间是上上个区间的右半区间：
(mathfrak{a}.)如果这一项在它所在当前区间的左半侧（小于等于区间长度的一半，那么在这一位填1
(mathfrak{b}.)如果在右半侧，填1；
注意是(color{ Gold }{当前})区间，这里当前区间的定义大概是：不断二分缩小范围后的区间(color{SkyBlue}{[l,r]}),举个例子：
假设要找四位格雷码的第5项(记j=5（从1开始记项
以下从高位到低位分别为第一位到第n位；
开始时的区间显然是整个四位格雷码 ([1,2^4])，5显然小于区间的一半(2^3)，最高位填0,区间范围缩小为([1,2^3]),
([1,2^3])的一半是(2^2),而(5>2^2)，大于区间的一半，上一个区间是上上个区间的左半区间，第二位填1，区间变为([2^2+1,2^3]),(代码的实现中，如果是一个([2^k+1,2^{k+1}])的区间，将其转化为了([1,2^k])的区间，而将j相应的减掉(2^k))
所以当前区间转化为([1,2^2],j=5-2^2=1，1<2^1),小于等于区间一半，并且上个区间是上上个区间的右半区间，填1，区间变为([1,2],j=1)
(j<=2^0),小于等于区间一半，并且上个区间是上上个区间的左半区间，因此填0；
所以第五项是0110；对照上表，嗯，是对的；
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<iostream>
#define ll long long
using namespace std;
inline unsigned ll read() {
unsigned ll ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n;
unsigned ll k;
int a[200],cnt;
ll quick_pow(int p) {
ll ans=1;
ll a=2;
while(p) {
if(p&1) ans=ans*a;
a*=a;
p>>=1;
}
return ans;
}
void solve(unsigned ll k,int q,int kind) {
//k：第几项（有的时候会被-区间长度一半
//q:填到第几位
//kind:上一个区间是上上个区间的左区间0/右区间1
if(q==0) return ;
ll d=quick_pow(q-1);
if(kind==0) {
if(k<=d) {
a[++cnt]=0;
solve(k,q-1,0);
}
else {
a[++cnt]=1;
solve(k-d,q-1,1);//始终保证区间在[1,2^f]中
}
} else {
if(k<=d) {
a[++cnt]=1;
solve(k,q-1,0);
}
else {
a[++cnt]=0;
solve(k-d,q-1,1);
}
}
}
int main() {
memset(a,0,sizeof(a));
scanf("%d",&n);
k=read();
if(k==18446744073709551615) {//考场上并没有考虑到的爆unsigned long long的情况
printf("1");
for(int i=2;i<=n;i++)
printf("0");
return 0;
}
k++;
solve(k,n,0);
for(int i=1;i<=n;i++)
printf("%d",a[i]);
return 0;
}
T2：括号树
T2考场上是真的毫无思路，连暴力都没想明白怎么打（，然后输出了0或y的生日，期望得分 0（绝望
update：果真爆零,看来(mathfrak{yky})欧气不够啊(mathfrak{yky})
T2:各种暴力部分分（因为考场上啥也没打出来就很很很难过，决心每一部分都要写：
1.期望20pts左右的完全暴力：
(mathbb{SOLUTION}:)
说真的我当时考场上真的连这个题的暴力都没想到
暴力的思路很简单，因为是链，可以依次枚举当前点i，然后枚举区间，判断这个区间是否合法，如果合法，ans++；
复杂度是(O(n^4)),实际并跑不满；
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
ll ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
ll n;
char a[500010];
char Getchar() {
char ch;
do {
ch=getchar();
}while(ch!=')'&&ch!='(');
return ch;
}
ll ans;
ll fa[500010];
bool check(int l,int r) {
int top=0;
for(int i=l;i<=r;i++) {
if(a[i]=='(') top++;
else {
if(top>0)
top--;
else
return 0;
}
}
return top==0?1:0;
}
int main() {
n=read();
for(int i=1;i<=n;i++)
a[i]=Getchar();
for(int i=1;i<n;i++)
fa[i+1]=read();
ll k;
for(int i=1;i<=n;i++) {
k=0;
for(int l=1;l<i;l++) {
for(int r=l+1;r<=i;r++) {
if(check(l,r))
k++;
}
}
ans^=(k*i);
}
printf("%lld",ans);
return 0;
}
2.链上的dp（55pts：
(mathbb{SOLUTION}:)
定义一个lst[i]，记录从1~i，以i结尾的合法的括号序列有多少个
对于一个'('来说，显然lst[i]=0;
所以考虑右括号：
举例子手玩一下：
| 括号√ | ( | ) | ) | ( | ) | ) | ( | ( | ) |
|---|---|---|---|---|---|---|---|---|---|
| lst | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| sum | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 |
| 括号√ | ( | ) | ( | （ | （ | ) | ） | ） | ) |
|---|---|---|---|---|---|---|---|---|---|
| lst | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 2 | 0 |
| sum | 0 | 1 | 1 | 1 | 1 | 2 | 3 | 5 | 5 |
可以发现，当一个括号是右括号（记位置为i）的时候，首先要找是否有匹配的左括号。
如果没有可以匹配的左括号，lst=0；
如果有了匹配的左括号，lst的值至少为1（显然中间的部分都是合法的说 感性李姐，
然后再考虑匹配的左括号左边是否可以与当前的括号再拼成其他的合法括号序列，这个时候我们就要看匹配的左括号的左边一个的lst（记这个位置为t-1），显然的，如果以t-1s结尾的括号可以拼成合法的括号序列，那么它与刚刚匹配的那段序列同样可以组成一个以最后的右括号结尾的合法序列。
因此，(lst[i]=lst[t-1]+1;)
用一个栈来维护左括号是再好不过了：遇到左括号压入栈中，如果碰到一个匹配的右括号，退栈。
于是：
(lst[i]=lst[t-1]+1,t=s[top]\ans[i]=ans[i-1]+lst[i])
于是这就是链的部分分：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
ll ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
ll n;
char a[500010];
char Getchar() {
char ch;
do {
ch=getchar();
}while(ch!=')'&&ch!='(');
return ch;
}
ll Ans;
ll fa[500010];
ll lst[500010],s[500010];
ll ans[500010];
ll top;
int main() {
n=read();
for(int i=1;i<=n;i++)
a[i]=Getchar();
for(int i=1;i<n;i++)
fa[i+1]=read();
for(int i=1;i<=n;i++) {
if(a[i]==')') {
if(top!=0) {
int t=s[top];
top--;
lst[i]=lst[t-1]+1;
}
}
else
s[++top]=i;
ans[i]=ans[i-1]+lst[i];
Ans^=ans[i]*i;
}
printf("%lld",Ans);
return 0;
}
3.关于正解
(mathbb{SOLUTION}:)
考虑把链上的dp转移到树上：
和在链上的dp很类似，因为是在树上，因此只需要将dp式子中的(t-1、i-1)替换成(fa[t]、fa[i])即可；
大致如下：
(lst[u]=lst[fa[t]]+1,t=s[top];\ans[u]=ans[fa[u]]+lst[u])
然后考虑应该如何维护s：
一路向下递归，显然递归得到的是一条链，因此往下递归的时候，按照链的递归方法可劲加就好，主要需要注意的在递归到底以后的回溯上：
(mathbb{A}.)如果当前节点是一个右括号，
(mathfrak{a}.)在这条链上，这个右括号找到了一个匹配的左括号。
显然，左括号会在与右括号匹配过程中从栈中弹出，而当我们要回溯时，被弹出的节点要重新压入栈中，来与其他子树中的右括号匹配，
(mathfrak{b}.)当然，如果这个点没有找到可以匹配的左括号，我们自然不需要再进栈。
(mathbb{B}.)如果当前节点是左括号，那么需要将当前节点退栈。
关于建图的话，因为给出的是明确的父亲儿子关系，因此可以只建单向边。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
ll ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
char Getchar() {
char ch;
do {
ch=getchar();
}while(ch!=')'&&ch!='(');
return ch;
}
const int mxn=500010;
ll n,Ans;
char a[mxn];
ll lst[mxn],ans[mxn];
ll s[mxn],top;
struct node {
int to,nxt;
}e[mxn<<1];
ll ecnt,head[mxn],fa[mxn];
void add(int from,int to) {
++ecnt;
e[ecnt].to=to;
e[ecnt].nxt=head[from];
head[from]=ecnt;
}
void dfs(int u) {
int t=0;
if(a[u]=='(') //左括号，入栈
s[++top]=u;
else {//右括号
if(top!=0) {//可以找到匹配的左括号
t=s[top];
lst[u]=lst[fa[t]]+1;
top--;//退栈
}
}
ans[u]=ans[fa[u]]+lst[u];
Ans^=ans[u]*u;
for(int i=head[u],v;i;i=e[i].nxt) {
v=e[i].to;
dfs(v);
}
if(t!=0) //A: a or b
s[++top]=t;
if(a[u]=='(') //B
top--;
}
int main() {
n=read();
for(int i=1;i<=n;i++)
a[i]=Getchar();
for(int v=2,u;v<=n;v++) {
u=read();
fa[v]=u;
add(u,v);
}
dfs(1);
printf("%lld",Ans);
return 0;
}
T3：树上的数
妄图看懂并且写会T3，然后我发现我错了；
黑题果真不是白评的（哭
考场上的时候非常cǎo的看错了题，认为菊花图和链的部分分还是挺好拿的（然而事实上因为看错题而爆零了
到现在luogu也只有107个人通过它？！
(mathcal{Day 2})
T1:Emiya家今天的饭
作为day2 t1，它好难（哭
考场上：
*这个题暴力我都不会打，怎么dfs啊（哭
诶?!lwy是不是讲过一个类似的dfs？可以先dfs行再dfs列是吧
于是果断打了暴力（以为day2 T1不会这么恶心的
然后发现暴力并过不了较大数据，于是尝试改成记忆化
调到了10点，还是没有调出来，于是
果断放弃（事实上并没有很果断，去看t2，t3
感觉策略上错了，如果打完暴力就跑去写t2t3的话，或许就能少一个题爆零了（因为直到最后记忆化也没有成功
但思路还是要学会的
(mathbb{SOLUTION}):
思路上的突破点在于Yazid的约束，“ 他要求每种主要食材至多在一半的菜（即 (lfloor frac{k}{2} floor)道菜）中被使用 ”,那么如果有一道食材被用在了超过一半的菜中，其余的每一种食材都不会超过一半的菜。由此，可以采用容斥原理：每行至多选1个的方案-每行至多选一个，并且有一列选择的超过了(lfloorfrac{k}{2} floor)道菜；
首先先从简单的开始嘛：如何计算总方案：
定义数组(s[i][0])表示第i行的菜品数的总和，(g[i][j])表示前i行共选了j个数的方案，于是：
(g[i][j]=g[i-1][j]+g[i-1][j-1]*s[i][0])；
也就是前i行选j个数的方案由前i-1行选j个数的方案+前i-1行选j-1个数，第i行选一个数的方案推过来的；
那么(sumlimits_{i=1}^n g[n][i])就是总方案数
再考虑不合法的情况：
首先我们要枚举一列L，表示这一列的选择超过了(lfloorfrac{k}{2} floor)道菜。
设(f[i][j][k])表示前i行，我们枚举的这一列L选了j道，除去L外的其他列选了k道的方案数
设(s[i][L])表示第i行，除去(a[i][L])这个食材所能做成的菜之外能做成的菜的和。
(f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k]*a[i][L]+f[i-1][j][k-1]*s[i][L])
转移方程分为三部分：
(mathbb{A}.)在第i行并不选菜品的方案数，就是上一行在L列选了j道，在其他列选了k道的方案数
(mathbb{B}.)在第i行选择了一道在L列的菜品的方案，首先上一行在L列选择了j-1道，在上一行的基础上，有(a[i][L])种选择方案，可以增加一道在L列的菜品，于是这种情况的方案就是：(f[i-1][j-1][k]*a[i][L])
(mathbb{C}.)在第i行选择了一道不是L列的菜品的方案，即(f[i-1][j][k-1]*s[i][L])
最后计算合法的方案数，也就是：(sumlimits_{j>k} f[n][j][k])（当j>k时，显然选择的菜品超出了总数的一半，嗯
时间复杂度是(O(mn^3))的，可以拿到84pts的分数
考虑优化：
注意到在不合法情况的计算过程中，也就是(f[i][j][k])的转移过程中，我们实际上并不关心j,k的具体数值，而只关心相对的大小关系；所以我们可以将状态变为(f[i][j])，表示前i行，当前L列的数比其他列的数多了j个，则有转移：
(f[i][j]=f[i-1][j]+f[i-1][j-1]*a[i][L]+f[i-1][j+1]*s[i][L])
因为多的j可能是负数，于是我们需要将j同时+n这样如果L列的数比其它列少k的情况，就可以看做：(f[i-1][n-k])
不合法状态最后的答案也就是：
(sumlimits_{j=1}^{n}f[n][n+j])
那么总结起来，最后答案应该为所有方案-不合法方案，即：
(sumlimits_{j=1}^ng[n][j]-sumlimits_{j=1}^nf[n][n+j])
记得取模，大概就好了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
const int mod=998244353;
int n,m;
int a[110][2019];
int s[110][2019];
ll ans,ANS;
ll f[110][320],g[110][310];
int main() {
n=read();m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
a[i][j]=read()%mod;
s[i][0]=(s[i][0]+a[i][j])%mod;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) //写代码时的s*错误之m变n，于是很愉快的挂了9个点（显然已改正
s[i][j]=(s[i][0]-a[i][j]+mod)%mod;
for(int L=1;L<=m;L++) {
f[0][n]=1;
for(int i=1;i<=n;i++)
for(int j=n-i;j<=n+i;j++)
f[i][j]=(f[i-1][j]%mod+(f[i-1][j-1]%mod*a[i][L])%mod+(f[i-1][j+1]%mod*s[i][L])%mod)%mod;
for(int i=1;i<=n;i++)
ans=(ans+f[n][n+i]%mod)%mod;
}
g[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++) {
g[i][j]=g[i-1][j];
if(j>0)
g[i][j]=(g[i][j]+(g[i-1][j-1]*s[i][0])%mod)%mod;
}
for(int i=1;i<=n;i++)
ANS=(ANS+g[n][i])%mod;
printf("%lld",(ANS-ans+mod)%mod);
return 0;
}
T2：划分
在考场上刚开始的时候想到一个非常非常错的贪心（为啥说它非常非常错呢，
因为我连第一组样例都过不了于是果断删了（快考完的时候后悔删掉，应该留着骗分的
（总比最后直接平方加起来可能得到的分多考场上想了dp，然后因为dp巨菜，(O(n^3))的思路几近推出，可最后还是没有推出
（枯了果断dfs滚粗
然后低估了自己dfs可以拿的分，数据分治了n<=50时dfs，拿24pts，但实际好像分可以拿到28pts（虽然只是多了4分但一分也是分啊
在考场上完全没有管type=1的情况，因为明确知道自己前面的分都拿不全。
据说这道题卡内存要写高精（心如止水
果真毒瘤出题人嘛
dfs：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<ctime>
#define ll long long
using namespace std;
inline int read() {
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,type;
int a[500010];
ll sum[500010];
ll ans=214748364720040703;
void dfs(int num,ll now,int Sum) {
if(num==n) {
ans=min(ans,now);
return;
}
for(int i=num+1;i<=n;i++) {
if(sum[i]-sum[num]>=Sum) {
dfs(i,now+(sum[i]-sum[num])*(sum[i]-sum[num]),sum[i]-sum[num]);
}
}
}
int main() {
n=read();
type=read();
if(type==0) {
for(int i=1;i<=n;i++) {
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
if(n<=100) {
dfs(0,0,0);
printf("%lld",ans);
}
}
return 0;
}
(O(n^3) mathcal{DP} 48 pts)
问：我为啥只粘了个代码？？？
(dp[i][j])表示当前划分到i，i的上一个划分点是j的最优值
于是:
(dp[i][j]=min(dp[i][j]+dp[j][k]+(sum[i]-sum[j])^2),sum[i]-sum[j]>=sum[j]-sum[k])
要注意考虑j=0时，(dp[i][j]=min(dp[i][j],(sum[i]-sum[j])^2))
#include<bits/stdc++.h>
#define ull long long
using namespace std;
inline long long read() {
long long ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
ull d(ull x) {return x*x;}
int n,type;
ull a[4110],sum[4110];
ull dp[4110][4110];
int main() {
n=read();
y=read();
if(y==0) {
for(int i=1;i<=n;i++) {
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
ull K=214748364720040703;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dp[i][j]=K;
dp[1][0]=a[1]*a[1];
for(int i=2;i<=n;i++) {
for(int j=0;j<i;j++) {
if(j==0)
dp[i][j]=min(dp[i][j],d(sum[i]-sum[j]));
for(int k=0;k<j;k++)
if(sum[i]-sum[j]>=sum[j]-sum[k])
dp[i][j]=min(dp[i][j],dp[j][k]+d(sum[i]-sum[j]));
}
}
}
ull y=214748364720040703;
for(int i=0;i<n;i++)
y=min(y,dp[n][i]);
printf("%lld",y);
return 0;
}
(O(n^2) mathcal{DP} 64 pts)
用(dp[i][0])表示最后一个划分点是i的最优值，(dp[i][1])表示最优值时，i作为划分点与它前面的数（当然也可以是就它自己）所组成的值是多少；
然后就可以迷惑的算了：
(mathbb{A}.)初始状态(dp[0][0]=dp[0][1]=0)，显然当在第0个数的时候的平方的和与它前面的数都是0；
(mathbb{B}.)考虑如何计算(dp[i][0]):
(mathfrak{a}.)首先考虑a[i]是否可以和前面的某一段数合并成一个数，从而使答案更小：根据某些神奇的贪心想法可以知道，当最后一段的数越小的时候，我们的答案是越小的（感性李姐一下，这里不再展开赘述，因此假设可以与前面某一段数合并成一个数，那么一定是与刚刚我们记录的(dp[i-1][1])合并，因此我们可以计算出((dp[i-1][1]+a[i])^2),然后(+(dp[i-1][0]-dp[i-1][1]^2))（因为以a[i-1]为结尾的这一段数被划分给了a[i],因此在+(i-1)这个位置的贡献时，要把(dp[i-1][1])对(dp[i-1][0])的贡献减去；
(mathfrak{b}.)考虑i是否和以后的某个点j合成一个新的数，相应的对(dp[j][0])做出贡献：从i~n循环枚举j，记录当前a[i]~a[j]的和sum，那么(dp[j][0]=min(dp[i-1][0]+sum^2)),在更新(dp[j][0])的同时更新(dp[j][1]);
(mathbb{C}.)于是最后的答案就是(dp[n][0]);
总的来说64pts思路的突破点在于想到贪心叭。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
inline long long read() {
long long ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
const ull _yKy=214748364720040703;//← ~~我媳妇~~
ull d(ull x) {return x*x;}
int n,type;
ull a[5010];
ull dp[5010][2];
int main() {
n=read();
type=read();
for(int i=1;i<=n;i++) dp[i][0]=_yKy;
if(type==0) {
for(int i=1;i<=n;i++)
a[i]=read();
ull sum=0;
dp[0][0]=dp[0][1]=0;//A
for(int i=1;i<=n;i++) {
//B a:
ull w1=dp[i-1][0]-d(dp[i-1][1]);
ull w2=w1+d(dp[i-1][1]+a[i]);
if(w2<dp[i][0]) {
dp[i][0]=w2;
dp[i][1]=a[i]+dp[i-1][1];
}
//B b:
sum=0;
for(int j=i;j<=n;j++) {
sum+=a[j];
if(sum<dp[i-1][1]) continue;
ull w3=dp[i-1][0]+d(sum);
if(w3<dp[j][0]) {
dp[j][0]=w3;
dp[j][1]=sum;
}
}
}
}
printf("%lu",dp[n][0]);
return 0;
}
update 2019.12.13:
看上去上面的思路有点乱w；
好像这样更容易理解（为什么当时写的时候不写这个w：
(dp[i])表示以i结尾的最优方案，(lst[i])表示以i结尾最优方案的最小段的前端是多少，显而易见的转移方程:
(dp[i]=min{dp[j]+(sum[i]-sum[j])^2}，jin[0,i-1],sum[j]-sum[lst[j]]<=sum[i]-sum[j];)
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
inline int read() {
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
const ll _yKy=214748364720040703;
int n,type;
ll a[50010],A;
ll dp[50010],lst[50010];
ll d(int x) {return x*x;}
int main() {
scanf("%d%d",&n,&type);
for(int i=1;i<=n;i++) {
scanf("%d",&A);
a[i]=a[i-1]+A;
}
for(int i=1;i<=n;i++)
dp[i]=_yKy;
dp[1]=a[1]*a[1];lst[1]=0;
for(int i=2;i<=n;i++) {
for(int j=0;j<i;j++) {
int tmp=d(a[i]-a[j]);
if((a[i]-a[j]>=a[j]-a[lst[j]])&&(dp[i]>dp[j]+tmp)) {
dp[i]=dp[j]+tmp;
lst[i]=j;
}
}
}
printf("%lu",dp[n]);
return 0;
}
$O(n) $正解
咕咕咕
update 2019.12.19
(88 pts)
显然是不用高精度的正解部分：
一个显而易见的结论：
当有多组划分都满足题目的不减性质时，最后一段最小的显然是更优的 =>感性李姐
考虑优化上面的(dp)，
显然我们第二重循环的目的是找一个使(dp[i])最小的(j)，其中满足(sum[i]-sum[j]>=sum[j]-sum[lst[j]])。
"移项，通分，除化乘，母非零"，不知道为什么就突然想起这句话来了（大雾，显然要尝试移项：
(sum[i]>=2*sum[j]-sum[lst[j]])；
然后，(2*sum[j]-sum[lst[j]])是具有单调不减性的（不会证
于是可以使用单调队列维护(2*sum[j]-sum[lst[j]])；
为了方便我们记(2*sum[j]-sum[lst[j]]=> cost(j))
更新时，找队列中最大的满足(cost(j)<=sum[i])的(j)（因为要让最后一段尽量小嘛），然后计算出(cost(i)),显然如果队列队尾的数的(cost>cost(i))的话，那么它一定不会为它后面的某个点的最优值做出贡献（(i)比它大,(cost)还比它小，那么显然用(i)更新更优）于是这些位置就可以"光荣退役"，被弹出队列；（——一个人如果比你小，还比你强，你就可以退役了）
作为(O_2)负优化选手(于是(O_2)多(TLE)了8个点），我也不想说什么了，一定要记得开快读（划重点
#include<bits/stdc++.h>
typedef __int128 LL;
#define ll unsigned long long
using namespace std;
inline ll read() {
ll ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}const int mxn=4e7+5;
const int mod=1<<30;
const int mxm=1e5+5;
int n,type,h,t;
ll a[mxn];
int lst[mxn],deq[mxm];
ll A,b[mxn];
int p[mxm],l[mxm],r[mxm];
LL d(LL x) {return x*x;}
LL cost(int i) {return 2*a[i]-a[lst[i]];}
void print(LL x) {
if(!x) return;
if(x<0) putchar('-'),x=-x;
print(x/10);
putchar(x%10+'0');
}
void Read() {
int x,y,z,m;
x=read();y=read();z=read();
b[1]=read();
b[2]=read();
m=read();
int i;
for(i=1;i<=m;i++) {
p[i]=read();
l[i]=read();
r[i]=read();
}
for(i=3;i<=n;i++)
b[i]=(x*b[i-1]+y*b[i-2]+z)%mod;
for(int j=1;j<=m;j++) {
for(i=p[j-1]+1;i<=p[j];i++) {
a[i]=(b[i]%(r[j]-l[j]+1))+l[j];
a[i]=a[i-1]+a[i];
}
}
}
int main() {
scanf("%d%d",&n,&type);
if(type==0) {
for(int i=1;i<=n;i++) {
A=read();
a[i]=a[i-1]+A;
}
} else
Read();
int i;
lst[0]=0;t=h=1;deq[1]=0;
for(i=1;i<=n;i++) {
while(h<t&&cost(deq[h+1])<=a[i]) h++;
lst[i]=deq[h];
while(h<=t&&cost(deq[t])>=cost(i)) t--;
deq[++t]=i;
}
LL Ans=0;
for(i=n;i>=1;i=lst[i])
Ans+=d(a[i]-a[lst[i]]);
print(Ans);
return 0;
}
T3：树的重心
咕咕咕
相比于T2，好像T3的部分分更容易拿一些，暴力与链的部分如果时间充足的话好像都可以打出来，但考场上的lz非常没有策略的一直也不知道在刚哪个题，反正T3链的部分打MLE了（十分不明白为啥，然后草草打了暴力还没写对（也没有调就这么交上去了，于是胜利爆零；不爆零的话怎么着也有10分了吧
(mathfrak{Before} mathfrak{End}:)
一些闲言碎语：
(mathbb{A}.)看头文件就能看出哪些是考场代码，哪些是回来以后又写的
(mathbb{B}.)虽然在弱省并且今年因为题难于是压得分很低，但就我这点破分大概是与省一无缘的（是真的很希望自己今年能拿省一的，虽然功利了些
(mathbb{C}.)考场上做题策略上可能还不够好叭，对做题顺序没有把握好，而且总是害怕爆，于是很多很暴力的骗分却不敢写（这不符合我写贪心时只管大胆胡说，绝不小心求证的特点诶
(mathbb{D}.)day1 t1 文件名写错成了node，于是day1差点爆零。
$mathbb{E}.$6道题爆了一半的0，格雷码有被卡的可能，算一算今年本来可以拿到但是没拿到的暴力分数得有5+20+10+0+0+25=>55~60分
于是从而因为考CSP从而达成四个星期不回家的成就√
明明很早就该有的东西被我整到都可以申诉了我才发（并且还并没有整完，就当我太颓废了叭