Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

线段树+高精度0ms1A

Posted by KatrineYang at 2016-09-22 11:44:44 on Problem 1349
#include <iostream>
#include <stdio.h>
using namespace std;

void buildTree(int s, int e, int *src, int numb){
	src[numb] = e-s+1;
	if(s==e) return;
	int mid = (s+e)/2;
	buildTree(s,mid,src,2*numb+1);
	buildTree(mid+1,e,src,2*numb+2);
}

void del(int s, int e, int *src, int numb, int pos){
	src[numb]--;
	if(s==e) return;
	int mid = (s+e)/2;
	if(pos<=mid) del(s,mid,src,2*numb+1,pos);
	else del(mid+1,e,src,2*numb+2,pos);
}

int query(int qs, int qe, int s, int e, int *src, int numb){
	if(qe<qs) return 0;
	if(qs==s && qe==e) return src[numb];
	int mid = (s+e)/2;
	if(qe<=mid) return query(qs,qe,s,mid,src,2*numb+1);
	if(qs>mid) return query(qs,qe,mid+1,e,src,2*numb+2);
	return query(qs,mid,s,mid,src,2*numb+1)+query(mid+1,qe,mid+1,e,src,2*numb+2);
}

int main() {
	char fei, ks;
	bool dyg = 1;
	while(1){
		cin >> ks;
		if(ks == '-') {
			cout << endl;
			return 0;
		}
		if(!dyg) cout << ",";
		dyg = 0;
		int n;
		cin >> n;
		cin >> fei >> fei;
		int lst[55];
		for(int i = 1; i <= n; i++){
			cin >> lst[i] >> fei;
		}
		//for(int i = 1; i <= n; i++) cout << lst[i] << " "; cout << endl;
		cin >> fei;
		if(n==1) {
			cout << 1;
			continue;
		}
		int xds[500];
		buildTree(1, n, xds, 0);
		int q[500];
		for(int i = 1; i < n; i++){
			q[i] = query(1,lst[i]-1,1,n,xds,0);
			del(1,n,xds,0,lst[i]);
		}
		//for(int i = 1; i < n; i++) cout << q[i] << " "; cout << endl;
		int gjd[500] = {0};
		int ws = 1;
		for(int i = 1; i < n; i++){
			gjd[0] += (q[i] + (i==n-1 ? 1 : 0));
			if(n-i-1){
				for(int j = 0; j < ws; j++){
					gjd[j] *= (n-i);
				}
			}
			int carry = 0;
			for(int j = 0; j < ws; j++){
				gjd[j] += carry;
				carry = gjd[j]/10;
				gjd[j]%=10;
			}
			while(carry){
				gjd[ws] = carry;
				carry = gjd[ws]/10;
				gjd[ws]%=10;
				ws++;
			}
		}
		for(int i = ws-1; i >= 0; i--){
			cout << gjd[i];
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator