@ivorysi 2018-01-02T09:03:58.000000Z 字数 32423 阅读 693

常用算法2学习笔记

笔记

01分数规划

POJ 2976 Dropping tests

Description

In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be.
Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.
Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

Sample Input

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

Sample Output

83
100

Hint

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

题解

01分数规划的板子题
我们枚举一个最大的分数
$\frac{\sum a_i}{\sum b_i}=l$
$\sum a_i-l\cdot b_i >=0$ 的时候说明l可以取到或者更大
$\sum a_i-l\cdot b_i <0$ 说明l取不到

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 1005
//#define ivorysi
using namespace std;
typedef long long ll;
int n,k;
double a[MAXN],b[MAXN],pos[MAXN];
bool check(double mid) {
    siji(i,1,n) pos[i]=a[i]-mid*b[i];
    sort(pos+1,pos+n+1);
    double res=0;
    gongzi(i,n,k+1) {
    res+=pos[i];
    }
    return res>=0.0;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d%d",&n,&k)!=EOF) {
    siji(i,1,n) scanf("%lf",&a[i]);
    siji(i,1,n) scanf("%lf",&b[i]);
    if(n+k==0) break;
    double l=0.0,r=1.0;
    int num=100;
    while(num--) {
        double mid=(l+r)/2.0;
        if(check(mid)) l=mid;
        else r=mid;
    }
    l=l*100;
    printf("%d\n",(int)(l+0.5));
    }
    return 0;
}

POJ 2728 Desert King

Description

David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which are connected to his capital village will be watered. As the dominate ruler and the symbol of wisdom in the country, he needs to build the channels in a most elegant way.
After days of study, he finally figured his plan out. He wanted the average cost of each mile of the channels to be minimized. In other words, the ratio of the overall cost of the channels to the total length must be minimized. He just needs to build the necessary channels to bring water to all the villages, which means there will be only one way to connect each village to the capital.
His engineers surveyed the country and recorded the position and altitude of each village. All the channels must go straight between two villages and be built horizontally. Since every two villages are at different altitudes, they concluded that each channel between two villages needed a vertical water lifter, which can lift water up or let water flow down. The length of the channel is the horizontal distance between the two villages. The cost of the channel is the height of the lifter. You should notice that each village is at a different altitude, and different channels can't share a lifter. Channels can intersect safely and no three villages are on the same line.
As King David's prime scientist and programmer, you are asked to find out the best solution to build the channels.

Input

There are several test cases. Each test case starts with a line containing a number N (2 <= N <= 1000), which is the number of villages. Each of the following N lines contains three integers, x, y and z (0 <= x, y < 10000, 0 <= z < 10000000). (x, y) is the position of the village and z is the altitude. The first village is the capital. A test case with N = 0 ends the input, and should not be processed.

Output

For each test case, output one line containing a decimal number, which is the minimum ratio of overall cost of the channels to the total length. This number should be rounded three digits after the decimal point.

Sample Input

4
0 0 0
0 1 1
1 1 2
1 0 3
0

Sample Output

1.000

题解

这道题是最小比率生成树，必须用prim算法，限制二分枚举次数的时候需要注意不能太大……大概50次应该够
二分上界是所有点到原点的高度之和，这个一定覆盖上界
然后每次枚举一个平均，每条边的边权是：价值-平均值×距离，然后做最小生成树

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 1005
//#define ivorysi
using namespace std;
typedef long long ll;
int n,tot;
double x[MAXN],y[MAXN],z[MAXN],dis[MAXN];
double mul(double x) {return x*x;}
int fa[MAXN];
bool vis[MAXN];
int getfa(int x) {
    return fa[x]==x ? x : fa[x]=getfa(fa[x]);
}
double dist(int a,int b) {
    return sqrt(mul(x[a]-x[b])+mul(y[a]-y[b]));
}
bool check(double mid) {
    memset(vis,0,sizeof(vis));
    siji(i,2,n) dis[i]=fabs(z[1]-z[i])-mid*dist(1,i);
    vis[1]=1;
    int tot=n-1;
    int id=-1;
    double val=0.0,tmp=0.0;
    while(tot--) {
    id=-1;
    siji(i,1,n) {
        if(!vis[i]) {
        if(id==-1) {id=i;}
        else if(dis[id]>dis[i]) {id=i;}
        } 
    }
    tmp+=dis[id];
    vis[id]=1;
    siji(i,1,n) {
        if(!vis[i]) {
        dis[i]=min(dis[i],fabs(z[i]-z[id])-mid*dist(i,id));
        } 
    }
    }
    return tmp<=0.0;
} 
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&n)!=EOF) {
    if(!n) break;
    int num=50;
    siji(i,1,n) scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
    double l=0.0,r=0.0;
    siji(j,2,n) {
        r+=fabs(z[j]-z[1]);
    }
    while(num--) {
        double mid=(l+r)/2.0;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.3lf\n",r);
    }
    return 0;
}

POJ 3621 Sightseeing Cows

Description

Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time.
Fortunately, they have a detailed city map showing the L (2 ≤ L ≤ 1000) major landmarks (conveniently numbered 1.. L) and the P (2 ≤ P ≤ 5000) unidirectional cow paths that join them. Farmer John will drive the cows to a starting landmark of their choice, from which they will walk along the cow paths to a series of other landmarks, ending back at their starting landmark where Farmer John will pick them up and take them back to the farm. Because space in the city is at a premium, the cow paths are very narrow and so travel along each cow path is only allowed in one fixed direction.
While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values Fi (1 ≤ Fi ≤ 1000) for each landmark i.
The cows also know about the cowpaths. Cowpath i connects landmark L1i to L2i (in the direction L1i -> L2i ) and requires time Ti (1 ≤ Ti ≤ 1000) to traverse.
In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off.
Help the cows find the maximum fun value per unit time that they can achieve.

Input

Line 1: Two space-separated integers: L and P

Lines 2..L+1: Line i+1 contains a single one integer: Fi

Lines L+2..L+P+1: Line L+i+1 describes cow path i with three space-separated integers: L1i , L2i , and Ti

Output

Line 1: A single number given to two decimal places (do not perform explicit rounding), the maximum possible average fun per unit time, or 0 if the cows cannot plan any trip at all in accordance with the above rules.

Sample Input

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

Sample Output

6.00

题解

这道题是最小比率生成环
也是二分一个小数，然后修改边权，spfa上跑负环
每条边的边权变成：比率×边权-边起点的点权（这个是分数式的取值取负，因为要跑负环）
把每条边的dis设成0，然后跑spfa，因为反正都要找负环，就把每个点都当成起点，一定会有一条路从开始走回来都是负的，所以我们只把距离从0往小里更新
用spfa跑dfs如果有重复计算的点那么必然是有负环，这样保证了点不会被重复计算

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 1005
//#define ivorysi
using namespace std;
typedef long long ll;
int L,P;
struct node {
    int to,next,val;
}edge[5005];
int head[1005],sumedge;
double fun[1005],dis[1005];
bool vis[1005];
void add(int u,int v,int c) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    edge[sumedge].val=c;
    head[u]=sumedge;
}
bool spfa_dfs(int u,double w) {
    vis[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
    int v=edge[i].to;
    if(dis[v] > dis[u]+edge[i].val*w-fun[u]) {
        dis[v]=dis[u]+edge[i].val*w-fun[u];
        if(!vis[v]) {if(spfa_dfs(v,w)) return 1;}
        else return 1;
    }
    }
    vis[u]=0;
    return 0;
}
bool check(double mid) {
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    siji(i,1,L) {
    if(spfa_dfs(i,mid)) return 1;
    }
    return 0;
} 
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&L,&P);
    double l=0.0,r=0.0;
    siji(i,1,L) {scanf("%lf",&fun[i]); r+=fun[i];}
    int u,v,c;
    siji(i,1,P) {
    scanf("%d%d%d",&u,&v,&c);
    add(u,v,c);
    }
    int num=50;
    while(num--) {
    double mid=(l+r)/2.0;
    if(check(mid)) l=mid;
    else r=mid;
    }
    printf("%.2f\n",l);
    return 0;
}

POJ 3155 Hard Life

Description

John is a Chief Executive Officer at a privately owned medium size company. The owner of the company has decided to make his son Scott a manager in the company. John fears that the owner will ultimately give CEO position to Scott if he does well on his new manager position, so he decided to make Scott’s life as hard as possible by carefully selecting the team he is going to manage in the company.
John knows which pairs of his people work poorly in the same team. John introduced a hardness factor of a team — it is a number of pairs of people from this team who work poorly in the same team divided by the total number of people in the team. The larger is the hardness factor, the harder is this team to manage. John wants to find a group of people in the company that are hardest to manage and make it Scott’s team. Please, help him.
In the example on the picture the hardest team consists of people 1, 2, 4, and 5. Among 4 of them 5 pairs work poorly in the same team, thus hardness factor is equal to 5⁄4. If we add person number 3 to the team then hardness factor decreases to 6⁄5.

Input

The first line of the input file contains two integer numbers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Here n is a total number of people in the company (people are numbered from 1 to n), and m is the number of pairs of people who work poorly in the same team. Next m lines describe those pairs with two integer numbers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) on a line. The order of people in a pair is arbitrary and no pair is listed twice.

Output

Write to the output file an integer number k (1 ≤ k ≤ n) — the number of people in the hardest team, followed by k lines listing people from this team in ascending order. If there are multiple teams with the same hardness factor then write any one.

Sample Input

sample input #1
5 6
1 5
5 4
4 2
2 5
1 2
3 1
sample input #2
4 0

Sample Output

sample output #1
4
1
2
4
5
sample output #2
1
1

Hint

Note, that in the last example any team has hardness factor of zero, and any non-empty list of people is a valid answer.

题解

再复习一下最大密度子图
首先我们需要知道最大闭合权子图
最大闭合权子图就是选取一个点集，这些点集的出边指向的点也在这个集合里，要求点权和最大，点权有正有负
做法是把每条边的边权改成正无穷，原点向点权为正的点连一条容量为点权的边，点权为负的点向汇点连一条容量为点权绝对值的边，然后跑网络流，所有点权为正的点的和减去最大流就是能得到的最大值，然后在残余网络里dfs能搜到的点就是在点集里的点

最大密度子图是
$\frac {e}{v}=g$
$h(g)=e-vg$ 我们把边抽象成一个点，选了一条边要选对应的两个点，每个点的点权是-g，每个边抽象成的点的点权是1，然后跑最大权闭合子图，看是不是>0,g就是合法的

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 1005
#define eps 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int to,next;
    double val;
}edge[100005];
int head[2005],sumedge,source,sink,dis[2005],gap[2005];
int n,m,ans;
bool vis[2005];
struct data {
    int a,b;
}Eg[2005];
void add(int u,int v,double c) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    edge[sumedge].val=c;
    head[u]=sumedge;
}
void addtwo(int u,int v,double c) {
    add(u,v,c);add(v,u,0);
}
double sap(int u,double aug) {
    if(u==sink) return aug;
    int dmin=sink-1;
    double flow=0;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val>0) {
        int v=edge[i].to;
        if(dis[v]+1==dis[u]) {
        double t=sap(v,min(edge[i].val,aug-flow));
        flow+=t;
        edge[i].val-=t;
        edge[i^1].val+=t;
        if(aug-flow<eps) return flow;
        if(dis[source]>=sink) return flow;
        }
        dmin=min(dmin,dis[v]);
    }
    }
    if(!flow) {
    --gap[dis[u]];
    if(gap[dis[u]]==0) dis[source]=sink;
    dis[u]=dmin+1;
    ++gap[dis[u]];
    }
    return flow;
}
bool check(double mid) {
    memset(head,0,sizeof(head));sumedge=1;
    memset(dis,0,sizeof(dis));
    memset(gap,0,sizeof(gap));
    siji(i,1,m) {
    addtwo(i+n+1,Eg[i].a+1,(double)m);
    addtwo(i+n+1,Eg[i].b+1,(double)m);
    addtwo(source,i+n+1,1);
    }
    siji(i,1,n) addtwo(i+1,sink,mid);
    double ans=m;
    while(dis[source]<sink) ans-=sap(source,ans);
    return ans > eps;
}
void dfs(int u) {
    vis[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val>0) {
        int v=edge[i].to;
        if(!vis[v]) dfs(v);
    }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    siji(i,1,m) {
    scanf("%d%d",&Eg[i].a,&Eg[i].b);
    }
    if(m==0) {
    printf("1\n1\n");
    return 0;
    }
    source=1,sink=m+n+2;
    double l=0,r=m;
    int num=100;
    while(num--) {
    double mid=(l+r)/2.0;
    if(check(mid)) l=mid;
    else r=mid;
    }
    check(l);
    dfs(source);
    siji(i,1,n) if(vis[i+1]) ++ans;
    printf("%d\n",ans);
    siji(i,1,n) if(vis[i+1]) printf("%d\n",i);
    return 0;
}

高斯消元

BZOJ 1013: [JSOI2008]球形空间产生器sphere

Description

有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球
面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。

Input

第一行是一个整数n(1<=N=10)。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点
后6位，且其绝对值都不超过20000。

Output

有且只有一行，依次给出球心的n维坐标（n个实数），两个实数之间用一个空格隔开。每个实数精确到小数点
后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。

Sample Input

2
0.0 0.0
-1.0 1.0
1.0 0.0

Sample Output

0.500 1.500

HINT

提示：给出两个定义：1、球心：到球面上任意一点距离都相等的点。2、距离：设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn)，则AB的距离定义为：dist = sqrt( (a1-b1)^2 + (a2-b2)^2 +… + (an-bn)^2 )

题解

高斯消元，注意交换的时候要一直交换到n+1……

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
//#define ivorysi
using namespace std;
typedef long long ll;
int n,m;
double c[15][15];
double f[15][15];
double ans[15];
void Guass() {
    siji(i,1,n) {
    int l=i;
    siji(j,l+1,n) if(fabs(f[j][i])>fabs(f[l][i])) l=j;
    if(l!=i) {
        siji(j,i,m) swap(f[i][j],f[l][j]);//这里是m不是n……交换一直连值也交换
    }
    siji(j,i+1,n) {
        double tmp=f[j][i]/f[i][i];
        siji(k,i,m) {
        f[j][k]-=f[i][k]*tmp;
        }
    }
    }
    gongzi(i,n,1) {
    double t=f[i][m];
    sigongzi(j,n,i) t-=ans[j]*f[i][j];
    ans[i]=t/f[i][i];
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&n);m=n+1;
    siji(i,0,n) {
    siji(j,1,n) {
        scanf("%lf",&c[i][j]);
    }
    }
    siji(i,1,n) {
    double d=0;
    siji(j,1,n) {
        f[i][j]=2*(c[i][j]-c[i-1][j]);
        d+=(c[i][j]*c[i][j]-c[i-1][j]*c[i-1][j]);
    }
    f[i][m]=d;
    }
    Guass();
    siji(i,1,n) {
    printf("%.3lf%c",ans[i]," \n"[i==n]);
    }
    return 0;
}

BZOJ 2337: [HNOI2011]XOR和路径

题面

给出一张无向连通图，有重边和自环，计算1到n的路径的异或和的期望，在每个点等概率选择一条路去走

题解

因为是异或，异或对每一个二进制位影响都是独立的，所以拆位来做
我们列出期望的dp来
$f[x]$ 表示从x到n该位是1的概率
把边权按这一位是否是1转化成1或0
$f[x]=\frac{1}{deg_x}\sum (f[y]\cdot(1-w)+(1-f[y])\cdot w)$
这样如果是0的话那么就取 $f[y]$ 如果是1的话就取 $(1-f[y])$ 减少了讨论情况
如果y是n的话， $f[x]+=\frac{w}{deg_x}$
但是这又不是一张拓扑图，没有办法dp，只能高斯消元，每次统计上1到n的概率乘上位权

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
//#define ivorysi
using namespace std;
typedef long long ll;
int n,m;
struct node {
    int to,next,val;
}edge[1000005];
int head[105],sumedge,deg[105];
double f[105][105],ans[105];
void add(int u,int v,int c) {
    edge[++sumedge].to=v;
    edge[sumedge].val=c;
    edge[sumedge].next=head[u];
    head[u]=sumedge;
    ++deg[u];
}
void Guass() {
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n-1;++i) {
        int l=i;
        for(int j=l+1;j<=n-1;++j) if(fabs(f[j][i])>fabs(f[l][i])) l=j;
        if(l!=i) {
            for(int j=i;j<=n;++j) swap(f[i][j],f[l][j]);
        }
        for(int j=i+1;j<=n-1;++j) {
            double tmp=f[j][i]/f[i][i];
            for(int k=i;k<=n;++k) {
                f[j][k]-=f[i][k]*tmp;
            }
        }
    }
    for(int i=n-1;i>=1;--i) {
        double t=f[i][n];
        for(int j=n-1;j>i;--j) t-=ans[j]*f[i][j];
        ans[i]=t/f[i][i];
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    int u,v,c;
    siji(i,1,m) {
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c);
        if(u!=v) add(v,u,c);
    }
    double res=0.0;
    siji(i,0,30) {
        memset(f,0,sizeof(f));
        siji(u,1,n-1) {
            f[u][u]=1;
            for(int k=head[u];k;k=edge[k].next) {
                int v=edge[k].to,w=edge[k].val;
                w=(w>>i)&1;
                if(v!=n) {
                    f[u][v]+=(double)(2*w-1)/deg[u]; 
                    f[u][n]+=(double)w/deg[u];
                }
                else f[u][n]+=(double)w/deg[u];
            }
        }
        Guass();
        res+=ans[1]*(1<<i);
    }
    printf("%.3lf\n",res);
    return 0;
}

BZOJ 3143: [Hnoi2013]游走

Description

一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。

Input

第一行是正整数N和M，分别表示该图的顶点数和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。

Output

仅包含一个实数，表示最小的期望值，保留3位小数。

Sample Input

3 3
2 3
1 2
1 3

Sample Output

3.333

HINT

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

题解

如果我们能求出每条边的期望经过次数，就可以贪心地把编号赋给他们，然而问题来了，我们怎么求出每条边期望经过次数
我们转化成求每个点经过的次数，或者说是每个点能做决策的次数
那么每条边期望经过的次数就是
$w_i=\frac{x_a}{deg_a}+\frac{x_b}{deg_b}$
走到n点就不动弹了，所以n点能做决策的次数是0，这个比较特殊

每个点的x是
$x_a=\sum_{(a,b)\in E} \frac{x_b}{deg_b}$
会得到n-1个方程
然后高斯消元……

为什么除掉删边操作忽然就A了不T了……

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
//#define ivorysi
using namespace std;
typedef long long ll;
int n,m;
int deg[505],U[1000005],V[1000005];
double f[505][505],ans[505],ex[1000005];
void Guass() {
    for(int i=1;i<=n-1;++i) {
    int l=i;
    for(int j=l+1;j<=n-1;++j) if(fabs(f[j][i])>fabs(f[l][i])) l=j;
    if(l!=i) {
        for(int j=i;j<=n;++j) swap(f[i][j],f[l][j]);
    }
    for(int j=i+1;j<=n-1;++j) {
        double tmp=f[j][i]/f[i][i];
        for(int k=i;k<=n;++k) {
        f[j][k]-=tmp*f[i][k];
        }
    }
    }
    for(int i=n-1;i>=1;--i) {
    double t=f[i][n];
    for(int j=n-1;j>i;--j) t-=ans[j]*f[i][j];
    ans[i]=t/f[i][i];
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    int u,v;
    siji(i,1,m) {
    scanf("%d%d",&u,&v);
    deg[u]++;deg[v]++;
    U[i]=u;V[i]=v;
    }
    siji(i,1,n-1) f[i][i]=-1.0;
    siji(i,1,m) {
    if(U[i]!=n && V[i]!=n) {
        f[V[i]][U[i]]=1.0/deg[U[i]];
        f[U[i]][V[i]]=1.0/deg[V[i]];
    }
    }
    f[1][n]=-1.0;
    Guass();
    siji(i,1,m) {
    ex[i]=ans[U[i]]/deg[U[i]]+ans[V[i]]/deg[V[i]];
    }
    sort(ex+1,ex+m+1);
    double res=0;
    gongzi(i,m,1) {
    res+=ex[m-i+1]*i;
    }
    printf("%.3lf\n",res);
    return 0;
}

BZOJ 3572: [Hnoi2014]世界树

Description

世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地a和b之间有道路，b和c之间有道路，因为每条道路长度为1而且又不可能出现环，所卧a与c之间的距离为2。
出于对公平的考虑，第i年，世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x（x为种族的编号），如果距离该种族最近的临时议事处为y（y为议事处所在聚居地的编号），则种族x将接受y议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则y为其中编号最小的临时议事处）。
现在国王想知道，在q年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。

Input

第一行为一个正整数n，表示世界树中种族的个数。
接下来n-l行，每行两个正整数x，y，表示x聚居地与y聚居地之间有一条长度为1的双
向道路。接下来一行为一个正整数q，表示国王询问的年数。
接下来q块，每块两行：
第i块的第一行为1个正整数m[i]，表示第i年授权的临时议事处的个数。
第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]]，表示被授权为临时议事处的聚居地编号（保证互不相同）。

Output

输出包含q行，第i行为m[i]个整数，该行的第j(j=1，2…，，m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。

Sample Input

10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
5
2
6 1
5
2 7 3 6 9
1
8
4
8 7 10 3
5
2 9 3 5 8

Sample Output

1 9
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1

HINT

N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000

题解

这是虚树（思想在那虚树路径上彷徨）
我们把这些特殊点选出来作为一棵树，构建方法用一个栈维护右链，新加入的一个点和栈顶的点求lca，如果lca不是栈里的点，就把lca也加进去
求的方法可以在虚树上做这样的操作

1.首先，虚树里最高的点，它以上的点一定和它的控制点相同
2.每个虚树上的点必然会和它在虚树上的点共用一个控制点
3.如果u和u的父亲fa共用一个控制点，那么u到fa的路径上的点以及这些点的子树也是用这个控制点
4.如果不用一个控制点，那么这条路径上一定存在一个分界点，使得前面路径的点属于fa的控制点，后面路径属于u的控制点，这个就是，u到控制点的距离+fa到控制点的距离+两点之间的距离的一半
然而会有距离相等然而fa控制点的编号较小，这个时候我们再往下走一步

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define pii pair<int,int>
#define fi first
#define se second
#define INF 0x3f3f3f3f
//#define ivorysi
using namespace std;
typedef long long ll;
const int N=300005;
const int M=20;
int n,m,sol[N],ans[N];
int fa[N][M],dep[N],dfn[N],size[N],inx;
int num,aux[N],faAux[N],delta[N],val[N];
pii f[N];
int stk[N],top;
struct node {
    int to,next;
}edge[N*4];
int head[N],sumedge;
void add(int u,int v) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    head[u]=sumedge;
}
void addtwo(int u,int v) {
    add(u,v);add(v,u);
}
void build_tree(int u) {
    size[u]=1;
    dfn[u]=++inx;
    for(int i=head[u];i;i=edge[i].next) {
    int v=edge[i].to;
    if(v!=fa[u][0]) {
        fa[v][0]=u;
        dep[v]=dep[u]+1;
        build_tree(v);
        size[u]+=size[v];
    }
    }
}
bool cmp(int a,int b) {
    return dfn[a]<dfn[b];
}
int lca(int a,int b) {
    int l=18;
    if(dep[a]<dep[b]) swap(a,b);
    while(l>=0) {
    if(dep[fa[a][l]]>=dep[b]) {
        a=fa[a][l];
    }
    --l;
    }
    if(a==b) return a;
    l=18;
    while(fa[a][0]!=fa[b][0]) {
    if(fa[a][l]!=fa[b][l]) {a=fa[a][l];b=fa[b][l];}
    --l;
    }
    return fa[a][0];
}
int Jump(int u,int d) {
    for(int l=0;d && l<=18;++l) {
    if(d&1) u=fa[u][l];
    d>>=1;
    }
    return u;
}
void build_auxtree(int aN) {
    num=aN;
    sort(aux+1,aux+num+1,cmp);
    stk[top=0]=0;
    siji(i,1,aN) {
    int u=aux[i];
    if(!top) {
        faAux[u]=0;stk[++top]=u;
    }
    else {
        int Lca=lca(stk[top],u);
        while(dep[stk[top]]>dep[Lca]) {
        if(dep[stk[top-1]]<=dep[Lca]) {
            faAux[stk[top]]=Lca;
        }
        --top;
        }
        if(stk[top]!=Lca) {
        faAux[Lca]=stk[top];
        f[Lca]=make_pair(INF,0);
        aux[++num]=Lca;
        stk[++top]=Lca;
        }
        faAux[u]=Lca;
        stk[++top]=u;
    }
    }
    sort(aux+1,aux+num+1,cmp);
}
void solve() {
    gongzi(i,num,2) {
    int u=aux[i];int v=faAux[u];
    delta[u]=dep[u]-dep[v];
    pii tmp=make_pair(f[u].fi+delta[u],f[u].se);
    if(tmp<f[v]) f[v]=tmp;
    }
    siji(i,2,num) {
    int u=aux[i];int v=faAux[u];
    pii tmp=make_pair(f[v].fi+delta[u],f[v].se);
    if(tmp<f[u]) f[u]=tmp;
    }
    siji(i,1,num) {
    int u=aux[i];int v=faAux[u];
    val[u]=size[u];
    if(i==1) {
        ans[f[u].se]+=n-size[u];
        continue;   
    }
    int son=Jump(u,dep[u]-dep[v]-1);
    int calc=size[son]-size[u];
    val[v]-=size[son];
    if(f[u].se==f[v].se) {ans[f[u].se]+=calc;}
    else {
        int z=f[u].fi-f[v].fi+dep[u]+dep[v]+1 >>1;
        if(f[v].se < f[u].se && dep[u]-z+f[u].fi == z-dep[v]+f[v].fi) {
        ++z;
        }
        z=size[Jump(u,dep[u]-z)]-size[u];
        ans[f[u].se]+=z;
        ans[f[v].se]+=calc-z;
    }
    }
    siji(i,1,num) {
    ans[f[aux[i]].se]+=val[aux[i]];
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&n);
    int u,v;
    xiaosiji(i,1,n) {
    scanf("%d%d",&u,&v);
    addtwo(u,v);
    }
    dep[1]=1;
    build_tree(1);
    siji(j,1,18) {
    siji(i,1,n) {
        fa[i][j]=fa[fa[i][j-1]][j-1];
    }
    }
    int Q;
    scanf("%d",&Q);
    while(Q--) {
    scanf("%d",&m);
    int u;
    siji(i,1,m) {
        scanf("%d",&u);
        f[u]=make_pair(0,u);
        aux[i]=u;
        sol[i]=u;
        ans[u]=0;
    }
    build_auxtree(m);
    solve();
    siji(i,1,m) {
        printf("%d ",ans[sol[i]]);
    }
    putchar('\n');
    }
    return 0;
}

BZOJ 2286: [Sdoi2011]消耗战

Description

在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。

Input

第一行一个整数n，代表岛屿数量。
接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。
第n+1行，一个整数m，代表敌方机器能使用的次数。
接下来m行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,…hk，表示资源丰富岛屿的编号。

Output

输出有m行，分别代表每次任务的最小代价。

Sample Input

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

Sample Output

12
32
22

HINT

对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

题解

虚树题其实都非常简单，只要把虚树建出来然后树dp就好
这道题我们先建一棵虚树，然后dp转移就是
如果它的儿子是一个有资源的节点，那么我们找到他到儿子的路径上边权最小的一条边（这个可以用倍增求lca的相同方式来维护）
如果它的儿子不是一个有资源的节点，那么我们找到儿子路径上边权最小的一条边删掉或者使用它儿子全部删除危险节点的费用

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define pii pair<int,int>
#define fi first
#define se second
#define INF 0x3f3f3f3f
//#define ivorysi
using namespace std;
typedef long long ll;
const int N=250005;
int n,Q,m;
struct node {
    int to,next,val;
}edge[N*4];
int head[N],sumedge;
int fa[N][21],val[N][21],dfn[N],inx,size[N],dep[N];
int sol[N],aux[N],faAux[N],num;
bool vis[N];
int stk[N],top;
ll dp[N];
void add(int u,int v,int c) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    edge[sumedge].val=c;
    head[u]=sumedge;
}
void addtwo(int u,int v,int c) {
    add(u,v,c);add(v,u,c);
}
void build_tree(int u) {
    dfn[u]=++inx;
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
    int v=edge[i].to;
    if(v!=fa[u][0]) {
        fa[v][0]=u;
        val[v][0]=edge[i].val;
        dep[v]=dep[u]+1;
        build_tree(v);
        size[u]+=size[v];
    }
    }
}
int lca(int a,int b) {
    int l=20;
    if(dep[a]<dep[b])swap(a,b);
    while(l>=0) {
    if(dep[fa[a][l]]>=dep[b]) a=fa[a][l];
    --l;
    }
    l=20;
    if(a==b) return a;
    while(fa[a][0]!=fa[b][0]) {
    if(fa[a][l]!=fa[b][l]) a=fa[a][l],b=fa[b][l];
    --l;
    }
    return fa[a][0];
}
bool cmp(int a,int b) {
    return dfn[a]<dfn[b];
}
int getdist(int u,int d) {
    int res=0x7fffffff;
    for(int l=0;d && l<=20;++l) {
    if(d&1) {res=min(res,val[u][l]);u=fa[u][l];}
    d>>=1;
    }
    return res;
}
void build_auxtree(int aN) {
    num=aN;
    sort(aux+1,aux+num+1,cmp);
    stk[top=0]=0;
    siji(i,1,aN) {
    int u=aux[i];
    if(!top) {
        stk[++top]=u;
        faAux[u]=0;
    }
    else {
        int Lca=lca(stk[top],u);
        while(dep[stk[top]]>dep[Lca]) {
        if(dep[stk[top-1]]<=dep[Lca]) {
            faAux[stk[top]]=Lca;
        }
        --top;
        }
        if(Lca!=stk[top]) {
        faAux[Lca]=stk[top];
        aux[++num]=Lca;
        stk[++top]=Lca;
        }
        stk[++top]=u;
        faAux[u]=Lca;
    }
    }
    sort(aux+1,aux+num+1,cmp);
}
void solve() {
    siji(i,1,num) dp[aux[i]]=0;
    gongzi(i,num,1) {
    int u=aux[i],v=faAux[u];
    if(!vis[u]) {
        dp[v]+=min(dp[u],(ll)getdist(u,dep[u]-dep[v]));
    }
    else {
        dp[v]+=getdist(u,dep[u]-dep[v]);
    }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&n);
    int u,v,c;
    xiaosiji(i,1,n) {
    scanf("%d%d%d",&u,&v,&c);
    addtwo(u,v,c);
    }
    dep[1]=1;
    build_tree(1);
    siji(j,1,20) {
    siji(i,1,n) {
        fa[i][j]=fa[fa[i][j-1]][j-1];
        val[i][j]=min(val[i][j-1],val[fa[i][j-1]][j-1]);
    }
    }
    scanf("%d",&Q);
    while(Q--) {
    scanf("%d",&m);
    int u;
    siji(i,1,m) {
        scanf("%d",&u);
        aux[i]=u;
        vis[u]=1;
        sol[i]=u;
    }
    aux[m+1]=1;
    build_auxtree(m+1);
    solve();
    siji(i,1,m) {
        vis[sol[i]]=0;
    }
    printf("%lld\n",dp[1]);
    }
    return 0;
}

BZOJ 3110: [Zjoi2013]K大数查询

Description

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

Input

第一行N，M
接下来M行，每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
1

HINT

【样例说明】

第一个操作后位置 1 的数只有 1 ，位置 2 的数也只有 1 。第二个操作后位置 1的数有 1 、 2 ，位置 2 的数也有 1 、 2 。第三次询问位置 1 到位置 1 第 2 大的数是1 。第四次询问位置 1 到位置 1 第 1 大的数是 2 。第五次询问位置 1 到位置 2 第 3大的数是 1 。‍
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint

题解

整体二分
听说这个题的数据被加强了就变得特别的恶心
首先有一个注意点，它的绝对值小于N可能还会有负数，所以次数界应该是2×N+1
然后这个c是50000×50000会爆int……
读入没改成long long……一直wa……这真是个毒瘤题
我们把所有询问都读进来，对于取值范围进行二分，用树状数组维护一下每个区间里的和有多少，然后看看次数是否大于k，如果大于等于k那么说明它的第k大在左半区间，否则在右半区间

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
//#define ivorysi
using namespace std;
typedef long long ll;
const int N=100500;
int n,m,tot;
int lowbit(int x) {return x&(-x);}
struct BIT {
    ll f[N+5];
    BIT() {
        memset(f,0,sizeof(f));
    }
    void Insert(int pos,ll val) {
        while(pos<=tot) {
            f[pos]+=val;
            pos+=lowbit(pos);
        }
    }
    ll Query(int pos) {
        ll res=0;
        while(pos>0) {
            res+=f[pos];
            pos-=lowbit(pos);
        }
        return res;
    }
    void clear(int pos) {
        while(pos<=N) {
            f[pos]=0;
            pos+=lowbit(pos);
        }
    }
}t,ts;
void Insert(int l,int r,ll v) {
    t.Insert(l,v);
    t.Insert(r+1,-v);
    ts.Insert(l,(l-1)*v);
    ts.Insert(r+1,-r*v);
}
ll Query_prefix(int pos) {
    return t.Query(pos)*pos-ts.Query(pos);
}
ll Query(int l,int r) {
    return Query_prefix(r)-Query_prefix(l-1);
}
int op[N],a[N],b[N],cur[N],ans[N];
ll c[N];
int tmp1[N],tmp2[N];
void Solve(int L,int R,int l,int r) {
    if(L>R) return;
    if(l==r) {
        siji(i,L,R) {
            if(op[cur[i]]==2) ans[cur[i]]=l;
        }
        return;
    }
    int idx1=0,idx2=0,mid=(l+r)>>1;
    siji(i,L,R) {
        if(op[cur[i]]==1) {
            if((int)c[cur[i]]<=mid) {
                Insert(a[cur[i]],b[cur[i]],1);
                tmp1[idx1++]=cur[i];
            }
            else tmp2[idx2++]=cur[i];
        }
        else {
            ll tmp=Query(a[cur[i]],b[cur[i]]);
            if(tmp<c[cur[i]]) {
                tmp2[idx2++]=cur[i];
                c[cur[i]]-=tmp;
            }
            else tmp1[idx1++]=cur[i];
        }
    }
    xiaosiji(i,0,idx1) {
        int k=tmp1[i];
        t.clear(a[k]);ts.clear(a[k]);
        t.clear(b[k]+1);ts.clear(b[k]+1);
    }
    int MID=L+idx1;
    xiaosiji(i,L,MID) cur[i]=tmp1[i-L];
    siji(i,MID,R) cur[i]=tmp2[i-MID];
    Solve(L,MID-1,l,mid);Solve(MID,R,mid+1,r);
    return;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    siji(i,1,m) {
        scanf("%d%d%d%lld",&op[i],&a[i],&b[i],&c[i]);
        if(op[i]==1) {c[i]=(ll)n-c[i]+1;tot=max(tot,(int)c[i]);}
        cur[i]=i;
    }
    Solve(1,m,1,2*n+1);
    siji(i,1,m) {
        if(op[i]==2) printf("%d\n",n-ans[i]+1);
    }
}

2527: [Poi2011]Meteors

Description

Byteotian Interstellar Union (BIU) has recently discovered a new planet in a nearby galaxy. The planet is unsuitable for colonisation due to strange meteor showers, which on the other hand make it an exceptionally interesting object of study.
The member states of BIU have already placed space stations close to the planet's orbit. The stations' goal is to take samples of the rocks flying by. The BIU Commission has partitioned the orbit into msectors, numbered from 1to m, where the sectors 1and mare adjacent. In each sector there is a single space station, belonging to one of the nmember states.
Each state has declared a number of meteor samples it intends to gather before the mission ends. Your task is to determine, for each state, when it can stop taking samples, based on the meter shower predictions for the years to come.
Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。
输入：
第一行是两个数N,M。
第二行有M个数，第i个数Oi表示第i段轨道上有第Oi个国家的太空站。
第三行有N个数，第i个数Pi表示第i个国家希望收集的陨石数量。
第四行有一个数K，表示BIU预测了接下来的K场陨石雨。
接下来K行，每行有三个数Li,Ri,Ai，表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中（如果Li<=Ri，就是Li,Li+1,...,Ri，否则就是Ri,Ri+1,...,m-1,m,1,...,Li），向区间中的每个太空站提供Ai单位的陨石样本。
输出：
N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到，输出NIE。
数据范围：
1<=n,m,k<=3*10^5
1<=Pi<=10^9
1<=Ai<10^9

Sample Input

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

Sample Output

3
NIE
1

题解

这道题整体二分的思路比较明显，然而在统计的过程中临时变量可能会爆long long解决方法就是中途不断判断如果>=就跳出
解题思路是二分一个结束点，然后看看每个国家都攒了多少陨石，把国家分到左右区间去

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define pii pair<int,int>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int L,R,a;
}qry[MAXN];
int n,m,cur[MAXN],k,ans[MAXN],tmp1[MAXN],tmp2[MAXN],p[MAXN];
vector<int> v[MAXN];
ll tr[MAXN];
int lowbit(int x) {return x&(-x);}
void Insert(int pos,ll val) {
    while(pos<=m) {
    tr[pos]+=val;
    pos+=lowbit(pos);
    }
}
ll Query(int pos) {
    ll res=0;
    while(pos>0) {
    res+=tr[pos];
    pos-=lowbit(pos);
    }
    return res;
}
void solve(int L,int R,int l,int r) {
    if(L>R) return;
    if(l==r) {
    siji(i,L,R) {
        ans[cur[i]]=l;
    }
    return;
    }
    int mid=(l+r)>>1;
    siji(i,l,mid) {
    if(qry[i].L<=qry[i].R) {
        Insert(qry[i].L,qry[i].a);
        Insert(qry[i].R+1,-qry[i].a);
    }
    else {
        Insert(qry[i].L,qry[i].a);
        Insert(1,qry[i].a);
        Insert(qry[i].R+1,-qry[i].a);
    }
    }
    int idx1=0,idx2=0;
    siji(i,L,R) {
    int s=v[cur[i]].size();
    ll tmp=0;
    xiaosiji(j,0,s) {
        tmp+=Query(v[cur[i]][j]);
        if(tmp>=(ll)p[cur[i]]) break;
    }
    if(tmp>=(ll)p[cur[i]]) {
        tmp1[idx1++]=cur[i];
    }
    else {
        p[cur[i]]-=(int)tmp;
        tmp2[idx2++]=cur[i];
    }
    }
    siji(i,l,mid) {
    if(qry[i].L<=qry[i].R) {
        Insert(qry[i].L,-qry[i].a);
        Insert(qry[i].R+1,qry[i].a);
    }
    else {
        Insert(qry[i].L,-qry[i].a);
        Insert(1,-qry[i].a);
        Insert(qry[i].R+1,qry[i].a);
    }
    }
    int MID=L+idx1;
    xiaosiji(i,L,MID) cur[i]=tmp1[i-L];
    siji(i,MID,R) cur[i]=tmp2[i-MID];
    solve(L,MID-1,l,mid);solve(MID,R,mid+1,r);
    return ;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    int u;
    siji(i,1,m) {
    scanf("%d",&u);
    v[u].push_back(i);
    }
    siji(i,1,n) {
    cur[i]=i;
    scanf("%d",&p[i]);
    }
    scanf("%d",&k);
    siji(i,1,k) {
    scanf("%d%d%d",&qry[i].L,&qry[i].R,&qry[i].a);
    }
    qry[k+1].L=1,qry[k+1].R=m,qry[k+1].a=1000000000;
    solve(1,n,1,k+1);
    siji(i,1,n) {
    if(ans[i]==k+1) puts("NIE");
    else {
        printf("%d\n",ans[i]);
    }
    }
    return 0;
}

BZOJ 2738: 矩阵乘法

Description

给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。

Input

第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。

Output

对于每组询问输出第K小的数。

Sample Input

2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3

Sample Output

1
3

HINT

矩阵中数字是109以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。

题解

整体二分
这个需要离散化一下所有的值，减少二分次数
二分一个值，然后把小于等于这个数加入矩阵，用树状数组维护矩阵和
对于每一个询问看看矩阵和是否大于等于询问值，然后左右分别处理

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define pii pair<int,int>
#define fi first
#define se second
#define MAXN 500005
//#define ivorysi
using namespace std;
typedef long long ll;
int n,Q;
int lowbit(int x) {return x&(-x);}
struct BIT {
    ll f[505][505];
    void Insert(int x,int y,ll v) {
    while(x<=n) {
        int t=y;
        while(t<=n) {
        f[x][t]+=v;
        t+=lowbit(t);
        }
        x+=lowbit(x);
    }
    }
    ll Query(int x,int y) {
    ll res=0;
    while(x>0) {
        int t=y;
        while(t>0) {
        res+=f[x][t];
        t-=lowbit(t);
        }
        x-=lowbit(x);
    }
    return res;
    }
}tl;
void Insert_pos(int x,int y,int v) {
    tl.Insert(x,y,v);
}
ll Query_prefix(int x,int y) {
    return tl.Query(x,y);
}
ll Query(int x1,int y1,int x2,int y2) {
    return Query_prefix(x2,y2)-Query_prefix(x1-1,y2)-Query_prefix(x2,y1-1)+Query_prefix(x1-1,y1-1);
}
struct node {
    int x,y,v;
    bool operator < (const node &rhs) const {
    return v<rhs.v;
    }
}point[MAXN];
struct data {
    int x1,y1,x2,y2,k;
}qry[MAXN];
int cur[MAXN],ans[MAXN],tmp1[MAXN],tmp2[MAXN],num[MAXN],tot;
void Solve(int L,int R,int l,int r,int st) {
    if(st>n*n) return;
    if(L>R) return;
    if(l==r) {
    siji(i,L,R) {
        ans[cur[i]]=num[l];
    }
    return;
    }
    int mid=(l+r)>>1,rd=n*n+1;
    for(int i=st;i<=n*n;++i) {
    if(point[i].v<=num[mid]) {
        Insert_pos(point[i].x,point[i].y,1);
    }
    else {
        rd=i;
        break;
    }
    }
    int idx1=0,idx2=0;
    siji(i,L,R) {
    ll tmp=Query(qry[cur[i]].x1,qry[cur[i]].y1,qry[cur[i]].x2,qry[cur[i]].y2);
    if(tmp>=(ll)qry[cur[i]].k) {
        tmp1[idx1++]=cur[i];
    }
    else {
        qry[cur[i]].k-=(int)tmp;
        tmp2[idx2++]=cur[i];
    }
    }
    xiaosiji(i,st,rd) {
    Insert_pos(point[i].x,point[i].y,-1);
    }
    int MID=L+idx1;
    xiaosiji(i,L,MID) cur[i]=tmp1[i-L];
    siji(i,MID,R) cur[i]=tmp2[i-MID];
    Solve(L,MID-1,l,mid,st);Solve(MID,R,mid+1,r,rd);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&Q);
    int u;
    siji(i,1,n) {
    siji(j,1,n) {
        int k=(i-1)*n+j;
        point[k].x=i;
        point[k].y=j;
        scanf("%d",&point[k].v);
        num[++tot]=point[k].v;
    }
    }
    siji(i,1,Q) {
    scanf("%d%d%d%d%d",&qry[i].x1,&qry[i].y1,&qry[i].x2,&qry[i].y2,&qry[i].k);
    cur[i]=i;
    }
    sort(point+1,point+n*n+1);
    sort(num+1,num+tot+1);
    tot=unique(num+1,num+tot+1)-num-1;
    Solve(1,Q,1,tot,1);
    siji(i,1,Q) {
    printf("%d\n",ans[i]);
    }
    return 0;
}