CodeForces 629A-Far Relative’s Birthday Cake(枚举/暴力)

2023-10-24 03:30

本文主要是介绍CodeForces 629A-Far Relative’s Birthday Cake(枚举/暴力),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:

Door's family is going celebrate Famil Doors's birthday party. They love Famil Door so they are planning to make his birthday cake weird!

The cake is a n×n n×n n×n square consisting of equal squares with side length 1 1 1 . Each square is either empty or consists of a single chocolate. They bought the cake and randomly started to put the chocolates on the cake. The value of Famil Door's happiness will be equal to the number of pairs of cells with chocolates that are in the same row or in the same column of the cake. Famil Doors's family is wondering what is the amount of happiness of Famil going to be?

Please, note that any pair can be counted no more than once, as two different cells can't share both the same row and the same column.

输入:

In the first line of the input, you are given a single integer n n n ( 1<=n<=100 1<=n<=100 1<=n<=100 ) — the length of the side of the cake.

Then follow n n n lines, each containing n n n characters. Empty cells are denoted with '.', while cells that contain chocolates are denoted by 'C'.

输出:

Print the value of Famil Door's happiness, i.e. the number of pairs of chocolate pieces that share the same row or the same column. 

样例输入1: 

3

.CC

C..

C.C  

样例输出1: 

样例输入2: 

4

CC..

C..C

.CC.

.CC.  

样例输出2: 

9

题目大意 and 解题思路: 

蛋糕是一个由 n×n 的正方形组成的形状,长度为1。每个方块要么是空的,要么是由一个巧克力组成的。他们买了蛋糕,便开始把巧克力放在蛋糕上。“家庭之门”的幸福值等于蛋糕中同一行或同一列中装有巧克力的一对细胞的数量。多尔的家人想知道他们的幸福程度是多少?

第一行输入一个整数n(1<=n<=100),表示蛋糕边的长度。然后输入n行数,每行有n个字符。空的细胞用'.'表示,而含有巧克力的细胞用“C”表示。

输出“家庭之门”幸福感的价值,即同一行或同一列的一对巧克力片的数量。

这道题直接遍历就可以了,用一个数c去记录一行或一列中巧克力的数量,t来表示“家庭之门”幸福感的价值,那么在某一行或者是某一列中,任意两个字符 'C' 就算是构成了一对巧克力,相应的价值加1,所以:

当c=1时,t=0;当c=2时,t=1;当c=3时,t=3;当c=4时,t=6......我们会发现一个规律:t=(c*(c-1))/2

你也可以理解成:一个包含n个结点的无向图中,可以包含的边数。

AC Code: 

#include<bits/stdc++.h>
using namespace std;
int main() {int n,sum=0,a=0,b=0;char s[101][101];scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf(" %c",&s[i][j]);//%前面有个空格,保证完整输入for(int i=1;i<=n;i++) {//横向遍历a=0;for(int j=1;j<=n;j++) {if(s[i][j]=='C')a++;}sum+=(a*(a-1))/2;}for(int j=1;j<=n;j++) {//纵向遍历b=0;for(int i=1;i<=n;i++) {if(s[i][j]=='C')b++;}sum+=(b*(b-1))/2;}printf("%d\n",sum);return 0;
} 

本题虽然是在洛谷上面提交的,但是题目来源在 CodeForces 上,所以博主就直接在 CodeForces 进行提交了。

这篇关于CodeForces 629A-Far Relative’s Birthday Cake(枚举/暴力)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/272405

相关文章

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

Java 枚举的常用技巧汇总

《Java枚举的常用技巧汇总》在Java中,枚举类型是一种特殊的数据类型,允许定义一组固定的常量,默认情况下,toString方法返回枚举常量的名称,本文提供了一个完整的代码示例,展示了如何在Jav... 目录一、枚举的基本概念1. 什么是枚举?2. 基本枚举示例3. 枚举的优势二、枚举的高级用法1. 枚举

Rust中的Option枚举快速入门教程

《Rust中的Option枚举快速入门教程》Rust中的Option枚举用于表示可能不存在的值,提供了多种方法来处理这些值,避免了空指针异常,文章介绍了Option的定义、常见方法、使用场景以及注意事... 目录引言Option介绍Option的常见方法Option使用场景场景一:函数返回可能不存在的值场景

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

CF629D Babaei and Birthday Cake

题意:给出N个半径,和高的圆柱,要求后面的体积比前面大的可以堆在前一个的上面,求最大的体积和。 dp[i]=max(dp[j])+v[i](j<i&&v[i]>v[j]); 离散化,线段树维护区间最大值 import java.io.BufferedInputStream;import java.io.BufferedOutputStream;import

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja