| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
拿这题练treap splay什么的不错。。朴素BST也可以。。/*
/ 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator