2010 East Central Regional Contest
声明：本博菜，只做水，未给出程序的题目待补充。
题目网址：
http://acm.ashland.edu/
【Problem A】 Cut It Out!
【Problem B】 Flip It
简单的模拟题。
把一个卡片矩阵通过四种操作翻成一叠，从 bottom 向 top 输出正面朝上的卡片编号。
每个矩阵的元素一个栈，每次按照命令执行即可。
#include<iostream>
#define MAXN 21
using namespace std ;
typedef struct
{
int stk[MAXN*MAXN] ;
int top ;
void clear(){ top = 0 ;}
void push(int x){
stk[top++] = x;
}
int pop(){
return stk[--top] ;
}
bool empty(){
return top == 0 ;
}
}STACK;
STACK bd[MAXN][MAXN] ;
int t , b , l , r ;
void move(int x0 ,int y0 ,int x1 , int y1){
while(!bd[x0][y0].empty()){
int x = bd[x0][y0].pop();
bd[x1][y1].push(-x);
}
}
void left_flip(){
int i ;
for(i = t ; i <= b ; ++ i)
move(i , l , i , l+1 );
l ++ ;
}
void right_flip(){
int i ,j ;
for(i = t ; i <= b ; ++i)
move(i , r , i , r-1);
r -- ;
}
void top_flip(){
int i ;
for(i = l ; i <= r ; ++ i)
move(t , i , t+1 , i);
t ++ ;
}
void bottom_flip(){
int i ;
for(i = l ; i<=r ; ++i)
move(b , i , b-1 , i);
b -- ;
}
int main(){
int i ,j , n , m , x , y , test = 0;
char cmd[3*MAXN] ;
while(scanf("%d%d" ,&n,&m)!=EOF && (n|m)){
for(i = 0 ; i < n ; ++ i)
for(j = 0 ; j < m ; ++ j)
bd[i][j].clear();
for(i = 0 ; i < n ; ++ i)
for(j = 0 ; j < m ; ++ j ){
scanf("%d" , &x);
bd[i][j].push(x);
}
t = l = 0 ; b = n-1 ; r = m -1 ;
getchar(); gets(cmd);
for(i = 0 ; i < strlen(cmd) ; ++ i)
switch(cmd[i]){
case 'L' : left_flip() ; break ;
case 'R' : right_flip(); break ;
case 'T' : top_flip(); break ;
case 'B' : bottom_flip(); break ;
}
x = b , y = r ;
printf("Case %d:" ,++test) ;
for(i = 0 ; i < bd[x][y].top ; ++i )
if(bd[x][y].stk[i] > 0){
printf(" %d" , bd[x][y].stk[i]);
}
printf("\n");
}
//while(getchar());
return 0 ;
}
【Problem C】
中等的广度优先搜索题，对练习编码速度比较有好处。
题目比较难懂(至少对我而言)，解释一下：
一个 n*n*n 的立方体，中间 <1,1,1>-<n-2,n-2,n-2> 这个被挖空，剩下三维立方体的6个面(具体信息由题目给出)。然后在<1,1,1>有一个 Marker ，有三根无线长的棒子穿过它，当你移动 Marker 时，由于三根棒子连在一起，所以会受到六个面的阻碍，求 Marker 到达 <n-2,n-2,n-2> 的最少步骤。
可以仔细看看题目中的图像。
状态还是比较好确定的，就用 Marker 的坐标<x,y,z>作为一个状态即可。然后，将看<x,y,z>映射到六个面上的格子是否皆可移动，若是，则 Marker 可以移动，否则，不可移动。这样生成状态即可。
其实，跟 2D 迷宫也是差不多的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define MAXN 35
#define INF (1<<29)
using namespace std ;
struct node{
int x ,y , z;
node(){}
node(int ix , int iy ,int iz): x(ix) ,y(iy) , z(iz){}
};
int dx[]={0,0,1,-1,0,0};
int dy[]={-1,1,0,0,0,0};
int dz[]={0,0,0,0,1,-1};
int n ;
int used[MAXN*MAXN*MAXN] , mov[MAXN*MAXN*MAXN] ;
char cube[MAXN][MAXN][MAXN] , cmd[]="FBLRUD";
inline int hash(node t){
return t.x * n * n + t.y * n + t.z ;
}
inline bool IsOut(node t){
return t.x<1||t.y<1||t.z<1||t.x>=n-1||t.y>=n-1||t.z>=n-1;
}
node GridInFace(node a , int i){
switch(i){
case 0: return node(a.x , 0 , a.z);
case 1: return node(a.x , n-1 , a.z);
case 2: return node(n-1 , a.y , a.z);
case 3: return node(0 , a.y , a.z);
case 4: return node(a.x , a.y , n-1);
case 5: return node(a.x , a.y , 0 );
}
}
void input(){
int x , y , z , i;
char info[100];
// init the cube
for(x =0 ;x<n ;++x)
for(y=0;y<n;++y)
for(z=0;z<n;++z)
cube[x][y][z]=' ';
getchar();
// read Forward face
for(z=n-1 ; z>=0 ; --z){
gets(info); i = 0 ;
for(x = n-1 ; x>=0 ; --x)
cube[x][0][z] = info[i++];
}
// read Right face
for(z=n-1 ; z>=0 ; --z){
gets(info); i = 0 ;
for(y=0;y<=n-1;++y)
cube[0][y][z] = info[i++];
}
// read Back face
for(z=n-1 ; z>=0 ; --z){
gets(info); i = 0 ;
for(x=0 ; x<=n-1 ; ++x)
cube[x][n-1][z] = info[i++];
}
// read Left face
for(z=n-1 ; z>=0 ;--z){
gets(info); i = 0 ;
for(y=n-1;y>=0;--y)
cube[n-1][y][z] = info[i++];
}
// read Up face
for(y=n-1;y>=0;--y){
gets(info); i = 0 ;
for(x=n-1;x>=0;--x)
cube[x][y][n-1] = info[i++];
}
// read down face
for(y=0;y<=n-1;++y){
gets(info); i = 0 ;
for(x=n-1;x>=0;--x)
cube[x][y][0] = info[i++];
}
}
bool extend(node cur , int k , node &nxt){
nxt.x = cur.x + dx[k] , nxt.y = cur.y + dy[k] , nxt.z = cur.z + dz[k] ;
if(IsOut(nxt)) return false ;
node t ;
for(int i = 0 ; i < 6 ; ++ i){
t = GridInFace(nxt , i);
if(cube[t.x][t.y][t.z] == 'X')
return false;
}
return true;
}
void MakeSolution(int val){
if( used[val] != INF){
MakeSolution(used[val]);
printf("%c" , cmd[mov[val]]);
}
}
void Run(){
int i , val;
queue<node> Q ;
node cur(1,1,1) , nxt , end(n-2,n-2,n-2) ;
memset(used ,-1 ,sizeof(used));
used[ hash(cur) ] = INF ; Q.push(cur);
while(!Q.empty()){
cur = Q.front() ; Q.pop() ;
for(i = 0 ; i < 6 ; ++i)
if(extend(cur , i , nxt)){
val = hash(nxt);
if(used[val] !=-1) continue;
used[val] = hash(cur) ; mov[val] = i ;
if(val == hash(end)){
MakeSolution(val); return ;
}
Q.push(nxt);
//printf("position (%d , %d ,%d)\n" , nxt.x, nxt.y ,nxt.z);
}
}
printf("Impossible");
}
int main(){
while(scanf("%d" ,&n)!=EOF && n){
input();
Run();
printf("\n");
}
//while(getchar());
return 0 ;
}
【Problem D】
【Problem E】
【Problem F】
比较经典的动态规划。
题目描述：Bob 有 M 美元，要向 N 个地区进行投资，以获得更高的选票，对 p 区投资x元后最终
的投票比例为 F(p , x) = I(p) + delta * x/(x+10.1) , 请问 Bob 应该怎样投资？请输出最高票数及投资
分布(注意：投资数按字典序从大到小)。
思路分析： opt[i,j]表示对 percincts_0 , percincts_1 .... , percincts_i 前面 i 个区一共投资 j 美元
可获得的最高票数。则有动态转移方程为：
opt[i , j] = max ( opt[i-1 , j - k] + f(i ,k)) 0<=k<=j .
递推理由其实就是依次枚举地区 i 的投资金额。
问题的难点在于找到最大字典序的一个投资分布：先按照逆序完成动态规划，按照从顶上向上的
原则递归选择使得 opt[i-1 , j-k] + f(i,k) == opt[i ,j] 成立的最大 k 即可。
具体可以参考程序。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define MAXN 105
using namespace std ;
int m , n , ans[MAXN] , opt[MAXN][MAXN] ;
double N[MAXN] , I[MAXN] , delta[MAXN] ;
inline int Round(double x){
return x - floor(x) < 0.500000 ? (int)floor(x) : (int)ceil(x) ;
}
inline int f(int i , int M){
double val = (double)M /(10.10 + (double)M) ;
val = N[i] * (I[i] + val*delta[i]) /100.00 ;
return Round(val);
}
int Run(){
int i ,j ,k ;
int maxval ;
opt[0][0] = f(0 , 0);
for(j = 1 ; j <= m ; ++j ) opt[0][j] = f(0 , j);
for(i = 1 ; i < n ; ++i ) opt[i][0] = opt[i-1][0] + f(i,0);
for(i = 1 ; i < n ; ++ i){
for(j = 1 ; j<=m ; ++j){
maxval = -1 ;
for(k = 0 ; k <= j ; ++ k)
maxval = max( opt[i-1][j-k] + f(i , k) , maxval );
maxval = max(maxval , opt[i][j-1]);
opt[i][j] = maxval ;
}
}
return opt[n-1][m] ;
}
void MakeSolution(int i , int j){ // 构造最优解
if(i == 0 ) {
ans[i] = j ; return ;
}
for(int k = j ; k >=0 ; -- k) // 选择最大满足递推的 k
if(opt[i-1][j-k] + f(i , k) == opt[i][j] ) {
ans[i] = k ;
MakeSolution(i-1 , j-k);
return ;
}
}
int main(){
int i , icase = 0 ;
//freopen("1.std.in" , "r" , stdin); freopen("my.out" ,"w" , stdout);
while(scanf("%d%d",&m ,&n)!=EOF && (n+m)){
for(i = n-1 ; i >= 0 ; --i) // 将地区的信息逆序处理
scanf("%lf%lf%lf",&N[i] , &I[i] , &delta[i]);
printf("Case %d: %d\n" , ++icase , Run());
memset(ans , 0 , sizeof(ans));
MakeSolution(n-1 , m);
printf("%d:%d" , 0 , ans[n-1]);
for(i = n-2 ; i >= 0 ; -- i)
printf(" %d:%d" , n - i - 1 , ans[i]);
printf("\n");
}
//fclose(stdin) ; fclose(stdout);
return 0 ;
}
【Problem G】Vampires!
依旧模拟题。也是练习编码速度的考题。
其实跟模拟机器人走迷宫差不多。
#include<iostream>
#define MAXN 105
#define SIZE (MAXN*MAXN)
using namespace std ;
typedef struct{
int x ,y ;
}node;
int bd[MAXN][MAXN], Vcnt ,Ocnt ,Mcnt ;
node vp[SIZE] ;
int face[SIZE] ;
int dx[] = {1,0,0,-1} ;
int dy[] = {0,1,-1,0} ;
char direction[][10]={
"east", "north" ,"south" , "west"
};
inline int IsOut(int x ,int y){
return (x<0)||(y<0)||(x>100)||(y>100) ;
}
int indanger(node p , int cmd){
int cx ,cy , nx ,ny , u;
cx = p.x , cy = p.y ;
while(1){
nx = cx + dx[cmd] , ny = cy + dy[cmd] ;
if(IsOut(nx ,ny) || bd[nx][ny] == -1) return 0 ;
if(bd[nx][ny] != 0 ){
return face[bd[nx][ny]] == cmd ;
}
cx = nx , cy = ny ;
}
}
void Run(){
int cnt = 0 , i , k , vis[4] , c ;
for(i = 1 ; i<=Vcnt ; ++ i){
memset(vis , 0 ,sizeof(vis));
c = 0 ;
for(k = 0 ; k < 4 ; ++ k)
if(indanger(vp[i] , k)){
vis[k] = 1 ;
++ c ;
}
if(c == 0) continue ;
++ cnt ;
printf("vampire %d" , i);
for(k = 0 ; k < 4 ; ++ k)
if(vis[k])
printf(" %s" , direction[k]);
printf("\n");
}
if(cnt == 0 )
printf("none\n");
}
int main(){
int i , j , x0, y0 , x1 , y1, tst = 0 , x, y , myp[300];
char dir[2] ;
myp['E'] = 3 ; myp['N'] = 2 ; myp['S'] = 1 ; myp['W'] = 0 ;
while(scanf("%d%d%d",&Vcnt,&Ocnt ,&Mcnt)!=EOF && (Vcnt + Ocnt + Mcnt)){
memset(bd , 0 ,sizeof(bd));
for(i = 1 ; i <= Vcnt ;++i){
scanf("%d%d" ,&vp[i].x, &vp[i].y);
}
for(i = 1 ; i <= Ocnt ; ++i){
scanf("%d%d",&x,&y);
bd[x][y] = -1 ;
}
for(i = 1 ; i <= Mcnt ; ++ i){
scanf("%s%d%d%d%d" ,dir , &x0,&y0,&x1,&y1);
face[i] = myp[ dir[0] ] ;
if(x0 == x1){
if(y0 <= y1){
for(j = y0 ; j <= y1 ; ++j) bd[x0][j] = i ;
}else{
for(j = y1 ; j <= y0 ; ++j) bd[x0][j] = i ;
}
}else if(x0 <= x1){
for(j = x0 ; j <= x1 ; ++ j) bd[j][y0] = i ;
}else {
for(j = x1 ; j <= x0 ; ++ j) bd[j][y0] = i ;
}
}
printf("Case %d:\n" ,++tst);
Run();
}
return 0 ;
}
【Problem H】