[Codeforces] 858D. Polycarp's phone book

題目連結:http://codeforces.com/contest/861/problem/D
裸裸的對於每個字串枚舉他可能會有的子字串,然後判斷一下是否沒出現在其他人過就好了,一開始寫了hash但不知道為何一直WA,最後開個unordered_map就過了...
#include <bits/stdc++.h>
using namespace std;
#define PB push_back

unordered_map<string,int> ex;
vector<string> inp;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++){
		string ss; cin>>ss;
		for(int j=0;j<9;j++){
			string tp;
			for(int k=j;k<9;k++){
				tp.push_back(ss[k]);
				ex[tp]++;
			}
		}
		inp.PB(ss);
	}
	for(int i=0;i<n;i++){
		string ans = "IOI2018Participant";
		for(int j=0;j<9;j++){
			string tp;
			for(int k=j;k<9;k++){
				tp.push_back(inp[i][k]);
				ex[tp]--;
			}
		}
		for(int j=0;j<9;j++){
			string tp;
			for(int k=j;k<9;k++){
				tp.push_back(inp[i][k]);
				if(tp.size() < ans.size() and ex[tp] == 0) ans=tp;
			}
		}
		for(int j=0;j<9;j++){
			string tp;
			for(int k=j;k<9;k++){
				tp.push_back(inp[i][k]);
				ex[tp]++;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology