资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

SRM477-创新互联

250pt:SRM477

题意：给定一块蜂巢状的N*M矩阵，每块六边形和周围6个六边形相邻，现在告诉你哪些是陆地，哪些是水，问水陆交界处的长度。

创新互联是一家集网站建设,邵东企业网站建设,邵东品牌网站建设,网站定制,邵东网站建设报价,网络营销,网络优化,邵东网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

思路：直接模拟

code：

 1 #line 7 "Islands.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 
34 typedef vector VI;
35 typedef vector VS;
36 typedef vector VD;
37 typedef long long LL;
38 typedef pair PII;
39 
40 
41 class Islands
42 {
43 public:
44 int beachLength(vector  S)
45         {
46   int ans = 0;
47   int n = S.size(), m = S[0].size(), p;
48   for (int i = 0; i < n; ++i)
49   for (int j = 0; j < m; ++j){
50  if (j > 0 && S[i][j] == '#' && S[i][j-1] == '.') ++ans;
51  if (j > 0 && S[i][j] == '.' && S[i][j-1] == '#') ++ans;
52  if (i == 0) continue;
53  if (i & 1) p = j;
54  else p = j - 1;
55  if (p >= 0 && S[i][j] == '.' && S[i-1][p] == '#') ++ans;
56  if (p >= 0 && S[i][j] == '#' && S[i-1][p] == '.') ++ans;  
57  if (p + 1 < m && S[i][j] == '.' && S[i-1][p+1] == '#') ++ans;
58  if (p + 1 < m && S[i][j] == '#' && S[i-1][p+1] == '.') ++ans; 
59                 }
60   return ans;
61         }
62   };
View Code

500pt:

题意:给定最多200个正整数，问最多能组成多少个勾股数对。勾股数对定义：对于互质数对(a, b)，存在c,使得a*a+b*b=c*c,

思路：隐蔽的二分图。

    很明显先求出勾股数对，那么接下来便是一个大匹配了。

    不过，是二分图吗？

    对于奇数a与奇数b，由于互质，那么a^2+b^2必定是2的倍数，必然不存在c

    对于偶数a与偶数b,不互质显然不存在。　

所以是个二分图，直接匹配即可

ｃｏｄｅ：

 1 #line 7 "PythTriplets.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
25 using namespace std;
26 #define PB push_back
27 #define MP make_pair
28 #define REP(i,n) for(i=0;i<(n);++i)
29 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
30 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
31 #define M0(a) memset(a, 0, sizeof(a))
32 typedef vector VI;
33 typedef vector VS;
34 typedef vector VD;
35 typedef long long LL;
36 typedef pair PII;
37 int match[210], g[210][210];
38 int n, m;
39 bool vis[210];
40 class PythTriplets
41 {
42 public:
43         vector v1, v2;
44 void makePoint(string &S){
45   int tmp = 0;
46   for (int i = 0; i < S.size(); ++i)
47   if (S[i] == ' '){
48  if (tmp == 0) continue;
49  if (tmp & 1) v1.push_back(tmp);
50  else v2.push_back(tmp);
51                      tmp = 0;
52                 } else tmp = tmp * 10 + S[i] - 48;
53   if (tmp > 0){
54  if (tmp & 1) v1.push_back(tmp);
55  else v2.push_back(tmp);
56              }
57         }
58         LL gcd(LL a, LL b){
59 return b ? gcd(b, a % b) : a;
60         }
61 bool ok(long long a, long long b){
62 if (gcd(a, b) > 1) return false;
63 long long c = floor(sqrt(a * a + b * b + .0));
64 if (c * c < a * a + b * b) ++c;
65 if (a * a + b * b == c * c) return true;
66 return false;
67         }
68 bool search_path(int u){
69   for (int v = 0; v < m; ++v) if (g[u][v] && !vis[v]){
70                    vis[v] = true;
71   if (match[v] == -1 || search_path(match[v])){
72                          match[v] = u;
73   return true;
74                    }
75              }
76   return false;
77         }
78 int findMax(vector  stick)
79         {
80             v1.clear();
81             v2.clear();
82  string S = accumulate(stick.begin(), stick.end(), string(""));
83             makePoint(S);
84             n = v1.size();
85             m = v2.size();
86             M0(g);
87  for (int i = 0; i < n; ++i)
88  for (int j = 0; j < m; ++j)
89  if (ok(v1[i], v2[j])) g[i][j] = true;//, cout << v1[i] <<  " " << v2[j] << endl;90  int ans = 0;
91             memset(match, -1, sizeof(match));
92  for (int i = 0; i < n; ++i){
93                   M0(vis);
94  if (search_path(i)) ++ ans;
95             }
96  return ans;
97         }
98 };
View Code
文章题目：SRM477-创新互联
本文链接：http://www.cdkjz.cn/article/dcjcei.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
微信小程序开发成都圣月制冷成都网站建设公司成都酒店服定制成都网站建设产品包装设计香港虚拟主机腾讯云微信公众号二次开发定制网站重庆教育培训网站建设

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图