Miriany and Matchstick
令 \(f_{i,0/1,j}\) 表示第 \(i\) 个数选 A 或 B 能否产生 \(j\) 的价值，枚举转移可以做到 \(O(n^2)\)。
可以发现 \(1\) 答案为 \(1\) 的 \(j\) 在分奇偶后都是一段区间，两个并起来会是一个中间最多一个空缺，证明可以看 CF1852D题解，可以维护每个 \(f_{i,0/1}\) 有值的 \(j\) 的范围。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10;
int n,k,a[N],b[N];
struct node{
int p,l,r;
bool check(int x)const{
return l<=x&&x<=r&&x!=p;
}
node change(int x)const{
return node{(p==-1?-1:p+x),l+x,r+x};
}
node operator +(const node &rhs)const{
int L=min(l,rhs.l),R=max(r,rhs.r);
if(L<=p&&p<=R&&!rhs.check(p)){
return node{p,L,R};
}
if(L<=rhs.p&&rhs.p<=R&&!check(rhs.p)){
return node{rhs.p,L,R};
}
if(r+2==rhs.l){
return node{r+1,L,R};
}
if(rhs.r+2==l){
return node{rhs.r+1,L,R};
}
return node{-1,L,R};
}
}f[N][2];
void solve(){
read(n),read(k);
for(int i=1;i<=n;i++){
char ch=getchar();
while(ch!='A'&&ch!='B'){
ch=getchar();
}
a[i]=ch-'A';
}
for(int i=1;i<n;i++){
if(a[i]!=a[i+1]){
k--;
}
}
if(k<0){
puts("NO");
return;
}
f[1][0]=node{-1,0,0};
f[1][1]=node{-1,1,1};
for(int i=2;i<=n;i++){
if(a[i-1]==a[i]){
f[i][0]=f[i-1][1].change(1)+f[i-1][0];
f[i][1]=f[i-1][0].change(2)+f[i-1][1].change(1);
}
else{
f[i][0]=f[i-1][0].change(1)+f[i-1][1];
f[i][1]=f[i-1][1].change(2)+f[i-1][0].change(1);
}
}
int type,p=k;
if(f[n][0].check(k)){
type=0;
}
else if(f[n][1].check(k)){
type=1;
}
else{
puts("NO");
return;
}
for(int i=n;i>1;i--){
b[i]=a[i]^type;
if(a[i-1]==a[i]){
if(!type){
if(f[i-1][1].check(p-1)){
p--;
type=1;
}
}
else{
if(f[i-1][0].check(p-2)){
p-=2;
type=0;
}
else{
p--;
}
}
}
else{
if(!type){
if(f[i-1][0].check(p-1)){
p--;
}
else{
type=1;
}
}
else{
if(f[i-1][1].check(p-2)){
p-=2;
}
else{
p--;
type=0;
}
}
}
}
b[1]=a[1]^type;
puts("YES");
for(int i=1;i<=n;i++){
if(b[i]){
putchar('B');
}
else{
putchar('A');
}
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
String Set Queries
很容易想到哈希，然后枚举每一个串是不是子串。但其实有很多串的枚举是没有必要的，因为集合中很可能没有那个长度的串，因此我们只枚举集合中存在的串的长度的子串。不同的子串长度最多有 \(\sqrt S\) 种，总复杂度 \(O(S\sqrt S)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int B=800,MOD=5e3+9,mod=1e9+7,N=3e5+10,base=131;
struct Hash_Table{
struct node{
int key,num;
};
vector<node>a[MOD];
void insert(int x){
int t=x%MOD;
for(int i=0;i<a[t].size();i++){
if(a[t][i].key==x){
++a[t][i].num;
return;
}
}
a[t].pb(node{x,1});
}
void erase(int x){
int t=x%MOD;
for(int i=0;i<a[t].size();i++){
if(a[t][i].key==x){
--a[t][i].num;
if(!a[t][i].num){
swap(a[t][i],a[t].back());
a[t].pop_back();
}
}
}
}
int count(int x){
int t=x%MOD;
for(int i=0;i<a[t].size();i++){
if(a[t][i].key==x){
return a[t][i].num;
}
}
return 0;
}
}HASH[B];
int n,tot,id[N],rid[N],mul[N],Hash[N];
string s;
void solve(){
mul[0]=1;
for(int i=1;i<N;i++){
mul[i]=mul[i-1]*base%mod;
}
read(n);
while(n--){
int opt;
read(opt);
cin>>s;
int len=s.size();
s=' '+s;
if(opt==1){
int hs=0;
for(int i=1;i<=len;i++){
hs=(hs*base%mod+s[i])%mod;
}
if(!id[len]){
id[len]=++tot;
rid[id[len]]=len;
}
HASH[id[len]].insert(hs);
}
else if(opt==2){
int hs=0;
for(int i=1;i<=len;i++){
hs=(hs*base%mod+s[i])%mod;
}
HASH[id[len]].erase(hs);
}
else{
for(int i=1;i<=len;i++){
Hash[i]=(Hash[i-1]*base%mod+s[i])%mod;
}
int ans=0;
for(int i=1;i<=tot;i++){
for(int j=rid[i];j<=len;j++){
ans+=HASH[i].count((Hash[j]-Hash[j-rid[i]]*mul[rid[i]]%mod+mod)%mod);
}
}
write_endl(ans);
fflush(stdout);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
括号
联考题。给定一个带有 ? 的括号串，? 可以替换为左右括号中的任意一个。对于一个合法括号串 \(s\)，令其长度为 \(len\)，贡献为 \(a\times len+b\)。求选出若干个不交的区间，使得每个区间都是合法括号串的最大贡献。
先考虑判断一个合法括号串的方法，先将所有的 ? 看成右括号，对于区间内的任意左端点都要满足将左括号看作 \(1\)，右括号看作 \(-1\)，后缀和均小于等于 \(0\)；反过来，将 ? 看成左括号，对于区间内的任意右端点都要满足将左括号看作 \(1\)，右括号看作 \(-1\)，前缀和均大于等于 \(0\)。可以得到合法的区间 \([l,r]\) 满足 \(r-l+1\) 是偶数，\(r<R_l,l> L_r\)，其中 \(R_l\) 表示以 \(l\) 为左端点，位置最小的不满足条件的右端点，\(L_r\) 表示以 \(r\) 为右端点，位置最大的不满足条件的左端点。
令 \(f_i\) 表示前 \(i\) 个数分为若干段的贡献最大值。可以得到转移 \(f_i=f_j+(i-j)\times a+b\)，其中 \([j+1,i]\) 为一个合法括号串。拆式子，\(f_i=f_j-j\times a+b+i\times a+b\)，\(i,j\) 奇偶性相同。令 \(g_i=f_{i-1}+(i-1)\times a\)，预处理出 \(l_i,r_i\)，用两棵的线段树维护奇偶性不同的 \(g\) 值，每次用奇偶性不同的线段树中 \([l_i+1,i]\) 区间中 \(g\) 的最大值转移，在奇偶性相同的线段树中删除 \(r_j=i\) 的 \(j\) 的权值。复杂度 \(O(n\log n)\)
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10,inf=1e18;
struct Seg_Tree{
int mx[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_up(int p){
mx[p]=max(mx[ls(p)],mx[rs(p)]);
}
void build(int p,int l,int r){
mx[p]=-inf;
if(l==r){
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
}
void update(int p,int l,int r,int pos,int val){
if(l==r){
mx[p]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
update(ls(p),l,mid,pos,val);
}
else{
update(rs(p),mid+1,r,pos,val);
}
push_up(p);
}
int query(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return mx[p];
}
int mid=(l+r)>>1,res=-inf;
if(q_l<=mid){
res=max(res,query(ls(p),l,mid,q_l,q_r));
}
if(q_r>mid){
res=max(res,query(rs(p),mid+1,r,q_l,q_r));
}
return res;
}
}tr[2];
int lst[N<<1],pos[N],n,a,b,f[N];
char s[N];
vector<int>del[N];
signed main(){
#ifdef luoshen
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#else
freopen("bracket.in","r",stdin);
freopen("bracket.out","w",stdout);
#endif
read(n),read(a),read(b);
for(int i=1;i<=n;i++){
s[i]=getchar();
while(s[i]!='('&&s[i]!=')'&&s[i]!='?'){
s[i]=getchar();
}
}
int num=0;
for(int i=1;i<=n;i++){
num+=(s[i]=='('?1:-1);
pos[i]=lst[num+n]+1;
lst[num+n+1]=i;
}
for(int i=0;i<=n*2+1;i++){
lst[i]=n+1;
}
num=0;
for(int i=n;i;i--){
num+=(s[i]==')'?-1:1);
del[lst[num+n+1]].pb(i);
lst[num+n]=i;
}
tr[0].build(1,1,n);
tr[1].build(1,1,n);
tr[1].update(1,1,n,1,0);
for(int i=1;i<=n;i++){
f[i]=f[i-1];
for(auto x:del[i]){
tr[x%2].update(1,1,n,x,-inf);
}
f[i]=max(f[i],tr[(i+1)%2].query(1,1,n,pos[i],i)+a*i+b);
tr[(i+1)%2].update(1,1,n,i+1,f[i]-i*a);
}
// for(int i=1;i<=n;i++){
// cerr<<f[i]<<' ';
// }
write_endl(f[n]);
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
Complete Mirror
不错的一道题。
通过条件可以发现如果满足条件的根有若干个深度为 \(i\) 的儿子且它们不是叶子，则一定都有深度为 \(i+1\) 的儿子。容易让人想到和直径终点有关，如果根不止一个深度为 \(1\) 的儿子，那一定是直径终点，但如果根只有一个深度为 \(1\) 的儿子，它的形状会类似一个链挂着一棵树。如果链的长度大于其它子树的深度，那么一定是直径端点，反之，从直径终点开搜，找到所有深度最浅的叶子，如果其中一个到直径中点的路径是链，可能可以为根，其它均为无解。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,rt,dep[N],f[N],deg[N];
vector<int>e[N];
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
f[u]=fa;
if(dep[u]>dep[rt]){
rt=u;
}
for(auto v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
}
}
bool flag=1;
int pos=0;
void query(int u,int Dep,int fa){
// f[u]=fa;
if(!deg[Dep]){
deg[Dep]=u;
}
else if(e[deg[Dep]].size()!=e[u].size()){
flag=0;
// if(e[deg[Dep]].size()==2){
// pos=deg[Dep];
// }
// else if(e[u].size()==2){
// pos=u;
// }
return;
}
for(auto v:e[u]){
if(v==fa){
continue;
}
query(v,Dep+1,u);
}
}
bool check(int x){
flag=1;
for(int i=0;i<=n;i++){
deg[i]=0;
}
query(x,0,0);
if(flag){
write_endl(x);
return 1;
}
return 0;
}
int mn=inf;
vector<int>num;
void find(int u,int fa){
f[u]=fa;
dep[u]=dep[fa]+1;
if(e[u].size()==1){
if(mn>dep[u]){
mn=dep[u];
num.clear();
num.pb(u);
}
else if(mn==dep[u]){
num.pb(u);
}
}
for(auto v:e[u]){
if(v==fa){
continue;
}
find(v,u);
}
}
void solve(){
read(n);
for(int i=1;i<n;i++){
int u,v;
read(u),read(v);
e[u].pb(v),e[v].pb(u);
}
dfs(1,0);
int rtt=rt;
rt=0;
dfs(rtt,0);
if(check(rt)||check(rtt)){
return;
}
// cerr<<dep[rt]<<endl;
int dis=dep[rt]/2;
for(int i=1;i<=dis;i++){
rt=f[rt];
}
if(check(rt)){
return;
}
find(rt,0);
for(auto x:num){
int y=f[x];
while(y!=rt){
if(e[y].size()!=2){
break;
}
y=f[y];
}
if(y==rt){
if(check(x)){
return;
}
break;
}
}
write_endl(-1);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
其它做法
看到这个条件，容易让人想到树同构，可以使用树哈希加换根，有兴趣的可以自己学习一下。
Alice and Recoloring 1
异或是可逆的，先将起始状态与终止状态交换。因为操作 \(2,3\) 均可以通过两次操作 \(1\) 得到，所以没有贡献。直接维护平面不是很好维护，考虑维护 \(a_{i,j}=c_{i,j}\oplus c_{i+1,j}\oplus c_{i,j+1}\oplus c_{i+1,j+1}\)，其中 \(c_{i,j}\) 表示格子 \((i,j)\) 是否为黑，最后所有点满足条件就转化为所有 \(a_{i,j}\) 等于 \(0\)，一次操作 \(1\) 可以翻转任意一个点 \(a_{i,j}\)；一次操作 \(4\) 可以翻转 \(a_{i,j},a_{i,m},a_{n,j},a_{n,m}\) 四个点，但因为代价为 \(3\)，\(a_{n,m}\) 翻转两次相当于没翻，等价于进行了 \(6\) 次操作 \(1\)。所以，最多进行 \(1\) 次操作 \(4\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=510;
int n,m,c[N][N],d[N][N];
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch=getchar();
while(ch!='W'&&ch!='B'){
ch=getchar();
}
c[i][j]=(ch=='W'?0:1);
}
}
int sum=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d[i][j]=(c[i][j]^c[i+1][j]^c[i][j+1]^c[i+1][j+1]);
sum+=d[i][j];
}
}
int ans=sum;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int num=d[i-1][m]+d[n][j-1]+d[i-1][j-1]+d[n][m];
ans=min(ans,sum-num*2+4+3);
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Alice and Recoloring 2
继续延续上面的推断，但是这里操作 \(4\) 代价为 \(2\)，当它翻转三个点的时候是一定会赚的，将其转为一个二分图模型。如果 \(a_{i,j}=a_{i,m}=a{n,j}=1(i<n,j<m)\) 时，从左侧第 \(i\) 个点向右侧第 \(j\) 个点连边，最后答案为 \(res-\) 最大匹配。其中 \(res\) 表示 \(a_{i,j}\) 为 \(1\) 的点的数量。注意特殊处理 \(a_{n,m}\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=510;
int n,m,c[N][N],a[N][N],vis[N],couple[N];
vector<int>e[N];
bool find(int u,int T){
if(vis[u]==T){
return 0;
}
vis[u]=T;
for(auto v:e[u]){
if(!couple[v]||find(couple[v],T)){
couple[v]=u;
return 1;
}
}
return 0;
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch=getchar();
while(ch!='W'&&ch!='B'){
ch=getchar();
}
c[i][j]=(ch=='W'?0:1);
}
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=c[i][j]^c[i+1][j]^c[i][j+1]^c[i+1][j+1];
cnt+=a[i][j];
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(a[i][j]&&a[i][m]&&a[n][j]){
e[i].pb(j);
}
}
}
int tot=0;
for(int i=1;i<=n;i++){
tot+=find(i,i);
}
cnt-=a[n][m];
write_endl(cnt-tot+(a[n][m]^(tot&1)));
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}