一天两个小时踹了两回机箱还把我五道题题解踹没了，我不好说什么。
论坛数学版看到一道高消 dp 的题，第一反应是这是个马尔可夫链可以列矩阵求逆嗯解。我是不是魔怔了。
\[%>特别是当两者科技树点的都很歪而且歪的方向不同的时候。 ——H_Kaguya in 13.5 %你在影射什么我不好说。 \]k 大值
值域 \(2^{64}\)，每 \(2^{16}\) 扫一次统计在值域内的个数，扫四遍出答案。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int U=(1<<16)-1;
int n,k,cnt[1<<16];
ull ans,t;
ull nxt(ull x){
x^=(x<<13);
x^=(x>>17);
x^=(x<<5);
return x;
}
int main(){
scanf("%d%d%llu",&n,&k,&t);ull T=t;
for(int i=1;i<=n;i++){
ull x=t;t=nxt(t);
cnt[(x>>48)&U]++;
}
int sum=0;
for(int i=U;i>=0;i--){
if(sum<k&&sum+cnt[i]>=k){
ans|=(ull)i<<48;k-=sum;
break;
}
sum+=cnt[i];
}
memset(cnt,0,sizeof(cnt));
t=T;
for(int i=1;i<=n;i++){
ull x=t;t=nxt(t);
if((x>>48)==(ans>>48))cnt[(x>>32)&U]++;
}
sum=0;
for(int i=U;i>=0;i--){
if(sum<k&&sum+cnt[i]>=k){
ans|=(ull)i<<32;k-=sum;
break;
}
sum+=cnt[i];
}
memset(cnt,0,sizeof(cnt));
t=T;
for(int i=1;i<=n;i++){
ull x=t;t=nxt(t);
if((x>>32)==(ans>>32))cnt[(x>>16)&U]++;
}
sum=0;
for(int i=U;i>=0;i--){
if(sum<k&&sum+cnt[i]>=k){
ans|=(ull)i<<16;k-=sum;
break;
}
sum+=cnt[i];
}
memset(cnt,0,sizeof(cnt));
t=T;
for(int i=1;i<=n;i++){
ull x=t;t=nxt(t);
if((x>>16)==(ans>>16))cnt[x&U]++;
}
sum=0;
for(int i=U;i>=0;i--){
if(sum<k&&sum+cnt[i]>=k){
ans|=(ull)i;k-=sum;
break;
}
sum+=cnt[i];
}
printf("%llu\n",ans);
return 0;
}
染色
超级原题 AGC004F。
函数
感觉最近数学直觉和数字敏感度真的很减退。直接开睡。
首先这题有个结论：\(f(a+2C)=f(a)+2C\)。
证明：考虑设 \(b=2f(a)-a+1,d=2f(b)-b+1\)，则 \(f(b)=f(a)+C,f(d)=f(a)+2C\)。于是 \(d=2f(a)+2C-2f(a)+a-1+1=a+2C\)。
于是只需确定在 \([0,2C)\) 内的函数值。
然后考虑 \(b=2f(a)-a+1\)，那么 \(a+b=2f(a)-1\)，即 \(a,b\) 奇偶性不同。若 \(a,b<2C\) 可以配对，则不管 \(f(a)\) 如何取值，一定有 \(a+b=2f(a)+1-2nC\)。设 \(a=2X,b=2Y+1\)，则容易得到
\[f(a)=X+Y+nC \]\[f(b)=X+Y-(n-1)C \]于是可以枚举 \(X,Y\) 统计每组的价值。现在考虑一对 \((x,y)\) 对一组的贡献：
- \(x,a\) 在同组，则 \(x=a+2kC\)，设 \(W=X+Y+2kC-y=X+Y+x-a-y\)，那么 \(|f(x)-y|=w+nC\)。
- \(x,b\) 在同组，则 \(x=b+2kC\)，设 \(W=-X-Y-2kC-C+y=-X-Y-x+b-C+y\)，则同样有 \(|f(x)-y|=w+nC\)。
只要找到一个 \(n\)。那么显然 \(-nC\) 一定要接近 \(w\) 的中位数，从而可以 \(O(nC)\) 地算出所有 \((X,Y)\) 的权值。然后现在就变成了选若干 \(X,Y\) 匹配，直接 KM 或者费用流即可。这题卡 SPFA，要原始对偶。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,C,ans,cost,S,T,h[1010];
struct node{
int x,y;
bool operator<(const node&s)const{
return x<s.x;
}
}A[10010];
vector<int>v[610];
struct gra{
int u,v,w,val,next;
int getval(){
return h[u]-h[v]+val;
}
}edge[200010];
int t=1,head[100010];
void Add(int u,int v,int w,int val){
edge[++t].v=v;edge[t].u=u;edge[t].w=w;edge[t].val=val;edge[t].next=head[u];head[u]=t;
}
void add(int u,int v,int w,int val){
Add(u,v,w,val);Add(v,u,0,-val);
}
int dis[1010],pre[1010],flow[1010];
bool vis[1010];
struct stu{
int x,w;
bool operator<(const stu&s)const{
return w>s.w;
}
};
priority_queue<stu>q;
bool dijkstra(int s,int t){
for(int i=0;i<=T;i++)dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=false,flow[i]=0;
q.push({s,0});
dis[s]=0;flow[s]=0x3f3f3f3f3f3f3f3f;
while(!q.empty()){
int x=q.top().x;q.pop();
if(!vis[x]){
vis[x]=true;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].w&&dis[edge[i].v]>dis[x]+edge[i].getval()){
dis[edge[i].v]=dis[x]+edge[i].getval();
flow[edge[i].v]=min(flow[x],edge[i].w);
pre[edge[i].v]=i;
q.push({edge[i].v,dis[edge[i].v]});
}
}
}
}
if(flow[t]==0)return false;
for(int x=t;x!=s;x=edge[pre[x]].u)edge[pre[x]].w-=flow[t],edge[pre[x]^1].w+=flow[t];
return true;
}
int val[10010];
int calc(int x){
int ans=0;
for(int i=1;i<=val[0];i++)ans+=abs(val[i]-x*C);
return ans;
}
signed main(){
scanf("%lld%lld",&n,&C);S=0,T=C<<1|1;
for(int i=1;i<=C;i++)add(S,i,1,0),add(C+i,T,1,0);
for(int i=1;i<=n;i++)scanf("%lld%lld",&A[i].x,&A[i].y),v[A[i].x%(C<<1)].push_back(i);
for(int x=0;x<C;x++){
for(int y=0;y<C;y++){
int a=x<<1,b=y<<1|1;val[0]=0;
for(int p:v[a])val[++val[0]]=x+y+A[p].x-a-A[p].y;
for(int p:v[b])val[++val[0]]=-x-y-A[p].x+b-C+A[p].y;
sort(val+1,val+val[0]+1);
int mid=(val[0]+1)>>1,ret=val[mid]/C;
int d=min({calc(ret-1),calc(ret),calc(ret+1)});
add(x+1,C+y+1,1,d);
}
}
memset(h,0x3f,sizeof(h));
h[S]=0;
for(int i=head[S];i;i=edge[i].next){
if(edge[i].w)h[edge[i].v]=min(h[edge[i].v],0ll);
}
for(int x=1;x<=(C<<1);x++){
for(int i=head[x];i;i=edge[i].next){
if(edge[i].w)h[edge[i].v]=min(h[edge[i].v],h[x]+edge[i].val);
}
}
if(h[T]==inf){
puts("0");return 0;
}
while(dijkstra(S,T)){
for(int i=0;i<=T;i++)h[i]+=dis[i];
ans+=flow[T];cost+=flow[T]*h[T];
}
printf("%lld\n",cost);
return 0;
}