夏令营提高班上午上机测试 Day 2 解题报告
发布日期:2022-03-11 15:03:31 浏览次数:9 分类:技术文章

本文共 7794 字,大约阅读时间需要 25 分钟。

那一天,日照一中夏令营数据结构提高班的同学们终于想起了,被Day2上午的三道题支配的恐惧……
 
是的。。这一天的题有点难想。。
本来打算前天写这篇随笔,然而前天在机房和同学打luogu月赛……
昨天晚上写着写着睡着了。。GG
 
  
声明:标程全部来源于GTY哥哥,并非本人所写。
 
 
T1:债务
题目描述
小G有一群好朋友,他们经常互相借钱。假如说有三个好朋友A,B,C。A欠B20元,B欠C20元,总债务规模为20+20=40元。小G是个追求简约的人,他觉得这样的债务太繁杂了。他认为,上面的债务可以完全等价为A欠C20元,B既不欠别人,别人也不欠他。这样总债务规模就压缩到了 20 元。
现在给定n个人和m条债务关系。小G想找到一种新的债务方案,使得每个人欠钱的总数不变,或被欠钱的总数不变(但是对象可以发生变化),并且使得总债务规模最小。
输入格式
输入文件第一行两个数字 n, m,含义如题目所述。
接下来 m 行,每行三个数字 a
i, b
i, c
i ,表示 a
i欠 b
i的钱数为 c
i
注意,数据中关于某两个人 A 和 B 的债务信息可能出现多次,将其累加即可。
如”A 欠 B 20 元”、”A 欠 B 30 元”、”B 欠 A 10 元”,其等价为”A 欠 B 40 元”。
输出格式
输出文件共一行,输出最小的总债务规模。
样例输入 1
5 3
1 2 10
2 3 1
2 4 1
样例输出 1
10
样例输入 2
4 3
1 2 1
2 3 1
3 1 1
样例输出 2
0
数据范围
对于 30% 的数据,1 ≤ n ≤ 10,1 ≤ m ≤ 10。
对于 60% 的数据,1 ≤ n ≤ 100, 1 ≤ m ≤ 10
4
对于 80% 的数据,1 ≤ n ≤ 10
4,1 ≤ m ≤ 10
4
对于 100% 的数据,1 ≤ n ≤ 10
6,1 ≤ m ≤ 10
6
对于所有的数据,保证 1 ≤ a
i, b
i≤ n, 0 < c
i≤ 100。
 
说简单点,就是让我们简化一下这些欠债和被欠债的关系,使得每个人欠钱或者被欠钱的总钱数不变,并且总债务之和最小。
这题在考场上想了好长时间,愣是没想出应该用什么做。。不过应该有一个结论能想出来:无论有多少欠钱和被欠钱的关系,债务规模应该是守恒的。这也就是说,我们优化之前和优化之后的债务规模应该是相等的。
我们设可能的最小债务规模为 总欠钱量/总被欠钱量,它应该被满足最优性和可行性才能作为一个最小债务规模。
通过画图模拟还钱的过程我们可以发现,无论我们怎样考虑等价债务关系,总会有一个方案,使得没有任何方案会比这个方案所等价出的债务规模更小。
同时我们发现,这应该是最小债务规模。如果债务规模还要比这更小,那钱根本就凑不齐,也就不符合题意了。
m只有10^6的规模 ,可以考虑O(m)去模拟这个过程。
我们假设每个人初始都有一定量的钱。
其实没必要非得给所有人加一些钱,初值为0就好。我们要计算的是等价到的债务而不是所有人具体有多少钱。
然后我们读入债务关系,如果a欠b c元钱,那么我们就模拟着让a去还给b c元钱,可以开一个数组记录w每个人初始拥有的钱数,每次读到a欠b c元,就让w[a]-=c,w[b]+=c,这样就完成了一次还钱。
全部操作完之后,也就是相当于所有人都对自己的债主还了钱之后,我们去统计每个人剩下的钱。
如果有人现在手里还剩下钱,那么统计这些钱的总值,这个值就是最小的债务规模。
这样做为什么正确?可能这样做有一点抽象,但它的确是对的。
想一下我们最初的目的,我们要统计的是最小的债务规模,而不用去关心到底要怎么去等价。如果有人把这个题想成一个图论题,那可能就gg了。 

  

#include 
#include
#include
#include
#include
using namespace std;const int max_n = 1e6 + 10;const int max_m = 1e6 + 10;int a[max_n];inline int getnum(){ int ans = 0; bool flag = false; char c; while ((c = getchar()) == ' ' || c == '\n' || c == '\r'); if (c == '-') flag = true; else ans = c - '0'; while (isdigit(c = getchar())) ans = ans * 10 + c - '0'; return ans;}int main(){ freopen("debt.in", "r", stdin); freopen("debt.out", "w", stdout); int n = getnum(); int m = getnum(); for (int i = 1; i <= m; i++) { int aa, bb, c; aa = getnum(); bb = getnum(); c = getnum(); a[aa] += c; a[bb] -= c; } int ans = 0; for (int i = 1; i <= n; i++) if (a[i] > 0) ans += a[i]; cout << ans << endl;}

 

 
 
 
T2:排列
题目描述
小 G 喜欢玩排列。现在他手头有两个 n 的排列。n 的排列是由 0, 1, 2, ..., n − 1这 n 的数字组成的。对于一个排列 p,Order(p) 表示 p 是字典序第 Order(p) 小的排列(从 0 开始计数)。对于小于 n! 的非负数 x,Perm(x) 表示字典序第 x 小的排列。
现在,小 G 想求一下他手头两个排列的和。两个排列 p 和 q 的和为 sum = Perm((Order(p) + Order(q))%n!)。
输入格式
输入文件第一行一个数字 n,含义如题。
接下来两行,每行 n 个用空格隔开的数字,表示小 G 手头的两个排列。
输出格式 
输出一行 n 个数字,用空格隔开,表示两个排列的和。
样例输入 1
2
0 1
1 0
样例输出 1
1 0
样例输入 2
3
1 2 0
2 1 0
样例输出 2
1 0 2
数据范围
1、2、3、4 测试点,1 ≤ n ≤ 10。
5、6、7 测试点,1 ≤ n ≤ 5000,保证第二个排列的 Order ≤ 10
5
8、9、10 测试点,1 ≤ n ≤ 5000。
 
Order和Perm可以理解为,他俩互为“反函数”。这句话怎么解释呢?Order(x)传入一个排列,返回的是这个排列的字典序。Perm(x)传入的是一个字典序的值,返回的值是一个排列。
暴力做法很简单,可以拿40分。
STL里头有一个algorithm头文件,里面有一个可以求全排列的函数next_premutation,那么我们根据题意去模拟这个过程就可以了。
那么我们该如何改进这个暴力做法呢?对于5,6,7测试点,数据范围给出了提示:保证第二个排列的Order≤10^5,我们可不可以以此为突破口进行探究呢?
当然可以!我们可以用next_permutaition计算出第二个排列的Order,然后对排列一做Order次next_permutaition,便可大大减少计算量。
你看,稍微一考虑,暴力就能拿70了,岂不是美滋滋。
好了,说正解。
很显然对于这道题,我们应该要尽量在O(n)的时间复杂度内求出一个排列的字典序的值。
我们设一个数组rank[n],表示从n位置上的数字在a[1]~a[n]上的排名,从0开始计数。
然而n很大,我们算出来的Order也必定很大,所以直接计算是不可行的。
什么?高精度?。。。。你不嫌麻烦吗?
喂。。我只是说高精度麻烦,并不是说不让你们用啊喂!
怎么用?我觉得得稍微改改。具体的请参见代码。你可以将两个数相加,但不能将两个排列相加。所以我们可以把原先的排列转化为一个Rank数组,两个排列的Rank用一个类似高精度加法的方式相加。最后通过这个新的Rank数组就可以推出答案的排列。
#include 
#include
#include
#include
#include
#include
using namespace std;const int max_n = 5e4 + 10;int cnt[max_n], p1[max_n], p2[max_n], pp1[max_n], pp2[max_n], ans[max_n];int n;inline int getnum(){ int ans = 0; char c; bool flag = false; while ((c = getchar()) == ' ' || c == '\n' || c == '\r'); if (c == '-') flag = true; else ans = c - '0'; while (isdigit(c = getchar())) ans = ans * 10 + c - '0'; return ans * (flag ? -1 : 1);}int main(){ freopen("perm.in", "r", stdin); freopen("perm.out", "w", stdout); n = getnum(); for (int i = n; i >= 1; i--) p1[i] = getnum(); for (int i = n; i >= 1; i--) p2[i] = getnum(); for (int i = 1; i <= n; i++) for (int j = 1; j < i; j++) if (p1[j] < p1[i]) pp1[i]++; for (int i = 1; i <= n; i++) for (int j = 1; j < i; j++) if (p2[j] < p2[i]) pp2[i]++; for (int i = 2; i <= n; i++) { ans[i] += pp1[i] + pp2[i]; ans[i + 1] += ans[i] / i; ans[i] %= i; } for (int i = n; i >= 1; i--) { int _ = -1; while (ans[i] >= 0) { _++; if (!cnt[_]) ans[i]--; } printf("%d ", _); cnt[_] = 1; }}

 

   
int _ ...你是真滴皮
 
T3:剪树枝
(据说做完题后,有同学在群里高呼“我要砍掉rzyz所有的苹果树!”
(这可能是我做的第一道树形DP题
(这段掐了别播
 
题目描述
rzyz 有一棵苹果树。苹果树有 n 个节点(也就是苹果),n − 1 条边(也就是树枝)。调皮的小 G 爬到苹果树上。他发现这棵苹果树上的苹果有两种:一种是黑苹果,一种是红苹果。小 G 想要剪掉 k 条树枝,将整棵树分成 k + 1 个部分。他想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝的方案?
输入格式
第一行一个数字 n,表示苹果树的节点(苹果)个数。
第二行一共 n − 1 个数字 p
0, p
1, p
2, p
3, ..., p
n-2,p
i 表示第 i + 1 个节点和 p
i节点之间有一条边。注意,点的编号是 0 到 n − 1。
第三行一共 n 个数字 x
0, x
1 , x
2 , x
3 , ..., x
n-1 。如果 x 是 1,表示 i 号节点是黑苹果;如果 x 是 0,表示 i 号节点是红苹果。
 
输出格式
输出一个数字,表示总方案数。答案对 10
9+ 7 取模。
样例输入 1
3
0 0
0 1 1
样例输出 1
2
样例输入 2
6
0 1 1 0 4
1 1 0 0 1 0
样例输出 2
1
样例输入 3
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
样例输出 3
27
数据范围
对于 30% 的数据,1 ≤ n ≤ 10。
对于 60% 的数据,1 ≤ n ≤ 100。
对于 80% 的数据,1 ≤ n ≤ 1000。
对于 100% 的数据,1 ≤ n ≤ 10
5
对于所有数据点,都有 0 ≤ p
i≤ n − 1,x
i = 0 或 x
i = 1。
特别地,60% 中、80% 中、100% 中各有一个点,树的形态是一条链。
 
noip式懵逼.jpg
如果不是正解告诉我要用树形DP做,我一定想不起来。。。
我直接按着课件上的思路说吧……我DP学瞎了。
我们先考虑暴力做法,搜索要删除的边,然后再检查每一部分是不是满足有且只有一个黑点。
正解是树上DP,也称树形DP。
既然是DP问题,那么我们就要考虑状态的转移。
影响我们转移的因素有哪些?
1.当前位于哪一棵子树
2.当前联通块中有没有黑苹果。
设dp[i][0]表示以i为根的这棵子树,最上面的那个联通块,没有黑点的方案数。dp[i][1]表示以i为根的子树,最上面那个联通块有一个黑点的方案数。
这样,初状态便是dp[i][0]=1,dp[i][1]=0。
对于每一个dp[i][1],有两种情况:
    1. i点是黑色的,所有i的子树v和i相接,必须接dp[v][0]。
    2. i点是红色的,所有i的子树,有一棵接dp[v][1],其余的接dp[v][0]。
对于dp[i][0],有三种情况:
    1. i点是黑色的,所有i的子树v和i相接,必须接dp[v][0],并且i上面的那条边得割断。
    2. i点是红色的,所有i的子树,有一棵接dp[v][1],其余的接dp[v][0],且i上面的那条边得割断。
    3. i点是红色的,所有i的子树v和i相接,都接dp[v][0]。
总体来说就分两种情况:
    1. 子树全都用dp[v][0]。
    2. 子树一棵用dp[v][1],其余用dp[v][0]。
先用dp[i][0]存第一种情况,dp[i][1]存第二种情况
对于第一种情况,只需要把所有的dp[v][0]乘起来就可以了。
对于第二种情况,一种笨办法是枚举哪一个是dp[v][1],然后再乘上其余的dp[v][0]。这样的话效率最坏到O(n
2)。
#include 
#include
#include
#include
#include
using namespace std;#define ll long longconst int MAXN = 1e5 + 10;const int MOD = 1e9 + 7;ll f[MAXN][2];int point[MAXN] = {
0}, nxt[MAXN * 2] = {
0}, v[MAXN * 2] = {
0}, tot = 0;bool color[MAXN] = {
0};int n;inline void addedge(int x, int y){ tot++; nxt[tot] = point[x]; point[x] = tot; v[tot] = y;}void dfs(int now, int father){ f[now][0] = 1; f[now][1] = 0; for (int tmp = point[now]; tmp; tmp = nxt[tmp]) if (v[tmp] != father) { dfs(v[tmp], now); f[now][1] = (f[now][1] * f[v[tmp]][0]) % MOD; f[now][1] = (f[now][1] + f[now][0] * f[v[tmp]][1]) % MOD; f[now][0] = (f[now][0] * f[v[tmp]][0]) % MOD; } if (color[now]) f[now][1] = f[now][0]; else f[now][0] = (f[now][0] + f[now][1]) % MOD;}int main(){ freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); scanf("%d", &n); for (int i = 2; i <= n; i++) { int x; scanf("%d", &x); addedge(i, x + 1); addedge(x + 1, i); } for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); if (x == 1) color[i] = true; else color[i] = false; } dfs(1, 0); cout << f[1][1] << endl;}

 

 
 
啊。。如果有哪位大佬能想出T3更好的解释方法的话请在评论区留言或者私信我,本蒟蒻表示不胜感激。。
 

转载于:https://www.cnblogs.com/OIerShawnZhou/p/7298762.html

转载地址:https://blog.csdn.net/weixin_30267785/article/details/99125415 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:ScheduledThreadPoolExecutor的scheduleAtFixedRate方法探究
下一篇:Leetcode: Shuffle an Array

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月26日 08时40分16秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

华为云welink成像是反的_华为发布智能办公神器WeLink,可连接会议室开会,还可一键遥控报销和智能翻译... 2019-04-21
唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱” 2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件 2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人... 2019-04-21
this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历 2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具 2019-04-21
英特尔cpu发布时间表_被嘲讽的英特尔核显,强大能力其实超乎你的想象 2019-04-21
chi2inv函数 matlab_MATLAB概率和统计(2) 2019-04-21
lisp修改上一个图素_在Windows上安装Haskell 2019-04-21
ad19 导出step 没有pcb_几款主流PCB软件哪个最好用,你用过几款? 2019-04-21
json mysql 字段 默认值_Newtonsoft.Json 六个超简单又实用的特性,值得一试 【上篇】... 2019-04-21
ocdma相干非相干_《Acconeer 60GHz脉冲相干雷达芯片:A111》 2019-04-21
修改表格字体颜色_Excel技巧:Excel如何修改字体颜色 2019-04-21
native react 变颜色 点击_React Native主动更改StackNavigator标头颜色 2019-04-21
prism项目搭建 wpf_WPF MVVM使用prism4.1搭建 2019-04-21
python发微信红包群_用Python实现微信自动化抢红包,再也不用担心抢不到红包了... 2019-04-21
python中func自定义函数_Python函数之自定义函数&作用域&闭包 2019-04-21