2019.04.18 第六次训练 【2018-2019 ACM-ICPC, NEERC, Southern Subregional Contest, Qualification Stage】
题目链接:https://codeforces.com/gym/101911又补了set的一个知识点,erase(it)之后it这个地址就不存在了,再引用的话就会REA: ✅B: ✅C: ✅D: ✅E: https://blog.csdn.net/Link_Ray/article/detail...
ACM-ICPC 2018 徐州赛区网络预赛 J Maze Designer(最大生成树,倍增lca)
https://nanti.jisuanke.com/t/31462要求在一个矩形中任意选两个点都有唯一的通路,所以不会建多余的墙。要求满足上述情况下,建墙的费用最小。理解题意后容易想到首先假设全部墙都建起来,然后拆掉费用最大的边使图成为一棵树,就是求一颗最大生成树求出最大生成树后,求任意两点的距离...
2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest
2017-2018 ACM-ICPC, Asia Tsukuba Regional ContestA Secret of Chocolate Poles思路:暴力枚举黑巧克力的个数和厚黑巧克力的个数代码:#pragma GCC optimize(2)#pragma GCC optimize(3)#p...
The 2018 ACM-ICPC Asia Qingdao Regional Contest
The 2018 ACM-ICPC Asia Qingdao Regional Contest青岛总体来说只会3题C#include<bits/stdc++.h>using namespace std;#define maxn 3000005char a[maxn],b[maxn];in...
2017 ACM-ICPC EC-Final ShangHai 东亚洲大陆-上海
比赛链接:传送门Gym 101775A Chat Group(签到:待补)Gym 101775B Scapegoat(待补)Gym 101775C Traffic Light(贪心+思维)思路:需要证明两个点:① 所有的N+1个S都是必须要走的,并且可以适当安排使得红灯只用等最长的一个。② 上面这样...
ACM-ICPC 2018 南京赛区网络预赛 E题
ACM-ICPC 2018 南京赛区网络预赛 E题题目链接: https://nanti.jisuanke.com/t/30994Dlsj is competing in a contest with n (0 < n \le 20)n(0<n≤20) problems. And he ...
ACM-ICPC 2019南昌网络赛F题 Megumi With String
ACM-ICPC 南昌网络赛F题 Megumi With String题目描述给一个长度为\(l\)的字符串\(S\),和关于\(x\)的\(k\)次多项式\(G[x]\).当一个字符串\(str\)是S的子串时,定义\(str\)的\(value\)值为\(G[length(str)]\),否则\...
2017-2018 ACM-ICPC, Asia Daejeon Regional Contest
题目传送门 只打了三个小时。 A. Broadcast Stations B. Connect3 补题:zz 题解:因为格子是4*4的,而且每次落子的位置最多是只有四个,再加上剪枝,情况不会很多,直接爆搜就行了,再用三进制记录已经合法的情况,去掉重复的情况就行了。(用vs2017交会ac,但c+...
ACM-ICPC 2018 南京赛区网络预赛 L 【分层图最短路】
<题目链接>题目大意:有N个城市,这些城市之间有M条有向边,每条边有权值,能够选择K条边 边权置为0,求1到N的最短距离。解题分析:分层图最短路模板题,将该图看成 K+1 层图,然后具体解析见代码:#include <cstdio>#include <cstring&g...
ACM-ICPC 2018 南京赛区网络预赛 - L Magical Girl Haze (分层迪杰斯特拉)
题意:N个点,M条带权有向边,求可以免费K条边权值的情况下,从点1到点N的最短路。分析:K<=10,用dist[i][j]表示从源点出发到点i,免费j条边的最小花费。在迪杰斯特拉的dfs过程中,每个结点表示的状态有三个属性:访问至的结点,免费的边数和最小花费。将免费的边数看作层,则该图被分为k...
2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)
A Drawing Borders很多构造方法,下图可能是最简单的了代码:#include<bits/stdc++.h>using namespace std;const int maxn=1e6+;struct Point{ int x,y; };Point a[maxn]; int...
2013-2014 ACM-ICPC, NEERC, Southern Subregional Contest Problem L. Stock Trading Robot 水题
Problem L. Stock Trading Robot题目连接:http://www.codeforces.com/gym/100253DescriptionCyberTrader is an all-in-one trading solution for investment banks, ...
2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest I. Photo Processing 二分+ dp,好题
I. Photo Processing 题意: 长度为 n 的 a[] 序列,要你划分成多个连续的部分,每一部分至少有 k 个数。对于每一部分,其权值为最大值减最小值。最后总的权值为每一部分权值的最大值,求出可能的最小的总权值。 tags: 二分是肯定的,但没想到 dp 去 check 。。 先对 ...
Gym - 100548H The Problem to Make You Happy 2014-2015 ACM-ICPC, Asia Xian Regional Contest (BFS+博弈)
题意:Bob和Alice在一张有向无环图上移动,给定二者的起点,Bob先手.Bob的失败条件是不能移动或者与Alice相遇.两个人都采取最优策略,求Bob是否会赢 分析:银牌题.先确定所有的失败状态,然后根据这些反向状态BFS. 用\(dp[i][j][0or1]\)表示bob在i点,Alice在j...
ACM-ICPC 2018 南京赛区网络预赛 I Skr (马拉车+hash去重)或(回文树)
https://nanti.jisuanke.com/t/30998 题意 给一串由0..9组成的数字字符串,求所有不同回文串的权值和。比如说“1121”这个串中有“1”,“2”,“11”,“121”三种回文串,他们的权值分别是1,2,11,121。最终输出ans=135。 分析 第一次知道马拉车是...
Gym 100548F Color 2014-2015 ACM-ICPC, Asia Xian Regional Contest (容斥原理+大数取模)
题意:有N朵花,在M种颜色中选择恰好k种不同的颜色,将这N朵花染色,要求相邻的两朵花颜色不相同. 分析:若限制改为选择不超过k种颜色将N朵花朵染色,则方案数\(f(N,k) = k*(k-1)^{N-1}\),第一朵可以在k个颜色中任意选择,第二朵可以有k-1个选择,第三朵也有k-1.... 但是f...
ACM-ICPC 2018 徐州赛区网络预赛 F Features Track(STL模拟)
https://nanti.jisuanke.com/t/31458题意有N个帧,每帧有K个动作特征,每个特征用一个向量表示(x,y)。两个特征相同当且仅当他们在不同的帧中出现且向量的两个分量分别相等。求最多连续相同特征的个数?分析用一个map来维护帧中特征的信息,map中的键即读入的向量,因此用一...
2017-2018 ACM-ICPC, NEERC解题报告
A. Union of Doubly Linked Lists 模拟链表的合并,注意收尾相接的问题,不少队都A了 B. Preparing for Merge Sort 动态规划,优化才能水过,否则会无情TLE C. Sum of Nestings dfs递归搜索,字符串操作 D. Do...
The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online Solution
A Live Love水。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const double eps = 1e-; const int INF = 0x3f3f3f3f; const ll...
ACM-ICPC 2018 南京赛区网络预赛(A, J)
A 签到题Alice, a student of grade 666, is thinking about an Olympian Math problem, but she feels so despair that she cries. And her classmate, Bob, has ...