MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 253 - Cube painting
AOAPC II

UVaOJ 253 - Cube painting

Chai
2021-11-24 0:00:00在线评测阅读 324

问题描述

p253

原题链接:UVaOJ 253 - Cube painting

相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-4

解法一:找规律(思维)

朴素解法是将正方体的 24 种摆放姿势生成(或罗列)出来,比如每次固定上下两个面(有六种情况),然后水平旋转 4 次,就能得到全部的可能,然后看是否有匹配的编码,有则输出 "YES".

实际上发现规律就很简单,如果两个正方体可以通过旋转得到,那么它们的 3 个对立面一定能够匹配。这个规律在尝试固定上下两个面的时候就能够发现,不论你选择哪两个面固定,它们一定是相对的,这个相对性在旋转时是不会被打破的。而如果给出了一个正方体的三个相对面,这个正方体其实就被确定了(任意的一个顶点一定与三个面相邻)。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  string s;
  while (cin >> s) {
    vector<pair<char, char>> opposite[2];
    for (int i = 0; i < 2; ++i) {
      int p = 6 * i;
      opposite[i].push_back(pair<char, char>{s[p], s[p + 5]});
      opposite[i].push_back(pair<char, char>{s[p + 1], s[p + 4]});
      opposite[i].push_back(pair<char, char>{s[p + 2], s[p + 3]});
    }
    for (auto o : opposite[0])
      for (auto it = opposite[1].begin(); it != opposite[1].end(); ++it)
        if ((o.first == it->first && o.second == it->second) ||
            (o.first == it->second && o.second == it->first)) {
          opposite[1].erase(it);
          break;
        }
    cout << (opposite[1].empty() ? "TRUE" : "FALSE") << endl;
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz