传送门:https://ac.nowcoder.com/acm/contest/5671/K
题意
T组测试,每组输入$n$和$k$,表示下一行有n个包,最多有1~k种包,下一行给出n个包的序列,问符不符合全排列的顺序,输出YES或NO(阳寿题)。
思路
因为n不一定整除k,所以前一段和后一段不一定是完整的k-全排列序列,先找出前后这一段,然后检查中间一部分是否是k-全排列(注意:k-全排列序列可重复)。当n<k时,只需要判断前一段的长度是否大于后一段长度,如果小于的话,中间一段一定不满足k-全排列序列。
==重点== 怎么判断中间是否为k-全排列序列,如果是暴力判断,可能会T,这时候就需要异或和和前缀和了,我们在输入的时候做一个前缀和、异或和预处理,再从1~k做一个异或和预处理为x,前缀和预处理为s,因为两个相同的数异或为0,所以判断一段序列中是否存在相同数字,只需要判断那一段的异或和是否等于x,这样还不够,还需要判断这一段的前缀和是否等于s,只有这两个条件满足,说明这一段序列是满足k-全排列序列。这样处理会比暴力好很多。
Code
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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
| ##include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef long double ld; typedef pair<int, int> pdd;
##define INF 0x7f7f7f ##define mem(a,b) memset(a , b , sizeof(a)) ##define FOR(i, x, n) for(int i = x;i <= n; i++)
const int MAXN = 5e5 + 10;
ll n, k; ll f[MAXN]; ll pre1[MAXN]; ll pre2[MAXN]; bool vis[MAXN]; map<int, int> mp;
void solve() { scanf("%lld%lld", &n, &k); for (int i = 1; i <= n; i++) { scanf("%lld", &f[i]); pre1[i] = pre1[i - 1] + f[i]; pre2[i] = pre2[i - 1] ^ f[i]; } int tot1 = 0, tot2 = 0; mp.clear(); for (int i = 1; i <= n; i++) { if (mp[f[i]] == 1) break; mp[f[i]]++; tot1 = i; } mp.clear(); for (int i = n; i >= 1; i--) { if (mp[f[i]] == 1) break; mp[f[i]]++; tot2 = i; } if (n < k) { if(tot1 + 1 >= tot2) printf("YES\n"); else printf("NO\n"); return; } ll s = 0; ll x = 0; for(int i = 1;i <= k; i++) { s += i; x ^= i; } int flag = 0; for (int len = 0; len <= tot1; len++) { ll i = len, flag2 = 1; for (; i + k <= n; i += k) { ll v1 = pre1[i + k] - pre1[i]; ll v2 = pre2[i + k] ^ pre2[i]; if (s != v1 x != v2) { flag2 = 0; break; } } if (flag2 && i + 1 >= tot2) { flag = 1; break; } } if(flag) printf("YES\n"); else printf("NO\n"); }
signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ##ifdef ACM_LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long long test_index_for_debug = 1; char acm_local_for_debug; while (cin >> acm_local_for_debug) { if (acm_local_for_debug == '$') exit(0); cin.putback(acm_local_for_debug); if (test_index_for_debug > 20) { throw runtime_error("Check the stdin!!!"); } auto start_clock_for_debug = clock(); solve(); auto end_clock_for_debug = clock(); cout << "Test " << test_index_for_debug << " successful" << endl; cerr << "Test " << test_index_for_debug++ << " Run Time: " << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl; cout << "--------------------------------------------------" << endl; } ##else int T; scanf("%d",&T); while (T--) solve(); ##endif return 0; }
|
本文作者:jujimeizuo
本文地址: https://blog.jujimeizuo.cn/2020/08/01/2020-nowcoder-shujia-6-k/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!