千万别用树套树 一道好题，我们计算包含这个区间的线段很难计算，离线也不行，于是我们用到了容斥的原理，用总的线段减去不在这个区间的线段。 一条线段没有包含这个区间有两种情况： 线段右端点在当前区间的右端点的左边 线段的左端点在当前区间左端点的右边 于是我们分别统计这两种线段的个数即可。 对于第一种情况，我们需要记录右端点的信息，我们用一个树状数组每次填充1到右端点即可，最后就能根据数字查询了。 对于第二种情况，我们记录左端点的信息，每次从1填充到左端点即可 AC代码： #pragma GCC optimize(2) #include<bits/stdc++....

题目链接：[CQOI2014]危桥 因为来回an和bn次，就相当于过去2an和2bn次。 一般人都会之间按照题目建图，如果是危桥就流量为2，然后如果是普通桥就流量为inf。 但是这样有一个问题，如果是a1的流量到b2，b1的流量到a2就会有问题。 但是如果我们交换b1和b2之后也是满流则答案正确，我们画图设a1流到b2的流量为x可得，如果也是满流，那么a1一定也可以到a2. AC代码： #include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=1e4+10,M...

Highway In ICPCCamp there were n towns conveniently numbered with 1,2,…,n connected with (n−1) roads. The i-th road connecting towns ai and bi has length ci. It is guaranteed that any two cities reach each other using only roads. Bobo would like to build (n−1) highways so that any two towns reach ...

Destroying the bus stations Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3688 Accepted Submission(s): 1253 Problem Description Gabiluso is one of the greatest spies in his country. Now he’s trying to complete an “impossible” mission ----- to...

题目描述 AA国有nn座城市，编号从 11到nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 qq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 输入格式 第一行有两个用一个空格隔开的整数n,mn,m，表示 AA 国有nn 座城市和 mm 条道路。 接下来 mm行每行33个整数 x, y, zx,y,z，每两个整数之间用一个空格隔开，表示从 xx号城市到yy号城市有一条限重为 zz 的道路。注意： ** xx 不等于 yy，两座城市之间可能有多条道路 ** 。 接下来一行有一个整数 q，表示有 q 辆货车需要运货。...

题目描述 毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。 爬啊爬爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果 “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： Change k w：将第k条树枝上毛毛果的个数改变为w个。 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛...

Computer Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 38471 Accepted Submission(s): 6981 Problem Description A school bought the first computer some time ago(so this computer’s id is 1). During the recent years the school bought N-1 new comp...

题目大意：起点到终点经过边的数目为k的最短路值为多少。 离散数学的定理： 01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数 对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路。 但是每次floyd的复制度十分大，所以我们需要使用矩阵快速幂。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int N=210,inf=0x...

Transportation Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3524 Accepted Submission(s): 1525 Problem Description There are N cities, and M directed roads connecting them. Now you want to transport K units of goods from city 1 to city N. The...

Key Vertex Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1651 Accepted Submission(s): 428 Problem Description You need walking from vertex S to vertex T in a graph. If you remove one vertex which stops you from walking from S to T, that vert...

题目描述 小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1…n编号）。 现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小M找到了规则***有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以获得c2i的额外收益。 小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？ 输入格式 第一行包括一个整数n 第二行包括n个整数，表示a...

题目描述 lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定： 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。 每支军队都可以在任意一个城镇停止征战。 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走12的路线，而他们只能走RC的路线。 lanzerb的野心使得他的目标是统一全国...

Matrix Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3788 Accepted Submission(s): 1803 Problem Description Give you a matrix(only contains 0 or 1),every time you can select a row or a column and delete all the ‘1’ in this row or this column ....

我们可以看出来，我们需要在DAG上面统计有多少到达某个点的路径数。 这不就是拓扑排序吗？ 我们在拓扑排序时，传递a的值，最后计算答案即可、但是减法取模错了，WA了几次。。。。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10,p=1e9+7; int n,m,a[N],b[N],in[N],s[N]; int head[N],to[N],nex[N],tot; inline void add...