比赛地址：https://ac.nowcoder.com/acm/contest/60063

先说好消息，搞出模拟了。
再说坏消息，就A了三个.......DE真的很巧妙，尤其D

D：大意是给出给出n*m的矩阵，从11走到nm。求最小花费时间。
两类操作，向上下左右四个反向走，如果与当前点标记不同。
更改下个要走的点，标记使其相反。

个人做法：诈骗DP。我的做法是f[i][0]表示当前点没有被更改时，f[i][1]表示当前点被更改时。然而不可以。过了84

正解：曼哈顿距离判断和1,1的距离，可以得出走了几步到这个点。然后根据奇偶性可以判断是否需要更改才可以到达，因此可以得到边权。
优先队列存储点位，dis[n][m]表示到1,1的距离。djstla搞一下即可。

code：

void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>c[i]+1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            dis[i][j] = INF;
    }
    priority_queue<pair<int,pair<int,int>>> p;
    dis[1][1] = 0;
    p.push({0,{1,1}});
    while(!p.empty()){
        auto t = p.top().se;
        p.pop();
        if(sign[t.fi][t.se])
            continue;
        sign[t.fi][t.se]=1;
        for(int k=0;k<4;k++){
            int nx = t.fi+fx[k],ny = t.se+fy[k];
            int w;
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
                if((nx+ny)&1){
                    if(c[nx][ny]==c[1][1]){
                        w = 2;
                    }else w = 1;
                }else{
                    if(c[nx][ny]==c[1][1]){
                        w = 1;
                    }else w = 2;
                }
            }
            if(dis[nx][ny]>dis[t.fi][t.se]+w){
                dis[nx][ny] = dis[t.fi][t.se]+w;
                p.push({-dis[nx][ny],{nx,ny}});
            }
        }
    }
    cout<<dis[n][m]<<endl;
}

E：大意是给出n和m，求构造数量，每个位上的数仅为m以内。求满足前缀是当前i的倍数的数量。

解法：考虑DP。f[i][j]表示前i个数，总和为i*j的数量。可以转移的是可以到达的i+1的量。直接拿总量去除以i+1，然后开始枚举到m。
复杂度是调和级数，这里没看出来，很惭愧....
剩下直接累加即可，难点是转移从哪里来优化？

code：

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		f[1][i] = 1;
	}
	//f[i][j]表示前i个数，总和为i*j的数量。需要转到可以影响的k位置。从最小影响开始遍历，复杂度是调和级数。
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			ll st = (i-1)*j/i+1;
			ll ed = m;
			for(int k=st;k<=m;k++){
				if(i*k-(i-1)*j>m) break;
				f[i][k]+=f[i-1][j];
				f[i][k]%=mod7;
			}
		}
	}
	ll ans = 0;
	for(int i=1;i<=m;i++){
		ans+=f[n][i];
		ans%=mod7;
	}
	cout<<ans<<endl;
}