anthony1314 - 个人主页动态

2019-10-31 16:32

已编辑

CCPC-Wannafly Summer Camp 2019 Day1 https://vjudge.net/contest/313046 完成进度 4/15 2019牛客多校 https://ac.nowcoder.com/acm/contest/vip-index 第二场 F  H  2/4  差 A B 第三场 B F H 3/4  差J 第四场 J C A K  4/4 第五场 A G B H  4/4 第六场 A J B   D 4/5 差G 第七场 A B D J   C E 6/6   银联高校极客挑战赛 初赛 https://www.jis...

0 点赞评论收藏

2019-10-31 16:33

已编辑

阿里巴巴_淘特技术部_开发工程师

hdu6586 String【贪心】【模拟】【2019 Multi-University Training Contest 1】

题意: 给你一个长度不超过 长度的只包含小写字母的字符串s，和一个整数k，要你求出长度为k的s的字典序最小子序列。 且给你两个长度为26的L数组, R数组作为限制条件， L[0] 表示 字符 'a' 在 子序列中的最少个数，  R[0] 表示 字符 'a' 在 子序列中的最多个数，依次类推。 题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6586 题解： 先构造出某个位置后每个字母的个数，用一个动态数组存每个字母的各个位置。 一位位地构造答案字符串，每次贪心地加能加入的最小的字符 (判断能否加入只要判断加入之后原字符串剩下的后缀中...

0 点赞评论收藏

2019-10-31 16:33

已编辑

阿里巴巴_淘特技术部_开发工程师

hdu6581 Vacation 【贪心】【2019 Multi-University Training Contest 1】

题意: 有n+1辆车，在一条单车道上（假设车道方向从左到右，车头向右）， 在终点线的左边，他们按照1，2，....，n，n+1  从右到左在终点线的左边,每辆车有三个属性 s(车头到终点线的距离), l（车子本身的长度）, v （车的最大速度），不能超车，请问第n+1辆车最快什么时候车头能碰到终点线。 题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6581 题解： 最终通过终点线的时候，一定是一个车后面堵着剩余所有的车，不同车超过终点线停止的位置也不同，那么影响时间的就只有最前面这辆车。最前面这辆车没有被其他车限制，所以他可以按他的最...

0 点赞评论收藏

2019-10-31 16:33

已编辑

阿里巴巴_淘特技术部_开发工程师

hdu 6582 Path【最短路】【最小割】【2019 Multi-University Training Contest 1】

题意: 给你一个n个点，m条边的有向图。让你以最小的代价删除一些边使得从点1到点n的最短路变长，删掉一条边的代价为这条边的长度，不用考虑删完之后点1是否能到达点n。 题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6582 题解： 要使最短路变长，那么我们就要删掉最短路的边，我们可以知道点1到点n也许不止一条最短路，那么这些最短路可以构成一个有向无环图(DAG)，我们要以最小代价破坏这个有方向,就是求这个图的最小割。 怎么判断这条边属不属于最短路呢，首先用Dijkstra算法求出 源点到终点的最短路。然后分别求出源点到每个点的最短距离...

0 点赞评论收藏

2019-10-31 16:34

已编辑

阿里巴巴_淘特技术部_开发工程师

Codeforces 1197D Yet Another Subarray Problem 【DP】【最大子区间和】

题意: 给你一个长度为n的a数组，要你去求出 最大的值。 题目链接： http://codeforces.com/contest/1197/problem/D 题解： 我们不难看出这道题求的是最大子区间和，但是加了个限制条件， 求的区间和必须减去   (区间的长度 / m) 向上取整的值。 求最大子区间和我们可以用DP的思想 O(n) 求出来，这道题暴力写过不了 我们可以做一个预处理，用一个新的数组存a数组每隔m个数减去k后的值，然后我们我可以枚举右端点，后对于长度为qm+p的区间，按p分类，直接求最大子区间和，这样求的值，长度都会减去相应的k的倍数。 AC_code: #...

0 点赞评论收藏

2019-10-31 16:34

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第二场） F Partition problem 【DFS】

题意: 有 2*n 个人，要把2*n个人平均分配到红队和白队，现在输入一个2n * 2n的矩阵， 第a行第b列代表  第a个人在红队，第b个人在白队的所产生竞争价值，定义竞争价值总和为所有不在同一队的两个队员的竞争价值总和，现在要你求出最大竞争价值总和。 题目链接： https://ac.nowcoder.com/acm/contest/882/F 题解： 直接暴力DFS， 时间复杂度 最大C(n, 2*n) * n AC_code: /* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */ #incl...

0 点赞评论收藏

2019-10-31 16:34

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第二场） H Second Large Rectangle 【次大全1子矩阵和】【单调栈】

题意: 给你一个n*m的只有 1 和 0 的矩阵， 求全是1的第二大的子矩阵的面积。 题目链接： https://ac.nowcoder.com/acm/contest/882/H 题解： 听说是陈年老题，可惜我不会 比赛一直在改就是不知道哪里错了qaq 比赛后看到有人用暴力写法A过了，惊了，我copy了他的代码交了一发，tle,牛客的服务器让我觉得好迷 然后看了队友的单调栈写法发现全是 1000*1000 个 1 暴力肯定会T  好迷啊 做法： 首先，先预处理，把h[i][j] 作为以h[i][j]作为最低点的连续的1的长度， 如果该点为0，则长度为 0。 然后对每一行...

0 点赞评论收藏

2019-10-31 16:35

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） J Fraction Comparision 【签到题】

题意： 输入x, a, y, b， 求  和    的大小比较 题目链接： https://ac.nowcoder.com/acm/contest/881/J 题解： AC_code: #include<bits/stdc++.h> using namespace std; #define ll long long int main() { ll x, y, a, b; while(cin>>x>>a>>y>>b) { ll xx = x/a; ll yy = ...

0 点赞评论收藏

2019-07-24 17:51

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） J Fraction Comparision 【签到题】

0 点赞评论收藏

2019-10-31 16:35

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） F Random Point in Triangle 【数学期望】

题意:  给出三角形三个点的坐标，求三角形内随机选点到与三边形成的三角形的最大值的期望 * 36 。 题目链接： https://ac.nowcoder.com/acm/contest/881/F 题解： 听群里的聚聚说是随机跑的点跑出的规律  E = S*22/36  （公式） AC_code: #include<bits/stdc++.h> #define ll long long using namespace std; int main() { ll x1, y1, x2, y2, x3, y3; while(cin>>x1>>...

0 点赞评论收藏

2019-07-24 17:51

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） F Random Point in Triangle 【数学期望】

0 点赞评论收藏

2019-10-31 16:36

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） E ABBA 【DP】

题意： 问你长度为2 * （n+m）的字符串由（n+m）个A和B组成，要求有n个AB子序列和m个BA子序列，这样的串有几个? 题目链接： https://ac.nowcoder.com/acm/contest/881/E 题解： f[now][index]  代表 当前状态下  前index个字符的方案数多少    假设有j个A  那么就有 （i - j）个B   （i为当前位置， 可以看下面AC代码） 对于A, 优先变为AB, 故num(AB) = num(A) - num(B) = 2 * j - i 对于B, 优先变为BA, 故num(BA) = num(B) - num...

0 点赞评论收藏

2019-07-24 17:51

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） E ABBA 【DP】

0 点赞评论收藏

2019-10-31 16:36

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） B Integration 【裂项相消法】

题意： 给n个不同整数, 求的值。 题目链接： https://ac.nowcoder.com/acm/contest/881/B 题解： 参考大神博客:传送门 所谓裂项就是： AC_code: #include<bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9+7; const int maxn = 1e5+5; ll a[maxn], cnt[maxn]; ll quick_pow(ll a, ll b){ ll ans = 1; while(b){ ...

0 点赞评论收藏

2019-07-24 17:51

已编辑

阿里巴巴_淘特技术部_开发工程师

2019牛客暑期多校训练营（第一场） B Integration 【裂项相消法】

0 点赞评论收藏

关注他的用户也关注了：