cf Round 601

2022-10-24 20:27:51

A.The Two Routes(BFS)

给出n个城镇，有m条铁路，铁路的补图是公路，汽车和火车同时从1出发，通过每条路的时间为1，不能同时到达除了1和n的其它点，问他们到达n点最少要用多长时间。

因为是补图，那么一定有一条路是可以直接从1到达n的。
那么我们把剩下的用bfs求一下即可。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int n, m, G[N][N], g[N][N], vis[N];

void bfs(int a[][N])

{

    queue<int>q;

    q.push(); vis[]=;

    while (!q.empty()) {

        if (vis[n]!=-) break;

        int u=q.front();

        q.pop();

        FOR(i,,n) if (a[u][i]&&vis[i]==-) q.push(i), vis[i]=vis[u]+;

    }

}

int main ()

{

    int u, v;

    mem(vis,-);

    scanf("%d%d",&n,&m);

    while (m--) scanf("%d%d",&u,&v), G[u][v]=G[v][u]=;

    FOR(i,,n) FOR(j,i+,n) if (G[i][j]==) g[i][j]=g[j][i]=;

    if (G[][n]==) bfs(g);

    else bfs(G);

    printf("%d\n",vis[n]);

    return ;

}

B.Lipshitz Sequence(单调队列)

给出一个序列和q个询问。询问区间的所有子区间的lipshitz的总和是多少。
lipshitz是指对于区间[l,r], 最大的ceil(|a[i]-a[j]|/i-j).(l<=j<i<=r)。

数形结合一下，我们画下图可以发现，一个区间[l,r]内的lipshitz一定是由两个相邻的数产生的。
于是我们把|a[i+1]-a[i]|预处理出来，计算每个值能对结果产生的贡献。
于是我们需要知道这个值它最左能延伸多少，最右能延伸多少。
用两个单调队列扫两下就行了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int a[N], b[N], q[N], l[N], r[N], head, tail;

int main ()

{

    int n, qq, c, d;

    scanf("%d%d",&n,&qq);

    FOR(i,,n) scanf("%d",a+i);

    FO(i,,n) b[i]=abs(a[i+]-a[i]);

    head=; tail=;

    FO(i,,n) {

        while (head<=tail&&b[q[tail]]<=b[i]) tail--;

        l[i]=q[tail]; q[++tail]=i;

    }

    head=; tail=; q[tail]=n;

    for (int i=n-; i>=; --i) {

        while (head<=tail&&b[q[tail]]<b[i]) tail--;

        r[i]=q[tail]; q[++tail]=i;

    }

    while (qq--) {

        scanf("%d%d",&c,&d);

        LL ans=;

        FO(i,c,d) {

            int l1=max(c,l[i]+), r1=min(d-,r[i]-);

            ans+=(LL)b[i]*(i-l1+)*(r1-i+);

        }

        printf("%lld\n",ans);

    }

    return ;

}

C.Kleofáš and the n-thlon(概率DP)

有n场比赛，和m名参赛者，已知这n场比赛每个人的rank都不同。
给出你每场比赛的排名，求最终排名的期望，最终排名是比你rank之和低的人数+1.

明显的DP，令dp[i][j]表示第i场比赛时分数为j的时候人数的期望。
那么有dp[i][j]=sum(dp[i-1][k])/(m-1).(j-m<=k<=j-1&&k!=j-a[i]).
这个复杂度是O(n*m*m)。
观察发现转移的时候加的是一个区间。我们用前缀和优化转移。
复杂度O(n*m).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int a[], flag;

double dp[][];

int main ()

{

    int n, m, sum=;

    scanf("%d%d",&n,&m);

    FOR(i,,n) scanf("%d",a+i), sum+=a[i];

    if (m==) {printf("%.10lf\n",1.0); return ;}

    dp[][]=m-;

    FOR(i,,n) {

        flag^=;

        mem(dp[flag],);

        FOR(j,i,i*m) {

            int l=max(j-m,i-), r=min(j-,(i-)*m);

            dp[flag][j]=dp[flag^][r]-(l==?:dp[flag^][l-]);

            int k=j-a[i];

            if (k>=l&&k<=r) dp[flag][j]-=(dp[flag^][k]-(k==?:dp[flag^][k-]));

            dp[flag][j]/=(m-);

        }

        FOR(j,i,i*m) dp[flag][j]+=dp[flag][j-];

    }

    double ans=(dp[flag][sum-]-dp[flag][n-]);

    printf("%.10lf\n",ans+);

    return ;

}

D.Acyclic Organic Compounds(Trie树合并)

我们算出每个节点的dif，这需要用到trie树的合并操作。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Edge{int p, next;}edge[N<<];

int head[N], cnt=, val[N], ch[N*][], tot, size[N*];

char s[N];

void add_edge(int u, int v)

{

    edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;

}

int merge(int u, int v)

{

    if (u<) return v;

    if (v<) return u;

    int t=++tot;

    size[t]=;

    FOR(i,,) {

        ch[t][i]=merge(ch[u][i], ch[v][i]);

        if (ch[t][i]>=) size[t]+=size[ch[t][i]];

    }

    return t;

}

void dfs(int x, int fa)

{

    FOR(i,,) ch[x][i]=-;

    for (int i=head[x]; i; i=edge[i].next) {

        int v=edge[i].p;

        if (v==fa) continue;

        dfs(v,x);

        int lab=s[v]-'a'+;

        ch[x][lab]=merge(ch[x][lab],v);

    }

    size[x]=;

    FOR(i,,) if (ch[x][i]>=) size[x]+=size[ch[x][i]];

    val[x]+=size[x];

}

int main ()

{

    int n, u, v;

    scanf("%d",&n);

    FOR(i,,n) scanf("%d",val+i);

    scanf("%s",s+);

    FO(i,,n) scanf("%d%d",&u,&v), add_edge(u,v), add_edge(v,u);

    tot=n;

    dfs(,);

    int ma=, ans=;

    FOR(i,,n) ma=max(val[i],ma);

    FOR(i,,n) if (ma==val[i]) ans++;

    printf("%d\n%d\n",ma,ans);

    return ;

}

E.A Museum Robbery(待填坑)

码农公寓

相关文章