Educational Codeforces Round 62
A. Detective Book
一本书有(n)页，每一页都有一个谜题，第(i)页谜题的答案在(a_i)。现在一个人看书，他每天往后看一页，然后一直往后看，直到他看到了他已知的所有谜题的答案就停止。
问这个人要看多少天。
模拟题。
#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,ans;
int main()
{
n=read();
for(int i=1,mx=0;i<=n;++i)
{
mx=max(mx,read());
if(mx==i)++ans,mx=0;
}
printf("%d
",ans);
}
B. Good String
你有一个长度为(n)的串(S)，这个串只由
<和>组成。你可以进行若干次操作，每次操作选择一个字符，如果这个字符是<，那么删去它左侧的字符，如果是>那么删去它右侧的字符。
现在有若干次询问，每次给你一个串，你可以先手动删去若干个字符，然后再通过它的操作，使得最终的串只剩下相同的字符。问你最少可以删去多少个字符。
显然找到左侧的第一个>或者右侧的第一个<，其左边或者右边的所有字符全部删掉取(min)就是答案了。
#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,ans;char s[105];
int main()
{
int T=read();
while(T--)
{
n=read();scanf("%s",s+1);ans=n-1;
for(int i=1;i<=n;++i)
if(s[i]=='>')ans=min(ans,i-1);
else ans=min(ans,n-i);
printf("%d
",ans);
}
}
C. Playlist
你有(n)首歌，第(i)首的时间为(t_i)，评分是(w_i)。
你现在要听不超过(K)首歌，产生的愉悦值是歌的总长乘上评分的最小值。
求愉悦值的最大值。
按照评分从大往小排序，拿一个堆维护最大的(k)个时间就行了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 300300
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,k;long long ans,len;
pair<int,int> a[MAX];
priority_queue<int,vector<int>,greater<int> > Q;
int main()
{
n=read();k=read();
for(int i=1;i<=n;++i)a[i].second=read(),a[i].first=read();
sort(&a[1],&a[n+1]);
for(int i=n;i;--i)
{
len+=a[i].second;Q.push(a[i].second);
if(Q.size()>k)len-=Q.top(),Q.pop();
ans=max(ans,a[i].first*len);
}
printf("%lld
",ans);
return 0;
}
D. Minimum Triangulation
你有一个(n)个顶点的正多边形，顶点逆时针编号。你现在要找到一个三角形划分，使得每一个三角形三个顶点的乘积的和最小。
当然要让(1)出现在每一个三角剖分里啊。
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n;ll ans;
int main()
{
n=read();
for(int i=3;i<=n;++i)ans+=i*(i-1);
printf("%lld
",ans);
return 0;
}
E. Palindrome-less Arrays
给定一个不完全的序列，你要把没有填的位置用([1,k])中的整数来替代。使得不存在任何一个长度大于(1)的奇数连续子序列使得它是回文。
求方案数。
首先发现如果存在一个不合法的子序列，那么一定是存在一个长度为(3)的不合法的子序列。
即每次只要有(a_i
eq a_{i-2})那么一定合法。
那么把奇偶分开考虑，变成给定一个序列，你要让相邻的两项不相等，求方案数。
发现对于已经填好的数，他们把一堆未知量为分割成了一段一段，且段与段之间不相邻，那么我们直接对于每一段进行(dp)，可以设(f[i][0/1/2])表示当前考虑到了第(i)个位置，当前值与段首相同、与段尾相同以及都不相同。对于段首段尾都相同以及没有段首和段尾就特殊考虑一下就行了。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 200200
#define MOD 998244353
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,k,ans=1,a[MAX],b[MAX],t1,t2;
int f[MAX][3];
int dp(int *a,int mx,int l,int r)
{
int lim=0,S=0;
if(l>1){lim+=1;S+=1;if(r<mx)S+=2;if(r<mx&&a[r+1]!=a[l-1])++lim;}
else if(r<mx)++lim,S+=2;
if(lim>0)f[l][0]=0;if(lim>1)f[l][1]=1;
if(!(S&1)&&lim>0)f[l][0]=1;
int v2=k-lim;f[l][2]=v2;
for(int i=l+1;i<=r;++i)
{
if(lim>0)f[i][0]=(f[i-1][1]+f[i-1][2])%MOD;
if(lim>1)f[i][1]=(f[i-1][0]+f[i-1][2])%MOD;
f[i][2]=(1ll*f[i-1][0]*v2+1ll*f[i-1][1]*v2+1ll*f[i-1][2]*(v2-1))%MOD;
}
int ret=f[r][2];
if(lim>0)ret=(ret+f[r][0])%MOD;
if(lim>1)ret=(ret+f[r][1])%MOD;
if(S&2)
{
if(lim==1)ret=(ret+MOD-f[r][0])%MOD;
if(lim==2)ret=(ret+MOD-f[r][1])%MOD;
}
for(int i=l;i<=r;++i)f[i][0]=f[i][1]=f[i][2]=0;
return ret;
}
int main()
{
n=read();k=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=3;i<=n;++i)if(~a[i]&&a[i]==a[i-2]){puts("0");return 0;}
for(int i=1;i<=n;++i)
if(i&1)a[++t1]=a[i];
else b[++t2]=a[i];
for(int i=1,j,p;i<=t1;i=p+1)
{
j=i;while(j<=t1&&~a[j])++j;
if(j>t1)break;
p=j;while(p<t1&&!~a[p+1])++p;
ans=1ll*ans*dp(a,t1,j,p)%MOD;
}
for(int i=1,j,p;i<=t2;i=p+1)
{
j=i;while(j<=t1&&~b[j])++j;
if(j>t2)break;
p=j;while(p<t2&&!~b[p+1])++p;
ans=1ll*ans*dp(b,t2,j,p)%MOD;
}
printf("%d
",ans);
return 0;
}
F. Extending Set of Points
一个点集的(E(S))是这样计算的：先令(R=S)，如果存在四个数(x1,x2,y1,y2)，满足((x1,y1),(x1,y2),(x2,y1)in R,(x2,y2) otin R)，那么就把((x2,y2))加入到(R)里面去。最后(R)的大小就是(E(S))。
现在有若干次操作，每次是往(S)中加入一个点或者删去一个点，求每次操作完之后的(E(S))。
不难发现这个东西本质上是一个并查集操作，即如果加入了点((x,y))，就加边(x-y)，那么最终就是所有在一个集合中的(x)的数量乘上(y)的数量的和就是(E(S))。
于是就变成了动态加边删边维护并查集操作？
直接离线线段树分治就可以了。
总的来说这题挺简单的？
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define MAX 300300
#define mp make_pair
#define fr first
#define sd second
#define pi pair<int,int>
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int f[MAX<<1],sz[MAX<<1],szx[MAX<<1],szy[MAX<<1];
int getf(int x){return x==f[x]?x:getf(f[x]);}
pi St[MAX];int top;ll ans;
ll Calc(int x){return 1ll*szx[x]*szy[x];}
void Merge(int x,int y)
{
x=getf(x);y=getf(y);if(x==y)return;
if(sz[x]<sz[y])swap(x,y);
ans-=Calc(x)+Calc(y);
f[y]=x;sz[x]+=sz[y];szx[x]+=szx[y];szy[x]+=szy[y];
ans+=Calc(x);St[++top]=mp(x,y);
}
void undo(int x,int y)
{
ans-=Calc(x);
f[y]=y;sz[x]-=sz[y];szx[x]-=szx[y];szy[x]-=szy[y];
ans+=Calc(x);ans+=Calc(y);
}
int n;
map<pi,int> M;
vector<pi> t[MAX<<2];
#define lson (now<<1)
#define rson (now<<1|1)
void Modify(int now,int l,int r,int L,int R,pi w)
{
if(L<=l&&r<=R){t[now].push_back(w);return;}
int mid=(l+r)>>1;
if(L<=mid)Modify(lson,l,mid,L,R,w);
if(R>mid)Modify(rson,mid+1,r,L,R,w);
}
void Divide(int now,int l,int r)
{
int ntop=top;
for(pi u:t[now])Merge(u.fr,u.sd);
if(l==r)printf("%lld ",ans);
else
{
int mid=(l+r)>>1;
Divide(lson,l,mid);
Divide(rson,mid+1,r);
}
while(top>ntop)undo(St[top].fr,St[top].sd),--top;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
{
int x=read(),y=read()+MAX;pi w=mp(x,y);
f[x]=x;sz[x]=szx[x]=1;
f[y]=y;sz[y]=szy[y]=1;
if(!M[w])M[w]=i;
else Modify(1,1,n,M[w],i-1,w),M[w]=0;
}
for(auto u:M)if(M[u.fr])Modify(1,1,n,M[u.fr],n,u.fr);
Divide(1,1,n);
return 0;
}
G. Double Tree
翻译见洛谷
给定的图是由两棵同构的树组成，然后树上两两对应的点之间有一条边。
每次询问求两点之间的最短路。
考虑树是一条链的情况，那么给定的图其实就是一个网格图。
那么我们把整个部分分治处理，每次考虑是否会跨越中线，预处理出中线到分治区间内每一个点的最短路，这样子询问的之后只需要把路径拼接起来。也就是类似这道题目。
现在回到树上，那么把分治变成点分治，每次还是考虑跨越分治重心的链就好了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define MAX 600600
inline ll read()
{
ll x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next;ll w;}e[MAX<<2];
int h[MAX],cnt=2;
inline void Add(int u,int v,ll w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
vector<int> E[MAX];
int n,size[MAX],Size,mx,rt;
bool vis[MAX];
ll dis[2][20][MAX];
int book[2][20][MAX];
#define pll pair<ll,int>
#define mp make_pair
priority_queue<pll,vector<pll>,greater<pll> >Q;
void Dijkstra(int S,ll *dis,int *book)
{
dis[S]=0;Q.push(mp(0,S));
while(!Q.empty())
{
int u=Q.top().second;Q.pop();
if(book[u]||vis[u>>1])continue;book[u]=true;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;ll w=dis[u]+e[i].w;
if(dis[v]>w)dis[v]=w,Q.push(mp(dis[v],v));
}
}
}
void Getroot(int u,int ff)
{
size[u]=1;int ret=0;
for(int v:E[u])
{
if(vis[v]||v==ff)continue;
Getroot(v,u);size[u]+=size[v];
ret=max(ret,size[v]);
}
ret=max(ret,Size-size[u]);
if(ret<mx)mx=ret,rt=u;
}
int Fa[MAX];
void Divide(int u,int ff,int dep)
{
Dijkstra(u<<1,dis[0][dep],book[0][dep]);
Dijkstra(u<<1|1,dis[1][dep],book[1][dep]);
vis[u]=true;Fa[u]=ff;Getroot(u,0);
for(int v:E[u])
{
if(vis[v])continue;
Size=mx=size[v];Getroot(v,u);
Divide(rt,u,dep+1);
}
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
{
ll w=read();
Add(i<<1,i<<1|1,w);
Add(i<<1|1,i<<1,w);
}
for(int i=1;i<n;++i)
{
int u=read(),v=read();ll w1=read(),w2=read();
E[u].push_back(v);E[v].push_back(u);
Add(u<<1,v<<1,w1);Add(v<<1,u<<1,w1);
Add(u<<1|1,v<<1|1,w2);Add(v<<1|1,u<<1|1,w2);
}
memset(dis,63,sizeof(dis));
Size=mx=n;Getroot(1,0);Divide(rt,0,0);
int Q=read();
while(Q--)
{
int x=read()+1,y=read()+1;
vector<int> fx,fy;
int X=x>>1;while(X)fx.push_back(X),X=Fa[X];
int Y=y>>1;while(Y)fy.push_back(Y),Y=Fa[Y];
reverse(fx.begin(),fx.end());reverse(fy.begin(),fy.end());
ll ans=8e18;
for(int i=0,lx=fx.size(),ly=fy.size();i<lx&&i<ly&&fx[i]==fy[i];++i)
ans=min(ans,min(dis[0][i][x]+dis[0][i][y],dis[1][i][x]+dis[1][i][y]));
printf("%lld
",ans);
}
return 0;
}