怎么说呢。。。。。 除了第一题一点难度都没有！！！！ORZ。。（我会把题目拿出来，看题解的话跳过题目就好）
T1无脑二分，T2树上二分+LCA，T3概率+矩阵快速幂优化递推 想要数据的小伙伴可以找我。 T1（猴子摘桃 monkey）：
【问题描述】
动物园内最受欢迎就是猴子了，因为它们除了能爬能跳外还会很多技能。其中A类猴子特别擅长爬树摘桃，而B类猴子擅长把桃子掰成两半。A类猴子有N只，编号为1到N，B类猴子有M只，编号为1到M。A类猴子中的第i只摘到第一个桃子需要花费Ai秒，此后每Bi秒就能摘到桃子；B类猴子中的第i只掰开第一个桃子需要花费Ci秒，此后每Di秒就能掰开一个桃子。
不幸的是，B类猴子非常具有侵略性，两种猴子不能同时待在场地内，因此，园长必须在A类猴子摘完所有桃子后立刻把它们带走，然后立刻让B类猴子进园；同样当B类猴子把所有桃子全部掰开后也不能待在场地内太久，因为它们之间也会发生冲突，所有园长将在B类猴子掰开所有桃子后立刻送走它们。
园长带走猴子和猴子进园的速度非常快，时间忽略不计。
Alice非常喜欢看B类猴子掰桃子，告诉你表演的总时间，但不知道一共有多少个桃子，请你帮Alice计算B类猴子进入动物园的时刻。
【输入格式】
从文件monkey.in中读入数据。
输入第一行包含一个整数T（秒），表示猴子表演的总时间。接下来一行包含一个整数N，表示A类猴子的数量。接下来N行，每行包含两个整数Ai和Bi，描述A类每只猴子摘桃的速度。接下来一行包含一个整数M，表示B类猴子的数量。接下来M行，每行包含两个整数Ci和Di，描述B类每只猴子掰桃的速度。
【输出格式】
输出到文件monkey.out中。
输出两类猴子进园的时刻相差多少秒。
【输入样例1】
12
1
3 1
1
5 1
【输出样例1】
5
【样例1说明】
　　样例1中，树上有3个桃子：
(1) A类猴子在3秒时摘下第一个桃子，在4秒时摘下第二个桃子，在5秒时摘下第三个桃子；
(2) 在第5秒，园长把A类猴子带走，此时B类猴子进园；
(3) B类猴子在10秒时掰开第一个桃子，在11秒时掰开第二个桃子，在第12秒时掰开第三个桃子；
(4) 在12秒时园长进园带走B类猴子。
【输入样例2】
20
2
3 2
1 3
3
3 1
4 1
5 1
【输出样例2】
13
【数据规模与约定】
对于 60%的数据， 1<=T<=1000，1<=Ak,Bk,Ck,Dk<=1000
对于100%的数据， 1<=T<=1000000000，1<=N,M<=100，1<=Ak,Bk,Ck,Dk<=1000000000 —————————————————————————————————————————————————— 显然就是二分，但是当时不知道怎么脑子一卡就。。。就。。。打了个二分套二分。。。
。
。
然后我就WA了两个点QAQAQAQAQ 时间这么大显然可以直接二分最后的时间（就是A猴子吃桃子用的时间mid），二分出一个时间之后算A猴子吃的桃子数量n1和B猴子吃的桃子数量n2，如果发现n1>n2说明A用的时间多了，应该往小的猜。否则往大的猜，同时记录为一个答案。
为什么是“>”而不是“>=”呢？我们二分A猴子用的时间，那么我们算出来的n1肯定是A猴子充分利用了这mid的时间恰好可以摘下这么多个桃子。而B猴子在剩下的时间里面不一定会恰好掰n2个桃子，因为一部分B猴子可能出现无桃子可掰的情况，但是它们必须要用最后的一秒来掰完桃子。所以说n1<=n2的时候有可能是A猴子用的时间少了，也有可能是时间恰好，这时候已经可能是一个解了。 AC代码： #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=105; int N,M,T; struct data{ int x,y; }A[maxn],B[maxn]; void _scanf(int &x) { x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } void data_in() { _scanf(T); _scanf(N); for(int i=1;i<=N;i++) { _scanf(A[i].x);_scanf(A[i].y); } _scanf(M); for(int i=1;i<=M;i++) { _scanf(B[i].x);_scanf(B[i].y); } } bool check(int mid) { int n1=0,n2=0; for(int i=1;i<=N;i++) if(A[i].x<=mid) n1+=1+(mid-A[i].x)/A[i].y; for(int i=1;i<=M;i++) if(B[i].x<=T-mid) n2+=1+(T-mid-B[i].x)/B[i].y; return n1>n2; } void work() { int L=1,R=T+1,mid,ans=-1; while(L>1; if(check(mid)) R=mid; else L=mid+1,ans=mid; } printf("%d ",ans); } int main() { freopen("monkey.in","r",stdin); freopen("monkey.out","w",stdout); data_in(); work(); return 0; } T2（避难向导 shelter）：
【问题描述】
“特大新闻，特大新闻！全国爆发了一种极其可怕的病毒，已经开始在各个城市中传播开来！全国陷入了巨大的危机！大量居民陷入恐慌，想要逃到其它城市以避难！经调查显示，该病毒来自于C市的A学校的一次非法的……”
　　“哎。 ”你关上电视，叹了口气。作为 A 学校的校长，你一天前为了保命，独自逃离了A学校，抛弃了全校师生，包括那个曾经帮你计算并拆除道路的工程师。你良心受到了巨大的谴责，因此决定做出一些补救，回答一些逃难的人提出的询问。
　　已知该国一共有 n 个城市，并且 1 号城市是首都。n-1条双向的公路连接这些城市，通过这些公路，任意两个城市之间存在且仅存在一条路径。每条公路有一个长度。如果一个城市只与一条公路相连，则称它为边境城市。该国政府有一个奇怪的规定：每个城市有一个封闭系数 di，定义di 为离这个城市最远的边境城市到这个城市的距离。市民们认为，一个城市的安全系数 Si 和它的封闭系数有很重要的联系。a，b，c是该国的幸运数字，所以大家公认一个城市的安全系数Si = (di + a) * b mod c。
　　市民们一共会提出m次询问。每个询问包含三个信息，xi，yi和 qi。xi 是询问者所在的城市编号。你要为这个询问者在 xi 到 yi 的必经之路上找出一个离 xi最近的避难城市，并且要求这个避难城市的安全系数大于等于 qi（Si>=qi）。如果存在这样的城市（包含xi和yi），则输出城市编号，否则输出一行包括一个数-1。
【输入格式】
从文件shelter.in中读入数据。
输入的第1行包含5个数：依次是n, m, a, b, c。接下来n-1行描述公路的信息，每行3个数，前两个数代表这条公路连接的两个城市的编号，第三个数表示这条公路的长度（在32位整数范围以内）。再接下来m行，每行描述一个询问，包含三个数xi, yi和qi。
【输出格式】
输出到文件shelter.out中。
对于每个询问，输出一行包含一个整数，存在符合要求的城市则输出城市编号，不存在则输出-1。
【样例输入】
7 6 5 6 20
1 2 4
2 4 2
2 5 3
1 3 5
3 6 6
6 7 7
7 5 15
3 4 5
5 4 2
4 5 2
6 6 10
3 5 19
【样例输出】
6
3
2
4
6
-1 【数据规模与约定】
。。。我就省略了，N<=100000,M<=300000 —————————————————————————————————————————————————— 。。。没什么难度的样子。
考虑一下封闭系数的问题，显然跟直径有关，离树上一个点最远的叶子结点显然就是由叶子结点为端点构成的最长链的端点其中之一（不然找到的就不是最长链），然后安全系数的问题就解决了。
考虑询问，询问里面要求找离起点最近的那个点使得Si>=p，那么就用二分，把询问的路径拆成向上和向下的，看向上路径的里面有没有一个点的S>=p，有的话就在向上里面来猜，没有的话就在向下里面猜。当然移动的时候肯定要用倍增，虽然看起来是一个logN*logN的复杂度，但是可以发现每一次都是“验证当前->变成一半的模式”，就类似于1+1/2+1/4……最后无限逼近于2的感觉，由于有一个验证当前有没有解的过程所以大不了乘个3（一半只会少爬一次），回答一次询问的时间复杂度变成O(6logN)，不会超时。
分析一堆，总时间复杂度为O(NlogN+(6)MlogN)。（PS：S写成了D不要在意AuA） AC代码： #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=100005; typedef long long LL; int N,M,a,b,c; struct edge{ int to,next,w; }E[maxn<<1]; int first[maxn],np,dep[maxn],fa[maxn][18]; int o1,o2,D[maxn],du[maxn],maxd[maxn][18]; LL d1[maxn],d2[maxn],dist[maxn]; void _scanf(int &x) { x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } void add_edge(int u,int v,int w) { E[++np]=(edge){v,first[u],w}; first[u]=np; } void data_in() { _scanf(N);_scanf(M);_scanf(a);_scanf(b);_scanf(c); int x,y,z; for(int i=1;ivoid getd(int i,int f,LL l,int &o) { dist[i]=l; if(du[i]==1&&dist[i]>dist[o]) o=i; for(int p=first[i];p;p=E[p].next) { int j=E[p].to; if(j==f) continue; getd(j,i,l+E[p].w,o); } } void DFS(int i,int f,LL l,LL *d) { d[i]=l; for(int p=first[i];p;p=E[p].next) { int j=E[p].to; if(j==f) continue; DFS(j,i,l+E[p].w,d); } } void _DFS(int i,int f,int d) { dep[i]=d; fa[i][0]=f; maxd[i][0]=max(D[i],D[f]); for(int j=1;(1<1]][j-1]; maxd[i][j]=max(maxd[i][j-1],maxd[fa[i][j-1]][j-1]); } for(int p=first[i];p;p=E[p].next) { int j=E[p].to; if(j==f) continue; _DFS(j,i,d+1); } } int LCA(int x,int y) { if(dep[x]int len=dep[x]-dep[y]; for(int j=0;(1<if((1<if(x==y) return x; for(int j=17;j>=0;j--) if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; return fa[x][0]; } int solve1(int x,int y,int p) { if(dep[x]-dep[y]<=1) { if(D[x]>=p) return x; if(D[y]>=p) return y; return -1; } int len=dep[x]-dep[y],maxv=0; int z=x; for(int j=0;(1<if((1<if(maxvreturn -1; len/=2; z=x; for(int j=0;(1<if((1<int re=solve1(x,z,p); if(re!=-1) return re; return solve1(fa[z][0],y,p); } int solve2(int x,int y,int p) { if(dep[x]-dep[y]<=1) { if(D[y]>=p) return y; if(D[x]>=p) return x; return -1; } int len=dep[x]-dep[y],maxv=0; int z=x; for(int j=0;(1<if((1<if(maxvreturn -1; len/=2; z=x; for(int j=0;(1<if((1<int re=solve2(fa[z][0],y,p); if(re!=-1) return re; return solve2(x,z,p); } void work() { for(int i=1;i<=N;i++) if(du[i]==1) { o1=i; break; } getd(o1,0,0,o1); getd(o1,0,0,o2=o1); DFS(o1,0,0,d1); DFS(o2,0,0,d2); for(int i=1;i<=N;i++) D[i]=(max(d1[i],d2[i])+a)*b%c; _DFS(1,0,1); int x,y,ans,gf,p; for(int i=1;i<=M;i++) { _scanf(x);_scanf(y);_scanf(p); gf=LCA(x,y); ans=solve1(x,gf,p); if(ans==-1) ans=solve2(y,gf,p); printf("%d ",ans); } } int main() { freopen("shelter.in","r",stdin); freopen("shelter.out","w",stdout); data_in(); work(); return 0; } T3（银河大盗robbers）：
【问题描述】
银河大盗驾驶着“太空飞船”在银河系的各星球之间逃窜，宇宙警察们追捕行动开始了。作为计算机专家，需要为警察局计算某时刻银河大盗在各星球出现的概率。
银河系有n个星球，用1~n的整数为每个星球标号，星球之间的交通工具是“太空飞船”。任何两个星球之间都可以由太空船直达，从星球i到星球j直达需要消耗的能量为tij（加仑），当然从j到i也需要消耗这么多能量。银河大盗总是选择最节约能量的路径从一个星球逃窜到另一个星球。具体来说，若 t 时刻盗匪在星球 i ，则在 t+1 时刻，他逃到星球 j 的概率：P=(dist(i,j))/(sum(i))，其中，dist(i,j)表示星球i到星球j的最小能量；sum(i)=∑_(k=1)^n▒dist(i,k) 。
现在，给定0 时刻盗匪在每个星球出现的概率。请求T时刻盗匪出现在每个星球的概率。
【输入格式】
从文件robbers.in中读入数据。
输入的第1行两个整数 n 和 T，他们的意义如题目描述。第2行 n 个实数，表示 0 时刻盗匪在个星球出现的概率（保证概率加起来为 1），第i个实数表示在第i个星球出现的概率。接下来 n 行每行 n 个整数，第 i 行第 j 个数表示星球 i 到星球 j 需要消耗的能量。　　保证第 i 行第 i 个数为 0 且第 i 行第 j 个数等于第 j 行第 i 个数（即给出的矩阵是关于副对角线对称的）。
【输出格式】
输出到文件robbers.out中。
输出共 n 行，第 i 行表示 T 时盗匪出现在星球 i 的概率，保留六位小数。
【输入样例】
3 2
0 1 0
0 1 4
1 0 2
4 2 0
【输出样例】
0.400000
0.350000
0.250000
【数据规模与约定】
对于 50% 的数据，T<=20。
对于 100% 的数据，n<=200，T<=109。保证对于每个星球dist 的和值在 int 范围。 ———————————————————————————————————————————————————— 好好解题：
50分直接dp模拟，100分用矩阵快速幂优化。只要会打快速幂就没什么问题（表示看出来了是矩阵快速幂但是之前没有写过就现场打了一次打对了，滑稽）。
注意几个问题：矩阵定义在结构体里面会使用栈空间，所以务必记得扩栈还有写成全局变量。于是快速幂千万不要打递归写法嗯。 哲学思想：
化学告诉我们万物都趋向于稳定的状态
所以
在无限久远的未来
强盗在每个星球的概率会趋近于一个定值
所以说
不会快速幂的小伙伴
在T大于2000的时候直接改成2000来递推就可以过啦！！！！！！厉害吧？！？！（当然不是所有题目都有效的，只是这个在时间可以承受的范围之内就可以在精度要求范围之内不发生变化了，不过有些题目的正解还真的是这个） 好好解题： #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=205; int N,T; int dist[maxn][maxn],sum[maxn],cnt; double f[maxn],p[maxn][maxn]; struct matrix{ int x,y; double A[maxn][maxn]; matrix(){ x=y=0; memset(A,0,sizeof(A)); } friend matrix operator * (matrix a,matrix b) { matrix c; c.x=a.x,c.y=b.y; for(int i=1;i<=c.x;i++) for(int j=1;j<=c.y;j++) for(int k=1;k<=a.y;k++) c.A[i][j]+=a.A[i][k]*b.A[k][j]; return c; } }ans,pp,re,tmp; void data_in() { scanf("%d%d",&N,&T); for(int i=1;i<=N;i++) scanf("%lf",&f[i]); for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) scanf("%d",&dist[i][j]); } void ready() { for(int k=1;k<=N;k++) for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) sum[i]+=dist[i][j]; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) p[i][j]=1.0*dist[i][j]/sum[i]; } void work() { if(T!=0) { pp.x=pp.y=N; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) pp.A[i][j]=p[j][i]; tmp=re=pp; for(int j=1;(1<if((1<1; for(int i=1;i<=N;i++) ans.A[i][1]=f[i]; ans=re*ans; for(int i=1;i<=N;i++) printf("%.6lf ",ans.A[i][1]); } else { for(int i=1;i<=N;i++) printf("%.6lf ",f[i]); } } int main() { freopen("robbers.in","r",stdin); freopen("robbers.out","w",stdout); data_in(); ready(); work(); return 0; }