输入两个正整数 n, m，输出 n!/m!，其中阶乘定义为 n!= 1*2*3*...*n (n>=1)。 比如，若 n=6, m=3，则 n!/m!=6!/3!=720/6=120。是不是很简单？现在让我们把问题反过来：输入 k=n!/m!，找到这样的整数二元组(n,m)(n>m>=1)。 如果答案不唯一， n 应该尽量小。比如，若 k=120，输出应该是 n=5， m=1，而不是 n=6，m=3，因为 5!/1!=6!/3!=120，而 5<6。
输入包含不超过 100 组数据。每组数据包含一个整数 k (1<=k<=109)。
对于每组数据，输出两个正整数 n 和 m。无解输出"Impossible"，多解时应让 n 尽量小。
代码：
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> using namespace std; typedef long long LL; int main() { LL k; LL t = 1; while(scanf("%lld",&k)!=EOF){ LL n = (LL)sqrt(k)+10; LL l = 1,r =2,sum=1; LL ans1=k-1,ans2=k; bool flag = true; while(l<n){ while(r<n&&sum<k){ sum*=r; r++; } if(sum==k){ ans1 = l; ans2 = r-1; flag = false; break; } sum=sum/l; l++; } if(!flag){ if(ans1!=1) ans1--; } printf("Case %lld: ",t++); if(k==1){ printf("Impossible\n"); }else{ printf("%lld %lld\n",ans2,ans1); } } return 0; }输入两个实数，判断第一个数大，第二个数大还是一样大。每个数的格式为： [整数部分].[小数部分]简单起见，整数部分和小数部分都保证非空，且整数部分不会有前导 0。 不过， 小数部分的最后可以有 0，因此 0.0 和 0.000 是一样大的
输入包含不超过 20 组数据。每组数据包含一行，有两个实数（格式如前所述）。每个实数都 包含不超过 100 个字符。
对于每组数据， 如果第一个数大， 输出"Bigger"。 如果第一个数小， 输出"Smaller"。 如果两个数相同， 输出"Same"。
给定两个简单多边形， 你的任务是判断二者是否有面积非空的公共部分。如下图， (a)中的两个 矩形只有一条公共线段，没有公共面积。 (a) (b) 在本题中，简单多边形是指不自交（也不会接触自身）、不含重复顶点并且相邻边不共线的多 边形。 注意： 本题并不复杂，但有很多看上去正确的算法实际上暗藏缺陷，请仔细考虑各种情况。
输入包含不超过 100 组数据。每组数据包含两行，每个多边形占一行。多边形的格式是：第一 个整数 n 表示顶点的个数 (3<=n<=100)， 接下来是 n 对整数(x,y) (-1000<=x,y<=1000)， 即多边 形的各个顶点， 按照逆时针顺序排列。
对于每组数据， 如果有非空的公共部分， 输出"Yes"， 否则输出"No"。
最后求面积并才过去了
代码： #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> using namespace std; const int maxn = 300; const double eps = 1e-8; const double pi = acos(-1.0); int dcmp(double x) { if(x > eps) return 1; return x < -eps ? -1 : 0; } struct Point { double x, y; }; double cross(Point a,Point b,Point c) ///叉积 { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } Point intersection(Point a,Point b,Point c,Point d) { Point p = a; double t =((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x)); p.x +=(b.x-a.x)*t; p.y +=(b.y-a.y)*t; return p; } double PolygonArea(Point p[], int n) { if(n < 3) return 0.0; double s = p[0].y * (p[n - 1].x - p[1].x); p[n] = p[0]; for(int i = 1; i < n; ++ i) s += p[i].y * (p[i - 1].x - p[i + 1].x); return fabs(s * 0.5); } double CPIA(Point a[], Point b[], int na, int nb)//ConvexPolygonIntersectArea { Point p[20], tmp[20]; int tn, sflag, eflag; a[na] = a[0], b[nb] = b[0]; memcpy(p,b,sizeof(Point)*(nb + 1)); for(int i = 0; i < na && nb > 2; i++) { sflag = dcmp(cross(a[i + 1], p[0],a[i])); for(int j = tn = 0; j < nb; j++, sflag = eflag) { if(sflag>=0) tmp[tn++] = p[j]; eflag = dcmp(cross(a[i + 1], p[j + 1],a[i])); if((sflag ^ eflag) == -2) tmp[tn++] = intersection(a[i], a[i + 1], p[j], p[j + 1]); ///求交点 } memcpy(p, tmp, sizeof(Point) * tn); nb = tn, p[nb] = p[0]; } if(nb < 3) return 0.0; return PolygonArea(p, nb); } double SPIA(Point a[], Point b[], int na, int nb)///SimplePolygonIntersectArea 调用此函数 { int i, j; Point t1[4], t2[4]; double res = 0, num1, num2; a[na] = t1[0] = a[0], b[nb] = t2[0] = b[0]; for(i = 2; i < na; i++) { t1[1] = a[i-1], t1[2] = a[i]; num1 = dcmp(cross(t1[1], t1[2],t1[0])); if(num1 < 0) swap(t1[1], t1[2]); for(j = 2; j < nb; j++) { t2[1] = b[j - 1], t2[2] = b[j]; num2 = dcmp(cross(t2[1], t2[2],t2[0])); if(num2 < 0) swap(t2[1], t2[2]); res += CPIA(t1, t2, 3, 3) * num1 * num2; } } return PolygonArea(a, na)+PolygonArea(b, nb) - res; } Point p1[maxn], p2[maxn]; int n1, n2; int main() { int t = 1; while(scanf("%d", &n1) != EOF) { for(int i = 0; i < n1; i++) scanf("%lf%lf", &p1[i].x, &p1[i].y); scanf("%d",&n2); for(int i = 0; i < n2; i++) scanf("%lf%lf", &p2[i].x, &p2[i].y); double Area = SPIA(p1, p2, n1, n2); double Area1 = PolygonArea(p1,n1)+PolygonArea(p2,n2); if(Area==Area1) printf("Case %d: No\n",t++); else printf("Case %d: Yes\n",t++); } return 0; }有道题目是这样的： 输入一个 n 行 m 列网格，找一个格子，使得它所在的行和列中所有格子的数之和最大。 如果答案不唯一，输出任意解即可。 比如， 在下面的例子中，最优解是(1,3)，即第一行和的三列的交点（行从上到下编号为 1~n，列从左到右编号为 1~m），所有 7 个数之和为 35。 快要比赛的时候， 有一个裁判想到了这样一个算法：首先找一行 r(1<=r<=n) 使得该行所有数之和最大， 然后找一列 c(1<=c<=m) 使得该列所有数之和最大，最后直接输出(r,c)。 如果有多个满足条件的 r，输出最小的r。对于 c 同样处理。
hint: 首先找一行 r(1<=r<=n) 使得该行所有数之和最大， 然后找一列(1<=c<=m) 使得该列所有数之和最大，最后直接输出(r,c)。 如果有多个满足条件的 r，输出最小的 r。对于 c 同样处理。
显然， 这个算法是错的， 但它竟然通过了大部分测试数据！你能找出那些让这个错误算法得到正确结果的“弱”数据，以便裁判们改进这些数据吗？
输入包含不超过 100 组数据。每组数据第一行为两个整数 n, m (1<=n<=500, 1<=m<=500)， 即行数和列数。 以下 n 行每行包含 m 个 1~100 的整数。输入的总大小不超过 2MB。
对于每组数据， 如果错误算法能得到正确结果， 输出"Weak"，否则输出"Strong"。
代码：
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int N = 550; int rsum[N],csum[N]; int graph[N][N]; int n,m; int main() { int t = 1; while(scanf("%d%d",&n,&m)!=EOF){ memset(rsum,0,sizeof(rsum)); memset(csum,0,sizeof(csum)); int r1,c1,r2,c2,MAX1=-1,MAX2=-1,MAX3=-1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&graph[i][j]); rsum[i] += graph[i][j]; csum[j] += graph[i][j]; } } for(int i=1;i<=n;i++){ if(MAX1<rsum[i]){ MAX1 = rsum[i]; r1 = i; } } for(int i=1;i<=m;i++){ if(MAX2<csum[i]){ MAX2 = csum[i]; c1 = i; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(MAX3<rsum[i]+csum[j]-graph[i][j]){ MAX3 = rsum[i]+csum[j]-graph[i][j]; r2 = i,c2 = j; } } } printf("Case %d: ",t++); if(r1==r2&&c1==c2){ printf("Weak\n"); }else{ printf("Strong\n"); } } return 0; }给一个 n 行 m 列的迷宫，每个格子要么是障碍物要么是空地。每个空地里都有一个权值。你的任务是从找一条(r1,c1)到(r2,c2)的路径，使得经过的空地的权值之和最小。每一步可以往上下左右四个方向之一移动一格，但不能斜着移动，也不能移动到迷宫外面或者进入障碍物格子。 如下图，灰色格子代表障碍物。路径 A->B->D->F->E 的权值为 10+3+6+14+8=41，它是从 A 到E 的最优路径。 注意，如果同一个格子被经过两次，则权值也要加两次。
为了让题目更有趣（顺便增加一下难度），你还需要回答另外一个问题：如果你每次必须转弯（左转、右转或者后退，只要不是沿着上次的方向继续走即可），最小权值是多少？ 比如， 在上图中， 如果你刚刚从 A 走到 B，那么下一步你可以走到 D 或者 A，但不能走到 G。 在上图中， A 到 E 的最优路径是 A->B->D->H->D->F->E，权和为10+3+6+2+6+14+8=49。注意， D 经过了两次。
输入包含不超过 10 组数据。每组数据第一行包含 6 个整数 n, m, r1, c1, r2, c2 (2<=n,m<=500,1<=r1,r2<=n, 1<=c1,c2<=m). 接下来的 n 行每行包含 m 个格子的描述。每个格子要么是一个1~100 的整数，要么是星号"*"（表示障碍物）。起点和终点保证不是障碍物。
对于每组数据， 输出两个整数。 第一个整数是“ 正常问题” 的答案， 第二个整数是“ 有趣问题” 的答案。 如果每个问题的答案是“无解”，对应的答案应输出-1。
思路：多记录一个方向
代码： #include <iostream> #include<cstdio>> #include<cstring> #include<queue> using namespace std; struct Node { int x,y,dir,w; //d表示方向 Node(){} Node(int x,int y,int dir,int w) { this->x = x; this->y = y; this->dir = dir; this->w = w; } bool operator < (const Node &rhs)const { return w > rhs.w; } }; int n,m,r1,r2,c1,c2; int map[505][505]; int dire[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int getnum(char *str) { int len = strlen(str); int ans = 0; for(int i = 0; i < len; i++) { ans = ans * 10 + str[i] - '0'; } return ans; } int bfs1(int x,int y) { priority_queue<Node> q; bool vis[505][505] = {0}; vis[x][y] = true; Node now; now.x = x, now.y = y; now.w = map[x][y]; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); if(now.x == r2 && now.y == c2) return now.w; for(int i = 0; i < 4; i++) { int newx = now.x + dire[i][0]; int newy = now.y + dire[i][1]; if(newx < 1 || newx > n || newy < 1 || newy > m) continue; if(vis[newx][newy] || map[newx][newy] == -1) continue; vis[newx][newy] = true; Node next; next.x = newx, next.y = newy, next.w = now.w + map[newx][newy]; q.push(next); } } return -1; } int bfs2(int x,int y) { priority_queue<Node> q; bool vis[505][505][4] = {0}; q.push(Node(x,y,-1,map[x][y])); while(!q.empty()) { Node now = q.top(); q.pop(); if(now.x == r2 && now.y == c2) return now.w; for(int i = 0; i < 4; i++) { int newx = now.x + dire[i][0]; int newy = now.y + dire[i][1]; if(newx < 1 || newx > n || newy < 1 || newy > m) continue; if(vis[newx][newy][i] || map[newx][newy] == -1) continue; if(i == now.dir) continue; vis[newx][newy][i] = true; q.push(Node(newx,newy,i,now.w + map[newx][newy])); } } return -1; } int main() { int cas = 1; char str[10]; while(scanf("%d%d%d%d%d%d",&n,&m,&r1,&c1,&r2,&c2)!=EOF) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%s",str); if(str[0] == '*') map[i][j] = -1; else map[i][j] = getnum(str); } } int ans1 = bfs1(r1,c1); int ans2 = bfs2(r1,c1); printf("Case %d: %d %d\n",cas++,ans1,ans2); } return 0; }输入一个四个数字组成的整数 n，你的任务是数一数有多少种方法，恰好修改一个数字，把它变成一个完全平方数（不能把首位修改成 0）。比如 n=7844，有两种方法： 3844=622和7744=882。
输入第一行为整数 T (1<=T<=1000)，即测试数据的组数，以后每行包含一个整数 n(1000<=n<=9999)。
对于每组数据， 输出恰好修改一个数字， 把 n 变成完全平方数的方案数。
（现代版） 俗话说： 流言止于智者，聊天止于呵呵。 输入一段聊天记录，你的任务是数一数有多少段对话“止于呵呵”，即对话的最后一句话包含单词 hehe 或者它的变形。具体来说， 我们首先提取出对话的最后一句话， 把所有非字母的字符替换成空格， 把所有字符替换成小写， 然后导出一个单词列表（ 由空格隔开） ，只要列表中的任何一个单词是hehe，这段对话就算作“止于呵呵” 。比如， "Hi! Are you OK?" 会变成四个单词： hi, are, you, ok。 注意，单词列表可以是空的（比如，这句话是： "?!?!!"）有些人喜欢使用 hehe 的变形，这些变形也应被视为“呵呵”。为了简单起见，本题只考虑由n(n>1)个 he 连接而成的单词，比如 hehehe 或者 hehehehe。注意，以 hehe 为连续子串的其他单词不应视为“呵呵”，比如 hehee，或者 ehehe。 每两个不同人之间的所有对话算作“一段对话”。
输入仅包含一组数据， 每行是一句对话， 格式为人名 1->人名 2: 一句话. 每行最多包含 1000 个字符，最多 100 行。
输出“ 止于呵呵” 的对话段落所占的百分比， 四舍五入到最近的整数。 输入数据保证答案不会同时和两个整数最近。
A 和 B 之间的最后一句话是"Hehe". A 和 C 之间的最后一句话是"Are you there?". B 和 D 之间的最后一句话是"What does hehehei mean?". E 和 F 之间的最后一句话是"I want to hehehehehe yah". 最后第一段和最后一段话是“止于呵呵”的（注意最后一段对话是以呵呵的变种结束），因此 比例是 50%。 思路：对每一段话进行判断有没有一个段落是由n个hehe组成的即可，注意边界条件
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> using namespace std; int ma[101][101]; map<string,int>m; int main() { char op[10],s[1100]; int cnt=0; memset(ma,0,sizeof(ma)); while(scanf("%s",op)!=EOF) { gets(s); int len=strlen(s); for(int i=len-1; i>=0; i--) { if(s[i]>='A'&&s[i]<='Z') s[i+1]=s[i]-'A'+'a'; else if(s[i]<'a'||s[i]>'z') s[i+1]=' '; else s[i+1]=s[i]; } s[0]=' '; int flag=-1; for(int i=0; i<len; i++) { if(s[i]==' '&&s[i+1]=='h') { int t=1; for(i=i+2; i<=len&&s[i]!=' '; i++) { if(s[i-1]=='h'&&s[i]!='e') break; if(s[i-1]=='e'&&s[i]!='h') break; t++; } if(t>=4&&(s[i]==' '||i>len)&&s[i-1]=='e') { flag=1; break; } i--; } } int q=0; string a; for(q=0; q<strlen(op); q++) { if(op[q]=='-') break; a+=op[q]; } if(m.find(a)==m.end()) m[a]=cnt++; string b; for(q=q+2; q<strlen(op)-1; q++) b+=op[q]; if(m.find(b)==m.end()) m[b]=cnt++; ma[m[a]][m[b]]=ma[m[b]][m[a]]=flag; } double qian=0,hou=0; for(int i=0; i<=100; i++) for(int j=i+1; j<=100; j++) { if(ma[i][j]==-1) hou+=1.0; else if(ma[i][j]==1) qian+=1.0; } hou+=qian; int ans=(int)(qian*100/hou+0.5); printf("%d%%\n",ans); return 0; }
