赞
踩
市政规划了一块绿地,需要采购一批围栏将绿地围起来。
为了简单起见,我们假设绿地的形状是个封闭连通的规则多边形,即所有边都是互相垂直或平行的,并且没有交叉的十字边。我们指定某条垂直边上的一个点为原点 (0,0),然后按照顺时针记录这个多边形的拐角顶点的位置。显然两个相邻的点坐标中,总有一个是不变的,因为当我们从一个点沿着平行于 x 轴的边移动到下一个点时,这两个点的 y 坐标是不变的;当我们从一个点沿着平行于 y轴的边移动到下一个点时,这两个点的 x 坐标是不变的,所以我们可以用一种简化的方式去记录这些拐角,即对于从原点开始顺时针出现的拐角点 P1、P2、P3、…… 我们只需要记录 y1、x2、y3、…… 即可,其中 P**i 的坐标是 (xi,yi)。
采购的围栏每一条有固定长度 L,但是可以从任何地方弯折 90 度角,并且超长的部分也可以截掉。我们需要在两条围栏的衔接处打桩固定连接。现按顺时针方向给出绿地多边形各个拐角的简化坐标列表,请你计算需要采购多少条围栏,以及应该在哪里打桩。
输入第一行给出 2 个正整数,分别是:N(≤103),为绿地拐角点的个数(原点不算在内);以及 L(≤100),是一条围栏的长度。
随后给出 N 个整数,即从原点开始,按顺时针方向给出多边形各个拐角的简化坐标列表。每个坐标的绝对值均不超过 104。数字间以空格分隔。题目保证没有重叠或交叉的边。
每行按格式 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
样例对应的多边形如下图所示(其中红色方块为原点):
容易算出围栏的总长度为 24,而每条围栏的长度为 5,所以需要 5 条围栏,多余的 1 个单位长度的围栏可以拆掉。从红色的原点出发,每隔 5 个单位打一根桩,图中蓝色方块即为打桩的位置。
有一个多边形,每条边都是水平或者垂直的。现在需要从(0, 0)点出发,每隔长度l
打一个木桩,按顺时针顺序输出木桩的坐标
模拟
存下各个拐点的坐标,尤其注意这是一个闭合回路,需要注意把(0, 0)点加入路径,也就是说最后一个拐点的下一个点是零点(最后一个测试点,在最后一条边有木桩,3分),然后每次走一个单位坐标,每次走了l
长度,都输出当前坐标,并清空长度,走到零点结束即可。
//7-1 绿地围栏 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<cmath> #define x first #define y second using namespace std; typedef pair<int, int> PLL; int n, l; int x, y; vector<PLL> ps; int main() { cin >> n >> l; for(int i = 0; i < n; i++) { int u; cin >> u; if(i % 2 == 0) y = u; else x = u; ps.push_back({x, y}); } x = 0, y = 0; int u = 0, i = 0; int px = ps[0].x, py = ps[0].y; ps.push_back({0, 0}); cout << "0 0" << endl; while(i < ps.size()) { if(u == l) { if(x == 0 && y == 0) break; u = 0; cout << x << ' ' << y << endl; } if(x == px && y == py) { i++; px = ps[i].x, py = ps[i].y; continue; } u++; if(x == px) { if(y < py) y++; else y--; } else { if(x < px) x++; else x--; } } return 0; }
现在有一个空队列 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个数按顺序加入进去,使得形成的序列构成的最长上升子序列长度最长,如果有多种方式,选择push
字典序最小的(每个数字加入双端队列的头或者尾 L or R),最后输出最长上升子序列的长度,及插入的LR序列
时间复杂度O(2n)
双端队列,dp,模拟
暴力解法,枚举所有插入可能,计算最长上升子序列(15分)
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <deque> #include <vector> using namespace std; const int N = 1010; typedef long long LL; int n, m; int a[N]; int cal(vector<int> s) { int dp[N] = {0}; for (int i = 0; i < n; i++) { for(int j = 0; j < i; j++){ if(s[i] > s[j]) dp[i] = max(dp[i], dp[j] + 1); } } int ml = 1; for (int i = 0; i < n; i++) { ml = max(ml, dp[i] + 1); } return ml; } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int mlen = 1; LL ans = 0; for (LL i = 0; i < (1 << n); i++) { deque<int> q; for (int j = 0; j < n; j++) { if((i >> (n - j)) & 1) q.push_back(a[j]); else q.push_front(a[j]); } vector<int> s; for(int &x : q) s.push_back(x); int ml = cal(s); if(ml > mlen) { mlen = ml; ans = i; } if(mlen == n) { break; } } cout << mlen << endl; for (int i = 0; i < n; i++) { cout << ((ans >> (n - i)) & 1 ? 'R' : 'L'); } return 0; }
拼题 A 系统为提高用户账户的安全性,打算开发一个自动安全预警的功能。对每个账户的每次登录,系统会记录其登录的 IP 地址。每隔一段时间,系统将统计每个账户从多少不同的 IP 地址分别登录了多少次。如果某个账户的登录 IP 超过了 TIP 种,并且登录过于频繁,超过了 Tlogin 次,则会自动向管理员发出警报。
下面就请你实现这个预警功能。
输入首先在第一行中给出三个正整数:N(≤104)为登录记录的条数;TIP 和 Tlogin,定义如题面中所描述,均不超过 100。
随后 N 行,每行格式为:
账户邮箱 IP地址
其中 账户邮箱
为长度不超过 40 的、不包含空格的非空字符串;IP地址
为形如 xxx.xxx.xxx.xxx
的合法 IP 地址。
按照登录所用不同 IP 的数量的非递增顺序,输出每个预警账户的信息。格式为:
账户邮箱
IP1 登录次数
IP2 登录次数
……
其中 IP 按登录次数的非递增顺序输出,如有并列,则按 IP 的递增字典序输出。此外,对所用不同 IP 的数量并列的用户,按其账户邮箱的递增字典序输出。
另一方面,即使没有账户达到预警线,也输出登录所用不同 IP 的数量最多的一批账户的信息。
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
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
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
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
给出一些登录记录,每条记录包含邮箱和登录ip,现在需要统计每个邮箱登录的不同的ip个数超过t次,登录总次数超过k次的邮箱信息,需要先按照不同ip个数递减的顺序,个数相同按照邮箱字典序递增输出,每个邮箱账号都需要输出其ip信息,先按照ip登录次数递减,次数相同按照ip字典序递增输出,如果没有任何邮箱符合要求,那么就输出不同ip登录次数最多的那一批账号信息
模拟,排序,哈希表
用哈希表去存储每个邮箱,各个ip的登录次数,需要哈希表嵌套
然后遍历哈希表去按照题目要求排序
这里需要认真读题,如果没有任何邮箱符合要求,邮箱登录不同ip次数最多的账号可能会有多个
//7-3 账户安全预警 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<unordered_map> using namespace std; int n, k, p; unordered_map<string, unordered_map<string, int>> mp; struct IPS { string ip; int cnt; bool operator < (const IPS &ips) const { if(cnt != ips.cnt) return cnt > ips.cnt; return ip < ips.ip; } }; struct Record { string email; vector<IPS> ips; int cnt; bool operator < (const Record &r) const { if(ips.size() != r.ips.size()) return ips.size() > r.ips.size(); return email < r.email; } }; vector<Record> records; vector<Record> res; int main() { scanf("%d %d %d", &n, &k, &p); for(int i = 0; i < n ; i++) { char email[56], ip[18]; scanf("%s %s", email, ip); mp[email][ip]++; } for(auto &m : mp) { int cnt = 0; vector<IPS> ips; for(auto &v : m.second) { cnt += v.second; ips.push_back({v.first, v.second}); } sort(ips.begin(), ips.end()); records.push_back({m.first, ips, cnt}); } for(Record &r : records) { if(r.ips.size() <= k || r.cnt <= p) continue; res.push_back(r); } if(res.size()) { sort(res.begin(), res.end()); for(Record &r : res) { cout << r.email << endl; for(IPS &ips : r.ips) { cout << ips.ip << ' ' << ips.cnt << endl; } } } else { sort(records.begin(), records.end()); for(int i = 0; i < records.size() && records[i].ips.size() == records[0].ips.size(); i++) { Record r = records[i]; cout << r.email << endl; for(IPS &ips : r.ips) { cout << ips.ip << ' ' << ips.cnt << endl; } } } return 0; }
在一个名叫刀塔的国家里,有一只猛犸正在到处跑着,希望能够用它的长角抛物技能来撞飞别人。已知刀塔国有 N 座城市,城市之间由 M 条道路互相连接,为了拦住这头猛犸,每条道路上设置了 Vi人的团队。
这只猛犸从 S 号城市出发,它可以选择:
猛犸经过一条道路后,就会把路上的人全部撞飞。作为一头爱喝雪碧的仁慈的猛犸,自然希望尽可能的少撞飞人。请你帮忙计算一下在最优的选择下,最少需要撞飞多少人才能够到达目标城市?
输入第一行是四个正整数 N,M,S,T (2≤N≤500,1≤M≤105),表示有 N 个城市,M 条道路,猛犸从 S 号城市出发,可以选择到达 T 号城市。
接下来的 M 行,每行三个正整数 Xi,Yi,Vi (0≤Vi≤100),表示从 Xi, 号城市到 Yi号城市有一条道路,道路上有 Vi人的团队。道路可双向通行,城市编号从 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!
给定一无向图,图中各边有权值,给出起点s,终点t,现在有两种选择,一种是从s出发走不重复的边到达s,一种是从s出发走不重复的边到达t,分别求出这两种方式中权值最小时的权值,并比较这两种方式的好坏,如果无法到达,输出-1
思维,dijkstra
首先从s到t,一遍dijkstra即可,因为该算法也是走的不重复的边
然后是s到s,如果直接暴力dfs的话,可以得到18分,其余点超时
n是不超过500的,极限情况我们可以运行O(n3)的算法
dijkstra是O(n2)的,我们能否执行n次该算法得到答案呢?是可以的
我们可以把s到s,一分为二,假设路径经过一点x,我们可以把环从s和x直接切开,问题便转化为求s到x,x到s到最短路径,题目要求了不重复边,我们可以这样,因为在求s到t的过程中,已经求得了s到x到最短路径,我们再在这个过程中求得每个节点的前一个节点是多少,也就是说记录路径,这样我们就可以得知最短路径中途径了哪些点,途径了那些边。我们依次枚举每个点作为途径点x,从s到x到最短路径记为dist1,随后标记这条路径所有经过的边,再跑一遍dijkstra,求x到s的最短路径,需要注意的是,在拓展时,之前被标记的边不能用,这样就能求得dist2,s到s就是枚举所有点作为中转点,最短路径为所有情况的min(dist1+dist2)
//7-4 猛犸不上Ban #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 510, INF = 0x3f3f3f3f, M = 1e5 + 10; int n, m, s, t; int G[N][N]; bool st[N][N]; bool vis[N], st1[N]; int dist[N], pre[N], dist1[N]; int ans1 = INF, ans2 = INF; void dijkstra(int x) { memset(dist1, 0x3f, sizeof dist1); memset(st1, 0, sizeof st1); dist1[s] = 0; while(true) { int t = -1; for(int i = 1; i <= n; i++) if(!st1[i] && (t == -1 || dist1[t] > dist1[i])) t = i; if(t == -1 || t == x) break; st1[t] = true; for(int i = 1; i <= n; i++) { if(st[i][t]) continue; if(dist1[i] > dist1[t] + G[t][i]) { dist1[i] = dist1[t] + G[t][i]; } } } } int main() { memset(G, 0x3f, sizeof G); memset(pre, -1, sizeof pre); memset(dist, 0x3f, sizeof dist); scanf("%d %d %d %d", &n, &m, &s, &t); for(int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); G[a][b] = G[b][a] = min(G[a][b], c); } dist[s] = 0; while(true) { int t = -1; for(int i = 1; i <= n; i++) if(!st1[i] && (t == -1 || dist[t] > dist[i])) t = i; if(t == -1) break; st1[t] = true; for(int i = 1; i <= n; i++) { if(dist[i] > dist[t] + G[t][i]) { dist[i] = dist[t] + G[t][i]; pre[i] = t; } } } // for(int i = 1; i <= n; i++) // cout << i << ' ' << dist[i] << ' ' << pre[i] << endl; 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]) { st[x][y] = st[y][x] = true; // cout << x << ' ' << y << endl; } dijkstra(i); // cout << i << ' ' << dist[i] << ' ' << dist1[i] << endl; ans1 = min(ans1, dist[i] + dist1[i]); for (int x = pre[i], y = i; x != -1 ; y = pre[y], x = pre[x]) { st[x][y] = st[y][x] = false; } } if(ans1 == INF) printf("-1"); else printf("%d", ans1); printf(" "); ans2 = dist[t]; if(ans2 == INF) printf("-1"); else printf("%d", ans2); puts(""); ans1 < ans2 ? puts("Win!") : puts("Lose!"); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。