递归遍历各种点的每条边即可,在三个排列中

题意:给部分直线,问这个直线在直线x=L,x=翼虎之间有稍许个交点。

倍感温馨那地点很弱,都以望着题解做的orz..

题材链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1019

教师见此文:http://blog.sina.com.cn/s/blog_778e7c6e0100q64a.html

fzu2038 Another Postman
Problem
(递归求解)

 

率先将直线分别跟x=L+eps,x=酷路泽-eps(防止出现相同纵坐标,故+-eps)求他们的交点,求的纵坐标为low,high,首先按low从大到小排序,一遍给予二个ind值,再按high从大到小排序,此时ind的逆序对数即为(L,RAV4)内的交点个数。成功将总结几何难题向树状数组转化。求逆序对数可用归并排序只怕树状数组解决。

题意:n个点n-1条边组成无向连通图,求逐个点到其它全部点的不二法门总和的和。

在二个排列中,假若一对数的左右地方与大小顺序相反,即日前的数当先后边的数,那么它们就称为1个逆序。贰个排列中逆序的总和就称为这一个排列的逆序数。

代码:(树状数组)

题解:每条边的拜会次数为边两端点数乘积的两倍。递归遍历每一个点的每条边即可。

 

图片 1图片 2

图片 3图片 4

如2 4 3 1中,2 1,4 3,4 1,3
1是逆序,逆序数是4。给出1个平头队列,求该体系的逆序数。

#include <iostream>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define eps 1e-5
using namespace std;
#define N 10007

struct node
{
    double x,y;
};

struct Line
{
    node a,b;
    int ind;
    double low,high;
}line[N];

int c[N],n;

int cmp(Line ka,Line kb)
{
    return ka.low > kb.low;
}

int cmp2(Line ka,Line kb)
{
    return ka.high > kb.high;
}

int lowbit(int x){ return x & (-x); }

void modify(int x)
{
    while(x <= n)
        c[x]++,x += lowbit(x);
}

int getsum(int x)
{
    int res = 0;
    while(x > 0)
        res += c[x],x -= lowbit(x);
    return res;
}

int main()
{
    int i,x,j;
    double L,R;
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        for(i=1;i<=n;i++)
            scanf("%lf%lf%lf%lf",&line[i].a.x,&line[i].a.y,&line[i].b.x,&line[i].b.y);
        scanf("%lf%lf",&L,&R);
        L += eps,R -= eps;
        for(i=1;i<=n;i++)
        {
            double k = (line[i].b.y-line[i].a.y)/(line[i].b.x-line[i].a.x);
            line[i].low = k*(L-line[i].a.x) + line[i].a.y;
            line[i].high = k*(R-line[i].a.x) + line[i].a.y;
        }
        sort(line+1,line+n+1,cmp);
        for(i=1;i<=n;i++)
            line[i].ind = i;
        sort(line+1,line+n+1,cmp2);
        int ans = 0;
        for(i=1;i<=n;i++)
        {
            modify(line[i].ind);
            ans += i - getsum(line[i].ind);
        }
        printf("%d\n",ans);
    }
    return 0;
}
 1 #include<cstdio>
 2 #include<vector>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=1e5+5;
 6 typedef long long ll;
 7 int n;
 8 ll sum;
 9 struct edge{
10     int v,c;
11     edge(int v,int c):v(v),c(c){}
12 };
13 vector<edge>g[N];
14 int vis[N];
15 ll dfs(int u){
16     vis[u]=1;
17     ll cnt=1;
18     for(int i=0;i<g[u].size();++i){
19         int v=g[u][i].v;
20         if(vis[v])continue;
21         ll t=dfs(v);
22         sum+=2*g[u][i].c*t*(n-t);
23         cnt+=t;
24     }
25     return cnt;
26 }
27 int main(){
28     int i,t,k,a,b,c;
29     scanf("%d",&t);
30     for(k=1;k<=t;++k){
31         scanf("%d",&n);
32         for(i=0;i<n;++i)g[i].clear();
33         memset(vis,0,sizeof(vis));
34         for(i=0;i<n-1;++i){
35             scanf("%d%d%d",&a,&b,&c);
36             g[a].push_back(edge(b,c));
37             g[b].push_back(edge(a,c));
38         }
39         sum=0;
40         dfs(0);
41         printf("Case %d: %I64d\n",k,sum);
42     }
43     return 0;
44 }

Input

View Code

View Code

第1行:N,N为序列的长度(n <= 50000)
第2 - N + 1行:序列中的元素(0 <= A[i] <= 10^9)

 

 

Output

hdu5355
Cake
(回溯)

输出逆序数

题意:有n个尺码大小分别为1,2,3..,n的蛋糕,问能不能将之平均分为m份(无法再切割),能的话输出每份蛋糕数量及尺寸。

Input示例

题解:无解情况有二种:

4
2
4
3
1

①全部蛋糕大小之和无法被m整除;

Output示例

②每一份蛋糕大小之和小于蛋糕大小最大值n,转化即n<2m-1。

4

其他境况有解。一向用2m去减n,直至n小于40(不清楚怎么是40(>_<))然后回溯法求40以内能划分的景况。

题意:普通话题诶~

官方题解:

 

图片 5

思路:

图片 6图片 7

方法1:归并排序~

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 using namespace std;
 5 const int N=41;
 6 int a[N],id[N],n,m;
 7 vector<int>g[N];
 8 int dfs(int n,int k){
 9     if(n<1)return 1;
10     for(int i=1;i<=m;++i){
11         if(a[i]+n<=k){
12             id[n]=i;
13             a[i]+=n;
14             if(dfs(n-1,k))return 1;
15             id[n]=0;
16             a[i]-=n;
17         }
18     }
19     return 0;
20 }
21 void solve(int n){
22     int i,j;
23     for(i=1;i<=m;++i){
24         g[i].clear();
25         a[i]=id[i]=0;
26     }
27     while(n>40){
28         for(i=1;i<=m;++i) g[i].push_back(n--);
29         for(i=m;i>=1;i--) g[i].push_back(n--);
30     }
31     dfs(n,n*(n+1)/2/m);
32     for(i=1;i<=n;++i) g[id[i]].push_back(i);
33     for(i=1;i<=m;++i){
34         sort(g[i].begin(),g[i].end());
35         int len=g[i].size();
36         printf("%d",len);
37         for(j=0;j<len;++j) printf(" %d",g[i][j]);
38         printf("\n");
39     }
40 }
41 int main(){
42     int t;
43     scanf("%d",&t);
44     while(t--){
45         scanf("%d%d",&n,&m);
46         if((1LL*n*(n+1)/2)%m||n<2*m-1) printf("NO\n");
47         else{
48             printf("YES\n");
49             solve(n);
50         }
51     }
52     return 0;
53 }

归并排序进度为,先不断二分直至每组成分数目为一,此时大家可以将每组成分看做已排序状态;然后在追忆进度把这一个组两两联结,并在联合进度中排序;

View Code

那么大家每贰次联合都得到已排序的组,直至合并为3个组,即已排序数组;

hdu5225 Tom and
permutation
(回溯)

那我们什么样用上述进程计算逆序对数码呢~那就须求分析一下合并的切实进度啦;

题意:给出多少个n的排列,求全部字典序小于给定排列的逆序对数之和。

如若大家明天有多个已排序数组a[p, m], a[q, y] 依次相比较a[p],
a[q],将其中较小的存入一时数组t中,那么最后收获的t数组就是a[p,
y]距离全数因素的已排序状态呀,然后将t数组覆盖a[p, y]数组,那么a[p,
y]哪怕已排序状态了啊~ 
发现了有木有,如果大家在某1回操作大校右侧的元素a[q]存入t中,那么a[q]当先当前左手数组a[p,
m]的有着因素,即a[q]与数组a[p,
m]中各类成分都能整合3个逆序对,对于a[q]要素我们得以拿走(m-p)个逆序对
(数组a[p, m]区间为左闭右开即为区间

题解:预处理1~N全数全排列的逆序数和。枚举第k位。dfs,每一趟考虑当下位(从前的设想过),假诺与原种类对应数差异,前边的逆序对数可得,排列数为阶乘,然后求当前位对前面暴发的逆序对数;否则,将前面数对逆序对数的熏陶留到前边的dfs中改。

[p, m));对于数组a[p, m], a[q, y],如若成分gg,
jj可以组合逆序对,我们得以将间距[p, y)里面可以组合逆序对的事态分为gg,
jj都在 右侧区间恐怕右侧区间,gg,
jj分别位于七个区间中,然则大家简单发现前二种景况就是统一前的第二种情状,例如对于数组a[p,
m] 和a[q, y]我们求出gg, jj分处于两边的逆序对数为ans,
那么在下3回联合进度中,对于a[p’, p] , a[p, q],则ans为gg,
jj都位于a[p, q]中的逆序对数;
从此处大家可以发现即使大家将逆序岁数分二种情景,事实上大家如果一起第2中状态的逆序对数就好啊~

图片 8图片 9

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N=101;
 7 const int mod=1e9+7;
 8 ll s[N],num[N];//逆序数和,排列数
 9 int vis[N],a[N],n,ans;
10 ll dfs(int k,int f){
11     if(k>n) return 0;
12     if(f==0){
13         ans=(ans+s[n-k+1])%mod;
14         return num[n-k+1];
15     }
16     else{
17         ll cnt=0;
18         for(int i=1;i<=a[k];++i){
19             if(vis[i])continue;
20             vis[i]=1;
21             int s1=0,j;
22             for(j=1;j<i;++j)
23                 if(vis[j]==0) s1++;
24             ll t=dfs(k+1,i==a[k]?1:0);
25             vis[i]=0;
26             ans=(ans+t*s1%mod)%mod;
27             cnt=(cnt+t)%mod;
28         }
29         return cnt;
30     }
31 }
32 int main(){
33     int i;
34     s[1]=0;
35     num[1]=1;
36     for(i=2;i<N;++i){
37         s[i]=s[i-1]*i%mod+num[i-1]*((1LL*i*(i-1)/2)%mod)%mod;
38         num[i]=num[i-1]*i%mod;
39         //printf("%lld %lld\n",s[i],num[i]);
40     }
41     while(scanf("%d",&n)==1){
42         ans=0;
43         for(i=1;i<=n;++i) scanf("%d",&a[i]);
44         memset(vis,0,sizeof(vis));
45         dfs(1,1);
46         printf("%d\n",ans);
47     }
48     return 0;
49 }

代码:

View Code

图片 10

 

 1 #include <bits/stdc++.h>
 2 #define MAXN 50010
 3 using namespace std;
 4 
 5 int ans=0;
 6 
 7 void teger_sort(int* a, int* t, int x, int y){
 8     if(y-x>1){  //**递归至单个元素为一组
 9         int m=(y+x)>>1;
10         int p=x, q=m, i=x;
11         teger_sort(a, t, x, m);  //***左递归
12         teger_sort(a, t, m, y);  //***右递归
13         while(p<m||q<y){   //**合并
14             if(q>=y||(p<m&&a[p]<=a[q])){
15                 t[i++]=a[p++];  //**将左边元素复制到临时数组
16             }else{
17                 t[i++]=a[q++]; //**将右边元素复制到临时数组
18                 ans+=m-p; //**累计逆序对的数目
19             }
20         }
21         for(int i=x; i<y; i++){ //**将临时数组里已排序的元素还原到原数组
22             a[i]=t[i];
23         }
24     }
25 }
26 
27 int main(void){
28     int n, a[MAXN], t[MAXN];
29     scanf("%d", &n);
30     for(int i=0; i<n; i++){
31         scanf("%d", &a[i]);
32     }
33     teger_sort(a, t, 0, n);
34     printf("%d\n", ans);
35     return 0;
36 }

hdu4911
Inversion
(归并排序)

图片 11

题意:给出3个队列,可以换到相邻地点的数不超过k次,求交流后小小的逆序数。

 

题解:用归并方法求原体系逆序数cnt,在归并经过中统计每一种小区间的逆序对数,进而总结出大间隔的逆序对数。因为沟通一遍可以减去八个逆序对数。所以最后答案为max(0,cnt-k)。

方法2:树状数组~

留意,归并排序是平静的排序,即约等于的要素的相继不会转移,那是它比赶快排序优势之处。

先是大家先创制3个数轴,对于输入的数据x,咱们给数轴上的x标记1(早先时标记都为0呀~),数轴上x后面的数都比x小,相当于说x前边的兼具标记的数都以不可以与x组成逆序对的数,假诺x是第i个输入,用sum(x)表示x以及后面全体标记的和,即sum=x后边i-三个因素中比x小的个数+1(因为x自身不只怕和团结组合逆序对嘛),那么i-sum(x)就是x和其前方的因素得以整合的逆序对数咯,累加全部因素和其面前的成分结合的逆序对数就是大家要的答案啦~

图片 12图片 13

对于那里的数轴大家得以一直用数组标记就好了,不过那里的x数据范围是1e9,直接开数组肯定开不下啦,用map会超时,所以大家须要对输入的数码先hash一下~

 1 #include<cstdio>
 2 long long cnt,k;
 3 int n,a[100001],b[100001];
 4 void Merge(int l,int m,int r){
 5     int i=l,j=m+1,c=0;
 6     while(i<=m||j<=r){
 7         if(a[i]<=a[j]&&i<=m||j>r)
 8             b[c++]=a[i++];
 9         else{
10             b[c++]=a[j++];
11             cnt+=(m-i+1);
12         }
13     }
14     for(i=0;i<c;++i)
15         a[l+i]=b[i];
16 }
17 void merge_sort(int l,int r){
18     if(l<r){
19         int m=(l+r)/2;
20         merge_sort(l,m);
21         merge_sort(m+1,r);
22         Merge(l,m,r);
23     }
24 }
25 int main(){
26     while(scanf("%d%lld",&n,&k)==2){
27         for(int i=0;i<n;++i) scanf("%d",&a[i]);
28         cnt=0;
29         merge_sort(0,n-1);
30         if(k>=cnt)printf("0\n");
31         else printf("%lld\n",cnt-k);
32     }
33     return 0;
34 }

但是这么些思路假如向来暴力的话照旧会晚点,不过,求sum(x)就是距离求和嘛,区间求和大家可以用树状数组恐怕线段树嘛,那里树状数组和线段树的意义等同,大家就用代码更简单的树状数组啦;要讲树状数组的话比较费心,那里就交给1个自家觉得讲的科学的树状数组博客好了~

View Code

http://blog.csdn.net/ljd4305/article/details/10101535

 

 

hdu5323 Solve
this interesting
problem
(dfs)

代码:

题意:求最小的线段树的右端点,使得给定的间距[L,R]是某节点

 

题解:注意标题标多寡,L/(Sportage-L+1)<=二〇一六,向上搜时,L不变,(ENVISION-L+1)翻倍,所以L/(奥迪Q5-L+1)每上一层变为原来的五成,所以层数最多只有log22015=11,简单想到dfs暴力增加。

图片 14

从[L,R]向根部搜,依据(L+本田UR-V)的奇偶性判断其父区间有八种恐怕:[L,2R-L]、[2(L-1)-R,R]、[L,2R-L+1]、[2(L-1)-R+1,R]。其中父节点为[L,2R-L]时,必须XC60>L,否则它右外甥为空,就争辨了。

 1 #include <bits/stdc++.h>
 2 #define MAXN 50010
 3 using namespace std;
 4 
 5 int tree[MAXN], n;
 6 
 7 int lowbit(int x){ //**得到pow(2, k), 其中k为x的二进制末尾0的个数即x二进制最低位1的值
 8     return x&(-x);
 9 }
10 
11 void update(int x, int d){ //**向上更新父节点及根节点~
12     while(x<=n){
13         tree[x]+=d;
14         x+=lowbit(x);
15     }
16 }
17 
18 int sum(int x){ //**向下求和
19     int ans=0;
20     while(x>0){
21         ans+=tree[x];
22         x-=lowbit(x);
23     }
24     return ans;
25 }
26 
27 int main(void){
28     pair<int, int> p[MAXN];
29     int gg[MAXN], ans=0;
30     scanf("%d", &n);
31     for(int i=1; i<=n; i++){  //**hash
32         scanf("%d", &p[i].first);
33         p[i].second=i
34     }
35     sort(p+1, p+n+1);
36     for(int i=1; i<=n; i++){
37         gg[p[i].second]=i;
38     }
39     for(int i=1; i<=n; i++){
40         update(gg[i], 1); //因为x不能和自己组成逆序对,要减去,所以我们要先更新再求和,更新后sum(x)就包括了x了嘛~
41         ans+=i-sum(gg[i]);
42     }
43     printf("%d\n", ans);
44     return 0;
45 }

瞩目到无解条件:L<(宝马X3-L+1),因为左孙子不容许比右外甥表示的区间长度小。

图片 15

图片 16图片 17

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 const ll inf=0x3f3f3f3f;
 6 ll L,R,n;
 7 void dfs(ll l,ll r){
 8     if(l==0||r>=2*R){
 9         if(l==0&&n>r)n=r;
10         return;
11     }
12     int c=r-l+1;
13     if(l<c)return;
14     dfs(l-c,r);
15     dfs(l-c-1,r);
16     dfs(l,r+c);
17     if(c>1) dfs(l,r+c-1);
18 }
19 int main(){
20     while(scanf("%lld%lld",&L,&R)==2){
21         n=inf;
22         dfs(L,R);
23         printf("%lld\n",n==inf?-1:n);
24     }
25 }

 

View Code

 

相关文章