划水系列（八）小弟我在2013年编程之美全国挑战赛的资格赛中殴打水题

（一）、传话游戏

时间限制: 1000ms 内存限制: 256MB

描述

Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。

由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。

输入

输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。

输出

对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。

数据范围

1 ≤ T ≤ 100

小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10

大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100

样例输入

2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired

样例输出

Case #1: the sheep is thinking
Case #2: a tiny bear is bear

这道题不废话，直接上。

#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <map> using namespace std; //字符串分割函数 std::vector<std::string> split(std::string str,std::string pattern) { std::string::size_type pos; std::vector<std::string> result; str+=pattern;//扩展字符串以方便操作 int size=str.size(); for(int i=0; i<size; i++) { pos=str.find(pattern,i); if(pos<size) { std::string s=str.substr(i,pos-i); result.push_back(s); i=pos+pattern.size()-1; } } return result; } void Update(vector<string> & str,map<string,string> & w_map) { map<string,string>::iterator it; for(int i=0;i<str.size();i++) { it = w_map.find(str[i]); if(it != w_map.end()) { str[i]=it->second; } } } int main() { int T; while(scanf("%d",&T) == 1) { for(int x=1;x<=T;x++) { int N,M; map<string,string> words_map; string s1,s2; string srcWords,tgtWords; scanf("%d%d",&N,&M); for(int i=1;i<=M;i++) { cin>>s1>>s2; words_map.insert(make_pair(s1,s2)); } cin.get();//吃掉上一行换行符 getline(cin,srcWords,'\n'); vector<string> singleWord = split(srcWords," "); for(int i=1;i<=N-1;i++) { Update(singleWord,words_map); } printf("Case #%d: ",x); for(int i=0;i<singleWord.size()-1;i++) cout<<singleWord[i]<<" "; cout<<singleWord[singleWord.size()-1]<<endl; } } return 0; }

（二）、长方形

时间限制: 1000ms 内存限制: 256MB

描述

在 N × M 的网格上，放 K 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。

输入

输入文件包含多组测试数据。

第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。

每组数据为三个用空格隔开的整数 N，M，K。

输出

对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。

数据范围

1 ≤ T ≤ 100

0 ≤ K ≤ N * M

小数据：0 < N, M ≤ 30

大数据：0 < N, M ≤ 30000

样例输入

样例输出

Case #1: 5
Case #2: 18
Case #3: 1398

这道题真的是很恶心！WA了无数次，因为这道题，我学会了一种查错忍术：大量生成随机数然后和AC的同学校对答案之术！

#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <map> #include <algorithm> #include <math.h> #include <fstream> using namespace std; typedef long long LL; int main() { /* 生成2.txt 后，和AC的代码生成的2.txt CMD下FC命令一下： fc 2.txt my2.txt 就能找到差异！ ofstream f1("1.txt"); if(!f1) return -100; f1<<10000<<endl; LL cnt = 0; for(int y=1;;y++) { int a,b,c; a = rand()%10; b = rand()%10; c = rand()%100; if(c <= a*b) { f1<<a<<" "<<b<<" "<<c<<endl; cnt++; if(cnt == 10000) break; } } f1.close(); freopen("1.txt", "r", stdin); freopen("2.txt", "w", stdout); */ int T; while(scanf("%d",&T) == 1) { for(int x=1;x<=T;x++) { LL N,M,K; scanf("%lld%lld%lld",&N,&M,&K); if(N>M) //让M > N { N = M+N; M = N-M; N = N-M; } int n = sqrt(K)>N?N:sqrt(K); int m = M; while(n * m > K) m--; LL ans = 0; LL res = 0; while(n >= 2 && m <= M ) { LL k = K; res += (n*m*(n-1)*(m-1)) >>2 ; k -= m*n; if(m < M) res += (m*k*(k-1)) >>1; else res += (n*k*(k-1)) >>1; ans = res > ans ? res : ans; res = 0; n --; m = K/n; } printf("Case #%d: %lld\n",x,ans); //printf("Case #%d: %I64d %I64d %I64d %I64d\n",x,ans,N,M,K); } } return 0; }

（三）、树上的三角形

时间限制: 2000ms 内存限制: 256MB

描述

有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？

输入

输入数据的第一行包含一个整数 T，表示数据组数。

接下来有 T 组数据，每组数据中：

第一行包含一个整数 N，表示树上节点的个数（从 1 到 N 标号）。

接下来的 N-1 行包含三个整数 a, b, len，表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。

接下来一行包含一个整数 M，表示询问数。

接下来M行每行两个整数 S, T，表示毛毛虫从 S 爬行到了 T，询问这段路程中的树枝/树干是否能拼成三角形。

输出

对于每组数据，先输出一行"Case #X:",其中X为数据组数编号，从 1 开始。

接下来对于每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。

数据范围

1 ≤ T ≤ 5

小数据：1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000

大数据：1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000

样例输入

样例输出

Case #1:
No
Yes
Case #2:
No
Yes

这WA和RE了好多次，主要是边界没处理好，导致溢出。虽然我知道肯定是溢出，但是在检查溢出的时候还是费了好大功夫。。不应该啊~~

#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <map> #include <algorithm> using namespace std; class CEdge { public: int dest; int weight; CEdge *Link; CEdge(int d,int w):dest(d),weight(w),Link(NULL){} CEdge():dest(-1),weight(-1),Link(NULL){} ~CEdge(){if(Link) delete Link;} void printEdge() { CEdge * e = Link; while(e) { cout<<e->dest<<" ("<<e->weight<<") "; e= e->Link; } cout<<endl; } void insertEdge(int d,int w) { CEdge *e = new CEdge(); e->dest = d; e->weight = w; e->Link = Link; Link = e; } }; class CGraph { public: int V; int E; vector<CEdge> edges; CGraph(int v,int e):V(v),E(e){init(V);} CGraph(int v):V(v),E(0){init(V);} ~CGraph() { //vector<CEdge>().swap(edges); } void insertEdge(int u,int v,int w) { if(u <= V && v <= V) edges[u].insertEdge(v,w); } void printGraph() { for(int i=1;i<=V;i++) { cout<<i<<": "; edges[i].printEdge(); } } int getWeight(int u,int v) { CEdge *e = edges[u].Link; while(e) { if(e->dest == v) return e->weight; e = e->Link; } return -1; } private: void init(int N) { for(int i=0;i<=N;i++) { edges.push_back(CEdge()); } } }; int dis[100010]; bool visited[100010]; int cnt=0; struct Node { int p; int w; }p[100010]; void DFS_Visited(CGraph &g,int f,int t,bool* visited,Node* pp) { if(f>0 && f<=g.V && t<=g.V && t>0) { CEdge *e = g.edges[f].Link; visited[f] = true; while(e) { int v = e->dest; if(!visited[v]) { p[v].p=f; p[v].w=e->weight; if(v == t) return; DFS_Visited(g,v,t,visited,p); } e = e->Link; } } } int main() { int T; while(scanf("%d",&T) == 1) { for(int x=1;x<=T;x++) { int N; int u,v,w; scanf("%d",&N); CGraph g(N); for(int i=1;i<=N-1;i++) { scanf("%d %d %d",&u,&v,&w); g.insertEdge(u,v,w); //无向图 g.insertEdge(v,u,w); } //g.printGraph(); printf("Case #%d:\n",x); int ask; scanf("%d",&ask); while(ask--) { int f,t; scanf("%d%d",&f,&t); memset(visited,false,sizeof(bool)*(N+1)); memset(p,0,sizeof(Node)*(N+1)); DFS_Visited(g,f,t,visited,p); int v = t; cnt = 0; while(p[v].p != f && p[v].p != 0) { dis[cnt] = p[v].w; cnt++; v = p[v].p; } dis[cnt]=p[v].w; sort(dis,dis+cnt+1); bool ans = false; for(int i=0;i<cnt-1;i++) { int a = dis[i]; int b = dis[i+1]; int c = dis[i+2]; if(a+b > c) { ans = true; break; } } if(ans) printf("Yes\n"); else printf("No\n"); } } } return 0; }