Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我 m*m*n的复杂度怎么可能超时?????

Posted by xiaojiongzi at 2017-06-14 20:14:16 on Problem 3865
//#include<bits/stdc++.h>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 10008;
map<string, int> hashG;
int g[MAXN][12];
int n, m, numG;

void read(int nowC)
{
    char s[88], str[88];
    gets(s);
    int ls = strlen(s), k = 0, t = 0;
    s[ls++] = ',';
    for(int i = 0; i < ls; i++)
    {
        if (s[i] == ',')
        {
            str[t] = '\0';
            string sp(str);
            int tmp = hashG.count(sp);
            if (!tmp)
            {
                hashG[sp] = numG++;
            }
            g[nowC][k] = hashG[sp];
            k++;
            t = 0;
            continue;
        }
        str[t++] = s[i];
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    numG = 0;
    getchar();
    //hashG.clear();
    for(int i = 0; i < n; i++)
    {
        read(i);
    }
    for(int i = 0; i < m; i++)
        for(int j = i+1; j < m; j++)
        {
            map<pair<int , int>, int> mp;
            for(int k = 0; k < n; k++)
            {
                pair<int, int> nowP = make_pair(g[k][i], g[k][j]);
                if (mp.count(nowP))
                {
                    printf("NO\n%d %d\n%d %d\n", mp[nowP]+1, k+1, i+1, j+1);
                    return 0;
                }
                mp[nowP] = k;
            }
        }
    printf("YES\n");
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator