- 2021 RoboCom 世界机器人开发者大赛-本科组(决赛)
- 1.绿地围栏
- 思路
- 代码
- 2.队列插入
- 思路×
- 代码×
- 3.账户安全预警
- 思路
- 代码
- 4.猛犸不上 Ban
- 思路
- 代码
模拟题目,主要是记住最后要把原点加入到目标点当中,不然最后一个测试点过不了。
代码#include2.队列插入 思路×using namespace std; #define int long long #define pii pair int n, l, now_l, x, y; vector v; void init(){ cin >> n >> l; for (int i = 1; i <= n; ++i) { if (i & 1) cin>>y; else cin>>x; v.emplace_back(x,y); } v.emplace_back(0,0); //这里很重要,因为要走回原点,这里如果不加上的话,最后一个测试点就会错。 } void solve(){ x = y = 0;now_l = l; cout< while (x != p.first || y != p.second){ if (x == p.first){ //如果当前是纵向 if (y < p.second) //向上 ++y; else //向下 --y; } else{ //如果当前是横向 if (x < p.first) //向右 ++x; else //向左 --x; } --now_l; if (now_l == 0){ if (x != 0 || y != 0) cout< ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); init(); solve(); return 0; }
不太会,每理解大佬的思路,以后有机会补
代码× 3.账户安全预警输入样例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思路
嵌套map,用外层map的键表示邮箱,外层map的值也是一个map(内层map),内层map的键表示ip,值表示ip出现的次数,最后遍历一下,按照规定要求排序后输出即可。
代码#includeusing namespace std; #define int long long #define psi pair int n, Tip, Tlogin; map > mp; struct node{ string email; //邮箱 vector ip; //存ip登录信息 int tip; //ip总数 int tlogin; //登录次数 }; vector v, v1; bool cmp(const node& a,const node& b){ if (a.tip != b.tip) return a.tip > b.tip; return a.email < b.email; } bool CMP(psi a, psi b){ if (a.second != b.second) return a.second > b.second; return a.first < b.first; } signed main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>Tip>>Tlogin; string s, ip; for (int i = 0; i < n; ++i) { cin>>s>>ip; mp[s][ip] += 1; } for (const auto& it : mp) { node a; a.tlogin = 0; a.email = it.first; a.tip = it.second.size(); for (const auto& x : it.second) { a.ip.emplace_back(x.first, x.second); a.tlogin += x.second; } v.push_back(a); } for (auto & i : v) if (i.tip > Tip && i.tlogin > Tlogin) v1.push_back(i); if (!v1.empty()){ sort(v1.begin(),v1.end(),cmp); for (node &it : v1) { sort(it.ip.begin(),it.ip.end(),CMP); cout< cout< sort(v.begin(),v.end(),cmp); for (node &it : v) { if (it.tip != v[0].tip) break; cout< cout< 4.猛犸不上 Ban 输入样例
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->s的情况。
这个题目看到一些大佬的题解,还是很容易理解的。
s->t就不用说了,裸的迪杰斯特拉。
s->s的话,这个题目可以拆成s->i + i -> s这两段,但是边不能重复,因此要先将s->i最短路径上面的所有边都标记一下,然后再跑一次s->i(i->s),这次跑的时候就不能用已经被标记过的边了,也是迪杰斯特拉,只不过需要特殊处理判断一下边的使用情况。
代码#includeusing namespace std; #define int long long int inf; int n,m,s,t; //如题 int mp[505][505]; //存边 int dis[505]; //表示s到每个点的距离 int dis1[505]; //表示删除第一条路径上的边之后的最短距离 int vis[505]; //标记每个点是否被访问过 int vis1[505][505]; //标记每条边是否被访问过 int pre[505]; //表示每个点的前序最优结点 void init(){ cin>>n>>m>>s>>t; memset(mp,0x3f,sizeof mp); memset(dis,0x3f,sizeof dis);dis[s] = 0; memset(pre,255,sizeof pre); inf = dis[0]; while (m--){ int from,to,value;cin>>from>>to>>value; mp[from][to] = mp[to][from] = value; } } void dij(){ while (true){ int mn = inf,k = -1; for (int i = 1; i <= n; ++i) if (!vis[i] && dis[i] < mn) mn = dis[i],k = i; if (k == -1) break; vis[k] = true; for (int i = 1; i <= n; ++i) { if (dis[i] > dis[k] + mp[k][i]) dis[i] = dis[k] + mp[k][i],pre[i] = k; } } } void dij1(){ memset(dis1,0x3f,sizeof dis1);dis1[s] = 0; memset(vis,0,sizeof vis); while (true){ int mn = dis1[0],k = -1; for (int i = 1; i <= n; ++i) if (!vis[i] && dis1[i] < mn) mn = dis1[i],k = i; if (k == -1) break; vis[k] = true; for (int i = 1; i <= n; ++i) { if (vis1[k][i]) continue; if (dis1[i] > dis1[k] + mp[k][i]) dis1[i] = dis1[k] + mp[k][i]; } } } int solve(){ //将s->s 拆分成s->i + i->s int ans = inf; for (int i = 1; i <= n; ++i) { //遍历每个中间点i if (i == s) continue; for (int from = pre[i], to = i; from != -1 ; to = from, from = pre[from]) { vis1[from][to] = vis1[to][from] = true; } //将所有的该路径上的边标记为使用过 dij1(); ans = min(ans,dis[i] + dis1[i]); for (int from = pre[i], to = i; from != -1 ; to = from, from = pre[from]) { vis1[from][to] = vis1[to][from] = false; } //去除标记 } return ans; } signed main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); init(); //输入等初始化操作 dij(); //跑s->t并且存储pre int ans2 = dis[t]; int ans1 = solve(); //处理s->s cout<<(ans1 == inf ? -1 : ans1)<<" "; cout<<(ans2 == inf ? -1 : ans2)<<"n"; cout<<(ans1 < ans2 ? "Win!" : "Lose!"); return 0; }