2021 RoboCom 世界机器人开发者大赛-本科组（决赛）

7-1 绿地围栏 20

7-1 绿地围栏
分数 20
作者 陈越
单位 浙江大学
wl.png

市政规划了一块绿地，需要采购一批围栏将绿地围起来。

为了简单起见，我们假设绿地的形状是个封闭连通的规则多边形，即所有边都是互相垂直或平行的，并且没有交叉的十字边。我们指定某条垂直边上的一个点为原点 (0,0)，然后按照顺时针记录这个多边形的拐角顶点的位置。显然两个相邻的点坐标中，总有一个是不变的，因为当我们从一个点沿着平行于 x 轴的边移动到下一个点时，这两个点的 y 坐标是不变的；当我们从一个点沿着平行于 y 轴的边移动到下一个点时，这两个点的 x 坐标是不变的，所以我们可以用一种简化的方式去记录这些拐角，即对于从原点开始顺时针出现的拐角点 P
1
​
、P
2
​
、P
3
​
、…… 我们只需要记录 y
1
​
、x
2
​
、y
3
​
、…… 即可，其中 P
i
​
的坐标是 (x
i
​
,y
i
​
)。

采购的围栏每一条有固定长度 L，但是可以从任何地方弯折 90 度角，并且超长的部分也可以截掉。我们需要在两条围栏的衔接处打桩固定连接。现按顺时针方向给出绿地多边形各个拐角的简化坐标列表，请你计算需要采购多少条围栏，以及应该在哪里打桩。

输入格式：
输入第一行给出 2 个正整数，分别是：N（≤10
3
），为绿地拐角点的个数（原点不算在内）；以及 L（≤100），是一条围栏的长度。

随后给出 N 个整数，即从原点开始，按顺时针方向给出多边形各个拐角的简化坐标列表。每个坐标的绝对值均不超过 10
4
。数字间以空格分隔。题目保证没有重叠或交叉的边。

输出格式：
每行按格式 x y 输出一对坐标，即从原点出发顺时针给出的打桩点的坐标 (x,y)。注意原点肯定要打一个桩。规定从原点出发顺时针布置围栏，优先使用整条围栏，最后回到原点时，有多余的围栏才会被截掉。

输入样例：
14 5
2 1 1 4 3 5 2 6 -1 4 0 2 -1 0
输出样例：
0 0
2 1
5 3
6 -1
2 0
样例说明：
样例对应的多边形如下图所示（其中红色方块为原点）：

sample.png

容易算出围栏的总长度为 24，而每条围栏的长度为 5，所以需要 5 条围栏，多余的 1 个单位长度的围栏可以拆掉。从红色的原点出发，每隔 5 个单位打一根桩，图中蓝色方块即为打桩的位置。

题意：

• 有一个多边形，每条边都是水平或者垂直的。现在需要从(0, 0)点出发，每隔长度l打一个木桩，按顺时针顺序输出木桩的坐标。
• 存下各个拐点的坐标，然后模拟走路的过程，走了l就打一下桩，输出坐标，直到回到（0,0）。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

int main(){
    int n, l;  cin>>n>>l;
    int x=0, y=0;
    vector<PII>vc;
    for(int i = 0; i < n; i++){
        int u;  cin>>u;
        if(i%2==0)y = u;else x = u;
        vc.push_back({x,y});
    }
    x = 0, y = 0;//起点
    int px = vc[0].first, py = vc[0].second;//下一个点
    vc.push_back({0,0});           //终点
    cout<<"0 0"<<"\n";
    int d = 0;
    for(int i = 0; i < vc.size(); ){
        if(d==l){
            if(x==0 && y==0)break;
            cout<<x<<" "<<y<<"\n";
            d = 0;
        }
        if(x==px && y==py){//换下一个点
            i++;
            px = vc[i].first, py = vc[i].second;
            continue;
        }
        d++;//走路
        if(x==px){
            if(y<py)y++;else y--;
        }else{
            if(x<px)x++;else x--;
        }
    }
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

7-2 队列插入 25

现在有一个空队列 Q 以及 N 个数字需要按顺序插入，你可以选择插入队列的头部或尾部，请问在合理选择插入方式的前提下，插入后的队列的最长上升子序列的长度最大是多少？

最长上升子序列指的是在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。子序列指的是通过删除原序列中零个或多个元素后获得的序列。

输入格式:
输入第一行是一个数 N (1≤N≤1000)，表示有 N 个要按顺序插入的数字。

接下来一行 N 个数，表示要插入的数字，数字已经按插入顺序排列好，并且都在 32 位整数范围内。

输出格式:
输出两行，第一行是一个数字，表示最大的最长上升子序列的长度。

接下来一行，输出插入的方案，其中用L表示插入到头部，用R表示插入到尾部。当有多个相同长度的方案时，选择字典序最小的方案（L 的字典序小于 R）。

输入样例:
8
1 3 2 4 2 4 5 0
输出样例:
5
LLLLLRRL
样例解释：
样例最后队列内容为：0 2 4 2 3 1 4 5

题意：

• 给出n个数，你可以按顺序放入队列的头部或尾部，求最后能够形成的队列的最长上升子序列的长度，多方案时取字典序最小。

思路：

• 最后的序列肯定是一部分R一部分L，并且R的下标肯定是按照原数组顺序升序排列的，因此我们可以O(n)暴力枚举R开始的第一个点作为起点，然后求最长上升子序列，并且把用到的数打上标记作为最终LIS的一部分，然后再用剩余没有打标记的数尝试去更新该LIS的左边部分，就可以得到本轮的最大LIS，最后维护个全局答案即可。

• 因为本题数据范围为1000，能过的复杂度大约是n*nlogn，所以求LIS的做法需要优化到nlog的复杂度。

• 考虑nlogn的最长上升子序列做法，贪心+二分。
  f[i]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然当前最后一个元素越小，越有利于添加新的元素，这样LIS长度自然更长。
  转移的时候若a[i]大于f数组最大值，则直接在数组末位添加更新长度，若小于则二分f数组中第一个大于等于a[i]的位置，用a[i]替换之（之后更优）。

• PS：如果第4个点WA了24分，那么是你没开longlong

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //WA4
const LL maxn = 2e5+10;
LL a[maxn];

LL f[maxn], g[maxn];//长度为i的LIS结尾元素的最小值, 到i为止的LIS的长度最大值

LL ans = 0;
vector<LL>rp; //维护放R的数的下标
LL res[maxn]; //1为R，0为L

int main(){
    LL n;  cin>>n;
    for(LL i = 1; i <= n; i++)cin>>a[i];
    for(LL i = 1; i <= n+1; i++){
        //枚举R开始的第一个点，跑LIS
        LL len = 0;
        for(LL j = i; j <= n; j++){
            if(len==0)f[++len] = a[j], g[j] = len;
            else{
                if(a[j] > f[len]){
                    f[++len] = a[j];  g[j] = len;
                }else if(a[j] > f[1]){
                    LL x = lower_bound(f+1, f+len+1, a[j])-f;
                    f[x] = a[j];
                    g[j] = x;
                }
            }
        }
        vector<LL>tmp; //统计该LIS用了哪些数
        LL cnt = len, len1 = 0; 
        for(LL j = n; j >= 1; j--){
            if(g[j]==cnt && cnt)tmp.push_back(j), cnt--;
            g[j] = 0;
        }
        sort(tmp.begin(),tmp.end());
        for(LL j = 0; j < tmp.size(); j++)res[tmp[j]] = 1;
        //剩余的[1,r-1]的数，即l部分，尝试续接上面的最LIS
        LL x = f[1]; //LIS的末位值，比他小就能接
        if(len==0)x = 1e18+10;
        for(LL j = n; j >= 1; j--){
            if(res[j]==1){
                res[j] = 0;  continue;
            }
            if(len1==0 && a[j]<x){
                f[++len1] = a[j];
            }else if(a[j] < x){
                if(a[j] > f[len1]){
                    f[++len1] = a[j];
                }else{
                    LL x = lower_bound(f+1, f+len1+1, a[j])-f;
                    f[x] = a[j];
                }
            }
        }
        //更新总的LIS答案
        if(len+len1 > ans){
            ans = len+len1;  rp = tmp;
        }else if(len+len1 == ans){//长度相同时取字典序更小的
            if(rp.size()==0)continue;
            if(tmp.size()==0)rp = tmp;
            else if(tmp > rp){
                rp = tmp;
            }
        }
    }
    cout<<ans<<"\n";
    for(LL i = 0; i < rp.size(); i++)res[rp[i]] = 1;
    for(LL i = 1; i <= n; i++){
        if(res[i])cout<<"R";else cout<<"L";
    }
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
 

7-3 账户安全预警 25

7-3 账户安全预警
分数 25
作者 陈越
单位 浙江大学
拼题 A 系统为提高用户账户的安全性，打算开发一个自动安全预警的功能。对每个账户的每次登录，系统会记录其登录的 IP 地址。每隔一段时间，系统将统计每个账户从多少不同的 IP 地址分别登录了多少次。如果某个账户的登录 IP 超过了 T
IP
​
种，并且登录过于频繁，超过了 T
login
​
次，则会自动向管理员发出警报。

下面就请你实现这个预警功能。

输入格式：
输入首先在第一行中给出三个正整数：N（≤10
4
）为登录记录的条数；T
IP
​
和
T
login
​
，定义如题面中所描述，均不超过 100。

随后 N 行，每行格式为：

账户邮箱 IP地址
其中 账户邮箱 为长度不超过 40 的、不包含空格的非空字符串；IP地址 为形如 xxx.xxx.xxx.xxx 的合法 IP 地址。

输出格式：
按照登录所用不同 IP 的数量的非递增顺序，输出每个预警账户的信息。格式为：

账户邮箱
IP1 登录次数
IP2 登录次数
……
其中 IP 按登录次数的非递增顺序输出，如有并列，则按 IP 的递增字典序输出。此外，对所用不同 IP 的数量并列的用户，按其账户邮箱的递增字典序输出。

另一方面，即使没有账户达到预警线，也输出登录所用不同 IP 的数量最多的一批账户的信息。

输入样例 1：
24 3 4
daohaole@qq.com 218.109.231.189
1jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 113.18.235.143
jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 218.109.231.189
chenyuelaolao@zju.edu.cn 111.18.235.143
1jiadelaolao@163.com 115.192.203.187
daohaole@qq.com 113.189.58.141
1jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 112.18.58.145
1jiadelaolao@163.com 114.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
daohaole@qq.com 123.89.158.214
chenyuelaolao@zju.edu.cn 112.18.235.143
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 114.192.203.187
youdaohaole@qq.com 113.189.58.141
youdaohaole@qq.com 123.89.158.214
1jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 112.18.58.145
输出样例 1：
1jiadelaolao@163.com
111.192.203.187 1
112.192.203.187 1
113.192.203.187 1
114.192.203.187 1
115.192.203.187 1
daohaole@qq.com
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1
youdaohaole@qq.com
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1
输入样例 2：
24 5 8
daohaole@qq.com 218.109.231.189
1jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 113.18.235.143
jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 218.109.231.189
chenyuelaolao@zju.edu.cn 111.18.235.143
1jiadelaolao@163.com 115.192.203.187
daohaole@qq.com 113.189.58.141
1jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 112.18.58.145
1jiadelaolao@163.com 114.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
daohaole@qq.com 123.89.158.214
chenyuelaolao@zju.edu.cn 112.18.235.143
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 114.192.203.187
youdaohaole@qq.com 113.189.58.141
youdaohaole@qq.com 123.89.158.214
1jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 112.18.58.145
输出样例 2：
1jiadelaolao@163.com
111.192.203.187 1
112.192.203.187 1
113.192.203.187 1
114.192.203.187 1
115.192.203.187 1

题意：

• 给出n条记录，每条记录包含IP和邮箱，找出不同IP个数>t1的邮箱和IP总个数>t2的邮箱，按登录次数递减，IP字典序递增排序输出。
  如果没有任何邮箱符合要求，那么就输出不同ip登录次数最多的那一批账号信息。

思路：

• 嵌套map存每个邮箱对应的IP。然后扫一遍按题目要求排序输出即可。

#include<bits/stdc++.h>
using namespace std;

unordered_map<string, unordered_map<string, int> >mp;
struct IP{ string ip;  int cnt = 0; };
bool cmp(IP a, IP b){ return a.cnt!=b.cnt?a.cnt>b.cnt:a.ip<b.ip; }
struct EMAIL{ string email; vector<IP>ips; int cnt; };
bool cmp2(EMAIL a, EMAIL b){ return a.ips.size()!=b.ips.size() ? a.ips.size()>b.ips.size() : a.email<b.email; }
vector<EMAIL>emails, res;

int main(){
    int n, t1, t2;  cin>>n>>t1>>t2;
    for(int i = 1; i <= n; i++){
        string email, ip;  cin>>email>>ip;
        mp[email][ip]++;
    }
    //枚举邮箱,并将每个邮箱的ip按照数量和字典序排序
    for(auto &m : mp){
        int cnt = 0;
        vector<IP>ips;
        for(auto &v : m.second){
            cnt += v.second;
            ips.push_back({v.first,v.second});
        }
        sort(ips.begin(),ips.end(), cmp);
        emails.push_back({m.first,ips,cnt});
    }
    //筛出满足种类数>t1和总个数>t2的邮箱
    for(auto &e : emails){
        if(e.ips.size()<=t1 || e.cnt <= t2)continue;
        res.push_back(e);
    }
    if(res.size()==0){ //没有符合要求的,找登录次数最多的
        sort(emails.begin(),emails.end(),cmp2);
        for(int i = 0; i < emails.size() && emails[i].ips.size()==emails[0].ips.size(); i++){
            EMAIL e = emails[i];
            cout<<e.email<<"\n";
            for(IP ip : e.ips){
                cout<<ip.ip<<" "<<ip.cnt<<"\n";
            }
        }  
    }else{
        sort(res.begin(),res.end(),cmp2);
        for(auto e : res){
            cout<<e.email<<"\n";
            for(IP ip : e.ips){
                cout<<ip.ip<<" "<<ip.cnt<<"\n";
            }
        }
    }
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
 

7-4 猛犸不上Ban 30

7-4 猛犸不上 Ban
分数 30
作者 DAI, Longao
单位 杭州百腾教育科技有限公司
mammoth-gd01e31f27_640.png

在一个名叫刀塔的国家里，有一只猛犸正在到处跑着，希望能够用它的长角抛物技能来撞飞别人。已知刀塔国有 N 座城市，城市之间由 M 条道路互相连接，为了拦住这头猛犸，每条道路上设置了 V
i
​
人的团队。

这只猛犸从 S 号城市出发，它可以选择：

在不重复地经过若干条道路后回到 S 号城市；
在不重复地经过若干条道路后到达 T 号城市。
猛犸经过一条道路后，就会把路上的人全部撞飞。作为一头爱喝雪碧的仁慈的猛犸，自然希望尽可能的少撞飞人。请你帮忙计算一下在最优的选择下，最少需要撞飞多少人才能够到达目标城市？

输入格式:
输入第一行是四个正整数 N,M,S,T (2≤N≤500,1≤M≤10
5
)，表示有 N 个城市，M 条道路，猛犸从 S 号城市出发，可以选择到达 T 号城市。

接下来的 M 行，每行三个正整数 X
i
​
,Y
i
​
,V
i
​
(0≤V
i
​
≤100)，表示从 X
i
​
号城市到 Y
i
​
号城市有一条道路，道路上有 V
i
​
人的团队。道路可双向通行，城市编号从 1 开始，两个城市之间最多只有一条道路，且没有一条道路连接相同的城市。

数据保证两种选择里至少有一种是可行的。

输出格式:
输出两行，第一行是两个数字，分别对应上面的两种选择分别最少需要撞飞多少人。如果无论撞飞多少人都无法满足选择要求，则输出 -1。

第二行是一个句子，如果第一种（回到原点）的选择比较好，就输出 Win!，否则输出Lose!。

输入样例:
5 6 1 5
1 2 1
2 3 2
3 4 3
4 1 5
3 5 4
4 5 1
输出样例:
在这里给出相应的输出。例如：

11 6
Lose!

题意：

• n个点m条边的无向图，求从s出发走不重复的边到达s，以及从s出发走不重复的边到达t，两种方案下的最短路是多少，无法到达就-1。

思路：

• 从s到t直接dijkstra即可，毕竟没有负权边的情况下走重边肯定不会出现最短路。
• 从s到s的情况，可以枚举一个中转点x，那么答案为s->x + x->s的值，求s->x的时候打印路径，并标记那些边不可用，然后再跑一遍x->s2，更新答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 510, inf = 0x3f3f3f3f;

int n, m, s, ed;
int e[maxn][maxn], ok[maxn][maxn];
int dist[maxn], vis[maxn], pre[maxn];
int dist2[maxn], vis2[maxn];
void dijkstra(int x){
    memset(dist2, 0x3f,sizeof(dist2));
    memset(vis2, 0, sizeof(vis2));
    dist2[s] = 0;
    while(1){
        int t = -1;
        for(int i = 1; i <= n; i++){
            if(!vis2[i] && (t==-1 || dist2[t]>dist2[i]))t=i;
        }
        if(t==-1 || t==x)break;
        vis2[t] = 1;
        for(int i = 1; i <= n; i++){
            if(ok[i][t])continue;
            if(dist2[i]>dist2[t]+e[t][i]){
                dist2[i]=dist2[t]+e[t][i];
            }
        }
    }
}

int main(){
    memset(e,0x3f,sizeof(e));
    memset(dist,0x3f,sizeof(dist));
    memset(pre,-1,sizeof(pre));
    cin>>n>>m>>s>>ed;
    for(int i = 1; i <= m; i++){
        int u, v, w;  cin>>u>>v>>w;
        e[u][v] = e[v][u] = min(e[u][v], w);
    }
    //dist维护s到t的最短路
    dist[s] = 0;
    while(1){
        int t = -1;
        for(int i = 1; i <= n; i++){
            if(!vis[i] && (t==-1||dist[t]>dist[i]))t = i;
        }
        if(t == -1)break;
        vis[t] = 1;
        for(int i = 1; i <= n; i++){
            if(dist[i] > dist[t]+e[t][i]){
                dist[i] = dist[t]+e[t][i];
                pre[i] = t;
            }
        }
    }
    //枚举中转点x
    int ans1 = inf;
    for(int i = 1; i <= n; i++){
        if(i==s)continue;
        for(int x = pre[i], y = i; x != -1; y=pre[y], x=pre[x])
            ok[x][y] = ok[y][x] = 1;
        dijkstra(i);
        ans1 = min(ans1, dist[i]+dist2[i]);
        for(int x = pre[i], y = i; x != -1; y=pre[y], x=pre[x])
            ok[x][y] = ok[y][x] = 0;
    }
    cout<<(ans1==inf ? -1 : ans1)<<" ";
    cout<<(dist[ed]==inf ? -1 : dist[ed])<<"\n";
    cout<<(ans1<dist[ed] ? "Win!" : "Lose!");
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/124577470