P2822

## 解题思路

c=c=c=1;
for(int i=1;i<=2000;++i)
c[i]=1;
for(int i=2;i<=2000;i++)
{
for(int j=1;j<=i;j++)
{
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
}
f[i][i+1]=f[i][i];//下面解释
}


#include <cstdio>
#include <cctype>

//快读

int c;
int f;

int main()
{
c=c=c=1;
for(int i=1;i<=2000;++i)
c[i]=1;
for(int i=2;i<=2000;i++)
{
for(int j=1;j<=i;j++)
{
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
}
f[i][i+1]=f[i][i];
}
while(t--)
{
printf("%d\n",f[n][m>n?n:m]);
}
return 0;
}


#include <cstdio>
#include <cctype>

{
char c = getchar();
int s = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return s;
}

int c;
int f;

int main()
{
c=c=c=1;
for(int i=1;i<=2000;++i)
c[i]=1;
for(int i=2;i<=2000;i++)
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]%k+c[i-1][j]%k)%k;
for(int i=1;i<=2000;i++)
for(int j=1;j<=2000;j++)
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(i>=j && c[i][j]==0);
//这里和上面一样，但是一定要注意判断这里的c[i][j]有没有意义，否则会抱灵
while(t--)
{
printf("%d\n",f[n][m]);
}
return 0;
}


P2858

## 解题思路

f_{i,j}=\max(f_{i-1,j}+dv_{i-1},f_{i,j+1}+dv_{j+1})

#include <cstdio>
#include <cctype>

//快读

//max

const int maxn=2005;
int v[maxn],f[maxn][maxn];

int main()
{
for(int i=1;i<=n;i++)
for(int len=n-1,day=1;len>=1;len--,day++)//从n-1开始枚举区间长度
for(int i=1,j=i+len-1;j<=n;i++,j++)
f[i][j]=max(f[i][j+1]+v[j+1]*day,f[i-1][j]+v[i-1]*day);
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,f[i][i]+n*v[i]);
printf("%d\n",ans);
return 0;
}


## 解题思路

• 起点只能往起点规定的方向走，不能任意出发
• IO 时的空格和换行问题
• 方向的转换
• (r_0,c_0,dir_0) 不能直接作为初始状态，需要先移动一格

#include <string>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

string maze_name;
int r0,c0,r1,c1,r2,c2;
char dir0;

struct node//bfs时的遍历状态
{
int r,c,dir;//三元组存储
node(){}
node(int _r,int _c,int _dir)
{
r=_r,c=_c,dir=_dir;
}
};

const char* dirs="NESW";
const char* turns="FLR";

inline int dir_id(char c)
{
return strchr(dirs,c)-dirs;//将字母返回数字id
}

inline int turn_id(char c)
{
return strchr(turns,c)-turns;//将字母返回数字id
}

inline bool chk(int r,int c)//防越界
{
return 1<=r && r<=9 && 1<=c && c<=9;
}

const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};

bool has_edge;
node p;
int d;

inline node walk(const node &now,int turn)//返回某个状态转弯之后的状态
{
int dir=now.dir;
if(turn==1)//左转
dir=(dir+3)%4;
else if(turn==2)//右转
dir=(dir+1)%4;
return node(now.r+dr[dir],now.c+dc[dir],dir);//返回转完之后的状态
}

void print(node u)//打印路径
{
vector<node> way;
while(true)
{
way.push_back(u);//加入路径
if(!d[u.r][u.c][u.dir])
break;
u=p[u.r][u.c][u.dir];//然后回溯上一个状态
}
way.push_back(node(r0,c0,dir_id(dir0)));
int cnt=0;
for(int i=way.size()-1;i>=0;i--)
{
if(cnt%10==0)
cout<<' ';
cout<<" ("<<way[i].r<<','<<way[i].c<<')';
if(++cnt%10==0)
cout<<endl;
}
if(way.size()%10)//注意io细节
cout<<endl;
return;
}

void bfs()
{
cout<<maze_name<<endl;
queue<node> q;
memset(d,-1,sizeof d);
memset(p,0,sizeof p);
q.push(node(r1,c1,dir_id(dir0)));//先将初始状态加入
d[r1][c1][dir_id(dir0)]=0;
while(!q.empty())
{
node now=q.front();
q.pop();
if(now.r==r2 && now.c==c2)//到达终点
{
print(now);
return;
}
for(int i=0;i<3;i++)//枚举转弯的方向
{
node to=walk(now,i);//转个弯
if(has_edge[now.r][now.c][now.dir][i] && chk(to.r,to.c) && d[to.r][to.c][to.dir]<0)//判断是否合法
{
d[to.r][to.c][to.dir]=d[now.r][now.c][now.dir]+1;
p[to.r][to.c][to.dir]=now;
q.push(to);
}
}
}
cout<<"  No Solution Possible"<<endl;//注意行首空格
}

{
memset(has_edge,0,sizeof has_edge);
cin>>maze_name;
if(maze_name=="END")
return false;
cin>>r0>>c0>>dir0>>r2>>c2;
r1=r0+dr[dir_id(dir0)];//注意(r0,c0)不能直接作为初始状态
c1=c0+dc[dir_id(dir0)];
int r,c;
string tmp;
while(true)//读入迷宫的点
{
cin>>r;
if(!r)
break;
cin>>c>>tmp;
while(tmp!="*")
{
int dir=dir_id(tmp);
for(int i=1;i<tmp.size();i++)
has_edge[r][c][dir][turn_id(tmp[i])]=true;
cin>>tmp;
}
}
bfs();
return true;
}

int main()
{
ios::sync_with_stdio(false);
return 0;
}


## 题目原文

### Description

The 1999 World Finals Contest included a problem based on a dice maze. At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last years problem statement. But we arehappy to report that Mr. Abbott has offered his expertise to this years contest with his original and unpublished walk-through arrow mazes.
As are most mazes,a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited.
These directions are always left, forward or right, or any combination of these.
Figure 1 illustrates a walk-through arrow maze. The intersections are identified as (row, column) pairs, with the upper left being (1,1). The Entrance intersection for Figure 1 is (3,1), and the Goal intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit(1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from(1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual(unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).
You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course.

### Input

The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9.
The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.
All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is N,S,E or W to indicate in what direction of travel the sign would be seen. For example,’S’ indicates that this is the sign that is seen when travelling south.(This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be L,F or R indicating left, forward, and right, respectively.
The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word END on a single line by itself.

### Output

For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase No Solution Possible. Maze names should start in column 1, and all other lines should start in column 3,i.e., indented two spaces. Solutions should be output as a list of intersections in the format(R,C) in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.

UVA297

## 解题思路

#include <cstdio>
#include <cstring>

char s[1024+5];
int buf;
int ans,p;

void draw(int x1,int y1,int w)
{
char ch=s[p++];
if(ch=='p')
{
draw(x1+w/2,y1    ,w/2);//1
draw(x1    ,y1    ,w/2);//2
draw(x1    ,y1+w/2,w/2);//3
draw(x1+w/2,y1+w/2,w/2);//4
}
else if(ch=='f')
for(int i=x1;i<x1+w;i++)
for(int j=y1;j<y1+w;j++)
if(!buf[i][j])
buf[i][j]=1,ans++;//直接填充并记录答案
return;
}

int main()
{
int n;
scanf("%d",&n);
while(n--)
{
ans=0;
memset(buf,0,sizeof buf);//记得每组数据间的清零操作
scanf("%s",s);
p=0;
draw(1,1,32);
p=0;
scanf("%s",s);
draw(1,1,32);
printf("There are %d black pixels.\n",ans);
}
return 0;
}


UVA839

## 解题思路

#include <cstdio>
#include <cctype>

{
//快读被省略了
}

{
bool b1=true,b2=true;
if(!WL)//如果有左儿子
if(!WR)
W=WL+WR;//当前天平的重量
return b1 && b2 && WL*DL==WR*DR;//左右儿子都平衡且自身平衡时为true
}

int main()
{
int W;
while(t--)
{
if(t)
printf("\n");//最后不输出多余空行
}
return 0;
}


UVA548

## 解题思路

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

const int maxn=1e4+5;
int in_o[maxn],post_o[maxn],lson[maxn],rson[maxn],n;

{
stringstream ss(s);
n=0;
int x;
while(ss>>x)
a[n++]=x;
return;
}

int ans,ans_sum;

int build(int l1,int r1,int l2,int r2,int sum)
{
if(l1>r1)
return 0;
int root=post_o[r2];
sum+=root;
int p=l1;
while(in_o[p]!=root)
p++;
int cnt=p-l1;
lson[root]=build(l1,p-1,l2,l2+cnt-1,sum);
rson[root]=build(p+1,r1,l2+cnt,r2-1,sum);
if(!lson[root] && !rson[root])
if(sum<ans_sum || (sum==ans_sum && root<ans))
ans_sum=sum,ans=root;
return root;
}

int main()
{
string in,post;
while(getline(cin,in) && getline(cin,post))
{
ans_sum=0x7f7f7f7f;
build(0,n-1,0,n-1,0);
cout<<ans<<endl;
}
return 0;
}


UVA122

## 解题思路

struct node
{
bool have_value;//是否被赋值过
int val;//节点的值
node *left,*right;//指向左右儿子的指针，默认为NULL
node():have_value(false),left(NULL),right(NULL){}//构造函数
};


char s[maxn];

{
failed=false;
remove_tree(root);//释放内存
root=newnode();//指定新的根节点
while(1)
{
if(scanf("%s",s)!=1)//如果输入结束了
return false;
if(!strcmp(s,"()"))//如果一棵树到头了
break;
int v;//读入该节点的值使用
sscanf(&s,"%d",&v);//sscanf大法好
}
return true;
}


inline node* newnode()
{
return new node();
}

void remove_tree(node *now)
{
if(now==NULL)//如果节点为空
return;
remove_tree(now->left);//递归释放左子树
remove_tree(now->right);
delete now;//删除当前节点
}


void addnode(int v,char *s)
{
int n=strlen(s);
node *u=root;//因为给出的点的形式都是从根开始遍历的
for(int i=0;i<n;i++)//根据提示一步步往下走
{
if(s[i]=='L')
{
if(u->left==NULL)
u->left=newnode();
u=u->left;
}
else if(s[i]=='R')
{
if(u->right==NULL)
u->right=newnode();
u=u->right;
}
}
if(u->have_value)//如果这个点已经被赋过值了，那么显然输入错误
failed=true;
u->val=v;//赋值
u->have_value=true;//打标记
return;
}


bool bfs(vector<int> &ans)
{
queue<node*> q;//存储待访问节点
ans.clear();
q.push(root);
while(!q.empty())
{
node *now=q.front();
q.pop();
if(!now->have_value)//如果当前节点未赋值
return false;//说明信息不完整
ans.push_back(now->val);//计入答案
if(now->left!=NULL)
q.push(now->left);
if(now->right!=NULL)
q.push(now->right);//分别加入左右儿子节点
}
return true;
}


#include <cstdio>
#include <cstring>
#include <queue>

using std::queue;
using std::vector;

struct node
{
bool have_value;
int val;
node *left,*right;
node():have_value(false),left(NULL),right(NULL){}
};

const int maxn=258;
bool failed;
node* root;

inline node* newnode()
{
return new node();
}

void remove_tree(node *now)
{
if(now==NULL)
return;
remove_tree(now->left);
remove_tree(now->right);
delete now;
}

{
int n=strlen(s);
node *u=root;
for(int i=0;i<n;i++)
{
if(s[i]=='L')
{
if(u->left==NULL)
u->left=newnode();
u=u->left;
}
else if(s[i]=='R')
{
if(u->right==NULL)
u->right=newnode();
u=u->right;
}
}
if(u->have_value)
failed=true;
u->val=v;
u->have_value=true;
return;
}

char s[maxn];

{
failed=false;
remove_tree(root);
root=newnode();
while(1)
{
if(scanf("%s",s)!=1)
return false;
if(!strcmp(s,"()"))
break;
int v;
sscanf(&s,"%d",&v);
}
return true;
}

bool bfs(vector<int> &ans)
{
queue<node*> q;
ans.clear();
q.push(root);
while(!q.empty())
{
node *now=q.front();
q.pop();
if(!now->have_value)
return false;
ans.push_back(now->val);
if(now->left!=NULL)
q.push(now->left);
if(now->right!=NULL)
q.push(now->right);
}
return true;
}

void print(vector<int> &ans)
{
for(int i=0;i<ans.size()-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[ans.size()-1]);
return;
}

int main()
{
vector<int> ans;
{
if(bfs(ans) && (!failed))
print(ans);
else
printf("not complete\n");
}
return 0;
}


UVA679

## 解题思路

#include <cstdio>

int main()
{
int D,I,l;
scanf("%d",&l);
while(l--)
{
scanf("%d %d",&D,&I);
int k=1;//一开始处于根节点
for(int i=1;i<D;i++)//往下走(D-1)层
{
k<<=1;//k先自乘2
if(!(I&1))//如果I是偶数
k|=1;//那么k要走右儿子
else
I+=1;//如果是奇数的话I先加1
I>>=1;//I自除以2
}
printf("%d\n",k);//打印出最后的k即可
}
return 0;
}


UVA12657

• X 移到 Y 的左侧
• Y 移到 X 的左侧
• 交换 XY
• 反转整个链

## 解题思路

inline void link(int L,int R)
{
l[R]=L,r[L]=R;
return;
}


• 4 操作可以直接打标记，因为反转两次即为正。但是对应的 12 操作都会发生变动
• 3 操作需注意 XY 相邻的情况，要进行特判
• 打了标记之后最后一步进行加和的时候要进行大减小操作
#include <cstdio>
#include <cctype>

typedef long long ll;

//快读省略

const int maxn=1e5+5;
int l[maxn],r[maxn];

{
l[R]=L,r[L]=R;
return;
}

int main()
{
int n,m,kase=0;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
l[i]=i-1;
r[i]=(i+1)%(n+1);
}
l=n;
r=1;

int op,x,y,inv=0;

while(m--)
{
if(op==4)
inv=!inv;
else
{
if(op==3 && r[y]==x)//如果x与y相邻，先进行交换操作方便后序调整
{
int t=x;
x=y;y=t;
}
if(op!=3 && inv)//打有标记的话1和2操作要反转
op=3-op;
if(op==1 && x==l[y])//忽略
continue;
if(op==2 && x==r[y])//忽略
continue;

int lx=l[x],ly=l[y],rx=r[x],ry=r[y];

if(op==1)
else if(op==2)
else if(op==3 && x!=y)
{
if(r[x]==y)//特判相邻的情况
else
}
}
}
int b=0;
ll ans=0;
for(int i=1;i<=n;i++)
{
b=r[b];
if(i&1)
ans+=b;
}
if(inv && n%2==0)//总个数为偶数且打了标记要用大减小
ans=(ll)n*(n+1)/2-ans;
printf("Case %d: %lld\n",++kase,ans);
}
return 0;
}


P1119

## 解题思路

for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j])


#include <cstdio>
#include <cctype>
#include <cstring>

{
char c = getchar();
int s = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return s;
}

inline int min(int a,int b)
{
return a<b?a:b;
}

const int maxn=205;
int n,m,t[maxn],f[maxn][maxn],q;

inline void floyd(int k)//更新信息的，通过给定可以中转的中转点来进行更新
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
return;
}

int main()
{
memset(f,0x3f,sizeof(f));//初始赋极大值 0x3f 不至于加起来爆int
for(int i=0;i<n;i++)
while(m--)
{
f[x][y]=f[y][x]=w;//双向边
}
int now=0;
while(q--)
{