解题报告 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;
}

解题报告 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;
}

解题报告 UVA12657 移动盒子 Boxes in a Line

题目内容

UVA12657

给定一排箱子,编号从左到右依次为 1n,四种操作:

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

完成所有操作后求从左到右所有奇数位上的箱子编号和

解题思路

可以使用链表进行模拟。

首先定义 link() 函数,link(x,y) 表示将 xy 连到一起:

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

其中 l 数组和 r 数组分别存储左右的箱子是什么,然后进行对应的模拟即可。

需要注意的是:

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

typedef long long ll;

//快读省略

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

inline void link(int L,int R)
{
    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[0]=n;
        r[0]=1;

        int op,x,y,inv=0;

        while(m--)
        {
            op=read();
            if(op==4)
                inv=!inv;
            else
            {
                x=read(),y=read();
                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)
                    link(lx,rx),link(ly,x),link(x,y);
                else if(op==2)
                    link(lx,rx),link(y,x),link(x,ry);
                else if(op==3 && x!=y)
                {
                    if(r[x]==y)//特判相邻的情况
                        link(lx,y),link(y,x),link(x,ry);
                    else
                        link(lx,y),link(y,rx),link(ly,x),link(x,ry);
                }
            }
        }
        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 灾后重建

题目内容

P1119

大意:给定编号从 1n-1 的村庄,每个村庄都被一定程度上损毁,而公路正常,在 t_i 时间前 i 号村庄不能通过,询问在 t 时间时 x 号和 y 号村庄能不能通车,如果能,最短路径是多少。

解题思路

这题思路真的很妙,让我们对 Floyd 的本质有了更深的理解,至少本蒟蒻是这样觉得的。

回归 Floyd 算法的本质:

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])

实际上,Floyd 是通过枚举中转点 k 来求得每个点之间的最短路,本质上是一种 dp。

然后,注意到本题中,每个村庄的恢复时间是递增的,且给出的询问的时间也是递增的。而题目让我们求任意两点的最短路,那么也可以抽象成 Floyd。具体的方法就是,由于时间是递增的,所以每到一个村庄恢复的时间点我们就可以让这个村庄成为那个可以用来中转的 k 来更新这一时间的所有最短路。

在这题中,就是使用时间戳,保证回答被询问的时间前信息被更新过即可。注意村庄编号从 0 开始

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

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

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()
{
    n=read(),m=read();
    memset(f,0x3f,sizeof(f));//初始赋极大值 0x3f 不至于加起来爆int
    for(int i=0;i<n;i++)
        t[i]=read(),f[i][i]=0;
    while(m--)
    {
        int x=read(),y=read(),w=read();
        f[x][y]=f[y][x]=w;//双向边
    }
    q=read();
    int now=0;
    while(q--)
    {
        int x=read(),y=read(),s=read();
        while(t[now]<=s && now<n)//将这一时间前的所有时间信息更新
            floyd(now++);
        if(t[x]>s || t[y]>s || f[x][y]>=0x3f3f3f3f)//如果这一时间时村庄未修复,或者无路线
            printf("-1\n");//输出 -1
        else
            printf("%d\n",f[x][y]);//否则输出最短路即可
    }
    return 0;
}