Double Strings (别总忘记substr)

语法
substr(size_type _Off = 0,size_type _Count = npos) // 开始位置，长度（默认是到结尾）
一种构造string的方法
形式 ： s.substr(pos, len)
返回值： string，包含s中从pos开始的len个字符的拷贝（pos的默认值是0，len的默认值是s.size() - pos，即不加参数会默认拷贝整个s）
异常 ：若pos的值超过了string的大小，则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾
1
2
3
4
5
6

题目描述

You are given $ n $ strings $ s_1, s_2, \dots, s_n $ of length at most $ \mathbf{8} $ .

For each string $ s_i $ , determine if there exist two strings $ s_j $ and $ s_k $ such that $ s_i = s_j + s_k $ . That is, $ s_i $ is the concatenation of $ s_j $ and $ s_k $ . Note that $ j $ can be equal to $ k $ .

Recall that the concatenation of strings $ s $ and $ t $ is $ s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q $ , where $ p $ and $ q $ are the lengths of strings $ s $ and $ t $ respectively. For example, concatenation of “code” and “forces” is “codeforces”.

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the number of strings.

Then $ n $ lines follow, the $ i $ -th of which contains non-empty string $ s_i $ of length at most $ \mathbf{8} $ , consisting of lowercase English letters. Among the given $ n $ strings, there may be equal (duplicates).

The sum of $ n $ over all test cases doesn’t exceed $ 10^5 $ .

输出格式

For each test case, output a binary string of length $ n $ . The $ i $ -th bit should be $ \texttt{1} $ if there exist two strings $ s_j $ and $ s_k $ where $ s_i = s_j + s_k $ , and $ \texttt{0} $ otherwise. Note that $ j $ can be equal to $ k $ .

样例 #1

样例输入 #1

3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

样例输出 #1

10100
011
10100101
1
2
3

提示

In the first test case, we have the following:

• $ s_1 = s_2 + s_2 $ , since $ \texttt{abab} = \texttt{ab} + \texttt{ab} $ . Remember that $ j $ can be equal to $ k $ .
• $ s_2 $ is not the concatenation of any two strings in the list.
• $ s_3 = s_2 + s_5 $ , since $ \texttt{abc} = \texttt{ab} + \texttt{c} $ .
• $ s_4 $ is not the concatenation of any two strings in the list.
• $ s_5 $ is not the concatenation of any two strings in the list.

Since only $ s_1 $ and $ s_3 $ satisfy the conditions, only the first and third bits in the answer should be $ \texttt{1} $ , so the answer is $ \texttt{10100} $ .

---

写的时候，用set写了非常丑陋的代码。不过set是真的好用。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
ll n,m,_;
string s[N];
bool ans[N];
set<string>st;
bool ck(string s,string t){
    // s删除t
    int pos = s.find(t);
    if(pos==-1)return false;
    string tmp = "";
    for(int i=pos;i<s.size();i++){
        tmp+=s[i];
    }
    if(st.find(tmp) == st.end())return -1;
    return 1;
}
void solve(){
    cin>>n;
	st.clear();
    fo(i,1,n){
        cin>>s[i];
        st.insert(s[i]);
    }
    for(int i=1;i<=n;i++){
        string t = s[i]; // 8
        st.erase(s[i]); // 8
        string tmp = "";
        for(int j=0;j<t.size();j++){
            tmp += t[j];
            if(ck(t,tmp)){
                ans[i]=1;
            }
        }
        st.insert(s[i]);
    }
    fo(i,1,n){
        cout<<ans[i];
    }
    cout<<endl;
}

int main(){
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include 
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	string s[n];
	map<string, bool> mp;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		mp[s[i]] = true;
	}
	for (int i = 0; i < n; i++) {
		bool ok = false;
		for (int j = 1; j < s[i].length(); j++) {
			string pref = s[i].substr(0, j), suff = s[i].substr(j, s[i].length() - j);
			if (mp[pref] && mp[suff]) {ok = true;}	
		}
		cout << ok;
	}
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33