Codeforces Round #234A

Inna and choose option

    题意:

一个由12个字符('O'或'X')组成的字符串,这12个字符可以排列成a*b(a*b=12)的矩阵,要求矩阵某一列都是'X'。用户输入t个字符串,都是由12个'O'或'X组成,设计函数可求解符合要求矩阵的个数,并且将符合要求的矩阵大小输出。

Input:

第一行输入一个整数t(Range:1-100),t表示要输入的测试数据的个数,下面每一行输入都是一组数据被录入。

Output:

将每组数据的结果放在一行输出,format:n axb axb axb ….

n表示满足要求的矩阵个数,后面是具体的矩阵大小。

    例如:

解题思路:

    可以看出矩阵个数最大为6,分别是(1,12)(2,6)(3,4)(4,3)(6,2)(12,1),将这些情况枚举出来,然后for循环判断矩阵的每一列,若有一列满足条件(全为'X'),那么将这个矩阵行数列数分别保存到一个6行2列的数组的第一行,k来计数,最后k中存的就是满足条件的矩阵个数,数组里面前k行存的就是具体大小。

    代码:

 1 #include <iostream>
 2 using namespace std;
 3 #include <string>
 4 #define MAX 100
 5 
 6 
 7 int main(void)
 8 {
 9     string s[MAX];
10     int t;
11     void inna(string card);
12     cin >> t;
13     for(int i=0;i<t;i++)
14     {
15         cin >> s[i];
16     }
17 
18     for(int i=0;i<t;i++)
19     {
20         inna(s[i]);
21     }
22     return 0;
23  } 
24 
25 void inna(string card)
26 {
27     int i,j,k=0,m;
28     bool flag = true;
29     int a[6] = {1,2,3,4,6,12};       // 行数有六中情况
30     int b[6] = {12,6,4,3,2,1};       // 列数 
31     int n[6][2];
32     
33     if(card == "OOOOOOOOOOOO")         // 12张卡片全为o 
34     {
35         cout << k << endl;
36         return;                      // 结束函数体 
37     }
38     
39     for(i=0;i<6;i++)                 // i表示行数 
40     {
41         for(j=0;j<b[i];j++)
42         {
43             flag = true;
44             for(m=0;m<a[i];m++)
45             {
46                 if(card[j+m*b[i]]!='X')
47                 {
48                     flag = false;
49                     break;
50                 }
51             }
52 
53             if(flag)
54             {
55                 n[k][0] = a[i];
56                 n[k][1] = b[i];
57                 k++;
58                 break;
59             }
60          }
61      }
62      
63      cout << k << ' ';
64      for(i=0;i<k;i++)
65      {
66          cout << n[i][0] << 'x' << n[i][1] << ' ';
67      }
68      cout << endl;
69 }

    测试结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

迷宫问题(BFS问题) - POJ 3984

本题是新加入我们的大虾Gabriel童鞋写的,他是一个刚入大学的大一新生,孺子如虎也,赞!

1072
来自专栏计算机视觉与深度学习基础

全排列生成算法:next_permutation

概念 全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则...

1966
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

811
来自专栏算法修养

温故KMP算法

最近由于某些原因,又回顾了一次KMP算法。上一次回顾KMP算法还是在刷题的时候遇到的: http://blog.csdn.net/dacc123/article...

3488
来自专栏编程理解

数据结构(八):邻接表与邻接矩阵

邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

902
来自专栏HTML5学堂

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

3305
来自专栏用户画像

7.4.1简单选择排序

选择排序的基本思想是:每趟(例如第i趟)在后面 n-i+1(i=1,2,...,n-1)个待排序元素中选取关键字最小的元素,

572
来自专栏算法channel

Leetcode|Find K Closest Elements

01 — 题目 Given a sorted array, two integers k and x, find the k closest elements ...

3384
来自专栏尾尾部落

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

872
来自专栏来自地球男人的部落格

[LeetCode] 523. Continuous Subarray Sum

【原题】 Given a list of non-negative numbers and a target integer k, write a fun...

2118

扫码关注云+社区