[CodeForces-629A 用阶乘会爆掉
2024-09-07 19:27:20
题意:
给你一个n*n的蛋糕,如果某个位置是'C'那就代表这是一个巧克力块,否则就不是。如果某两个巧克力块在同一行或同一列,那么这个家庭的幸福值就会加1,问你这个家庭的幸福值最大是多少
Input
3
.CC
C..
C.C
Output
4
Input
4
CC..
C..C
.CC.
.CC.
Output
9
If we number rows from top to bottom and columns from left to right, then, pieces that share the same row in the first sample are:
- (1, 2) and (1, 3)
- (3, 1) and (3, 3)
Pieces that share the same column are:
- (2, 1) and (3, 1)
- (1, 3) and (3, 3)
题解:
原本写的是先统计一下每一行每一列上巧克力块的个数,然后对于一行或一列用排列组合方式求出来有多少巧克力对,比如某行或某列有n块巧克力,那么巧克力对数就是C2n
但是这种方法要求阶乘,会爆掉long long
WA代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<math.h>
6 #include<vector>
7 #include<queue>
8 #include<map>
9 using namespace std;
10 typedef long long ll;
11 const int maxn=110;
12 const int INF=0x3f3f3f3f;
13 char s[maxn][maxn];
14 ll row[maxn],col[maxn],result[maxn];
15 int main()
16 {
17 ll n;
18 scanf("%lld",&n);
19 result[1]=result[0]=1;
20 for(ll i=2;i<=n;++i)
21 {
22 result[i]=result[i-1]*i;
23 }
24 for(ll i=0;i<n;++i)
25 {
26 scanf("%s",s[i]);
27 }
28 for(ll i=0;i<n;++i)
29 {
30 for(ll j=0;j<n;++j)
31 {
32 if(s[i][j]=='C')
33 row[i]++,col[j]++;
34 }
35 }
36 ll sum=0;
37 for(ll i=0;i<n;++i)
38 {
39 //printf("%lld**\n",result[row[i]]);
40 if(row[i]>=2)
41 sum=sum+result[row[i]]/(2*result[row[i]-2]);
42 }
43 for(ll i=0;i<n;++i)
44 {
45 //printf("%lld****\n",result[col[i]]);
46 if(col[i]>=2)
47 sum=sum+result[col[i]]/(2*result[col[i]-2]);
48 }
49 printf("%lld\n",sum);
50 return 0;
51 }
我没有用快速乘和边乘边约分去优化,感觉用的话也可以过。。。但是还要打板子,,我换了一种方式
用时间换空间,暴力去找有多少对,,具体看代码
代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<math.h>
6 #include<vector>
7 #include<queue>
8 #include<map>
9 using namespace std;
10 typedef long long ll;
11 const int maxn=110;
12 const int INF=0x3f3f3f3f;
13 ll n;
14 ll Map[maxn][maxn];
15 char s[maxn][maxn];
16 ll dfs(ll x, ll y)
17 {
18 ll xx = 0, yy = 0;
19 for (ll i = x + 1; i < n; i++)
20 {
21 if (Map[i][y])
22 {
23 xx++;
24 }
25 }
26 for (ll i = y + 1; i < n; i++)
27 {
28 if (Map[x][i])
29 {
30 yy++;
31 }
32 }
33 return xx + yy;
34 }
35 int main()
36 {
37 ll sum=0;
38 scanf("%lld",&n);
39 for(ll i=0;i<n;++i)
40 scanf("%s",s[i]);
41 for (ll i = 0; i < n; i++)
42 {
43 for (ll j = 0; j < n; j++)
44 {
45 if (s[i][j]=='C')
46 {
47 Map[i][j] = 1;
48 }
49 }
50 }
51 for (ll i = 0; i < n; i++)
52 {
53 for (ll j = 0; j < n; j++)
54 {
55 if (Map[i][j])
56 {
57 sum += dfs(i, j);
58 }
59 }
60 }
61 printf("%lld\n",sum);
62 return 0;
63 }
最新文章
- sqlserver实现数据库读写分离介绍
- Lua 之os库
- Java系列笔记(3) - Java 内存区域和GC机制
- GC是什么? 为什么要有GC?
- HDU4945 2048(dp)
- free-jqGrid
- 构建ASP.NET MVC4+EF5+EasyUI+Unity2.x注入的后台管理系统(19)-权限管理系统-用户登录
- MyISAM 存储引擎
- SQLyog-12.4.2版下载,SQLyog最新版下载,SQLyog官网下载,SQLyog Download
- EAS(学生管理系统)初建
- 资源向导之 &;quot;APUE&;quot;
- docker-compose部署ELK
- Nginx 文件下载 apk 文件下载不了
- mongodb插入数据获取本次插入的mongodb id
- Java 语法糖详解
- 使用UI管理docker
- Vue父子组件生命周期
- leetcode 852. Peak Index in a Mountain Array
- beeline 连接hive
- Jquery获取敲击回车时光标所在的位置