2038: [2009國家集訓隊]小Z的襪子(hose)

Time Limit:?20 Sec??Memory Limit:?259 MB
Submit:?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行，每行兩個正整數L，R表示一個詢問。

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種可能，概率為(1+3)/10=4/10=2/5。
詢問2：共C(3,2)=3種可能，無法抽到顏色相同的襪子，概率為0/3=0/1。
詢問3：共C(3,2)=3種可能，均為抽出兩個3，概率為3/3=1/1。
注：上述C(a, b)表示組合數，組合數C(a, b)等價于在a個不同的物品中選取b個的選取方案數。
【數據規模和約定】
30%的數據中 N,M ≤ 5000；
60%的數據中 N,M ≤ 25000；
100%的數據中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。
代碼如下： #include<bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false),cin.tie(0); const int maxn = 1<<20; int a[maxn]; int sz; long long gcd(long long x,long long y){while(y>0){long long tmp=y;y=x%y;x=tmp;}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?r<x.r:(l-1)/sz<(x.l-1)/sz;} }Q[maxn]; long long ans[maxn][2]; long long flag[maxn];int n,m,k;int L=1,R=0; long long Ans=0; void add(int x){Ans-=comb(flag[a[x]]);flag[a[x]]++;Ans+=comb(flag[a[x]]); } void del(int x){Ans-=comb(flag[a[x]]);flag[a[x]]--;Ans+=comb(flag[a[x]]); }int main(){scanf("%d%d",&n,&m);sz=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=m;i++){scanf("%d%d",&Q[i].l,&Q[i].r);Q[i].id=i;}sort(Q+1,Q+1+m);flag[0]=1;for(int i=1;i<=m;i++){while(L<Q[i].l){del(L++);}while(L>Q[i].l){add(--L);}while(R<Q[i].r){add(++R);}while(R>Q[i].r){del(R--);}if(Q[i].l==Q[i].r){ans[Q[i].id][0]=0;ans[Q[i].id][1]=1;continue;}long long t=comb((long long)(Q[i].r-Q[i].l+1));long long gg=gcd(t,Ans);ans[Q[i].id][0]=Ans/gg;ans[Q[i].id][1]=t/gg; }for(int i=1;i<=m;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

總結

以上是生活随笔為你收集整理的2038: [2009国家集训队]小Z的袜子(hose)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。