真的跪了
時間配置設定極欠妥當。心态不穩定，處于“暴力寫不好”“正解沒時間寫”的絕妙境地。
會建圖，反而是算法的具體實施很不熟練。細節處欠缺太多。
多自主思考。
T1 促銷
【問題描述】
小x在jzyz開了一家冷飲店，因為剛開張，他決定做一次促銷活動。而活動的獲獎者可以免費得到一杯聖代。
為了和同學的生活貼近，小x費勁腦汁想到了一個促銷方案：
1） 當場搖出一個正整數M，再搖出兩個正整數X和Y
2） 每個人可以在1..M這M個自然數中挑出N個不同的數。
3） 如果某人可以在現場把這N個數的倒數的累加和恰好等于X/Y，那麼這個人可以得到一杯聖代。
4） 每種方案隻限第一名想到答案的領取一杯聖代。
現在小x苦惱的是，對于給定的N，M,X,Y，他能否盡快得知他最多要準備多少杯聖代。
【輸入】
四個整數：N，M,X,Y。
【輸出】
一個整數，表示最多要準備多少杯聖代。
【輸入樣例】
2 4 3 4
【輸出樣例】
1
【資料範圍】
對于30%的資料，1<=N<=M<=15
對于60%的資料，1<=N<=M<=20
對于100%的資料，1<=N<=M<=25，X<=25,Y<=25
看到這題的第一瞬間腦内就是，“要被卡精度了”，果然被卡了。
想過用gcd，又覺得可行性低，沒有寫，後來同學有人寫出來了，哎。
暴力搜尋。
可行性剪枝：沒取到n個數累加和已超過x/y。
最優化剪枝：由于取數是有順序的，故比目前數x小的數都已經取過，即下次取數區間為[x+1,m]。
挨個取數，沒必要另開數組判斷取沒取過了。
精度啊精度
#include<bits/stdc++.h>
using namespace std;
int x,y,m,n;
double summ=;
int ans=;
double a=;
void dfs(int step,double summ,int x)
{
if(step==n) {
if(abs(summ-a)<=) ans++;//誤差在一定範圍内可接受，即為一解。
return;
}
if(summ-a>) return;//可行性剪枝。
for(int i=x+;i<=m;++i)//最優化剪枝。
dfs(step+,summ+/i,i);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
a=(*x)/(*y);
dfs(,summ,);
cout<<ans;
return ;
}
涉及double 這個妖豔賤貨一定 要注意注意非常注意。
T2 特殊字典序
【問題描述】
Bessie發現了一些很奇怪的殘缺的字典，這些字典的單詞是按照某種特殊的字典序排序的，現在Bessie給你多組按照特殊字典序給出的單詞組，問你能不能給出這些字母的先後順序。
比如按順序給出4個單詞：ula uka klua kula al。這裡隻有四個小寫字母，分别是：u l k a。 根據首字母我們知道 u< k< a，根據klua 和 kula 知道 l< u，于是我們知道字典序是luka.
比如給定另4個單詞：jaja baba baja beba。我們發現既有j< b，也有b< j，存在沖突的先後關系，對于此種情況，我們輸出 “!”。
再比如給定3個單詞：marko darko zarko ，無法确定一些的關系，對于這種情況，我們輸出 “?”
【輸入】
多組資料
每組資料第一行一個整數N (1≤ N ≤ 100)
接下來N行，每行一個單詞，保證單詞由小寫字母組成，且長度不超過10.
【輸出】
多行，每行按要求輸出相應的結果。
看到輸入方式就開始煩躁了。第一眼拓撲第二眼還是拓撲，遂義無反顧走了下去。建圖建得感動自己，臨到這拓撲怎麼判環怎麼輸出順序忘得一幹二淨。等想起來整個人已經煩躁到炸裂了。
沒想到可以用floyed，其實該想到的，因為26*26*26，幾乎是為floyed量身打造。果然floyed還是最強的。
然而還沒有調出來
T3 星級隧道
【問題描述】
小x當上了銀河系的國王，一共統治了N個星球，現在帝國要建立N-1條星際隧道，将所有的星球全部連接配接起來。
每個星球都有自己的立體坐标。xA,yA,zA表示星球A的三維坐标，xB,yB,zB分别表示星球B的三維坐标.在A和B兩個星球建立通道的代價是：
Cost[A,B] = min{ |xA-xB|, |yA-yB|, |zA-zB| }
現在小x想知道，最少要花費多少代價，能将這N個星球用星級隧道連接配接起來。
【輸入】
第一行包含1個整數N（1<=N<=100000）,表示星球的數目。
接下來N行包含3個整數，所有整數介于-10^9到10^9之間.每一行包含x，y，z，表示該星球的三個坐标。
注意：沒有兩個在空間中的同一點。
【輸出】
隻有1行，表示最小的代價。
【樣例輸入】
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
【樣例輸出】
4
直白的最小生成樹。顯然的稠密圖。最開始的想法，是每兩個點之間連邊搞，會ＭＬＥ＋TLE雙享。考完才發現如果用prim是不用存邊的。我大概是失去了脖子以上的部分。
因為prim是基于點的算法，故點與點之間的聯系可以臨時計算，完全ok。
copy一下cxgg的代碼：
就是活生生的裸的prim，怪我太淺薄。
但是prim O(n^2)，這裡會逾時。後來想到正解Kruskal，居然死于快讀。可惡啊，然而。
Kruskal基于邊實作，既然躲不開存邊那就存吧。兩點間路徑為xyz坐标差的最小值，故可将星球分别以xyz為關鍵字排三次序，再保留三次有序數列相鄰兩項之間的內插補點，即這兩點之間的邊權。在所得的3*(n-1)條邊中可以保證滿足kruskal對n-1條最短邊的需求。為什麼？顯然法，可以意會。
#include<bits/stdc++.h>
using namespace std;
int n;
struct edge
{
int x,y,z,i;
}e[];
struct edge2
{
int x,y,v;
}a[];
long long summ=;
int fa[];
int tott=;
inline void read(int &x)
{
int f=;x=;char s=getchar();
for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-;
for(;s>='0'&&s<='9';s=getchar()) x=(x<<)+(x<<)+s-;
x*=f;
}//可恨的快讀啊
inline int find(int x){return(fa[x]==x?x:fa[x]=find(fa[x]));}
inline bool cmp1(edge a,edge b){return(a.x<b.x);}
inline bool cmp2(edge a,edge b){return(a.y<b.y);}
inline bool cmp3(edge a,edge b){return(a.z<b.z);}//xyz排序
inline bool mycmp(edge2 a,edge2 b){return(a.v<b.v);}
void sett()
{
read(n);
for(int i=;i<=n;++i)
{
read(e[i].x);read(e[i].y);read(e[i].z);e[i].i=i;
}
sort(e+,e+n+,cmp1);
for(int i=;i<=n;++i)
{
a[++tott].x=e[i-].i;a[tott].y=e[i].i;a[tott].v=abs(e[i].x-e[i-].x);
}
sort(e+,e+n+,cmp2);
for(int i=;i<=n;++i)
{
a[++tott].x=e[i-].i;a[tott].y=e[i].i;a[tott].v=abs(e[i].y-e[i-].y);
}
sort(e+,e+n+,cmp3);
for(int i=;i<=n;++i)
{
a[++tott].x=e[i-].i;a[tott].y=e[i].i;a[tott].v=abs(e[i].z-e[i-].z);
}//三次排序。
sort(a+,a+tott+,mycmp);//把得到的邊升序排一遍。
}
void kru()
{
for(int i=;i<=n;++i) fa[i]=i;
int flag=;
for(int i=;i<=tott;++i)
{
int x=find(a[i].x);
int y=find(a[i].y);
if(x!=y)
{
fa[x]=y;
summ+=a[i].v;
flag++;
if(flag==n-) return;
}
}
}//正常Kruskal。
int main()
{
sett();
kru();
printf("%d",summ);
return ;
}
快讀裡判符号的f定義為bool了，跪了九個點，不能再說了，要落淚了。感謝ycy。