多校专题
2015多校联合训练第三场Work（hdu5326）
题意: a是b的上司，b是c的上司，则a是c的上司，问构成一个树种，有多人是 k个人的上司 思路: 先找出root，然后dfs一下就行 #include <bits/stdc++.h>#define LL long longusing namespace std;const int MAXN = 1e6;int f[105];int n, k;int mp[101][101];
2015年多校联合训练第三场RGCDQ（hdu5317）
题意: f(i)代表i数中有的素数的种数，给出区间[l,r],求区间内max(gcd(f（i）)), 由于i最大是1e6,2*3*5*7*11*13*17>1e6,故最多不超过7种素数， 先打表打出1e6内的素数种数表，然后用sum[i][j]代表1-i个数中，还有j个素数的个数，最后用sum[r][j] - sum[l-1][j]求出区间内含有j个素数的数的个数，暴力找出1，2，3，4，5
2015多校联合训练第一场Tricks Device（hdu5294）
题意:给一个无向图，给起点s,终点t,求最少拆掉几条边使得s到不了t，最多拆几条边使得s能到t 思路: 先跑一边最短路，记录最短路中最短的边数，总边数-最短边数就是第二个答案 第一个答案就是在最短路里面求最小割，也就是求最大流，然后根据最短路在建个新图，权为1，跑一边网络流 模板题，以后就用这套模板了 #include <iostream>#include <cstdio>#incl
2015多校联合训练第一场Assignment（hdu5289）三种解法
题目大意：给出一个数列，问其中存在多少连续子序列，子序列的最大值-最小值< k 这题有三种解法： 1：单调队列,时间复杂度O(n) 2：RMQ+二分,时间复杂度O(nlogn) 3：RMQ+贪心,时间复杂度O(nlogn) 一：RMQ+二分 RMQ维护最大值，最小值，枚举左端点i，二分找出最远的符合的右端点j，答案就是ans += j - i+1;(手推一下就知道) 比如1 2 3
2015年多校联合训练第一场OO’s Sequence（hdu5288）
题意：给定一个长度为n的序列，规定f(l,r)是对于l，r范围内的某个数字a[i]，都不能找到一个对应的j使得a[i]%a[j]=0，那么l，r内有多少个i，f(l,r)就是几。问所有f（l,r）的总和是多少。 公式中给出的区间，也就是所有存在的区间。 思路:直接枚举每一个数字，对于这个数字，如果这个数字是合法的i，那么向左能扩展的最大长度是多少，向右能扩展的最大长度是多少，那么i为合法的情况
2014多校联赛总结
转眼间2014年暑期多校联赛已经落下帷幕，下面是关于暑期比赛的一些总结. 题型统计: 2014 Multi-University Training Contest 1--by FZU A：数学（费马小定理） B:网络流（最小K路径覆盖） C：树形dp（树的重心+数据结构） D:贪心 （巧妙） E:数学+dp（隐含马尔科夫模型） F:线段树（函数式+二分） G:线段树+状态压
2014多校联合十（HDU 4972 HDU 4973 HDU 4974 HDU 4975）
HDU 4972 A simple dynamic programming problem 题意：篮球比赛有1、2、3分球 现给出两队的分差序列（5：3 分差2 3：5分差也是2） 问有多少种可能的比分 思路： 比较简单的想法题 可以类一张表“从分差x到分差y一共有几种情况” 很容易发现只有1->2和2->1的时候会多一种情况 其他均是一种 所以只需要统计这种特殊分差即可 注
2014多校训练九（HDU 4960 HDU 4961 HDU 4965 HDU 4968 HDU 4969 HDU 4970）
HDU 4960 Another OCD Patient 题意：给你一串数字 相邻x个数字合并成一个数字（相加）有一定代价 问 最少花费多少使得串变成回文串 思路： 读完题感觉像dp 数据范围也像 就开始想怎么表示状态 最简单的应该想到dp[i][j]表示i到j区间变成回文串的最小花费 状态想好了想做法 考虑将串分成AAAABBBBBBBCCC三段 即所有A合成一个数字
2014多校联合八（HDU 4945 HDU 4946 HDU 4948 HDU 4950 HDU 4951 HDU 4952）
HDU 4945 2048 题意：给你一堆数字 问有几个子集可以拼出2048 思路： 拼数字的规则相当于让数字乘二 所以不是2^i的数字不会拼出2048 那么这些数可选可不选 即为2^cnt种可能 之后只要计算出有几个子集不可能拼出2048即可 不过简单的直接dp是2048*100000的复杂度的 会TLE 所以要变成先枚举元素 再枚举该种元素个数 再枚举2048种状态
2014多校联合七（HDU 4937 HDU 4938 HDU 4939 HDU 4941）
好几天没写题解了… 都怪我太弱 补题补不动… HDU 4937 Lucky Number 题意：一个数字如果只有3456这四种数字组成 那么这个数字是幸运的 问 给出一个x 它在几种进制下是幸运的 如果无穷输出-1 思路： 分类讨论 如果x是3或4或5或6 那么一定有无穷个进制满足（从十进制开始…） 直接输出-1 除去上述情况 那么我们可以将一个数字写成这样 a0 +
【多校第9场】【组合数学】【区间dp】【Expression】
Expression Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 370 Accepted Submission(s): 208 Problem Description Teacher Mai has
2015ACM多校对抗赛第四场 hdu 5336
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5336 XYZ and Drops Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1024 Accepted Submissio
2015ACM多校对抗赛第四场 hdu 5335
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5335 Walk Out Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2280 Accepted Submission(s):
2015ACM多校对抗赛第四场 hdu 5327
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5327 Olympiad Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 442 Accepted Submission(s):
Hdu 5326 2015多校对抗赛三
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5326 Work Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 749 Accepted Submission(s): 490
Hdu 5325 2015多校对抗赛三
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5325 Crazy Bobo Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 1305 Accepted Submission(
Hdu 5323 2015多校对抗赛三
Solve this interesting problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2029 Accepted Submission(s): 617 Problem Description
hdu 5318 2015多校对抗赛三
The Goddess Of The Moon Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 842 Accepted Submission(s): 373 Problem Description Chang
2024牛客暑期多校训练营7 D.Interval Selection（异或哈希+双指针）
原题链接：D.Interval Selection 题目大意： 给你一个长度为 n n n 的数组 a a a，定义一个区间 [ l , r ] [l,r] [l,r] 内的连续子数组为好的，当且仅当这个子数组内的所有元素 a l , a l + 1 , . . . , a r a_{l},a_{l+1},...,a_{r} al,al+1,...,ar 在当前区间中恰好
hdu5385（2015多校8）--The path（贪心，搜索）
题目链接：点击打开链接 题目大意：给出一个有向图，求1到其它点的最短距离，要求dis[1] < dis[2]....dis[x] ... > dis[n-1] > dis[n] (1 < x <= n) 给出符合条件的每条边的边长(1<=边长<=n) 设置vis标记点是否已经存在，从左边开始逐个搜索，如果点已经存在那么继续遍历，否则换方向遍历（从右开始遍历），因为题目保证存在输出，所以一定可
hdu5386(2015多校8)--Cover
题目链接：点击打开链接 题目大意：给出一个n*n的矩阵的初始值，和最终的值，现在有m个操作 L i j ，将第i列的值重置为j，H i j，将第i行的值重置为j。问m个操作应该怎么执行，可以完成矩阵的变化。 从最终的值向前找寻方案，每次找行和列中剩余的颜色全部相同的，看是否存在没被使用的操作可以完成它，如果有就记录下来，那么最终按照记录的逆序输出，就是可以完成变化的序列啦 #includ
hdu5387（2015多校8）--Clock(模拟)
题目链接：点击打开链接 题目大意：给出一个时间，问在钟表上这个时间的时候，时针和分针的角度，时针和秒针的角度，分针和秒针的角度，如果不是整数以分数的形式输出。 如果按照最小的格来算，那么： 1s对于秒针来说走1格，分针走12/720格，时针走1/720格。 1m对于分针来说走一个，时针走60/720格。 1h对于时针来说走5格。 计算给出的时间中时针，分针，秒针走的格数，相减得到差，每
hdu5389(2015多校8)--Zero Escape（dp）
题目链接：点击打开链接 题目大意：有A和B两个门，每个门上有一个数字，现在有n个人，每个人手里也有一个数字，现在n个人都要选择一个门进去，要求计算门内的人的数字每一位的和，一直累加到一位。这个数和门代表的数字是相同的。问n个人有多少种走法。 例如 65536 -> 25 -> 7 输入n A B，之后一行输入n个数字代表n个人手中的数字。每个数字都是大于0的 输出种类个数。 对于累加每一
hdu5372（2015多校7）--Segment Game（树状数组）
题目链接：点击打开链接 题目大意：存在一个横轴，有n此操作，0代表在横轴上新增加一条边，1代表删除1条边，其中0 x代表在从x位置开始增加一条边，当第i次加边时，边的长度为i，1 x代表删除第x次加的边。问每当新加入一条边是，这条边能完整的包含几条边。 为什么当时没做这个题，，，已经泪奔，，， 问的是新加的那条边能覆盖多少条边，统计已加入的边的左端点大于或等于新边左端点的个数x，统计已加入的
hdu5361（2015多校6）--In Touch（变形的dijkstra）
题目链接：点击打开链接 题目大意：给出一个n个数的序列，标号为1到n，对于第i个数，它可以移动到距离i为[ li,ri ]的位置，花费为c[i]，输入三行，第一行l[i]，第二行r[i]，第三行c[i],现在问对于第一个数来说，它移动到第i个位置的最小花费。（1<=i<=n） 这是一个每个点可以移动到一段中任意一个点，并且花费一样，这样就不适用与已有的四种最短路，但是可以对dijkstra进行
hdu5375（2015多校7）--Gray code（dp）
题目链接：点击打开链接 题目大意：给出不完全的二进制编码，其中包含'0','1','?'，‘?’可以是0也可以是1，同时给出格雷码中每一位对应的权值，将二进制编码转化为格雷码后，对应位如果是1，那么累加权值，求权值最大是多少？ 将二进制编码转化为格雷码的方法： 二进制码：a[n-1] a[n-2] ,,,, a[2] a[1] a[0] 格雷码： b[n-1] b[n-2]