董神出的题目 第一次成功卡上200pts...
A 物理
问题描述
物理课上，nodgd一拍脑袋，发明了一个最短路算法：给无向图的每个节点制作一个小球，
每条边制作一根绳子，绳子的长度就是边的权值；将最短路问题的起点对应的小球缓缓提
起，然后测量每个小球到起点小球的距离，就得到了起点到每个节点的最短路。nodgd发现
这个算法非常厉害——它的时间复杂度为O(1) 。
nodgd打算在课上给大家演示这个最短路算法，于是用数据生成器生成了一组数据，即一个
个节点 条边的无向图。nodgd发现，分别选取不同的最短路起点，有些绳子总是处于松
弛状态，有些绳子总是处于绷紧状态，剩下的绳子时而绷紧时而松弛，这样可以将绳子分成
三类。现在nodgd想知道，每种绳子属于哪一类？
输入格式
输入文件phys.in。
第一行两个整数 nm，表示无向图的节点数和边数。
接下来 m行，每行三个整数 abc，表示第 i条无向边连接 ab节点，权值为 c。保证没
有重边和自环。
输出格式
输出文件phys.out。
输出 m行，第 i行输出一个整数x ， 分别表示第 x根绳子总是总是松弛、总是绷
紧、时而绷紧时而松弛。
输入输出样例1
见下发的文件phys-sample1.in和phys-sample1.ans。
董神还是这么毒瘤 专门卡dij
看到\(n<=500\) 邻接存图 floyd呗 dij主要处理点多边少的情况
然后讨论每个点的情况 如果这个点处于一条边的端点 就可以讨论是否为最短距离
如果不是端点讨论边是否存在于最短路中 否则就不行
code：
//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 510
#define ll long long
#define inf 100000000000
bool is[250010],son[250010];
struct node {
int st,en;
ll l;
} ed[250010];
ll mapp[maxnn][maxnn];
int n,m;
ll x,y,z;
#define GC getchar()
inline int R() {
char t;
int x=0;
int f=1;
t=GC;
while(!isdigit(t)) {
if(t=='-') f=-1;
t=GC;
}
while(isdigit(t)) {
x=x*10+t-48;
t=GC;
}
return x*f;
}
int main() {
freopen("phys.in","r",stdin);
freopen("phys.out","w",stdout);
n=R();
m=R();
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(i==j) continue;
mapp[i][j]=inf;
}
}
for(int i=1; i<=m; i++) {
ed[i].st=R();
ed[i].en=R();
ed[i].l=R();
mapp[ed[i].st][ed[i].en]=mapp[ed[i].en][ed[i].st]=ed[i].l;
}
for(int k=1; k<=n; k++) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(mapp[i][j]>mapp[i][k]+mapp[k][j]) {
mapp[i][j]=mapp[i][k]+mapp[k][j];
}
}
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(ed[j].st==i) {
if(mapp[i][ed[j].en]==ed[j].l) {
is[j]=true;
continue;
}
continue;
}
if(ed[j].en==i) {
if(mapp[i][ed[j].st]==ed[j].l) {
is[j]=true;
continue;
}
continue;
}
if(mapp[i][ed[j].en]+ed[j].l==mapp[i][ed[j].st]) {
is[j]=true;
continue;
}
if(mapp[i][ed[j].st]+ed[j].l==mapp[i][ed[j].en]) {
is[j]=true;
continue;
}
son[j]=true;
}
}
for(int i=1; i<=m; i++) {
if((!is[i])&&son[i]) {
printf("1\n");
continue;
}
if(is[i]&&(!son[i])) {
printf("2\n");
continue;
}
if(is[i]&&(son[i])) {
printf("3\n");
continue;
}
}
}
B. 数学
（math.c/.cpp/.in/.out）
问题描述
扎实的数学功底是每个信息学竞赛选手必须具备的基本素养之一。
比如计算一个正整数 n有多少个正约数，通常的做法是先将 n分解质因数，将每个质因数的
幂次加一之后乘起来。
现在nodgd给你一个正整数序列 i,k，并进行很多次询问：序列前 i个数的乘积有
多少个正约数的所有质因数都不超过k 呢？特别的，1 没有质因数，所以无论怎么询问 总是
符合条件。
输入格式
输入文件math.in。
第一行两个整数 ，表示序列的长度和询问的次数。
第二行 个正整数 。
从第三行起的连续 行，每行两个正整数 ，表示一次询问。
输出格式
解：
树状数组维护前缀乘积 .... 话说lhd说过可以做区间gcd 我怎么就没想到 ... (sqrt(n))分解我真是厉害
一定要把自己的思路记下来 不然就会忘记自己以前想过的思路...
C.生物
（biol.c/.cpp/.in/.out）
问题描述
一个生态系统中有 种生物，它们形成了食物链和食物网。这 种生物中，一些是生产者，
不需要吃其他生物就能生存；剩下的一些是消费者，必须吃其他的一些生物才能生存。
一种生物的重要性定义为，如果这种生物灭绝，将会导致包括自身在内的多少种生物灭绝。
一种消费者生物，如果它的所有食物都灭绝，则这种生物也会灭绝。
一种生物的后效性定义为，如果这种生物灭绝，引发的灭绝事件将会持续多少个单位时间。
一种消费者生物，如果它的最后一种食物在上个单位时间灭绝，则它会在当前这个单位时间
灭绝。
现在的任务是计算每种生物的重要性和后效性。
输入格式
输入文件biol.in。
第一行两个整数 n,m，表示生物的种类数和食物关系数量。
接下来m 行，每行两个整数 a,b，表示第 a种生物可以以第b 种生物为食。保证不会出现
任何一种生物直接或间接吃自己的情况，同一条关系保证不会重复出现。不吃其他任何生物
的生物都是生产者。
输出格式
输出文件biol.out。
输出n 行，第i 行两个整数 c d，分别是表示第 种生物的重要性和后效性。
输入输出样例1
见下发的文件biol-sample1.in和biol-sample1.ans。