首页 > 代码库 > CodeForces R285 Div2
CodeForces R285 Div2
落下好多，趁着假期慢慢补吧。。
C. Misha and Forest
因为是一个森林，所以可以先找到所有的叶子节点，然后进行递推即可。开一个队列搞就好了。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <map>#include <set>#include <list>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 1 << 17;int n, xsum[maxn], cnt[maxn];bool vis[maxn];set< pair<int, int> > ans;int main() { scanf("%d", &n); queue<int> q; for(int i = 0; i < n; i++) { scanf("%d%d", &cnt[i], &xsum[i]); if(cnt[i] == 1) { q.push(i); vis[i] = true; } } while(!q.empty()) { int now = q.front(); q.pop(); if(cnt[now] == 0) continue; int u = now, v = xsum[now]; if(u > v) swap(u, v); ans.insert(make_pair(u, v)); xsum[xsum[now]] ^= now; cnt[xsum[now]]--; if(cnt[xsum[now]] == 1 && !vis[xsum[now]]) { q.push(xsum[now]); vis[xsum[now]] = true; } } printf("%d\n", (int)ans.size()); for(auto it = ans.begin(); it != ans.end(); ++it) { printf("%d %d\n", it->first, it->second); } return 0;}D Misha and Permutations Summation
利用康拓展开得到展开之后进行相加，取模之后化简，观察一下很容易就发现做法了。。
中间可能要用一下线段树或者是树状数组来降低一下复杂度。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <map>#include <set>#include <list>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 2e5 + 10;int p1[maxn], p1t[maxn], p2[maxn], p2t[maxn], n;int apt[maxn], ans[maxn];int C[maxn];int lowbit(int x) { return x & (-x);}int init_bit() { memset(C, 0, sizeof(C));}void addv(int pos, int x, int mx) { while(pos <= mx) { C[pos] += x; pos += lowbit(pos); }}int ask(int pos) { int ret = 0; while(pos > 0) { ret += C[pos]; pos -= lowbit(pos); } return ret;}void calc(int arr[], int tar[], int len) { init_bit(); for(int i = 0; i < len; i++) { addv(i + 1, 1, len); } for(int i = len - 1; i >= 0; i--) { tar[i] = ask(arr[i]); addv(arr[i] + 1, -1, len); }}int findk(int val, int mx) { int l = 1, r = mx, ret = 1; while(l <= r) { int mid = (l + r) >> 1; if(ask(mid) >= val) { ret = mid; r = mid - 1; } else { l = mid + 1; } } return ret;}void recalc(int arr[], int tar[], int len) { init_bit(); for(int i = 0; i < len; i++) { addv(i + 1, 1, len); } for(int i = len - 1; i >= 0; i--) { tar[i] = findk(arr[i] + 1, len) - 1; addv(tar[i] + 1, -1, len); }}int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &p1[i]); } reverse(p1, p1 + n); calc(p1, p1t, n); for(int i = 0; i < n; i++) { scanf("%d", &p2[i]); } reverse(p2, p2 + n); calc(p2, p2t, n); for(int i = 0; i < n; i++) { apt[i] += p1t[i] + p2t[i]; apt[i + 1] += apt[i] / (i + 1); apt[i] %= (i + 1); } recalc(apt, ans, n); for(int i = n - 1; i >= 0; i--) { printf("%d ", ans[i]); } puts(""); return 0;}E Misha and Palindrome Degree
这题没想出来，看了题解才会的。。
首先根据题意，很容易想到的是找到所有的最小区间，然后通过容斥原理求解。 并且在这之前可以先进行统计，如果有个数为奇数的字符种类数超过1的话可以直接判不成立。
首先找到最大的i使得 任意k < i 有 a[i] = a[n - i + 1]， 不难发现最小区间必然有一个边界是i 或者 n - i + 1
然后分别固定左边界和右边界，然后来找最小区间的位置。可以发现这里是具有单调性的，所以可以用二分来降低复杂度，二分最小区间的长度。
至于这个区间是否合法可以用O(n)来判断。
对于每一个位置i，有以下几种情况，并且会以以下的次序出现（以左区间端点固定为例），并且设当前区间是[l, r]
首先是 i < l， n - i + 1 > r，此时必然有a[i] = a[n - i + 1]成立，可以不做判断
然后是 r >= i >= l， n - i + 1 > r，或者是i < l，n - i + 1 <= r， 此时区间中必须要有大于等于1个对应字符，否则不成立，这里要在之前做一些统计并且判断
然后是 l <= i <= n - i + 1 <= r，设这里的i为i0，必然有当i < i0外面那部分都是回文的，在进行二分之前判断过字符串必定可以构成回文的，所以此时剩下的字符必然也可以构成回文，所以不必判断。
最后是 r < i <= n - i + 1，这里要判断a[i]是否和a[n - i + 1]相等。
之后容斥原理随意搞即可。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <map>#include <set>#include <list>#include <queue>#include <stack>//using namespace std;typedef long long LL;const int maxn = 1e5 + 10;int a[maxn], n, cl, cr, count[maxn], odd;bool check(int lpos, int rpos) { memset(count, 0, sizeof(count)); for(int i = lpos; i <= rpos; i++) { count[a[i]]++; } for(int i = 1; i < n - i + 1; i++) { bool inL = (i >= lpos && i <= rpos); bool inR = (n - i + 1 >= lpos && n - i + 1 <= rpos); if(inL && inR) continue; else if(inL) { if(--count[a[n - i + 1]] < 0) return false; } else if(inR) { if(--count[a[i]] < 0) return false; } else { if(a[i] != a[n - i + 1]) return false; } } return true;}LL calc(int pos) { int l = pos, r = n, tar; while(l <= r) { int mid = (l + r) >> 1; if(check(pos, mid)) { tar = mid; r = mid - 1; } else { l = mid + 1; } } return (LL)pos * (LL)(n - tar + 1);}int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); count[a[i]]++; } for(int i = 1; i <= n; i++) { if(count[i] & 1) { odd++; } } cl = 1; cr = n; while(cl <= cr && a[cl] == a[cr]) { cl++; cr--; } if(cl > cr) { LL ret = (LL)n * (LL)(n - 1) / 2 + n; printf("%I64d\n", ret); } else if(odd > 1) { puts("0"); } else { LL ret = -(LL)cl * (LL)(n - cr + 1); ret += calc(cl); std::reverse(a + 1, a + 1 + n); ret += calc(cl); printf("%I64d\n", ret); } return 0;}
CodeForces R285 Div2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。