只会 \(A\sim G\)
主观难度：\(A<B<C<E<D<F<G<Ex\)
A - Saturday
分别对周一到周五判断即可。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
string s;
int main(){
cin>>s;
if(s=="Monday")puts("5");
else if(s=="Tuesday")puts("4");
else if(s=="Wednesday")puts("3");
else if(s=="Thursday")puts("2");
else puts("1");
return 0;
}
B - Split?
将十个数映射到长度为 \(7\) 的数组 \(t\) 中（因为一共有 \(7\) 列），判断是否编号为 \(1\) 的球倒了且 \(t[i]\) 列没全倒，\(t[i+1]\) 列全倒了，\(t[i+2]\sim t[7]\) 是否有没全倒的。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
char a[11];
int t[10];
int main(){
cin>>a+1;
for(int i=1;i<=10;++i){
if(a[i]=='1'){
if(i==1||i==5)t[4]++;
else if(i==2||i==8)t[3]++;
else if(i==4)t[2]++;
else if(i==7)t[1]++;
else if(i==10)t[7]++;
else if(i==6)t[6]++;
else t[5]++;
}
}
for(int i=1;i<=7;++i){
if(t[i]&&!t[i+1]){
for(int j=i+2;j<=7;++j){
if(t[j]&&a[1]=='0'){
puts("Yes");
return 0;
}
}
}
}
puts("No");
return 0;
}
C - Index × A(Continuous ver.)
记 \(sum[i]=\sum\limits_{j=1}^ia_j,f[i]=\sum\limits_{j=1}^{m}j\times a_{i-m+j}\)。
考虑如何 \(O(1)\) 从 \(f[i-1]\) 转移到 \(f[i]\)。
\(f[i]=f[i-1]-(sum[i-1]-sum[i-1-m])+m\times a_i\)
取 \(f[m]\sim f[n]\) 的最大值即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=2e5+5;
int n,m,a[N],sum[N],f,ans=-1e18;
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read(),sum[i]=sum[i-1]+a[i];
for(int i=1;i<=m;++i)f+=i*a[i];ans=f;
for(int i=m+1;i<=n;++i)f=f-(sum[i-1]-sum[i-1-m])+m*a[i],ans=max(ans,f);
print(ans);
return 0;
}
D - Index × A(Not Continuous ver.)
设 \(f[i][j]\) 为在前 \(i\) 个数中选 \(j\) 个数，强制选 \(a[i]\) 的最大值。
我们发现这样转移是 \(O(n^3)\) 的，考虑优化，对于 \(i,j\)，我们可以记录 \(f\) 的最大值，然鹅这样不太好。
重新设 \(f[i][j]\) 为在前 \(i\) 个数中选 \(j\) 个数，不强制选 \(a[i]\) 的最大值。
\(f[i][j]=\max(f[i-1][j],f[i-1][j-1]+j\times a_i)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=2e3+5;
int n,m,a[N],f[N][N];
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=0;i<=n;++i)for(int j=1;j<=m;++j)f[i][j]=-1e18;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i]*j);
}
}
print(f[n][m]);
return 0;
}
E - Erasing Vertices 2
考虑贪心，记 \(f(i)\) 为点 \(i\) 计算出来的值，我们从最小点值的点开始删，因为 \(f(i)\) 不会增大，所以这样一定是最优的。
- 用一个 \(set\) 维护，需要注意的是，若
set<node>s的node重载运算小于号时，两个变量都需要考虑到。
这样写：
struct NODE{
int num,w;
bool operator<(const NODE &p)const{return w==p.w?num<p.num:w<p.w;}
};
set<NODE>s;
而不能这样写：
struct NODE{
int num,w;
bool operator<(const NODE &p)const{return w<p.w;}
};
set<NODE>s;
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=2e5+5;
int n,m,a[N],head[N],cnt,f[N];
bool vis[N];
struct node{
int to,next;
}e[N<<1];
void add(int from,int to){
e[++cnt]={to,head[from]},head[from]=cnt;
}
struct NODE{
int num,w;
bool operator<(const NODE &p)const{return w==p.w?num<p.num:w<p.w;}
};
set<NODE>s;
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
for(int i=1;i<=n;++i){
for(int j=head[i];j;j=e[j].next){
f[i]+=a[e[j].to];
}
s.insert({i,f[i]});
}
int ans=0,cnt=n;
while(cnt--){
int u=(*s.begin()).num;
ans=max(ans,(*s.begin()).w);
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v])continue;
s.erase({v,f[v]});
f[v]-=a[u];
s.insert({v,f[v]});
}
s.erase({u,f[u]});
vis[u]=1;
}
print(ans);
return 0;
}
F - Exactly K Steps
这题排除一些不可做的想法之后，我们可以想到树的直径和将 \(k\) 分解倍增。
一种很麻烦的方法是，把一颗树拆分成一条直径，若能走到直径上，在直径上倍增即可；若不能走到直径上，从该点和直径上的最近点跳即可，需要很多的分类讨论以及细节。
- 直接让直径的两个端点为根，各求一遍关于点 \(i\) 的 \(2^j\) 级祖先，直接求该点的 \(k\) 级祖先即可。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=2e5+5;
int n,q,head[N],cnt,a[N],num;
struct node{
int to,next;
}e[N<<1];
void add(int from,int to){
e[++cnt]=(node){to,head[from]},head[from]=cnt;
}
int dis[N],pre[N],L,R,lg[N],tmp;
bool vis[N];
int fl[N][21],fr[N][21],depl[N],depr[N],disl[N],disr[N];
void dfs(int x,int Fa){
dis[x]=dis[Fa]+1;
pre[x]=Fa;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==Fa)continue;
dfs(y,x);
if(dis[y]>dis[tmp])tmp=y;
}
}
void get_d(){
tmp=1;
dis[0]=-1;
dfs(1,0);
L=tmp,dis[0]=-1;
dfs(tmp,0);
R=tmp,num=dis[R]+1;
}
void dfsL(int x,int fa){
depl[x]=depl[fa]+1,fl[x][0]=fa;
for(int i=1;i<=lg[depl[x]];++i)fl[x][i]=fl[fl[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==fa)continue;
dfsL(y,x);
}
}
void dfsR(int x,int fa){
depr[x]=depr[fa]+1,fr[x][0]=fa;
for(int i=1;i<=lg[depr[x]];++i)fr[x][i]=fr[fr[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==fa)continue;
dfsR(y,x);
}
}
int get_kth_fa_L(int x,int k){
if(!k)return x;
if((1<<lg[k])==k)return fl[x][lg[k]];
return get_kth_fa_L(fl[x][lg[k]],k-(1<<lg[k]));
}
int get_kth_fa_R(int x,int k){
if(!k)return x;
if((1<<lg[k])==k)return fr[x][lg[k]];
return get_kth_fa_R(fr[x][lg[k]],k-(1<<lg[k]));
}
int main(){
n=read();
for(int i=1;i<=n-1;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
get_d();
for(int i=R;i;i=pre[i])vis[i]=1,a[num--]=i;
for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
num=dis[R]+1;
depl[0]=depr[0]=-1;
dfsL(L,0);
dfsR(R,0);
q=read();
while(q--){
int u=read(),k=read(),ans;
if(depl[u]<k&&depr[u]<k)ans=-1;
else if(depl[u]>=k)ans=get_kth_fa_L(u,k);
else ans=get_kth_fa_R(u,k);
print(ans),puts("");
}
return 0;
}
G - Increasing K Times
不妨从大到小放入，假设原来本就有两个数 \(\{0,0\}\) 我们在其中插入数，这样最后我们求的是恰好有 \(k+1\) 个。
记 \(f[i][j]\) 为插入前 \(i\) 小的数，使得有 \(j\) 个 \(a_p<a_{p+1}\) 的方案数。
分析一波在 \(a_p\) 和 \(a_{p+1}\) 之间插入的情况，发现只有 \(a_i>a_p\ge a_{p+1}\) 的情况，将 \(a_i\) 插入到 \(a_p\) 和 \(a_{p+1}\) 之间会使个数增加 \(1\)，其余都是 \(0\)。
先排序一遍。
已放入 \(i-1\) 个数，之前有 \(cnt\) 个数与 \(a_i\) 相同。
\(f[i][j]=(j+cnt)f[i-1][j]+(i+1-j-cnt)f[i-1][j-1]\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=5e3+5,mod=998244353;
int n,k,a[N],f[N][N],cnt;
signed main(){
n=read(),k=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
f[0][0]=1;
for(int i=1;i<=n;++i){
if(a[i]==a[i-1])cnt++;
else cnt=0;
for(int j=1;j<=min(k+1,i+1-cnt);++j){
f[i][j]=(f[i-1][j]*(j+cnt)%mod+f[i-1][j-1]*(i+1-j-cnt)%mod)%mod;
}
}
print(f[n][k+1]);
return 0;
}