[AGC027E] ABBreviate
令 \(a\) 为 \(1\)，\(b\) 为 \(2\)，一次操作后，整个串的字符和模三的结果是不会改变的。令 \(P(a)\) 表示 \(a\) 的字符和模三的结果，并不是所有 \(P(a)=P(b)(b\text{为字符 a 或 b})\) 的 \(a\) 串都能成功变为 \(b\)，可以证明的是可以转变的条件是 \(a\) 串中存在两个相同字符。
证明：既然有相邻相同，肯定能操作一次，即能变成长度减小 1 的串，而且因为 \(sum(s)\) 是保证的，可以发现操作后不会变成没有相邻相同的串。
对于一个结果串 \(t\)，本质上来说是将 \(s\) 划分为 \(|t|\) 个子串，每个子串变为 \(t\) 中一个字符。贪心考虑将每次找到最小的前缀。这样变成了 \(|t|\) 个子串加上一个后缀 \(t'\)。如果该串合法，则需满足 \(P(t')=0\) 且 \(s\) 中有相邻字符相同。
先特判掉没有相邻字符相同的情况，答案为 \(1\)。
设出状态 \(f_i\) 表示将前缀 \(i\) 分段的方案数，\(p_{i,j}\) 表示 \([i,p_{i,j}]\) 是字符和模三为 \(j\) 的最小的位置。
转移 \(f_{i}\rightarrow f_{p_{i,1}},f_{i}\rightarrow f_{p_{i,2}}\)。
对于 \(P(t')=0\) 的后缀对应位置 \(p\)，\(f_p\rightarrow ans\)。
点击查看代码
#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,mod=1e9+7;
char s[N];
int n,p[N][3],f[N],a[N],mn[3];
void solve(){
scanf("%s",s+1);
n=strlen(s+1);
bool flag=1;
for(int i=1;i<n;i++){
if(s[i]==s[i+1]){
flag=0;
break;
}
}
if(flag){
write_endl(1);
return;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+(s[i]-'a'+1);
a[i]%=3;
}
mn[0]=mn[1]=mn[2]=n+1;
for(int i=n;i;i--){
mn[a[i]]=i;
p[i][1]=mn[(1+a[i-1])%3];
p[i][2]=mn[(2+a[i-1])%3];
}
f[0]=1;
int ans=0;
for(int i=0;i<=n;i++){
f[p[i+1][1]]=(f[p[i+1][1]]+f[i])%mod;
f[p[i+1][2]]=(f[p[i+1][2]]+f[i])%mod;
if(a[n]==a[i]&&i){
ans+=f[i];
ans%=mod;
}
}
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;
}
[CCO2020] Travelling Salesperson
模拟赛题，赛时写挂了没时间调，\(-100pts\)。
以一个颜色为标准色，可以得到一个分界点，如果当前分界点是结尾，可以直接将新的点连在后面。
对于分界点在开头的，可以直接将分界点放到结尾，将标准色改变即可，按照标准点在结尾的情况添加新点。
对于剩下情况，分类讨论：如果新点 \(x\) 与分界点 \(p\) 的边 \((p,x)\) 颜色为标准色，则断开分界点与其下一个点 \(nxt\) 的边 \((p,nxt)\)，连接 \((p,x),(x,nxt)\)。若 \((x,nxt)\) 为标准色，则分界点变为 \(nxt\)，反之变为 \(x\)。若 \((p,x)\) 的颜色不为标准色也类似，只不过考察的边是 \((pre,x)\)，其中 \(pre\) 表示 \(p\) 的前一个点。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll 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=2e3+10;
int n,c[N][N],pre[N],nxt[N],mid;
signed main(){
#ifdef luoshen
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#else
// freopen("hamil.in","r",stdin);
// freopen("hamil.out","w",stdout);
#endif
read(n);
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
char ch=getchar();
while(ch!='R'&&ch!='B'){
ch=getchar();
}
c[j][i]=c[i][j]=(ch=='B');
}
}
for(int i=1;i<=n;i++){
mid=i;
for(int i=1;i<=n;i++){
nxt[i]=pre[i]=0;
}
int opt=-1;
for(int j=1;j<=n;j++){
if(j==i){
continue;
}
if(opt==-1){
opt=c[i][j];
nxt[i]=j;
pre[j]=i;
mid=j;
continue;
}
if(!pre[mid]){
opt^=1;
while(nxt[mid]){
mid=nxt[mid];
}
}
if(!nxt[mid]){
nxt[mid]=j;
pre[j]=mid;
if(c[mid][j]==opt){
mid=j;
}
}
// cerr<<i<<' '<<j<<' '<<
else{
if(c[mid][j]==opt){
int Nxt=nxt[mid],now=mid;
nxt[now]=j;
pre[j]=now;
nxt[j]=Nxt;
pre[Nxt]=j;
if(c[Nxt][j]==opt){
mid=Nxt;
}
else{
mid=j;
}
}
else{
int Pre=pre[mid],now=mid;
nxt[Pre]=j;
pre[j]=Pre;
nxt[j]=mid;
pre[mid]=j;
if(c[Pre][j]==opt){
mid=j;
}
else{
mid=Pre;
}
}
}
}
write_endl(n);
int now=i;
while(now){
write_space(now);
now=nxt[now];
}
putchar('\n');
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
Short Code
将 trie 剪出来，容易发现将一个串变为前缀就是将串从对应点移动到其的任意一个祖宗，在 trie 上搜索时使用优先队列维护即可。
点击查看代码
#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,idx=1,ans=0;
namespace trie{
priority_queue<int>q[N];
struct node{
int ch[26],flag;
}tr[N];
void ins(string s){
int now=1;
for(int i=0;i<s.size();i++){
if(!tr[now].ch[s[i]-'a']){
tr[now].ch[s[i]-'a']=++idx;
}
now=tr[now].ch[s[i]-'a'];
}
tr[now].flag=1;
q[now].push(s.size());
ans+=s.size();
}
void dfs(int u,int d){
// cerr<<u<<' '<<d<<endl;
for(int i=0;i<26;i++){
int v=tr[u].ch[i];
if(!v){
continue;
}
dfs(v,d+1);
while(q[v].size()){
q[u].push(q[v].top());
q[v].pop();
}
}
if(u!=1&&!tr[u].flag){
// cerr<<u<<endl;
ans-=q[u].top()-d;
q[u].pop();
q[u].push(d);
}
}
}
string s[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
cin>>s[i];
trie::ins(s[i]);
}
// cerr<<ans<<endl;
trie::dfs(1,0);
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;
}
Serega and Fun
数据范围挺良心的，放根号过，就没必要写 \(n+1\) 棵平衡树去维护了。
分块，对于每个块维护两个东西：块内一个数的出现次数，以及用一个deque维护块内的数的顺序。维护很简单。
点击查看代码
#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,S=350;
int n,m,B,belong[N],buc[S][N],val[N],L[S],R[S],cnt;
deque<int>q[S];
int stk[N],top;
void update(int l,int r){
if(belong[l]==belong[r]){
int bel=belong[l];
l-=L[bel];
r-=L[bel];
stk[++top]=q[bel][r];
for(int i=l;i<r;i++){
stk[++top]=q[bel][i];
}
for(int i=r;i>=l;i--){
q[bel][i]=stk[top];
top--;
}
// cerr<<l<<' '<<r<<endl;
return;
}
int cnt1=R[belong[l]]-l+1,cnt2=r-L[belong[r]]+1;
top=0;
while(cnt1--){
int x=q[belong[l]].back();
q[belong[l]].pop_back();
stk[++top]=x;
buc[belong[l]][x]--;
}
stk[++top]=q[belong[r]][cnt2-1];
while(top>1){
int x=stk[top];
q[belong[l]].pb(x);
buc[belong[l]][x]++;
top--;
}
for(int i=belong[l]+1;i<=belong[r]-1;i++){
int x=stk[top];
q[i].push_front(x);
buc[i][x]++;
top--;
int y=q[i].back();
q[i].pop_back();
buc[i][y]--;
stk[++top]=y;
}
while(cnt2--){
int x=q[belong[r]].front();
q[belong[r]].pop_front();
stk[++top]=x;
buc[belong[r]][x]--;
}
top--;
while(top){
int x=stk[top];
q[belong[r]].push_front(x);
buc[belong[r]][x]++;
top--;
}
}
int query(int l,int r,int k){
if(belong[l]==belong[r]){
int bel=belong[l],ans=0;
l-=L[bel],r-=L[bel];
for(int i=l;i<=r;i++){
if(q[bel][i]==k){
ans++;
}
}
return ans;
}
int cnt1=R[belong[l]]-l+1,cnt2=r-L[belong[r]]+1,ans=0;
for(int i=q[belong[l]].size()-cnt1;i<q[belong[l]].size();i++){
if(q[belong[l]][i]==k){
ans++;
}
}
for(int i=0;i<cnt2;i++){
if(q[belong[r]][i]==k){
ans++;
}
}
for(int i=belong[l]+1;i<=belong[r]-1;i++){
ans+=buc[i][k];
}
return ans;
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(val[i]);
}
B=sqrt(n);
cnt=n/B;
for(int i=1;i<=n/B;i++){
L[i]=R[i-1]+1;
R[i]=i*B;
}
if(R[cnt]<n){
cnt++;
L[cnt]=R[cnt-1]+1;
R[cnt]=n;
}
for(int i=1;i<=n;i++){
belong[i]=(i-1)/B+1;
buc[belong[i]][val[i]]++;
q[belong[i]].pb(val[i]);
}
int lst_ans=0;
read(m);
while(m--){
// cerr<<m<<endl;
int opt,l,r,k;
read(opt),read(l),read(r);
l=(l+lst_ans-1)%n+1,r=(r+lst_ans-1)%n+1;
if(l>r){
swap(l,r);
}
if(opt==1){
// cerr<<l<<' '<<r<<endl;
update(l,r);
// for(int i=1;i<=cnt;i++){
// cerr<<q[i].size()<<' '<<L[i]<<' '<<R[i]<<endl;
// }
// cerr<<endl;
}
else{
read(k);
k=(k+lst_ans-1)%n+1;
lst_ans=query(l,r,k);
write_endl(lst_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;
}
Construct a tree
子树大小之和最小为 \(2\times n-1\)，最大为 \(\frac{n\times(n+1)}{2}\)，剩下的全部可以构造出来。
二分分支系数 \(k\)，对于一个分支系数 \(k\)，考虑如何构造。可以先构造一棵完全 \(k\) 叉树，再进行调整，为了防止调整时分支系数大于 \(k\)，可以先调整深度大的点，再调整深度小的点。
点击查看代码
#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 N=1e5+10;
int n,k,dep[N],cnt[N];
bool check(int x){
// cerr<<x<<endl;
memset(dep,0,sizeof(dep));
memset(cnt,0,sizeof(cnt));
int now=2,tot=1,num=k-1,d=1;
dep[1]=1;
while(now<=n){
tot*=x;
++d;
for(int j=1;j<=tot&&now<=n;j++){
cnt[d]++;
dep[now]=d;
num-=d;
now++;
}
}
if(num<0){
return 0;
}
now=n;
while(num){
++d;
if(cnt[dep[now]]==1){
now--;
}
int t=min(num,d-dep[now]);
cnt[dep[now]]--;
dep[now]+=t;
cnt[dep[now]]++;
num-=t;
now--;
}
return 1;
}
void solve(){
read(n),read(k);
if(k<n*2-1||k>n*(n+1)/2){
puts("No");
return;
}
puts("Yes");
int l=1,r=n,ans=n;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
check(ans);
int pos=1;
sort(dep+1,dep+n+1);
memset(cnt,0,sizeof(cnt));
for(int i=2;i<=n;i++){
while(dep[pos]!=dep[i]-1||cnt[pos]==ans){
pos++;
}
write_space(pos);
cnt[pos]++;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[GXOI/GZOI2019] 旅行者
在原图上跑一遍多源最短路，记录到每个点距离最近的关键点及其距离，再在反图上跑一遍，求出每个点距离最近的关键点及其距离。对于每条边，求出经过它的路径的距离最小值，需要注意的是有可能会出现一条边在一个环上，且这个环是经过这条边距离最小的的路径，需要去掉。
点击查看代码
#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=3e5+10,M=1e6+10,inf=1e18;
int n,m,k,u[M],v[M],w[M],head[N],tot=1,col[2][N],dis[2][N],a[N],vis[N];
struct edge{
int v,w,nxt;
}e[M];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void dij(int id){
for(int i=1;i<=n;i++){
dis[id][i]=inf;
vis[i]=0;
}
priority_queue<pii>q;
for(int i=1;i<=k;i++){
dis[id][a[i]]=0;
col[id][a[i]]=a[i];
q.push(mp(-dis[id][a[i]],a[i]));
}
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[id][v]>dis[id][u]+w){
dis[id][v]=dis[id][u]+w;
col[id][v]=col[id][u];
q.push(mp(-dis[id][v],v));
}
}
}
}
void solve(){
read(n),read(m),read(k);
for(int i=1;i<=m;i++){
read(u[i]),read(v[i]),read(w[i]);
if(u[i]!=v[i]){
add(u[i],v[i],w[i]);
}
}
for(int i=1;i<=k;i++){
read(a[i]);
}
dij(0);
for(int i=1;i<=n;i++){
head[i]=0;
}
tot=1;
for(int i=1;i<=m;i++){
if(u[i]!=v[i]){
add(v[i],u[i],w[i]);
}
}
dij(1);
int ans=inf;
for(int i=1;i<=m;i++){
if(col[0][u[i]]&&col[1][v[i]]&&col[0][u[i]]!=col[1][v[i]]){
ans=min(ans,dis[0][u[i]]+dis[1][v[i]]+w[i]);
}
}
write_endl(ans);
for(int i=1;i<=n;i++){
head[i]=0;
}
tot=1;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
0-1-Tree
要计数的路径是先一段 \(0\)，再一段 \(1\) 的路径，用并查集维护 \(x\) 所在的边权只有 \(0\) 的连通块和边权只有 \(1\) 的连通块。枚举分界点，设它所在的两个连通块大小分别为 \(a,b\)，起点的选法有 \(a\) 种，终点的选法有 \(b\) 种，贡献为 \(a\times b-1\)（要去掉起点终点相同的路径）。
点击查看代码
#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 N=2e5+10;
int n;
struct DSU{
int fa[N],siz[N];
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
}
int getfa(int x){
if(fa[x]!=x){
fa[x]=getfa(fa[x]);
}
return fa[x];
}
void merge(int u,int v){
u=getfa(u),v=getfa(v);
if(u!=v){
fa[v]=u;
siz[u]+=siz[v];
}
}
}dsu[2];
void solve(){
read(n);
dsu[0].init();
dsu[1].init();
for(int i=1;i<n;i++){
int u,v,w;
read(u),read(v),read(w);
dsu[w].merge(u,v);
}
int ans=0;
for(int i=1;i<=n;i++){
ans+=dsu[0].siz[dsu[0].getfa(i)]*dsu[1].siz[dsu[1].getfa(i)]-1;
}
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;
}