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。

相关文章

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...
将sqlserver数据迁移到mysql的详细步骤记录

将sqlserver数据迁移到mysql的详细步骤记录

《将sqlserver数据迁移到mysql的详细步骤记录》：本文主要介绍将SQLServer数据迁移到MySQL的步骤,包括导出数据、转换数据格式和导入数据,通过示例和工具说明,帮助大家顺利完成... 目录前言一、导出SQL Server 数据二、转换数据格式为mysql兼容格式三、导入数据到MySQL数据
阅读更多...
关于rpc长连接与短连接的思考记录

关于rpc长连接与短连接的思考记录

《关于rpc长连接与短连接的思考记录》文章总结了RPC项目中长连接和短连接的处理方式,包括RPC和HTTP的长连接与短连接的区别、TCP的保活机制、客户端与服务器的连接模式及其利弊分析,文章强调了在实... 目录rpc项目中的长连接与短连接的思考什么是rpc项目中的长连接和短连接与tcp和http的长连接短
阅读更多...
Oracle查询优化之高效实现仅查询前10条记录的方法与实践

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》：本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI
阅读更多...
Python MySQL如何通过Binlog获取变更记录恢复数据

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志（Binlog）获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat
阅读更多...
Servlet中配置和使用过滤器的步骤记录

Servlet中配置和使用过滤器的步骤记录

《Servlet中配置和使用过滤器的步骤记录》：本文主要介绍在Servlet中配置和使用过滤器的方法,包括创建过滤器类、配置过滤器以及在Web应用中使用过滤器等步骤,文中通过代码介绍的非常详细,需... 目录创建过滤器类配置过滤器使用过滤器总结在Servlet中配置和使用过滤器主要包括创建过滤器类、配置过滤
阅读更多...
正则表达式高级应用与性能优化记录

正则表达式高级应用与性能优化记录

《正则表达式高级应用与性能优化记录》本文介绍了正则表达式的高级应用和性能优化技巧,包括文本拆分、合并、XML/HTML解析、数据分析、以及性能优化方法,通过这些技巧,可以更高效地利用正则表达式进行复杂... 目录第6章：正则表达式的高级应用6.1 模式匹配与文本处理6.1.1 文本拆分6.1.2 文本合并6
阅读更多...
python与QT联合的详细步骤记录

python与QT联合的详细步骤记录

《python与QT联合的详细步骤记录》：本文主要介绍python与QT联合的详细步骤,文章还展示了如何在Python中调用QT的.ui文件来实现GUI界面,并介绍了多窗口的应用,文中通过代码介绍... 目录一、文章简介二、安装pyqt5三、GUI页面设计四、python的使用python文件创建pytho
阅读更多...
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、路由模块添加前缀 四、中间件
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2