这次。。。。。。好像稍有起色？
不像前几次那么差了，但是还是不尽如人意
凭君莫话封侯事，一将功成万骨枯，也许是在暗示着什么吧
继续保持
简要说一下考试经历
上来肛T1，想岔了把前缀和相减想成了相加，复杂度平添一个log，得到了和暴力一样的好成绩
然后肛T2，很快发现是一个贪心，然而由于倍增打错以及剪枝剪错WA成了65分，鼓掌
然后发现只剩30分钟，想T3毫无起色，开始打特判，得到了16分的好成绩
总分60+65+16=141pts,rank10,emmm......还好吧
T1：入阵曲
60pts算法：n^4直接做，或者n^3logn的分治（，zkt的n^3??），没什么差别......没有
100pts算法：我们将思路从相加改为相减，那么如果我们固定了左右边，直接开一个桶从上扫到下就好了，复杂度O(n^3)
#include<bits/stdc++.h>
#define ll long long
#define re register
#define cri const register int
#define crs const register short
#define re register
#define db double
using namespace std;
int n,m,k,has[510];
short tong[2000010];
int sum[510][510];
inline int mo(cri x){
if(x==k) return 0;
return x;
}
ll solve(crs l,crs r){
re ll ans=0,x;
if(l==r){
for(int i=1;i<=m;i++)
for(int j=i;j<=m;j++)
if(!((sum[l][j]-sum[l-1][j]-sum[l][i-1]+sum[l-1][i-1]+k*2)%k)) ans++;
return ans;
}
short mid=l+r>>1;
ans=solve(l,mid)+solve(mid+1,r);
for(re short i=1;i<=m;i++)
for(re short j=i;j<=m;j++){
for(re short t=mid;t>=l;t--){
x=(sum[mid][j]-sum[mid][i-1]-sum[t-1][j]+sum[t-1][i-1]+k*2)%k;
tong[x]++;
has[t]=x;
}
for(re short t=mid+1;t<=r;t++){
x=(sum[t][j]-sum[t][i-1]-sum[mid][j]+sum[mid][i-1]+k*2)%k;
ans+=tong[mo(k-x)];
}
for(re short t=mid;t>=l;t--){
tong[has[t]]--;
}
}
//cout<<ans<<endl;
return ans;
}
signed main(){
scanf("%d%d%d",&n,&m,&k);
int x;ll ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&x),sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x+k)%k;
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++){
tong[0]=1;
for(int t=1;t<=n;t++){
x=(sum[t][j]-sum[t][i-1]+k)%k;
ans+=tong[x];tong[x]++;
}
for(int t=1;t<=n;t++){
x=(sum[t][j]-sum[t][i-1]+k)%k;
tong[x]--;
}
}
}
printf("%lld",ans);
}
T2：将军令
考试想了想dp感觉不可做（%%yxm），然后发现这就是个贪心
每次找到剩余深度最深的点，找到他的k层父亲然后暴力更新这个点周围k层就好了
复杂度O(kn)
#include<bits/stdc++.h>
#define ll long long
#define re register
#define cri const register int
#define re register
#define db double
#define mp make_pair
using namespace std;
int f[100010][8],dep[100010],v[100010];
int fa[100010],to[200010],la[200010],cnt,now,q[100010];
inline void add(cri x,cri y){
to[++cnt]=y;
la[cnt]=fa[x];
fa[x]=cnt;
}
void dfs(cri x,cri ff){
for(int i=1;(1<<i)<=dep[x]&&i<=7;i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=fa[x];i;i=la[i])
if(to[i]!=ff){
dep[to[i]]=dep[x]+1;
f[to[i]][0]=x;
dfs(to[i],x);
}
}
void dfss(cri x,cri k,cri ff,cri is){
if(is)v[x]=1;
else v[x]=2;
if(!k) return;
for(int i=fa[x];i;i=la[i])
if(to[i]!=ff&&v[to[i]]!=1){
if(x==now&&dep[to[i]]<dep[x]||!is)dfss(to[i],k-1,x,0);
else dfss(to[i],k-1,x,1);
}
}
inline bool as(cri x,cri y){
return dep[x]>dep[y];
}
signed main(){
int n,k,t,x,y,ans=0;
scanf("%d%d%d",&n,&k,&t);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
q[i]=i;
}
q[n]=n;
dep[1]=1;
dfs(1,0);
sort(q+1,q+n+1,as);
for(int j=1;j<=n;j++)
if(!v[q[j]]){
x=q[j];
t=k;ans++;
for(int i=5;i>=0;i--)
if((1<<i)<=t)x=f[x][i],t-=(1<<i);
if(!x) break;
now=x;
dfss(x,k,0,1);
}
printf("%d",ans);
}
T3:星空
最近T3日常神仙啊......
24分我们可以直接状压，但是我们发现根本没用到k很小这个条件
这启发我们把用n状压改变成用k状压，需要经历下面几次题意转换
F，我们直接最暴力地暴力翻转一段区间是O(n)的，考虑优化，区间修改转单点修改，emmm，差分啊
我们设g[i]=a[i]^a[i+1]，那么每次修改[l,r]这个区间就变成了让g[l-1],g[r]取反
显然我们每次都要对1（表示数不同）进行操作，考虑以下两种情况
1，改变一个1和一个0,可以看成一个1转移了位置
2，改变两个1,可以看成一个移动到另一个的位置然后都变成0
这样我们就把原来的操作转换成了移动
S，原题转换成了：让原序列上的1进行移动，遇到1可以一起消除，问最小移动距离和
等等，最小距离？边权为1？bfs不就好了嘛，bfs预处理出每两个1之间的最短路就好了，复杂度O(nmk)
然后我们继续转换题意
T，有2k个物品，每次选两个消去，消去操作有花费，问最小花费
k很小，简单的状压dp就好了，复杂度O(k*22k)
等等，枚举两个点不是k^2的吗？为什么复杂度是O(k*22k)?
显然，我们发现每个点最终都要删去，那么我们在枚举点对的时候直接选一个点固定下来，枚举另一个点就好了
总复杂度O(nmk+k*22k)
#include<bits/stdc++.h>
#define ll long long
#define re register
#define cri const register int
#define re register
#define db double
using namespace std;
int n,k,m,b[100];
bool a[40010],g[40010];
int dis[20][40010],v[40010],is[20],len[20][20],f[700010],h[70010];
inline void spfa(cri x,cri num){
queue<int>q;
v[x]=num;
q.push(x);dis[num][x]=0;
while(!q.empty()){
cri u=q.front();q.pop();
for(int i=1;i<=m;i++){
if(u+b[i]<=n&&v[u+b[i]]!=num){
dis[num][u+b[i]]=dis[num][u]+1;
v[u+b[i]]=num;
if(!g[u+b[i]])q.push(u+b[i]);
}
if(u-b[i]>=0&&v[u-b[i]]!=num){
dis[num][u-b[i]]=dis[num][u]+1;
v[u-b[i]]=num;
if(!g[u-b[i]]) q.push(u-b[i]);
}
}
}
}
signed main(){
int x,num=0;
memset(dis,0x3f,sizeof dis);
scanf("%d%d%d",&n,&k,&m);
memset(a,1,sizeof a);
for(int i=1;i<=k;i++) scanf("%d",&x),a[x]=0;
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
for(int i=0;i<=n;i++)
g[i]=a[i]^a[i+1];
for(int i=0;i<=n;i++)
if(g[i]) is[++num]=i,spfa(i,num);
for(int i=1;i<=num;i++){
h[1<<(i-1)]=i;
for(int j=1;j<=num;j++)
len[i][j]=dis[i][is[j]];
}
memset(f,0x3f,sizeof f);
f[(1<<num)-1]=0;
for(int i=(1<<num)-1;i>=1;i--){
x=h[i&-i];
for(int j=1;j<=num;j++)
if(((i>>(j-1))&1)&&j!=x)
f[i^(1<<(j-1))^(1<<(x-1))]=min(f[i^(1<<(j-1))^(1<<(x-1))],f[i]+len[x][j]);
}
printf("%d",f[0]);
return 0;
}