9.1 CSP 模拟 32
After Hours - The Weeknd
Thought I almost died in my dream again (Baby, almost died)
Fightin' for my life, I couldn't breathe again
I'm fallin' into new (Oh, oh)
Without you goin' smooth (Fallin' in)
'Cause my heart belongs to you
I'll risk it all for you
I won't just leave
This time, I'll never leave
I wanna share babies
Protection, we won't need
Your body next to me
Is just a memory
I'm fallin' in too deep, oh
Without you, I can’t sleep
Insomnia relieve, oh
Talk to me, without you, I can't breathe
My darkest hours
Girl, I felt so alone inside of this crowded room
Different girls on the floor, distractin' my thoughts of you
I turned into the man I used to be, to be
Put myself to sleep
Just so I can get closer to you inside my dreams
Didn't wanna wake up 'less you were beside me
I just wanted to call you and say, and say
Oh, baby
Where are you now when I need you most?
I'd give it all just to hold you close
Sorry that I broke your heart, your heart
Never comin' through
I was running away from facin' reality
Wastin' all of my time on living my fantasies
Spendin' money to compensate, compensate
'Cause I want you, baby
I'll be livin' in Heaven when I'm inside of you
It was definitely a blessing, wakin' beside you
I'll never let you down again, again
Oh, baby
Where are you now when I need you most?
I'd give it all just to hold you close
Sorry that I broke your heart, your heart
I said, baby
I'll treat you better than I did before
I'll hold you down and not let you go
This time, I won't break your heart, your heart, yeah
I know it's all my fault
Made you put down your guard
I know I made you fall
I said you were wrong for me
I lied to you, I lied to you, I lied to you (To you)
Can't hide the truth, I stayed with her in spite of you
You did some things that you regret, still right for you
'Cause this house is not a home
Without my baby
Where are you now when I need you most?
I gave it all just to hold you close
Sorry that I broke your heart, your heart
And I said, baby
I'll treat you better than I did before
I'll hold you down and not let you go
This time, I won't break your heart, your heart, no
\(\text{happyguy round}\)
T1 鱿鱼
AtCoder-AGC012B Splatter Painting
注意到 \(d\) 很小，把操作按 \((u,d)\) 分组，每组只维护最后一次操作的颜色。
这样倒序枚举 \(d\)，转移形如 \((u,d)\) 对 \((v,d-1)\) 产生影响，影响是关于时间取 \(\max\)。
时间复杂度 \(O(nd)\)。
点击查看代码
int n,m,q;
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
pii OP[maxn][11];
pii ans[maxn];
int main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;++i){
u=read(),v=read();
add_edge(u,v);
}
q=read();
for(int i=1,u,d,c;i<=q;++i){
u=read(),d=read(),c=read();
OP[u][d]=make_pair(i,c);
ans[u]=make_pair(i,c);
}
for(int d=10;d>=1;--d){
for(int u=1;u<=n;++u){
if(!OP[u][d].fir) continue;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
OP[v][d-1]=max(OP[v][d-1],OP[u][d]);
ans[v]=max(ans[v],OP[u][d]);
}
}
}
for(int i=1;i<=n;++i) printf("%d\n",ans[i].sec);
return 0;
}
T2 球瓶
一个做法是随机三个向量 \(\vec{e_1}=(\lambda_1,0),\vec{e_2}=(\lambda_2,\lambda_2),\vec{e_3}=(0,\lambda_3)\)，构造出 \(\{\vec{e}\mid \vec{e}=a\vec{e_1}+b\vec{e_2}+c\vec{e_3},1\le a,b,c\le k\}\)，\(k\) 取 \(13\) 左右即可。
正确性考虑另外三个方向一定只能看到 \(k^2\) 级别的点，而最后一个方向可以看到 \(k^3\) 级别的点。
点击查看代码
vector<pii> V;
pii X,Y,Z;
int main(){
X=make_pair(rand(1,10000),0),Y=make_pair(rand(1,10000),0),Z=make_pair(0,rand(1,10000));
Y.sec=Y.fir;
for(int i=1;i<=13;++i){
for(int j=1;j<=13;++j){
for(int k=1;k<=13;++k){
V.push_back(make_pair(i*X.fir+j*Y.fir+k*Z.fir,i*X.sec+j*Y.sec+k*Z.sec));
}
}
}
printf("%ld\n",V.size());
for(pii v:V) printf("%d %d\n",v.fir,v.sec);
return 0;
}
T3 边数
原图是基环内向树。
容易发现连边都由 \(1\) 连出一定不劣，那么树的部分就是从叶子开始贪心连，设 \(f_u\) 为按照最优策略到 \(1\) \(u\) 的最短距离，这里要求 \(1\) 一定不能同环上节点增加边。
如果环上节点 \(u\) 满足 \(f_u<k\)，那么还可以覆盖一些其他的节点，差分处理之后转化成环上有一些节点已经被覆盖，用若干长度为 \(k\) 的区间覆盖整个环，求最小区间个数。
特判环长不大于 \(k\) 的情况，找到环上节点 \(u\) 使得以 \(u\) 为左端点覆盖一个区间，右端点恰好之前没有被覆盖。这样覆盖这个右端点的区间的左端点一定在 \(u\) 及以后，枚举这 \(O(k)\) 个可能的左端点，后续暴力 \(O\left(\dfrac{len}{k}\right)\) 求，具体可以预处理 \(nxt_u\) 表示在环上 \(u\) 及以后的第一个之前没有被覆盖的节点，暴力跳即可。
点击查看代码
int n,k;
struct edge{
int to,nxt;
bool type;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],e[cnt].type=true,head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],e[cnt].type=false,head[v]=cnt;
}
int pre[maxn],tmp;
vector<int> L;
bool mark[maxn];
int dfn[maxn],dfncnt,id[maxn];
void dfs_loop(int u,int last){
pre[u]=last;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(i==(last^1)) continue;
if(pre[v]){
if(!tmp) tmp=u;
}
else dfs_loop(v,i);
}
}
int dep[maxn],f[maxn],nxt[maxn];
int ans;
void dfs(int u,int d){
dep[u]=d,f[u]=(u==1)?0:k+1;
for(int i=head[u],v;i;i=e[i].nxt){
if(e[i].type) continue;
v=e[i].to;
if(mark[v]) continue;
dfs(v,d+1);
f[u]=min(f[u],f[v]+1);
}
if(d&&f[u]==k+1) f[u]=1,++ans;
}
int sum[maxn];
inline void add(int l,int r){
if(r<=dfncnt) ++sum[l],--sum[r+1];
else{
++sum[l],--sum[dfncnt+1];
++sum[1],--sum[r-dfncnt+1];
}
}
int main(){
n=read(),k=read();
cnt=1;
for(int i=1,u,v;i<=n;++i){
u=read(),v=read();
add_edge(u,v);
}
for(int i=1;i<=n;++i){
if(pre[i]) continue;
tmp=0;
dfs_loop(i,2*n+2);
L.clear();
for(int u=tmp;;){
mark[u]=true;
L.push_back(u);
for(int i=head[u],v;i;i=e[i].nxt){
if(!e[i].type) continue;
v=e[i].to;
u=v;
break;
}
if(u==tmp) break;
}
dfncnt=0;
for(int u:L) dfn[u]=++dfncnt;
for(int u:L) dfs(u,0);
for(int j=1;j<=dfncnt+1;++j) sum[j]=0;
for(int u:L){
if(f[u]!=k+1) add(dfn[u],dfn[u]+k-f[u]);
}
for(int j=1;j<=dfncnt;++j) sum[j]+=sum[j-1];
if(dfncnt<k){
bool chk=true;
for(int j=1;j<=dfncnt;++j){
if(!sum[j]) chk=false;
}
if(!chk) ++ans;
continue;
}
id[1]=-1;
for(int j=1;j<=dfncnt;++j){
if(!sum[j+k-1>dfncnt?j+k-1-dfncnt:j+k-1]){
for(int x=j,y=1;y<=dfncnt;++x,++y){
if(x>dfncnt) x=1;
id[y]=x;
}
break;
}
}
if(id[1]==-1) continue;
int last=-1;
for(int j=dfncnt;j>=1;--j){
if(!sum[id[j]]) last=j;
}
for(int j=dfncnt;j>=1;--j){
if(!sum[id[j]]) last=j;
nxt[j]=last;
}
int mn=0x3f3f3f3f;
for(int j=1;j<=k;++j){
int x=j,y=1,now=0;
bool vis=false;
while(1){
++now;
x+=k,y+=k;
if(x>dfncnt) x-=dfncnt;
if(x<=nxt[x]) y+=nxt[x]-x;
else y+=(dfncnt-x)+nxt[x];
x=nxt[x];
if(y>dfncnt) break;
}
mn=min(mn,now);
}
ans+=mn;
}
printf("%d\n",ans);
}
T4 假人
暴力 DP 是容易的。
结论是多重集 \(S\) 满足值域 \([0,4]\) 且元素和 \(24\)，一定可以拆成两个元素和为 \(12\) 的子集。
那么 DP 过程中 \(f_{i,j+12}-f_{i,j}\ge f_{i,j+24}-f_{i,j+12}\)，即一定可以先加入的贡献更大的部分，在模 \(k=12\) 的意义下转移具有凸性，可以分治再闵可夫斯基和转移，分治过程 \(O(k^2)\) 枚举左右区间模 \(k\) 的值，转移是 \(O\left(\dfrac{n}{k}\right)\)，总复杂度是 \(O(kn\log n)\)。
点击查看代码
int n;
int a[maxn][6],sumk[maxn];
vector<ll> Minkowski(vector<ll> f,vector<ll> g){
vector<ll> a,b,h;
for(int i=1;i<f.size();++i) a.push_back(f[i]-f[i-1]);
for(int i=1;i<g.size();++i) b.push_back(g[i]-g[i-1]);
h.resize(f.size()+g.size()-1);
merge(a.begin(),a.end(),b.begin(),b.end(),h.begin()+1,greater<ll>());
h[0]=f[0]+g[0];
for(int i=1;i<h.size();++i) h[i]+=h[i-1];
return h;
}
#define mid ((l+r)>>1)
vector<vector<ll>> solve(int l,int r){
vector<vector<ll>> res;
res.resize(12);
if(l==r){
for(int i=0;i<a[l][5];++i) res[i].push_back(a[l][i]);
return res;
}
vector<vector<ll>> f,g;
vector<ll> h;
f=solve(l,mid),g=solve(mid+1,r);
for(int i=0;i<12;++i) res[i].resize((sumk[r]-sumk[l-1])/12+(i<=((sumk[r]-sumk[l-1])%12)));
for(int i=0;i<12;++i){
for(int j=0;j<12;++j){
if(!f[i].size()||!g[j].size()) continue;
h=Minkowski(f[i],g[j]);
if(i+j<12){
for(int k=0;k<h.size();++k){
res[(i+j)%12][k]=max(res[(i+j)%12][k],h[k]);
}
}
else{
for(int k=0;k<h.size();++k){
res[(i+j)%12][k+1]=max(res[(i+j)%12][k+1],h[k]);
}
}
}
}
return res;
}
#undef mid
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i][5]=read();
sumk[i]=sumk[i-1]+a[i][5]-1;
for(int j=0;j<a[i][5];++j){
a[i][j]=read();
}
}
vector<vector<ll>> ans=solve(1,n);
for(int i=0;i<=sumk[n];++i){
printf("%lld ",ans[i%12][i/12]);
}
printf("\n");
return 0;
}