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

拿这题练treap splay什么的不错。。朴素BST也可以。。

Posted by fjxmyzwd at 2011-02-14 19:59:23
/*
/ Problem : POJ 1002
/ Author  : FJXMYZ Wu Di (leap.ahead)
/ Date    :
*/

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <deque>
#include <cassert>
#include <ctime>
#include <bitset>
#include <climits>

using namespace std;

#define repeach(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define rep(i, a, n) for (register int i = (a); i <= (int)n; ++i)
#define ll long long
#define pb push_back
#define size(array,type) sizeof(array)/sizeof(type)

const int maxn = 100001;
bool flag = false;
int n;

int yingshe[26] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,1,7,7,8,8,8,9,9,9,1};

struct Treap
{
    int root, cnt;
    struct node
    {
      int left, right, value,fix, weight;
    }tr[maxn];

    void Init()
    {
        root = -1;
        cnt = 0;
    }

	void rot_l(int &x)
	{
		int y=tr[x].right;
		tr[x].right=tr[y].left;
		tr[y].left=x;
		x=y;
	}

	void rot_r(int &x)
	{
		int y=tr[x].left;
		tr[x].left=tr[y].right;
		tr[y].right=x;
		x=y;
	}

    void Insert(int &now, int num)
    {
        if(now == -1)
        {
            now = ++cnt;
            tr[now].value = num;
            tr[now].left=tr[now].right = -1;
            tr[now].weight = 1;
            tr[now].fix = rand()%1000000007;
            return;
        }
        if(tr[now].value == num)
        {
            tr[now].weight++;
            return;
        }
        if(tr[now].value < num)
        {
            Insert(tr[now].right, num);
            if(tr[tr[now].right].fix > tr[now].fix) rot_l(now);
        }
        else
        {
            Insert(tr[now].left, num);
            if(tr[tr[now].left].fix > tr[now].fix) rot_r(now);
        }
    }

    void Zero(int x, int t)
    {
        if(t==4){
         if(x<10) printf("000");
         else if(x<100) printf("00");
         else if(x<1000) printf("0");
         printf("%d",x);
        }
        if(t==3){
           if(x<10) printf("00");
           else if(x<100) printf("0");
           printf("%d",x);
        }
    }

    void Print(int &now)
    {
        if(tr[now].left!=-1) Print(tr[now].left);
        if(tr[now].weight>1)
        {
         flag=true;
         int f = 1, s1 = tr[now].value, s2 = 0, t;
         for(int i = 1; i <= 4; i++)
         {
             t = s1 % 10;
             s1 /= 10;
             s2 += f*t;
             f*=10;
         }
         Zero(s1,3);
         printf("-");
         Zero(s2,4);
         printf(" %d\n",tr[now].weight);
        }
        if(tr[now].right!=-1) Print(tr[now].right);
    }
}treap;

int get(string s)
{
    for(register int i = 0; i < min(7,(int)s.length()); ++i)
    {
        if('0'<=s[i]&&s[i]<='9') continue;
        if(s[i]=='-')
        {
            for(register int j = i; j < (int)s.length() - 1; ++j)
            {
                swap(s[j],s[j+1]);
            }
            i--;
            continue;
        }
        s[i]=yingshe[s[i]-'A']+'0';
    }

    int ret = 0;
    for(register int i = 0; i < 7; i++) ret = ret*10 + s[i] - '0';
    return ret;
}

int main()
{
    srand(time(0));
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    treap.Init();
    scanf("%d",&n);
    string s;
    int t;
    rep(i,1,n)
    {
        cin >> s;
        t = get(s);
        //printf("%d\n",t);
        treap.Insert(treap.root, t);
    }
    treap.Print(treap.root);
    if(!flag) printf("No duplicates.\n");
    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