树上结点对路径和

发表于2021-10-24更新于2021-10-24

Tree and Permutation

题意：一棵树有n < 1e5个点，每条边有个权值，n个点全排列，若每个排列为a1,a2…..an,
则每个排列的值为(a1,a2),(a2,a3)…..(an-1,an)的和，括号表示两点路径值，求所有排列值的和。


`










`
思路：公式不难推出为2*(n-1)!Dis。Dis为所有结点对的路径和。
直接求Dis，因为有1e51e5对，不可。我们转而考虑求每条边的贡献。
每条边连接两个连通块，设两个连通块点数分别为a,b。那么a * b 即为此边的贡献次数。
遍历每条边即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*** 
 * @Practice Win
 * 洛谷 P3379 【模板】最近公共祖先（LCA）
 */
#include<cstdio>
#include<iostream>
#include<cstring>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff//10^9级别，不到2^32
typedef long long ll;
const ll maxn=2e5+11;
const ll mod=1e9+7;
struct Edge{
	ll to,w,nx;
}e[maxn];
ll head[maxn],f[maxn];
ll tmp,cnt,n,ans;

void init(){
	memset(head,0,sizeof(head));
	tmp=2;cnt=1;ans=0;
}

void add(ll u,ll v,ll w){
	e[tmp]={v,w};e[tmp].nx=head[u];head[u]=tmp++;
}
ll dfs(ll u,ll fu){
	ll sum=1;
	for(ll i=head[u];i;i=e[i].nx){
		ll v=e[i].to,w=e[i].w;
		if(v!=fu){
			ll a=dfs(v,u);
			sum=sum+a;
			ans=(ans+(a*(n-a)%mod)*w%mod)%mod;
		}
	}
	return sum;
}
void solve(){
	dfs(1,0);
	//cout<<ans<<endl;
	ans=(ans*f[n-1])*2%mod;
	printf("%lld\n",ans);
}

int main(){
	// cin
	// cout
    f[0]=1;
    for(ll i=1;i<maxn;i++){
    	f[i]=f[i-1]*i%mod;
    }
    while(scanf("%lld",&n)==1){
    	init();
    	for(ll i=1;i<=n-1;i++){
    		ll u,v,w;
    		scanf("%lld%lld%lld",&u,&v,&w);
    		add(u,v,w);add(v,u,w);
    	}
    	solve();
    	//printf("%lld\n",tmp);
    }
    return 0;
}

思维+数学

发表于2021-10-21更新于2021-10-21

Sky Garden

题意，给n < 500个以原点为圆心的等间距圆，被m < 500条过圆心的直线均分，其中圆和直线以及直线和直线的交点构成了一个点集，问点集内的两两最短距离的和是多少（其中最短距离只能是从直线或圆上走出来的）。

·
·
·
·
·
··
·
·
·
··

··
·
·
·
·
·
·
·
·
·

··
·
·
·

思路：
不难证明和发现，从a到b，要么走线段+圆弧，要么就是两个线段。
然后这道题就可以暴力莽过去了。
也可以优化到n方。
对于一个圆，分点在圆上和在圆内考虑。
踩坑：这道都是浮点数的题，一个浮点数公式，写了a/2 * b * c，a为整形，b,c为浮点型，发生了整形截断，错了。

这道题让我知道，若求和可以用公式化简，就可以不用循环求和，优化复杂度。
还有就是这道题，O(1),O(n),O(n方)的运行时间几乎都没有区别。

n方做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-21 16:52:25
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
const ld pi=acos(-1);
ll n,m;
void solve(){
    ld ans=0;
    if(m==1){
        ans=1.0/6.0*(2*n+2)*(2*n+1)*(2*n)-n*(n+1);//此处推公式可以用到裂项相消法
        printf("%.10Lf\n",ans);
        return ;
    }
    for(ld r2=1;r2<=n;r2++){
        //圆内:
        ld ans1=0;
        for(ld i=1;i<=m-1;i++){
            if(i*pi*r2/m<2*r2){
                ans1=ans1+r2*(r2-1.0)/2.0*(i*pi/m+1);
            }
            else{
                ans1=ans1+3*r2/2.0*(r2-1);// /2出错
            }
        }  
        ans1=ans1*2;
        ans1=ans1+r2*(2*r2-1);
        ans1=ans1*2*m;
        ans+=ans1;
        //圆上：
        ld ans2=0;
        for(ld i=1;i<=m-1;i++){
            ans2+=min(i*pi*r2/m,(ld)2*r2);
        }
        ans2=ans2*2+2*r2;
        ans=ans+ans2*2*m/2.0;
    }
    printf("%.10Lf\n",ans);
}
int main(){
    cin>>n>>m;
    solve();
    return 0;
}

O(n) 做法：
/*

  • @Author: Marhoosh

  • @Date: 2021-10-11 11:00:11

  • @Last Modified by: Marhoosh

  • @Last Modified time: 2021-10-21 18:07:32

  • /
    #include<bits/stdc++.h>
    using namespace std;
    #define Debug(x) cout<<#x<<’:’<<x<<endl
    #define INF 0x7fffffff
    typedef long long ll;
    typedef long double ld;
    typedef pair<ll,ll> P;
    const ll maxn=2e5+11;
    const ld pi=acos(-1);
    ld n,m;
    void solve(){
    ld ans=0;
    if(m==1){

       ans=1.0/6.0*(2*n+2)*(2*n+1)*(2*n)-n*(n+1);
   printf("%.10Lf\n",ans);
   return ;

    }
    ld ans1=0,ans2=0;
    for(ld i=1;i<=m-1;i++){

       if(i*pi/m<2){
       ans1=ans1+1.0/6.0*(n+1)*n*(n-1)*(i*pi/m+1);
       ans2=ans2+i*pi/m;
   }
   else{
       ans1=ans1+1.0/2.0*(n+1)*n*(n-1);
       ans2=ans2+2.0;
   }

    }
    ans1*=2;
    ans1=ans1+n*(n+1)(4n-1)/6.0;
    ans=ans+ans12m;

    ans2=ans22+2;
    ans2    =m;
    ans=ans+ans2n(n+1.0)/2.0;

// for(ld r2=1;r2<=n;r2++){
//     //圆内:
//     ld ans1=0;
//     for(ld i=1;i<=m-1;i++){
//         if(i*pi*r2/m<2*r2){
//             ans1=ans1+r2*(r2-1.0)/2.0*(i*pi/m+1);
//         }
//         else{
//             ans1=ans1+3*r2/2.0*(r2-1);// /2出错
//         }
//     }  
//     ans1=ans1*2;
//     ans1=ans1+r2*(2*r2-1);
//     ans1=ans1*2*m;
//     ans+=ans1;
//     //圆上：
//     ld ans2=0;
//     for(ld i=1;i<=m-1;i++){
//         ans2+=min(i*pi*r2/m,(ld)2*r2);
//     }
//     ans2=ans2*2+2*r2;
//     ans=ans+ans2*2*m/2.0;
// }
printf("%.10Lf\n",ans);

}
int main(){
cin>>n>>m;
solve();
return 0;
}

O(1)做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-21 18:25:51
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
const ld pi=acos(-1);
ld n,m;
void solve(){
    ld ans=0;
    if(m==1){
        ans=1.0/6.0*(2*n+2)*(2*n+1)*(2*n)-n*(n+1);
        printf("%.10Lf\n",ans);
        return ;
    }
    ld ans1=0,ans2=0;
    ld x=floor(2.0*m/pi),y=ceil(2.0*m/pi);
    ans1=((1.0+x)*x/2.0*pi/m+x)*(n+1)*n*(n-1)/6.0;
    ans1=ans1+1.0/2.0*(n+1)*n*(n-1)*(m-1-y+1.0);

    ans2=(1.0+x)*x/2.0*pi/m;
    ans2=ans2+2.0*(m-1-y+1.0);

    // for(ld i=1;i<=m-1;i++){
    //     if(i*pi/m<2){
    //         ans1=ans1+1.0/6.0*(n+1)*n*(n-1)*(i*pi/m+1);
    //         ans2=ans2+i*pi/m;
    //     }
    //     else{
    //         ans1=ans1+1.0/2.0*(n+1)*n*(n-1);
    //         ans2=ans2+2.0;
    //     }
    // }
    ans1*=2;
    ans1=ans1+n*(n+1)*(4*n-1)/6.0;
    ans=ans+ans1*2*m;

    ans2=ans2*2+2;
    ans2*=m;
    ans=ans+ans2*n*(n+1.0)/2.0;


    // for(ld r2=1;r2<=n;r2++){
    //     //圆内:
    //     ld ans1=0;
    //     for(ld i=1;i<=m-1;i++){
    //         if(i*pi*r2/m<2*r2){
    //             ans1=ans1+r2*(r2-1.0)/2.0*(i*pi/m+1);
    //         }
    //         else{
    //             ans1=ans1+3*r2/2.0*(r2-1);// /2出错
    //         }
    //     }  
    //     ans1=ans1*2;
    //     ans1=ans1+r2*(2*r2-1);
    //     ans1=ans1*2*m;
    //     ans+=ans1;
    //     //圆上：
    //     ld ans2=0;
    //     for(ld i=1;i<=m-1;i++){
    //         ans2+=min(i*pi*r2/m,(ld)2*r2);
    //     }
    //     ans2=ans2*2+2*r2;
    //     ans=ans+ans2*2*m/2.0;
    // }
    printf("%.10Lf\n",ans);
}
int main(){
    cin>>n>>m;
    solve();
    return 0;
}

二分思维好题

发表于2021-10-20更新于2021-10-20

Walker Gym - 102900D

题面：在一个长为n的线段，左端点为0，右端点为n

有两个端点分别位于p1,p2，它们的速度分别为v1,v2

问最少需要多少时间，可以使得p1，p2的路程覆盖整条线段
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
··

··

·
·
·

思路：
分类讨论：

先令p1<p2

①p1走完全程

②p2走完全程

③p1向右走完全部，p2向左走完全部

④p1走完左边的全部，p2走完右边的全部，剩余中间的部分p1与p2共同走完，二分中间相遇位置即可。

踩坑:最后二分出来的结果，没有取max(t1,t2)，只取了t1的值wa了。
原因是二分出来的最后结果，不能保证t1==t2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-20 15:21:01
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
ld x,x1,v1,x2,v2,ans;
void load(ld xx){
    ans=min(ans,xx);
}
void solve(){
    ld xx=min(x+x1,x-x1+x);
    load(xx/v1);//A走完全程
    xx=min(x+x-x2,x+x2);
    load(xx/v2);//B走完全程
    ld tt=max((x-x1)/v1,x2/v2);
    load(tt);//A,B对向走
    ld l=x1,r=x2;
    while(r-l>1e-12){
        ld mid=(l+r)/2;
        ld t1=min(x1+mid,mid+mid-x1)/v1;
        ld t2=min(x-mid+x2-mid,x-mid+x-x2)/v2;
        //load(max(t1,t2));
        if(t1<t2)  l=mid;
        else  r=mid;
    }
    ld t1=min(x1+l,l+l-x1)/v1;
    ld t2=min(x-l+x2-l,x-l+x-x2)/v2;
    load(max(t1,t2));
    printf("%.10LF\n",ans);
}
int main(){
    ll ca;cin>>ca;
    while(ca--){
        scanf("%Lf%Lf%Lf%Lf%Lf",&x,&x1,&v1,&x2,&v2);
        if(x1>x2){
            swap(x1,x2);swap(v1,v2);
        }
        ans=1e12;
        solve();
    }
    return 0;
}


矩阵最短路

发表于2021-10-18更新于2021-10-18

The Shortest Path HDU - 2807

题面：有n < 80个点，每个点用一个m * m(m < 80)的矩阵表示，若a,b,c三个点满足a * b=c，则表示a到c有一条长度为1的单向边。
有q < 80次询问，每次询问x,y的最短路

关键在于如何处理这个矩阵。

思路在下面





















这道题挺有意思的，得处理下矩阵的相乘，其实没必要弄得很复杂，直接暴力处理就行了。

floyd变形题，处理一下矩阵即可，因为数据不大，暴力求就行，也可以采取乘法优化。踩坑：注意A*B=B不能说明AB之间有边，在这里wa了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-18 15:18:30
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e2+11;
struct Node{
    ll a[maxn][maxn];
}city[maxn];
ll gra[maxn][maxn];
ll n,m;
void matirx(ll u,ll t){
    ll mid[maxn][maxn];
    for(ll i=1;i<=m;i++){
        for(ll j=1;j<=m;j++){
            mid[i][j]=0;
            for(ll k=1;k<=m;k++){
                mid[i][j]+=city[u].a[i][k]*city[t].a[k][j];
            }
        }
    }
    for(ll v=1;v<=n;v++){
        if(v==u || v==t)  continue;
        ll flag=1;
        for(ll i=1;i<=m;i++){
            if(flag==0)  break;
            for(ll j=1;j<=m;j++){
                if(mid[i][j]!=city[v].a[i][j]){
                    flag=0;break;
                }
            }
        }
        if(flag)  gra[u][v]=1;
    }
}
void floyd(){
    for(ll k=1;k<=n;k++){
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++)  gra[i][j]=min(gra[i][j],gra[i][k]+gra[k][j]);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n>>m && (n||m)){
        memset(gra,0x1f,sizeof(gra));
        for(ll c=1;c<=n;c++){
            for(ll i=1;i<=m;i++){
                for(ll j=1;j<=m;j++)  cin>>city[c].a[i][j];
            }
        }
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                if(i==j)  continue;
                matirx(i,j);
            }
        }
        floyd();
        ll q;cin>>q;
        for(ll i=1;i<=q;i++){
            ll u,v;cin>>u>>v;
            if(gra[u][v]>1e9)  cout<<"Sorry"<<endl;
            else  cout<<gra[u][v]<<endl;
        }
    }
    return 0;
}

二分

发表于2021-10-12更新于2021-10-12

据说只有10%的程序员能写对二分😮

阅读全文