题目大意 题目链接 跟你n个(x, y) 每一组， 都满足x_i < x_i + 1 && y_i < y_i + 1，问如何尽可能分更少的组， 输出每一个分到第几组（组号从1开始） 分析 按x从小到大排序。 Dilworth定理： 最小组数等于y的最长下降子序列长度 最长下降子序列 用二分优化的dp求法中， dp[i]表示长度为i的最长下降子序列的最后一个数， 显然， 我们dp[i]越大越好， 当前为a[i] 所以我们就用二分找到dp数组中第一个比a[i]小的数(位置为cnt)， 如果有， 就把dp[cnt] = a[i] ，， 如果没有， cnt = ++l...

题目大意 题目链接 有n个元素（1-n）， 第i个元素能量值为ai， 可以选择至少k的元素施法， 消耗为选择的k个元素所组成的极值的差，每个元素当且仅当被用1次的最小消耗， 分析 首先排序。 f[i] 表示使用前i（包括第i）个元素的最小消耗 然后维护min(f[j - 1] - a[j]) 即可。 代码 /* power by Solo_Dance */ #include <bits/stdc++.h> #define eps 1e-8 using namespace std; #define ms(a, b) memset((a), (b), sizeof(a)) typ...

题目大意 题目链接 有n个物品， 每个物品有a，b两个属性， A， B两人一人一次拿一个（A获得a属性， B获得b属性）， A先拿， 求A如何拿能使 sumA - sumB越大， B如何拿能使 sumB - sumA越大， 求出最优策略下， A， B分别拿哪些物品。 分析 贪心， 比赛的时候试了两个策略不对（这两个策略是我猜的）， 没有找到理论依据。 假设A拿B的物品1， B拿A的物品2 sumA' = sumA - a2 + a1 sumB' = sumB - b1 + b2 使得sumA' - sumB' >= sumA - sumB sumA - a2 + a1 + b1 - b...

题目大意 题目链接 给你一颗n个节点的树， 每个节点有黑白两种颜色， 问有多少条不同的简单路径， 恰好只经过一个黑点。 注： 1. <u, v> 和 <v, u> 视为相同取法。2. 简单路径为两点的最短路。 分析 两种情况， 一种是以黑点为端点， 另一种黑点不为端点。 可以先求出白点连通块以及每个连通块的点的数量sum[cnt]。 然后，以黑点为端点的情况是 ans += sum[i] | 1 <= i <= cnt， 黑点不为端点的情况ans += sum[i] * sum[j] | 1 <= i <= cnt | i + 1 <=...

题目大意 汉诺塔， 伪代码为 Function Hanoi(n,a,b,c) if n==1 then print(a+'->'+c) else Hanoi(n-1,a,c,b) print(a+'->'+c) Hanoi(n-1,b,a,c) end if end Function 统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。 分析 一开始硬生生找规律， 呜呜呜呜呜， 找的心态爆炸最后终于找出来...

1.用一键测试脚本Superspeed.sh 测试服务器到国内的速度 wget https://raw.githubusercontent.com/oooldking/script/master/superspeed.sh chmod +x superspeed.sh ./superspeed.sh测试截图： 可以发现下载速度很好（毕竟1M宽带）， 就是上传速度差了点。 2.用一键检测VPS的CPU、内存、负载、IO读写、机房带宽等的脚本：bench.sh 命令1： wget -qO- bench.sh | bash 或者 curl -Lso- bench.sh | bash 命令2： wg...

title: 2019牛客国庆集训派对 E-Partial Sum （绝对值的特殊性）categories: 2019牛客国庆集训派对top: falsetags: acm 绝对值的特殊性 思维 题目大意 题目链接给定长为n的数组， 找到m组(L, R)， 使得|sum（L,R）| - C的和最大， 其中C为常数（输入中给出）， 每个(L, R)只出现一次。 思路 求区间前缀和， 因为绝对值的特性， |sumi - sumj = sumj - sumi| 所以前后减的顺序没关系， 他也没要求具体是那m组， 所以sort后 最大减最小就可。 AC代码 #include <bits/...

title: 2019牛客国庆集训派对 H-Highway (dijk求树的直径（当然还有更优的）) categories: 2019牛客国庆集训派对 top: false tags: acm 树的直径 题目大意 题目链接 n个点从1-n, 有(n - 1)条边连接。 现在要重新修（n - 1）条路， 修i 到 j 所用的代价为i到j的最短路， 问最多的代价是多少 分析 就是求树的直径， 然后跑两边最短路求其他点到直径两端点的最短路， 最后把最大值加起来就可。 AC代码 #include using namespace std; typedef long long ll; ...

https://stusdnueducn-my.sharepoint.com/:b:/g/personal/201811010121_stu_sdnu_edu_cn/EQ_gRkqRBUNHlawcHdLKwdsBg_upz0QjAlxiV-jsRqMzDQ?e=GBmb0s

题解下载地址 ： [https://stusdnueducn-my.sharepoint.com/:b:/g/personal/201811010121_stu_sdnu_edu_cn/EQ_gRkqRBUNHlawcHdLKwdsBg_upz0QjAlxiV-jsRqMzDQ?e=GBmb0s]

题解下载地址：https://www.icpc.camp/contests

搬家啦， 请访问新博客地址： solodance.top

集训室给我的是，最真挚的感动。 第一年参加就拿到奖牌，挺幸运的吧，也挺开心的。 大大的教训 其实都是老教训了，却还是一直翻车。 首先就是改了一点就交了，然后在WA一次才细心的好好看一遍程序。 还有爆int，刻骨铭心却还是不改。 自我检讨一下： 对我自己太自信了，当时没有一个人A的题， 我却自以为找到了正确思路，然后浪费了很多时间，最后A的人还不到两位数，到底是什么懵逼了我的双眼！！！！！！！！！！！！！！ 不知道为什么，精力不能长时间集中，好难过。 我好菜啊。 小小感悟 这一年在集训队待的挺快乐的，虽然我入队晚，但是确实感到了集训队的温馨（最重要的是有女...