欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

泉五培训Day1

程序员文章站 2022-09-07 20:58:42
T1 树学 题目 【问题描述】 给定一颗 n 个点的树,树边带权,试求一个排列 P,最大化下式 其中,calc(a, b)表示树上由a到b经过的最大边权。 【输入格式】 第一行一个整数 n,表示点数下接 n − 1 行,每行三个数 u, v, w 表示一条连接点 u 和点 v 权值为 w 【输出格式 ......

t1 树学

题目

【问题描述】

给定一颗 n 个点的树,树边带权,试求一个排列 p,最大化下式

泉五培训Day1

其中,calc(a, b)表示树上由a到b经过的最大边权。

【输入格式】

第一行一个整数 n,表示点数下接 n − 1 行,每行三个数 u, v, w 表示一条连接点 u 和点 v 权值为 w

【输出格式】

总共一行一个整数,表示答案

【输入样例】

2

1 2 2333

【输出样例】

2333

【数据范围】

对于前5%的数据满足 n ≤ 8

对于前40%的数据满足 n ≤ 20

对于前60%的数据满足 n ≤ 200

对于100%的数据满足 n ≤ 100

解析

先从边权最小的边开始累加,尽可能的减少当前边的贡献次数。发现每轮最少贡献一次,即将边两侧的点在p中完全分开。

试过多组数据之后,不难发现,答案即为所有边权之和。

1、最长边只计算过一次。

2、如果次长边被经过两次及以上,从次长边的一端出发,到了最长边的一端,走了一个来回,很显然,这是错误的,所以,次长边只计算过一次。

3、以此类推,最后,所有边都只计算过一次。

code

泉五培训Day1
#include <iostream>
#include <cstdio>
using namespace std;
int n,u,v,w;
long long ans;
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>w;
        ans+=w;
    }
    cout<<ans;
    return 0;
}
view code

 

 

 

 

 

t2 保留道路

题目

【问题描述】

很久很久以前有一个国家,这个国家有n个城市,城市由1,2,3,…,n标号,城市间有m条双向道路,每条道路都有两个属性g和s,两个城市间可能有多条道路,并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因,国王不得不下令减小花费从而关闭一些道路,但是必须要保证任意两个城市相互可达。

道路花费的计算公式为wg*max{所有剩下道路的属性g}+ws*max{所有剩下道路的属性s},其中wg和ws是给定的值。国王想要在满足连通性的前提下使这个花费最小,现在需要你计算出这个花费。

【输入格式】

输入文件名为road.in。

第一行包含两个正整数n和m。

第二行包含两个正整数wg和ws。

后面的m行每行描述一条道路,包含四个正整数u,v,g,s,分别表示道路连接的两个城市以及道路的两个属性。

【输出格式】

输出文件名为road.out。

输出一个整数,表示最小花费。若无论如何不能满足连通性,输出-1。

【输入输出样例】

road.in

road.out

3 3

2 1

1 2 10 15

1 2 4 20

1 3 5 1

 

30

 

【数据规模与约定】

对于10%的数据,n≤10,m≤20;

对于30%的数据,n≤100,m≤1000;

对于50%的数据,n≤200,m≤5000;

对于100%的数据,n≤400,m≤50000,wg,ws,g,s≤1000000000。

解析

这题难在最小生成树有两个变量。

先按g从小到大排序,在加入边的过程中发现,当前的最小生成树只会由上一次的最小生成树和新边构成。

所以每次只需在n条边中生成最小生成树即可。

code

泉五培训Day1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define inf 100000000000000000ll;
#define m 50010
#define n 410
long long ans=inf;
long long n,m,ws,wg,cnt,f[n];//cnt表示已生成的树的边数 
struct rec{
    long long x,y;
    bool vis;//是否被使用过 
    long long g,s;
}tree[m],small[m],ra[m];//tree表示初始数据,small表示最小生成树的数据,ra是最小生成树的替身 
int find(long long x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]); 
}
bool cmp(rec a,rec b)
{
    if(a.g!=b.g) return a.g<b.g;
    else return a.s<b.s;
}
void kruskal(long long maxg)//生成最小生成树 
{
    for(int i=1;i<=cnt;i++)
    {
        ra[i]=small[i];//复制数据 
        ra[i].vis=0;//初始化,0为未访问 ,1为访问 
    }
    long long maxs=0,tot=0;
    for(int i=1;i<=n;i++)   f[i]=i; //并查集初始化
    for(int i=1;i<=cnt;i++)
    {
        int a=find(small[i].x);
        int b=find(small[i].y);
        if(a!=b)
        {
            maxs=max(maxs,small[i].s);
            f[a]=b;
            tot++;
            ra[i].vis=1;//标记 
        }
        if(tot==n-1) 
        {
            int num=0;
            for(int i=1;i<=cnt;i++)
                if(ra[i].vis) small[++num]=ra[i]; 
            cnt=num;
            ans=min(ans,maxg+maxs);
            break; 
        }
    }
}
void start()
{
    for(int i=1;i<=m;i++)//按g的大小,从小到大枚举边
    {
        if(tree[i].g+tree[i].s>ans) continue;
        int pos=cnt+1;
        for(int j=1;j<=cnt;j++)
        {
            if(small[j].s>tree[i].s)
            {
                pos=j;
                break;
            }
        }
        if(pos==cnt+1)
        {
            cnt++;
            small[cnt]=tree[i];
        }
        else
        {
           cnt++;
           for(int j=cnt;j>=pos+1;j--) small[j]=small[j-1];
           small[pos]=tree[i];
        }
        kruskal(tree[i].g);
     } 
}
int main()
{
    cin>>n>>m>>wg>>ws;
    for(int i=1;i<=m;i++)
    {
        cin>>tree[i].x>>tree[i].y>>tree[i].g>>tree[i].s;
        tree[i].g*=1ll*wg;
        tree[i].s*=1ll*ws;//初始化 
    } 
    sort(tree+1,tree+m+1,cmp);//将原数据的g从小到大排序
    start();
    cout<<ans;
    return 0;
}
view code

 

 

 

 

 

t3 appointment

题目

【问题描述】

定义两个排列v_i和g_i的“友好值”为:在1 <= i <= n中,出现v_i > g_i的次数。

给定n,m,以及一个1~n的排列v_i,你需要分别求出和排列v_i“友好值”为0,1,2,...,m的排列g_i有多少个。

【输入格式】

输入一共有两行。

第一行包含两个整数 n,m,意义如上

第二行包含 n 个整数,第 i 个为 vi,意义如上

【输出格式】

输出共 m+1 行,第i行友好值为 i-1 时的g_i有多少个。由于答案可能较大,请输出ans%998244353 的结果。

【样例输入】

3 2

1 3 2

【样例输出】

1

4

1

【样例解释】

友好值为0时,排列g只能是(1, 3, 2) 

友好值为1时,排列g可以是(1, 2, 3)  (2, 1, 3)  (2, 3, 1)  (3, 1, 2)    

友好值为2时,排列g只能是(3, 2, 1)

【数据范围】

对于20%的数据: n <= 10

对于100%的数据: n <= 6000

解析

先试几组数据,可以发现答案与v_i无关。

设f[i][j]表示当前序列长度为i时,友好值为j。

如果在原有序列中加入一个新数字,原有序列的友好值要么+1要么不变。

若友好值不变,则把新加入的数和一个具有贡献的数交换位置,共有(j+1)种换法。

若友好值+1,则把新加入的数和一个没有贡献的数交换位置,即(i-1)-(j-1),即i-j。

于是得出了状态转移方程f[i][j]=f[i-1][j]*(j+1)+f[i-1][j-1]*(i-j)。

边界:f[i][0]=1。

code

泉五培训Day1
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=998244353;
long long f[10000][10000];
int main()
{
    int n,m,temp;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>temp;
    for(int i=1;i<=n;i++) f[i][0]=1;
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++) f[i][j]=(f[i-1][j]*(j+1)%mod+f[i-1][j-1]*(i-j)%mod)%mod;
    for(int i=0;i<=m;i++) cout<<f[n][i]<<endl;
    return 0;
 } 
view code