Prateek Krishna Ответов: 3

Как бороться с превышением лимита времени в этом случае?

вопрос в том, чтобы найти ни одного из общих символов в n строках.

Первая строка входных данных содержит одно целое число T, обозначающее количество тестовых случаев. Описание тестов t следующим образом.
Первая строка каждого тестового набора содержит одно целое число N
Н
строк. Для каждого i (1≤i≤N) i-я из этих строк содержит одну строку Si.

Ограничения

1≤T≤1000
1≤N≤1000
1≤|Si|≤200

для каждого действительного i
S1,S2,...,SN
содержат только строчные английские буквы
Сумма длин строк по всем тестовым случаям ≤ 3500000

Что я уже пробовал:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {
	int n;
	cin>>n;
	if(n==1)
	{cin.ignore();
	    string s;
	    getline(cin,s);
	    int k=s.length();
	    cout<<k<<"\n";
	}
	else
	{
	int i,ctr=0;
	bool c[26];
	memset(c,true,sizeof(c));
	cin.ignore();
	while(n--)
	{
	     string s;
	     getline(cin,s);
	     bool a[26]={false};
	     
	     for(i=0;i<s.length();i++)
	     a[s[i]-'a']=true;
	    
	     for(i=0;i<26;i++)
	     if(a[i]!=c[i])
	      c[i]=false;
	}
	for(i=0;i<26;i++)
	if(c[i]==true)
	ctr++;
	cout<<ctr<<"\n";
	}
    }
	return 0;
}

ZurdoDev

В чем заключается ваш вопрос?

Prateek Krishna

он показывает превышение лимита времени...
Как с этим бороться?

Rick York

Напишите код, который работает быстрее.

Prateek Krishna

можете ли вы дать несколько советов относительно этого кода для работы с TLE

Rick York

Вы можете начать с получения всех ваших входных данных из файла, а не cin. Вы просто должны использовать другой поток, отличный от cin, тот, который вы открыли сами. Вы всегда должны делать это, когда можете, потому что гораздо проще создавать тестовые случаи, которые можно использовать снова и снова. Вы можете иметь несколько файлов для различных тестов и легко переключаться между ними.

Richard MacCutchan

Эти упражнения в значительной степени являются пустой тратой времени. Возьмите хорошую книгу на C++ и изучите язык в деталях.

Rick York

Я полностью согласен! Очень жаль, что я не могу дать этому комментарию оценку. ;)

Richard MacCutchan

Спасибо, но не волнуйтесь; очки здесь не делают призов. :)

3 Ответов

Рейтинг:
1

Patrice T

Цитата:
Как бороться с превышением лимита времени в этом случае?

Проще говоря, вам нужно найти более эффективный алгоритм, который решит эту проблему.
Вам нужно понять, где ваша программа тратит время и вещь, если другой способ может быть быстрее.
инструмент, позволяющий увидеть, как программа тратит время, - это профилировщик программ.

Рейтинг:
1

CPallini

Попробуйте с помощью C++

#include <iostream>
#include <array>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
  size_t T;
  cin >> T;
  for (size_t t = 0; t<T; t++)
  {
    size_t N;

    cin >> N;
    cin.ignore();

    array<size_t, 26> occur{0};
    for (size_t n = 0; n< N; ++n)
    {
      string line; 
      getline(cin, line);
      set<char> s;
      for (auto c : line)
        s.insert(c); 
      for ( auto c : s)
        occur[c-'a']++;
      }
    }
    size_t common = count_if(occur.begin(),  occur.end(), [N](size_t x){return x == N;});
    cout << common << "\n";
  }
}

Рейтинг:
0

Dave Kreskowiak

Эти задачи написаны, чтобы заставить вас действительно думать о различных решениях проблемы.

Если вы просто идете и кодируете простой, прямолинейный алгоритм для решения проблемы, ваш код будет работать, но всегда будет терпеть неудачу в течение ограниченного времени.

Вы должны отказаться от этого кода и переосмыслить, как вы атакуете проблему, как описано выше.

Нет, я не даю вам алгоритм решения проблемы, потому что это я буду думать о том, как решить проблему, а не вы думаете об этом, и в этом весь смысл этих проблем.