泉五培训Day1
t1 树学
题目
【问题描述】
给定一颗 n 个点的树，树边带权，试求一个排列 p，最大化下式
其中，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
#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;
}
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
#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;
}
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
#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;
}