2020年ICPC南京站 补题记录

2024-09-02 19:44
文章标签 2020 记录 icpc 补题 南京站

本文主要是介绍2020年ICPC南京站 补题记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • A - Ah, It's Yesterday Once More（构造）
  • E - Evil Coordinate（构造）
  • F - Fireworks（概率+三分）
  • H - Harmonious Rectangle（打表）
  • K - K Co-prime Permutation（签到）
  • L - Let's Play Curling（贪心+签到）
  • M - Monster Hunter（树形dp）

A - Ah, It’s Yesterday Once More（构造）

  • 奇妙构造。。。总的来说就是斜着，下面是出题人给的方案
    在这里插入图片描述
#include <bits/stdc++.h>
#include <bits/extc++.h>using namespace std;
using namespace __gnu_pbds;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 2e5 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{cout << 20 << ' ' << 20 << '\n';cout << "11111011111011111011\n";cout << "00101100101100101101\n";cout << "10110110110110110111\n";cout << "10011011011011011001\n";cout << "11101101101101101101\n";cout << "10110110110110110110\n";cout << "11011011011011011011\n";cout << "01101101101101101101\n";cout << "10110110110110110111\n";cout << "10011011011011011001\n";cout << "11101101101101101101\n";cout << "10110110110110110110\n";cout << "11011011011011011011\n";cout << "01101101101101101101\n";cout << "10110110110110110111\n";cout << "10011011011011011001\n";cout << "11101101101101101100\n";cout << "10110110110110110111\n";cout << "11011010011010011001\n";cout << "01101111101111101111\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}return 0;
}

E - Evil Coordinate（构造）

  • 首先如果起点或者终点就是地雷，那一定没有方案
  • 记录每个方向的次数，左右和上下都可以抵消，之后左右和上下都只剩下一个方向，判断一下画个矩形就行了
  • 有个特殊情况就是如果最后只剩下一个方向，且只走这一个方向会遇到地雷，可以利用另外的方向避开这个地雷（说起来有点抽象，看代码即可）
#include <bits/stdc++.h>using namespace std;// #define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 6e6 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int xx, yy; cin >> xx >> yy;string s; cin >> s;bool lr = 0, ud = 0;if (xx == 0 && yy == 0){cout << "Impossible\n";return;}vector<int> cnt(4); // UDLRint nowx = 0, nowy = 0;bool flag = false;for (auto t : s){if (t == 'U'){nowy ++ ;cnt[0] ++ ;}else if (t == 'D'){nowy -- ;cnt[1] ++ ;}else if (t == 'L'){nowx -- ;cnt[2] ++ ;}else{nowx ++ ;cnt[3] ++ ;}if (nowx == xx && nowy == yy) flag = true;}if (cnt[0] && cnt[1]) ud = true;if (cnt[2] && cnt[3]) lr = true;if (!flag) cout << s << '\n';else{if (nowx == xx && nowy == yy) cout << "Impossible\n";else{string ans = "";if (cnt[0] > cnt[1]){if (!(xx == 0 && yy == 1)) for (int i = 0; i < cnt[1]; i ++ ) ans += "UD";else for (int i = 0; i < cnt[1]; i ++ ) ans += "DU";cnt[0] -= cnt[1], cnt[1] = 0;}else{if (!(xx == 0 && yy == 1)) for (int i = 0; i < cnt[0]; i ++ ) ans += "UD";else for (int i = 0; i < cnt[0]; i ++ ) ans += "DU";cnt[1] -= cnt[0], cnt[0] = 0;}if (cnt[2] > cnt[3]){if (!(xx == -1 && yy == 0)) for (int i = 0; i < cnt[3]; i ++ ) ans += "LR";else for (int i = 0; i < cnt[3]; i ++ ) ans += "RL";cnt[2] -= cnt[3], cnt[3] = 0;}else{if (!(xx == -1 && yy == 0)) for (int i = 0; i < cnt[2]; i ++ ) ans += "LR";else for (int i = 0; i < cnt[2]; i ++ ) ans += "RL";cnt[3] -= cnt[2], cnt[2] = 0;}auto check1 = [&](){int x = 0, y = 0;for (int i = 0; i < cnt[2]; i ++ ){x -- ;if (xx == x && yy == y) return false;}for (int i = 0; i < cnt[3]; i ++ ){x ++ ;if (xx == x && yy == y) return false;}for (int i = 0; i < cnt[0]; i ++ ){y ++ ;if (xx == x && yy == y) return false;}for (int i = 0; i < cnt[1]; i ++ ){y -- ;if (xx == x && yy == y) return false;}return true;};auto check2 = [&](){int x = 0, y = 0;for (int i = 0; i < cnt[0]; i ++ ){y ++ ;if (xx == x && yy == y) return false;}for (int i = 0; i < cnt[1]; i ++ ){y -- ;if (xx == x && yy == y) return false;}for (int i = 0; i < cnt[2]; i ++ ){x -- ;if (xx == x && yy == y) return false;}for (int i = 0; i < cnt[3]; i ++ ){x ++ ;if (xx == x && yy == y) return false;}return true;};// 先左右后上下if (check1()){for (int i = 0; i < cnt[2]; i ++ ) ans += 'L';for (int i = 0; i < cnt[3]; i ++ ) ans += 'R';for (int i = 0; i < cnt[0]; i ++ ) ans += 'U';for (int i = 0; i < cnt[1]; i ++ ) ans += 'D';}else if (check2()) // 先上下后左右{for (int i = 0; i < cnt[0]; i ++ ) ans += 'U';for (int i = 0; i < cnt[1]; i ++ ) ans += 'D';for (int i = 0; i < cnt[2]; i ++ ) ans += 'L';for (int i = 0; i < cnt[3]; i ++ ) ans += 'R';}else{int tt = 0;for (int i = 0; i < 4; i ++ ) tt += (cnt[i] > 0);if (tt != 1){cout << "Impossible\n";return;}else{if (cnt[0] > 0 || cnt[1] > 0){if (!lr){cout << "Impossible\n";return;}ans.pop_back(), ans.pop_back();ans += 'L';for (int i = 0; i < cnt[0]; i ++ ) ans += 'U';for (int i = 0; i < cnt[1]; i ++ ) ans += 'D';ans += 'R';}else{if (!ud){cout << "Impossible\n";return;}for (int i = 0; i + 2 < ans.size(); i ++ ) ans[i] = ans[i + 2];ans.pop_back(), ans.pop_back();ans += 'U';for (int i = 0; i < cnt[2]; i ++ ) ans += 'L';for (int i = 0; i < cnt[3]; i ++ ) ans += 'R';ans += 'D';}}}cout << ans << '\n';}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

F - Fireworks（概率+三分）

  • 数学渣，偷个队友的码
#include<cstdio>
int n,m,p;
long double pow(long double n,long long m)
{if(m==0) return 1;long double fl=pow(n,m/2);fl*=fl;if(m&1) fl*=n;return fl;
}
long double F(long long k)
{long double a=(long double)n*k+m;long double b=1-pow(1-(long double)0.0001*p,k);return a/b;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&p);long long f=1,l=1e16;while(f<l){long long dt=(l-f)/3;long long mid1=f+dt,mid2=f+dt*2;long double val1=F(mid1),val2=F(mid2);if(val1>val2) f=mid1+1;else l=mid2;}f-=500;if(f<=0) f=1;long double ans=1e300;ans = F(l);for(long long i=f;i<=f+1000;i++){long double get=F(i);if(get<ans) ans=get;}if(f>1) {if(F(f-1)<F(f))while(1){f++;}}if(F(f+1000+1)<F(f+1000)){while(1){f++;}}printf("%.10lf\n",(double)ans);}return 0;
}

H - Harmonious Rectangle（打表）

  • 小数据打表 大数据直接pow(3, n*m)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int ans[100][100]={{0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,15,339,4761,52929,517761,4767849,43046721,387420489,486784380,381059392,429534507},{0,0,339,16485,518265,14321907,387406809,460338013,429534507,597431612,130653412,527642103,246336683},{0,0,4761,518265,43022385,486780060,429534507,792294829,175880701,246336683,953271190,214965851,412233812},{0,0,52929,14321907,486780060,288599194,130653412,748778899,953271190,644897553,710104287,555340537,947749553},{0,0,517761,387406809,429534507,130653412,246336683,579440654,412233812,518446848,947749553,909419307,966670169},{0,0,4767849,460338013,792294829,748778899,579440654,236701429,666021604,589237756,662963356,900849429,157687433},{0,0,43046721,429534507,175880701,953271190,412233812,666021604,767713261,966670169,322934415,772681989,566494346},{0,0,387420489,597431612,246336683,644897553,518446848,589237756,966670169,968803245,954137859,295347237,319625180},{0,0,486784380,130653412,953271190,710104287,947749553,662963356,322934415,954137859,886041711,876626606,924095353},{0,0,381059392,527642103,214965851,555340537,909419307,900849429,772681989,295347237,876626606,772286045,155055959},{0,0,429534507,246336683,412233812,947749553,966670169,157687433,566494346,319625180,924095353,155055959,93330098}};
int ksm(int a, int b)
{int res = 1;while (b){if (b & 1)res = res * a % mod;b >>= 1;a = a * a % mod;}return res;
}
signed main()
{int T;scanf("%lld",&T);while(T--){int n,m;scanf("%lld%lld",&n,&m);if(n<=10&&m<=10) printf("%lld\n",ans[n][m]);else if (n == 1 || m == 1) printf("%lld\n", 0ll);else printf("%lld\n",ksm(3,n*m));}return 0;
}

K - K Co-prime Permutation（签到）

#include<cstdio>
#include<iostream>
using namespace std;int a[1000005];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,k;// scanf("%d%d",&n,&k);cin >> n >> k;for(int i=1;i<=n;i++)a[i]=i;if(k==0) cout << -1;else{for(int i=1;i<k;i++)a[i]=a[i+1];a[k]=1;for(int i=1;i<=n;i++){// printf("%d ",a[i]);cout << a[i] << ' ';}}return 0;
}

L - Let’s Play Curling（贪心+签到）

#include <bits/stdc++.h>using namespace std;// #define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 6e6 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m; cin >> n >> m;vector<PII> a(n + m + 1);set<int> st;for (int i = 1; i <= n; i ++ ){cin >> a[i].first;a[i].second = 0;}for (int i = n + 1; i <= n + m; i ++ ){cin >> a[i].first;a[i].second = 1;st.insert(a[i].first);}sort(a.begin() + 1, a.end());int ans = 0, tmp = 0;for (int i = 1; i <= n + m; i ++ ){if (a[i].second == 0){if (st.count(a[i].first) == 0) tmp ++ ;}else{ans = max(ans, tmp);tmp = 0;}}ans = max(ans, tmp);if (ans == 0) cout << "Impossible\n";else cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

M - Monster Hunter（树形dp）

  • 参考：2020 ICPC南京 M.Monster Hunter(树形背包)
#include <bits/stdc++.h>
#include <bits/extc++.h>using namespace std;
using namespace __gnu_pbds;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 2e5 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;vector<vector<int>> g(n + 1);for (int i = 2; i <= n; i ++ ){int x; cin >> x;g[i].push_back(x);g[x].push_back(i);}vector<int> a(n + 1), sz(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];vector<vector<vector<int>>> dp(2, vector<vector<int>>(n + 1, vector<int>(n + 1, INF)));function<void(int, int)> dfs = [&](int u, int fa){dp[0][u][0] = 0;dp[1][u][1] = a[u];for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa) continue;dfs(j, u);}sz[u] = 1;for (int i = 0; i < g[u].size(); i ++ ){int v = g[u][i];if (v == fa) continue;for (int j = sz[u]; j >= 0; j -- ){for (int k = sz[v]; k >= 0; k -- ){dp[0][u][j + k] = min(dp[0][u][j + k], dp[0][u][j] + min(dp[0][v][k], dp[1][v][k]));dp[1][u][j + k] = min(dp[1][u][j + k], dp[1][u][j] + min(dp[0][v][k], dp[1][v][k] + a[v]));}}sz[u] += sz[v];}};dfs(1, -1);for (int i = 0; i <= n; i ++ ){if (i != 0) cout << ' ';cout << min(dp[0][1][n - i], dp[1][1][n - i]);}cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

这篇关于2020年ICPC南京站 补题记录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1130892。

相关文章

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...
记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪（un-tracking）文件重新跟踪（re-tracking）文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法，现在我们已经有了一个仓库，并从这个仓
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
perl的学习记录——仿真regression

perl的学习记录——仿真regression

1 记录的背景 之前只知道有这个强大语言的存在，但一直侥幸自己应该不会用到它，所以一直没有开始学习。然而人生这么长，怎就确定自己不会用到呢？ 这次要搭建一个可以自动跑完所有case并且打印每个case的pass信息到指定的文件中。从而减轻手动跑仿真，手动查看log信息的重复无效低质量的操作。下面简单记录下自己的思路并贴出自己的代码，方便自己以后使用和修正。 2 思路整理 作为一个IC d
阅读更多...
SSM项目使用AOP技术进行日志记录

SSM项目使用AOP技术进行日志记录

本步骤只记录完成切面所需的必要代码 本人开发中遇到的问题： 切面一直切不进去，最后发现需要在springMVC的核心配置文件中中开启注解驱动才可以，只在spring的核心配置文件中开启是不会在web项目中生效的。 之后按照下面的代码进行配置，然后前端在访问controller层中的路径时即可观察到日志已经被正常记录到数据库，代码中有部分注释，看不懂的可以参照注释。接下来进入正题 1、导入m
阅读更多...
flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位 一、背景二、定位问题三、解决方法 一、背景 flume系列之：定位flume没有关闭某个时间点生成的tmp文件的原因，并制定解决方案在博主上面这篇文章的基础上，在机器内存、cpu资源、flume agent资源都足够的情况下，flume agent又出现了tmp文件无法关闭的情况 二、
阅读更多...
Linux常用工具与命令日常记录（长期更新）

Linux常用工具与命令日常记录（长期更新）

Linux常用工具与命令日常记录（长期更新） 目录 1.本地复制到远程2.Linux压缩拆包与解压3.生成随机密码4.ubuntu默认Python版本设置5.计算当前文件夹中文件数量6.windows中编写shell脚本，在Linux运行出错7.history 历史命令显示时间用户8.Ubuntu18.04设置源、网卡9.Ubuntu18.04设置网卡10.Ubuntu：自定义开
阅读更多...
Excel和Word日常使用记录：

Excel和Word日常使用记录：

Excel使用总结 表格颜色填充： 合并单元格： 选中你要合并的单元格区域。按下快捷键 Alt + H，然后松开这些键。再按下 M，接着按 C。这个组合键执行的操作是：Alt + H：打开“主页”选项卡。M：选择“合并单元格”选项。C：执行“合并并居中”操作。 插入行： 在Excel中，插入一行的快捷键是：Windows：选择整行（可以点击行号）。按下 Ctrl + Sh
阅读更多...
野火霸天虎V2学习记录

野火霸天虎V2学习记录

文章目录 嵌入式开发常识汇总1、嵌入式Linux和stm32之间的区别和联系2、stm32程序下载方式3、Keil5安装芯片包4、芯片封装种类5、STM32命名6、数据手册和参考手册7、什么是寄存器、寄存器映射和内存映射8、芯片引脚顺序9、stm32芯片里有什么10、存储器空间的划分11、如何理解寄存器说明12、如何操作寄存器的某一位 STM32F407芯片学习1、stm32单片机启动流程s
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2