当前位置： 首页 > news >正文

2020年ICPC南京站 补题记录

news 来源：原创 2024/9/21 8:36:45

文章目录

  • 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;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Kevin‘s notes about Qt---Episode 2 线程通信
  • 突破编程_C++_设计模式(组合模式)
  • C#知识|加强面向对象编程的认识
  • 2024年【氧化工艺】考试及氧化工艺最新解析
  • docker run的--shm-size是干嘛用的
  • 聊一下Jetpack AppStartUp的使用和原理。
  • ClimODE——使用神经网络ODE 进行天气预报
  • 日志管理与时钟同步
  • 11 Java 方法引用、异常处理、Java接口之函数式编程（接口知识补充Function＜T,R＞、BiFunction＜T, U, R＞和自定义泛型接口）
  • 14个中国各朝代地图图源分享
  • YoloV9改进策略：下采样改进|集成GCViT的Downsampler模块实现性能显著提升|即插即用
  • 燃油车淘汰倒计时开始了？
  • 音视频入门基础：WAV专题（8）——FFmpeg源码中计算WAV音频文件AVStream的time_base的实现
  • echarts处理y轴最大小值根据数据动态处理、分割数和是否从0开始
  • 衡石科技产品手册-指标分析
  • 【Leetcode】101. 对称二叉树
  • 实现windows 窗体的自己画，网上摘抄的，学习了
  • hadoop集群管理系统搭建规划说明
  • MySQL主从复制读写分离及奇怪的问题
  • nginx 负载服务器优化
  • Nginx 通过 Lua + Redis 实现动态封禁 IP
  • PHP的类修饰符与访问修饰符
  • Sequelize 中文文档 v4 - Getting started - 入门
  • SQL 难点解决：记录的引用
  • tweak 支持第三方库
  • 机器学习 vs. 深度学习
  • 如何打造100亿SDK累计覆盖量的大数据系统
  • 腾讯视频格式如何转换成mp4 将下载的qlv文件转换成mp4的方法
  • 通过几道题目学习二叉搜索树
  • 用Python写一份独特的元宵节祝福
  • 在weex里面使用chart图表
  • Python 之网络式编程
  • ​​​​​​​GitLab 之 GitLab-Runner 安装，配置与问题汇总
  • ## 基础知识
  • #NOIP 2014# day.1 T3 飞扬的小鸟 bird
  • #鸿蒙生态创新中心#揭幕仪式在深圳湾科技生态园举行
  • $.each()与$(selector).each()
  • (09)Hive——CTE 公共表达式
  • (android 地图实战开发)3 在地图上显示当前位置和自定义银行位置
  • （pt可视化）利用torch的make_grid进行张量可视化
  • (附源码)计算机毕业设计SSM智能化管理的仓库管理
  • (计算机网络)物理层
  • （提供数据集下载）基于大语言模型LangChain与ChatGLM3-6B本地知识库调优：数据集优化、参数调整、Prompt提示词优化实战
  • （一）Java算法：二分查找
  • (转) RFS+AutoItLibrary测试web对话框
  • (最完美)小米手机6X的Usb调试模式在哪里打开的流程
  • .bat批处理（十）：从路径字符串中截取盘符、文件名、后缀名等信息
  • .NET WebClient 类下载部分文件会错误？可能是解压缩的锅
  • .NET 依赖注入和配置系统
  • .NET委托：一个关于C#的睡前故事
  • @Mapper作用
  • [ C++ ] STL---string类的模拟实现
  • [ 手记 ] 关于tomcat开机启动设置问题
  • [ 数据结构 - C++]红黑树RBTree
  • [12] 使用 CUDA 进行图像处理