2016「百度の星」-資格試合(Astar Round 1)ProblemE(複雑なシミュレーション問題)

Problem E  
 
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
Problem Description
小度熊は責任を果たすプログラム熊で、毎日数千行のコードを産出し、コードには多くの判断条件がある.度熊は自分のコードの中のこれらの条件に交差がないようにしたいと思っています.問題を簡略化するために、1つの条件は「単純条件」または「複合条件」であってもよく、単純条件は「変数」、「比較子」および「演算数」からなり、「変数」は小文字で表される文字列であり、「演算数」は整数のみであり、「演算子」には「<、>、<=、>=、==」==が含まれる.「より小さい」、「より大きい」、「より小さい」、「より小さい」、「より大きい」、「等しい」および「等しい」の関係を表します.単純条件のフォーマットは固定され、左側は変数名、中間はオペレータ、右側は数値です.いくつかの「単純条件」の間には英語のカンマで「複合条件」が構成されており、各「単純条件」の間には論理と関係があり、例えば:
単純条件:a>100
複合条件:duxiong<1000,a>100
Input
ここにはテストデータのセットが含まれています.最初の行は正の整数です. N(1leq Nleq 1000)N(1≦N≦1000)、次に NN 行、行ごとに1つの条件、条件は1つの『簡単な条件』あるいは1つの『複合条件』である可能性があります.このうち「変数」は30文字を超えず、「演算数」の絶対値は10000以内です.テストデータでは、異なる変数の数は30を超えません.このうち、「変数」、「比較子」、「演算数」の前後には、いくつかのスペース文字が表示される可能性があります.すべての単純なルールは『変数』『比較子』『演算数』のような順序で定義されており,特例はない.
Output
第 ii 個の条件を出力 i−1 i−1条件に交差非空があるかどうか.交差が空でない他の条件がない場合は、「unique」という行の文字列を出力します.そうでなければ、空でない交差が存在する条件の番号を小さい順に出力し、番号間をスペースで区切り、最後の番号の末尾にスペースを付けません.各条件は1−N 1−Nから番号付けする.
Sample Input

4
a < 100
c > 99
b > 100 , b == 99 , c < 98
a < 1000, a >= 99

Sample Output

unique
1
unique
1 2

問題を解く構想:実はこの問題は特に話すことができるところがなくて、その構想がとても簡単なため、シミュレーションです
最初はサンプルがよく理解できなかったかもしれませんが、なぜ2番目の条件c>99が1番目の条件a<100と交差するのか分かりません.
理由は簡単であり、第2の条件はcの下限のみを規定し、aの範囲を規定していないため、デフォルトaは任意に取ることができ、第1の条件a<100であるため、100未満の数は任意に取ることができるため、交差が存在する
注意しなければならないのは、いくつかの点です.
1つの複合条件について複数の条件が矛盾すると、その複合条件が空のセットであることを意味し、他の条件とは必ず交差しない、すなわち「unique」
②2つの条件の間に交差がある場合、2つの条件のすべての変数がそれぞれ交差している場合にのみ、2つの条件の間に交差があると計算します.
最大で全部で30個の変数があるので、s[1000][30][2]の配列を開き、1次元表示条件、2次元表示変数、3次元表示変数の上下境界を開き、入力した文字列を処理してから比較すればよい.
タイトルリンク→HDU 5689 ProblemE

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
int a[1007][37][2];
bool f[1007];
map<string,int> mp;
int n;
char str[1000010],op[3];
string s1;
int main()
{
    int i,j,k,cnt,pos,flag;
    int val;
    while(~scanf("%d",&n))
    {
        mp.clear();
        cnt = 0;
        getchar();
        for(i = 0;i < n;i++)
        {
            for(j = 1;j <= 30;j++)
            {
                a[i][j][0] = -1000001;
                a[i][j][1] =  1000001;

            }f[i] = true;
            memset(str,0,sizeof(str));
            gets(str);
            for(j = 0;str[j];j++)
            {
                if(str[j] == ' ' || str[j] == ',') continue;
                s1 = "";
                while(str[j] >= 'a' && str[j] <= 'z')
                    s1 += str[j++];
                if(mp[s1] == 0)
                    mp[s1] = ++cnt;
                pos = mp[s1];
                while(str[j] == ' ') j++;
                memset(op,0,sizeof(op));
                op[0] = str[j];
                if(str[++j] == '=')
                {
                    op[1] = str[j++];
                    op[2] = '\0';
                }
                else
                    op[1] = '\0';
                while(str[j] == ' ') j++;
                val = 0;
                while(str[j] && str[j] >= '0' && str[j] <= '9')
                    val = val*10 + str[j++] - '0';
              //  cout<<"_____"<<s1<<" "<<pos<<" "<<op<<" "<<val<<"_____"<<endl;
                // a[i][pos][0] a[i][pos][1]op val
                if(op[0] == '>' && op[1] == '\0')
                {
                    if(val >= a[i][pos][1]) f[i] = false;
                    else if(val >= a[i][pos][0]) a[i][pos][0] = val+1;
                }
                else if(op[0] == '<' && op[1] == '\0')
                {
                    if(val <= a[i][pos][0]) f[i] = false;
                    else if(val <= a[i][pos][1]) a[i][pos][1] = val-1;
                }
                else if(op[0] == '>' && op[1] == '=')
                {
                    if(val > a[i][pos][1]) f[i] = false;
                    else if(val > a[i][pos][0]) a[i][pos][0] = val;
                }
                else if(op[0] == '<' && op[1] == '=')
                {
                    if(val < a[i][pos][0]) f[i] = false;
                    else if(val < a[i][pos][1]) a[i][pos][1] = val;
                }
                else if(op[0] == '=')
                {
                    if(!(val >= a[i][pos][0] && val <= a[i][pos][1]))   f[i] = false;
                    else
                    {
                        a[i][pos][0] = val;
                        a[i][pos][1] = val;
                    }
                 }
               //  cout<<"_____"<<a[i][pos][0]<<" "<<a[i][pos][1]<<"_____"<<endl;
                 if(!f[i]) break;
            }
            for(j = 0,flag = 0;j < i && f[i];j++)
            {
                if(!f[j]) continue;
                for(k = 1;k <= 30;k++)
                    if(a[i][k][0] > a[j][k][1] || a[i][k][1] < a[j][k][0])
                        break;
                if(k != 31) continue;
                if(!flag)
                {
                    printf("%d",j+1);
                    flag = 1;
                }
                else printf(" %d",j+1);
            }
            if(!flag) puts("unique");
            else puts("");
         //   for(k = 1;k <= 30;k++)
              // cout<<k<<" "<<a[i][k][0]<<" "<<a[i][k][1]<<endl;
        }
    }
    return 0;
}

菜鳥成長記