6月13日NOIP训练总结
T1
T1还是一如既往的水，但有个小技巧值得留意下：在对数据溢出的处理，我们把乘法转除法来处理。 设maxa=1e18 。在判断a × b > m a x a a\times b>maxaa×b>maxa的过程中，a × b a\times ba×b可能溢出long long，转化成a > n a x a / b a>naxa/ba>naxa/b即可。
#include<bits/stdc++.h>
using namespace std;
const long long maxa=1e18;
int n,flag=0;
long long ans=1,temp;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>temp;
if(temp==0) //为0则继续算必定为0，提前结束
{
cout<<0<<endl;
return 0;
}
if(maxa/temp<ans) //溢出，但是最终结果可能为0，不能提前结束
flag=1;
else
ans=ans*temp;
}
if(flag)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
T2
实质上就是质因数分解，顺带着复习下质数的判定
对一个大于1的自然数 n 依次判断 2 → √n 能否整除 n，如果发现一个数能整除 n，那么 n 不是素数，否则是。
还有质数的筛选，埃氏筛法蛮不错的。
题解
算法步骤：
1、从1～√?枚举能整除N的素数i，并计算i能整除N几次，求出i的指数大小cnt。
2、用函数solve()计算cnt能分成的次数res比如：
cnt=3可以分成2次乘积，即i 3 = i 2 × i i^3=i^2\times ii3=i2×i于是i的res=2。
3、对枚举的、所有i的res求和即为答案。
注意细节：N被所有符合条件的素数整除后，可能结果不为1，此时答案ans++，需要
特判一下。
T3
一个贪心，没啥好说的。
题解
倒着循环每次最早能上班的时刻上班，然后找c天后的不是x的天；
然后正着循环做一遍。 如果两遍都要某一个点的话那个点就是答案。这是因为这两遍分别是Tom上班的左区间和右区间，只要这个区间最后聚在一个点，这一天就是确定的一天。
T4
T4值得细看，先列题。
【题目描述】
老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10，要求在6天内交，那么要想拿到这10学分，就必须在第6天结束前交。 每个作业的完成时间都是只有一天。例如，假设有7次作业的学分和完成时间如下：
作业号 1 2 3 4 5 6 7
期 限 1 1 3 3 2 2 6
学 分 6 7 2 1 4 5 1
最多可以获得15学分，其中一个完成作业的次序为2，6，3，1，7，5，4，注意可能
还有其他方法。
你的任务就是找到一个完成作业的顺序获得最大学分。
【输入格式】
第一行一个整数N，表示作业的数量；
接下来N行，每行包括两个整数，第一个整数表示作业的完成期限，第二个数表示该作
业的学分。
【输出格式】
输出一个整数表示可以获得的最大学分。保证答案不超过C语言的int范围。
【样例输入】
7
1 6
1 7
3 2
3 1
2 4
2 5
6 1
【样例输出】
15
【数据范围】
对于部分数据，0＜N≤1000；
对于部分数据，0＜N≤10000；
对于部分数据，0＜N≤100000；
对于部分数据，作业的完成期限小于100；
对于部分数据，作业的完成期限小于1000；
对于所有数据，0＜N≤1000000，作业的完成期限均是小于700000的正整数。
这道题和智力大冲浪很像 传送门 两道题都是类似带限期和罚款的单位时间任务调度。
题目模型：
有n个任务，每个任务都需要1个时段去执行，任务i的截止时间di（1≤di≤n）表示要求任务i在时间段di必须完成，误时惩罚wi表示若任务i未在时间段di及之前完成，将导致wi的罚款。确定所有任务的执行顺序，使得惩罚最少。
所以很自然的这类题都有类似的贪心做法，要使惩罚最少，我们显然应尽量先完成wi值较大的任务。 将任务按wi从大到小进行排序，然后按照排好的顺序依次对任务进行安排。安排的规则为：使得处理任务i的时间既在1～di之内，又尽量靠后（即从di倒着往前尝试）；如果1～di范围之内的时间都已经安排，则放弃处理该任务，接受惩罚。
代码
#include<bits/stdc++.h>
using namespace std;
struct work
{
int val;
int li;
};
work a[1000001];
int n,pre[1000001],ans,whe[1000001];
bool comp(work a,work b)
{
return a.val>b.val;
}
int Find(int pos)
{
if(whe[pos]==0)
return pos;
pre[pos]=Find(pre[pos]);
return pre[pos];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].li,&a[i].val);
sort(a+1,a+1+n,comp);
for(int i=1;i<=n;i++)
pre[i]=i-1;
for(int i=1;i<=n;i++)
{
int t=Find(a[i].li);
if(t!=0)
{
whe[t]=1;
ans+=a[i].val;
if(t!=a[i].li)
pre[a[i].li]=pre[t];
}
}
cout<<ans;
return 0;
}
最最最最重要的T5
【问题描述】
给出一张n个点，m条边的无向图，摧毁每条边都需要一定的体力，并且花费的体力值
各不相同，给定图中两个点x，y（x≠y），每当(x,y)之间存在路径，就需要不断摧毁当前图中花费体力最少的一条边，直到该路径不联通。他定义cost(x,y)为摧毁(x,y)之间路径花费的体力和。
他想要求出以下这个结果：
( ∑ 1 ≤ i , j ≤ n c o s t ( i , j ) ) % 1 0 9 (\sum\limits_{1\le i,j\le n}cost(i,j))\%10^9(1≤i,j≤n∑cost(i,j))%109
其中 i,j∈n，并且i＜j 。
【输入格式】
第一行两个整数n，m，表示点数和边数。
接下来m行，每行三个整数x，y，z，表示x和y之间存在一条花费体力为z的无向边。
【输出格式】
输出一个整数表示所求结果。
【输入样例】
6 7
1 2 10
2 3 2
4 3 5
6 3 15
3 5 4
4 5 3
2 6 6
【输出样例】
256
【数据范围】
对50%的输入数据 ：1≤n≤100；1≤m≤1000
对100%的输入数据 ：1≤n,m≤100000；1≤z≤100000
我们想一条边能为点对(i,j)贡献的情况是去掉比他权值小的边，i，j仍然联通的状况，也就是权值大于等于他的边组成的图中，i，j 联通的状况，那么我们可以按权值从大到小枚举，计算加入这条边后图中有多少点对联通，更新答案；现在的问题就变成了如何维护图，考虑使用并查集，如果两个端点在同一联通块中，点对数目不增加，反之，增加的点对为两个联通块的数目之积，问题解决，复杂度为O(m*log(m))。
没错，虽然它问你删掉的边的和，但你没必要选择去枚举删的边再加，选择反着来也是一种思路。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,fa[100001],x,y,z,num[100001],ans,sum;
struct bian
{
int fr;
int to;
int zhi;
};
bian q[100001];
bool comp(bian a,bian b)
{
return a.zhi>b.zhi;
}
int Get(int x)
{
if(fa[x]==x)
return x;
fa[x]=Get(fa[x]);
return fa[x];
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i,num[i]=1;
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&q[i].fr,&q[i].to,&q[i].zhi);
}
sort(q+1,q+1+m,comp);
for(int i=1;i<=m;i++)
{
int f1=Get(q[i].fr);
int f2=Get(q[i].to);
if(f1!=f2)
{
fa[f1]=f2;
sum+=num[f1]*num[f2];//这可以想想为什么
num[f2]+=num[f1];
}
ans+=sum*q[i].zhi;//还有这，鬼知道我个蒟蒻想了多久
}
cout<<ans%1000000000;
}