题目描述 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。 然而数据中有L=R的情况，请特判这种情况，输出0/1。 输入格式 输入文件第一行包含两个正整数N和...

题目描述 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过） 小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到： 如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。 如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加same_art[i][j]的满意值。 如果第i...

题目描述 有一个草原可以用一个1~400的数轴表示。有n头羊和q个查询。每头羊的编号分别是1，2，3…n。第i头羊只喜爱数轴上[ai，bi]这样的一个闭区间，每一时刻每头羊只可能在自己喜爱的区间的某个点上吃草。现在给出q个查询，每个查询两个整数l，r。你需要计算出在同一时刻，最多能有多少头羊同时在这个区间内吃草。数轴上每一个整点同一时刻只能容纳一只羊，羊只会在整点吃草。 输入描述: 第一行三个数n q。 第二行n个数a1 a2…an。 第三行n个数b1 b2…bn。 接下来q行每行两个数l，r。表示询问的区间。 输出描述: 对于每个查询，输出一个整数表示答案。 示例1 输入 复制 5 ...

题目描述 给出一个长度为n的字符串s和q个查询。对于每一个查询，会输入一个字符串t，你需要判断这个字符串t是不是s的子串。子串的定义就是存在任意下标a<b<c<d<e，那么”s[a]s[b]s[c]s[d]s[e]”就构成s的一个子串。如”abc”的子串有”a”、”b”、”c”、”ab”、”ac”、”bc”、”abc”。 输入描述: 第一行两个数n，q。1<=n，q<=1e5。 第二行一个长度为n的字符串s,所有字符都为小写拉丁字符。 接下来q行每行一个字符串t。1<=|t|<=50。 输出描述: 对于每个查询，如果t是s的字串，输出”YES...

地震破坏 时间限制: 1 Sec 内存限制: 128 MB 题目描述 威斯康星发生了一场地震！约翰的牧场遭到了打击，有一些牛棚变成了废墟，如果一间牛棚遭到 了破坏，那么所有和它相连的道路都不能使用了。 约翰有 N 个牛棚，编号为 1 到 N，有 M 条双向道路连接这些牛棚，第 i 条道路连接的牛棚是 A i 和 B i ，A i 可能等于 B i ，也可能有多条道路连接同一对牛棚。 约翰让奶牛们集中到 1 号牛棚避难。有 P 头奶牛通过手机向约翰求救，她们的遭遇类似：好消 息是她们所在的牛棚没有损坏，坏消息是由于其他的牛棚遭到破坏，所以她们找不到任何可以走到 1 号牛棚的路径。假设发送报告的第...

题目链接:so easy 一道哈希+并查集。 因为数字比较多，我们不能开数组并查集，但是询问次数不多，所以询问涉及的数字不多，我们哈希即可。然后哈希可以利用C++的 unordered_map。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; unordered_map<int,int> mp; int n,q; int find(int x){ if(!mp[x]) return x; if(mp[x...

题目链接：XKC’s basketball team 比较简单的做法就是线段树维护最大值，然后二分区间找最远的那一个即可。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int N=5e5+10; int n,m,a[N],res[N]; struct node{ int l,r,mx; }t[N<<2]; inline void push_up(int p){ t[p].mx=max(t[...

题目链接：Fire-Fighting Hero 大意：给出多个点，问这些点，到所有点的最短路当中的最大值是多少。和一个单独的点到所有点的最短路的最大值除C之后比较，输出最小的最大值。 我们肯定不能以每一个点去跑最短路，我们分析可知，因为从每个点出发是一样的，所以我们可以单独建立一个点，指向这些点，路程为0，最后跑这个点到所有点的最短路。单独的点就直接跑最短路即可。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; con...

题目描述 满汉全席是中国最丰盛的宴客菜肴，有许多种不同的材料透过满族或是汉族的料理方式，呈现在數量繁多的菜色之中。由于菜色众多而繁杂，只有极少數博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成，而他们之间还细分为许多不同等级的厨师。 为了招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在參赛的厨师之中，找到满汉料理界的明日之星。 大会的规则如下：每位參赛的选手可以得到n 种材料，选手可以自由选择用满式或是汉式料理将材料当成菜肴。 ...

题目链接：codeforces 877-E 题目大意：一棵树上，有些灯亮着，有些灯暗的，我们每次可以查询某个节点的亮灯个数，或者改变某个子树的暗亮情况（暗变成亮，亮变成暗）。 比较简单的dfs序，然后用线段树区间亮的个数即可。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int N=2e5+10; int n,q,cnt,st[N],ed[N],a[N]; int head[N],nex[N],to...

题目链接：Interesting Array 题目大意：题目要我们构造一个序列，满足m个条件，m个区间的与值为x，问我们是否能够构造出来，若不能输出NO，若可以则输出YES并输出，构造出的序列。 一道线段树好题。这道题我们要用到与运算的性质。要让我们当前区间的区间与为x，那么我们可以想到，我们区间的每个数字的每一位（二进制每一位），若x在这一位有1，那么区间所有数字都必须为1.因为只要有一个不是1，那么这一位就不会有1了，然后就不会等于x。怎么让每个数字的每一位与x相等呢？我们让区间每个数字或运算上x即可。所以我们最后计算每个需要满足的区间是否为需要满足的值即可。 AC代码：...

题目链接：Gosha is hunting 题目大意：我们有两种精灵球，每种精灵球对于每种精灵抓住的概率不同，对同一个精灵，同种精灵球只能用一个。 比较明显的费用流，但是由于浮点数没有考虑精度，TLE了几次。 考虑建图：对于两种精灵球，我们可以建立两个虚拟节点，用超级源点S指向精灵球，流量就是精灵球的个数，费用为0.然后精灵球指向每个精灵，流量为1，费用为0. 精灵指向汇点T，有两条边，流量都为1，一条费用为0，代表只使用了一种精灵球，一条费用为-p*q代表使用了两种精灵球。 最后跑一次最大费用流即可： AC代码： #pragma GCC optimize(2) ...

题目描述 N(2<=n<=200)个城市，M(1<=m<=40000)条无向边，你要找T(1<=T<=200)条从城市1到城市N的路，使得最长的边的长度最小，边不能重复用。 输入格式 第1行三个整数N,M,T用空格隔开。 第2行到P+1行，每行包括三个整数Ai,Bi,Li表示城市Ai到城市Bi之间有一条长度为Li的道路。 输出格式 输出只有一行，包含一个整数，即经过的这些道路中最长的路的最小长度。 输入输出样例 输入 #1复制 7 9 2 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3 输出...

题目链接：query 题目大意：就是有m次询问，每次问一个区间当中满足 gcd(i,j) = min(i,j) 的有多少对。 当时比赛的时候，一直给我感觉就是莫队，但是一直没有维护出来。 其实满足这个条件，就是相当于 i , j 有一个倍数关系。而且又是一个全排列，所以满足这个关系的并不多，最多 n log(n) 个，于是我们就可以把所有这样的关系都预处理出来。 我们对询问按照 r 排序，然后我们每次就可以保证，当前的右区间不用维护了，然后我们就是查询所有左区间满足大于当前的询问的左区间的个数一共有多少对,每次都把当前的右区间对应满足条件的左区间，插入到树状数组里面。 这个用树状...