URAL1104[Don’t Ask Woman about Her Age]

数学题,需要知道(a*k^n)mod(k-1)=a,即sum{a[i]*k^i}mod(k-1)=sum{a[i]}。
其实不知道也可以做。
继续练习Java。

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-18
DESCRIPTION:
$DESCRIPTION
*/


import
java.io.*;
import
java.util.*;

public class
Ural {
public static
void main(String args[])
{

new
Ural();
}

public
int c2i(char c)
{

if
('A'<=c&&c<='Z') return (int)(c-'A')+10;
else return
(int)(c-'0');
}

public
Ural()
{

Scanner
cin=new Scanner(new BufferedInputStream(System.in));
String
s=cin.nextLine();
int
sum=0;
int
mink=2;
for
(int i=0;i<s.length();i++)
{

sum+=c2i(s.charAt(i));
if
(c2i(s.charAt(i))>=mink) mink=c2i(s.charAt(i))+1;
}

for
(int k=mink;k<=36;k++)
{

if
(sum%(k-1)==0)
{

System
.out.println(k);
return
;
}
}

System
.out.println("No solution.");
}
}

URAL1103[Pencils and Circles]

数学题。
首先可以证明有解当且仅当N不小于3且为奇数。
证明:
若N为偶数或N小于3,显然无解。
若N为不小于3的奇数,那么可以用下面的方法构造一个可行解。
首先选则两点(记为A,B),使得除这两点以外的所有点都在直线AB一侧。
那么若再选一点C,则对A,B,C以外的点(记为D)来说,它在过三角形ABC的外接园内当且仅当角ADB>角ACB。
由此,若把除A,B以外的所有点(记为P[i])排个序,使得对所有可取得的i,角AP[i]B>角AP[i+1]B。
又记排序后的P[i]中的中间那个一个点P[mid]为C。
则对所有i<mid,P[i]在三角形ABC内;对所有i>mid,P[i]在三角形ABC外。
所以三角形ABC即为所求三角形。
然后继续练习Java,这次刚好还用上了大数。

CODE:

import java.io.*;
import
java.util.*;
import
java.math.*;

public class
Ural {
public static
void main(String args[]) throws IOException
{

new
Ural();
}

public
int N;
public
BigInteger x[],y[],ax,ay,bx,by,cx,cy;
public
BigInteger cross(BigInteger ax,BigInteger ay,BigInteger bx,BigInteger by,BigInteger cx,BigInteger cy)
{

return
bx.subtract(ax).multiply(cy.subtract(ay)).subtract(by.subtract(ay).multiply(cx.subtract(ax)));
}

public
BigInteger dot(BigInteger ax,BigInteger ay,BigInteger bx,BigInteger by,BigInteger cx,BigInteger cy)
{

return
bx.subtract(ax).multiply(cx.subtract(ax)).add(by.subtract(ay).multiply(cy.subtract(ay)));
}

public
boolean less(BigInteger xa,BigInteger ya,BigInteger xb,BigInteger yb)
{

BigInteger
A=BigInteger.valueOf(dot(xa,ya,ax,ay,bx,by).signum()).multiply(dot(xa,ya,ax,ay,bx,by).pow(2).multiply(dot(xb,yb,ax,ay,ax,ay).multiply(dot(xb,yb,bx,by,bx,by))));
BigInteger
B=BigInteger.valueOf(dot(xb,yb,ax,ay,bx,by).signum()).multiply(dot(xb,yb,ax,ay,bx,by).pow(2).multiply(dot(xa,ya,ax,ay,ax,ay).multiply(dot(xa,ya,bx,by,bx,by))));
return
A.compareTo(B)<0;
}

public
void nth_element(int l,int r,int n)
{

int
i=l,j=r;
BigInteger
midx=x[(l+r)/2];
BigInteger
midy=y[(l+r)/2];
while
(i<=j)
{

while
(less(x[i],y[i],midx,midy)) i++;
while
(less(midx,midy,x[j],y[j])) j--;
if
(i<=j)
{

BigInteger
swap;
swap=x[i];
x[i]=x[j];
x[j]=swap;
swap=y[i];
y[i]=y[j];
y[j]=swap;
i++;
j--;
}
}

if
(l<j)
{

if
(n<=j) nth_element(l,j,n);
}

if
(i<r)
{

nth_element(i,r,n-i);
}
}

public
Ural()
{

Scanner
cin=new Scanner(new BufferedInputStream(System.in));
N=cin.nextInt();
if
(N%2!=1)
{

System
.out.println("No solution");
return
;
}

x=new BigInteger[N];
y=new BigInteger[N];
for
(int i=0;i<N;i++)
{

x[i]=cin.nextBigInteger();
y[i]=cin.nextBigInteger();
}

int
ai,bi,ci;
ax=x[0];
ay=y[0];
ai=0;
for
(int i=1;i<N;i++)
if
(x[i].compareTo(ax)>0)
{

ax=x[i];
ay=y[i];
ai=i;
}

N--;
x[ai]=x[N];
y[ai]=y[N];
System
.out.println(ax+" "+ay);
bx=x[0];
by=y[0];
bi=0;
for
(int i=1;i<N;i++)
if
(cross(ax,ay,bx,by,x[i],y[i]).compareTo(BigInteger.valueOf(0))>0)
{

bx=x[i];
by=y[i];
bi=i;
}

N--;
x[bi]=x[N];
y[bi]=y[N];
System
.out.println(bx+" "+by);
nth_element(0,N-1,N/2);
cx=x[N/2];
cy=y[N/2];
System
.out.println(cx+" "+cy);
}
}

URAL1102[Strange Dialog]

水动规。

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-17
DESCRIPTION:
$DESCRIPTION
*/

#include <cstdio>
#include <cstring>
using namespace std;

const
int MAXS=10000000+1;
const
int MAXM=6;
int
N;
bool
f[MAXS];
int
sl;
char
s[MAXS];
char
match[MAXM][7]={"out","output","puton","in","input","one"};
int
matchl[MAXM]={3,6,5,2,5,3};

int
main()
{

gets(s);
sscanf(s,"%d",&N);
for
(int n=0;n<N;n++)
{

gets(s);
sl=strlen(s);
memset(f,0,sizeof(f));
f[0]=true;
for
(int i=0;i<sl;i++)
if
(f[i])
for
(int j=0;j<MAXM;j++)
if
(i+matchl[j]<=sl)
{

bool
matched=true;
for
(int k=0;k<matchl[j];k++)
if
(s[i+k]!=match[j][k])
matched=false;
if
(matched) f[i+matchl[j]]=true;
}

if
(f[sl]) puts("YES");
else
puts("NO");
}

return
0;
}


URAL1101[Robot in the Field]

表达式求值+简单模拟。
继续练习Java。

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-17
DESCRIPTION:
$DESCRIPTION
*/


import
java.io.*;
import
java.util.*;

public class
Ural {
public static
void main(String args[])
{

new
Ural();
}

public
String exp;
public
int N,M,K;
public
int mx[],my[],kx[],ky[],iv[];
public
boolean vars[];
public
final int DIRS=4;
public
int dir,x,y;
public
int dx[],dy[];
public
int getid(char ch)
{

return
(int)(ch-'A');
}

public
boolean calc()
{

Stack
<Boolean> va=new Stack<Boolean>();
Stack
<Character> op=new Stack<Character>();
for
(int i=0;i<exp.length();i++)
{

boolean
opn1,opn2;
switch
(exp.charAt(i))
{

case
'!':
op.push('!');
break
;
case
'&':
while
(!op.empty())
{

if
(op.peek()=='!')
{

opn1=va.pop();
va.push(!opn1);
}

else if
(op.peek()=='&')
{

opn1=va.pop();
opn2=va.pop();
va.push(opn1&&opn2);
}

else break
;
op.pop();
}

op.push('&');
break
;
case
'|':
while
(!op.empty())
{

if
(op.peek()=='!')
{

opn1=va.pop();
va.push(!opn1);
}

else if
(op.peek()=='&')
{

opn1=va.pop();
opn2=va.pop();
va.push(opn1&&opn2);
}

else if
(op.peek()=='|')
{

opn1=va.pop();
opn2=va.pop();
va.push(opn1||opn2);
}

else break
;
op.pop();
}

op.push('|');
break
;
case
'(':
op.push('(');
break
;
case
')':
while
(op.peek()!='(')
{

if
(op.peek()=='!')
{

opn1=va.pop();
va.push(!opn1);
}

else if
(op.peek()=='&')
{

opn1=va.pop();
opn2=va.pop();
va.push(opn1&&opn2);
}

else if
(op.peek()=='|')
{

opn1=va.pop();
opn2=va.pop();
va.push(opn1||opn2);
}

else break
;
op.pop();
}

op.pop();
break
;
case
'0':
va.push(false);
break
;
case
'1':
va.push(true);
break
;
default
:
va.push(vars[getid(exp.charAt(i))]);
break
;
}
}

return
va.pop();
}

public
Ural()
{

Scanner
cin=new Scanner(new BufferedInputStream(System.in));
exp=cin.nextLine();
N=cin.nextInt();
M=cin.nextInt();
K=cin.nextInt();
mx=new int[M];
my=new int[M];
kx=new int[K];
ky=new int[K];
iv=new int[K];
for
(int i=0;i<M;i++)
{

mx[i]=cin.nextInt();
my[i]=cin.nextInt();
}

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

kx[i]=cin.nextInt();
ky[i]=cin.nextInt();
iv[i]=getid(cin.next().charAt(0));
}

exp=exp.replaceAll("NOT","!");
exp=exp.replaceAll("AND","&");
exp=exp.replaceAll("OR","|");
exp=exp.replaceAll("TRUE","1");
exp=exp.replaceAll("FALSE","0");
exp=exp.replaceAll(" ","");
exp="("+exp+")";
vars=new boolean[26];
Arrays
.fill(vars,false);
dir=0;
x=0;
y=0;
dx=new int[]{1,0,-1,0};
dy=new int[]{0,1,0,-1};
while
(Math.abs(x)<=N&&Math.abs(y)<=N)
{

System
.out.println(x+" "+y);
for
(int i=0;i<M;i++)
if
(mx[i]==x&&my[i]==y)
{

if
(calc())
{

if
(dir==0) dir+=DIRS;
dir--;
}

else

{

dir++;
if
(dir==DIRS) dir-=DIRS;
}
}

for
(int i=0;i<K;i++)
if
(kx[i]==x&&ky[i]==y)
vars[iv[i]]=!vars[iv[i]];
x+=dx[dir];
y+=dy[dir];
}
}
}

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]I.Isabella's Message

2011年成都赛区I题的题解。
水题不解释。主要是练练Java,刚学Java,需要多练练。

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-11
DESCRIPTION:
$DESCRIPTION
*/


import
java.io.*;
import
java.util.*;

public class
Main {
public static
void main(String args[])
{

new
Main();
}

public
int N,M;
public
String message[],mask[],words[];
public
String get_answer()
{

StringBuffer
masks[][]=new StringBuffer[4][N];
for
(int i=0;i<N;i++)
masks[0][i]=new StringBuffer(mask[i]);
for
(int i=1;i<4;i++)
for
(int x=0;x<N;x++)
{

masks[i][x]=new StringBuffer();
masks[i][x].setLength(N);
for
(int y=0;y<N;y++)
masks[i][x].setCharAt(y,masks[i-1][N-1-y].charAt(x));
}

StringBuffer
answers_[]=new StringBuffer[4];
for
(int start=0;start<4;start++)
{

answers_[start]=new StringBuffer();
for
(int offset=0;offset<4;offset++)
{

int
now=(start+offset)%4;
for
(int x=0;x<N;x++)
for
(int y=0;y<N;y++)
if
(masks[now][x].charAt(y)=='*')
{

char
get=message[x].charAt(y);
if
(get=='.')
{

if
(answers_[start].length()!=0&&answers_[start].charAt(answers_[start].length()-1)!=' ')
answers_[start].append(' ');
}

else
answers_[start].append(get);
}
}

while
(answers_[start].length()!=0&&answers_[start].charAt(answers_[start].length()-1)==' ')
answers_[start].deleteCharAt(answers_[start].length()-1);
}

String
answers[]=new String[4];
for
(int i=0;i<4;i++) answers[i]=new String(answers_[i]);
Arrays
.sort(answers);
for
(int start=0;start<4;start++)
{

String
set[]=answers[start].split(" ");
boolean
possible=true;
for
(int i=0;i<set.length;i++)
{

boolean
possible_=false;
for
(int j=0;j<M;j++)
{

if
(set[i].equals(words[j])) possible_=true;
}

if
(!possible_)
{

possible=false;
break
;
}
}

if
(possible) return answers[start];
}

return
"FAIL TO DECRYPT";
}

public
Main()
{

Scanner
cin=new Scanner(new BufferedInputStream(System.in));
int
T=cin.nextInt();
for
(int t=1;t<=T;t++)
{

N=cin.nextInt();
message=new String[N];
mask=new String[N];
cin.nextLine();
for
(int i=0;i<N;i++)
message[i]=cin.nextLine();
for
(int i=0;i<N;i++)
mask[i]=cin.nextLine();
M=cin.nextInt();
cin.nextLine();
words=new String[M];
for
(int i=0;i<M;i++)
words[i]=cin.nextLine();
System
.out.println("Case #"+t+": "+get_answer());
}
}
}

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]H.Holiday's Accommodation

2011年成都赛区H题的题解。

对于每一条边,设它左边有X个点,右边有Y个点,则显然有min(X,Y)*2个点会经过这条边,所以答案=sum{每条边的长度乘以会经过这条边的点数}。然后需要动态规划一下。据现场经验,不能直接DFS来动规(会爆栈),需要BFS。
然后,我现在正在学习Java所以代码是用Java写的,呵呵。这是我用Java写的第一个AC的程序哦。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-11
DESCRIPTION:
$DESCRIPTION
*/


import
java.io.*;
import
java.util.*;

public class
Main {
public static
void main(String args[])
{

new
Main();
}

public class
Graph {
public class
edge {
public
int v,d,n;
}

public
int top;
public
edge edges[];
public
int adj[];
public
int N;
public
Graph(int N_)
{

N=N_;
edges=new edge[(N-1)*2];
top=0;
adj=new int[N];
Arrays
.fill(adj,-1);
}

void
add_edge(int u,int v,int d)
{

u--;v--;
edges[top]=new edge();edges[top].v=v;edges[top].d=d;edges[top].n=adj[u];adj[u]=top++;
edges[top]=new edge();edges[top].v=u;edges[top].d=d;edges[top].n=adj[v];adj[v]=top++;
}
}

public
Graph graph;
public
long get_answer()
{

int
qh,qt;
int
q[]=new int[graph.N];
int
f[]=new int[graph.N];
int
d[]=new int[graph.N];
boolean
inq[]=new boolean[graph.N];
Arrays
.fill(inq,false);
inq[q[qh=qt=0]=0]=true;
while
(qh<=qt)
{

int
u=q[qh++];
for
(int e=graph.adj[u];e!=-1;e=graph.edges[e].n)
{

int
v=graph.edges[e].v;
if
(!inq[v])
{

inq[q[++qt]=v]=true;
f[v]=u;
d[v]=graph.edges[e].d;
}
}
}

long
answer=0;
int
c[]=new int[graph.N];
Arrays
.fill(c,0);
while
(qt>=0)
{

int
u=q[qt--];
c[u]++;
c[f[u]]+=c[u];
answer+=(long)(Math.min(c[u],graph.N-c[u]))*(long)(d[u])*(long)(2);
}

return
answer;
}

public
Main()
{

Scanner
cin = new Scanner(new BufferedInputStream(System.in));
int
T=cin.nextInt();
for
(int t=1;t<=T;t++)
{

int
N=cin.nextInt();
graph=new Graph(N);
for
(int i=1;i<N;i++)
{

int
X,Y,Z;
X=cin.nextInt();
Y=cin.nextInt();
Z=cin.nextInt();
graph.add_edge(X,Y,Z);
}

System
.out.println("Case #"+t+": "+get_answer());
}
}
}

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]G.GRE Words

2011年成都赛区G题的题解。

很容易想到一个朴素的,O(n^2)的动态规划(把做KMP的时间当做常数)。

显然,这样做太慢了,要想想应该怎么优化。

关于字符串的匹配,很容易想到用后缀数组来优化。

但是只用后缀数组的话,还是没有用的。

要优化转移使每次转移的代价由O(n)变成O(logn)甚至O(1)。那么时间复杂度就自然降低了。

于是很容易就想到了线段树。

接着,把它们组合起来。

首先把输入的所有字符串连接起来,中间用’#’分割(这样可以减少用倍增法做后缀数组的时间复杂度的,不添加的话会超时,不过如果你是用其他一些O(n)的算法来构造后缀数组或者后缀树的话就可以不用分割)。

再做后缀数组。

然后开始动规。

用f[i]表示第一个单词为word[i]的最优解。

那么f[i]=max{f[j]|j>i and word[i] is a substring of word[j]}+W[i],可以用线段树来优化max操作。

设suffix(i)表示从第i位到最后所构成的后缀,rank[i]表示suffix(i)的排名,p[i]表示word[i]在拼接后的字符串中的位置,用len[i]表示word[i]的长度。

线段树记录排名在某个区间的所有串的开头部分(即’#’前部分)所在单词的f值。

求f[i]时,用二分法(需要利用高度数组,并需要用到RMQ)求得L=min{i|LCP(suffix(SA[j]),suffix(p[i]))=len[i]},R=max{i|LCP(suffix(SA[j]),suffix(p[i]))=len[i]}。

然后f[i]=排名在L到R之间的所有f的最大值+W[i],这一步用线段树来求。 

最后更新线段树,将排名为rank[p[i]+j](0<=j<len[i])的f值更新为f[i]。

这道题就做出来了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2011-11-10

DESCRIPTION:

$DESCRIPTION

*/

#include <cstdio>

#include <cstring>

using namespace std;

 

namespace sujiaos_lab

{

const int LOG2_MAXLENGTH=19;

const int MAXLENGTH=320003;

const int MAXALPHABET=129;

typedef char string[MAXLENGTH];

typedef int* int_pointer;

int_pointer sort;

int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];

int_pointer SA=_SA,rank=_rank,TSA=_TSA,Trank=_Trank;

void get_SA(string s,int length)

{

     sort=Trank;

     for (int i=0;i<MAXALPHABET;i++) sort[i]=0;

     for (int i=1;i<=length;i++) sort[s[i]]++;

     for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];

     for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;

     rank[SA[1]]=1;

     for (int i=2;i<=length;i++)

         if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];

         else rank[SA[i]]=rank[SA[i-1]]+1;

     for (int block=1;rank[SA[length]]!=length;block<<=1)

     {

         sort=Trank;

         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;

         for (int i=length;i>=1;i–)

             if (SA[i]-block>=1)

                TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

         for (int i=length-block+1;i<=length;i++)

             TSA[sort[rank[i]]–]=i;

         int_pointer swap;

         swap=SA,SA=TSA,TSA=swap;

         swap=rank,rank=Trank,Trank=swap;

         rank[SA[1]]=1;

         for (int i=2;i<=length;i++)

             if (Trank[SA[i]]==Trank[SA[i-1]]

                &&Trank[SA[i]+block]==Trank[SA[i-1]+block])

                rank[SA[i]]=rank[SA[i-1]];

             else rank[SA[i]]=rank[SA[i-1]]+1;

     }

}

int_pointer height;

void get_height(string s,int length)

{

     height=TSA;

     for (int i=1,h=0;i<=length;i++)

     {

         if (h) h–;

         if (rank[i]!=1)

         {

            int j=SA[rank[i]-1];

            while (s[i+h]==s[j+h]) h++;

         }

         height[rank[i]]=h;

     }

}

int_pointer log2;

int rmq[LOG2_MAXLENGTH][MAXLENGTH];

void get_RMQ(int length)

{

     log2=Trank;

     log2[1]=0;

     for (int i=2;i<=length;i++) log2[i]=log2[i-1]+(i==(i&(-i)));

     for (int i=1;i<=length;i++) rmq[0][i]=i;

     for (int log=1;log<=log2[length];log++)

     {

         int exp=1<<log,exp_div_2=exp>>1;

         for (int i=1;i<=length-exp+1;i++)

         {

             int a=rmq[log-1][i];

             int b=rmq[log-1][i+exp_div_2];

             rmq[log][i]=height[a]<height[b]?a:b;

         }

     }

}

int RMQ(int a,int b)

{

    int log=log2[b-a+1];

    int exp=1<<log;

    a=rmq[log][a],b=rmq[log][b-exp+1];

    return height[a]<height[b]?a:b;

}

int LCP(int a,int b)

{

    a=rank[a],b=rank[b];

    if (a>b) return height[RMQ(b+1,a)];

    else return height[RMQ(a+1,b)];

}

}

using namespace sujiaos_lab;

const int MAXN=20003;

sujiaos_lab::string s;

int W[MAXN];

int p[MAXN];

int len[MAXN];

 

const int MAXNODE=MAXLENGTH*4+1;

int st[MAXNODE];

void insert(int p,int value,int L,int R,int root=1)

{

     if (p<L||R<p) return;

     else

     {

         if (value>st[root])

            st[root]=value;

         if (L==R) return;

         int LL=L,LR=(L+R)>>1,Lroot=root<<1,

             RL=LR+1,RR=R,Rroot=Lroot|1;

         insert(p,value,LL,LR,Lroot);

         insert(p,value,RL,RR,Rroot);

     }

}

int query(int l,int r,int L,int R,int root=1)

{

    if (r<L||R<l||L>R) return 0;

    else if (l<=L&&R<=r) return st[root];

    else

    {

        int LL=L,LR=(L+R)>>1,Lroot=root<<1,

            RL=LR+1,RR=R,Rroot=Lroot|1;

        int LV=query(l,r,LL,LR,Lroot);

        int RV=query(l,r,RL,RR,Rroot);

        return LV>RV?LV:RV;

    }

}

int main()

{

    int TC;

    scanf(“%d”,&TC);

    for (int tc=1;tc<=TC;tc++)

    {

        int N;

        scanf(“%d”,&N);

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

        {

            p[i]=p[i-1]+len[i-1];

            s[p[i]++]=’#’;

            scanf(“%s%d”,s+p[i],&W[i]);

            len[i]=strlen(s+p[i]);

        }

       

        int length=strlen(s);

        get_SA(s,length);

        get_height(s,length);

        get_RMQ(length);

       

        int answer=0;

        memset(st,0,sizeof(st));

        for (int i=N;i>=1;i–)

        {

            int L,R,l,r;

            L=0,R=rank[p[i]];

            while (L+1!=R)

            {

                  int mid=(L+R)>>1;

                  if (height[RMQ(mid+1,rank[p[i]])]>=len[i]) R=mid;

                  else L=mid;

            }

            l=R;

            L=rank[p[i]],R=length+1;

            while (L+1!=R)

            {

                  int mid=(L+R)>>1;

                  if (height[RMQ(rank[p[i]]+1,mid)]>=len[i]) L=mid;

                  else R=mid;

            }

            r=L;

            int get=query(l,r,1,length)+W[i];

            if (get>answer) answer=get;

            for (int j=0;j<len[i];j++)

                insert(rank[p[i]+j],get,1,length);

        }

        printf(“Case #%d: %d\n”,tc,answer);

    }

}

 

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]B.Break the Chocolate

2011年成都赛区B题的题解。

水题不解释。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2011-11-09

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

int cut(long long int x)

{

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

    {

        if (x<=0) return i;

        x-=1ll<<i;

    }

}

 

int main()

{

    int TC;

    cin>>TC;

    for (int tc=1;tc<=TC;tc++)

    {

        long long int x,y,z;

        cin>>x>>y>>z;

        cout<<“Case #”<<tc<<“: “<<(x*y*z-1)<<” “<<(cut(x-1)+cut(y-1)+cut(z-1))<<endl;

    }

    return 0;

}

 

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]A.Alice and Bob

2011年成都赛区A题的题解。

这是一道博弈动规题目。

首先,我们把数字分成4类,1,,2,大于1的奇数,大于2的偶数。

一个大于3的奇数是等价于3的,因为,总可以对手减一个,你也减一个,就又变成了一个大于3的奇数或者3,总可以让它变成3。因此所有大于1的奇数都等价于3。同理,所有大于2的偶数等价于4。

所以我们用f[a][b][c][d]表示有a个1,b个2,c个3,d个4是不是一个必胜态,然后动规求解就好了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2011-11-09

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

bool calced[51][51][51][51];

bool f[51][51][51][51];

int F(int a,int b,int c,int d)

{

    if (!calced[a][b][c][d])

    {

       if (a>=1&&!F(a-1,b,c,d)) f[a][b][c][d]=true;

       if (b>=1&&!F(a+1,b-1,c,d)) f[a][b][c][d]=true;

       if (c>=1&&!F(a,b+1,c-1,d)) f[a][b][c][d]=true;

       if (d>=1&&!F(a,b,c+1,d-1)) f[a][b][c][d]=true;

      

       if (a>=2&&!F(a-2,b+1,c,d)) f[a][b][c][d]=true;

       if (b>=2&&!F(a,b-2,c,d+1)) f[a][b][c][d]=true;

       if (c>=2&&!F(a,b,c-2,d+1)) f[a][b][c][d]=true;

       if (d>=2&&!F(a,b,c,d-2+1)) f[a][b][c][d]=true;

      

       if (a>=1&&b>=1&&!F(a-1,b-1,c+1,d)) f[a][b][c][d]=true;

       if (a>=1&&c>=1&&!F(a-1,b,c-1,d+1)) f[a][b][c][d]=true;

       if (a>=1&&d>=1&&!F(a-1,b,c+1,d-1)) f[a][b][c][d]=true;

       if (b>=1&&c>=1&&!F(a,b-1,c-1+1,d)) f[a][b][c][d]=true;

       if (b>=1&&d>=1&&!F(a,b-1,c,d-1+1)) f[a][b][c][d]=true;

       if (c>=1&&d>=1&&!F(a,b,c-1+1,d-1)) f[a][b][c][d]=true;

      

       calced[a][b][c][d]=true;

    }

    return f[a][b][c][d];

}

 

int main()

{

    int TC;

    cin>>TC;

    for (int tc=1;tc<=TC;tc++)

    {

        int N,a=0,b=0,c=0,d=0;

        cin>>N;

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

        {

            int t;

            cin>>t;

            if (t==1) a++;

            else if (t==2) b++;

            else if (t%2==1) c++;

            else d++;

        }

        cout<<“Case #”<<tc<<“: “<<(F(a,b,c,d)?“Alice”:“Bob”)<<endl;

    }

    return 0;

}

 

OI的结束,ACM的开始[2011年10月26日]

去年的八月份,参加了NOI2010,以一枚银牌结束了自己的OI生涯,然后又回去参加了高考,可惜没考好啊,还不如当时现场保送走。(所以,能现场保送的同学们,最好还是直接走吧。)

然后,来到了人大,一个ACM弱校。不过也好,要是到清华北大复旦上交之类的学校就不那么容易进ACM队了。
在这个月,我有幸参加了2011 ACM/ICPC 上海赛区现场赛,和队友zx及wyw一起得到了一个银奖。也算我的ACM生涯的开始吧。
(附图,拿气球的是我。)
OI的结束,ACM的开始 - Boleyn Su - @Boleyn Sus