B. 0-1 MST time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Ujan has a lot of useless stuff in his drawers, a considerable part of which are his math notebooks: it is time to sort them out. This time he found an old dusty graph theory notebook...

2654: tree Time Limit: 30 Sec Memory Limit: 512 MB Submit: 4829 Solved: 2093 [Submit][Status][Discuss] Description 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。 Input 第一行V,E,need分别表示点数，边数和需要的白色边数。 接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。 Output 一行表示所求生成树的边权和。 V<=50000,E<=100...

1150: [CTSC2007]数据备份Backup Time Limit: 10 Sec Memory Limit: 162 MB Submit: 4042 Solved: 1720 [Submit][Status][Discuss] Description   你在一家 IT 公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味 的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。已知办公 楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网 络电缆使得它们可以互...

题目链接：小Y写文章 一道挺好的建图。 这道题我们不难想到先二分最大差值，然后再用网络流判断。 但每个位置分为两种不同的属性，必须放，和随便放。但是又害怕最大流的时候，全部都跑到随便放的位置去了。 于是我们可以把源点拆开，分成必须放的流量，和随便放的流量最后统计最大流即可。 很明显也是可以费用流的，因为必须放的具有更高的优先级。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int N=410,M=...

G. Petya and Graph time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Petya has a simple graph (that is, a graph without loops or multiple edges) consisting of n vertices and m edges. The weight of the i-th vertex is ai. The weight of the i-...

题目链接：上决╇ф的精确打击问题 题目大意：给你一个矩阵，矩阵里面有一些士兵，每次可以消灭一行或者一列，或者一个单点，问最小费用。 按行，列，建图，对于每个点，行连向列，权值为点的权值即可。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int inf=0x3f3f3f3f; const int N=1e3+10,M=1e5+10; int n,m,k,h[N],s,t; int head[N],nex[M]...

题目链接：D. Single-use Stones 真的很思维。 其实很简单，我们这样想，青蛙的移动距离是[0,l],那么每次青蛙移动我们都可以看作是l这么一段在移动(跳出l外面的我们已经不用管他了)，真正影响是否能到河对面的是这l里是否有足够的落脚点，我们找到l里最少的落脚点即是ans. AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e5+10; int w,l,a[N],res=0x3f3f...

题目链接：E. Segments Removal 题意：给你一个长为n的序列，每次对当前序列进行一次操作，就是将当前序列中最长的一段各元素相等的子段删掉，若满足题意的最长子段不止一条，则删最左边的，问你将该序列删完要操作多少次？ 看到这种删除，合并的操作，我们可以想到并查集或者set来做是很方便的。 然后我们就要去想怎么去用set维护。 我们开两个set，一个存，块的长度和编号，另一个存块的编号，这样我们就可以找到每个块前面的位置，和后面的位置。 然后每次取出一块，再看前后两块是否可以合并即可。 AC代码： #pragma GCC optimize(2) #include...

D. Exploration plan time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output The competitors of Bubble Cup X gathered after the competition and discussed what is the best way to get to know the host country and its cities. After exploring the map o...

C. Glass Carving time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Leonid wants to become a glass carver (the person who creates beautiful artworks by cutting the glass). He already has a rectangular w mm  ×  h mm sheet of glass, a diamond glas...

题目背景 小Z童鞋一日意外的看到小X写了一个正则表达式的高级程序，这个正则表达式程序仅仅由字符“0”,“1”，“.”和“*”构成，但是他能够匹配出所有在OJ上都AC的程序的核心代码！小Z大为颇感好奇，于是他决定入侵小X的电脑上去获得这个正则表达式的高级程序。 题目描述 在Internet网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在A到B的连接不一定存在B到A的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，...

题目链接：HDU - 6703 array 我们可以先来看一下，官方的题解： 题解 因为数组中的值唯一，且在1到n的范围内，而询问的r和k也在1到n的范围内。 所以对于任意一个*** 作1修改过的值都不会成为询问的答案，而询问的结果也必然在k到n＋1的范围内。 因为没有被修改过 值是唯一的，所以可以建立权值线段树，维护权值区间内的值所在下标的最大值。而询问则转化为不小 于k的值里面，下标超过r的最小权值是多少。 如何处理询问呢，一种较为暴力的解法是直接在线段树上 询问权值在k到n+1的范围内第一个下标超过r的权值是多少。但复杂度可能会被卡，需要减枝。 再加上 一个额外的判断就可以了，就是在...

E. Subsegments time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Programmer Sasha has recently begun to study data structures. His coach Stas told him to solve the problem of finding a minimum on the segment of the array in , which Sasha coped ...

D. Powerful array time limit per test5 seconds memory limit per test256 megabytes inputstandard input outputstandard output An array of positive integers a1, a2, …, an is given. Let us consider its arbitrary subarray al, al + 1…, ar, where 1 ≤ l ≤ r ≤ n. For every positive integer s denote by Ks th...