郑州轻工业大学2020年数据结构练习集

迷南。 2023-02-22 07:56 67阅读 0赞

# 郑州轻工业大学2020年数据结构练习集 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkwNjE0OQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkwNjE0OQ_size_16_color_FFFFFF_t_70 1]

按顺序：

## 函数题 ##

### 1 ###

List MakeEmpty()
    {
        
        List list;
    
        list = (List)malloc(sizeof(struct LNode));
        list->Last = -1;
    
        return list;
    }
    
    Position Find( List L, ElementType X )
    {
        
        int i;
    
        for(i = 0; i < MAXSIZE; i++)
        {
        
            if(L->Data[i] == X)
                return i;
        }
        return ERROR;
    }
    
    bool Insert( List L, ElementType X, Position P )
    {
        
        int i;
        if(L->Last == MAXSIZE-1)
        {
        
            printf("FULL");
            return false;
        }
        
        if(P < 0 || P > L->Last+1)
        {
        
            printf("ILLEGAL POSITION");
            return false;
        }
        
        for(i = L->Last; i >= P; i--)
        {
        
            L->Data[i+1] = L->Data[i];
        }
        L->Data[P] = X;
        L->Last++;
        
        return true;
    }
    
    bool Delete( List L, Position P )
    {
        
        int i;
        if(P < 0 || P > L->Last)
        {
        
            printf("POSITION %d EMPTY", P);
            return false;
        }
        
        for(i = P; i < L->Last; i++)
        {
        
            L->Data[i] = L->Data[i+1];
        }
        
        L->Last--;
        
        return true;    
    }

### 2 ###

List MakeEmpty() {
        
    	List p;
    	p=(Position)malloc(sizeof(struct LNode));
    	p->Data =0;
    	p->Next =NULL;
    	return p;
    }
     
    Position Find( List L, ElementType X ) {
        
    	List p=L;
    	while(p->Next) {
        
    		if(p->Next->Data==X) {
        
    			return p->Next;
    		}
    		p=p->Next ;
    	}
    	return ERROR;
    }
     
    bool Insert( List L, ElementType X, Position P ) {
        
    	Position tmp,pre;
    	pre=L;
    	while(pre->Next!=NULL && pre->Next !=P)
    		pre=pre->Next ;
     
    	if(pre->Next==P) {
        
    		tmp=(Position)malloc(sizeof(struct LNode));
    		tmp->Data=X;
    		tmp->Next=pre->Next;
    		pre->Next =tmp;
    		return true;
    	}	else {
        
    		printf("Wrong Position for Insertion\n");
    		return false;
    	}
     
     
    }
    bool Delete( List L, Position P ) {
        
    	Position tmp,pre;
    	pre=L;
    	while(pre->Next!=NULL &&pre->Next !=P)
    		pre=pre->Next ;
     
    	 if(pre->Next==P)  {
        
    		tmp=pre->Next ;
    		pre->Next =tmp->Next;
    		free(tmp);
    		return true;
    	}	
    	else
    	{
        
    		printf("Wrong Position for Deletion\n");
    		return false;}
    }

### 3 ###

void merge(int* a, int m, int* b, int n, int* c){
        
        int a_index = 0, b_index = 0;
        int c_index = 0;
        while(a_index < m && b_index < n){
        
            if(*(a + a_index) < *(b + b_index)){
        
                *(c + c_index) = *(a + a_index);
                c_index++, a_index++;
            }else{
        
                *(c + c_index) = *(b + b_index);
                c_index++, b_index++;
            }
        }
        while(a_index < m){
        
            *(c + c_index) = *(a + a_index);
            c_index++, a_index++;
        }
        while(b_index < n){
        
            *(c + c_index) = *(b + b_index);
            c_index++, b_index++;
        }
    }

### 4 ###

List Delete( List L, ElementType minD, ElementType maxD )
    {
        
        int i,sum=0;
        if(!L || minD >= maxD) return L;
        for(i=0;i<=L->Last;i++)
        {
        
            if(L->Data[i]>minD && L->Data[i]<maxD )
                sum++;
            else L->Data[i-sum]=L->Data[i];
        }
        L->Last-=sum;
        return L;
    }

### 5 ###

List Insert( List L, ElementType X )
    {
        
        List head = L;///头结点 无信息
        L = L->Next;///转到第一个结点
        List p = (List)malloc(sizeof(struct Node));
        p->Data = X;
        p->Next = NULL;
        List q = head;///初始为头结点
        if(L == NULL)///空链表
        {
        
            head->Next = p;
            return head;
        }
        while(L->Data < X)
        {
        
            q = L;
            L = L->Next;
            if(L->Next == NULL)///链表尾
            {
        
                L->Next = p;
                return head;
            }
        }
        p->Next = L;//插在中间
        q->Next = p;
        return head;
    }

### 6 ###

List Merge( List L1, List L2 )
    {
        
        List p1, p2, p3, L;
        L = (List)malloc(sizeof(struct Node));
        p1 = L1->Next;
        p2 = L2->Next;
        p3 = L;
        while (p1 && p2){
        
            if (p1->Data <= p2->Data){
        
                p3->Next = p1;
                p3 = p1;
                p1 = p1->Next;
            } else {
        
                p3->Next = p2;
                p3 = p2;
                p2 = p2->Next;
            }
        }
        p3->Next = p1 ? p1 : p2;
        L1->Next = NULL;
        L2->Next = NULL;
        return L;
    }

### 7 ###

ElementType Find( List L, int m )
    {
        
    	List p1,p2;
    	p1=L->Next;
    	p2=L->Next;
    	int i=0;
    	int flag=0;
    	for(i=0;i<m;i++)
    	{
        
    		if(p2==NULL)
    		{
        
    			flag=1;
    			break;
    		}
    	    p2=p2->Next;
    	}
    	if(flag!=1)
    	{
        
    		while(p2)
    		{
        
    			p1 = p1->Next;
    	        p2 = p2->Next;
    		}
    	        return p1->Data;
    	}
        else
             return ERROR;
    }

### 8 ###

bool Push( ElementType X, Deque D )
    {
        
    	if((D->Rear+1)%(D->MaxSize)==D->Front)
    		return false;
    	D->Front--;
    	D->Front=(D->MaxSize+D->Front)%(D->MaxSize);
    	D->Data[D->Front]=X;
    	return true;
    } 
    ElementType Pop( Deque D )
    {
        
    	if(D->Front==D->Rear)
    		return ERROR;
    	ElementType d=D->Data[D->Front];
    	D->Front++;
    	D->Front=D->Front%(D->MaxSize);
    	return d;
    } 
    bool Inject( ElementType X, Deque D )
    {
        
    	if((D->Rear+1)%(D->MaxSize)==D->Front)
    		return false;
    	D->Data[D->Rear]=X;
    	D->Rear=(D->Rear+1)%D->MaxSize;
    	return true;
    } 
    ElementType Eject( Deque D )
    {
        
    	if(D->Front==D->Rear)
    		return ERROR;
    	if(!D->Rear)
    		D->Rear=D->MaxSize;
    	D->Rear--;
    	ElementType d=D->Data[D->Rear];
    	return d;
    }

### 9 ###

int GetHeight(BinTree BT){
        
        int cnt =0; 
        if(BT){
        
            int l,r;
            l=GetHeight(BT->Left);
            r=GetHeight(BT->Right);
            if(l>r)cnt=l+1;else cnt=r+1;
        }
        return cnt;
    }

### 10 ###

void InorderTraversal( BinTree BT )
    {
        
      if(BT){
        
        InorderTraversal(BT->Left);
        printf(" %c",BT->Data);
        InorderTraversal(BT->Right);
      }
    }
    void PreorderTraversal( BinTree BT )
    {
        
      if(BT)
      {
        
        printf(" %c",BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
      }
    }
    void PostorderTraversal( BinTree BT )
    {
        
      if(BT)
      {
        
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c",BT->Data);
      }
    }
    void LevelorderTraversal( BinTree BT )
    {
        
      BinTree p;
      BinTree q[50];
      int head=0;int tail=0; 
      if(BT)
      {
        
        q[tail++]=BT;
        while(head!=tail)
        {
        
          p=q[head++];
        printf(" %c",p->Data);
        if(p->Left!=NULL)
        {
        
          q[tail++]=p->Left;
        }
        if(p->Right!=NULL)
        {
        
          q[tail++]=p->Right;
        }
        }
      }
    }

### 11 ###

void InorderTraversal( BinTree BT ){
        
        Stack s=CreateStack();
        if(BT!=NULL)
            Push(s,BT);
        BinTree now;
        while(!IsEmpty(s)){
        
            while(Peek(s)->Left!=NULL)
                Push(s,Peek(s)->Left);
            while(!IsEmpty(s)){
        
                now=Peek(s);
                printf(" %c",now->Data);
                Pop(s);
                if(now->Right!=NULL){
        
                    Push(s,now->Right);
                    break;
                }
            }
        }
    }
    
    void PreorderTraversal( BinTree BT ){
        
    
        Stack s=CreateStack();
       //Push(s,BT);
        BinTree now=BT;
        if(now!=NULL)
            Push(s,now);
        while(!IsEmpty(s)){
        
            now=Pop(s);
            printf(" %c",now->Data);
            if(now->Right!=NULL)
                Push(s,now->Right);
            if(now->Left!=NULL)
                Push(s,now->Left);
        }
    }
    
    void PostorderTraversal( BinTree BT ){
        
        Stack s=CreateStack();
        if(BT!=NULL)
            Push(s,BT);
        BinTree now=BT,last=NULL;
        while(!IsEmpty(s)){
        
            while(Peek(s)->Left!=NULL)
                Push(s,Peek(s)->Left);
            while(!IsEmpty(s)){
        
                now=Peek(s);
                if(now->Right==last||now->Right==NULL){
        
                    printf(" %c",now->Data);
                    Pop(s);
                    last=now;
                }
                else{
        
                    Push(s,now->Right);
                    break;
                }
            }
        }
    }

### 12 ###

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
    /*第一个参数是传入二维数组的头地址（即图）
    第二个参数是结点编号
    第三个参数是传入Visit()这个函数的地址（可以自行百度函数是怎么作为参数传递的）*/
    {
        
        /*从第V个顶点出发递归地深度优先遍历图G*/
        int i;
        Visited[V] = true;//标记为true，说明已经遍历过了
        Visit(V); //打印出V这个结点
        for(i = 0; i < Graph->Nv; i++) //遍历V的每个邻接点
        {
        
            if(Graph->G[V][i] == 1 && !Visited[i])
            /*Graph->G[V][i] == 1说明有结点，!Visited[i]为真，说明未遍历过*/
            {
        
               DFS(Graph, i, Visit); //递归调用DFS
            }
        }
    }

### 13 ###

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) )
    {
        
     Visited[S]=true;//标记起始点 
     Visit(S);
     int queue[1000],front=0,rear=0;
     queue[rear++]=S;//起始点入队列 
     PtrToAdjVNode temp;//temp就代表当前点的邻接点的下标 
     while(front<rear){
        //队伍不为空 
      temp=Graph->G[queue[front++]].FirstEdge;
      while(temp){
        
       int p=temp->AdjV;//把temp中的下标提取出来 
       if(!Visited[p]){
        //如果p点没有被标记的话 
        Visited[p]=true;
        Visit(p);
        queue[rear++]=p;//储存在队列中 
       }
       temp=temp->Next;//指向下一个邻接点 
      }
     }
    }

### 14 ###

BinTree Insert( BinTree BST, ElementType X )
    {
        
    	if(BST==NULL)
    	{
        
    		BinTree gg=(BinTree)malloc(sizeof(struct TNode));
    		gg->Data=X;
    		gg->Left=NULL;
    		gg->Right=NULL;
    		BST=gg;
    		return BST;
    	}
    	else
    	{
        
    		BinTree hh=BST,parent;
    		int flag;
    		while(hh!=NULL)
    		{
        
    			parent=hh;
    			if(X>hh->Data)
    			hh=hh->Right,flag=1;
    			else
    			hh=hh->Left,flag=0;
    		}
    		BinTree tmp=(BinTree)malloc(sizeof(struct TNode));
    		tmp->Data=X;
    		tmp->Left=NULL;
    		tmp->Right=NULL;
    		hh=tmp;
    		if(flag)parent->Right=hh;
    		else parent->Left=hh;
    		return BST;
    	}
    }
    Position Find( BinTree BST, ElementType X )
    {
        
    	if(BST)
    	{
        
    		while(BST)
    		{
        
    			if(X==BST->Data)return BST;
    			else if(X>BST->Data)
    			BST=BST->Right;
    			else if(X<BST->Data)
    			BST=BST->Left;	
    		}
    	} 
    	return BST;
    }
    Position FindMin( BinTree BST )//找到搜索二叉树中最小值 
    {
        
    	BinTree gg=NULL;
    	if(BST)
    	{
        
    		while(BST)
    		gg=BST,	BST=BST->Left;
    	}
    	return gg;
    }
    Position FindMax( BinTree BST )//找到搜索二叉树最大值 
    {
        
    	BinTree gg=NULL;
    	if(BST)
    	{
        
    		while(BST)
    		gg=BST,BST=BST->Right;
    	}
    	return gg;
    }
    BinTree Delete( BinTree BST, ElementType X )
    {
        
    	//删除处理的关键在于 删除这个节点
    	//之后还要就是将后面是节点给补上去 
    	Position tmp;  
        if(!BST)
    	{
        
    		printf("Not Found\n");
    		return BST; 
    	}
    	else if(X<BST->Data)
    	BST->Left=Delete(BST->Left,X);
    	else if(X>BST->Data)
    	BST->Right=Delete(BST->Right,X);
    	else
    	{
        
    		 if(BST->Left && BST->Right) {
                       /* 被删除的结点有左右子结点 */
                tmp=FindMin(BST->Right);                /* 在右子树中找到最小结点填充删除结点 */
                BST->Data = tmp ->Data;
                BST->Right=Delete(BST->Right,BST->Data);/* 递归删除要删除结点的右子树中最小元素 */
    			//这一步无法理解  
    		}else 
    		{
        
    			if(!BST->Left)
    			BST=BST->Right;
    			else if(!BST->Right)
    			BST=BST->Left;
    		}
    	} 
    	return BST; 
    }

## 编程题 ##

### 1 ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct PolyNode* Polynomial;
    
    struct PolyNode{
        
        int coef;
        int expon;
        Polynomial next;
    };
    
    Polynomial ReadPoly();
    Polynomial Mult(Polynomial P1,Polynomial P2);
    void PrintPoly(Polynomial PP);
    Polynomial Add(Polynomial P1,Polynomial P2);
    
    int main() //程序框架搭建
    {
        
        Polynomial P1, P2, PP, PS;
        P1 = ReadPoly();
        P2 = ReadPoly();
    
        PP = Mult(P1, P2);
        PrintPoly(PP);
    
        PS = Add(P1, P2);
        PrintPoly(PS);
    
        return 0;
    }
    
    //对Rear指针的处理：1.初值为NULL,根据是否为空做不同处理；2.指向一个空节点
    //*pRear当前结果表达式尾项指针的指针
    //函数实现在pRear后面插入节点
    void Attach(int c, int e, Polynomial *pRear)
    {
        
        Polynomial P;
        P = (Polynomial)malloc(sizeof(struct PolyNode));
        P->coef = c;
        P->expon = e;
        P->next = NULL;
        (*pRear)->next = P;
        *pRear = P;
    }
    
    Polynomial ReadPoly()
    {
        
        Polynomial P, Rear, t;
        int c, e, N;
        scanf("%d", &N);
        P = (Polynomial)malloc(sizeof(struct PolyNode)); //链表头空节点
        P->next = NULL;
        Rear = P;
        while (N--)
        {
        
            scanf("%d %d", &c, &e);
            if (c != 0)
               Attach(c, e, &Rear); //将当前项插入多项式尾部
        }
        t = P;
        P = P->next;
        free(t); //删除临时生成的头结点
        return P;
    }
    
    Polynomial Add(Polynomial P1, Polynomial P2)
    {
        
        Polynomial t1, t2;
        t1 = P1;
        t2 = P2;
        //生成新的头结点
        Polynomial P,t;
        P = (Polynomial)malloc(sizeof(struct PolyNode));
        P->next = NULL;
        Polynomial Rear;
        Rear = P;
        while (t1&&t2)
        {
        
            if (t1->expon==t2->expon)
            {
        
                if (t1->coef+t2->coef)  //系数和为0时不添加到尾节点上  /*考虑周全*/
                {
        
                    Attach(t1->coef + t2->coef, t1->expon, &Rear);
                }
                t1 = t1->next;
                t2 = t2->next;
            }
            else if (t1->expon>t2->expon)
            {
        
                Attach(t1->coef, t1->expon, &Rear);
                t1=t1->next;
            }else
            {
        
                Attach(t2->coef, t2->expon, &Rear);
                t2 = t2->next;
            }
        }
        while (t1)
        {
        
            Attach(t1->coef, t1->expon, &Rear);
            t1 = t1->next;
        }
        while (t2)
        {
        
            Attach(t2->coef, t2->expon, &Rear);
            t2 = t2->next;
        }
        t = P;
        P = P->next;
        free(t);
        return P;
    }
    
    //多项式乘法方法：
    //1. 将乘法运算转换为加法运算，让P1的每一项和P2相乘，在加到结果多项式中
    //2. 逐项插入，将P1当前项乘P2当前项，在插入到结果表达式中，关键是要找到插入的位置
    
    Polynomial Mult(Polynomial P1, Polynomial P2)
    {
        
        Polynomial P, Rear;
        Polynomial t1, t2, t;
        if (!P1||!P2)
        {
        
            return NULL;
        }
        t1 = P1;
        t2 = P2;
        P = (Polynomial)malloc(sizeof(struct PolyNode));
        Rear = P;
        while (t2)
        {
        
            //先用P1的第一项乘以P2,得到初始结果多项式
            Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
            t2 = t2->next;
        }
        t1 = t1->next;
        while (t1)
        {
        
            t2 = P2;
            Rear = P; //将尾节点置到头结点来
            while (t2)
            {
        
                int e = t1->expon + t2->expon;
                int c = t1->coef * t2->coef;   //以后的每一项相乘的结果
                while (Rear->next&&Rear->next->expon>e) //找插入位置
                {
        
                    Rear = Rear->next;
                }
                if (Rear->next&&Rear->next->expon==e)
                {
        
                    if (Rear->next->coef+c) //判系数是否为0
                    {
        
                        Rear->next->coef += c;
                    }
                    else  //为0删除节点
                    {
        
                        t = Rear->next;
                        Rear->next = t->next;
                        free(t);
                    }
                }
                else  //插入位置
                {
        
                    t = (Polynomial)malloc(sizeof(struct PolyNode));
                    t->coef = c;
                    t->expon = e;
                    t->next = Rear->next;
                    Rear->next = t;
    
                    Rear = Rear->next;
                }
                t2 = t2->next;
            }
            t1 = t1->next;
        }
        t2 = P;
        P = P->next;
        free(t2);
    
        return P;
    }
    
    void PrintPoly(Polynomial P)
    {
        
        int flag = 0;//辅助调整输出格式
        if (!P)
        {
        
            printf("0 0\n"); /*格式*/
            return;
        }
        while (P)
        {
        
            if (!flag) //第一次
            {
        
                flag = 1;
            }
            else
            {
        
                printf(" ");
            }
            printf("%d %d", P->coef, P->expon);
            P = P->next;
        }
        printf("\n");
    }

### 2 ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int Position;
    typedef int ElementType;
    typedef struct Node *PtrToNode;
    struct Node {
        
        Position Address;
        ElementType Data;
        Position Next;
        PtrToNode   Nextptr;
    };
    typedef PtrToNode List;
    
    #define MaxSize 100000
    struct Node arr[MaxSize];
    
    List ReadList(Position firstAddr, int *length)
    {
        
        int i, list_size;
        Position addr, pos;
        List L, p, temp;
        L = (List)malloc(sizeof(struct Node)); L->Nextptr = NULL;
        p = L;
        memset(&arr, -1, sizeof(struct Node));
    
        for ( i = 0; i < (*length); ++i ) {
        
            scanf("%d", &addr);
            arr[addr].Address = addr;
            scanf("%d %d", &arr[addr].Data, &arr[addr].Next);
        }
    
        list_size = 0;
        pos = firstAddr;
        while (arr[pos].Address != -1) {
        
            p->Nextptr = &arr[pos];
            p = p->Nextptr;
            ++list_size;
            if (arr[pos].Next == -1)
                break;
    
            pos = p->Next;
        }
    
        *length = list_size;
        temp = L; L = L->Nextptr; free(temp);
        return L;
    }
    
    List Reverse(List L, int reverse_length)
    {
        
        List p1, p2, p3, rear;
        p1 = L; p2 = L->Nextptr; p3 = p2->Nextptr;
    
        while (reverse_length--) {
        
            p2->Nextptr = p1;
            p1 = p2;
            p2 = p3;
            if(p3) p3 = p3->Nextptr;
        }
        rear = L->Nextptr;
        rear->Nextptr = p2;
        L->Nextptr = p1;
        return rear;
    }
    
    List ReverseList(List L, int length, int reverse_length)
    {
        
        if (reverse_length == 1)
            return L;
    
        int t;
        List head, p, temp;
        head = (List)malloc(sizeof(struct Node)); head->Nextptr = L;
        p = head;
        t = length / reverse_length;
        while (t--) {
        
            p = Reverse(p, reverse_length);
        }
        if (length % reverse_length == 0)
            p->Nextptr = NULL;
        temp = head;
        head = head->Nextptr;
        free(temp);
        return head;
    }
    
    void PrintList( List L )
    {
        
        List p;
        p = L;
        while (p) {
        
            if (!p->Nextptr)
                printf("%.5d %d %d\n", p->Address, p->Data, -1);
            else
                printf("%.5d %d %.5d\n", p->Address, p->Data, p->Nextptr->Address);
            p = p->Nextptr;
        }
    }
    
    int main()
    {
        
        Position firstAddr;
        int N, K;
        List L;
        scanf("%d %d %d", &firstAddr, &N, &K);
    
        L = ReadList(firstAddr, &N);
        L = ReverseList(L, N, K);
        PrintList(L);
    
        return 0;
    }

### 3 ###

#include<stdio.h>
    #define maxsize 1003
    int main()
    {
        
        char stack[maxsize]; int top=-1;
        char ch[maxsize],ch1[maxsize],ch2[maxsize];
        int i,j,k=0;
        ch1['(']=')';
        ch1['[']=']';
        ch1['{']='}';
        ch1['<']='>';
        while(1)    //此函数地目的是，依次输入所有字符，当遇到字符为括号符时，存入数组ch2;
        {
        
            gets(ch);          //看样例3，里面有0.1这个小数点。再加上结束的标记是某一行只有一个小数点和一个回车，因此，一行字符一行字符地输入。
            if(ch[0]=='.'&&ch[1]=='\0') break;
            for(j=0;ch[j]!='\0';j++)   
            {
        
                if(ch[j]=='('||ch[j]==')'||ch[j]=='['||ch[j]==']'||ch[j]=='{'||ch[j]=='}')
                ch2[k++]=ch[j];
                else if(ch[j]=='/'&&ch[j+1]=='*')   //因为这里有j和j+1，所以，完成后j需要加1；
                {
        ch2[k++]='<';j++;}
                else if(ch[j]=='*'&&ch[j+1]=='/')
                {
        ch2[k++]='>';j++;}
            }
        }
        int flag=1;
        for(i=0;i<k;i++)
        {
        
            if(ch2[i]=='('||ch2[i]=='['||ch2[i]=='{'||ch2[i]=='<')
                stack[++top]=ch2[i];
            if(ch2[i]==')'||ch2[i]==']'||ch2[i]=='}'||ch2[i]=='>')
            {
        
                if(top!=-1&&ch1[stack[top]]==ch2[i])   
                top--;
                else
                {
        
                     printf("NO\n");
                     if(top==-1)  //缺左边符号
                     {
        
                         if(ch2[i]==')') printf("?-)");
                         else if(ch2[i]==']') printf("?-]");
                         else if(ch2[i]=='}') printf("?-}");
                         else if(ch2[i]=='>') printf("?-*/");
    
                     }
                     else if(top!=-1&&ch1[stack[top]]!=ch2[i])   //缺右边符号
                     {
        
                         if(stack[top]=='(') printf("(-?");
                         else if(stack[top]=='[') printf("[-?");
                         else if(stack[top]=='{') printf("{-?");
                         else if(stack[top]=='<') printf("/*-?");
                     }
                     flag=0;
                     break;              //只要检测到不匹配，就结束
                }
            }
        }
        if(flag==1&&top==-1)   //只有再栈为空时才可能输出yes；
        printf("YES");
        else if(flag==1&&top!=-1)   //当输入字符为[[[]时，虽然flag=1，但是也是错误的
        {
        
            printf("NO\n");
            if(stack[top]=='(') printf("(-?");                //跟上面一样
            else if(stack[top]=='[') printf("[-?");
            else if(stack[top]=='{') printf("{-?");
            else if(stack[top]=='<') printf("/*-?");
        }
        return 0;
    }

### 4 ###

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    char str[27];
    int len;
    char stack[27];
    int top=0;
    int index=0;
     
    int IsNum(char c)
    {
        
    	if(c>='0'&&c<='9'||c=='.')
    	  return 1;
    	else 
    	  return 0;
    } 
     
    int compare(char a,char b)
    {
        
    	if(b==')')return 1;
    	if(a=='('||b=='(')return 0;
    	switch(b)
    	{
        
    		case '+':
    		case '-':
    			return 1;
    		case '*':
    		case '/':
    			switch(a){
        
    				case '+':
    			    case '-':
    			    	return 0;
    			    case '*':
    			    case '/':
    			    	return 1;
    			}
    	}
    }
     
    int ZhengFu(char a)
    {
        
    	if(a=='+'||a=='-')
    	 return 1;
    	else 
    	 return 0;
    }
     
    void Mainfun()
    {
        
    	int space=0; 
    	for(index=0;index<len;index++)
    	{
        
    		//先判断是否为数字，为数字就输出 
    		if(IsNum(str[index]))
    		{
        
    			if(space==1)
    			{
        
    				printf(" ");
    				space =0;
    			}
    			printf("%c",str[index]);
    		}
    		//+ - 这两个符号要进一步判断是否是正负号
    		//判断符号为+-号 并且是在第一位 或者 前一位不是数字和‘）’ 那么这个就是正负号 
    		else if(ZhengFu(str[index])&&( (index==0) || (IsNum(str[index-1])!=1&&str[index-1]!=')') ))
    		{
        
    			//如果是正负号，那么符号需要输出，正号不需要输出
    			if(str[index]=='-')
    			{
        
    				if(space==1)
    				{
        
    					printf(" ");
    					space=0;
    				}
    				printf("%c",str[index]);
    			} 
    		}
    		//如果是运算符 
    		else
    		{
        
    			if(top!=0)   //栈内有运算符，需要比较 
    			{
        
    				if(str[index]==')')    //如果是')',就要输出'('之前的所有运算符 
    				{
        
    					while(top--)
    					{
        
    						if(stack[top]=='(')break;
    						else printf(" %c",stack[top]);
    					} 
    				}
    				else
    				{
        
    					while(top!=0)
    					{
        
    						if(compare(stack[top-1],str[index]))   //来比较运算符 
    						  printf(" %c",stack[--top]);
    						else
    						  break;
    					}
    					stack[top++]=str[index];
    				}
    			} 
    			else   //栈为空，直接入栈 
    			{
        
    				stack[top++]=str[index];
    			}
    			int j;
    			for(j=0;j<top;j++)
    			 if(stack[j]!='(')
    			 {
        
    			 	space=1;
    			 	break;
    			 }
    		}
    	}
    	while(top!=0)
    	 printf(" %c",stack[--top]);
    }
     
    int main()
    {
        
    	scanf("%s",str);
    	len=strlen(str);
    	
    	Mainfun();
    	return 0;
    }

### 5 ###

#include<stdio.h>
    #include<stdlib.h>
    struct st
    {
        
    	int date[1005];
    	int front,rear;
    };
    typedef struct st *Qnode;
    typedef Qnode queue;
    int main()
    {
        
    	int n;
    	scanf("%d",&n);
    	queue q1,q2;
    	q1=(queue)malloc(sizeof(st));//c创建奇数队列q1 
    	q2=(queue)malloc(sizeof(st));//创建偶数队列q2 
    	q1->rear=q2->rear=q1->front=q2->front=0;//初始化q1 q2 
    	while(n--)
    	{
        
    		int m;
    		scanf("%d",&m);
    		if(m%2) {
        //如果是奇数就存在q1 
    			q1->date[q1->rear]=m;
    			q1->rear++;
    		}
    		else {
        //如果是偶数就存在q2 
    			q2->date[q2->rear]=m;
    			q2->rear++;
    		}
    	}
    	//队列就相当于一个结构体里面嵌套了一个数组然后用front和rear来指向队首和队尾进而模拟这个操作
    	//入队的话相当于rear向后移出队的话就相当于front向后移 
    	while(q1->front!=q1->rear)//模拟出队的过程 如果q1->front不等于q2->rear就让front向后移 
    	{
        
    		int cnt=2,i=0;
    		//cnt 记录每次要输出两个个数i是用来控制空格的 
    		while(cnt--&&q1->front!=q1->rear){
        
    			// 
    			if(i++) printf(" ");//奇数的第一个前面不加空格其他都加  
    			printf("%d",q1->date[q1->front]);//输出这个队首的元素
    			//同时让front后移 
    			q1->front++;
    		}
    		if(q2->front!=q2->rear){
        //同上 
    			printf(" %d ",q2->date[q2->front]);
    			q2->front++;
    		}
    	}
    	int cnt=0;
    	while(q2->rear!=q2->front){
        
    		//如果奇数输出完了还有偶数就让偶数输出道理相同cnt是控制空格的 个人习惯这样你也可以换其他的方法 
    		if(cnt++) printf(" ");
    		printf("%d",q2->date[q2->front]);
    		q2->front++;
    	}
    	return 0; 
    }

### 6 ###

#include<iostream>
    #include<stack>
    #include<algorithm>
    using namespace std;
    int main()
    {
        
    	stack<int>a, b;
    	int c, d;
    	cin >> c >> d;
    	if (c > d)swap(c, d);//让1为小栈
    	while (1)
    	{
        
    		char temp1;
    		cin >> temp1;
    		if (temp1 == 'T')
    			break;
     
    		if (temp1 == 'A')
    		{
        
    			int temp2;
    			cin >> temp2;
    			if (a.size() < c)//1栈没满
    			{
        
    				a.push(temp2);
    			}
    			else
    			{
        
    				if (b.empty())//2栈为空
    				{
        
    					while (!a.empty())
    					{
        
    						int temp = a.top(); a.pop();
    						b.push(temp);
    					}
    					a.push(temp2);
    				}
    				else
    				{
        
    					cout << "ERROR:Full" << endl;
    				}
    			
    			}
    		}
    		else if (temp1 == 'D')
    		{
        
    			if (!b.empty())//2栈不空
    			{
        
    				int  temp = b.top(); b.pop();
    				cout << temp << endl;
    			}
    			else//2栈为空
    			{
        
    				if (!a.empty())//1栈不空
    				{
        
    					while (!a.empty())
    					{
        
    						int temp = a.top(); a.pop();
    						b.push(temp);
    					}
    					int  temp = b.top(); b.pop();
    					cout << temp << endl;
    				}
    				else//1栈也为空
    				{
        
    					cout << "ERROR:Empty" << endl;
    				}
    			}
    		
    		}
     
     
    	}
    	
     
     
    }

### 7 ###

#include<stdio.h>
    #include <iostream>
    #include<string>
    #include<cstring>
    using namespace std;
    int main()
    {
        
        char s1[1000001];
        scanf("%s",s1);
        int N;
        cin >> N;
        char s2[10][100001];
        for(int i = 0;i<N;i++)
        {
        
            cin>>s2[i];
        }
        string s3[10];
        char *s;
        for(int i = 0;i<N;i++)
        {
        
            //s3[i] = strstr(s1,s2[i]);
            //strcpy(s3[i],strstr(s1,s2[i]));
            s = strstr(s1,s2[i]);
            if(s==NULL)
            {
        
                s3[i] = "Not Found";
            }
            else
            {
        
                s3[i] = s;
            }
     
        }
        for(int i = 0;i<N;i++)
        {
        
            cout << s3[i]<<endl;
        }
        return 0;
    }

### 8 ###

#include <iostream>
    #include <vector>
     
    using namespace std;
     
    #define Max_Node 11
    #define END -1
     
    typedef struct node
    {
        
        char value;
        int left;
        int right;
    }Node;
     
    void CreateTree(vector<Node>& Tree,int N)//获取树的输入，并将输入的字符合理转化成整型数字
    {
        
        
        char value,left,right;
        for (int i=0; i<N; ++i)
        {
        
            cin>>value>>left>>right;
            Tree[i].value=value;
            
            if (left=='-')
            {
        
                Tree[i].left=END;
            }else
            {
        
                Tree[i].left=left-'0';
            }
            
            if (right=='-')
            {
        
                Tree[i].right=END;
            }else
            {
        
                Tree[i].right=right-'0';
            }
        }
    }
     
    int FindTreeRoot(vector<Node>& Tree,int N)//寻找树的树根（树根没有其它的结点指向它）
    {
        
        int Flag[Max_Node];
        for (int i=0; i<N; ++i)
        {
        
            Flag[i]=0;
        }
        
        for (int i=0; i<N; ++i)
        {
        
            if (Tree[i].left!=END)
            {
        
                Flag[Tree[i].left]=1;
            }
            if (Tree[i].right!=END)
            {
        
                Flag[Tree[i].right]=1;
            }
        }
        
        int k;
        for (k=0; k<N; ++k)
        {
        
            if (Flag[k]==0)
            {
        
                break;
            }
        }
        return k;
    }
     
    bool IsOmorphic(int Root1,int Root2,vector<Node>& Tree1,vector<Node>& Tree2)//递归判断两树是否同构
    {
        
        if (Tree1[Root1].value==Tree2[Root2].value)
        {
        
            //两结点相等，并都是叶子结点
            if (Tree1[Root1].left==END && Tree1[Root1].right==END && Tree2[Root2].left==END && Tree2[Root2].right==END)
            {
        
                return true;
            }
            
            //以下四种情况都是，两个结点都是有一个孩子为空，另一个子树不空且这两个孩子相等的情形
            if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].right==END && Tree2[Root2].right==END)
            {
        
                return IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2);
            }
            if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].right==END && Tree2[Root2].left==END)
            {
        
                return IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2);
            }
            if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].left==END && Tree2[Root2].right==END)
            {
        
                return IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2);
            }
            if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].left==END && Tree2[Root2].left==END)
            {
        
                return IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2);
            }
            
            //以下两种情形，两个结点的孩子都相等
            if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value)
            {
        
                return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2));
            }
            if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value)
            {
        
                return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2));
            }
        }
        //不符合以上7种情况的其它情况都说明这两棵树不同构
        return false;
    }
     
    int main(int argc, const char * argv[])
    {
        
        //Input
        int N1=0;
        cin>>N1;
        vector<Node> Tree1(Max_Node);
        CreateTree(Tree1,N1);
        int N2=0;
        cin>>N2;
        vector<Node> Tree2(Max_Node);
        CreateTree(Tree2,N2);
        
        
        if (N1!=N2)
        {
        
            cout<<"No";
        }else
        {
        
            if (N1==0)
            {
        
                cout<<"Yes";
            }else
            {
        
               
        
                //Build Tree
                int root1=FindTreeRoot(Tree1,N1);
                int root2=FindTreeRoot(Tree2,N2);
        
                //Judge
                if (IsOmorphic(root1, root2, Tree1, Tree2))
                {
        
                    cout<<"Yes";
                }else
                {
        
                    cout<<"No";
                }
            }
        
        }
        return 0;
    }

### 9 ###

#include <cstdio>
    #include <cstring>
    #include <ctype.h>
    #include <cstdlib>
    #include <cmath>
    #include <climits>
    #include <ctime>
    #include <iostream>
    #include <algorithm>
    #include <deque>
    #include <vector>
    #include <queue>
    #include <string>
    #include <map>
    #include <stack>
    #include <set>
    #include <numeric>
    #include <sstream>
    #include <iomanip>
    #include <limits>
    
    #define CLR(a) memset(a, 0, sizeof(a))
    #define pb push_back
    
    using namespace std;
    typedef long long ll;
    typedef long double ld;
    typedef unsigned long long ull;
    typedef pair <int, int> pii;
    typedef pair <ll, ll> pll;
    typedef pair<string, int> psi;
    typedef pair<string, string> pss;
    
    const double PI = 3.14159265358979323846264338327;
    const double E = exp(1);
    const double eps = 1e-30;
    
    const int INF = 0x3f3f3f3f;
    const int maxn = 1e2 + 5;
    const int MOD = 1e9 + 7;
    
    int v[10];
    
    struct Node
    {
        
        int l, r;
    }q[10];
    
    void init()
    {
        
        CLR(q);
        CLR(v);
    }
    
    queue <int> Q;
    vector <int> ans;
    
    void bfs()
    {
        
        int len = Q.size();
        for (int i = 0; i < len; i++)
        {
        
            int num = Q.front();
            Q.pop();
            if (q[num].l == -1 && q[num].r == -1)
                ans.pb(num);
            if (q[num].l != -1)
                Q.push(q[num].l);
            if (q[num].r != -1)
                Q.push(q[num].r);
        }
        if (Q.size())
            bfs();
    }
    
    int main()
    {
        
        init();
        int n;
        scanf("%d", &n);
        char a, b;
        for (int i = 0; i < n; i++)
        {
        
            scanf(" %c %c", &a, &b);
            if (a == '-')
                q[i].l = -1;
            else
            {
        
                q[i].l = a - '0';
                v[a - '0'] = 1;
            }
            if (b == '-')
                q[i].r = -1;
            else
            {
        
                q[i].r = b - '0';
                v[b - '0'] = 1;
            }
        }
        int root;
        for (int i = 0; i < n; i++)
        {
        
            if (v[i] == 0)
            {
        
                root = i;
                break;
            }
        }
        Q.push(root);
        bfs();
        vector <int>::iterator it;
        for (it = ans.begin(); it != ans.end(); it++)
        {
        
            if (it != ans.begin())
                printf(" ");
            printf("%d", *it);
        }
        cout << endl;
    }

### 10 ###

#include <stdio.h>
    #include <stdlib.h>
    #define Max 10001
    #define INF -1
    
    
    void BulidHeap();
    void Insert(int n);
    void Calculate();
    int Delete();
    
    typedef struct HeapStruct MinHeap;
    struct HeapStruct{
        
        int Data[Max];
        int Size;
    };
    
    MinHeap H;
    int Sum;
    
    int main()
    {
        
    	BulidHeap();
    	Calculate();
    	printf("%d",Sum);
    	
    }
    
    void BulidHeap()
    {
        
    	int N,i,n;
    	H.Data[0] = INF;//哨兵
    	scanf("%d",&N);
    	for(i = 1; i <= N; i++){
        
    		scanf("%d",&n);
    		Insert(n);
    	}
    }
    
    void Insert(int n)
    {
        
    	int i;
    	i = ++H.Size;
    	for( ; H.Data[i / 2] > n; i /= 2){
        
    		H.Data[i] = H.Data[i / 2];
    	}
    	H.Data[i] = n;
    }
    
    void Calculate()
    {
        
    	int a1,a2;
    	while(H.Size > 1){
        
    		a1 = Delete();
    		a2 = Delete();
    		Insert(a1 + a2);
    		Sum = Sum + a1 + a2;
    	}
    }
    
    int Delete()
    {
        
    	int parent,child,t,n;
    	n = H.Data[1];
    	t = H.Data[H.Size--];
    	for(parent = 1; parent * 2 <= H.Size;parent = child){
        
    		child = parent * 2;
    		if(H.Data[child + 1] < H.Data[child]){
        
    			child++;
    		}
    		if(t <= H.Data[child]) break;
    		else{
        
    			H.Data[parent] = H.Data[child];
    		}
    	}
    	H.Data[parent] = t;
    	return n;
    }

### 11 ###

#include <stdio.h>
    #include <stdlib.h>
    void find(int *a,int i,int j)
    {
        
        if(a[i]==0)
        {
        
            printf("ERROR: T[%d] is NULL\n",i);
            return;
        }
        if(a[j]==0)
        {
        
            printf("ERROR: T[%d] is NULL\n",j);
            return;
        }
        while(1)
        {
        
            if(i==j)break;
            else
            {
        
                if(i>j)
                    i=i/2;
                else
                    j=j/2;
            }
        }
        printf("%d %d\n",i,a[i]);
    }
    int main()
    {
        
        int a[1100],i,j,n;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        scanf("%d%d",&i,&j);
        find(a,i,j);
        return 0;
    }

### 12 ###

#include<cstdio>
    #include<cstring>
    #include<queue>
    #define MAX 20
    using namespace std;
    int map[MAX][MAX] = {
        0};
    int visited[MAX]={
        0};
    int m,n;
    void dfs(int x){
        
        for(int i = 0; i < n; ++i){
        
            if(!visited[i]&&map[x][i]){
        
                visited[i] = 1;
                printf(" %d",i);
                dfs(i);
            }
        }
    }
    int main()
    {
         
        int v1,v2;
        scanf("%d",&n);
        scanf("%d",&m);
        for(int i = 0; i < m; ++i){
        
            scanf("%d %d",&v1,&v2);
            map[v1][v2]=map[v2][v1]=1;
        }
        for(int i = 0; i < n; ++i){
        
            if(!visited[i]){
        
                visited[i]=1;
                printf("{");
                printf(" %d",i);
                dfs(i);
                printf(" }\n");
            }
        }
        //bfs
        memset(visited,0,sizeof(visited));
        queue<int> q;
        for(int i = 0; i < n; ++i){
        
            if(!visited[i]){
        
                visited[i]=1;
                printf("{");
                //printf(" %d",i);
                q.push(i);
                while(!q.empty()){
        
                    for(int j = 0; j <= n; ++j){
        
                        if(!visited[j]&&map[q.front()][j]){
        
                            visited[j]=1;
                            q.push(j);
                        }
                    }
                    printf(" %d",q.front());
                    q.pop();
                }
                printf(" }\n");
            }
        }
        return 0;
    }

### 13 ###

/*2015.7.16cyq*/
    //Prim最小生成树算法
    #include <iostream>
    #include <vector>
    #include <fstream>
    #include <algorithm>
    using namespace std;
     
    const int MAX=2147483647;
    //ifstream fin("case1.txt");
    //#define cin fin
     
    struct node{
        
    	int num;	//结点序号
    	int weight;	//能连通到已确定子图的最小边
    	int preNode;//最小边依附的结点,用于输出具体生成树
    	node():num(-1),weight(-1),preNode(-1){
        }
    	node(int n,int wei,int preN):num(n),weight(wei),preNode(preN){
        }
    	bool operator < (const node &a) const{
        
    		return weight<a.weight;
    	}
    };
     
    int main(){
        
    	int N,M;
    	cin>>N>>M;
    	vector<vector<int> > edges(N+1,vector<int>(N+1,-1));//-1表示不连通
    	int a,b,c;
    	while(M--){
        
    		cin>>a>>b>>c;
    		edges[a][b]=c;
    		edges[b][a]=c;
    	}
    	
    	vector<node> AB;//已吸收的点,一开始只有结点1
    	AB.push_back(node(1,0,-1));//
    	vector<node> UD(N-1);//未吸收的点
    	for(int i=0;i<N-1;i++){
        
    		UD[i].num=i+2;//编号2到N
    		int tmp=edges[1][UD[i].num];
    		if(tmp>0){
        //能连到结点1的结点
    			UD[i].weight=tmp;
    			UD[i].preNode=1;
    		}else{
        //不能连到结点1的结点
    			UD[i].weight=MAX;
    			UD[i].preNode=-1;
    		}
    	}
    	int totalLength=0;
    	//vector<pair<int,int> > result;//用于输出具体生成树
    	while(!UD.empty()){
        
    		sort(UD.begin(),UD.end());
    		node cur=UD[0];//取出能以最小代价吸收的点
    		UD.erase(UD.begin());
    		if(cur.weight==MAX){
        
    			cout<<"-1"<<endl;
    			return 0;
    		}
    		totalLength+=cur.weight;
    	//	result.push_back(make_pair(cur.num,cur.preNode));
    		for(auto it=UD.begin();it!=UD.end();++it){
        //用该点修正未吸收的点
    			int w=edges[cur.num][(*it).num];
    			if(w>0){
        
    				if(w<(*it).weight){
        
    					(*it).weight=w;
    					(*it).preNode=cur.num;
    				}
    			}
    		}
    	}
    	cout<<totalLength<<endl;
    	//for(auto it=result.begin();it!=result.end();++it){//输出最小生成树
    	//	cout<<(*it).first<<" "<<(*it).second<<" "<<edges[(*it).first][(*it).second]<<endl;
    	//}
    	return 0;
    }

### 14 ###

#include <bits/stdc++.h>
     
    using namespace std;
    const int maxn=1000+10;
    const int INF=0x3f3f3f3f;
     
     
    int cost[maxn][maxn];
    int mincost[maxn];
    bool used[maxn];
    int V,E;
     
    void prim()
    {
        
        memset(mincost,INF,sizeof(mincost));
        memset(used,false,sizeof(used));
     
        mincost[1]=0;
        int res=0;
        bool flag=false;
     
        while(true)
        {
        
            int v=-1;
            //cout<<"ggV:   "<<V<<endl;
            for(int u=1;u<=V;u++)
            {
        
                //cout<<"gg:    "<<mincost[u]<<"   "<<used[u]<<endl;
                if(!used[u]&&(v==-1||mincost[u]<mincost[v]))
                {
        
                    v=u;
                }
            }
     
            //cout<<"ggv:    "<<v<<endl;
            if(v==-1) break;
     
            used[v]=true;
            if(mincost[v]==INF)
            {
        
                flag=true;
                break;
            }
            res+=mincost[v];
     
            for(int u=1;u<=V;u++)
            {
        
                mincost[u]=min(mincost[u],cost[u][v]);
            }
        }
     
        if(flag) printf("Impossible\n");
        else printf("%d\n",res);
    }
     
    int main()
    {
        
        for(int i=0;i<maxn;i++) memset(cost[i],INF,sizeof(cost[i]));
        //for(int i=0;i<maxn;i++) cout<<"gg::   "<<cost[i][1]<<endl;
     
        scanf("%d %d",&V,&E);
        for(int i=0;i<E;i++)
        {
        
            int s,t,c; scanf("%d %d %d",&s,&t,&c);
            cost[s][t]=c;
            cost[t][s]=c;
            //cout<<"输出中间值   "<<s<<"  "<<t<<"   "<<c<<"    "<<f<<endl;
        }
        prim();
        return 0;
    }

### 15 ###

#include<bits/stdc++.h>
    using namespace std;
    const int N=105;
    vector<pair<int,int> >G[N];
    int n,m,out[N],ans[N],dis[N],tot;
    int main()
    {
        
        cin>>n>>m;
        for(int i=0,u,v,w; i<m; i++)cin>>u>>v>>w,out[v]++,G[u].push_back({
        v,w});
        queue<int>Q;
        for(int i=0; i<n; i++)if(!out[i])Q.push(i);
        while(!Q.empty())
        {
        
            int u=Q.front();
            Q.pop(),ans[tot++]=u;
            for(auto X:G[u])
            {
        
                int v=X.first,w=X.second;
                if(--out[v]==0)Q.push(v);
                if(dis[v]<dis[u]+w)dis[v]=dis[u]+w;
            }
        }
        if(tot==n)
        {
        
            int ans1=0;
            for(int i=0;i<n;i++)ans1=max(ans1,dis[i]);
            cout<<ans1<<"\n";
        }
        else cout<<"Impossible";
        return 0;
    }

### 16 ###

#include<stdio.h>
    #include<stdlib.h>
    #define maxvertex 110
    #define maxweigh 0x3f3f3f
    int mindis = maxweigh;
    int mindex = 0;
    int maxn;
    int main(){
        
        //利用邻接矩阵存储图
        int Graph[maxvertex][maxvertex];
        int N,M;
        int idx1,idx2,weigh;
        scanf("%d%d",&N,&M);
        //初始化
        for (int i=1; i<=N; i++) {
        
            for (int j=1; j<=N; j++) {
        
                if (i==j) {
        
                    Graph[i][j] = 0;
                }
                else Graph[i][j] = maxweigh;
            }
        }
        //输入边，建立图
        for (int i=0; i<M; i++) {
        
            scanf("%d%d%d",&idx1,&idx2,&weigh);
            Graph[idx1][idx2] = Graph[idx2][idx1] = weigh;
        }
        //floyd算法
        for (int k=1; k<=N; k++) {
        
            for (int i=1; i<=N ; i++) {
        
                for (int j=1; j<=N; j++) {
        
                    if (Graph[i][j] > (Graph[i][k]+Graph[k][j])) {
        
                        Graph[i][j] = (Graph[i][k]+Graph[k][j]);
                    }
                }
            }
        }
        for (int i=1; i<=N; i++){
        
            maxn =0;
            for (int j=1; j<=N; j++) {
        
                
                //更新当前结点的最大值
                if (Graph[i][j] > maxn) {
        
                    maxn = Graph[i][j];
                }
            }
            if (maxn < mindis) {
        
                mindis = maxn;
                mindex = i;
            }
        }
        //输出结果
        if (mindex ==0 ) {
        
            printf("0\n");
        }
        else
            printf("%d %d\n",mindex,mindis);
        return 0;
    }

### 17 ###

#include<iostream>
    #include<cstring>
    #define MAXN 505
    #define MCOST 250005
    #define ERROR 0
    using namespace std;
    float g[MAXN][MAXN],dist[MAXN];
    int cost[MAXN][MAXN],dis[MAXN][MAXN],collected[MAXN],path[MAXN];
    int n;
    int FindMinDist(   )
    {
         /* 返回未被收录顶点中dist最小者 */
        int MinV, V;
        float MinDist = MCOST;
        for (V=0; V<n; V++) {
        
            if ( collected[V]==0 && dist[V]<MinDist) {
        
                /* 若V未被收录，且dist[V]更小 */
                MinDist = dist[V]; /* 更新最小距离 */
                MinV = V; /* 更新对应顶点 */
            }
        }
        if (MinDist < MCOST) /* 若找到最小dist */
            return MinV; /* 返回对应的顶点下标 */
        else return ERROR;  /* 若这样的顶点不存在，返回错误标记 */
    }
    
    int Dijkstra( int S )
    {
        
        int V, W;
        /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
        for ( V=0; V<n; V++ ) {
        
            dist[V] = g[S][V];
            if ( dist[V]<MCOST )
                path[V] = S;
            else
                path[V] = -1;
            collected[V] = 0;
        }
        /* 先将起点收入集合 */
        dist[S] = 0;
        collected[S] = 1;
        while (1) {
        
            /* V = 未被收录顶点中dist最小者 */
            V = FindMinDist( );
            if ( V==ERROR ) /* 若这样的V不存在 */
                break;      /* 算法结束 */
            collected[V] = 1;  /* 收录V */
            for( W=0; W<n; W++ ) /* 对图中的每个顶点W */
                /* 若W是V的邻接点并且未被收录 */
                if ( collected[W]==0 && g[V][W]<MCOST ) {
        
                    if ( g[V][W]<0 ) /* 若有负边 */
                        return 0; /* 不能正确解决，返回错误标记 */
                    /* 若收录V使得dist[W]变小 */
                    if ( dist[V]+g[V][W] < dist[W] ) {
        
                        dist[W] = dist[V]+g[V][W]; /* 更新dist[W] */
                        path[W] = V; /* 更新S到W的路径 */
                    }
                }
        } /* while结束*/
        return 1; /* 算法执行完毕，返回正确标记 */
    }
    int main(){
        
    	cin>>n;
    	for(int i=0;i<n;i++){
        
    		for(int j=0;j<n;j++){
        
    		g[i][j]=MCOST;
    	    }
    	    g[i][i]=0;
    	}
    	int m,s,d;cin>>m>>s>>d;int a,b,p,c;
    	for(int i=0;i<m;i++){
        
    		cin>>a>>b>>p>>c;
    		g[a][b]=p*0.9999+c*0.0001;g[b][a]=p*0.9999+c*0.0001;
    		cost[a][b]=c;cost[b][a]=c;
    		dis[a][b]=p;dis[b][a]=p;
    	}
    	Dijkstra(s);
    	int cntc=0,t=d,cntd=0;
    	while(t!=s){
        
    		cntc+=cost[t][path[t]];
    		cntd+=dis[t][path[t]];
    		t=path[t];
    	}
    	cout<<cntd<<" "<<cntc;
    	return 0;
    }

### 18 ###

#include <iostream>
    #include <deque>
    #include <iomanip>
    #define ElementType int
    #define Vertex int
     
    typedef struct _ENode
    {
        
    	Vertex V1;
    	Vertex V2;
    }Edge;
     
    typedef struct _GNode
    {
        
    	int num_of_array;//下三角矩阵存储，所以和一般的二维不一样
    	int Nv;//顶点数
    	int Ne;//边数
    	ElementType *G;//下三角临接矩阵,一维代替二维
    }Graph;
     
    using namespace std;
     
    void creat_Graph(Graph *, int num_v, int num_e);
    void insert_Edge(Graph *, Edge);
    void Six_Degrees(Graph *);
    double Calculate_Six_Percent(Graph *, Vertex, int degrees, bool visited[]);
    void print(Graph *);
     
    double *percent;
     
    int main()
    {
        
    	int N, M;
    	cin >> N >> M;
    	Graph *graph = new Graph;
    	creat_Graph(graph, N, M);
    	for (int i = 0; i < M; i++)
    	{
        
    		Edge edge;
    		cin >> edge.V1 >> edge.V2;
    		insert_Edge(graph, edge);
    	}
    	percent = new double[graph->num_of_array];
    	Six_Degrees(graph);
    	print(graph);
     
        return 0; 
    }
     
    void creat_Graph(Graph *graph, int num_v, int num_e)
    {
        
    	graph->num_of_array = num_v * (num_v + 1) / 2;
    	graph->Nv = num_v;
    	graph->Ne = num_e;
    	graph->G = new ElementType[graph->num_of_array];
    	for (int i = 0; i < graph->num_of_array; i++)	//下三角临接矩阵初始化
    		graph->G[i] = 0;
    }
     
    void insert_Edge(Graph *graph, Edge edge)
    {
        
    	edge.V1 -= 1;//输出的是从1开始计数，而此程序矩阵从0开始
    	edge.V2 -= 1;
    	if (edge.V1 < edge.V2)
    		graph->G[edge.V2*(edge.V2 + 1) / 2 + edge.V1] = 1;
    	else
    		graph->G[edge.V1*(edge.V1 + 1) / 2 + edge.V2] = 1;
    }
     
    void Six_Degrees(Graph *graph)
    {
        
    	bool *visited = new bool[graph->Nv];
    	for (Vertex i = 0; i < graph->Nv; i++)
    	{
        
    		for (int i = 0; i < graph->Nv; i++)//初始化visited，visited只有Nv个数据
    			visited[i] = 0;
    		percent[i] = Calculate_Six_Percent(graph, i, 1, visited);//percent也只有Nv个数据
    	}
    }
     
    double Calculate_Six_Percent(Graph *graph, Vertex start_V, int degrees, bool visited[])
    {
        
    	Vertex *queue = new Vertex[graph->num_of_array + 1];
    	int front = 0, rear = 0, last = 0;
    	int num_six_degrees = 0;//不超过6度的顶点数
    	Vertex V = start_V;
     
    	visited[V] = 1;
    	queue[rear++] = V;//入队
    	while (front != rear && degrees <= 6)
    	{
        
    		V = queue[front++];//出队
    		Vertex target_V = 0;//由于三角矩阵的关系，i不能表示顶点，遂用 target_V 表示要与顶点 V 做判断的顶点
    		Vertex start_TLine = V * (V + 1) / 2;
    		Vertex start_VLine = start_TLine + V;
    		for (Vertex i = start_TLine; i < start_TLine + V; i++)				//遍历横向顶点
    		{
        
    			if (graph->G[i] == 1 && visited[target_V] == 0) {
        				//有边且未被访问过
    				queue[rear++] = target_V;
    				visited[target_V] = 1;
    				num_six_degrees++;
    			}	
    			target_V++;
    		}
    		int k = 0;
    		for (Vertex i = start_VLine; i < graph->num_of_array; i = i + V + k)//遍历竖向顶点
    		{
        
    			k++;
    			if (graph->G[i] == 1 && visited[target_V] == 0) {
        
    				queue[rear++] = target_V;
    				visited[target_V] = 1;
    				num_six_degrees++;
    			}
    			target_V++;
    		}
    		if (last == front - 1) {
        
    			degrees++;
    			last = rear - 1;
    		}
    	}
    	return (double)(num_six_degrees + 1) / graph->Nv;
    }
     
    void print(Graph *graph)
    {
        
    	int flag = 1;
    	cout << setprecision(2) << setiosflags(ios::fixed);
    	for (int i = 0; i < graph->Nv; i++)
    	{
        
    		if (flag)
    			flag = 0;
    		else
    			cout << endl;
    		cout << i+1 << ": " << percent[i] * 100 << "%";
    	}
    }

### 19 ###

#include <cstdio>   
    #include <iostream> 
    #include <algorithm> 
    #include <cmath> 
    #include <cstdlib> 
    #include <cstring> 
    #include <vector> 
    #include <list> 
    #include <map> 
    #include <stack> 
    #include <queue> 
    using namespace std; 
    #define ll long long
    typedef struct Tree{
        
    	int data;
    	Tree *l,*r;
    }*BiTree;
    bool check[20];
    void build(BiTree &T,int e)
    {
        
    	if(!T)
    	{
        
    		T = new Tree;
    		T->data = e;
    		T->l = T->r = NULL;
    		return;
    	}
    	if(!T->l && e < T->data)
    	{
        
    		/*BiTree temp = new Tree;
    		temp->l = temp->r = NULL;
    		T->l = temp;
    		temp->data = e;*/
    		T->l = new Tree;
    		T->l->l = T->l->r = NULL;
    		T->l->data = e;
    		return;
    	}
    	if(!T->r && e > T->data)
    	{
        
    		/*BiTree temp = new Tree;
    		temp->l = temp->r = NULL;
    		T->r = temp;
    		temp->data = e;*/
    		T->r = new Tree;
    		T->r->l = T->r->r = NULL;
    		T->r->data = e;
    		return;
    	}
    	if(e > T->data)
    		build(T->r,e);
    	else
    		build(T->l,e);
    	return;
    }
    bool juge(BiTree T,int e)
    {
        
    	if(!check[T->data] && e != T->data)
    		return false;
    	check[T->data] = 1;
    	if(e == T->data)
    		return true;
    	if(e < T->data)
    		return juge(T->l,e);
    	else
    		return juge(T->r,e);
    }
    int main() 
    {
        
    	int n,l;
    	while(cin >> n&&n)
    	{
        
    		cin >> l;
    		BiTree T ;
    		T = NULL;
    		for(int i = 0;i < n;i++)
    		{
        
    			int x;
    			cin >> x;
    			build(T,x);
    		}
    		while(l--)
    		{
        
    			int f = 0;
    			memset(check,0,sizeof(check));
    			for(int i = 0;i < n;i++)
    			{
        
    				int x;
    				cin >> x;
    				if(!juge(T,x))
    					f = 1;
    			}
    			if(f)
    				cout << "No" <<endl;
    			else
    				cout << "Yes" <<endl;
    		}
    	} 
        //cout << "AC" <<endl; 
        return 0; 
    }

### 20 ###

#include <bits/stdc++.h>
    #define KEYLENGTH 15
    typedef char ElementType[KEYLENGTH+1];
    typedef int Index;
    typedef struct LNode *PtrToLNode;
    struct LNode
    {
        
        ElementType Data;
        PtrToLNode Next;
        int cnt;
    };
    typedef PtrToLNode Position;
    typedef PtrToLNode List;
     
    typedef struct TblNode *HashTable;
    struct TblNode
    {
        
        int TableSize;
        List Heads;
    };
    typedef struct Result
    {
        
        ElementType MinData;
        int sum;
    } Result;
    int GetTableSize(int n)
    {
        
        int i, j;
        for(i = n; ; ++i)
        {
        
            for(j = 2; j * j <= i; ++j)
                if(i % j == 0)
                    break;
            if(j * j > i)
                return i;
        }
    }
    Index Hash(ElementType Key, int TableSize )
    {
        
        return (atoi(Key + 6))%TableSize; //Key 取第六位到最后一位，全取的话太长
    }
    PtrToLNode GetMax(HashTable H)
    {
        
        int Max = 0;
        PtrToLNode mmax = NULL;
        for(int i = 0; i < H->TableSize; ++i)
        {
        
            PtrToLNode  temp = H->Heads[i].Next;
            while(temp != NULL)
            {
        
                if(Max < temp->cnt)
                {
        
                    Max = temp->cnt;
                    mmax = temp;
                }
                temp = temp->Next;
            }
        }
        return mmax;
    }
    PtrToLNode Find(HashTable H, ElementType key)
    {
        
        int hvalue = Hash(key, H->TableSize);
        PtrToLNode  temp = H->Heads[hvalue].Next;
        while(temp != NULL)
        {
        
            if(strcmp(temp->Data, key) == 0)
                return temp;
            temp = temp->Next;
        }
        return NULL;
    }
    void Insert(HashTable &H, ElementType key)
    {
        
        int hvalue = Hash(key, H->TableSize);
        PtrToLNode  temp = Find(H, key);
        if(temp != NULL)
        {
        
            ++temp->cnt;
        }
        else
        {
        
            PtrToLNode ins = (PtrToLNode)malloc(sizeof(struct LNode));
            strcpy(ins->Data, key);
            ins->cnt = 1;
            ins->Next = H->Heads[hvalue].Next;
            H->Heads[hvalue].Next = ins;
        }
    }
    HashTable BuildTable()
    {
        
        int n;
        scanf("%d", &n);
        HashTable H = (HashTable)malloc(sizeof(struct TblNode));
        H->TableSize = GetTableSize(2 * n);
        H->Heads = (PtrToLNode)malloc(sizeof(struct LNode) * (H->TableSize));
        char key1[KEYLENGTH - 1], key2[KEYLENGTH - 1];
        for(int i = 0; i < H->TableSize; ++i)
        {
        
            H->Heads[i].Next = NULL;
        }
        for(int i = 0; i < n; ++i)
        {
        
            scanf("%s %s", key1, key2);
            Insert(H, key1);
            Insert(H, key2);
        }
        return H;
    }
    void Solve(HashTable H)
    {
        
        PtrToLNode Max = GetMax(H);
        Result re;
        strcpy(re.MinData, Max->Data);
        re.sum = 0;
        for(int i = 0; i < H->TableSize; ++i)
        {
        
            PtrToLNode temp = H->Heads[i].Next;
            while(temp != NULL)
            {
        
                if(temp->cnt == Max->cnt)
                {
        
                    ++re.sum;
                    if(strcmp(re.MinData, temp->Data) > 0)
                        strcpy(re.MinData, temp->Data);
                }
                temp = temp->Next;
            }
        }
        printf("%s %d", re.MinData, Max->cnt);
        if(re.sum > 1)
            printf(" %d", re.sum);
        printf("\n");
    }
    int main()
    {
        
        int n;
        HashTable H;
        H = BuildTable();
        Solve(H);
        return 0;
    }

### 21 ###

#include<iostream>
    #include<map>
    #include<algorithm>
    #include<string>
    using namespace std;
    int main()
    {
        
    	int n;
    	cin>>n;
    	map<long long,string> mp;
    	for(int i=0;i<n;i++)
    	{
        
    		char c;
    		long long a;
    		string b;
    		cin>>c>>a>>b;
    		if(mp.count(a)==0 )//如果映射中还没有这个QQ号 
    		{
        
    			if(c=='L')
    			{
        
    				cout<<"ERROR: Not Exist"<<endl;
    				
    			}
    			else if(c=='N')
    			{
        
    				mp[a]=b;
    			cout<<"New: OK"<<endl;
    			}
    			
    		}
    		else 
    		{
        
    			if(c=='N')
    			{
        
    				cout<<"ERROR: Exist"<<endl;
    			}
    			else if(c=='L')
    			{
        
    				if(b==mp[a])
    				{
        
    					cout<<"Login: OK"<<endl;
    				}
    				else
    				{
        
    					cout<<"ERROR: Wrong PW"<<endl;
    				}
    			}
    		}
    		
    	}
     }

### 22 ###

#include <stdio.h>
    #include <stdlib.h>
    #define N 100000
    #define Cutoff 10
    #define Radix 10
     
    void percdown(long *a, int n, int i);
    void merge(long *a, long *tmp, int start, int end, int middle);
    void msort(long *a, long *tmp, int start, int end);
    void merge_pass(long *a, long *tmp, int n, int length);
    void q_sort(long *a, int left, int right);
     
    void bubble_sort(long *a, int n);
    void insertion_sort(long *a, int n);
    void selection_sort(long *a, int n);
    void shell_sort(long *a, int n);
    void shellsedgewick_sort(long *a, int n);
    void heap_sort(long *a, int n);
    void merge1_sort(long *a, int n);
    void merge2_sort(long *a, int n);
    void quick_sort(long *a, int n);
    void radix_sort(long *a, int n);
     
    int main() {
        
    	int i, n;
    	long a[N];
    	scanf("%d", &n);
    	for (i = 0;i < n;i++)
    		scanf("%ld", &a[i]);
    	radix_sort(a, n);
    	printf("%ld", a[0]);
    	for (i = 1;i < n;i++)
    		printf(" %ld", a[i]);
    	return 0;
    }
     
    //冒泡排序
    void bubble_sort(long *a, int n) {
        
    	int i, j, flag;
    	long temp;
    	for (i = n - 1;i > 0;i--) {
        
    		flag = 0;
    		for (j = 0;j < i;j++) {
        
    			if (a[j] > a[j + 1]) {
        
    				temp = a[j];
    				a[j] = a[j + 1];
    				a[j + 1] = temp;
    				flag = 1;
    			}
    		}
    		if (!flag) break;
    	}
    }
     
    //插入排序
    void insertion_sort(long *a, int n) {
        
    	int i, j;
    	long temp;
    	for (i = 1;i < n;i++) {
        
    		temp = a[i];
    		for (j = i; j > 0 && a[j - 1] > temp; j--) 
    				a[j] = a[j - 1];
    		a[j] = temp;
    	}
    }
     
    //选择排序
    void selection_sort(long *a, int n) {
        
    	int i, j, t;
    	long temp;
    	for (i = 0;i < n - 1;i++) {
        
    		temp = a[i];
    		t = i;
    		for (j = i + 1;j < n;j++) {
        
    			if (a[j] < temp) {
        
    				temp = a[j];
    				t = j;
    			}	
    		}
    		a[t] = a[i];
    		a[i] = temp;
    	}
    }
     
    //希尔排序-希尔增量
    void shell_sort(long *a, int n) {
        
    	int i, j, d;
    	long temp;
    	for (d = n / 2;d > 0;d /= 2) {
        
    		for (i = d;i < n;i++) {
        
    			temp = a[i];
    			for (j = i;j >= d && a[j - d] > temp;j -= d)
    				a[j] = a[j - d];
    			a[j] = temp;
    		}
    	}
    }
     
    //希尔排序-sedgewick增量
    void shellsedgewick_sort(long *a, int n) {
        
    	int i, j, d, si;
    	int Sedgewick[] = {
         929, 505, 209, 109, 41, 19, 5, 1, 0 };
    	long temp;
    	for (si = 0;Sedgewick[si] >= n;si++)
    		;
    	for (;Sedgewick[si] > 0;si++) {
        
    		d = Sedgewick[si];
    		for (i = d;i < n;i++) {
        
    			temp = a[i];
    			for (j = i;j >= d && a[j - d] > temp;j -= d)
    				a[j] = a[j - d];
    			a[j] = temp;
    		}
    	}
    }
     
    //堆排序
    void heap_sort(long *a, int n) {
        
    	int i;
    	long temp;
    	for (i = (n - 2) / 2; i >= 0; i--)
    		percdown(a, n, i);
    	for (i = n - 1;i > 0;i--) {
        
    		temp = a[i];
    		a[i] = a[0];
    		a[0] = temp;
    		percdown(a, i, 0);
    	}
    }
     
    void percdown(long *a, int n, int i) {
        
    	int child;
    	long x = a[i];
    	for (;i * 2 + 1 <= n - 1;i = child) {
        
    		child = i * 2 + 1;
    		if (child < n - 1 && a[child + 1] > a[child])
    			child++;
    		if (x >= a[child]) break;
    		else a[i] = a[child];
    	}
    	a[i] = x;
    }
     
    //归并排序-递归实现
    void merge1_sort(long *a, int n) {
        
    	long *tmp = (long*)malloc(n*sizeof(long));
    	msort(a, tmp, 0, n - 1);
    	free(tmp);
    }
     
    void msort(long *a, long *tmp, int start, int end) {
        
    	int middle;
    	if (start < end) {
        
    		middle = (start + end) / 2;
    		msort(a, tmp, start, middle);
    		msort(a, tmp, middle + 1, end);
    		merge(a, tmp, start, end, middle);
    	}
    }
     
    void merge(long *a, long *tmp, int start, int end, int middle) {
        
    	int l, r, s;
    	s = start;
    	l = start;
    	r = middle + 1;
    	while (l <= middle && r <= end) {
        
    		if (a[l] <= a[r]) tmp[s++] = a[l++];
    		else tmp[s++] = a[r++];
    	}
    	while (l <= middle) tmp[s++] = a[l++];
    	while (r <= end) tmp[s++] = a[r++];
    	for (;start <= end;start++)
    		a[start] = tmp[start];
    }
     
    //归并排序-循环实现
    void merge2_sort(long *a, int n) {
        
    	int length = 1;
    	long *tmp = (long*)malloc(n*sizeof(long));
    	while (length < n) {
        
    		merge_pass(a, tmp, n, length);
    		length *= 2;
    		merge_pass(tmp, a, n, length);
    		length *= 2;
    	}
    	free(tmp);
    }
     
    void merge_pass(long *a, long *tmp, int n, int length) {
        
    	int i, j;
    	for (i = 0;i + 2 * length <= n;i += 2*length) 
    		merge(a, tmp, i, i + 2 * length - 1, i + length - 1);
    	if (i + length <= n)
    		merge(a, tmp, i, n - 1, i + length - 1);
    	else
    		for (j = i;j < n;j++)
    			tmp[j] = a[j];
    }
     
    //快速排序
    void quick_sort(long *a, int n) {
        
    	q_sort(a, 0, n - 1);
    }
     
    void q_sort(long *a, int left, int right) {
        
    	long pivot, temp;
    	int i, j, center;
     
    	if (right - left + 1 > Cutoff) {
        
    		center = (left + right) / 2;
    		if (a[center] < a[left]) {
        
    			temp = a[center];a[center] = a[left];a[left] = temp;
    		}
    		if (a[right] < a[left]) {
        
    			temp = a[right];a[right] = a[left];a[left] = temp;
    		}
    		if (a[right] < a[center]) {
        
    			temp = a[right];a[right] = a[center];a[center] = temp;
    		}
    		temp = a[right - 1];a[right - 1] = a[center];a[center] = temp;
    		pivot = a[right - 1];
     
    		i = left;
    		j = right - 1;
    		for (;;) {
        
    			while (a[++i] < pivot);
    			while (a[--j] > pivot);
    			if (i < j) {
        
    				temp = a[i];a[i] = a[j];a[j] = temp;
    			}
    			else break;
    		}
    		temp = a[i];a[i] = a[right - 1];a[right - 1] = temp;
     
    		q_sort(a, left, i - 1);
    		q_sort(a, i + 1, right);
    	}
    	else
    		insertion_sort(a + left, right - left + 1);
    }
     
    //基数排序-次位优先
    struct Node {
        
    	int data;
    	Node* next;
    };
    struct Bucket {
        
    	Node *head, *tail;
    };
     
    void radix_sort(long *a, int n) {
        
    	int d, di, i, flag;
    	long t;
    	Bucket b[Radix*2 - 1];//19个桶 -9--1，0，1-9；
    	Node *tmp, *p, *list = NULL;
     
    	for (i = 0;i <= (Radix-1) * 2;i++)
    		b[i].head = b[i].tail = NULL;
    	for (i = n - 1;i >= 0;i--) {
        
    		tmp = (Node*)malloc(sizeof(Node));
    		tmp->data = a[i];
    		tmp->next = list;
    		list = tmp;
    	}
    	for (d = 1;;d++) {
        
    		p = list;
    		flag = 0;
    		while (p) {
        
    			t = p->data;
    			for (i = 1;i <= d;i++) {
        
    				di = t % Radix;t /= Radix;
    			}
    			if (di != 0) flag = 1;
    			di += Radix-1;
    			tmp = p;
    			p = p->next;
    			tmp->next = NULL;
    			if (!b[di].head)
    				b[di].head = b[di].tail = tmp;
    			else {
        
    				b[di].tail->next = tmp;
    				b[di].tail = tmp;
    			}
    		}
     
    		if (!flag) break;
    		else {
        
    			list = NULL;
    			for (i = (Radix - 1) * 2;i >= 0;i--) {
        
    				
    				if (b[i].head) {
        
    					b[i].tail->next = list;
    					list = b[i].head;
    					b[i].head = b[i].tail = NULL;
    				}
    			}
    		}
    	}
     
    	for (i = 0;i < n;i++) {
        
    		a[i] = b[Radix - 1].head->data;
    		b[Radix - 1].head = b[Radix - 1].head->next;
    	}
    }

### 23 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int n,m,k;
        cin>>n>>m>>k;
        int data[10];
        double num[10000],num1[10000];
        int t=0;
        while(n--)
        {
        
            int sum=0;
            memset(data,0,sizeof(data));
            for(int i=0; i<m; i++)
                cin>>data[i];
            sort(data,data+m);
            for(int i=1; i<m-1; i++)
            {
        
                sum+=data[i];
            }
            num[t++]=1.0*sum/(m-2);
        }
        int ss,tt=0;
        while(k--)
        {
        
            double max1=-1000.0;
            for(int i=0; i<t; i++)
            {
        
                if(num[i]>max1)
                {
        
                    max1=num[i];
                    ss=i;
                }
            }
             num1[tt++]=max1;
             num[ss]=0;
        }
         for(int i=tt-1;i>0;i--)
            printf("%.3lf ",num1[i]);
         printf("%.3lf\n",num1[0]);
        return 0;
    }

### 24 ###

#include<iostream>
    #include<algorithm>
    using namespace std;
    int sum[100005];
    int main(){
        
    	int n;
    	cin>>n;
    	int s=0;
    	for(int i=0;i<n;i++){
        
    		cin>>sum[i];
    		s+=sum[i];
    	}
    	sort(sum+0,sum+n);
    	int out=0,in=0;
    		for(int i=0;i<n/2;i++){
        
    			in+=sum[i];
    		}
    		for(int i=n-1;i>=n/2;i--){
        
    			out+=sum[i];
    		}
    		printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n%2==0? n/2:n/2+1,n/2,out-in);
    	return 0;
    }

### 25 ###

#include<stdio.h>
    #include<stdlib.h>
    
    int cmp(const void *a,const void *b) //定义快排函数规则，这里即非升序
    {
        
        return (*(long *)b > *(long *)a) ? 1 : -1;
    }
    
    int main()
    {
        
        int i, k, n, m, cnt = 0, flag = 1;
        long x, s[10] = {
        0};
        scanf("%d %d", &n, &m);
        int len = m < n ? m : n; //判读数组的长度取m还是n（取小的那个）
        for(i = 0; i < len; i ++) {
        
            scanf("%ld", &s[i]);
        }
        qsort(s, len, sizeof(long), cmp); //调用快排函数
        for(i = len; i < n; i ++) {
        
            scanf("%ld", &x);
            if(x > s[len-1]) {
         //如果当前输入的x大于数组最小的那个元素
                for(k = 0; k < len; ++ k) {
         //遍历数组
                    if(s[k] < x) {
         //找到第一个s[k] < x的位置
                        int t;
                        for(t = len-1; t > k; t --) {
         
                        //k后面的元素全部往后移一个位置
                            s[t] = s[t-1];
                        }
                        s[t] = x; //移动后，空出来的位置，即x插入的位置
                        break; //跳出循环
                    }
                }
            }
        }
        if(len >= 1) {
        
            printf("%ld", s[0]);
        }
        for(i = 1; i < len; i ++) {
        
            printf(" %ld", s[i]);
        }
    
        return 0;
    }

### 26 ###

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    using namespace std;
    struct student
    {
        
    	string id;//考号 
    	int kao;//考场 
    	int score;//成绩 
    	int rank;//在考场内的排名 
    	int rankz;//总排名 
    }stu[30005];
    bool cmp(student a,student b)
    {
        
    	if(a.score ==b.score )//如果两人分数相同个，按考号递增输出 
    	return a.id <b.id ;
    	else
    	return a.score >b.score ;
    }
    
    int main()
    {
        
    	int n,cnt=0,s=0;//cnt来记录下标，s记录总数 
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
        
    		int k,st;
    		cin>>k;
    		s+=k;
    		for(int j=0;j<k;j++)
    		{
        
    			stu[cnt].kao  =i+1;
    			cin>>stu[cnt].id >>stu[cnt].score ;
    			cnt++;
    			
    		}
    		st=s-k;
    		//st表示这一个考场的第一个人在stu[]中起始下标，s表示末下标 
    		sort(stu+st,stu+s,cmp);//这个处理非常重要 
    		int p=1;//用来排名次 
    		for(int i=st;i<s;i++)
    		{
        
    			if(stu[i].score ==stu[i-1].score&&i>=1 )//如果和前面一个人分数相同，则名次一样 
    			stu[i].rank =stu[i-1].rank ;
    			else
    			stu[i].rank =p;
    			p++;//记得要加1	
    		}
    	}
    	sort(stu,stu+s,cmp);//对整个结构体数组进行排序 
    	for(int i=0;i<s;i++)
    		{
        
    			if(stu[i].score ==stu[i-1].score&&i>=1 )
    			stu[i].rankz =stu[i-1].rankz ;
    			else
    			stu[i].rankz =i+1;//i是下标从0开始的，所以表示排名的时候要+1 
    			
    		}
    		cout<<s<<endl;
    		for(int i=0;i<s;i++)
    		{
        
    			cout<<stu[i].id <<' '<<stu[i].rankz<<' '<<stu[i].kao <<' '<<stu[i].rank <<endl;
    		}
    	
    }

r(int i=0; i<t; i++)  
\{  
if(num\[i\]>max1)  
\{  
max1=num\[i\];  
ss=i;  
\}  
\}  
num1\[tt++\]=max1;  
num\[ss\]=0;  
\}  
for(int i=tt-1;i>0;i–)  
printf("%.3lf “,num1\[i\]);  
printf(”%.3lf\\n",num1\[0\]);  
return 0;  
\}

### 24
    
    ```c
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int sum[100005];
    int main(){
    	int n;
    	cin>>n;
    	int s=0;
    	for(int i=0;i<n;i++){
    		cin>>sum[i];
    		s+=sum[i];
    	}
    	sort(sum+0,sum+n);
    	int out=0,in=0;
    		for(int i=0;i<n/2;i++){
    			in+=sum[i];
    		}
    		for(int i=n-1;i>=n/2;i--){
    			out+=sum[i];
    		}
    		printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n%2==0? n/2:n/2+1,n/2,out-in);
    	return 0;
    }

### 25 ###

### 26 ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkwNjE0OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200702123944240.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkwNjE0OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkwNjE0OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200702123955686.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkwNjE0OQ==,size_16,color_FFFFFF,t_70