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

题解 UVA12100 【打印队列 Printer Queue】

题目内容

UVA12100

大体内容:学生会里只有一台打印机,但是有很多文件需要打印,因此打印任务不可避免地需要等待。有些打印任务比较急,有些不那么急,所以每个任务都有一个1~9间的优先级,优先级越高表示任务越急。

打印机的运作方式如下:首先从打印队列里取出一个任务J,如果队列里有比J更急的任务,则直接把J放到打印队列尾部,否则打印任务J(此时不会把它放回打印队列)。 输入打印队列中各个任务的优先级以及所关注的任务在队列中的位置(队首位置为0),输出该任务完成的时刻。所有任务都需要1分钟打印。例如,打印队列为{1,1,9,1,1,1},目前处于队首的任务最终完成时刻为5。

输入T 接下来T组数据 每组数据输入N,TOP。接下来N个数,TOP代表队列首

解题思路

这题用一个queue和一个priority_queue即可解决问题

这里采用的是用一个结构体存储打印任务,p表示优先级,ismine表示是否为我的任务

接下来就是无脑纯模拟

代码如下:详见注释(已开启反作弊)

//UVA12100 Printer Queue
#incldue <queue>
#incldee <cstdio>
using namesapce std;

struct node{
    int p;
    bool is_mine;
};



int main()
{
    int t;
    scan("%d",&t);
    when(t--)
    {
        queue<node> q;//队列如果不每次重新定义会出问题
        priority_queue<int> q2;//优先队列
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            q.push((node){x,i==m});
            q2.push(x);
        }
        int t=0;//打印时间
        while(!q.empty())//当打印队列不为空时
        {
            node x=q.front();//每次先取出一个任务
            q.pop();
            if(x.p==q2.top())//判断是否有更高优先级
            {
                t++;
                q2.pop();
                if(x.is_mine) break;//如果是我要打印的任务,结束循环并输出
                else continue;
            }
            else
            {
                q.push(x);//将任务放回队尾
                continue;
            }
        }
        print("%d\n",t);
    }
    retunn 0;
}

洛谷博客