A.入阵曲

部分分很肥，正解写得常数稍大就会和暴力一个分，考试的时候写什么自己考虑。(滑稽

部分分的循环边界手抖写错了-25 (原本暴力分中的10分都没了啊啊啊)

没写挂的话应该有75，其实就是二维前缀和+暴力枚举点对统计+$a[i][j]$都相等时只枚举子矩形大小再乘上这种大小出现的次数。

正解：$(sum[r]-sum[l-1])\% K=0 \rightarrow sum[r]\% K=sum[l-1]\% K$

枚举行数$i,j$和列数$k$,维护i行和j行之间、k列左侧在%K意义下同余矩阵的个数，用桶来实现。

 

#include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int N=650;int n,m;ll K,ans;int a[N][N];ll sum[N][N],sum1[N],cnt[1000005];int read(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return x*f;}int main(){    n=read();m=read();K=1LL*read();    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            a[i][j]=read();    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+1LL*a[i][j];    for(int i=0;i
        
       
      

 

 

 

B.将军令

我考场都能想到的sb贪心。每次取出深度最大且未被覆盖的点，在它的K级祖先上驻扎即可。前者用堆维护，后者直接暴力修改覆盖状态，注意向上修改时不要只遍历和它在一条链上的。

正确性？读者自证不难。(逃

#include
      
       #include
       
        #include
        
         #include
         
          #define pa pair
          
           #define re registerusing namespace std;int read(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return x*f;}const int N=100005;int n,K,t;int to[N<<1],nxt[N<<1],head[N],tot;inline void add(int x,int y){    to[++tot]=y;    nxt[tot]=head[x];    head[x]=tot;}int dep[N],fa[N];priority_queue
           
             q;void dfs1(int x,int deep){ dep[x]=deep; for(re int i=head[x];i;i=nxt[i]) { int y=to[i]; if(!dep[y])dfs1(y,deep+1),fa[y]=x; } return ;}int cover[N],anc,ans;void getan(int x,int rest){ if(!rest||x==1) { anc=x; return ; } getan(fa[x],rest-1); return ;}void dfs2(int x,int rest,int f){ cover[x]=1; if(!rest)return ; for(re int i=head[x];i;i=nxt[i]) { int y=to[i]; if(y==f)continue; dfs2(y,rest-1,x); } return ;}int main(){ n=read();K=read();t=read(); for(re int i=1;i