CF 239

本文主要是介绍CF 239，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C 

http://codeforces.com/contest/408/problem/C

题意：给一个直角三角行的两条直角边a,b，求出直角三角形的三个顶点（必须是整数）满足该直角三角形的三条边都不平行于坐标轴。

思路：对于a,b,若它不平行于坐标轴，那么它肯定是某两个整数的平方和。然后根据点积判断这两条假设的直角边是否垂直，垂直的前提下判断第三条边是否平行于坐标轴。若a,b不是某两个整数的平方和输出NO、

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;const int INF = 0x3f3f3f3f;int p[1010];
struct node
{int x,y;
}aa[1010],bb[1010];void init()
{for(int i = 1; i <= 1000; i++){p[i] = i*i;}
}int solve(int x1,int y1,int x2,int y2)
{if(x1 * x2 + y1 * y2  == 0)return 1;return 0;
}int main()
{init();int a,b;while(~scanf("%d %d",&a,&b)){int t = max(a,b);int cnt1 = 0;int cnt2 = 0;for(int i = 1; i <= t; i++){for(int j = 1; j <= t; j++){if(p[i] + p[j] == a*a){aa[cnt1++] = (struct node){i,j};}if(p[i] + p[j] == b*b){bb[cnt2++] = (struct node){i,j};}}}if(cnt1 == 0 || cnt2 == 0){printf("NO\n");continue;}int f = 0;for(int i = 0; i < cnt1; i++){int x1 = aa[i].x;int y1 = aa[i].y;for(int j = 0; j < cnt2; j++){int x2 = bb[j].x;int y2 = bb[j].y;if(solve(-x1,y1,x2,y2) == 1){if(y1 != y2){printf("YES\n");printf("0 0\n");printf("%d %d\n",-x1,y1);printf("%d %d\n",x2,y2);f = 1;break;}}if(solve(-x1,y1,y2,x2) == 1){if(y1 != x2){printf("YES\n");printf("0 0\n");printf("%d %d\n",-x1,y1);printf("%d %d\n",y2,x2);f = 1;break;}}if(solve(-y1,x1,x2,y2) == 1){if(x1 != y2){printf("YES\n");printf("0 0\n");printf("%d %d\n",-y1,x1);printf("%d %d\n",x2,y2);f = 1;break;}}if(solve(-y1,x1,y2,x2) == 1){if(x1 != x2){printf("YES\n");printf("0 0\n");printf("%d %d %d %d\n",-y1,x1,y2,x2);f = 1;break;}}}if(f)break;}if(f == 0) printf("NO\n");}return 0;}

D. Long Path 

http://codeforces.com/problemset/problem/407/B

题意：有n+1个迷宫，编号1~n+1，Vasya从1开始，初始他在1号房间标记1，他按如下规则前进：

他每走进一个房间，都会在房间上多画一个十字架；

假设他当前在i房间，已画上十字架，如果天花板上有奇数个十字架，他要移动到pi房间，否则就移动到i+1房间。

问他走到n+1房间要走的步数。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define LL __int64
using namespace std;const int mod = 1000000007;
int n;
LL dp[1010];
int a[1010];int main()
{while(~scanf("%d",&n)){for(int i = 1; i <= n; i++)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));LL ans = 0;dp[1] = 2; ans += dp[1];for(int i = 2; i <= n; i++){dp[i] = 2;for(int j = a[i]; j < i; j++)dp[i] = (dp[i]+dp[j])%mod;ans = (ans%mod + dp[i])%mod;}printf("%I64d\n",ans);}return 0;
}

这篇关于CF 239的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---