Codeforces Round 1096 (Div. 3)补题

D. Palindromex

知识点：思维

思路：要注意到几个点，每个 \([0,n-1]\) 之间的数都出现了两次，而且要找最大 \(mex\) 的话,序列一定会有 \(0\),有两种情况 \(0\) 作为奇数串的中心，或者 \(0\) 在一个序列的两边，以这两个点为中心的回文串，也就是说只需要找三个回文串，分别是以 两个 \(0\) 为中心的子串和以 两个 \(0\) 中心为中心的子串，取其中的最大值即可

Code

点击查看代码

int f(int l, int r, const vi &a, int n)
{int len = 2 * n;while (l >= 0 && r < len && a[l] == a[r]){l--;r++;}l++;r--;if (l > r)return 0;vi v(n + 1, 0);for (int i = l; i <= r; i++){if (a[i] <= n){v[a[i]]++;}}int mex = 0;while (v[mex] > 0){mex++;}return mex;
}void solve()
{cin >> n;vi a(2 * n);int o1 = -1, o2 = -1;for (int i = 0; i < 2 * n; i++){cin >> a[i];if (a[i] == 0){if (o1 == -1)o1 = i;elseo2 = i;}}int ans1 = f(o1, o1, a, n);int ans2 = f(o2, o2, a, n);int ans3 = f((o1 + o2) / 2, (o1 + o2 + 1) / 2, a, n);cout << max({ans1, ans2, ans3}) << endl;
}