首页 > 代码库 > bzoj 2038 小Z的袜子
bzoj 2038 小Z的袜子
好久没写题解了=_= ，整个暑假就没写过，还是决定写写吧，所以挑了这道大水题。
这是标准的莫队算法的问题，但由于可能数据水还是别的什么原因，不用曼哈顿最小生成树也可以过。具体就是按询问区间的左端点分块， 块内按右端点排序，然后暴力……
真的是暴力，太暴力了，直到AC以后我才相信这么暴力真的可以在O(N^1.5)的时间复杂度内过掉。
块内具体就是右端点递增，左端点由于在块内并不是有序的，所以左端点就会晃来晃去，真是太暴力了……
上代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define N 50001using namespace std;int n, m, kuai;struct sss{ int l, r; int num, ku;}ask[N];struct ss{ long long first, second;}ans[N];int colorcount[N], color[N];bool cmp(sss x, sss y) { return x.ku == y.ku ? x.r < y.r : x.ku < y.ku; }long long gcd(long long x, long long y){ if (!y) return x; return gcd(y, x%y);}int main(){ scanf("%d%d", &n, &m); kuai = (int)sqrt(n+0.5); for (int i = 1; i <= n; ++i) scanf("%d", &color[i]); for (int i = 1; i <= m; ++i) { scanf("%d%d", &ask[i].l, &ask[i].r); ask[i].num = i; ask[i].ku = ask[i].l / kuai + 1; } sort(ask+1, ask+1+m, cmp); int nowkuai = 0, nowr, nowl; long long nowans; for (int i = 1; i <= m; ++i) { if (ask[i].ku != nowkuai) { nowkuai = ask[i].ku; nowans = 0; nowl = ask[i].l; nowr = nowl-1; for (int j = 1; j <= n; ++j) colorcount[j] = 0; } for (int j = nowl; j < ask[i].l; ++j) { colorcount[color[j]] --; nowans -= colorcount[color[j]]; } for (int j = nowl-1; j >= ask[i].l; --j) { colorcount[color[j]] ++; nowans += colorcount[color[j]] - 1; } for (int j = nowr+1; j <= ask[i].r; ++j) { colorcount[color[j]] ++; nowans += colorcount[color[j]] - 1; } nowl = ask[i].l; nowr = ask[i].r; long long x = ask[i].r - ask[i].l + 1; x = (long long)x*(long long)(x-1)/2; long long d = gcd(x, nowans); if (nowans) { ans[ask[i].num].first = nowans/d; ans[ask[i].num].second = x/d; } else { ans[ask[i].num].first = 0; ans[ask[i].num].second = 1; } } for (int i = 1; i <= m; ++i) printf("%lld/%lld\n", ans[i].first, ans[i].second); return 0;}
bzoj 2038 小Z的袜子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。