解题报告 P2822 组合数问题

题目内容

P2822

大意:给定 tkt 次给出 nm,询问所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right ) 有多少对 (i,j) 满足 k|\binom{i}{j}

解题思路

因为数据范围中 n,m\leq 2000,所以不能直接把组合数存储起来,而注意到一个数据点中 k 是固定的,因此可以定义 f_{i,j} 为对于所有的 x\in[0,i]y\in[0,\min(j,x)] 中满足 k|\binom x y\binom x y 的个数。

可以使用递推法预处理所有的 \binom i j\bmod k,然后使用二维前缀和来处理 f_{i,j},每次 O(1) 回答询问。

c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=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];//下面解释
    }

上面是处理 f 的部分。每次求出组合数直接取模方便判断是否能被 k 整除。二维前缀和的递推都很容易看懂,但是对于最后的 f[i][i+1]=f[i][i]; 的理解是:由于每次 f[i][j] 都要加上 f[i-1][j],而不处理最后的 f[i][i+1] 的话会造成处理下一排时 f[i-1][j] 为 0,所以要进行这样的处理。

还有就是数据中可能有 n,这时候要进行特判

完整代码:

#include <cstdio>
#include <cctype>

//快读

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=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--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m>n?n:m]);
    }
    return 0;
}

当然还有另一种方法就不需要特判,如下:

#include <cstdio>
#include <cctype>

inline int read()
{
    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[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=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--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m]);
    }
    return 0;
}

NOI Online 2020 Round 2 PJ 游记

前言

菜死了

Day 0

还在学校和文化课苦苦挣扎,差点忘了有这场比赛的存在

Day 1

最近几天一直腰痛(不排除 AS 的可能),遂中午一从学校出来就去了医院检查,谁知道医院 tm 没号了,遂苦逼的赶回家。

回到家想起来今天有 NOIOL,于是吃完饭打开电脑开始看题

第一眼:T1 模拟,T2 搜索,T3 dp,于是直接从 T2 开搞

看题面名字:荆轲刺秦王,我估摸着这就是一个普通的走迷宫然后存储状态就可以了,于是菜到爆的我写了两小时的暴搜,拍完样例后发现没问题就直接走了。

那时的我并没有意识到我处理士兵的方式是 O(n^3) 级别的,不 T 才怪,然后搜索也是傻傻的用 STL 搞,于是乎最后 55 pts 走人。

T1 第一眼看着没思路,分析了几分钟之后发现有点像贪心,然后就想到一个二分答案+前缀和水过去了,注意了下精度问题,发现无大碍,滚去看 T3,发现不会做,写了个输出随机数,卒。

期望得分:100+70+0

Day 2

官方题解出来了,发现 T2 要用差分,T3 是道计数(我没学过计数/kk)于是已经做好滚粗的准备(

Day x

出成绩了,刚好从学校回来,测了民间数据发现 T2 只有 55 分,结果确实只有 55 分,T3 的输出随机数一分没得(好吧我人品确实太惨了)只有 T1 所幸没被卡精度成功 AC。

总结:下次做任何题都要记得估计时间复杂度,不然像这次一样直接爆炸。

最终结果:100+55+0=155

解题报告 P2858 [USACO06FEB]Treats for the Cows G/S

题目内容

P2858

大意:n 个元素的序列,每次可以从头或者尾去掉一个元素,获得的收益是这个元素的权值乘上该次去除的次数,求最大收益。

解题思路

不难发现,这题由于去除元素的顺序对最终的结果是有影响的,所以不能直接贪心,考虑使用 dp。

这题一眼看上去像是一个区间 dp,那我们先开始寻找如何定义状态。考虑我们已经去除了 [i,j] 以外的所有元素,可以发现外面元素去除的顺序已经不重要了,满足无后效性,说明可以这样定义状态:f_{i,j} 表示还剩 [i,j] 时可以达到的最大收益。

转移:当我们达到 [i,j] 时,要么是去掉了第 i-1 个元素,要么是去掉了第 j+1 个元素,设当前的天数为 d,第 i 个元素为 v_i,则有状态转移方程

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

那么枚举区间长度的时候就必须从大到小枚举,为了方便可以在枚举区间长度的同时枚举天数

最后统计答案的时候答案为 ans=\displaystyle\max_{i=1}^n\lbrace f_{i,i}+nv_i\rbrace,输出即可。

#include <cstdio>
#include <cctype>

//快读

//max

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

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        v[i]=read();
    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;
}

当然,这题正序枚举区间长度也是可以的,只是倒序的更好理解我太菜不会

解题报告 UVA816 Abbott的复仇 Abbott’s Revenge

题目内容

原文在文末,须认真阅读。

大意:给定一个迷宫,进入某个交叉点的方向不同,允许走出的方向也不同,求出从起点到终点的最短路并输出路径,如无解,输出 No Solution Possible

解题思路

思路就是一个 bfs,第一次到达终点时一定是最短路,遍历每个节点的时候存储上一个状态就可以逆推回去了。状态使用三元组 (r,c,dir) 表示。

但是此题需要注意很多细节:

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

代码的思路参照了紫书,p[r][c][dir] 存储此状态的上一个状态,d[r][c][dir] 存储到达此状态的最短路(相当于vis),has_edge[r][c][dir][turn] 存储当前状态能不能朝 turn 方向转弯。

思路很明了,注意细节即可,顺便吐槽 UVa 的毒瘤 IO,同时需要仔细阅读英文题面理解题面的意思。

#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[10][10][4][4];
node p[10][10][4];
int d[10][10][4];


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;//注意行首空格
}

bool read_maze()
{
    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[0]);
            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);
    while(read_maze());
    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 四分树 Quadtrees

题目内容

UVA297

大意:一个 32*32 的黑白图像可以用一棵四分树表示,方法是用根节点表示整张图像,然后子树描述四个正方形,如果某个小正方形里面又有白色又有黑色,则这个儿子节点为灰色并且递归向下建树。

给出两棵四分树的前序遍历,求两张图合并起来之后的黑像素点个数。

解题思路

根据四分树的递归性,直接模拟填充颜色并统计并集的答案即可。

其中 draw(int x1,int y1,int w) 表示当前以 s_p 为根的四分树描述的是以 (x_1,y_1) 为左上角,边长为 w 的正方形区域。如果当前的根为灰色,则需要按顺序往四个子树递归(四个顺序就是象限的顺序),如果为黑色,说明整块区域都是黑色的,直接 O(w^2) 填充,白色的话直接不管即可。

#include <cstdio>
#include <cstring>

char s[1024+5];
int buf[33][33];
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 天平 Not so Mobile

题目内容

UVA839

以前序遍历的形式给出一棵二叉树天平,给出每边的力和力臂,求整个天平能不能平衡。

解题思路

首先是 IO,由于天平是以前序遍历的形式给出来的,因此考虑直接在递归读入并直接求解。

某个天平平衡当且仅当它的每一个子天平平衡且它自身平衡,所以当读入有子天平的天平时继续往子天平递归,然后返回上来的是描述是否平衡的 bool 值,同时本层也返回本身是否满足平衡即可。

#include <cstdio>
#include <cctype>

inline int read_int()
{
    //快读被省略了
}

bool read(int &W)//W参数为子天平重量的引用,可以很方便的往上层传子天平值
{
    int WL=read_int(),DL=read_int(),WR=read_int(),DR=read_int();
    bool b1=true,b2=true;
    if(!WL)//如果有左儿子
        b1=read(WL);
    if(!WR)
        b2=read(WR);//如果有右儿子
    W=WL+WR;//当前天平的重量
    return b1 && b2 && WL*DL==WR*DR;//左右儿子都平衡且自身平衡时为true
}

int main()
{
    int t=read_int();
    int W;
    while(t--)
    {
        printf("%s\n",read(W=0)?"YES":"NO");
        if(t)
            printf("\n");//最后不输出多余空行
    }
    return 0;
}

解题报告 UVA548 树 Tree

题目内容

UVA548

给定一棵二叉树的中序遍历和后序遍历,找出一个叶子节点,使得满足从根节点到该叶子节点经过的路径上节点编号的和最小的前提下该叶子节点的编号也最小

解题思路

思路非常类似于求先序排列,关键都是在于后序遍历序列的最后一位一定是该子树的根节点,由此进行向下的递归遍历整棵树并直接在递归的时候统计答案。

难点在于 IO,可先使用 getline() 直接读入一行然后再用 stringstream 提出每一个数字来。

代码中的 int build(int l1,int r1,int l2,int r2,int sum) 表示中序遍历为 in_o[l1]in_o[r1],后序遍历为 post_o[l2]post_o[r2]sum 表示当前从根节点到当前根节点的路径经过的点权总和。

#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;

void read(string s,int *a)
{
    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))
    {
        read(in,in_o);
        read(post,post_o);
        ans_sum=0x7f7f7f7f;
        build(0,n-1,0,n-1,0);
        cout<<ans<<endl;
    }
    return 0;
}

解题报告 UVA122 树的层次遍历 Trees on the level

题目内容

UVA122

大意:给定一棵二叉树,每个节点按照从根节点到它的移动序列(L 或 R)表示,如果能构成合法的二叉树,输出这棵二叉树的层次遍历,否则输出 not complete

解题思路

不能单纯的使用开一个很大的数组来堆式存储二叉树了,因为 2^{256}-1 会炸空间,所以需要使用指针来动态开点存储二叉树。

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

然后就是读入一棵树了:

char s[maxn];

bool read()
{
    failed=false;
    remove_tree(root);//释放内存
    root=newnode();//指定新的根节点
    while(1)
    {
        if(scanf("%s",s)!=1)//如果输入结束了
            return false;
        if(!strcmp(s,"()"))//如果一棵树到头了
            break;
        int v;//读入该节点的值使用
        sscanf(&s[1],"%d",&v);//sscanf大法好
        addnode(v,strchr(s,',')+1);//将逗号以后的所有值传入addnode函数进行开点操作
    }
    return true;
}

动态开点:

使用 new 操作符可以动态开一个空间,同样用 delete 可以释放空间:

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;
}

最后就是层次遍历了,可以使用 bfs 实现

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;
}

具体的思路就是动态开点,动态维护,然后进行 bfs。唯一的坑点是行末不能输出多余空格

#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;
}

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;
}

char s[maxn];

bool read()
{
    failed=false;
    remove_tree(root);
    root=newnode();
    while(1)
    {
        if(scanf("%s",s)!=1)
            return false;
        if(!strcmp(s,"()"))
            break;
        int v;
        sscanf(&s[1],"%d",&v);
        addnode(v,strchr(s,',')+1);
    }
    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;
    while(read())
    {
        if(bfs(ans) && (!failed))
            print(ans);
        else
            printf("not complete\n");
    }
    return 0;
}

解题报告 UVA679 小球下落 Dropping Balls

题目内容

UVA679

一棵满二叉树,深度为 D,每个非叶子节点有一个开关,所有开关初始为关。在根节点放一个小球,他会下落,小球到达某个开关时,如果开关关,则往左走,如果开关关,则往右走,并改变开关状态,求第 I 个小球下落到的叶子节点的编号

解题思路

不难写出模拟,但发现复杂度极高,所以会 TLE,需要思考性质。

发现:对于一个落到 k 节点的第 I 个小球,I 如果是单数,则说明这个小球要向左走,反之向右走,而且发现如果落下左边,则他是落到左边的儿子节点的第 (I+1)/2 个小球,如果落到右边则是落到右边儿子节点的第 I/2 个小球,于是我们可以只关注第 I 个小球,根据奇偶性判断小球应该往哪边走。

总的时间复杂度为 O(lD),可以通过本题。

#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;
}