T1
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define ll long long 5 #define dd double 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 9 int n,intemp,maxp; 10 ll sum; 11 dd p[26]; 12 dd f[(1<<20)+10]; 13 int cnt[(1<<20)+10]; 14 15 void dp() 16 { 17 for(int i=0;i<=maxp;++i) 18 for(int k=1;k<=n;++k) 19 if( i&(1<<(k-1)) ) 20 ++cnt[i]; 21 dd temp; 22 for(int num=1;num<=n;++num) 23 for(int j=1;j<=maxp;++j) 24 if(cnt[j]==num) 25 { 26 temp=0; 27 f[j]=1; 28 for(int k=1;k<=n;++k) 29 if( (1<<(k-1))&j ) 30 { 31 temp+=p[k]; 32 f[j]+=f[ j^(1<<(k-1)) ]*p[k]; 33 } 34 f[j]/=temp; 35 } 36 /*f[maxp]=1; 37 for(int k=1;k<=n;++k) 38 f[maxp]+=f[maxp^(1<<(k-1))]*p[k];*/ 39 printf("%.3lf",f[maxp]); 40 41 /*printf(" "); 42 for(int i=0;i<=maxp;++i) 43 printf("i=%d %.3lf ",i,f[i]);*/ 44 45 } 46 47 int main(){ 48 49 scanf("%d",&n); 50 maxp=(1<<n)-1; 51 for(int i=1;i<=n;++i) 52 { 53 scanf("%lf%d",&p[i],&intemp); 54 sum+=intemp; 55 } 56 printf("%lld ",sum); 57 dp(); 58 }
T2
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define ll long long 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 const int N=50006; 9 const int M=100006; 10 inline int minn(int a,int b){return a<b?a:b;} 11 struct son 12 { 13 int v,next,w; 14 }; 15 son a1[M*3]; 16 int first[M*3],e; 17 void addbian(int u,int v,int w) 18 { 19 a1[e].v=v; 20 a1[e].w=w; 21 a1[e].next=first[u]; 22 first[u]=e++; 23 } 24 25 struct son2 26 { 27 int u,v,w; 28 bool friend operator < (son2 a,son2 b) 29 { 30 return a.w<b.w; 31 } 32 }; 33 son2 ji[M*2]; 34 int sum; 35 36 int n,m; 37 int u,o,oo; 38 int dfn[N],low[N],now; 39 int dui[N],cnt; 40 int zhan[N*2],he; 41 bool flag[N*2]; 42 ll ans; 43 44 void tarjan(int x) 45 { 46 dfn[x]=low[x]=++now; 47 zhan[++he]=x;flag[x]=1; 48 for(int i=first[x];i!=-1;i=a1[i].next) 49 { 50 int temp=a1[i].v; 51 if(dfn[temp]==-1) 52 { 53 tarjan(temp); 54 low[x]=minn(low[x],low[temp]); 55 } 56 else 57 if(flag[temp]) 58 low[x]=minn(low[x],dfn[temp]); 59 } 60 if(low[x]==dfn[x]) 61 { 62 ++cnt; 63 int temp; 64 while(1) 65 { 66 temp=zhan[he--]; 67 flag[temp]=0; 68 dui[temp]=cnt; 69 if(temp==x) 70 break; 71 } 72 } 73 } 74 75 int fa[N]; 76 int fin(int x) 77 { 78 if(fa[x]==-1) 79 return x; 80 fa[x]=fin(fa[x]); 81 return fa[x]; 82 } 83 84 bool judge[N]; 85 86 void mn_tree() 87 { 88 int temp1,temp2,sumnow=0; 89 for(int i=1;i<=sum;++i) 90 { 91 temp1=fin(ji[i].u); 92 temp2=fin(ji[i].v); 93 if(temp1!=temp2&&judge[ji[i].v]==0) 94 { 95 fa[temp1]=temp2; 96 ++sumnow; 97 ans+=ji[i].w; 98 judge[ji[i].v]=1; 99 } 100 if(sumnow==cnt-1) 101 break; 102 } 103 } 104 105 void out11() 106 { 107 printf(" "); 108 for(int i=0;i<n;++i) 109 printf("i=%d dui[i]=%d ",i,dui[i]); 110 printf(" "); 111 /*printf("e1=%d ",h[1].e); 112 for(int i=0;i<h[1].e;++i) 113 printf("w=%d ",h[1].a1[i].w);*/ 114 } 115 116 void work() 117 { 118 for(int i=0;i<n;++i) 119 if(dfn[i]==-1) 120 tarjan(i); 121 for(int i=0;i<n;++i) 122 for(int j=first[i];j!=-1;j=a1[j].next) 123 { 124 int temp=a1[j].v; 125 if(dui[i]!=dui[temp]&&dui[temp]!=dui[0]) 126 { 127 ji[++sum]=(son2){dui[i],dui[temp],a1[j].w}; 128 //printf("i=%d u=%d v=%d w=%d ",sum,ji[sum].u,ji[sum].v,ji[sum].w); 129 } 130 } 131 sort(ji+1,ji+1+sum); 132 //out11(); 133 134 mn_tree(); 135 cout<<ans<<endl; 136 } 137 138 int main(){ 139 140 //freopen("1.txt","r",stdin); 141 142 143 while(1) 144 { 145 ans=0; 146 mem(judge,0); 147 mem(dfn,-1);mem(low,0);now=0;mem(dui,0);cnt=0; 148 he=0;mem(flag,0); 149 mem(fa,-1); 150 mem(ji,0);sum=0; 151 mem(first,-1); 152 mem(a1,0);e=0; 153 154 scanf("%d%d",&n,&m); 155 if(n==0||m==0) 156 break; 157 158 for(int i=1;i<=m;++i) 159 { 160 scanf("%d%d%d",&u,&o,&oo); 161 addbian(u,o,oo); 162 } 163 work(); 164 } 165 }
T3
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define ll long long 6 #define dd double 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 using namespace std; 9 const int INF=0x7fffffff; 10 const int N=300006; 11 inline int minn(int a,int b){return a<b?a:b;} 12 inline int maxn(int a,int b){return a>b?a:b;} 13 14 int n; 15 int u,o; 16 int a[N]; 17 int mn[N],mx[N]; 18 ll tong[N*2+1000]; 19 //int mnl[N],mnr[N],mxl[N],mxr[N]; 20 21 ll get(int l,int r) 22 { 23 if(l==r) 24 return 1; 25 int mid=(l+r)>>1,temp1,temp2,temp; 26 ll ans=get(l,mid)+get(mid+1,r); 27 //mem(mn,127);mem(mx,0); 28 mn[mid]=mx[mid]=a[mid]; 29 mn[mid+1]=mx[mid+1]=a[mid+1]; 30 for(int i=mid-1;i>=l;--i) 31 { 32 mn[i]=minn(mn[i+1],a[i]); 33 mx[i]=maxn(mx[i+1],a[i]); 34 } 35 for(int i=mid+2;i<=r;++i) 36 { 37 mn[i]=minn(mn[i-1],a[i]); 38 mx[i]=maxn(mx[i-1],a[i]); 39 } 40 for(int i=l;i<=mid;++i) 41 { 42 temp=i+mx[i]-mn[i]; 43 if(temp<=mid||temp>r) 44 continue; 45 if(mn[i]<mn[temp]&&mx[i]>mx[temp]) 46 ++ans; 47 } 48 for(int i=mid+1;i<=r;++i) 49 { 50 temp=i-(mx[i]-mn[i]); 51 if(temp>mid||temp<l) 52 continue; 53 if(mn[i]<mn[temp]&&mx[i]>mx[temp]) 54 ++ans; 55 } 56 /*printf("nwonwwonwwownw l=%d r=%d mid=%d ",l,r,mid); 57 printf("max= "); 58 for(int i=l;i<=r;++i) 59 printf("%d ",mx[i]); 60 printf(" min= "); 61 for(int i=l;i<=r;++i) 62 printf("%d ",mn[i]); 63 printf(" ");*/ 64 // min | max 65 //printf("now_is_left_min_right_max "); 66 temp1=mid+1;temp2=mid; 67 for(int i=mid;i>=l;--i) 68 { 69 while(mn[temp2+1]>mn[i]&&temp2<r) 70 { 71 ++temp2; 72 ++tong[mx[temp2]-temp2+N]; 73 } 74 while(mx[temp1]<mx[i]&&temp1<=r) 75 { 76 --tong[mx[temp1]-temp1+N]; 77 ++temp1; 78 } 79 if(temp1>r) 80 break; 81 //printf("i=%d temp1=%d temp2=%d jishu=%d ",i,temp1,temp2,jishu); 82 if(temp1<=temp2) 83 { 84 //printf("jishu1=%d ",jishu); 85 ans+=tong[mn[i]-i+N]; 86 } 87 } 88 //mem(tong,0); 89 for(int i=mid-1;i<=r+1;++i) 90 tong[mx[i]-i+N]=0; 91 // max | min 92 //printf("now_is_left_max_right_min "); 93 temp1=mid;temp2=mid+1; 94 for(int i=mid+1;i<=r;++i) 95 { 96 while(mn[temp2-1]>mn[i]&&temp2>l) 97 { 98 --temp2; 99 ++tong[mx[temp2]+temp2]; 100 } 101 while(mx[temp1]<mx[i]&&temp1>=l) 102 { 103 --tong[mx[temp1]+temp1]; 104 --temp1; 105 } 106 if(temp1<l) 107 break; 108 //printf("i=%d temp1=%d temp2=%d jishu=%d ",i,temp1,temp2,jishu); 109 if(temp2<=temp1) 110 { 111 //printf("jishu2=%d ",jishu); 112 ans+=tong[mn[i]+i]; 113 } 114 } 115 //mem(tong,0); 116 for(int i=l-1;i<=mid+1;++i) 117 tong[mx[i]+i]=0; 118 //printf("ans=%d ",ans); 119 return ans; 120 } 121 122 int main(){ 123 124 //freopen("1.txt","r",stdin); 125 //freopen("raid9.in","r",stdin); 126 127 scanf("%d",&n); 128 for(int i=1;i<=n;++i) 129 { 130 scanf("%d%d",&u,&o); 131 a[u]=o; 132 } 133 cout<<get(1,n); 134 }
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 inline void judge(){ 6 freopen("raid.in","r",stdin); 7 freopen("raid.out","w",stdout); 8 } 9 struct info{ 10 int x,num; 11 info operator +(info b){ 12 if(x<b.x)return *this; 13 if(x>b.x)return b; 14 return (info){x,num+b.num}; 15 } 16 info operator +(int b){ 17 return (info){x+b,num}; 18 } 19 }v[200005]; 20 int tag[200005]; 21 void build(int u,int l,int r){ 22 if(l==r){ 23 v[u]=(info){0,1}; 24 return; 25 } 26 int mid=l+((r-l)>>1); 27 build(u<<1,l,mid); 28 build((u<<1)|1,mid+1,r); 29 v[u]=v[u<<1]+v[(u<<1)|1]; 30 } 31 inline void add(int u,int l,int r,int L,int R,int k){ 32 if(L<=l&&r<=R){ 33 tag[u]+=k; 34 v[u].x+=k; 35 return; 36 } 37 int mid=l+((r-l)>>1); 38 if(R<=mid)add(u<<1,l,mid,L,R,k); 39 else if(L>mid)add((u<<1)|1,mid+1,r,L,R,k); 40 else add(u<<1,l,mid,L,R,k),add((u<<1)|1,mid+1,r,L,R,k); 41 v[u]=v[u<<1]+v[(u<<1)|1]+tag[u]; 42 } 43 info query(int u,int l,int r,int L,int R){ 44 if(L<=l&&r<=R)return v[u]; 45 int mid=l+((r-l)>>1); 46 if(R<=mid)return query(u<<1,l,mid,L,R)+tag[u]; 47 else if(L>mid)return query((u<<1)|1,mid+1,r,L,R)+tag[u]; 48 else return query(u<<1,l,mid,L,R)+query((u<<1)|1,mid+1,r,L,R)+tag[u]; 49 } 50 int a[50005],q0[50005],q1[50005]; 51 int main(){ 52 judge(); 53 int n; 54 scanf("%d",&n); 55 for(int i=1;i<=n;i++){ 56 int x,y; 57 scanf("%d%d",&x,&y); 58 a[x]=y; 59 } 60 build(1,1,n); 61 int t0=0,t1=0; 62 q0[0]=q1[0]=0; 63 info ans=(info){0,0}; 64 for(int i=1;i<=n;i++){ 65 while(t0&&a[q0[t0]]<a[i]){ 66 add(1,1,n,q0[t0-1]+1,q0[t0],-a[q0[t0]]); 67 t0--; 68 } 69 while(t1&&a[q1[t1]]>a[i]){ 70 add(1,1,n,q1[t1-1]+1,q1[t1],a[q1[t1]]); 71 t1--; 72 } 73 add(1,1,n,q0[t0]+1,i,a[i]); q0[++t0]=i; 74 add(1,1,n,q1[t1]+1,i,-a[i]); q1[++t1]=i; 75 ans=ans+query(1,1,n,1,i); 76 /* printf("-------%d-------- ",i); 77 printf("%d ",t0); 78 for(int i=1;i<=t0;i++)printf("%d ",i); puts(""); 79 printf("%d ",t1); 80 for(int i=1;i<=t1;i++)printf("%d ",i); puts(""); 81 printf("%d ",ans.num); 82 */ 83 add(1,1,n,1,i,-1); 84 } 85 printf("%d ",ans.num); 86 return 0; 87 }