编程2222

7-2 寻找大富翁

#include   //堆排序；  注意:此算法中，下标从1开始
#define max 1000010
int num[max];
void sift(int *num,int low,int high)  //将下标为low位置上的点调到适当位置
{
    int i,j,temp;
    i=low;    j=2*i;   //num[j]是num[i]的左孩子结点；
    temp=num[i];  //待调整的结点
    while(j<=high)
    {
        if(j=1;i--)  //所有结点建立初始堆
       sift(num,i,n);
     for(i=n;i>=2;i--)   //进行n-1次循环，完成堆排序
    {
        
        temp=num[1];
        num[1]=num[i];
        num[i]=temp;
        count++;
        if(count==1)
        printf("%d",num[i]);
        else
        printf(" %d",num[i]);
        if(count==m) break;  //打印前m个；
        sift(num,1,i-1);    //减少了1个关键字的无序序列，继续调整。
    }
    if(m==n) printf(" %d",num[1]);  //当n 
7-1 公路村村通
 
#include
#define  inf 0x3f3f3f3f
int size=0;
typedef struct NODE node;
struct NODE{
    int cell;//节点是谁
    int key;
};
void heapify(node *am,int i)
{
    int l,r,min;
    while(1)
    {
        l=i<<1;
        r=i<<1|1;
        if(l<=size&&am[l].key1&&am[i>>1].key>am[i].key)
    {
        node tep=am[i>>1];
        am[i>>1]=am[i];
        am[i]=tep;
        i=i>>1;
    }
}
int findit(node *dis,int v)
{
    for(int i=1;i<=size;i++)
    {
        if(dis[i].cell==v)
        {
            return i;        
        }
    }
}
int cost[1001][1001]={0};
int main(void)
{
    node dis[1002];
    node tep[1002];
    int n,m;
    scanf("%d%d",&n,&m);
    size=n;
    for(int i=1;i<=n;i++)//初始化，dis是队列，tep保存结点的更新情况
    {
        dis[i].key=tep[i].key=inf;
        dis[i].cell=tep[i].cell=i;
        
    }
    for(int i=1;i<=m;i++)
    {
        int r1,r2,co;
        scanf("%d%d%d",&r1,&r2,&co);
        cost[r1][r2]=co;
        cost[r2][r1]=co;
    }
    int ans=0;
    dis[1].key=0;//初始时，设根结点1的路径长度为0
    int mark[1002]={0};//标记有木有在生成树里面
    int flag=0;
    while(size!=0)
    {
        node u=extract_min(dis);
        if(u.key==inf)
        {
            flag=1;
            break;
        }
        mark[u.cell]=1;
        ans+=u.key;
        for(int v=1;v<=n;v++)//用临接链表更快，但也麻烦
        {
            if(cost[u.cell][v]!=0&&mark[v]==0&&cost[u.cell][v] 
7-1 地下迷宫探索
 
#include
using namespace std;
int vis[1010],r[1010][1010],path[1010];
int n,m,s,j=0,cnt=1;  //cnt统计可以点亮的灯个数

void dsf(int x){
    for(int i=1; i<=n; i++){
        if(r[x][i]&&!vis[i]){
            cnt++;
            vis[i]=1;
            
            //核心*************
            path[j++]=i;//保存去的结点
            dsf(i);
            path[j++]=x; //保存回去的路
            //*************
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    while(m--){
        int a,b;
        cin>>a>>b;
        r[a][b]=1;
        r[b][a]=1;
    }
    path[j++]=s;
    vis[s]=1;
    dsf(s);
    for(int i=0; i 
  
7-2 深入虎穴
 
#include 
using namespace std;
int main(){
    int n;
    cin>>n;
    vector e[n+1];
    vector vis(n+1,0);
    for(int i = 1;i <= n;i++){
        int t;
        cin>>t;
        for(int j = 0;j < t;j++){
            int a;
            cin>>a;
            vis[a] = 1;
            e[i].push_back(a);
        }
    }
    queue q;
    //找到入口并将入口入队
    for(int i = 1;i <= n;i++){
        if(vis[i] == 0){
            q.push(i);
            break;
        }
    }
    int u = -1;
    //从入口开始bfs
    while(!q.empty()){
        u = q.front();
        q.pop();
        for(auto i : e[u]){
            q.push(i);
        }
    }
    //输出
    cout< 
7-1 那就别担心了
 
#include 
using namespace std;

const int maxn = 510;
int n,m,s,t;
vector ve[maxn];
int dp[maxn];

int dfs(int x){
    if(dp[x]) return dp[x];
    if(x == t) return 1;
    for(auto v : ve[x]){
        dp[x] += dfs(v);
    }
    return dp[x];
}

int vis[maxn];
queue que;
int bfs(){
    que.push(s);
    while(!que.empty()){
        int tp = que.front();
        que.pop();
        if(vis[tp]) continue;
        vis[tp] = 1;
        if(tp == t) continue;
        if(!dp[tp]) return 0;
        for(auto x : ve[tp]){
            que.push(x);
        }
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a,b;cin >> a >> b;
        ve[a].push_back(b);    
    }
    cin >> s >> t;
    dfs(s);
    //for(int i = 1; i <= n; i++){
    //    cout << " " << dp[i] << endl;
//    }
    cout << dp[s] << " ";
    if(bfs()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}
 
  
1-1 新浪微博热门话题
 
#include 
#include 
#include 
#define MAXLENTH 1000007
typedef struct node *Node;
struct node {
    char* KTitle;//整理后的话题
    int Times;//提到次数
    int LastTimeWhoPost;//最近一次提及它的是哪条微博（用于去重）
};
void Scan(int);
int HashKey(char*);
int Mod(int);
void Insert(int,char*);

Node Hash[MAXLENTH];//散列存储
Node Titles[MAXLENTH]; // 建立双索引
int SumofTitles=0;//话题总数

int main() {
    int n;
    scanf("%d",&n);
    getchar();
    for(int i=0; iKTitle,Titles[i]->Times);
        if(Titles[i]->Times>MostTimes->Times) {
            MostTimes=Titles[i];
            NumofMost=0;
        } else if(Titles[i]->Times==MostTimes->Times) {
            if(strcmp(Titles[i]->KTitle,MostTimes->KTitle)<0) {
                MostTimes=Titles[i];
            }
            ++NumofMost;
        }
    }
    if(MostTimes->KTitle[0]>='a'&&MostTimes->KTitle[0]<='z')MostTimes->KTitle[0]+='A'-'a';
    printf("%sn%d",MostTimes->KTitle,MostTimes->Times);
    if(NumofMost) {
        printf("nAnd %d more ...",NumofMost);
    }
    return 0;
}
void Scan(int NumofWeibo) {
    char temp[141];//每行给出一条英文微博，其长度不超过140个字符
//  getchar();
    gets(temp);
    int Flag_Jin=0;
    char title[141];
    int Flag_Space=1;
//  printf("{S-%s}n",temp);
    for(char*i=temp,*j=title; *i!=''; i++) {
        if(Flag_Jin==1) {
            switch(*i) {
                case '#':
                    while(*(j-1)==' ')--j;
                    *j='';
                    if(strlen(title)>0)//两个连续的#是空话题，不予计数
                        Insert(NumofWeibo,title);
                    Flag_Jin=0;                 
                    j=title;
                    break;
                case 'a'...'z':
                case '0'...'9':
                    *j++=*i;
                    Flag_Space=0;
                    break;
                case 'A'...'Z':
                    *j++=*i-'A'+'a';
                    Flag_Space=0;
                    break;
                default:
                    if(Flag_Space==0) {
                        *j++=' ';
                        Flag_Space=1;
                    }
                    break;
            }
        } else if(*i=='#') {
            Flag_Jin=1;
            Flag_Space=1;
        }
    }
}
int HashKey(char*K) {
//  printf("&");
    unsigned int n=0;
    while(*K) {
        n+=*K-'a';
        n<<=5;
//      printf("(%d)",n);
        K++;
    }
//  printf("*-*");
    return n;
}
int Mod(int n) {
    while(n<0)n+=MAXLENTH;
    return n%MAXLENTH;
}
void Insert(int NumofWeibo,char*t) {//比较后插入散列表并更新话题原型
//  printf("{I-%s}",t);
    int Key=HashKey(t);
    int i=0,j=0;
    for( ; i<=MAXLENTH/2; i++) {
        j=Mod(Key+i);
        if(Hash[j]) {
            if(strcmp(t,Hash[j]->KTitle)==0) {
                if(Hash[j]->LastTimeWhoPost==NumofWeibo)return;
                ++Hash[j]->Times;
                Hash[j]->LastTimeWhoPost=NumofWeibo;
//              printf("{add:%s}",Hash[j]->KTitle);
            }
        } else break;
        j=Mod(Key-i);
        if(Hash[j]) {
            if(strcmp(t,Hash[j]->KTitle)==0) {
                if(Hash[j]->LastTimeWhoPost==NumofWeibo)return;
                ++Hash[j]->Times;
                Hash[j]->LastTimeWhoPost=NumofWeibo;
//              printf("{add:%s}",Hash[j]->KTitle);
            }
        } else break;
    }
    if(i>MAXLENTH/2) {
//      printf("NOT ENOUGH SPACE");
        exit(1);
    }
    Hash[j]=(Node)malloc(sizeof(struct node));
    Hash[j]->KTitle=(char*)malloc(strlen(t));
    strcpy(Hash[j]->KTitle,t);
    Hash[j]->Times=1;
    Hash[j]->LastTimeWhoPost=NumofWeibo;
    Titles[SumofTitles++]=Hash[j];//把新加入的元素在哈希表中的地址保存进数组。方便遍历。
//  printf("{new:%s}",Hash[j]->KTitle);
}
 
  
7-1 修理牧场
 
#include
#include
#include
using namespace std;
const int maxn=10010;
 
priority_queue,greater > q;
 
int main(){
    
    int n,k;
    
    cin>>n;
    while(n--){
        
        cin>>k;
        q.push(k);
    }
    
    int ans=0;
    while(q.size()>1){
        
        int x=q.top();
         q.pop();
        
        int y=q.top();
         q.pop();
        
         ans+=x+y;
        q.push(x+y);
        
    }
    cout<
 
1-1 二叉排序树查找操作
 

 BSTree SearchBST(BSTree T,ElemType e){
     if(!T||T->data==e)return T;
     else if(edata)return SearchBST(T->lchild,e);
     else
         return SearchBST(T->rchild,e);
 }
 
2-1 平衡二叉树的根
 
#include 
#include
typedef struct node *AVLTree;
struct node{
    int Data;
    AVLTree Left;
    AVLTree Right;
};
int High(AVLTree T){
    if(!T)
        return 0;
    int left=High(T->Left)+1;
    int right=High(T->Right)+1;
    return left>right?left:right;
}
AVLTree LL(AVLTree T){
    AVLTree T1;
    T1=T->Right;
    T->Right=T1->Left;
    T1->Left=T;
    return T1;
}
AVLTree RR(AVLTree T){
    AVLTree T1;
    T1=T->Left;
    T->Left=T1->Right;
    T1->Right=T;
    return T1;
}
AVLTree LR(AVLTree T){
    AVLTree T1,T2;
    T1=T->Left;
    T2=T1->Right;
    T->Left=NULL;
    T2->Right=T;
    T1->Right=NULL;
    T2->Left=T1;
    return T2;
}
AVLTree RL(AVLTree T){
    AVLTree T1,T2;
    T1=T->Right;
    T2=T1->Left;
    T->Right=NULL;
    T2->Left=T;
    T1->Left=NULL;
    T2->Right=T1;
    return T2;
}
AVLTree Insert(AVLTree T,int x){
    if(!T){
        AVLTree T =(AVLTree)malloc(sizeof(struct node));
        T->Data=x;
        T->Left=T->Right=NULL;
        return T;
    }else if(x>T->Data){
        T->Right=Insert(T->Right,x);
        if((High(T->Right)-High(T->Left))>=2){
            if(x>T->Right->Data)
                T=LL(T);
            else
                T=RL(T);
        }
    }else if(xData){
        T->Left=Insert(T->Left,x);
        if((High(T->Left)-High(T->Right))==2){
            if(xLeft->Data)
                T=RR(T);
            else
                T=LR(T);
        }
    }
    return T;
}
int main() {
    int n,x;
    AVLTree T=NULL;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%d",&x);
        T=Insert(T,x);
    }
    printf("%dn",T->Data);
    return 0;
}
 
1-1 分糖果（循环线性表）
 
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int tangGuo = 0;
        int temp;
        
        int array[] = new int[n];
 
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
 
        while (true) {
                        int x=0; //x用于记录数组中相同元素的个数
            for (int i = 0; i < n; i++) {
 
                if (array[i] % 2 != 0) {
                    array[i]++;
                    tangGuo++;
                }
            }
            for (int i = 0; i < n; i++) {
                array[i] = array[i] / 2;
            }
 
            temp = array[0]; //将第一个元素的一半赋值给临时变量
            for (int i = 0; i < n - 1; i++) {
 
                array[i] = array[i] + array[i + 1];
 
            }
            array[n - 1] = array[n - 1] + temp;
            
            for (int i = 0; i < n - 1; i++) {
                if (array[i] == array[i + 1])
                    ++x;
            }
            if (x == n-1) {
                System.out.print(tangGuo);
                break;
            }
        }
    }
}
 
1-2 表达式转换
 
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        Stack stk = new Stack();
        Map map = new HashMap();
        map.put('+', 1);map.put('-', 1);map.put('*', 2);map.put('/', 2);
        map.put('(', 3);map.put(')', 3);
        int index = 0;
        boolean flag = true;
        while(index < str.length()){
            
            if((index < 1 || str.charAt(index - 1) == '(') && (str.charAt(index) == '+' || str.charAt(index) == '-')  || isdigit(str.charAt(index))){
                if(flag) flag = false;
                else System.out.printf(" ");
                if(str.charAt(index) != '+') System.out.printf("%c", str.charAt(index));
                while(index + 1 < str.length() && (str.charAt(index + 1) == '.' || isdigit(str.charAt(index + 1))))
                    System.out.printf("%c", str.charAt(++index));
                index++;
            }else{
                
                if(str.charAt(index) == '(') stk.push(str.charAt(index));
                else if(str.charAt(index) == ')'){
                    while(!stk.empty() && stk.peek() != '('){
                        System.out.printf(" %c", stk.peek());
                        stk.pop();
                    }
                    stk.pop();
                }else{
                    while(!stk.empty() && stk.peek() != '(' && map.get(stk.peek()) >= map.get(str.charAt(index))){
                        System.out.printf(" %c", stk.peek());
                        stk.pop();
                    }
                    stk.push(str.charAt(index));
                }
                index++;
            }
        }
        while(!stk.empty()){
            System.out.printf(" %c", stk.peek());
            stk.pop();
        }
    }
    static boolean isdigit(char s){
        if(s == '1' || s == '2' || s == '3' || s == '4' || s == '5' || s == '6' || s == '7'
                || s == '8' || s == '9' || s == '0') {
            return true;
        }
        return false;
    }
}
 
3-1 优美的括号序列
 
#include 
 
using namespace std;
char s[1000];
 
int main(){
    while(~scanf("%s",s)){
         int count=0;
         int judge=1;
         int i;
         for(i=0;i