当前位置：首页 > java >正文

GJOI 4.29 题解

java 2025/5/6 7:03:07

1.网络

题意

小明管理着一个 $n$ 个节点的网络，网络中的每个节点上有一台设备，每台设备初始状态均为“运行中”。小明每次操作可以改变相邻两台设备的状态（运行中变停机，停机变运行中）。他的目标是确保不存在两台相邻的设备同时处于“运行中”状态。请你帮助小明计算达到这一目标所需的最小操作次数。

$1\le n \le 10^5$ 。

思路

考场设状态抽风了，其实是不知道有一种套路。这种题一条边限制两个端点，有一个套路，就是分“父亲限制儿子”和“儿子限制父亲”两种状态。

设 $f_{u,0}$ 表示不变， $f_{u,1}$ 表示在 $u$ 处做关闭操作， $f_{u,2}$ 表示在儿子 $v$ 处做关闭操作。

容易证明，在一个对一个节点做了两次操作其实是不优的。反正目标都是关着，完全可以用其它边平替。

如果 $u$ 不关，那么只能从 $v$ 关掉且不关 $u$ 转移过来：
$f_{u,0}\leftarrow f_{v,1}$

如果 $u$ 作为儿子牵制父亲，根据刚刚的贪心结论，我们不能用 $u$ 来牵制 $v$ ，因此不能从 $f_{v,1}$ 转移过来。
$f_{u,2}\leftarrow \min(f_{v,0},f_{v,2})$

如果 $u$ 作为父亲，在 $u$ 处操作同时改变 $v$ ，那么就是从 $f_{u,2}$ 撤销过来：
$f_{u,1}=\min\{f_{u,2}+f_{v,2}-\min(f_{v,0},f_{v,1})\}$

其实都已经有了贪心策略了，那倒不如直接用贪心来写，每次如果（当前没有关的） $u$ 下面有没关的 $v$ ，就对 $(u, v)$ 操作，否则对 $u,fa_u)$ 操作。

dp 部分代码略。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n;
ll idx,head[N];
ll ans;
struct node
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
bool vis[N];
void dfs(ll u,ll fa)
{ll pos=0,cnt=0;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs(v,u);if(!vis[v])pos=v,cnt++;}if(cnt&&!vis[u]){vis[u]=1;if(!vis[fa])vis[fa]=1;else vis[pos]=1;ans++;}
}
int main()
{scanf("%lld",&n);for(int i=1;i<n;i++){ll u,v;scanf("%lld%lld",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,0);printf("%lld",ans);return 0;
}

2.CF196D The Next Good String

题意

给定长度为 $n$ 的小写字母串 $s$ 和正整数 $m$ 。

定义一个串是好的当且仅当他没有长度大于等于 $m$ 的回文子串。

请你求出长度为 $n$ 并且字典序比 $s$ 严格大的好串里，字典序最小的那个。没有就输出Impossible。

$1\le m\le n\le 4×10^5$ 。

思路

~~暴搜有 30pts 诶。~~

首先对回文串的判断，我们可以记正向和反向的哈希值 $h1_i$ 和 $h2_i$ ，每次查询区间 $l, r$ 是否为回文串只需要 $\Theta(1)$ 判断正反串是否相等即可。

我们考虑破坏那些长度 $\ge m$ 的回文串，但我们只需要考虑长度为 $m$ 或 $m + 1$ 的回文串，将它们破坏掉。因为长度为 $m + 2$ 的回文串里肯定包着一个长度为 $m$ 的回文串，还没遍历完一个长度为 $m + 2$ 的回文串，就已经会发现一个长度为 $m$ 的回文串将其改变了。

考虑先在尽可能靠前找一个长度为 $m$ 或 $m + 1$ 的回文串，在其末尾修改字符，强制把这个回文串破坏；因为修改的字符肯定比原来的字典序大，而修改后的字符串长度不变，因此在修改位置后面可以尽量填小的以满足题目要求。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const ll N=4e5+9;
ll m,n,base=131;
ull pw[N],h1[N],h2[N];
char s[N];
void init()
{pw[0]=1;for(int i=1;i<N;i++)pw[i]=pw[i-1]*base;
}
bool check(ll l,ll r)
{ull x=h1[r]-h1[l-1],y=(h2[r]-h2[l-1]*pw[r-l+1])*pw[l-1];return x==y;
}
int main()
{init();cin>>m>>s+1;n=strlen(s+1);ll fail=n;for(int i=1;i<=n;i++){h2[i]=h2[i-1]*base+(ll)s[i];h1[i]=h1[i-1]+(ll)s[i]*pw[i-1];if(i>=m&&check(i-m+1,i)||i>=m+1&&check(i-m,i)){fail=i;break;}//贪心地销毁前面会出现的，长度为 m,m+1 的回文串 }bool flag=0;for(int i=fail;i>=1;i--){for(char c=s[i]+1;c<='z';c++){s[i]=c;//强制破坏回文串h2[i]=h2[i-1]*base+(ll)s[i];h1[i]=h1[i-1]+(ll)s[i]*pw[i-1];if(i>=m&&check(i-m+1,i)||i>=m+1&&check(i-m,i))continue;//还有回文串，不能用cflag=1;//成功破坏，就用当前字符c就是最优的break;}if(flag){fail=i;break;}}if(!flag)//怎么改都有回文串{puts("Impossible");return 0;}for(int i=fail+1;i<=n;i++){for(char c='a';c<='z';c++){s[i]=c;//后面随便填，没有长度为m或m+1的回文串就好了h2[i]=h2[i-1]*base+(ll)s[i];h1[i]=h1[i-1]+(ll)s[i]*pw[i-1];if(i>=m&&check(i-m+1,i)||i>=m+1&&check(i-m,i))continue;break;}}for(int i=1;i<=n;i++)cout<<s[i];return 0;
}