国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

相同的雪花

2019-11-14 10:26:38
字體:
來源:轉載
供稿:網友

相同的雪花

時間限制:1000 ms  |  內存限制:65535 KB難度:4描述 You may have heard that no two snowflakes are alike. Your task is to write a PRogram to determine whether this is really true. Your program will read information about a collection of snowflakes, and search for a pair that may be identical. Each snowflake has six arms. For each snowflake, your program will be provided with a measurement of the length of each of the six arms. Any pair of snowflakes which have the same lengths of corresponding arms should be flagged by your program as possibly identical.輸入The first line of the input will contain a single interger T(0<T<10),the number of the test cases.The first line of every test case will contain a single integer n, 0 < n ≤ 100000, the number of snowflakes to follow. This will be followed by n lines, each describing a snowflake. Each snowflake will be described by a line containing six integers (each integer is at least 0 and less than 10000000), the lengths of the arms of the snow ake. The lengths of the arms will be given in order around the snowflake (either clockwise or counterclockwise), but they may begin with any of the six arms. For example, the same snowflake could be described as 1 2 3 4 5 6 or 4 3 2 1 6 5.輸出For each test case,if all of the snowflakes are distinct, your program should print the message:No two snowflakes are alike.If there is a pair of possibly identical snow akes, your program should print the message:Twin snowflakes found.樣例輸入
121 2 3 4 5 64 3 2 1 6 5樣例輸出
Twin snowflakes found.

解題報告:Hash算法的簡單應用。對arms和Hash下就行了。

code:

#include<iostream>#include<stdio.h>#include<queue>#include<vector>#include<stack>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int maxn=100005;const int gcd=100000;int snow[maxn][6];  //存雪花arms值vector<int> v[maxn]; //存相同arms和的雪花bool deal(int a,int b){  //比較兩個雪花是否相同    for(int i=0;i<6;i++){        if(           (snow[a][0]==snow[b][i] &&      //順時針比較           snow[a][1]==snow[b][(i+1)%6] &&           snow[a][2]==snow[b][(i+2)%6] &&           snow[a][3]==snow[b][(i+3)%6] &&           snow[a][4]==snow[b][(i+4)%6] &&           snow[a][5]==snow[b][(i+5)%6])            ||           (snow[a][0]==snow[b][i] &&      //逆時針比較           snow[a][1]==snow[b][(i+5)%6] &&           snow[a][2]==snow[b][(i+4)%6] &&           snow[a][3]==snow[b][(i+3)%6] &&           snow[a][4]==snow[b][(i+2)%6] &&           snow[a][5]==snow[b][(i+1)%6])           )            return true;    }    return false;}int main(){  //  freopen("input.txt","r",stdin);    int t,n;    scanf("%d",&t);    while(t--){        memset(snow,0,sizeof(snow));        for(int i=0;i<maxn;i++){ //初始化            v[i].clear();        }        scanf("%d",&n);        for(int i=0;i<n;i++){            int sum=0;            for(int j=0;j<6;j++){                scanf("%d",&snow[i][j]);                sum+=snow[i][j];            }            sum=sum%gcd;            v[sum].push_back(i);        }        int flag=0;  //默認無相同雪花        for(int i=0;i<maxn;i++){            if(flag)                break;            if(v[i].size()>=2){                for(int j=0;j<v[i].size()-1;j++){                    for(int k=j+1;k<v[i].size();k++){                        if(deal(v[i][j],v[i][k])){                            flag=1;                            break;                        }                    }                }            }        }        if(!flag)            printf("No two snowflakes are alike./n");        else            printf("Twin snowflakes found./n");    }    return 0;}


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 开江县| 峡江县| 绵阳市| 加查县| 京山县| 革吉县| 公安县| 通化市| 宁晋县| 读书| 榆社县| 淮滨县| 乌鲁木齐市| 肥乡县| 铜梁县| 德惠市| 宜宾市| 屏边| 平昌县| 绩溪县| 兴隆县| 延川县| 牙克石市| 策勒县| 聂拉木县| 宜兰市| 平远县| 苗栗市| 菏泽市| 深泽县| 龙泉市| 防城港市| 始兴县| 台东县| 佛坪县| 东莞市| 乌鲁木齐县| 彝良县| 临沂市| 黔东| 岚皋县|