A - Saturday
题意：
给定今天的日期，问到周六还有几天。
分析：
暴力判断即可。
代码：
int main(){
cin>>s;
if(s=="Monday") ans=5;
if(s=="Tuesday") ans=4;
if(s=="Wednesday") ans=3;
if(s=="Thursday") ans=2;
if(s=="Friday") ans=1;
cout<<ans;
return 0;
}
B - Split?
题意：
询问一个保龄球瓶阵是否是一个 split。
split 的定义如下：
- \(1\) 号保龄球被击倒
- 存在两列不同的保龄球瓶，这两列保龄球瓶都没被全部击倒，且两列间存在一列保龄球瓶被全部击倒。
保龄球瓶的排列如下：
分析：
显然 \(1\) 号保龄球瓶没被击倒时一定输出 No。
接下来就是暴力判断了，统计每列的保龄球瓶个数，然后枚举两列即可。
代码：
int get(int x){ // 返回 x 号保龄球瓶所在列
if(x==7) return 1;
if(x==4) return 2;
if(x==2 || x==8) return 3;
if(x==1 || x==5) return 4;
if(x==9 || x==3) return 5;
if(x==10) return 6;
}
int main(){
cin>>s;
s=" "+s;
if(s[1]=='1') cout<<"No";
else{
vector<int> vec(7,0);
for(int i=1;i<=10;i++)
vec[get(i)]+=s[i]-'0';
bool flag=false;
for(int i=1;i<6;i++)
for(int j=i+1;j<=6;j++){
if(vec[i]==0 || vec[j]==0) continue;
bool flag2=false;
for(int k=i+1;k<j;k++)
if(vec[k]==0) flag2=true;
flag|=flag2;
}
cout<<(flag?"Yes":"No");
}
return 0;
}
C - Index × A(Continuous ver.)
题意：
给定一个长度为 \(n\) 的序列 \(A=(A_1,A_2,...,A_n)\)，令 \(B\) 是 \(A\) 的一个长度为 \(m\) 的连续子序列，求 \(\sum\limits_{i=1}^m i*B_i\) 的最大值。
分析：
令 \(f(B)=\sum\limits_{i=1}^m i*B_i\)，考虑求出 \(A\) 序列每一个长度为 \(m\) 的子序列的 \(f\) 值，取最大即可。
如果每次都暴力算过去的话，一共有 \(n-m+1\) 个子序列，每次计算复杂度为 \(O(m)\)，而数据范围是 \(2*10^5\) 显然会超时。
我们发现，相邻两个子序列间有重复的部分，可以节省计算。
假设我们已经算出了 \(f(A_{i-m},...,A_{i-1})\) 的值（记为 \(x\)），那么我们该如何快速求出 \(f(A_{i-m+1},...,A_{i})\) 的值（记为 \(y\)）呢？
不难发现，后者就是前者每个元素权重 \(-1\) 后再加上 \(m*A_i\)，也就是 \(y=x-\sum\limits_{j=i-m}^{i-1}A_j+m*A_i\)。
而 \(\sum\limits_{j=i-m}^{i-1}A_j\) 我们可以通过前缀和预处理得到，所以此题得解，时间复杂度 \(O(n)\)。
代码：
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>arr[i],sum[i]=sum[i-1]+arr[i];
i64 now=0;
for(int i=1;i<=m;i++) now+=i*arr[i]; // 求出 f(A1,...,Am)
i64 ans=now;
for(int i=m+1;i<=n;i++){
now-=sum[i-1]-sum[i-m-1];
now+=m*arr[i];
ans=max(ans,now);
}
cout<<ans;
return 0;
}
D - Index × A(Not Continuous ver.)
题意：
给定一个长度为 \(n\) 的序列 \(A=(A_1,A_2,...,A_n)\)，令 \(B\) 是 \(A\) 的一个长度为 \(m\) 的子序列，求 \(\sum\limits_{i=1}^m i*B_i\) 的最大值。
注：此题与上一题不同在子序列是否要求连续。
分析：
考虑采用动态规划。
设 \(dp_{i,j}\) 表示从前 \(i\) 个元素中选择 \(j\) 个能得到的最大值。
所以此题答案为 \(dp_{n,m}\)。
类似于背包问题，我们在当前有选或不选第 \(i\) 个数两种决策。
若不选择第 \(i\) 个数，则为 \(dp_{i-1,j}\)
若选择第 \(i\) 个数，则为 \(dp_{i-1,j-1}+j*A_i\)
所以状态转移方程就是：
\[dp_{i,j}=\max(dp_{i-1,j}\;,\;dp_{i-1,j-1}+j*A_i) \]状态转移方程得出后，我们便不难编写此题代码了。
代码：
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>arr[i];
// dp[i][j] 表示在前 i 个数中选 j 个得到的最大值
dp[0][0]=0;
dp[0][1]=-2e18; // 非法情况赋值为负无穷
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
if(j==0) dp[i][j]=0; // 一个都不取
else if(j>i) dp[i][j]=-2e18; // 非法情况赋值为负无穷
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+j*arr[i]);
}
cout<<dp[n][m];
return 0;
}
此题还可以通过滚动数组优化空间，这里不再多说。
E - Erasing Vertices 2
题意：
给定一棵 \(n\) 个节点的树，每个节点有一个点权。
你需要进行 \(n\) 次操作，每次操作需要删掉任意一个点，删掉该点的代价为与该点相邻点的点权和，删去该点后与其相邻的边也会被删去。
定义 \(n\) 次操作的花费为这 \(n\) 次操作中代价的最大值，找到删掉整棵树的最小花费。
分析：
我们用 \(d_i\) 表示当前情况删掉第 \(i\) 个节点的代价。
容易发现决策的顺序对最后图的结构是没有影响的（\(n\) 个操作不管按什么顺序删最后图都会变为空），于是我们在操作的时候应尽量先删去 \(d\) 值小的节点，这样在当前是最优的，也不会使之后的操作变劣。
那么如何动态更新操作后每一个节点的 \(d\) 值并查找最小值呢？
朴素的做法是 \(O(n^2)\) 的，显然会超时，这里我们可以使用优先队列来优化，类似于 Dijkstra 算法，我们操作完对相邻节点的 \(d\) 值进行更新，然后只把更新过的 \(d\) 值放进优先队列里，这样子查找最小值的操作复杂度就变成了 \(O(\log n)\) 的，不会超时。
注：代码中 PLI 为 pair<i64,int>，pb 为 push_back，mp 为 make_pair。
代码：
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>arr[i];
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
}
for(int i=1;i<=n;i++)
for(auto v:G[i])
d[i]+=arr[v];
priority_queue<PLI,vector<PLI>,greater<PLI>> pq;
for(int i=1;i<=n;i++) pq.push(mp(d[i],i));
i64 ans=0;
while(!pq.empty()){
PLI now=pq.top(); pq.pop();
if(vis[now.second]) continue;
vis[now.second]=true;
ans=max(ans,now.first);
for(auto v:G[now.second]){ // 更新 d 值
d[v]-=arr[now.second];
pq.push(mp(d[v],v));
}
}
cout<<ans;
return 0;
}