NOIP提高组模拟赛4
A. 入阵曲
丹青千秋酿，一醉解愁肠。
无悔少年枉，只愿壮志狂。
矩阵前缀和加暴力\(O(N^2M^2)\) 60pts有手就行
观察数据范围，猜测应该是求一种\(O(N^3)\)的算法，想到之前做的题，应该是\(N^2\)枚举行,\(N\)处理一个序列的答案，然后，就没有然后了
对于一个序列，求子段和为k的倍数，如何\(O(N)\)求解，
考虑前缀和，如果一个子段和为k的倍数，那么子段的左右两界在模k意义下是同余的，开数组记录，\(s[i]\)表示模k余数为i的前缀和有几个，而任意两个都对应一个合法的矩阵，所以可以愉快的切掉此题，还有一点就是\(s[0]\)初值应设为1，原因模k为0的直接就是合法矩阵。
记得开longlong，还有不要每次memset，不然你会喜提TLE35 还不如暴力
#include
#include
using namespace std;
const int maxn=405;
int n,m,k;
int mp[maxn][maxn];
long long sum[maxn][maxn];
int s[1000005];
int main()
{
freopen("rally.in","r",stdin);
freopen("rally.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&mp[i][j]);
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]+mp[i][j];
long long ans=0;
for(int i=1;i<=n;++i)
for(int x=i;x<=n;++x)
{
s[0]=1;
for(int j=1;j<=m;++j){
long long w=(sum[x][j]-sum[i-1][j])%k;
ans+=s[w];s[w]++;
}
for(int j=1;j<=m;++j){
long long w=(sum[x][j]-sum[i-1][j])%k;
s[w]--;
}
}
printf("%lld\n",ans);
return 0;
}
B. 将军令
历史落在赢家之手,至少我们拥有传说
谁说败者无法不朽,拳头只能让人低头
念头却能让人抬头,抬头去看去爱去追
你心中的梦
就我一个打DP的，思路没啥问题，但是挂了一堆细节，调了一个多小时，结果只有20pts，然后改了亿一点细节A了
画图可以发现，转移时子节点不仅可能对父节点有贡献，还可能需要父节点贡献，设\(g[x][i]\)表示以x为根的子树能够驻守的距离为i的最小方案，转移时我们需要知道\(g[v][j]\)(v是x的子节点，\(j \in [-k,k]\))，为了处理下标为负的情况，我统一加上了21，也可以像洛谷题解一样加k。
考虑具体过程(具体代码下标请自行加上一个常数)
如果是叶节点 那么\(g[x][i]=0\;(i\in [-k,-1]) g[x][i]=1\;(i\in [0,k])\)
一般情况的转移
预处理\(ls[i]\)记录x子树驻守距离为i的方案之和
如果在x驻守，那么子节点贡献-k即可\(g[x][k]=ls[-k]+1\)
如果x有正贡献i，但是没有在x驻守，那么一定有一个子节点贡献了i+1，其他子节点贡献-i即可\(g[x][i]=min(g[v][i+1]+ls[-i]-g[v][-i])i\in[0,k)\)
如果x有负贡献i，那么所有子节点贡献了i+1才保证合法\(g[x][i]=ls[i+1]i\in[-k,-1]\)
由于某些状态实际上不存在，所以存在\(g[x][i]>g[x][j](i< j)\)这显然不合理，所以需要倒着取\(min\)即\(g[x][i]=min(g[x][i],g[x][i+1])\)，这样保证了i越小g也越小，且保证合法
dp到这里就结束了，然后我们再简单讲讲正解
考虑放弃DP，这题可以贪心，随便找个根，然后找最深的点，在该点的k级祖先驻守一定最优，按点深度从大到小排序，每次取最深的点，检查是否被控制，没有就驻守k级父亲或者根节点，暴力更新周围点。
附dp代码
#include
#include
using namespace std;
int min(int x,int y){return x=21-k;--i)g[x][i]=min(g[x][i],g[x][i+1]);
}
//print();
}
int main()
{
freopen("general.in","r",stdin);
freopen("general.out","w",stdout);
scanf("%d%d%d",&n,&k,&t);
for(int i=1;i C. 星空
命运偷走如果只留下结果，时间偷走初衷只留下了苦衷。
你来过， 然后你走后， 只留下星空。
这题，挺神的。。。
考场由于调T2根本没时间打T3，最后输出2居然骗了12pts
搜索类似分手是祝愿那题，大概有72pts，可恶啊
正解需要亿点巧妙转化
首先用01表示灯亮与灭，然后用类似前缀和的方式维护一个前缀的差分\(cf[i]=a[i]\;xor\;a[i-1]\)，注意i最大要到n+1
每次操作，相当于取反两个数，最终目的是让整个序列变成0
这就是
第一个转化：
对于给定的0 1数列，每次对于按要求的某两个数进行取反，问最少次可以使数列全部变为1.
想到分手那题，或者简单思考一下，可以发现每次操作一定至少有1个1，如果操作两个1，那么他们都变成0，如果操作一个1一个0，那相当于交换他们的位置，1最多16个且位置已知，于是有了
第二个转化
给你几个点，每次将其中一个点移动特定的距离，如果两个点碰到了一起，则两个点一起消失。
问如何移动使得消去所有的点的步数最少。
所以，跑最短路，我使用了某个死去的算法,这样得出消去任意两个1的最小步数，问题可以进一步转化
第三个转化
给你一堆物品，一次只能取出给定的一对物品，取出不同对的物品有不同的代价，问如何取出物品使得代价最小。
物品只有16个，状压即可
#include
#include
#include
#include
using namespace std;
int min(int x,int y){return xy?x:y;}
int flag[40005],cf[40005];
int n,k,m,op[67],x[19],cnt;
int dis[21][40005];
bool vis[40005];
queueq;
void spfa(int now,int nowx){
memset(vis,0,sizeof(vis));
q.push(nowx);dis[now][nowx]=0;
while(!q.empty()){
int y=q.front();q.pop();vis[y]=0;
for(int i=1;i<=m;++i)
{
int v=y+op[i],u=y-op[i];
if(v<=n+1){
if(dis[now][v]>dis[now][y]+1){
dis[now][v]=dis[now][y]+1;
if(!vis[v]){q.push(v);vis[v]=1;}
}
}
if(u>0){
if(dis[now][u]>dis[now][y]+1){
dis[now][u]=dis[now][y]+1;
if(!vis[u]){q.push(u);vis[u]=1;}
}
}
}
}
}
int f[67737];
void dp(){
memset(f,0x3f,sizeof(f));
f[(1<