团体程序设计天梯赛-练习集-白红宇

团体程序设计天梯赛-练习集

阅读量：6265 次

发布时间：2019-06-22

本文共 30770 字，大约阅读时间需要 102 分钟。

团体程序设计天梯赛-练习集

题目链接：

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int main(void){ 6     int n; 7     char ch; 8     scanf("%d %c",&n,&ch); 9     int floor=sqrt((n+1.0)/2);10     int res=n-2*floor*floor+1;11     for(int i=floor;i>=1;--i){12         for(int j=0;j

L1-002. 打印沙漏

1 #include
      
        2 #include
       
         3 using namespace std; 4 int a[10]; 5 char s[1005]; 6 int main(void){ 7     scanf("%s",s); 8     for(int i=0;i

L1-003. 个位数统计

1 #include
      
        2 #include
       
         3 using namespace std; 4 struct S{ 5     char id[15]; 6     int a,b; 7 }; 8 bool complare(S x,S y){ 9     return x.a

L1-005. 考试座位号

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define MAX_N 1000 6 #define LL long long 7 using namespace std; 8 int a[MAX_N]; 9 int main(void){10     int n;11     //freopen("in.txt","r",stdin);12     freopen("in.txt","r",stdin);13     freopen("out.txt","w",stdout);14     while(~scanf("%d",&n)){15             memset(a,0,sizeof(a));16     int k=0;17     int start=0;18     int limit=(int)sqrt(n);19     for(int i=2;i<=limit;++i)20         if(n%i==0)21             a[k++]=i;22     a[k++]=n;23     int len=1,temp=1,l=0;24     int store=a[0];25     for(int i=1;i
          
           len){45             len=temp;46             start=l;47         }48     }49     printf("%d\n%d",len,a[start]);50     for(int i=start+1;i

L1-006. 连续因子

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 char a[200]; 7 int main(void){ 8     string b[10]={
    "ling","yi","er","san","si","wu","liu","qi","ba","jiu"}; 9     scanf("%s",a);10     int len=strlen(a);11     if(a[0]=='-')printf("fu");12     else cout<

L1-007. 念数字

1 #include
      
        2 using namespace std; 3 int main(void){ 4     int a,b; 5     scanf("%d%d",&a,&b); 6     int sum=0,k=0; 7     for(int i=a;i<=b;++i){ 8         printf("%5d",i); 9         k++;10         sum+=i;11         if(!(k%5))printf("\n");12     }13     if(k%5)printf("\n");14     printf("Sum = %d\n",sum);15     return 0;16 }

L1-008. 求整数段和

1 #include
      
        2 #include
       
         3 #include
        
          4 #define LL long long 5 using namespace std; 6 LL a[101],b[101]; 7 LL gcd(LL x,LL y){ 8     return y==0?x:gcd(y,x%y); 9 }10 void simple(LL i){11     LL temp=gcd(abs(a[i]),b[i]);12     a[i]/=temp;13     b[i]/=temp;14 }15 int main(void){16     //freopen("1.in.txt","r",stdin);17     LL n;18     scanf("%lld",&n);19     for(LL i=0;i

L1-009. N个数求和

1 #include
      
        2 #include
       
         3 using namespace std; 4 int main(void){ 5     int a[3]; 6     for(int i=0;i<3;++i) 7         scanf("%d",&a[i]); 8     sort(a,a+3); 9     printf("%d->%d->%d\n",a[0],a[1],a[2]);10     return 0;11 }

L1-010. 比较大小

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define N 10000 6 #define LL long long 7 using namespace std; 8 char a[N+1],b[N+1],s[N+1]; 9 bool sb[300];10 int main(void){11     //freopen("1.in.txt","r",stdin);12     gets(a);13     gets(b);14     LL len=strlen(b);15     for(LL i=0;i

L1-011. A-B

1 #include
      
        2 using namespace std; 3 int main(void){ 4     int n; 5     scanf("%d",&n); 6     int temp=1; 7     for(int i=1;i<=n;++i) 8         temp*=2; 9     printf("2^%d = %d\n",n,temp);10     return 0;11 }

L1-012. 计算指数

1 #include
      
        2 #define LL long long 3 using namespace std; 4 int main(void){ 5     LL n; 6     scanf("%lld",&n); 7     LL temp=1; 8     LL sum=0; 9     for(LL i=1;i<=n;++i){10         temp=1;11         for(LL j=1;j<=i;++j){12             temp*=j;13         }14         sum+=temp;15     }16     printf("%lld\n",sum);17     return 0;18 }

L1-013. 计算阶乘和

1 #include
      
        2 using namespace std; 3 int main(void){ 4     int n; 5     char a; 6     scanf("%d %c",&n,&a); 7     for(int i=1;i<=((n+1)/2);++i){ 8         for(int j=1;j<=n;++j) 9             printf("%c",a);10         printf("\n");11     }12     return 0;13 }

L1-015. 跟奥巴马一起画方块

1 #include
      
        2 #include
       
         3 using namespace std; 4 int main(void){ 5     //freopen("in.txt","r",stdin); 6     char z[]={
    '1','0','X','9','8','7','6','5','4','3','2'}; 7     char a[19]; 8     int q[]={
    7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2}; 9     int temp=0;10     int n,m;11     bool flat=false,k=true;12     scanf("%d",&n);13     while(n--){14         memset(a,0,sizeof(a));15         scanf("%s",a);16         flat=false;17         temp=0;18         for(int i=0;i<17;++i){19             if(a[i]<'0'||a[i]>'9'){20                 flat=true;21                 break;22             }23             temp=(temp+q[i]*(a[i]-'0'))%11;24         }25         if(flat){26             printf("%s\n",a);27             k=false;28         }else{29             if(z[temp]!=a[17]){30                 printf("%s\n",a);31                 k=false;32             }33         }34     }35     if(k)printf("All passed\n");36     return 0;37 }

L1-016. 查验身份证

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 string s; 6 int bit,o=1,t; 7 double f=1; 8 int main(void){ 9     cin>>s;10     for(int i=0;i

L1-017. 到底有多二

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 char s[10]; 5 int h,m; 6 int get(int l,int r){ 7     int t=0; 8     for(int i=l;i<=r;++i) 9         t=t*10+s[i]-'0';10     return t;11 }12 int main(void){13     scanf("%s",s);14     h=get(0,1);m=get(3,4);15     if(0<=h&&h<=11)printf("Only %s.  Too early to Dang.",s);16     else if(h==12&&m==0)printf("Only %s.  Too early to Dang.",s);17     else{18         if(h>12)h-=12;19         if(m)h+=1;20         for(int i=0;i

L1-018. 大笨钟

1 #include 
      
        2 using namespace std; 3 int a,b,n,jia,yi; 4 int main(void){ 5     cin>>a>>b>>n; 6     while(n--){ 7         int x,xh,y,yh; 8         cin>>x>>xh>>y>>yh; 9         int t=x+y;10         if(t==xh&&t==yh)continue;11         else if(t==xh)jia++;12         else if(t==yh)yi++;13         if(jia>a){14             cout<<"A\n"<
       
        b){17             cout<<"B\n"<

L1-019. 谁先倒

1 #include 
      
        2 using namespace std; 3 int n,m,p[100000],ans[100000],vis[100000]; 4 int main(void){ 5     scanf("%d",&n); 6     while(n--){ 7         int k; 8         scanf("%d",&k); 9         int x;10         for(int i=0;i

L1-020. 帅到没朋友

1 #include 
      
        2 #include 
       
         3 #define N 10005 4 using namespace std; 5 char a[N],b[N]; 6 int string2int(char a[]){ 7     int temp=0; 8     for(int i=0;i
        
         '9')return -1;10         temp=temp*10+a[i]-'0';11     }12     return temp<=1000&&temp>=1?temp:-1;13 }14 int main(void){15     scanf("%s%*c",a);16     gets(b);17     int x=string2int(a);18     int y=string2int(b);19     printf("%s + %s = ",x==-1?"?":a,y==-1?"?":b);20     if(x!=-1&&y!=-1)printf("%d\n",x+y);21     else puts("?");22 }

L1-025. 正整数A+B

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define N 505 5 using namespace std; 6 const int inf=0x3fffffff; 7 int n,m,s,d,p[N],pre[N],dis[N],per[N],num[N]; 8 bool vis[N]; 9 struct edge{
    int to,w;};10 vector
         
          e[N];11 struct node{12     int u,d;13     bool operator < (const node x)const{
    return d>x.d;}14 };15 priority_queue
          
           q;16 void dij(int s){17     for(int i=0;i
           
            per[v])32 ||dis[u]+w
            
             >n>>m>>s>>d;49 for(int i=0;i
             
              >p[i];50 for(int i=0;i
              
               >u>>v>>w;53 e[u].push_back((edge){v,w});54 e[v].push_back((edge){u,w});55 }56 dij(s);57 cout<
               
                <<" "<
                
                 <<"\n";58 dfs(pre[d]);59 cout<
                 
                  <

L2-001. 紧急救援

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define MAX_N 100000 7 using namespace std; 8 struct TYPE{ 9     int vul,next;10 };11 TYPE a[MAX_N+1];12 int x[MAX_N+1],y[MAX_N+1];13 bool compare[MAX_N+1];14 int main(void){15     freopen("in.txt","r",stdin);16     int adress,n;17     scanf("%d%d",&adress,&n);18     for(int i=0;i

L2-002. 链表去重

1 #include
      
        2 #include
       
         3 #define N 1005 4 #define EPS 1e-8 5 using namespace std; 6 typedef pair
        
          P; 7 P a[N+1]; 8 bool compare(P x,P y){ 9     return (x.second/x.first)>(y.second/y.first);10 }11 int main(void){12     int n;13     double d;14     //freopen("in.txt","r",stdin);15     scanf("%d%lf",&n,&d);16     for(int i=0;i

L2-003. 月饼

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 bool isST(int a[],int l,int r){ 6     if(l>=r)return 1; 7     int key=r; 8     for(int i=l+1;i<=r;++i){ 9         if(a[l]<=a[i]){10             key=i;11             break;12         }13     }14     for(int i=key+1;i<=r;++i)15         if(a[l]>a[i])return 0;16     return isST(a,l+1,key-1)&&isST(a,key,r);17 }18 bool isMirST(int a[],int l,int r){19     if(l>=r)return 1;20     int key=r;21     for(int i=l+1;i<=r;++i){22         if(a[l]>a[i]){23             key=i;24             break;25         }26     }27     for(int i=key+1;i<=r;++i)28         if(a[l]<=a[i])return 0;29     return isMirST(a,l+1,key-1)&&isMirST(a,key,r);30 }31 struct node{32     int vul;33     node *l,*r;34 };35 node *T=NULL;36 node* st(node *t,int key){37     if(t==NULL){38         node *temp=(node*)malloc(sizeof(node));39         temp->vul=key;40         temp->l=NULL;41         temp->r=NULL;42         return temp;43     }44     if(key>=t->vul)t->r=st(t->r,key);45     else t->l=st(t->l,key);46     return t;47 }48 node* Mirst(node *t,int key){49     if(t==NULL){50         node *temp=(node*)malloc(sizeof(node));51         temp->vul=key;52         temp->l=NULL;53         temp->r=NULL;54         return temp;55     }56     if(key
         
          vul)t->r=Mirst(t->r,key);57     else t->l=Mirst(t->l,key);58     return t;59 }60  void printT(node *t){61     if(t==NULL)return;62     printT(t->l);63     printT(t->r);64     if(t!=T)printf("%d ",t->vul);65 }66 int main(void){67     freopen("in.txt","r",stdin);68     int a[1001];69     memset(a,0,sizeof(a));70     int n;71     scanf("%d",&n);72     if(n==0){73         printf("YES\n");74         return 0;75     }76     for(int i=0;i
          
           vul);89     printf("\n");90     return 0;91 }

L2-004. 这是二叉搜索树吗？

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 using namespace std;11 typedef long long ll;12 void debug(int x){13 printf("debug:%d\n",x);14 }15 int n,m,k[55],a[55][10005];16 int same(int u,int v){17 int j=0,cnt=0;18 for(int i=0;i
               
                a[v][j])j++;20 if(a[u][i]==a[v][j])cnt++;21 }22 return cnt;23 }24 int main(void){25 scanf("%d",&n);26 for(int i=0;i

L2-005. 集合相似度

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define N 30 6 using namespace std; 7 struct node{ 8     int vul; 9     node *r,*l;10 };11 queue
          
           q;12 node* creat(int a[],int al,int ar,int b[],int bl,int br){13     if(al>ar||bl>br)return 0;14     int i,k=0;15     for(i=bl;i<=br;++i){16         if(b[i]==a[ar])break;17         k++;18     }19     node *t=(node*)malloc(sizeof(node));20     t->vul=a[ar];21     t->l=creat(a,al,al+k-1,b,bl,i-1);22     t->r=creat(a,al+k,ar-1,b,i+1,br);23     return t;24 }25 int main(void){26     //freopen("in.txt","r",stdin);27     int a[N+1];28     int b[N+1];29     memset(a,0,sizeof(a));30     memset(b,0,sizeof(b));31     int n;32     scanf("%d",&n);33     for(int i=0;i
           
            vul);40 q.push(t);41 while(!q.empty()){42 temp=q.front();43 q.pop();44 if(temp){45 if(temp!=t)printf(" %d",temp->vul);46 q.push(temp->l);47 q.push(temp->r);48 }49 }50 printf("\n");51 return 0;52 }

L2-006. 树的遍历

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #define EPS 1e-8  6 #define N 10000  7 using namespace std;  8 struct node{  9     int house,area; 10 }; 11 struct res{ 12     int num; 13     int people; 14     int house; 15     int area; 16     double rh,ra; 17 }; 18 res r[1000]; 19 int k; 20 node a[N]; 21 int pre[N]; 22 bool mark[N]; 23 void Make(){ 24     for(int i=0;i
          
           y.ra; 38 } 39 int main(void){ 40     freopen("in.txt","r",stdin); 41     int n; 42     scanf("%d",&n); 43     Make(); 44     for(int i=0;i

L2-007. 家庭房产

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 char s[1001]; 6 int a[1001]; 7 int b[1001]; 8 int main(void){ 9     freopen("in.txt","r",stdin);10     gets(s);11     int len=strlen(s);12     for(int i=0;i
         
          =len||i-j<0)break;15             if(s[i-j]==s[i+j])a[i]++;16             else break;17         }18         if(s[i]==s[i+1]){19             for(int j=0;;++j){20                 if(i+1+j>=len||i-j<0)break;21                 if(s[i-j]==s[i+1+j])b[i]++;22                 else break;23             }24         }25     }26     int Max=1;27     for(int i=0;i

L2-008. 最长对称子串

1 #include
      
        2 using namespace std; 3 bool enemy[105][105]; 4 int pre[105]; 5 int Find(int a){ 6     if(a!=pre[a])pre[a]=Find(pre[a]); 7     return pre[a]; 8 } 9 void uion(int a,int b){10     int t1=Find(a),t2=Find(b);11     if(t1!=t2)pre[t1]=t2;12 }13 void make(int n){14     for(int i=1;i<=n;i++)pre[i]=i;15 }16 int main(void){17     int n,m,k;18     scanf("%d%d%d",&n,&m,&k);19     make(n);20     while(m--){21         int a,b,g;22         scanf("%d%d%d",&a,&b,&g);23         if(g==1)uion(a,b);24         else enemy[a][b]=enemy[b][a]=1; //a和b是敌人25     }26     while(k--){27         int a,b;28         scanf("%d%d",&a,&b);29         int ta=Find(a),tb=Find(b);30         if(enemy[a][b]){31             if(ta==tb)printf("OK but...\n");32             else printf("No way\n");33         }else{34             if(ta==tb)printf("No problem\n");35             else printf("OK\n");36         }37     }38     return 0;39 }

L2-009. 抢红包

1 #include
      
        2 using namespace std; 3 bool enemy[105][105]; 4 int pre[105]; 5 int Find(int a){ 6     if(a!=pre[a])pre[a]=Find(pre[a]); 7     return pre[a]; 8 } 9 void uion(int a,int b){10     int t1=Find(a),t2=Find(b);11     if(t1!=t2)pre[t1]=t2;12 }13 void make(int n){14     for(int i=1;i<=n;i++)pre[i]=i;15 }16 int main(void){17     int n,m,k;18     scanf("%d%d%d",&n,&m,&k);19     make(n);20     while(m--){21         int a,b,g;22         scanf("%d%d%d",&a,&b,&g);23         if(g==1)uion(a,b);24         else enemy[a][b]=enemy[b][a]=1;25     }26     while(k--){27         int a,b;28         scanf("%d%d",&a,&b);29         int ta=Find(a),tb=Find(b);30         if(enemy[a][b]){
    //a和b是敌人31             if(ta==tb)printf("OK but...\n");32             else printf("No way\n");33         }else{34             if(ta==tb)printf("No problem\n");35             else printf("OK\n");36         }37     }38     return 0;39 }

L2-010. 排座位

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N 30 5 using namespace std; 6 typedef struct node{ 7     int v; 8     node *l,*r; 9 }*Node;10 int mid[N];//中序11 int pre[N];//前序12 int res[N];//结果13 int n;14 int Find(int x){
    //在中序数组中找树根的位置15     for(int i=0;i
         
          pr)return NULL;23     Node T=(Node)malloc(sizeof(node));24     T->v=pre[pl];25     int t=Find(pre[pl]);26     T->r=Make(pl+1,pl+t-ml,ml,t-1);27     T->l=Make(pl+t-ml+1,pr,t+1,mr);28     return T;29 }30 int main(void){31     scanf("%d",&n);32     for(int i=0;i
          
           q;41     q.push(T);42     int k=0;43     while(!q.empty()){44         Node t=q.front();45         q.pop();46         if(t){47             res[k++]=t->v;48             q.push(t->l);49             q.push(t->r);50         }51     }52 53     printf("%d",res[0]);54     for(int i=1;i

L2-011. 玩转二叉树

1 #include
      
        2 #include
       
         3 using namespace std; 4 int a[1005]; 5 int location(int key){ 6     int k=0; 7     while(a[k]!=key)k++; 8     return k; 9 }10 int transint(char s[]){11     if(s[0]=='-'){12         int temp=0;13         for(int i=1;s[i]!=' '&&s[i]!='\0';i++)14             temp=temp*10+s[i]-'0';15         return -temp;16     }else{17         int temp=0;18         for(int i=0;s[i]!=' '&&s[i]!='\0';i++)19             temp=temp*10+s[i]-'0';20         return temp;21     }22 }23 int main(void){24     int n,m;25     scanf("%d%d",&n,&m);26     for(int i=0;i

L2-012. 关于堆的判断

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define N 505 5 using namespace std; 6 int n,m,k,pre[N],a[5005]; 7 vector
         
          e[N]; 8 set
          
           s,rest; 9 struct node{10     int alert,id;11 }ans[5005];12 void debug(char *a,int x){13     printf("%s:%d\n",a,x);14 }15 int Find(int x){16     return x==pre[x]?x:pre[x]=Find(pre[x]);17 }18 void Union(int a,int b){19     int x=Find(a),y=Find(b);20     if(x!=y)pre[x]=y;21 }22 int main(void){23     for(int i=0;i<=500;++i)pre[i]=i;24     scanf("%d%d",&n,&m);25     for(int i=0;i
           
            =0;--i){46 int x=a[i],pre=-1;47 ans[i]=(node){ 0,x};48 for(int j=0;j

L2-013. 红色警报

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 int a[100005],k,n; 5 int main(void){ 6     cin>>n; 7     for(int i=0;i
        
         >x;10         int idx=lower_bound(a,a+k,x)-a;11         if(idx==k)a[k++]=x;12         else a[idx]=x;13     }14     cout<
         
          <

L2-014. 列车调度

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 int n,k,m; 6 double ans[25]; 7 priority_queue
         
          q; 8 int main(void){ 9     cin>>n>>k>>m;10     for(int i=0;i
          
           >x;15             sum+=x;16             maxn=max(maxn,x);17             minn=min(minn,x);18         }19         q.push(1.0*(sum-minn-maxn)/(k-2));20     }21     for(int i=0;i
           
            =0;--i){26 printf("%.3lf%c",ans[i],i==0?'\n':' ');27 }28 }

L2-015. 互评成绩

1 /* 2 本题坑点： 3 1.题目说的五代（本人、父母、祖父母、曾祖父母、高祖父母）包括外婆那部分. 4 2.查询时有可能查询在本人ID内没出现过的ID（父母的ID） 5 */ 6 #include 
      
        7 #include 
       
         8 #define N 100005 9 using namespace std;10 int n,k;11 bool f;12 set
        
         s;13 struct node{14     int fa,ma;15     char sex;16     node(int FA=-1,int MA=-1,char SEX=0){17         fa=FA;ma=MA;sex=SEX;18     }19 }p[N];20 void dfs_u(int x,int d){21     if(x==-1||d>5)return;22     s.insert(x);23     dfs_u(p[x].fa,d+1);24     dfs_u(p[x].ma,d+1);25 }26 void dfs_v(int x,int d){27     if(!f)return;28     if(x==-1||d>5)return;29     if(s.count(x))f=0;30     dfs_v(p[x].fa,d+1);31     dfs_v(p[x].ma,d+1);32 }33 int main(void){34     scanf("%d",&n);35     for(int i=0;i

L2-016. 愿天下有情人都是失散多年的兄妹

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int INF=-0x3fffffff; 7 stack
          
           s; 8 int dp[101],pre[101],a[10001]; 9 int main(void){10     //freopen("in.txt","r",stdin);11     for(int i=0;i<=100;++i){12         dp[i]=INF;13         pre[i]=-1;14     }15     dp[0]=0;16     int n,m;17     scanf("%d%d",&n,&m);18     for(int i=1;i<=n;++i)19         scanf("%d",&a[i]);20     sort(&a[1],&a[1]+n);21     for(int i=1;i<=n;++i){22         for(int j=m;j>=a[i];--j){23             if(dp[j]<=dp[j-a[i]]+1){24                 dp[j]=dp[j-a[i]]+1;25                 pre[j]=j-a[i];26             }27         }28     }29     if(dp[m]>0){30         int k=m;31         while(pre[k]){32             s.push(k-pre[k]);33             k=pre[k];34         }35         printf("%d",k);36         while(!s.empty()){37             printf(" %d",s.top());38             s.pop();39         }40         printf("\n");41     }else printf("No Solution\n");42     return 0;43 }

L3-001. 凑零钱

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N 100001 5 #define lson l,m,n<<1 6 #define rson m+1,r,n<<1|1 7 using namespace std; 8 stack
         
          pq; 9 int st[N<<2];10 void build(int l,int r,int n,int key);11 void change(int l,int r,int n,int key);12 void updata(int n);13 int query(int l,int r,int n,int key);14 int main(void){15     freopen("in.txt","r",stdin);16     int n,key;17     char s[15];18     scanf("%d",&n);19     while(n--){20         scanf("%s",s);21         switch(s[1]){22     case 'o':23         if(pq.empty())printf("Invalid\n");24         else{25             key=pq.top();26             printf("%d\n",key);27             pq.pop();28             change(1,100000,1,key);29         }30         break;31     case 'u':32         scanf("%d",&key);33         pq.push(key);34         build(1,100000,1,key);35         break;36     case 'e':37         if(pq.empty())printf("Invalid\n");38         else{39             key=pq.size()+1;40             key>>=1;41             printf("%d\n",query(1,100000,1,key));42         }43         break;44     }45     }46     return 0;47 }48 void build(int l,int r,int n,int key){49     if(l>=r){50         st[n]++;51         return;52     }53     int m=(l+r)/2;54     if(key<=m)build(lson,key);55     else build(rson,key);56     updata(n);57 }58 void change(int l,int r,int n,int key){59     if(l==r){60         st[n]--;61         return;62     }63     int m=(l+r)/2;64     if(key<=m)change(lson,key);65     else change(rson,key);66     updata(n);67 }68 void updata(int n){69     st[n]=st[n<<1]+st[n<<1|1];70 }71 int query(int l,int r,int n,int key){72     if(l==r)return l;73     int m=(l+r)/2;74     if(key<=st[n<<1])return query(lson,key);75     else return query(rson,key-st[n<<1]);76 }

L3-002. 堆栈

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N 1005 5 using namespace std; 6 int a[N];//num 7 int pre[N+1]; 8 int r[N];//sum 9 void Make();10 int Find(int n);11 void Uion(int x,int y);12 bool compare(int x,int y){13     return x>y;14 }15 int main(void){16     freopen("in.txt","r",stdin);17     int n;18     Make();19     scanf("%d",&n);20     for(int i=0;i

L3-003. 社交集群

1 /**dfs over_stack**/ 2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 struct position{ 7     int x,y,z; 8 }; 9 int a[65][1291][133];10 int dx[6]={-1,1,0,0,0,0};11 int dy[6]={
    0,0,0,0,1,-1};12 int dz[6]={
    0,0,-1,1,0,0};13 int l,m,n;14 queue
         
          q;15 int bfs(int x,int y,int z);16 int main(void){17     freopen("in.txt","r",stdin);18     int t,sum=0,temp;19     scanf("%d%d%d%d",&m,&n,&l,&t);20     for(int i=0;i
          
           =t)sum+=temp;30                 }31             }32         }33     }34     printf("%d\n",sum);35     return 0;36 }37 int bfs(int x,int y,int z){38     position t,tt;39     t.x=x,t.y=y,t.z=z;40     int temp=0;41     q.push(t);42     while(!q.empty()){43         t=q.front();44         q.pop();45         if(a[t.x][t.y][t.z]){46             temp++;47             a[t.x][t.y][t.z]=0;48             for(int i=0;i<6;++i){49                 tt.x=t.x+dx[i];50                 tt.y=t.y+dy[i];51                 tt.z=t.z+dz[i];52                 if((0<=tt.x&&tt.x
           
            <=tt.y&&tt.y
            
             <=tt.z&&tt.z

L3-004. 肿瘤诊断

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #define N 1000  6 #define M 10  7 #define EPS 1e-8  8 using namespace std;  9 const int INF=0x3fffffff; 10 int mp[N+M+1][N+M+1]; 11 int n,m,d; 12 int Dis[M+1][N+M+1]; 13 bool out[N+M+1]; 14 struct res{ 15     double ave,mindis; 16     int num; 17     bool mark; 18 }; 19 res r[11]; 20 int inti(char a[]); 21 void dijstra(int x); 22 bool compare(res a,res b){ 23     if(a.mindis!=b.mindis) 24         return a.mindis>b.mindis; 25     else{ 26         if(fabs(a.ave-b.ave)
          
           d) 63                     r[i].mark=1; 64                 if(r[i].mindis>Dis[i][j]) 65                     r[i].mindis=Dis[i][j]; 66                 r[i].ave+=Dis[i][j]; 67             } 68         } 69         r[i].ave/=n; 70     } 71     sort(&r[1],&r[1]+m,compare); 72     bool flag=1; 73     for(int i=1;i<=m;i++){ 74         if(r[i].mark)continue; 75         printf("G%d\n",r[i].num); 76         printf("%.1lf %.1lf\n",r[i].mindis,r[i].ave); 77         flag=0; 78         break; 79     } 80     if(flag) 81         printf("No Solution\n"); 82     return 0; 83 } 84 int inti(char a[]){ 85     int len=strlen(a); 86     int temp=0; 87     for(int i=0;i
           
            Dis[x][i]){ 97 Min=Dis[x][i]; 98 index=i; 99 }100 }101 if(Min==INF)break;102 out[index]=0;103 for(int i=1;i<=N+m;++i){104 if(out[i]&&Dis[x][index]+mp[index][i]

L3-005. 垃圾箱分布

1 #include
      
         2 #include
       
          3 #include
        
           4 #define N 505  5 using namespace std;  6 const int INF=0x3f3f3f3f;  7 bool mark[N];  8 int n,Start,End;  9 int lenmp[N][N]; 10 int timemp[N][N]; 11 int lendis[N]; 12 int timedis[N]; 13 int lenpre[N]; 14 int timepre[N]; 15 void lenDijstra(); 16 void timeDijstra(); 17 int main(void){ 18     /**输入**/ 19     memset(lenpre,-1,sizeof(lenpre)); 20     memset(timepre,-1,sizeof(timepre)); 21     int m; 22     scanf("%d%d",&n,&m); 23     for(int i=0;i

times; 50 while(k!=Start){ 51 times.push(k); 52 if(timepre[k]!=lenpre[k])flag=0; 53 k=timepre[k]; 54 } 55 if(flag){ 56 printf("Time = %d;",timedis[End]); 57 printf(" Distance = %d:",lendis[End]); 58 printf("% d",Start); 59 while(!times.empty()){ 60 printf(" => %d",times.top()); 61 times.pop(); 62 } 63 printf("\n"); 64 }else{ 65 printf("Time = %d:",timedis[End]); 66 printf("% d",Start); 67 while(!times.empty()){ 68 printf(" => %d",times.top()); 69 times.pop(); 70 } 71 printf("\n"); 72 printf("Distance = %d:",lendis[End]); 73 printf("% d",Start); 74 stack

diss; 75 k=End; 76 while(k!=Start){ 77 diss.push(k); 78 k=lenpre[k]; 79 } 80 while(!diss.empty()){ 81 printf(" => %d",diss.top()); 82 diss.pop(); 83 } 84 printf("\n"); 85 } 86 return 0; 87 } 88 void lenDijstra(){ 89 int node[N]; 90 memset(node,0,sizeof(node)); 91 node[Start]=1; 92 93 memset(mark,1,sizeof(mark)); 94 lendis[Start]=0; 95 while(1){ 96 int Min=INF,index; 97 for(int i=0;i

lendis[i]){ 99 Min=lendis[i];100 index=i;101 }102 }103 if(Min==INF)break;104 mark[index]=0;105 for(int i=0;i

d){108 lendis[i]=d;109 lenpre[i]=index;110 node[i]=node[index]+1;/*非node[i]++*/111 }else if(mark[i]&&lendis[i]==d&&node[index]+1

timedis[i]){129 Min=timedis[i];130 index=i;131 }132 }133 if(Min==INF)break;134 mark[index]=0;135 for(int i=0;i

t){139 dis[i]=d;140 timedis[i]=t;141 timepre[i]=index;142 }else if(mark[i]&&timedis[i]==t&&dis[i]>d){143 dis[i]=d;144 timepre[i]=index;145 }146 }147 }148 }

L3-007. 天梯地图

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define X first 6 #define Y second 7 #define N 10005 8 using namespace std; 9 int n,m,k;10 bool vis[N];11 vector
          
           e[N];12 struct node{13     int id,d;14     node(int ID=-1,int D=-1){id=ID;d=D;}15     bool operator<(node t)const{16         if(d==t.d)return id>t.id;17         return d
           
            q;27 q.push(ans);28 while(!q.empty()){29 node t=q.front();q.pop();30 if(!vis[t.id]){31 vis[t.id]=1;32 ans=max(ans,t);33 for(int i=0;i<(int)e[t.id].size();++i)34 q.push(node(e[t.id][i],t.d+1));35 }36 }37 return ans.d?ans.id:0;38 }39 int main(void){40 std::ios::sync_with_stdio(false);41 cin>>n>>m>>k;42 for(int i=1;i<=m;++i){43 int u,v;44 cin>>u>>v;45 e[u].push_back(v);46 e[v].push_back(u);47 }48 for(int i=1;i<=k;++i){49 int x;cin>>x;50 cout<
            
             <<"\n";51 }52 }

L3-008. 喊山

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 int n,k,dep,ans[50],d_; 6 struct node{ 7     int x,l,r; 8     node(int X=-1,int L=-1,int R=-1){ 9         x=X;l=L;r=R;10     }11 }a[50];12 void cha(int &rt,int x,int d){13     if(rt==-1){14         rt=k;15         if(d==dep-1)d_++;16         a[k++].x=x;17         return;18     }19     if(a[rt].x
         
          >n;24     for(int i=1;i<=5;++i){25         if((1<
          
           =n+1){26             dep=i;27             break;28         }29     }30     int root=-1;31     for(int i=0;i
           
            >x;34 cha(root,x,1);35 }36 queue
            
             q;37 q.push(0);38 int k=0;39 bool bk=1,complete=1;40 while(!q.empty()){41 int t=q.front();q.pop();42 ans[k++]=a[t].x;43 if(a[t].l!=-1){44 q.push(a[t].l);45 if(!bk)complete=0;46 }else bk=0;47 if(a[t].r!=-1){48 q.push(a[t].r);49 if(!bk)complete=0;50 }else bk=0;51 }52 for(int i=0;i

L3-010. 是否完全二叉搜索树

1 /* 2 本题坑点： 3 1.最快进攻路径的条数指的并非是最合适进攻路径的边数，而是距离最短的路径有多少条 4 */ 5 #include 
      
        6 #include 
       
         7 #include 
         8 #define N 205 9 using namespace std;10 const int inf=0x03ffffff;11 int n,k,mp[N][N],s,t,idx,def[N];12 int pre[N],dis[N],ps[N],num[N],kill[N],vis[N],rount[N];13 string i2s[N];14 map
         
          s2i;15 void debug(string s,int v){16     cout<
          <<":"<
           
            <<"\n";17 }18 void init(){19 string ss,st;20 cin>>n>>k>>ss>>st;21 for(int i=0;i
            
             >s>>df;30 def[idx]=df;31 i2s[idx]=s;32 s2i[s]=idx++;33 }34 s=s2i[ss]=idx;35 i2s[idx]=ss;36 t=s2i[st];37 for(int i=0;i
             
              >su>>sv>>d;41 int u=s2i[su],v=s2i[sv];42 mp[u][v]=min(mp[u][v],d);43 mp[v][u]=min(mp[v][u],d);44 }45 dis[s]=0;num[s]=1;rount[s]=1;46 }47 void dfs_printf(int x){48 if(x==-1)return;49 dfs_printf(pre[x]);50 cout<
              
               <<"->";51 }52 int main(void){53 std::ios::sync_with_stdio(false);54 init();55 while(1){56 int k,maxn=inf;57 for(int i=0;i
               
                d){67 pre[i]=k;68 dis[i]=d;69 num[i]=m;70 ps[i]=p;71 rount[i]=rount[k];72 }else if(dis[i]==d){73 rount[i]+=rount[k];74 if(num[i]