第一场专题

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为合法的情况

【牛客网 2017年校招模拟笔试(第一场)】超级素数幂

超级素数幂 描述 如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。 输入 输入一个正整数n(2 ≤ n ≤ 10^18) 分析 暴力枚举幂q,将n开q次方之后得到p,检查p是否为素数,并且检查p的q次幂是否等于n。 *要注意精度问题,代码待之后补充。

【牛客网 2017年校招模拟笔试(第一场)】 序列和

求序列和 描述 我们要找连续的一段长度大于等于L小于等于100整数和等于N,容易观察到合法的长度范围很小,于是我们从L开始枚举,然后找到第一个输出即可。 我的代码 最初提交了一次代码,用vector保存了所有满足条件的序列,输出长度最小的,提交之后说内存超出限制,看了一眼题目,发现内存貌似是限制在2w多k?伤心,之前做题没遇到过内存还有这么严格的限制。 修改了一下,其实这个代码并没

多校第一场 费马小定理+模拟+组合数学

A题:Couple doubi 链接:http://acm.hdu.edu.cn/showproblem.php?pid=4861 这题逗逼了,刚开始根本就没什么思路,刚开始看题的时候有点像费马小定理,但是这个定理我只知道,然后没用过。看了下定义,有点不一样的是反着的,然后反着的我又不会转化,尼玛,就这样错过了最好的解题方法。然后队友又理解错题意了。WA了多发,然后我重新看了下题意,然后队友才

hdu 4607 park visit 2013多校联合训练第一场

题目的大意是给你一棵树 ,相连节点之间的距离为一,让你找出一个路线访问到k个不同节点 (一条边在这个路径中可以被走多次),问你这样这个路径的距离最小值是多少?   转化之后其实就是要找出数的直径即任意2点间的最大距离,一种方法是任取一个节点做一次广搜找出其最长的子树,然后以该子树的最远的叶子上的节点作为起点再做一次广搜之后得到的最长子树的长度就是树的直径了 对于要访问的点的个数k 小于等于树

校省选赛第一场D题TwoDecks题解

今天晚上第二场比赛,现在还是赛后刷上次的题目,越刷越伤心,发现我赛后一次AC的功力很强大啊!!!(希望今晚变成是赛中一次AC啊!!) 好啦,回归正题。 看题目 D. Merging Two Decks time limit per test 2 seconds memory limit per test 256 megabytes input input.tx

校省选赛第一场C题解Practice

比赛时间只有两个小时,我没有选做这题,因为当时看样例也看不懂,比较烦恼。 后来发现,该题对输入输出要求很低。远远没有昨天我在做的A题的麻烦,赛后认真看了一下就明白了,写了一下,一次就AC了,没问题,真心有点后悔。 来先看题目: C. Practice t ime limit per test 1 second memory limit per test 256 megabyt

计蒜之道 初赛 第一场 题解 dp 高效 网络流 最小割 最大流 ISAP 模板

搜狗输入法的分词算法 搜狗输入法最近的用户输入中出现了一种新的输入模式,形如 “0k1234567”,搜狗的工程师发现这一模式后了解到,这是一种新被提出的对于十五进制数字的标记模式,其中 “0k” 是标记进制为15的前缀标记,之后的部分 “1234567” 是实际的十五进制的数字串。 在发现这一标记模式后,搜狗的工程师开始尝试在已有的分词算法上进一步加入对于十五进制数字串的处理,把网

2015年北京的第一场雪-关于android学习的思考(84)

今天是2015年11月6日,今天北京下了大雪。## 前段时间读了黑客与画家。大受启发,代码应该是写出来的,要在写的过程中思考,程序员和画家很像,你看画家都是边画边改,很多时候,做的过程会带动你思考,最后形成完整的作品。##

西山居初赛第一场1001

魔法串(杭电4545) Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 476    Accepted Submission(s): 201 Problem Description 小明和他的好朋友小西在玩一个新的

牛客美团2024年春招第一场笔试【技术】解题

1.小美的平衡矩阵 小美拿到了一个n∗n的矩阵,其中每个元素是 0 或者 1。 小美认为一个矩形区域是完美的,当且仅当该区域内 0 的数量恰好等于 1 的数量。 现在,小美希望你回答有多少个i∗i的完美矩形区域。你需要回答1≤i≤n的所有答案 输出描述: 输出n行,第i行输出i*i的完美矩形区域的数量 例子: 输入例子: 4 1010 0101 1100 0011 输出例子: 0 7 0 1

小美的平衡矩阵-美团2024年春招第一场笔试

思路:暴力枚举所有的i*i矩阵,复杂度为O(),至于矩阵中0和1的数量,使用二维前缀和数组求得。 解释下构造前缀和数组语句:sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];作用 求以(i,j)左上角,(k,l)右下角的的前缀和语句: sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1

Facebook Libra第一场参议院听证会有哪些亮点?

美国时间7月16日上午10点,Facebook Libra第一场参议院听证会正式举行。 Facebook Calibra的负责人David Marcus刚刚告诉参议院银行委员会,Libra协会只会将Calibra加密货币钱包集成在Facebook Messenger和Whatsapp中,此外再不会有其他钱包嵌入。 虽然有些人像参议员布朗一样鼓吹Facebook很危险,但其他人却对Libra

2018湖南多校第一场 Exponial Gym - 101550E(广义欧拉降幂)

Everybody loves big numbers (if you do not, you might want to stop reading at this point). There are many ways of constructing really big numbers known to humankind, for instance: Exponentiation: 4

2020杭电多校第一场 Finding a MEX(分块+树状数组,维护MEX)

Problem Description Given an undirected graph G=(V,E). All vertices are numbered from 1 to N. And every vertex u has a value of Au. Let Su={Av│(u,v)∈E}. Also, F(u) equals MEX(minimum excludant) value

2020小米网络赛第一场 G Tree Projection(拓扑序,构造)

题意: 构造一棵树,使得按照 A 1 A1 A1为根拓扑排序可以得到 A A A序列,按照 B 1 B1 B1为根拓扑排序可以得到 B B B序列。 思路: 表示很巧妙,没想出来,直接搬题解吧 这道题倒是纠正了我一直以来的误区,我以前一直用bfs写拓扑,所以转换到树上的时候想当然的把bfs序与拓扑序等价了起来。但其实拓扑排序也可以是树上dfs序,只要满足前驱限制条件的序列都是拓扑序。

2020小米网络赛第一场 Matrix Subtraction(二维前缀和)

题意: 每次使得一个 a ∗ b a*b a∗b的子矩阵每个值减1,问能否使得这个 n ∗ m n*m n∗m的矩阵全部变成0。 思路: 也是套路题了,直接维护二维前缀和。 #include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace st

2020小米网络赛第一场 Walking Machine(BFS)

题意: 每个点有一个方向值,代表这个点出发只能走这个方向。 求多少个点出发可以走到棋盘外。 思路: 经典题了吧,直接从外边界bfs进来看能遍历到多少个点。当然遍历的时候我们要记得把每个点的方向值反一下。 #include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>usi

2020小米网络赛第一场 F.Design Problemset(二分)

题意: 有 k k k种数,每种数有 b [ i ] b[i] b[i]个,每次选择的范围数目为 [ l i , r i ] [l_i,r_i] [li​,ri​],选择完的数字下次不能再选。 每次选择完毕后,数目总数范围要求在 [ L , R ] [L,R] [L,R]内,求一共能选择多少次。 思路: 直接二分能选择 m i d mid mid次,算出选择这么多次得到的最小值(每次取左端点就

2020小米网络赛第一场 Smart Browser

签到不解释 #include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;typedef long long ll;const int mod = 1e9 + 7;const int maxn = 1e5 + 7;char s[ma

2020小米网络赛第一场 D Router Mesh(点双连通分量)

题意: 一个图,求出删掉每个点后得到的连通块数量。 思路: 算出每个点所在的点双连通分量数目 v i s [ i ] vis[i] vis[i],就可以得出这个点删掉后增加的连通块数目了。同时算出初始的连通块数目 a l l all all,则删掉点 i i i的连通块数目为 v i s [ i ] + a l l − 1 vis[i]+all-1 vis[i]+all−1。 #includ

【Nowcoder】2020牛客寒假集训营(第一场):maki和tree 思维

传送门 分析 我们先去把每一个相同颜色的联通快记录下来,然后去遍历每一个黑点,计算他连接的所有白点所在的联通块的大小,有两种情况 黑点就是端点 这种情况只需要答案加上白色联通快大小的和即可两个端点都是白点 任意两个联通快组合即可 代码 #pragma GCC optimize(3)#include <bits/stdc++.h>#define debug(x) cout<<#x<<"

【HDU】2021杭电暑假集训营(第一场):KD-Graph 思维 + 并查集

传送门 题意 n个顶点,给出m条边的信息。现在问是否存在一个最小的D值恰好使原图变为k个连通的部分。 若顶点p和q (p≠q)连通,则p和q之间最长边小于或等于D(不是总路径长度)。 若点p和q (p≠q)不连通,则p和q之间最长边不可能小于或者等于D。 分析 我们把所有点看成 n n n个连通块,然后去动态合并 把所有边按照边权排序,如果两个端点不在同一个连通块内,就进行合并,一直合并

2015级计算机学院《程序设计基础(1)》(第一场)

2015级计算机学院《程序设计基础(1)》(第一场) Problem A: 花坛 Description 学校要修一些圆形的花坛,每个花坛外围铺一圈大理石的地面。现在知道花坛的内圆半径r米和大理石地面的外圆半径R米,求大理石地面的面积。 圆周率取3.14159。 Input 输入两个浮点数r和R。 Output 输出大理石地面的面积,精确到小数点后三位。 Sample Input 2