Test in 01.22 T4:pogo

2024-02-24 05:10

文章标签 test t4 pogo 01.22

本文主要是介绍Test in 01.22 T4:pogo，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

　　这是道很有意思的模拟题。

　　首先，sro XF orz

　　题面：

　　首先想到的是暴力的算法，枚举每一步操作中最顶端的数字，然后在加上顶端数字，但具体的暴力做法是需要一定的思路的，因为骰子中每一面所对的面都是固定的，所以只需要确定上，前，右三个面就可以确定所有面上的数字，然后一一枚举即可：关键代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int r,c,Opposite[7]={0,6,5,4,3,2,1},Top=1,Right=3,Front=2,temp;
 5 long long ans=0;
 6 int main()
 7 {
 8     //读入数据
 9     for (int i=1;i<=r;i++)
10     {
11         ans+=Top;
12     if (i%2==1)//如果为奇数行做向右移动的操作，否则做向左移动的操作
13     for (int j=1;j<c;j++)//注意操作次数为c-1
14     {
15         temp=Opposite[Right];
16         Right=Top;
17         Top=temp;//左右移动的操作中前面的点数不变
18         ans+=Top;
19     }
20     else
21         for (int j=1;j<c;j++)
22         {
23              temp=Opposite[Top];
24                  Top=Right;
25          Right=temp;
26          ans+=Top;
27         }
28         temp=Opposite[Front];
29         Front=Top;
30         Top=temp;//向下移动的操作中右面的点数不变
31     }
32     cout<<ans<<endl;
33     return 0;
34 } 
35

　　但是题目上的数据范围为100000，而暴力算法的时间复杂度为O(n^2)，所以暴力算法只能过50%的数据。

　　这时候需要提取题面中的重要信息：每面上的点数加上其所对的点数之和为7。而在每行上，每4次操作都是重复的，所以在这么多操作中存在了许多次重复的固定操作，而这些固定操作的数字和均为14，次数均为4，所以需要在读入数据直接进行特殊处理，将c转化为小于4的正整数，这样的话就不会超时了。

　　但需要注意的是，如果c在处理之后值为0，在让c取膜并进行计算的同时也将r上的操作进行了，所以这时候需要对是否进行循环进行判断。下面给出AC代码：

#include<iostream>
#include<cstdio>
using namespace std;
int r,c,Opposite[7]={0,6,5,4,3,2,1},Top=1,Right=3,Front=2,temp;
long long ans=0;
int main()
{freopen("pogo.in","r",stdin);freopen("pogo.out","w",stdout);scanf("%d%d",&r,&c);ans=14*((c/4)*r);//直接进行重复的操作c=c%4;//对c进行处理if (c!=0)//特判for (int i=1;i<=r;i++){ans+=Top;if (i%2==1)for (int j=1;j<c;j++){temp=Opposite[Right];Right=Top;Top=temp;ans+=Top;}elsefor (int j=1;j<c;j++){temp=Opposite[Top];Top=Right;Right=temp;ans+=Top;}temp=Opposite[Front];Front=Top;Top=temp;}cout<<ans<<endl;return 0;
}