2018.8.6 正睿暑期集训营 Day3
时间：5h(实际)
期望得分：...
实际得分：...
rating-93 _(:зゝ∠)_
A *(DP)
贪心不对啊，根本不知道该以什么策略。。
最优情况下*应是最后用，此时所有元素都应在1~x内。
f[i][j]表示前i个元素全部变到1~j内（每个整数）的最小花费。则f[i][j]=min(f[i-1][j-1],f[i-1][j])+cost(i->j)。初始时除0全为INF，因为新的j只能从j-1转移。
注意除1外显然不能从0转移。
略错的思路（答案应该一样）：
DP，f[i][j]表示当前i个，构成阶梯长为j。
我们还要知道用哪些数构成了阶梯。假设用i放到j的话，那么前i-1个要么也构成了阶梯，要么被减到和i一样。
那么就有两种转移：f[i][j]=min(f[i-1][j-1],f[i-1][j])+cost(i->j)。（不管怎样i都是要削成j的）
在枚举所有i时更新答案就可以了。之前预处理后缀和。
事实上只在最后更新答案就可以，原因见上。。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=5005;
int n,A[N];
LL P,Q,R,f[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
n=read(); LL ans=0;
for(int i=1; i<=n; ++i) ans+=(A[i]=read());
std::sort(A+1,A+1+n);
P=read(), Q=read(), R=read(), ans*=Q;
f[0]=0;
// for(int i=1; i<=n; ++i) f[i]=1e15;
for(int i=1; i<=n; ++i)
{
LL ai=A[i];
f[i]=f[i-1]+(ai>i?Q*(ai-i):P*(i-ai)), f[0]=1e15;//一维得特判一下f[i]。。
for(int j=i-1; j; --j)
f[j]=std::min(f[j-1],f[j])+(ai>j?Q*(ai-j):P*(j-ai));
}
for(int i=1; i<=n; ++i)
ans=std::min(ans,f[i]+R);
printf("%lld\n",ans);
return 0;
}
B 绕口令(KMP)
一个环删掉一段，剩下的一段也是连续的。它当中不含有相邻的相同字符。如果原串中存在相邻的相同字符，则在这里把环切开，最后会把环切若干段，合法的剩下的段显然是某一段的一部分。
然后判断在合法的段中是否有长\(x\)的合法长度（若存在，则删\(n-x\)个是可以的），即长\(x\)首尾字母不同的段。而再删一段后首尾字母相同就是一段前后缀相同。
判断前后缀是否相同可以直接用KMP/Hash。如果有长为\(l\)的相同前后缀长度，则\(n-l+1\)位置是非法的。拆环为链每次只删后缀就是正确的了。
如果不存在相邻的相同字符，把整个串求一遍就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=2e6+5;
bool ok[N];
char s[N],t[N];
void Calc(int l)
{
static int fail[N];
static bool ban[N];
// fail[0]=fail[1]=0;
for(int i=1,j=0; i<l; ++i)
{
while(j && t[j]!=t[i]) j=fail[j];
fail[i+1]=t[i]==t[j]?++j:0;
}
for(int i=fail[l]; i; i=fail[i]) ban[l-i+1]=1;
for(int i=1; i<=l; ++i) if(!ban[i]) ok[i]=1;
for(int i=fail[l]; i; i=fail[i]) ban[l-i+1]=0;
}
void Solve()
{
int n=strlen(s+1),cnt=0,len=n<<1;
for(int i=1; i<=n; ++i) s[i+n]=s[i];
for(int i=1; i<len; ++i)
{
t[cnt++]=s[i];
if(s[i]==s[i+1]) Calc(cnt), cnt=0;
}
if(cnt) Calc(cnt);
for(int i=0; i<n; ++i) putchar(ok[n-i]+'0');//, ok[n-i]=0;//清空不完a!!
for(int i=1; i<len; ++i) ok[i]=0;
putchar('\n');
}
int main()
{
int Cs=1;
while(~scanf("%s",s+1))
printf("Case %d:",Cs++), Solve();
return 0;
}
C 最远点(LCT)
动态维护森林中每个点距最远点的距离及其所在树的直径，支持增加、删除边。
LCT，维护每个点到其子树内的最远距离及次远距离。因为树的形态一直在变，用set/heap维护每个点其所有虚子树的 最长延伸距离(hp1)和答案(hp2)。
单独维护每个点左右两棵实子树的最长距离。
因为LCT的Splay形态是中序遍历的序列，即每个点x与其左右儿子不一定是连续的，所以要用x的左子树中与最右点(最深点，即一定与x相邻)相连的最长距离rdis[lson]。
ldis同理。因为一个点可能一会是左儿子一会是右儿子，所以ldis[lson]也顺便维护。
ldis[x]可以由 左子树中的某条链ldis[lson] 或是 左子树整个与x相连的这条实链+右子树或虚子树中的一条链 更新。
距离更新可能不太方便，直接维护路径上的点数，初始都为1，最后输出-1。
其中 x子树整个与fa[x]相连的实链的长度len[x] 可以直接由 len[lson]+len[rson]+1 更新。
x到最远点的距离mxdis[x]由 max{rdis[lson],ldis[rson],虚子树最大值hp1.top()}(+1)更新。
过x的最长链 = max{rdis[lson]+ldis[rson]+1, 虚子树最长链+左/右子树最长链/虚子树次长链+1}，但是ans要算上左右子树、虚子树的ans（再取max）（要整个连通块答案）。
注意hp1[x]中的最长链是要与x相连的，即如果用lson/rson更新则是ldis[rson]/rdis[lson]，用直接与其相连的点x更新则是mxdis[x]（Access与Link）。
说的比较乱。。尽量在解释清楚了。画画图就能看出来。
//2395ms 31672kb
#include <queue>
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=1e5+5;
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace LCT
{
#define lson son[x][0]
#define rson son[x][1]
int sk[N],fa[N],son[N][2],mxdis[N],ldis[N],rdis[N],len[N],ans[N];
bool rev[N];
struct Heap
{
std::priority_queue<int> h,d;
inline void Delete(int x) {d.push(x);}
inline void Insert(int x) {h.push(x);}
inline void Fix() {while(!h.empty()&&!d.empty()&&h.top()==d.top()) h.pop(),d.pop();}
inline int Top() {Fix(); return h.empty()?0:h.top();}
inline int Sec()
{
Fix(); if(h.empty()) return 0;
int tmp=h.top(); h.pop();
int ans=Top(); h.push(tmp);
return ans;
}
}hp1[N],hp2[N];
inline void Init(int n){
for(int i=1; i<=n; ++i) len[i]=ldis[i]=rdis[i]=ans[i]=1;
}
inline void Rev(int x){
rev[x]^=1, std::swap(lson,rson), std::swap(ldis[x],rdis[x]);
}
inline void PushDown(int x){
if(rev[x]) Rev(lson), Rev(rson), rev[x]^=1;
}
inline bool n_root(int x){
return son[fa[x]][0]==x||son[fa[x]][1]==x;
}
void Update(int x)
{
int ls=lson, rs=rson, vmx=hp1[x].Top();
len[x]=len[ls]+len[rs]+1;
ldis[x]=std::max(ldis[ls],len[ls]+std::max(ldis[rs],vmx)+1);
rdis[x]=std::max(rdis[rs],len[rs]+std::max(rdis[ls],vmx)+1);
mxdis[x]=std::max(vmx,std::max(rdis[ls],ldis[rs]))+1;
ans[x]=std::max(std::max(hp2[x].Top(),std::max(ans[ls],ans[rs])),std::max(rdis[ls]+ldis[rs]+1,vmx+1+std::max(hp1[x].Sec(),std::max(rdis[ls],ldis[rs]))));
}
void Rotate(int x)
{
int a=fa[x],b=fa[a],l=son[a][1]==x,r=l^1;
if(n_root(a)) son[b][son[b][1]==a]=x;
if(son[x][r]) fa[son[x][r]]=a;
fa[a]=x, fa[x]=b, son[a][l]=son[x][r], son[x][r]=a;
Update(a);
}
void Splay(int x)
{
int t=1,a=x; sk[1]=x;
while(n_root(a)) sk[++t]=a=fa[a];
while(t) PushDown(sk[t--]);
while(n_root(x))
{
if(n_root(a=fa[x])) Rotate(son[a][0]==x^son[fa[a]][0]==a?x:a);
Rotate(x);
}
Update(x);
}
void Access(int x)
{
for(int pre=0; x; x=fa[pre=x])
{
Splay(x);
hp1[x].Insert(ldis[rson]), hp2[x].Insert(ans[rson]);
hp1[x].Delete(ldis[pre]), hp2[x].Delete(ans[pre]);
rson=pre, Update(x);
}
}
void Make_root(int x){
Access(x), Splay(x), Rev(x);
}
void Link(int x,int y)
{
Make_root(x), Access(y), Splay(y);
fa[x]=y, hp1[y].Insert(mxdis[x]), hp2[y].Insert(ans[x]);
Update(y);//y的虚子树变了 别忘更新y啊
}
void Cut(int x,int y)
{
Make_root(x), Access(y), Splay(y);
son[y][0]=fa[x]=0, Update(y);
}
void Query(int x)
{
Access(x), Splay(x);
printf("%d %d\n",mxdis[x]-1,ans[x]-1);
}
}
int main()
{
int n=read(); LCT::Init(n);
for(int i=1; i<n; ++i) LCT::Link(read(),read());
for(int m=read(),opt; m--; )
if((opt=read())==1) LCT::Link(read(),read());
else if(opt==2) LCT::Cut(read(),read());
else LCT::Query(read());
return 0;
}
考试代码
A
//还没调对，应该是f[0]和f[i]的特判（初值问题），不想改了。。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=5005,M=1e6+5;
int n,A[N],tm[M];
LL P,Q,R,f[N],suf[M],suf2[M];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
// freopen("A1.in","r",stdin);
// freopen("A.out","w",stdout);
n=read(); int mx=0;
for(int i=1; i<=n; ++i) mx=std::max(mx,A[i]=read());
std::sort(A+1,A+1+n);
P=read(), Q=read(), R=read();
for(int i=1; i<=n; ++i) ++suf2[A[i]];
for(int i=1; i<=n; ++i) suf[A[i]]=Q*A[i]*suf2[A[i]];
for(int i=mx-1; i; --i) suf[i]+=suf[i+1], suf2[i]+=suf2[i+1];
LL res=0;
for(int i=1; i<=n; ++i) res+=A[i];
res*=Q;
f[0]=1e15, f[1]=(A[1]-1)*Q;
for(int i=2; i<=n; ++i) f[i]=1e15;
for(int i=2; i<=n; ++i)
{
LL ai=A[i];
for(int j=i-1; ~j; --j)
{
f[j+1]=std::min(f[j+1],f[j])+(ai>j+1?Q*(ai-j-1):P*(j+1-ai));
res=std::min(res,R+f[j+1]+suf[j+2]-Q*(j+1)*suf2[j+2]);
}
}
printf("%I64d\n",res);
return 0;
}
B
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=1e6+5;
int n,sum[N];
char s[N];
bool Check(int k)
{
if(k+1==n) return 1;
if(!k){
for(int i=1; i<=n; ++i) if(sum[i]) return 0;
return 1;
}
for(int i=1; i<=n; ++i)
{
int a=i-1,b=(i+k-1)%n+1; if(!a) a=n;
if(sum[n]-sum[i+k]==0 && s[a]!=s[b]) return 1;
}
return 0;
}
void Solve()
{
n=strlen(s+1); sum[1]=0;
for(int i=2; i<=n; ++i)
sum[i]=sum[i-1]+(s[i]==s[i-1]);
// sum[n+1]=sum[n]+(s[n]==s[1]);
// for(int i=n+2; i<=n<<1; ++i) sum[i]=sum[i-1]+(s[i-n]==s[i-n-1]);
// for(int i=1; i<=n; ++i) printf("%d:%d\n",i,sum[i]);
for(int k=0; k<n; ++k) putchar(Check(k)+'0');
putchar('\n');
}
int main()
{
freopen("b2.in","r",stdin);
freopen("b.out","w",stdout);
int Cs=1;
while(~scanf("%s",s+1))
printf("Case %d:",Cs++), Solve();
return 0;
}
C
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 400000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+5,M=4e5+5;
int n,Enum,H[N],nxt[M],to[M],len[M],V,D;
bool ban[5003][5003];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int u,int v)
{
if(ban[u][v]) {ban[u][v]=ban[v][u]=0; return;}
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS(int x,int f,int d)
{
if(d>D) D=d, V=x;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=f && !ban[x][v]) DFS(v,x,d+1);
}
int main()
{
// freopen("c2.in","r",stdin);
// freopen("my.out","w",stdout);
n=read();
for(int i=1; i<n; ++i) AddEdge(read(),read());
for(int Q=read(),u,v,opt; Q--; )
if((opt=read())==1) AddEdge(read(),read());
else if(opt==2) u=read(),v=read(),ban[u][v]=ban[v][u]=1;
else
{
V=u=read();
D=0, DFS(u,u,0), printf("%d ",D), D=0, DFS(V,V,0), printf("%d\n",D);
}
return 0;
}