0604
CF1566F
数轴，
思考
初始情况下内部含有点的线段都没用了，因此所有的线段现在与初始点无交。
如果线段 A 包含线段 B，那么 A 是无用的。
如果两个点的行动轨迹出现了交叉那么一定不优。因此每个点的移动范围就是包含它初始位置的一小段区间。
一个点要么向左挪动要么向右挪动。假设最终的移动范围区间是
尝试依次枚举每个点先向左还是先向右。失败
考虑到两个点区间之间的空隙不会产生贡献，相当于被 "节省" 了。猜测可以先贪心选择空隙最大的部分。发现可以进一步调整，失败。
题解
尝试枚举每个点的方向进行 DP 实则是可行的。
会觉得
更好的办法是拆开计算。
转移时我们枚举一个
能这样做是因为，
别急着丢掉一个 DP
int n,m;
LL a[MAXN];
class Range{
public:
LL l,r;
bool operator < (const Range& x)const{
if(r==x.r) return l>x.l;
return r>x.r;
}
};
vector<Range> ls[MAXN];
void solve(bool SPE){
n=RIN,m=RIN;
foru(i,1,n){
a[i]=RIN;
}
sort(a+1,a+1+n);
foru(i,0,n){
ls[i].clear();
}
static set<pair<LL,int>> st;
st.clear();
st+=mkp(LLONG_MIN,0);
st+=mkp(LLONG_MAX,n+1);
foru(i,1,n){
st+=mkp(a[i],i);
}
foru(i,1,m){
int l=RIN,r=RIN;
auto it=st.lower_bound(mkp(l,0));
if(it->fi<=r){
//useless segment
continue;
}
ls[prev(it)->se]+=Range{l,r};
}
static LL f[MAXN][2];
foru(i,0,n+1){
f[i][0]=f[i][1]=0;
}
// init f[1];
{
int L=a[1];
for(auto [l,r]:ls[0]){
chkmin(L,r);
}
f[1][0]=2*(a[1]-L);
f[1][1]=(a[1]-L);
}
foru(i,2,n){
//enum segments between i-1 and i
sort(All(ls[i-1]));
f[i][0]=f[i][1]=LLONG_MAX;
static vector<LL> pre;
pre.clear();
pre.resize(ls[i-1].size()+1,a[i-1]);
for(int j=ls[i-1].size()-1;j>=0;j--){
pre[j]=max(pre[j+1],(LL)ls[i-1][j].l);
}
size_t ptr=0;
for(size_t j=0;j<ls[i-1].size();j++){
LL L=ls[i-1][j].r;
LL R=a[i-1];
while(ptr<ls[i-1].size() && ls[i-1][ptr].r==L) ptr++;
// for(size_t k=j+1;k<ls[i-1].size();k++){
// if(ls[i-1][k].r!=L){
// chkmax(R,ls[i-1][k].l);
// // chkmax(R,pre[k]);
// // break;
// }
// }
chkmax(R,pre[ptr]);
LL v0=f[i-1][0]+(R-a[i-1]);
LL v1=f[i-1][1]+(R-a[i-1])*2;
chkmin(f[i][0],min(v0,v1)+(a[i]-L)*2);
chkmin(f[i][1],min(v0,v1)+(a[i]-L));
}
LL v0=f[i-1][0]+(pre[0]-a[i-1]);
LL v1=f[i-1][1]+(pre[0]-a[i-1])*2;
chkmin(f[i][0],min(v0,v1));
chkmin(f[i][1],min(v0,v1));
}
LL ans=LLONG_MAX;
LL R=a[n];
for(auto [l,r]:ls[n]){
chkmax(R,l);
}
ans=min(f[n][0]+(R-a[n]),f[n][1]+(R-a[n])*2);
cout<<ans<<'\n';
// exit(0);
return ;
}P8179
有
使用第
滴叉需要进入维修站来更换轮胎，所消耗的时间为
为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每圈的时间之和加上进站所花费的时间。
转移里的平方和公式很烦
拆开肯定会有
继续找性质？
题解
应该从
考虑
因此可以直接把
但此时发现无法贪心，因为轮胎的开销不是单调递增的了。
但每个轮胎除第一圈以外的部分依然是单调递增的，且注意到
在非单调时，我们有 DP 做法，复杂度较高。在单调时，我们有贪心做法，复杂度较低。
尝试把二者拼起来。我们需要给轮胎划的使用分成两个阶段。第一阶段不单调，第二阶段单调。我们将在第一阶段使用 DP 决策，第二阶段使用贪心决策，最后枚举第一阶段使用的轮胎总数，把二者拼起来。
如果只关注单调性，我们甚至可以只把第一个轮胎分为第一阶段。
但分阶段会带来问题。
假设对于某个轮胎，我们把它的前
这种情况显然是非法的。我们希望这种情况能被自动地排除掉，希望对于每个非法情况，一定存在一个合法情况比这个非法情况更优。
我们尝试对于每个非法情况构造对应的更优合法情况。一个很无脑的做法是，把贪心部分选的轮胎往前推，补充到
如果我们的确在第一阶段选了第
考虑为什么无法分析二者优劣。本质上是因为
那么答案呼之欲出了，我们只需要排除掉这种情况即可。
即，我们希望贪心部分的开销全部比
发现这个题非常厉害地保证了
观察诡异的数据范围
int n,m,t;
class Item{
public:
LL a,b;
}a[505];
LL f[505][505*30];
LL calc(LL n){
return n*(n+1)*(2*n+1)/6ll;
}
void solve(bool SPE){
n=RIN,m=RIN,t=RIN;
foru(i,1,n){
a[i]={RIN,RIN};
}
int P=ceil(sqrt(t))+5;
f[0][0]=0;
foru(i,1,n*P){
f[0][i]=1e18;
}
// cerr<<a[2].a<<endl;
foru(i,1,n){
foru(j,1,n*P){
f[i][j]=f[i-1][j];
foru(k,1,min(j,P)){
if(f[i-1][j-k]==1e18) continue;
// cerr<<i<<' '<<j<<' '<<k<<endl;
// if(i==2 && j==4 && k==3){
// cerr<<' '<<a[2].a<<endl;
// }
chkmin(f[i][j],f[i-1][j-k]+t+a[i].a*k+a[i].b*calc(k-1));
}
}
}
// exit(0);
// cout<<f[2][4]-t<<endl;
// exit(0);
static priority_queue<pair<i128,int>,vector<pair<i128,int>>,greater<pair<i128,int>>> q;
static int cur[505];
foru(i,1,n){
cur[i]=P+1;
q.push(mkp(a[i].a+a[i].b*P*P,i));
}
static i128 g[MAXN];
g[0]=0;
foru(i,1,m){
g[i]=g[i-1];
auto [v,id]=q.top();
q.pop();
g[i]+=v;
cur[id]++;
q.push(mkp(a[id].a+(i128)a[id].b*(cur[id]-1)*(cur[id]-1),id));
}
// cout<<P<<endl;
i128 ans=i128(1e15)*i128(1e15);
foru(i,0,min(n*P,m)){
chkmin(ans,f[n][i]-t+g[m-i]);
}
cout<<ans;
return ;
}CF1592F1
给定一个
现在你可以矩阵实施以下操作：
- 使用一块钱，选定一个包含
(1,1) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。 - 使用两块钱，选定一个包含
(n,1) 的子矩阵，把矩阵中的元素全部反转。 - 使用四块钱，选定一个包含
(1,m) 的子矩阵，把矩阵中的元素全部反转。 - 使用三块钱，选定一个包含
(n,m) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
思考
23操作都是无用的，可以用1操作代替不劣
如果只有 1 操作，代价是确定性的，从右下角开始计算即可
考虑用 4 操作去替换 1 操作
只有一种情况可能被替换？
用一次 4？
并非，但答案差得并不多
可以用1个4替换4个1
可以用2个4替换7个1
不好操作
题解
刚才分析的 2个4 替换 7个1 实则分析有误。并且暴力代码写错了，如果写对的话应该可以注意到只会用一次 4。
对矩阵做一步神秘转化
首先，原矩阵变为全 0 等价于这个矩阵变为全 0。并且注意到这样变形之后，操作一变成了只反转
这样一来就变得非常简单了。注意到作两次操作四是不优的，因为
正常反转之后处理操作四即可。
如果一个过程难以刻画，尝试把他转化成更简单的过程，同时与原先等价
int n,m;
int a[505][505];
bitset<505> b[505];
void solve(bool SPE){
n=RIN,m=RIN;
foru(i,1,n){
foru(j,1,m){
a[i][j]=RCIN=='B';
}
}
foru(i,1,n){
foru(j,1,m){
a[i][j]^=a[i+1][j]^a[i][j+1]^a[i+1][j+1];
}
}
int ans=0;
foru(i,1,n){
foru(j,1,m){
ans+=a[i][j];
}
}
foru(i,1,n-1){
foru(j,1,m-1){
if(a[i][j] && a[n][j] && a[i][m] && a[n][m]){
ans--;
goto fd;
}
}
}
fd:
cout<<ans;
return ;
}CF1592F2
给定一个
现在你可以矩阵实施以下操作：
使用一块钱，选定一个包含
使用三块钱，选定一个包含
使用四块钱，选定一个包含
使用两块钱，选定一个包含
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
思考
这次 2 3 操作似乎还是来搞笑的，忽略他
有了刚才的构造，现在变成一块钱反转某个，或两块钱反转一个矩形的四角
这次不是只用一个四了。
如果把
Accept
对了，确实是一个二分图问题，连边后直接求最大匹配，讨论一下
int n,m;
int a[505][505];
bitset<505> b[505];
void solve(bool SPE){
n=RIN,m=RIN;
foru(i,1,n){
foru(j,1,m){
a[i][j]=RCIN=='B';
}
}
foru(i,1,n){
foru(j,1,m){
a[i][j]^=a[i+1][j]^a[i][j+1]^a[i+1][j+1];
}
}
static vector<int> e[505];
foru(i,1,n-1){
if(a[i][m]!=1) continue;
foru(j,1,m-1){
if(a[n][j]!=1) continue;
if(a[i][j]){
e[i]+=j;
}
}
}
int ver=0;
static int vis[505];
static int nto[505];
static int mto[505];
int cnt=0;
auto dfs=[&ver](auto dfs,int u)->bool{
for(auto v:e[u]){
if(vis[v]==ver) continue;
vis[v]=ver;
if(mto[v]==0 || dfs(dfs,mto[v])){
nto[u]=v;
mto[v]=u;
return true;
}
}
return false;
};
foru(i,1,n){
if(nto[i]!=0) continue;
ver++;
if(dfs(dfs,i)){
cnt++;
}
}
int ans=0;
foru(i,1,n){
foru(j,1,m){
ans+=a[i][j];
}
}
ans-=a[n][m];
ans-=cnt;
if((cnt&1)!=a[n][m]) ans++;
cout<<ans;
return ;
}P7390
你要帮 djy 造一棵树，满足以下条件：
-
由
n 个点组成。 -
定义一条边
保证存在这样的树。
对于
思考
感觉可能需要进行调整，来减少可能的策略连接方法
考虑一个一个加入点，当前的策略只与每个点的剩余度数有关，与连接方式无关。
如果有
所以可能大的尽量与大的连接是好的？
考虑排序后从大到小加入点，直接优先与还有度数的最大点连接，有无 hack？
还得考虑 1 度点。直接分两个序列双指针插入。
炸了，答案偏小。
题解
刚才的判断是对的，尽量让大的与大的连是完全没问题的，问题在于构造方式出现问题。原来那样构造，在当前联通块只剩下
因此在每个联通块尝试拓展时判断，如果这个联通块变成叶子了就不与下个非叶点连边，而是加入叶子的数据结构。
一开始的叶子是单调递减的，随着算法进行新增的叶子也是单调递减的，使用两个队列维护即可做到线性，避免使用优先队列。
int n;
class Node{
public:
int a,b;
}a[10000005],lf[10000005];
int rf[10000005];
int N,M;
unsigned seed;
unsigned rnd(unsigned x){
x^=x<<13;
x^=x>>17;
x^=x<<5;
return x;
}
int rad(int x,int y){
seed=rnd(seed);
return seed%(y-x+1)+x;
}
void init_data(){
cin>>seed;
for(int i=1;i<=n;i++)
a[i].a=1,a[i].b=rad(1,500000);
for(int i=1;i<=n-2;i++)
a[rad(1,n)].a++;
}
void solve(bool SPE){
int type=RIN;
n=RIN;
if(type==0){
foru(i,1,n){
a[i].a=RIN;
}
foru(i,1,n){
a[i].b=RIN;
}
}else{
init_data();
}
sort(a+1,a+1+n,[](const Node& x,const Node& y)->bool{
return x.b>y.b;
});
class LEAF{
public:
queue<int> q;
queue<int> qn;
void pushsrc(int x){
q.push(x);
}
void push(int x){
qn.push(x);
}
bool empty(){
return q.empty() && qn.empty();
}
int get(){
if(q.empty()) return qn.front();
if(qn.empty()) return q.front();
if(q.front()>qn.front()){
return q.front();
}else{
return qn.front();
}
}
void pop(){
if(q.empty()){
qn.pop();
return ;
}
if(qn.empty()){
q.pop();
return ;
}
if(q.front()>qn.front()){
q.pop();
}else{
qn.pop();
}
}
int size(){
return q.size()+qn.size();
}
}leaf;
foru(i,1,n){
if(a[i].a==1){
leaf.pushsrc(a[i].b);
// rf[++M]=a[i].b;
}else{
lf[++N]=a[i];
}
}
LL ans=0;
int l=1;
// int ptr=0;
foru(r,1,N){
// cerr<<"r "<<r<<endl;
auto check=[&]()->bool{
return l==r && lf[l].a==1;
};
auto us=[&]()->void{
lf[l].a--;
if(lf[l].a==0) l++;
};
while(!check() && !leaf.empty() && (r==N || leaf.get()>lf[r+1].b)){
// cerr<<lf[l].b<<' '<<leaf.get()<<endl;
ans+=(LL)lf[l].b*leaf.get();
leaf.pop();
us();
}
if(r==N){
ast(check());
}
if(!check()){
// cerr<<lf[l].b<<'~'<<lf[r+1].b<<endl;
ans+=(LL)lf[l].b*lf[r+1].b;
us();
lf[r+1].a--;
}else{
leaf.push(lf[l].b);
l=r+1;
}
}
ast(leaf.size()==2);
LL V=leaf.get();
leaf.pop();
ans+=leaf.get()*V;
// foru(i,1,n){
// cerr<<a[i].a<<' '<<a[i].b<<endl;
// }
cout<<ans;
return ;
}CF1870E
给你一个序列
思考
能否直接 DP。
下标同时与
有用的区间并不多？对于每个 mex 的"极紧"区间是有限的
有效区间数量应该是
直接做一下看看
去掉所有被支配的区间
Accept
去掉就过了。
形式化地，一个区间
可以证明，这样的区间个数为
令每个有效区间在较大的端点一侧被统计。显然一个有效区间的端点不可能相等，除了
考虑以
以
int n;
int a[5005];
int fa[5005],sz[5005];
int find(int x){
// cerr<<x<<' '<<fa[x]endl;
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Union(int x,int y){
x=find(x),y=find(y);
if(x==y) return ;
fa[x]=y;
sz[y]+=sz[x];
}
void solve(bool SPE){
n=RIN;
foru(i,1,n){
a[i]=RIN;
}
static int mex[5005][5005];
foru(i,1,n){
foru(j,0,n+1){
fa[j]=j;
sz[j]=1;
}
for(int l=i;l>=1;l--){
Union(a[l],a[l]+1);
mex[l][i]=sz[find(0)]-1;
// cerr<<l<<' '<<i<<' '<<mex[l][i]<<endl;
}
}
static int lf[5005][5005];
foru(i,0,n){
foru(j,0,n){
lf[i][j]=0;
}
}
static bitset<9000> f[5005];
f[0].reset();
f[0][0]=1;
foru(i,1,n){
f[i]=f[i-1];
ford(l,i,1){
if(l<i && mex[l][i]==mex[l+1][i]) continue;
lf[i][mex[l][i]]=l;
if(lf[i-1][mex[l][i]]==l) continue;
// cerr<<' '<<l<<' '<<i<<' '<<mex[l][i]<<endl;
for(int j=f[l-1]._Find_first();j<=8192;j=f[l-1]._Find_next(j)){
// cerr<<
f[i][j^mex[l][i]]=1;
}
}
}
int ans=0;
foru(i,0,8192){
if(f[n][i]){
ans=i;
}
}
cout<<ans<<'\n';
return ;
}agc012_e
在数轴上有
骆驼希望访问所有这些绿洲。最初，他背上驼峰的容积为
骆驼可以通过步行或跳跃在数轴上移动：
- 步行距离为
d 需要从驼峰消耗体积为d 的水。无法进行导致存储水量为负的步行。 - 令
v 为当前存储的水量。当v\gt 0 时，骆驼可以跳到他选择的数轴上的任意点。此举之后，驼峰的容量变为v/2 (向下取整到最接近的整数)，存储的水量变为0 。
对于每个绿洲，确定是否可以从该绿洲出发访问所有绿洲。
-
2 \le N,V \le 2 \times 10^5 -
-10^9 \le x_1 \lt x_2 \lt ... \lt x_N \le 10^9 -
思考
对于当前所处的绿洲，肯定利用
跳跃后也会走完 "一个联通块"
注意到这些联通块构成了一个树形结构状物。每层拥有相同的
在高层（
最高层的每个块可以独立做。
每个询问于是形如，钦定最高层的一段必选，是否存在一个在下层每层选出一个联通块的方案，使得他们能拼出整个序列。
或许可以枚举最高层的段，用前后的答案拼起来。需要解决的是，对于一个前缀，在每层（除去最高层）选一个联通块，能否拼出整个前缀。
似乎不可行，不能保证前后层数无交。
削弱询问，考虑任意起点怎么做。
可以枚举最高层选哪个，然后转变为了一个子问题。
但这个子问题需要排除掉最高层选的这个范围。重新计算的复杂度应该是不可接受的，但前后拼接似乎也很困难。
前后拼接应该是不可行的，因为下面每层都会受到这次决策的影响？
考虑能否转化这个过程，例如合并，分裂层联通块。似乎不行。
题解
看似不能状压，恰恰相反，就得状压
觉得不能状压是因为试图做形如
然而这个 DP 蠢的没边了。这是个可行性 DP，考虑对于相同的
哪怕在类序列上状压 DP，也有可能只以集合作为下标
观察 DP 的信息，和我们使用的信息。如果使用的信息小，DP 的信息多，且 DP 的信息具有某种性质，可以压缩 DP，使得对于状态空间的划分更少。
对于此题，DP 维护了一大堆 0 1，但具有前缀
1 后缀0 的性质。因此只维护一个分界点，而不是维护所有 01 是正确的。
于是用脚做就行了。
CF1984F
两只饥饿的小熊猫奥斯卡和露拉，有一棵具有
- 从原始树
T 中选择任意节点V 。创建一棵以V 为根的新树T_2 。 - 从
T 中移除V ，使得原始树分裂成一个或多个子树（如果V 是T 中唯一的节点，则为零个子树）。 - 对每个子树使用相同的过程进行洗牌（再次选择任意节点作为根），然后将所有洗牌后的子树的根连接回
V ，完成构建T_2 。
之后，奥斯卡和露拉留下一棵新树
注意，叶子是所有度为
思考
提根很抽象。
提联通块的过程相当于，给连接点度数减一，再把新根度数加一。
要最大化度数为一的数量。
于是可以这样转化这个过程：
对于一个联通块
- 选一个初始点，把它的度数加一，把它周围的、联通块内的点的度数减一
- 对于每个裂出来的联通块，做相同算法
最后枚举一个全局的根，它的度数不加一，对他的每个子树都做上面的算法，最后就能得到每个点的度数，而不需要真的旋转树结构
这个过程是可打乱顺序来 DP 的。
考虑每一条边
换言之，对于每条边，我们只关心二者的相对操作早晚，据此就能知道
设
考虑如何转移，发现也是简单的。
Accept
过了，这思路对的不能再对了，满昏😋️
int n;
vector<int> e[MAXN];
void solve(bool SPE){
n=RIN;
foru(i,1,n){
e[i].clear();
}
foru(i,1,n-1){
int u=RIN,v=RIN;
e[u]+=v;
e[v]+=u;
}
static int f[MAXN][2];
static int fa[MAXN];
auto dfs=[](auto dfs,int u,int fath)->void {
fa[u]=fath;
for(auto v:e[u]){
if(v==fa[u]) continue;
dfs(dfs,v,u);
}
f[u][0]=1;
f[u][1]=0;
for(auto v:e[u]){
if(v==fa[u]) continue;
f[u][0]+=f[v][1];
f[u][1]+=max(f[v][0],f[v][1]);
}
chkmax(f[u][0],f[u][1]);
};
dfs(dfs,1,0);
int ans=0;
auto calc=[&ans](auto calc,int u,array<int,2> F)->void {
int sum=F[0];
for(auto v:e[u]){
if(v==fa[u]) continue;
sum+=f[v][0];
}
chkmax(ans,sum+((int)e[u].size()==1));
// if(u==3){
// cerr<<F[0]<<' '<<F[1]<<endl;
// }
array<int,2> g{1,0};
g[0]+=F[1];
g[1]+=max(F[0],F[1]);
for(auto v:e[u]){
if(v==fa[u]) continue;
g[0]+=f[v][1];
g[1]+=max(f[v][0],f[v][1]);
}
for(auto v:e[u]){
if(v==fa[u]) continue;
calc(calc,v,array<int,2>{max(g[0]-f[v][1],g[1]-max(f[v][0],f[v][1])),g[1]-max(f[v][0],f[v][1])});
}
};
// cerr<<f[2][1]<<endl;
calc(calc,1,array<int,2>{0,0});
cout<<ans<<'\n';
// exit(0);
return ;
}