2017 Russian Code Cup (RCC 17), Final Round
思路:原题转换一下就是找一个b数组,使得b数组任意两个数的差值都和a数组任意两个数的差值相等
根据题目数据范围, 肯定可以构造一个1, 1+d, 1+2d, 1+3d, ... , 1+(n-1)*d的序列
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 105, M = 1e6 + 4; int a[N]; bool vis[M]; int main() { int n, T; scanf("%d", &T); while(T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a+1, a+1+n); bool f = true; for (int i = 1; i <= n; i++) { if(a[i] == a[i-1]) { f = false; break; } } if(!f) { puts("NO"); continue; } f = true; mem(vis, false); for (int i = 1; i <= n; i++) { for (int j = i+1; j <= n; j++) { vis[a[j] - a[i]] = true; } } for (int i = 1; i <= 1000000; i++) { if(!vis[i]) { int cnt = 1; for (int j = i+i; j <= 1000000; j += i) { if(!vis[j]) cnt++; else break; } if(cnt >= n-1) { f = false; puts("YES"); for (int j = 1; j <= n; j ++) printf("%d ", 1+(j-1)*i); printf(" "); break; } } } if(f) puts("NO"); } return 0; }
思路:对于每一个字符串xy, 如果它删去最前面字母得到的后缀y是某个串的前缀的话,我们把xy -> y
这样就会形成一个内向树森林,然后就是求任意两个相邻点最多选一个的点集的最大大小,这个可以用树形dp实现
然后就是要用字符串hash把字符串映射到数,这道题卡单hash,要用双hash
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e6 + 5, base1 = 233, base2 = 43; const int MOD = 1e9 + 7; string s[N]; bool vis[N]; vector<int> g[N]; vector<pair<ULL, ULL>> vc; int dp[N][2]; int dfs(int u, int o, int st) { if(~dp[u][st]) return dp[u][st]; if(vis[u]) vis[u] = false; int ans = 0; if(st) ans = 1; for (int v : g[u]) { if(v != o) { if(st == 1) ans += dfs(v, u, 0); else ans += max(dfs(v, u, 1), dfs(v, u, 0)); } } return dp[u][st] = ans; } int main() { fio; int T, n; cin >> T; while(T--) { cin >> n; for (int i = 0; i < n; i++) cin >> s[i]; vc.clear(); for (int i = 0; i < n; i++) { ULL pre1 = 0, pre2 = 0; for (int j = 0; j < s[i].size(); j++) { pre1 = (pre1*base1 + s[i][j]-'a'+1) % MOD; pre2 = pre2*base2 + s[i][j]-'a'+1; vc.pb({pre1, pre2}); } } sort(vc.begin(), vc.end()); for (int i = 0; i < n; i++) { ULL pre1 = 0, nxt1 = 0, pre2 = 0, nxt2 = 0; for (int j = 0; j < s[i].size(); j++) { pre1 = (pre1*base1 + s[i][j]-'a'+1) % MOD; pre2 = pre2*base2 + s[i][j]-'a'+1; if(j == 0) { int t = lower_bound(vc.begin(), vc.end(), pair<ULL,ULL>{pre1, pre2}) -vc.begin(); if(!vis[t]) { vis[t] = true; } } else { nxt1 = (nxt1*base1 + s[i][j]-'a'+1) % MOD; nxt2 = nxt2*base2 + s[i][j]-'a'+1; int t = lower_bound(vc.begin(), vc.end(), pair<ULL,ULL>{pre1, pre2}) - vc.begin(); if(!vis[t]) { vis[t] = true; int tt = lower_bound(vc.begin(), vc.end(), pair<ULL,ULL>{nxt1, nxt2}) - vc.begin(); if(tt != vc.size() && vc[tt] == pair<ULL,ULL>{nxt1, nxt2}) { g[t].pb(tt); g[tt].pb(t); } } } } } int up = vc.size(); for (int i = 0; i < up; i++) dp[i][0] = dp[i][1] = -1; int ans = 0; for (int i = 0; i < up; i++) { if(vis[i]) { ans += max(dfs(i, i, 0), dfs(i, i, 1)); } } cout << ans << endl; for (int i = 0; i < up; i++) g[i].clear(), vis[i] = false; } return 0; }