## URAL1009[K-based numbers]

N位中有i个取0，且不连续，不前导
i个0:
0一共有(N-i)!/(((N-i*2)!)*(i!))种插法(明显N-i>=i，即N>=i*2)

(N-i)!/(((N-i*2)!)*(i!))就是传说中的C(N-i,i)
N-i个非0:
他们一共有(K-1)^(N-i)种可能

CEDE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-13

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

int N,K;

public:

Application()

{

cin>>N>>K;

}

int run()

{

/*

N位中有i个取0，且不连续，不前导

i0:

0一共有(N-i)!/(((N-i*2)!)*(i!))种插法(明显N-i>=i，即N>=i*2)

N-i个非0:

他们一共有(K-1)^(N-i)种可能

要求的就是sum{(N-i)!/(((N-i*2)!)*(i!))*((K-1)^(N-i)), 0<=i<=N/2}

*/

for (int i=0;i*2<=N;i++)

{

long long int a=1,b=1,c=1,d=1;

for (int j=1;j<=N-i;j++)

a*=j;

for (int j=1;j<=N-i*2;j++)

b*=j;

for (int j=1;j<=i;j++)

c*=j;

for (int j=1;j<=N-i;j++)

d*=K-1;

}

return 0;

}

};

int main()

{

Application app;

return app.run();

}

## URAL1008[Image encoding]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-12

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

using std::getline;

class ApplicationNumberToString

{

static const int oo=~(1<<31);

int n;

pair<int,int> LB;

vector<pair<pair<int,int>,bool> > dot;

public:

{

LB=make_pair(oo,oo);

for (int i=0;i<n;i++)

{

pair<int,int> get;

cin>>get.first>>get.second;

dot.push_back(make_pair(get,false));

if (get<LB) LB=get;

}

}

int run()

{

queue<pair<int,int> > q;

q.push(LB);

for (int i=0;i<dot.size();i++)

if (dot[i].first==q.front())

dot[i].second=true;

cout<<LB.first<<” “<<LB.second<<endl;

while (!q.empty())

{

int x=q.front().first;

int y=q.front().second;

q.pop();

#define if_find_print(point,flag)\

for (int i=0;i<dot.size();i++)\

if ((dot[i].first==point)&&(!dot[i].second))\

{\

dot[i].second=true;\

q.push(point);\

cout<<flag;\

}

if_find_print(make_pair(x+1,y),’R’);

if_find_print(make_pair(x,y+1),’T’);

if_find_print(make_pair(x-1,y),’L’);

if_find_print(make_pair(x,y-1),’B’);

cout<<char(q.empty()?’.’:’,’)<<endl;

#undef if_find_print

}

return 0;

}

};

class ApplicationStringToNumber

{

pair<int,int> LB;

vector<pair<int,int> > dot;

public:

{

dot.push_back(LB);

string description;

int counter=0;

while (cin>>description)

{

for (int i=0;i<description.length()-1;i++)

{

if (description[i]==’R’)

dot.push_back(make_pair(dot[counter].first+1,dot[counter].second));

if (description[i]==’T’)

dot.push_back(make_pair(dot[counter].first,dot[counter].second+1));

if (description[i]==’L’)

dot.push_back(make_pair(dot[counter].first-1,dot[counter].second));

if (description[i]==’B’)

dot.push_back(make_pair(dot[counter].first,dot[counter].second-1));

}

counter++;

}

}

int run()

{

sort(dot.begin(),dot.end());

cout<<dot.size()<<endl;

for (int i=0;i<dot.size();i++)

cout<<dot[i].first<<” “<<dot[i].second<<endl;

return 0;

}

};

class Application

{

bool NumberToString()

{

string first_line;

getline(cin,first_line);

stringstream sin_LB(first_line);

stringstream sin_n(first_line);

}

public:

int run()

{

if (NumberToString())

{

return app.run();

}

else

{

return app.run();

}

}

};

int main()

{

Application app;

return app.run();

}

## URAL1007[Code words]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-12

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <cassert>

//using std::assert;

class Application

{

public:

int run()

{

int n;

cin>>n;

string word;

while (cin>>word)

{

int sum;

if (word.length()==n)

{

sum=0;

for (int i=0;i<n;i++)

sum+=(word[i]==’1′?i+1:0);

if (sum%(n+1)==0) cout<<word<<endl;

else

{

for (int i=0;i<n;i++)

if ((word[i]==’1′)&&(((sum-(i+1))%(n+1))==0))

{

word[i]=’0′;

break;

}

cout<<word<<endl;

}

}

if (word.length()==n+1)

{

int insert;

for (insert=0;insert<n+1;insert++)

{

sum=0;

for (int i=0;i<n+1;i++)

if (word[i]==’1′)

{

if (i<insert) sum+=i+1;

else if (i>insert) sum+=i+11;

}

if (sum%(n+1)==0) break;

}

for (int i=0;i<n+1;i++)

if (i!=insert) cout<<word[i];

cout<<endl;

}

if (word.length()==n-1)

{

int remove;

bool is0;

for (remove=0;remove<n;remove++)

{

sum=0;

for (int i=0;i<n-1;i++) if (word[i]==’1′)

{

if (i<remove) sum+=i+1;

else if (i>=remove) sum+=i+1+1;

}

if (sum%(n+1)==0)

{

is0=true;

break;

}

if ((sum+remove+1)%(n+1)==0)

{

is0=false;

break;

}

}

for (int i=0;i<n;i++)

{

if (i==remove) cout<<char(is0?’0′:’1′);

if (i<n-1)cout<<word[i];

}

cout<<endl;

}

}

return 0;

}

};

int main()

{

Application app;

return app.run();

}

## URAL1006[Square frames]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-11

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <vector>

using std::vector;

#include <string>

//using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <cassert>

//using std::assert;

class Application

{

typedef unsigned char uc;

static const int W=50,H=20;

static const uc LU=218,//Left upper corner

RU=191,//Right upper corner

LB=192,//Left bottom corner

RB=217,//Right bottom corner

VE=179,//Vertical (left and right) border line

HO=196,//Horizontal (top and bottom) border line

DO=46,//Dot

CO=0;//Cover

uc pic[H][W];

public:

Application()

{

for (int i=0;i<H;i++)

for (int j=0;j<W;j++)

cin>>pic[i][j];

}

int run()

{

bool update=true;

while (update)

{

/*

cout<<“updating…”<<endl;

for (int x=0;x<H;x++)

{

for (int y=0;y<W;y++)

{

switch(pic[x][y])

{

case LU:cout<<‘/’;break;

case RU:cout<<‘\\’;break;

case LB:cout<<‘\\’;break;

case RB:cout<<‘/’;break;

case VE:cout<<‘|’;break;

case HO:cout<<‘-‘;break;

case DO:cout<<‘.’;break;

case CO:cout<<‘ ‘;break;

}

}

cout<<endl;

}

*/

update=false;

for (int x=0;x<H;x++)

for (int y=0;y<W;y++)

if (pic[x][y]==CO||pic[x][y]==LU)

for (int a=2;a<=H;a++)

if ((pic[x+a-1][y]==CO||pic[x+a-1][y]==LB)

&&(pic[x][y+a-1]==CO||pic[x][y+a-1]==RU)

&&(pic[x+a-1][y+a-1]==CO||pic[x+a-1][y+a-1]==RB))

{

#define impossibleHO(x,y) ((x>=H)or(y>=W)or((pic[x][y]!=CO)&&(pic[x][y]!=HO)))

#define impossibleVE(x,y) ((x>=H)or(y>=W)or((pic[x][y]!=CO)&&(pic[x][y]!=VE)))

bool ispossible=true;

bool L=false,R=false,U=false,B=false;

if (pic[x][y]==LU) L=U=true;

if (pic[x+a-1][y]==LB) L=B=true;

if (pic[x][y+a-1]==RU) R=U=true;

if (pic[x+a-1][y+a-1]==RB) R=B=true;

for (int i=1;i<a-1;i++)

{

if (impossibleHO(x,y+i)

||impossibleHO(x+a-1,y+i)

||impossibleVE(x+i,y)

||impossibleVE(x+i,y+a-1))

{

ispossible=false;

break;

}

if (pic[x][y+i]==HO) U=true;

if (pic[x+a-1][y+i]==HO) B=true;

if (pic[x+i][y]==VE) L=true;

if (pic[x+i][y+a-1]==VE) R=true;

}

#define cover(x,y) pic[x][y]=CO;

if (ispossible&&(L||R||U||B))

{

for (int i=0;i<a;i++)

{

cover(x,y+i);

cover(x+a-1,y+i);

cover(x+i,y);

cover(x+i,y+a-1);

}

update=true;

//cout<<y<<” “<<x<<” “<<a<<endl;

}

#undef impossibleHO

#undef impossibleVE

#undef cover

}

}

{

}

return 0;

}

};

int main()

{

Application app;

return app.run();

}

## URAL1005[Stone pile]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-10

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <cassert>

//using std::assert;

class Application

{

static const int oo=~(1<<31);

int N;

vector<int> W;

int total;

public:

Application()

:total(0)

{

cin>>N;

W.resize(N);

for (int i=0;i<N;i++)

{

cin>>W[i];

total+=W[i];

}

}

int run()

{

vector<bool> f(total+1,false);

f[0]=true;

for (int k=0;k<N;k++)

for (int i=total;i>=W[k];i–)

f[i]=f[i] or f[i-W[k]];

for (int i=(total+1)/2;i<=total;i++)

{

if (f[i])

{

break;

}

}

return 0;

}

};

int main()

{

Application app;

return app.run();

}

## URAL1004[Sightseeing trip]

Floyd求最小环。

CODE:

/*
PROGRAM: \$PROGRAM
AUTHOR: Su Jiao
DATE: 2010-3-10
DESCRIPTION:
\$DESCRIPTION
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <map>
//using std::map;
#include <stack>
using std::stack;
#include <queue>
using std::queue;
using std::pair;
using std::make_pair;
#include <cassert>
//using std::assert;

class Question
{

static const int oo=1<<29;
vector<vector<
int> > map;

void print(stack<int>& s,vector<vector<int> >& mid,int u,int v)
{

if (mid[u][v]<0)
{

if (s.top()!=u) s.push(u);

if (s.top()!=v) s.push(v);
}

else
{
print(s,mid,u,mid[u][v]);
print(s,mid,mid[u][v],v);
}
}

public:

{

int N,M;
cin>>N;

if (N==-1) return false;
cin>>M;

map.resize(N,vector<
int>(N,oo));

for (int i=0;i<M;i++)
{

int u,v,l;
cin>>u>>v>>l;
u–;
v–;

//assert(u<N&&v<N);
if (map[u][v]>l) map[u][v]=l;

if (map[v][u]>l) map[v][u]=l;
}

return true;
}

void solve()
{
vector<vector<
int> > dist,mid;

dist=map;
mid.resize(dist.size(),vector<
int>(dist.size(),-1));

int min=oo;

int min_i,min_j,min_k;

for (int k=0;k<dist.size();k++)
{

for (int i=0;i<k;i++)

for (int j=i+1;j<k;j++)
{

//assert(i!=j&&i!=k&&j!=k);
if (min>(dist[j][i]+map[i][k]+map[k][j]))
{
min=dist[j][i]+map[i][k]+map[k][j];
min_i=i;
min_j=j;
min_k=k;
}
}

for (int i=0;i<dist.size();i++)

for (int j=0;j<dist.size();j++)

if (dist[i][j]>dist[i][k]+dist[k][j])
dist[i][j]=dist[i][k]+dist[k][j];
}

if (min<oo)
{
dist=map;
dist[min_i][min_k]=dist[min_k][min_i]=oo;
dist[min_j][min_k]=dist[min_k][min_j]=oo;

for (int k=0;k<dist.size();k++)

for (int i=0;i<dist.size();i++)

for (int j=0;j<dist.size();j++)

if (dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
mid[i][j]=k;
}

stack<
int> s;

s.push(min_k);
print(s,mid,min_i,min_j);

for (;;)
{
cout<<s.top()+
1;
s.pop();

if (s.empty())
{
cout<<endl;

break;
}

else cout<<” “;
}
}

else cout<<“No solution.”<<endl;

map.clear();
}
};

class Application
{

public:
Application()
{
}

int run()
{
Question q;

return 0;
}
};

int main()
{
Application app;

return app.run();
}

## URAL1003[Parity]

(又见POJ1733,VIJOS1112)

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-9

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <cstring>

using std::memset;

#include <string>

using std::string;

#include <vector>

using std::vector;

using std::pair;

using std::make_pair;

#include <map>

using std::map;

class Question

{

int length;

int Q;

map<int,pair<int,bool> > record_l,record_r;

bool dfs_judge_l(int l,int r,bool isEven)

{

map<int,pair<int,bool> >::iterator it;

if ((it=record_l.find(l))!=record_l.end())

{

if (it->second.first==r)

return it->second.second==isEven;

else if (it->second.first>r)

{

//it->first to it->second.first it->second.second

record_l[r+1]=make_pair(it->second.first,isEven xor it->second.second);

//it->first to r isEven

it->second=make_pair(r,isEven);

return dfs_judge_r(r+1,record_l[r+1].first,record_l[r+1].second);

}

else

{

return dfs_judge_l(it->second.first+1,r,isEven xor it->second.second);

}

}

else

{

record_l[l]=make_pair(r,isEven);

return true;

}

}

bool dfs_judge_r(int l,int r,bool isEven)

{

map<int,pair<int,bool> >::iterator it;

if ((it=record_r.find(r))!=record_r.end())

{

if (it->second.first==l)

return it->second.second==isEven;

else if (it->second.first<l)

{

//it->second.first to it->first it->second.second

record_r[l-1]=make_pair(it->second.first,isEven xor it->second.second);

//l to it->first isEven

it->second=make_pair(l,isEven);

return dfs_judge_l(record_r[l-1].first,l-1,record_r[l-1].second);

}

else

{

return dfs_judge_r(l,it->second.first-1,isEven xor it->second.second);

}

}

else

{

record_r[r]=make_pair(l,isEven);

return true;

}

}

public:

{

cin>>length;

if (length==-1) return false;

cin>>Q;

return true;

}

void solve()

{

int l,r;

{

}

record_l.clear();

record_r.clear();

}

};

class Application

{

public:

int run()

{

Question q;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

## URAL1002[Phone numbers]

f[i]=min{f[j],从j到i可以被匹配}+1

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-8

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <cstring>

using std::memset;

#include <string>

using std::string;

#include <vector>

using std::vector;

#include <stack>

using std::stack;

class Question

{

int get_num[256];

string number;

vector<string> dictionary;

bool match(int f,int t,int id)

{

if (t-f!=dictionary[id].length()) return false;

else

{

for (int i=f;i<t;i++)

if (get_num[dictionary[id][i-f]]!=(number[i]-‘0’)) return false;

return true;

}

}

public:

Question()

{

get_num[‘a’]=2;

get_num[‘b’]=2;

get_num[‘c’]=2;

get_num[‘d’]=3;

get_num[‘e’]=3;

get_num[‘f’]=3;

get_num[‘g’]=4;

get_num[‘h’]=4;

get_num[‘i’]=1;

get_num[‘j’]=1;

get_num[‘k’]=5;

get_num[‘l’]=5;

get_num[‘m’]=6;

get_num[‘n’]=6;

get_num[‘o’]=0;

get_num[‘p’]=7;

get_num[‘q’]=0;

get_num[‘r’]=7;

get_num[‘s’]=7;

get_num[‘t’]=8;

get_num[‘u’]=8;

get_num[‘v’]=8;

get_num[‘w’]=9;

get_num[‘x’]=9;

get_num[‘y’]=9;

get_num[‘z’]=0;

}

{

dictionary.clear();

cin>>number;

if (number==“-1”) return false;

int n;

cin>>n;

while (n–)

{

string get;

cin>>get;

dictionary.push_back(get);

}

return true;

}

void solve()

{

int* f=new int[number.length()+1];

int* pre=new int[number.length()+1];

int* use=new int[number.length()+1];

memset(f,0x7f,sizeof(int)*(number.length()+1));

f[0]=0;

for (int k=1;k<=number.length();k++)

for (int i=0;i<k;i++)

for (int j=0;j<dictionary.size();j++)

if (match(i,k,j))

if (f[k]>f[i]+1)

{

f[k]=f[i]+1;

pre[k]=i;

use[k]=j;

}

if (f[number.length()]>number.length()) cout<<“No solution.”<<endl;

else

{

stack<int> s;

s.push(number.length());

while (pre[s.top()])

s.push(pre[s.top()]);

for (;!s.empty();)

{

cout<<dictionary[use[s.top()]]<<char(s.size()>1?’ ‘:’\n’);

s.pop();

}

}

delete[] f;

}

};

class Application

{

public:

Application()

{

}

int run()

{

Question q;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

## URAL1001[Reverse root]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-8

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <cstring>

using std::memset;

#include <stack>

using std::stack;

#include <cmath>

using std::sqrt;

#include <iomanip>

using std::setiosflags;

using std::setprecision;

class Application

{

stack<long long int> A;

public:

Application()

{

long long int input;

while (cin>>input)

A.push(input);

}

int run()

{

long long int pop;

cout<<setiosflags(std::ios::fixed)<<setprecision(4);

while (!A.empty())

{

pop=A.top();

A.pop();

cout<<sqrt(double(pop))<<endl;

}

return 0;

}

};

int main()

{

Application app;

return app.run();

}

## URAL1000[A+B Problem]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-8

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <cstring>

using std::memset;

class Application

{

int a,b;

public:

Application()

{

cin>>a>>b;

}

int run()

{

cout<<(a+b)<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}