网站建设和维护合同书,seo资讯,网站上传后,wordpress同时使用两个主题2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 15879 Solved: 7205[Submit][Status][Discuss]Description 作为一个生活散漫的人#xff0c;小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天#xff0c;小… 2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 15879 Solved: 7205[Submit][Status][Discuss] Description 作为一个生活散漫的人小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天小Z再也无法忍受这恼人的找袜子过程于是他决定听天由命……具体来说小Z把这N只袜子从1到N编号然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双甚至不在意两只袜子是否一左一右他却很在意袜子的颜色毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z他有多大的概率抽到两只颜色相同的袜子。当然小Z希望这个概率尽量高所以他可能会询问多个(L,R)以方便自己选择。 Input 输入文件第一行包含两个正整数N和M。N为袜子的数量M为小Z所提的询问的数量。接下来一行包含N个正整数Ci其中Ci表示第i只袜子的颜色相同的颜色用相同的数字表示。再接下来M行每行两个正整数LR表示一个询问。 Output 包含M行对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1否则输出的A/B必须为最简分数。详见样例 Sample Input 6 4 1 2 3 3 3 2 2 6 1 3 3 5 1 6 Sample Output 2/5 0/1 1/1 4/15 【样例解释】 询问1共C(5,2)10种可能其中抽出两个2有1种可能抽出两个3有3种可能概率为(13)/104/102/5。 询问2共C(3,2)3种可能无法抽到颜色相同的袜子概率为0/30/1。 询问3共C(3,2)3种可能均为抽出两个3概率为3/31/1。 注上述C(a, b)表示组合数组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。 【数据规模和约定】 30%的数据中 N,M ≤ 5000 60%的数据中 N,M ≤ 25000 100%的数据中 N,M ≤ 500001 ≤ L R ≤ NCi ≤ N。 代码如下 #includebits/stdc.h
using namespace std;
#define IO ios::sync_with_stdio(false),cin.tie(0);
const int maxn 120;
int a[maxn];
int sz;
long long gcd(long long x,long long y){while(y0){long long tmpy;yx%y;xtmp;}return x;
}
long long comb(long long x){return x*(x-1)/2;
}
struct node{int l,r,id;bool operator (const node x) const {return (l-1)/sz(x.l-1)/sz?rx.r:(l-1)/sz(x.l-1)/sz;}
}Q[maxn];
long long ans[maxn][2];
long long flag[maxn];int n,m,k;int L1,R0;
long long Ans0;
void add(int x){Ans-comb(flag[a[x]]);flag[a[x]];Anscomb(flag[a[x]]);
}
void del(int x){Ans-comb(flag[a[x]]);flag[a[x]]--;Anscomb(flag[a[x]]);
}int main(){scanf(%d%d,n,m);szsqrt(n);for(int i1;in;i){scanf(%d,a[i]);}for(int i1;im;i){scanf(%d%d,Q[i].l,Q[i].r);Q[i].idi;}sort(Q1,Q1m);flag[0]1;for(int i1;im;i){while(LQ[i].l){del(L);}while(LQ[i].l){add(--L);}while(RQ[i].r){add(R);}while(RQ[i].r){del(R--);}if(Q[i].lQ[i].r){ans[Q[i].id][0]0;ans[Q[i].id][1]1;continue;}long long tcomb((long long)(Q[i].r-Q[i].l1));long long gggcd(t,Ans);ans[Q[i].id][0]Ans/gg;ans[Q[i].id][1]t/gg; }for(int i1;im;i){if(ans[i][0]0){printf(0/1\n);}else printf(%lld/%lld\n,ans[i][0],ans[i][1]);}
} View Code 我跑了3000ms 然后 某屁屁黄就嘲讽我 说他只用了800ms 此处贴上他的代码也不是很懂他为什么就比我快男人那么快真的好吗滴滴滴下车 代码如下 #include set
#include map
#include queue
#include stack
#include cmath
#include bitset
#include cstdio
#include string
#include vector
#include cstdlib
#include cstring
#include iostream
#include algorithm
using namespace std;typedef long long ll;
typedef unsigned long long ull;#define bug printf(*********\n);
#define FIN freopen(in.txt, r, stdin);
#define debug(x) cout[x] endl;
#define IO ios::sync_with_stdio(false),cin.tie(0);const double eps 1e-8;
const int mod 1e9 7;
const int maxn 5e4 7;
const double pi acos(-1);
const int inf 0x3f3f3f3f;
const ll INF 0x3f3f3f3f3f3f3f3f;int n, m, block;
ll sum;
int a[maxn], cnt[maxn];struct node {int l, r, id;ll ans1, ans2;bool operator (const node x) const {return (l - 1) / block (x.l - 1) / block ? r x.r : (l - 1) / block (x.l - 1) / block;}
}ask[maxn];void update (int p, int val) {sum - cnt[p] * cnt[p];cnt[p] val;sum cnt[p] * cnt[p];
}ll gcd(ll a, ll b) {return b 0 ? a : gcd(b, a % b);
}int main() {//FIN;while(~scanf(%d%d, n, m)) {block sqrt(n);for(int i 1; i n; i) {scanf(%d, a[i]);}for(int i 1; i m; i) {scanf(%d%d, ask[i].l, ask[i].r);ask[i].id i;}sort(ask 1, ask m 1);for(int i 1, l 1, r 0; i m; i) {for(; r ask[i].r; r) update(a[r 1], 1);for(; r ask[i].r; r--) update(a[r], -1);for(; l ask[i].l; l) update(a[l], -1);for(; l ask[i].l; l--) update(a[l - 1], 1);if(ask[i].l ask[i].r) {ask[ask[i].id].ans1 0, ask[ask[i].id].ans2 1;continue;}ll k1 sum - (ask[i].r - ask[i].l 1);ll k2 (long long) (ask[i].r - ask[i].l 1) * (ask[i].r - ask[i].l);ll gg gcd(k1, k2);ask[ask[i].id].ans1 k1 / gg;ask[ask[i].id].ans2 k2 / gg;}for(int i 1; i m; i) {if(ask[i].ans1 0) {printf(0/1\n);} else {printf(%lld/%lld\n, ask[i].ans1, ask[i].ans2);}}}return 0;
} View Code 转载于:https://www.cnblogs.com/buerdepepeqi/p/9452278.html
