长乐培训Day6

怼烎@ 2021-11-05 16:22 265阅读 0赞

## T1 数列 ##

### 题目 ###

【题目描述】

![1447229-20190727173252051-622114858.png][]

【输入格式】

![1447229-20190727173417358-1655965898.png][]

![1447229-20190727173425452-1062363086.png][]

【输出格式】

![1447229-20190727173509734-631146043.png][]

【输入样例】

![1447229-20190730110244458-1321181658.png][]

【输出样例】

![1447229-20190730110300037-1832531257.png][]

【数据规模】

如上所述。

### 解析 ###

身为T1，居然比T4还难......让我怎么办......以下为巨佬题解：

![1447229-20190728103500246-857882340.png][]

我猜你们看了题解估计也不理解（手动滑稽），配合代码一起看吧，我也无能为力了。

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

## T2 集合 ##

### 题目 ###

【题目描述】

给定一个可重集合，一开始只有一个元素0。然后你可以操作若干轮，每一轮，你需要对于集合中的每个元素x进行如下三种操作之一：

1、将x变为x+1。

2、将x分裂为两个非负整数y,z，且满足x=y+z。

3 、什么都不做。

每一轮，集合中的每个元素都必须进行上面三个操作之一。

对于一个最终的集合，你的任务是判断至少进行了多少轮。

【输入格式】

第一行为一个正整数n，表示集合的最终大小。

第二行为n个非负整数，描述集合中的元素。

【输出格式】

输出一个非负整数，为最少的轮数。

【输入样例】

0 0 0 3 3

【输出样例】

【数据规模】

![1447229-20190727173902963-476208012.png][]

### 解析 ###

四题中唯一一道送分题，结果看错题目了QAQ。

很显然我们应该尽量把数分得多一些，然后尽量加一。

从零开始推显然不好操作，我们不妨逆着推：

每次把不是零的数都减一，把零两两合并。

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

## T3 迎接仪式 ##

### 题目 ###

【题目描述】

教主要来C市指导学习工作了。为了迎接教主，在一条道路旁，一群人穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。

一旁的人依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的人却不太和谐。

为了简单描述这个不和谐的队列，我们用“j”替代“教”，“z”替代“主”。而一个“j”与“z”组成的序列则可以描述当前的队列。

为了让教主看得尽量舒服，你必须调整队列，使得“jz”子串尽量多。每次调整你可以交换任意位置上的两个人，也就是序列中任意位置上的两个字母。

而因为教主马上就来了，时间仅够最多作K次调整（当然可以调整不满K次），所以这个问题交给了你。

【输入格式】

第1行包含2个正整数N与K，表示了序列长度与最多交换次数。

第2行包含了一个长度为N的字符串，字符串仅由字母“j”与字母“z”组成，描述了这个序列。

【输出格式】

仅包括一个非负整数，为调整最多K次后最后最多能出现多少个“jz”子串。

【输入样例】

5 2

zzzjj

【输出样例】

【数据规模】

对于10%的数据，有N≤10；

对于30%的数据，有K≤10；

对于40%的数据，有N≤50；

对于100%的数据，有N≤500，K≤100

### 解析 ###

又是动态规划，令f\[i\]\[j\]\[z\]表示前i个字符，已经处理了j个'j'和z个'z'。

边界为f\[0\]\[0\]\[0\]=f\[1\]\[0\]\[0\]=0。

状态转移方程：

1、不换：f\[i\]\[j\]\[z\]=f\[i-1\]\[j\]\[z\]。

2、换：如果a\[i-1\]为'j'的话，令u=0，否则u=1，如果a\[i\]为'z'的话，令v=0，否则v=1，

因为如果之前处理过了'j'或'z'的话，就不用增加处理'j'与'z'的数量，反之要增加，故f\[i\]\[j\]\[z\]=f\[i-2\]\[j-u\]\[z-v\]。

最后答案为最大的f\[n\]\[i\]\[i\](i=1-k)。

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

## T4 益智游戏 ##

### 题目 ###

【题目描述】

小P和小R在玩一款益智游戏。游戏在一个正权有向图上进行。

小P控制的角色要从A点走最短路到B点，小R控制的角色要从C点走最短路到D点。

一个玩家每回合可以有两种选择，移动到一个相邻节点或者休息一回合。

假如在某一时刻，小P和小R在相同的节点上，那么可以得到一次特殊奖励，但是在每个节点上最多只能得到一次。

求最多能获得多少次特殊奖励。

【输入格式】

第一行两个整数n，m表示有向图的点数和边数。

接下来m行每行三个整数xi，yi，li，表示从xi到yi有一条长度为li的边。

最后一行四个整数A，B，C，D，描述小P的起终点，小R的起终点。

【输出格式】

输出一个整数表示最多能获得多少次特殊奖励。若小P不能到达B点或者小R不能到达D点则输出-1。

【输入样例】

5 5

1 2 1

2 3 2

3 4 4

5 2 3

5 3 5

1 3 5 4

【输出样例】

【数据规模】

对于30%的数据，满足n≤50

对于60%的数据，满足n≤1000，m≤5000

对于100%的数据，满足n≤50000，m≤200000，1≤li≤500000000

### 解析 ###

这题正解居然是四遍dijkstra+topu排序，恐怖如斯，不说了，直接扔大佬题解：

(1)特殊奖励的点一定是连续的

(2)若s-->x+(x,y)+y-->t = s-->t 则(x,y)在s到t的最短路上

(3)所有在A-->B,C-->D的最短路上的边构成一个有向无环图

在正向图上求A，C出发的最短路

在反向图上求到达B，D的最短路

最短路可以用dijkstra+优先队列

筛选出在A-->B,C-->D的最短路上的边作为新图

对新图拓扑排序+DP求最长路

时间复杂度(MlogN)

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <string>
    #include <cstdio>
    #include <vector>
    #include <cmath>
    #include <queue>
    using namespace std;
    long long read()
    {
        long long num=0,w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-') w=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            num=(num<<1)+(num<<3)+ch-'0';
            ch=getchar();
        }
        return num*w;
    }
    const int N=50010;
    const int M=200010;
    struct rec{
        int to,next;
        long long l;
    }edge1[M],edge2[M];
    int n,m,cnt,head1[N],head2[N],in[N],f[N],ans;
    long long d1[N],d2[N],d3[N],d4[N];
    bool vis[N];
    void add1(int x,int y,int l)
    {
        edge1[++cnt].to=y;
        edge1[cnt].l=l;
        edge1[cnt].next=head1[x];
        head1[x]=cnt;
        edge2[cnt].to=x;
        edge2[cnt].l=l;
        edge2[cnt].next=head2[y];
        head2[y]=cnt;
    }
    void add2(int x,int y)
    {
        edge2[++cnt].to=y;
        edge2[cnt].next=head2[x];
        head2[x]=cnt;
    }
    void dijkstra(int t,long long *d,int *head,rec *edge)
    {
        for(int i=1;i<=n;i++) d[i]=0x7f7f7f7f7f7f7f7f;
        memset(vis,false,sizeof(vis));
        priority_queue< pair<long long,int> > q;
        d[t]=0,q.push(make_pair(0,t));
        while(q.size())
        {
            int now=q.top().second;
            q.pop();
            if(vis[now]) continue;
            vis[now]=true;
            for(int i=head[now];i;i=edge[i].next)
            {
                int next=edge[i].to;
                long long l=edge[i].l;
                if(d[next]>d[now]+l)
                {
                    d[next]=d[now]+l;
                    q.push(make_pair(-d[next],next));
                }
            }
        }
    }
    void topu_sort()
    {
        queue<int> q;
        for(int i=1;i<=n;i++)
            if(!in[i]) q.push(i);
        while(q.size())
        {
            int now=q.front();
            q.pop();
            for(int i=head2[now];i;i=edge2[i].next)
            {
                int next=edge2[i].to;
                f[next]=max(f[next],f[now]+1);
                ans=max(ans,f[next]);
                in[next]--;
                if(!in[next]) q.push(next);
            }
        }
    }
    int main()
    {
        //freopen("game.in","r",stdin);
        //freopen("game.in","w",stdout);
        n=read(),m=read();
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read();
            long long l=read();
            add1(x,y,l);
        }
        int a=read(),b=read(),c=read(),d=read(),k=0;
        dijkstra(a,d1,head1,edge1),dijkstra(b,d2,head2,edge2);
        dijkstra(c,d3,head1,edge1),dijkstra(d,d4,head2,edge2);
        if(d1[b]==0x7f7f7f7f7f7f7f7f||d3[d]==0x7f7f7f7f7f7f7f7f)
        {
            cout<<"-1";
            return 0;
        }
        for(int i=1;i<=n;i++)
            if(d1[i]+d2[i]==d1[b]&&d3[i]+d4[i]==d3[d])
            {
                k=1;
                break;
            }
        memset(edge2,0,sizeof(edge2));
        memset(head2,0,sizeof(head2));
        cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=head1[i];j;j=edge1[j].next)
            {
                int next=edge1[j].to;
                if(d1[i]+d2[next]+edge1[j].l==d1[b]&&d3[i]+d4[next]+edge1[j].l==d3[d])
                {
                    in[next]++;
                    add2(i,next);
                }
            }
        topu_sort();
        cout<<ans+k;
        return 0;
        //fclose(stdin);
        //fclose(stdout);
    }

转载于:https://www.cnblogs.com/I-Love-You-520/p/11255959.html

[1447229-20190727173252051-622114858.png]: /images/20211104/a3e2c2e0ba084214b151a5adcde7e4e0.png
[1447229-20190727173417358-1655965898.png]: /images/20211104/9cd236847d9144b08385b1858331d29f.png
[1447229-20190727173425452-1062363086.png]: /images/20211104/5a4bce162b484cd9a034403507b76685.png
[1447229-20190727173509734-631146043.png]: /images/20211104/43babc31576e4935ab2db96a2cee5045.png
[1447229-20190730110244458-1321181658.png]: /images/20211104/17f5bdd1735c4606b4392fba768892b8.png
[1447229-20190730110300037-1832531257.png]: /images/20211104/66df0b6ed8084317969090949b34c03f.png
[1447229-20190728103500246-857882340.png]: /images/20211104/a67efc9615b7456bb90849fcc2acc07b.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211104/f3b0bb0fa7db43bda92e711ca0bdc2ed.png
[1447229-20190727173902963-476208012.png]: /images/20211104/d89b52e88d864f4daadfbe8eb7dbe51c.png