A-小杜要迟到了！

题解

比较(n-1)*a和 (n+k-2)*b的大小，按要求输出结果即可。 时间复杂度O(1)

参考代码

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);++i)
#define R(i,j,k) for(ll i=(j);i>=(k);--i)
#define inf 2e9
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const int N=1e6+10,M=10;
const int mod=998244353,mmod=mod-1;
const double pi=acos(-1),eps=1e-8;
using namespace std;

int m,n,t,x,y,z,l,r,u,v,k,p,pp,nx,ny,nz,ansx,ansy,mn,mx;
int a,b;
int rt,op,lim,pos,key,block;
int cnt,tot,num,sum,ans;

void solve(){
    scanf("%d%d%d%d",&n,&k,&a,&b);
    ll x=1ll*(n-1)*a;
    ll y=1ll*(n+k-2)*b;
    if(x>y)puts("1");
    else if(x<y)puts("2");
    else puts("0");
}

int main(){
    int Case=1;
    //scanf("%d",&Case);
    while(Case--)solve();
}

B-小杜捕鱼

题解

考虑哪个位置距离所有鱼的位置的最大值最大，即矩形鱼塘的四个角落。分别计算撒网中心落在(1,1)，(1,m)，(n,1)，(n,m)时，与所有鱼的曼哈顿距离的最大值。四种结果再取一个最大值。 时间复杂度O(nm)

参考代码

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define inf 2e9
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const int N=1e3+10,M=10;
const int mod=998244353,mmod=mod-1;
const double pi=acos(-1),eps=1e-8;
using namespace std;

int m,n,t,x,y,z,l,r,u,v,k,p,pp,nx,ny,nz,ansx,ansy,mn,mx;
int a,b;
int rt,op,lim,pos,key,block;
int cnt,tot,num,sum,ans;
char s[N][N];

void solve(){
    scanf("%d%d",&n,&m);
    ans=0;
    L(i,1,n)scanf("%s",s[i]+1);
    L(i,1,n)L(j,1,m)if(s[i][j]=='#'){
        ans=max(ans,i-1+j-1);
        ans=max(ans,i-1+m-j);
        ans=max(ans,n-i+j-1);
        ans=max(ans,n-i+m-j);
    }
    printf("%d\n",ans);
}

int main(){
    int Case=1;
    //scanf("%d",&Case);
    while(Case--)solve();
}

C-Karashi的生日蛋糕

题解

记sv[i][j]表示第i块蛋糕第j圈水果的个数，首先保证sv[i][j]有⌊j/k⌋个水果。 对于第j列，我们还需添加j%k个水果，我们在保证两两水果总数相差不大于1的情况下，按照顺序逐一添加，其规律见下图，每一列新增的水果从上一列水果的末尾开始新增，以此保证任意两块蛋糕水果总数相差不大于1。我们可以开二维不定长数组vector模拟此过程。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define inf 2e9
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const int N=1e3+10,M=10;
const int mod=998244353,mmod=mod-1;
const double pi=acos(-1),eps=1e-8;
using namespace std;

int m,n,t,x,y,z,l,r,u,v,k,p,pp,nx,ny,nz,ansx,ansy,mn,mx;
int rt,op,lim,pos,key,block;
int cnt,tot,num,sum,ans;

void solve(){
    scanf("%d%d",&n,&k);
    vector<vector<int> >sv(k+2,vector<int>(n+2,0));
    p=1;
    L(j,1,n)L(i,1,j%k){
        sv[p][j]=1;
        p++;
        if(p>k)p-=k;
    }
    L(i,1,k){
        L(j,1,n){
            printf("%d ",sv[i][j]+j/k);
        }
        printf("\n");
    }
}

int main(){
    int Case=1;
    //scanf("%d",&Case);
    while(Case--)solve();
}

D-Karashi的树

题解

首先考虑化简这棵树的价值Val。可以发现每一个点的权值在答案中计算了其子树大小次，即${\sum }_{i=1}^n{\sum }_{x\in pat{h}_i}{a}_x={\sum }_{i=1}^n{a}_i\times si{z}_i\sum \_\{i=1\}^n\sum \_\{x\in path\_i\}a\_x\; =\sum \_\{i=1\}^n\; a\_i\backslash times\; siz\_i$，其中$si{z}_{i}siz\_i$表示以$ii$为根的子树大小。因此，我们需要尽可能将较大的权值尽可能转移到子树较大的地方去。 容易发现，我们可以通过两次操作，将点u的权值转移到任意点v（即第一次选择节点u操作，第二次选择节点v操作），并且只会改变路径(1,u)与路径(1,v)上的权值。在转移过程中，我们并不需要在意路径中间那部分的权值变化，我们只关注两头。

所以我们按照拓补序的顺序转移权值，即先修改叶子的权值，再一层层往上修改。可以保证最终序列a与序列siz按顺序从小到大一一匹配。 因此，我们只需要将数组a按从小到大排序，将siz按从小到大排序，然后计算$Val={\sum }_{i=1}^n{a}_i\times si{z}_{i}Val=\sum \_\{i=1\}^n\; a\_i\backslash times\; siz\_i$即可。 时间复杂度O(nlogn)

参考代码

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define inf 2e9
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const int N=1e6+10,M=10;
const int mod=998244353,mmod=mod-1;
const double pi=acos(-1),eps=1e-8;
using namespace std;

int m,n,t,x,y,z,l,r,u,v,k,p,q,pp,nx,ny,nz,ansx,ansy,mn,mx;
int rt,op,lim,pos,key,block;
ll cnt,tot,num,sum,ans;
int a[N],siz[N];

struct edge{
    int cnt,hed[N],to[N*2],nxt[N*2];
    void add(int u,int v){to[++cnt]=v;nxt[cnt]=hed[u];hed[u]=cnt;}
    void ADD(int u,int v){add(u,v);add(v,u);}
    void clear(int n){cnt=0;L(i,1,n)hed[i]=0;}
}eg;

void dfs(ll u){
    siz[u]=1;
    for(ll i=eg.hed[u];i;i=eg.nxt[i]){
        ll v=eg.to[i];
        dfs(v);
        siz[u]+=siz[v];
    }
}

void solve(){
    scanf("%d",&n);
    L(i,1,n)scanf("%d",&a[i]);
    L(i,2,n){
        scanf("%d",&x);
        eg.add(x,i);
    }
    dfs(1);
    sort(a+1,a+n+1);
    sort(siz+1,siz+n+1);
    ans=0;
    L(i,1,n){
        ans+=1ll*a[i]*siz[i];
    }
    printf("%lld\n",ans);
}

int main(){
    int Case=1;
    //scanf("%d",&Case);
    while(Case--)solve();
}

E-Karashi的数组

题解

记$A=a_k\mathrm{，}B={\sum }_{i=k+1}^{k+len}{a}_i\mathrm{，}C=a_{k+len+1}A=a\_k，B=\sum \_\{i=k+1\}^\{k+len\}a\_i\; ，C=a\_\{k+len+1\}$。 由此，$S(L)\times S(R)=S(L\cup R)\times S(L\cap R)S(L)\times S(R)=S(L\cup R)\times S(L\cap R)$ 可以转化为$(A+B)(B+C)=(A+B+C)B(A+B)(B+C)=(A+B+C)B$，化简可得$AC=0AC=0$。 因为A和C的区间长度仅为1，所以答案等价于：对于$i\in [1,n-len-1]i\in [1,n-len-1]$，满足$a_i=0a\_i=0$或$a_{i+len+1}=0a\_\{i+len+1\}=0$的个数。 我们先预处理出满足上述条件的数量，对于每次修改操作，我们再对答案进行增减修改即可。 时间复杂度O(n+m)

参考代码

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define inf 2e9
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const int N=1e6+10,M=10;
const int mod=998244353,mmod=mod-1;
const double pi=acos(-1),eps=1e-8;
using namespace std;

int m,n,t,x,y,z,l,r,u,v,k,p,q,pp,nx,ny,nz,ansx,ansy,mn,mx;
int rt,op,lim,pos,key,block;
int cnt,tot,len,num,sum,ans;
int a[N];

void solve(){
    scanf("%d%d%d",&n,&m,&len);
    L(i,1,n)scanf("%d",&a[i]);
    ans=0;
    L(k,1,n-len-1){
        if(a[k]==0||a[k+len+1]==0)ans++;
    }
    while(m--){
        scanf("%d%d",&pos,&x);
        l=pos-len-1,r=pos;
        if(1<=l&&l<=n-len-1&&a[l]!=0){
            if(a[pos]==0)ans--;
            if(x==0)ans++;
        }
        if(1<=r&&r<=n-len-1&&a[r+len+1]!=0){
            if(a[pos]==0)ans--;
            if(x==0)ans++;
        }
        printf("%d\n",ans);
        a[pos]=x;
    }
}

int main(){
    int Case=1;
    //scanf("%d",&Case);
    while(Case--)solve();
}

F-小杜跑酷

题解

考虑动态规划，先将机关按y值排序，考虑经过(x,y)的方案数，容易推导出：

如果该位置有机关， dp[max(1,x-1)][min(n,y+1)]+=dp[x][y]， dp[min(3,x+1)][min(n,y+1)]+=dp[x][y]， dp[x][min(n,y+2)]+=dp[x][y]； 如果该位置没有机关， dp[x][min(n,y+1)]+=dp[x][y] ；

但是，这边的n有10^9，因此我们只需要考虑有机关的dp值。当该单元格不存在机关时，我们可以直接将该单元格的值传递到同层的后一个机关处，将每层机关排序预处理，可以使用二分直接找到后一个机关的位置。 时间复杂度O(mlogm)

参考代码1

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define inf 2e9
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const int N=5e5+10,M=10;
const int mod=998244353,mmod=mod-1;
const double pi=acos(-1),eps=1e-8;
using namespace std;

int m,n,t,x,y,z,l,r,u,v,k,p,pp,nx,ny,nz,ansx,ansy,mn,mx;
int rt,op,lim,key,block;
int pos[5],cnt[5],tot,num,sum,ans;
int a[5][N],dp[5][N];

struct qq{int x,y;}q[N];
bool cmp(qq u,qq v){
    return u.y<v.y;
}

void ps(int &x,int y){
    x=(x+y>=mod?x+y-mod:x+y);
}

void solve(){
    scanf("%d%d",&n,&m);
    L(i,1,m){
        scanf("%d%d",&x,&y);
        a[x][++cnt[x]]=y;
        q[++num]={x,y};
    }
    L(i,1,3){
        a[i][++cnt[i]]=n;
        q[++num]={i,n};
    }
    L(i,1,3)sort(a[i]+1,a[i]+cnt[i]+1);
    sort(q+1,q+num+1,cmp);
    dp[1][1]=1;
    L(i,1,num){
        if(q[i].y==n)break;
        l=q[i].x,r=++pos[l];

        x=max(1,q[i].x-1),y=q[i].y+1;
        p=lower_bound(a[x]+1,a[x]+cnt[x]+1,y)-a[x];
        ps(dp[x][p],dp[l][r]);

        x=min(3,q[i].x+1),y=q[i].y+1;
        p=lower_bound(a[x]+1,a[x]+cnt[x]+1,y)-a[x];
        ps(dp[x][p],dp[l][r]);

        x=q[i].x,y=min(n,q[i].y+2);
        p=lower_bound(a[x]+1,a[x]+cnt[x]+1,y)-a[x];
        ps(dp[x][p],dp[l][r]);
    }
    L(i,1,3)printf("%d\n",dp[i][cnt[i]]);
}

int main(){
    int Case=1;
    //scanf("%d",&Case);
    while(Case--)solve();
}

参考代码2

考虑不使用二分，直接传递

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define inf 2e9
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const int N=5e5+10,M=10;
const int mod=998244353,mmod=mod-1;
const double pi=acos(-1),eps=1e-8;
using namespace std;

int m,n,t,x,y,z,l,r,u,v,k,p,pp,nx,ny,nz,ansx,ansy,mn,mx;
int rt,op,lim,key,block;
int pos[5],cnt[5],tot,num,sum,ans;
int a[5][N],dp[5][N];

struct qq{int x,y;}q[N];
bool cmp(qq u,qq v){
    return u.y<v.y;
}

void ps(int &x,int y){
    x=(x+y>=mod?x+y-mod:x+y);
}

void solve(){
    scanf("%d%d",&n,&m);
    L(i,1,m){
        scanf("%d%d",&x,&y);
        a[x][++cnt[x]]=y;
        q[++num]={x,y};
    }
    L(i,1,3){
        a[i][++cnt[i]]=n;
        q[++num]={i,n};
    }
    L(i,1,3)sort(a[i]+1,a[i]+cnt[i]+1);
    sort(q+1,q+num+1,cmp);
    dp[1][1]=1;
    L(i,1,3)pos[i]=1;
    L(i,1,num){
        if(q[i].y==n)break;
        l=q[i].x,r=pos[l]++;

        x=max(1,q[i].x-1),y=q[i].y+1;
        p=(a[x][pos[x]]<y?pos[x]+1:pos[x]);
        ps(dp[x][p],dp[l][r]);

        x=min(3,q[i].x+1),y=q[i].y+1;
        p=(a[x][pos[x]]<y?pos[x]+1:pos[x]);
        ps(dp[x][p],dp[l][r]);

        x=q[i].x,y=min(n,q[i].y+2);
        p=(a[x][pos[x]]<y?pos[x]+1:pos[x]);
        ps(dp[x][p],dp[l][r]);
    }
    fclose(stdin);
    L(i,1,3)printf("%d\n",dp[i][cnt[i]]);
}

int main(){
    int Case=1;
    //scanf("%d",&Case);
    while(Case--)solve();
}

/* 元旦将至，提前祝大伙元旦快乐 */