第一题：题意就是给定n个点每个点可能带表Female或者Male，以及给出各个节点的关系矩阵，让你求出现 AbOr的期望，  、

AbOr这样定义：

1：必须是Male；

2:他至少有m个Female朋友；

刚开始我一直以为求的是AbOr出现的概率，所以显示按每个节点两种状态（F ，M）爆搜所有可能的情况然后除以总的可能（2^N）样例竟然都过了，提交直接TLE因为本菜没有注意到T = 10000 这样复杂度就成了10^4*2^20了，指定超时。后来想到了循环每个节点，然后检查他的哦鞥有节点只有他的朋友节点大于m 才有可讨论性，假设他的朋友节点为ct个，那么他所有的可能是 c(ct,m) ，c(ct,m + 1) ， ct(ct,m + 2) ， ...... ， c(ct,ct);而他的概率全都是 （1/2）（当前节点肯定是M）*（1/2^i) *(1/2^(ct - i)) (m<=i <= ct) 及概率p = 1/2^(ct+1);而且每个情况得概率相同。这样再根据期望公式 　E(X) = X1*p(X1） + X2*p(X2） + …… + Xn*p(Xn)求即可：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 55using namespace std; int pow2[maxn];double c[maxn][maxn];int n,m;char str[maxn][maxn]; int main(){    int i,j,t;    //求2的幂    for (i = 0; i < 21; ++i)    pow2[i] = 1<
         
          = m)            {                //求和后乘以概率                for (int k = m; k <= ct; ++k)                {                    sum += c[ct][k];                }                ans += (1.0/pow2[ct + 1])*sum;            }        }        printf("%.2lf\n",ans);    }    return 0;} /**************************************************************    Problem: 1421    User: gbaoxing    Language: C++    Result: Accepted    Time:10 ms    Memory:1536 kb****************************************************************/
         
        
       
      
     

　　

第二题：

这道题啊，问了虎哥才做出来的，分别开两个数组记录当前节点左边比他小的最近位置，右边比他小的最近位置，然后比较左右距离大小输出即可；

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 1000009using namespace std; int a[maxn],l[maxn],r[maxn];int n;int Abs(int x){    if (x < 0) return -x;    else return x;}int main(){    int i,t;    scanf("%d",&t);    while (t--)    {        scanf("%d",&n);        memset(a,0,sizeof(a));        scanf("%d",&a[1]);        //查找左边的最近的比他小的位置        l[1] = 0;        for (i = 2; i <= n; ++i)        {            scanf("%d",&a[i]);            int pos = i - 1;            while (a[pos] >= a[i])            {                pos = l[pos];                if (pos == 0) break;            }            if (pos == 0) l[i] = 0;            else l[i] = pos;        }        //查找右边的最近的比他小的位置        r[n] = 0;        for (i = n - 1; i >= 1; --i)        {            int pos = i + 1;            while (a[pos] >= a[i])            {                pos = r[pos];                if (pos == 0) break;            }            if (pos == 0) r[i] = 0;            else r[i] = pos;        }        //遍历输出        for (i = 1; i < n; ++i)        {            if (l[i] !=0 && r[i] != 0)            {                int t;                if (Abs(l[i] - i) <= Abs(r[i] - i)) t = l[i];                else t = r[i];                printf("%d ",a[t]);             }            else            {                if (l[i] == 0 && r[i] == 0) printf("0 ");                else                {                    if (l[i] != 0)                    printf("%d ",a[l[i]]);                    else                    printf("%d ",a[r[i]]);                }            }        }         if (l[n] !=0 && r[n] != 0)         {                int t;                if (Abs(l[n] - n) <= Abs(r[n] - n)) t = l[n];                else t = r[n];                printf("%d",a[t]);          }        else        {                if (l[n] == 0 && r[n] == 0) printf("0");                else                {                    if (l[n] != 0)                    printf("%d",a[l[n]]);                    else                    printf("%d",a[r[n]]);                }        }        printf("\n");    }   return 0;} /**************************************************************    Problem: 1422    User: gbaoxing    Language: C++    Result: Accepted    Time:1610 ms    Memory:13228 kb****************************************************************/
        
       
      
     

　　第四题：

题意是给定n个圆，m个描述，x y表示编号为x的圆要套y个圆，题目给出如果重复嵌套只算最外层的嵌套。这道题目trick大大的多，首先看

1：1≤n≤16,0≤m≤100  这里m可能远大于n所以会出现 形如下面的数据

1 2 

1 4

1 6 这样不确定的话输出NO 

如果是：

1 2

1 2 的重复数据要记得去重；

2：. (1≤x≤n,|y|≤1000)y还有可能负值，并且有可能大于 n - 1

所以如果出现这样的数据也指定不可能了。

才开始我使用两个栈来模拟的，s1放需要套圆的圆（即y ！= 0） s2放不需要套圆的圆（即y ==0） 每次从s2中取y个给s1中的圆套，这样就满足了，然后s1的那个出栈，y ==0 压入s2变为可被套的、、知道s2为空即可，我在处理向阳里给的第三组数数据时，直接从m 到 n处理未给定的节点了，其实应该从s1.size() + s2.size()开始的，改后总算A了，整死我了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxn 108using namespace std; struct node{    int x;    int num;}stock[maxn];stack
          
           s1,s2;int n,m,len;int isok(node z){ for (int i = 0; i < len; ++i) { if (stock[i].x == z.x && stock[i].num != z.num) return -1;//判断trick if (stock[i].x == z.x && stock[i].num == z.num) return 0;//去重 } stock[len++] = z; return 1;}int main(){ int i,t; scanf("%d",&t); while (t--) { len = 0; while (!s1.empty()) s1.pop(); while (!s2.empty()) s2.pop(); scanf("%d%d",&n,&m); node p; bool flag = false; for (i = 0; i < m; ++i) { scanf("%d%d",&p.x,&p.num); int mark = isok(p); if (mark == -1) flag = true; else if (mark == 1) { if (p.num) s1.push(p); else s2.push(p); } if (p.num > n - 1 || p.num < 0) flag = true; } if (flag) { printf("NO\n"); continue; } //注意起点。。 for (i = s1.size() + s2.size(); i < n; ++i) { p.num = 0; s2.push(p); } //两个栈的模拟 while (!s1.empty() && !s2.empty()) { node tmp = s1.top(); s1.pop(); if (tmp.num > s2.size()) { flag = true; break; } else { for (i = 0; i < tmp.num; ++i) { s2.pop(); } tmp.num = 0; s2.push(tmp); } } if (s1.empty() && !flag) printf("YES\n"); else printf("NO\n"); } return 0;} /************************************************************** Problem: 1424 User: gbaoxing Language: C++ Result: Accepted Time:10 ms Memory:1516 kb****************************************************************/
          
         
        
       
      
     

　　其实还有一个更容易的办法就是判完trick后，把所有满足条件并且去重之后的y相加，判断是否<= n -1 如果成立YES 否则NO 不知道怎么证明：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std; struct node{    int x;    int y;}p[108];int n,m,len; int isok(node z){    for (int i = 0; i < len; ++i)    {        if (p[i].x == z.x && p[i].y != z.y) return -1;        if (p[i].x == z.x && p[i].y == z.y) return 1;    }    p[len++] = z;    return 0;} int main(){    int i,t;    int x,y;    scanf("%d",&t);    while (t--)    {        len = 0;        scanf("%d%d",&n,&m);        bool flag = false;        node q;        int ct = 0;        for (i = 0; i < m; ++i)        {            scanf("%d%d",&x,&y);            q.x = x; q.y = y;            int mark = isok(q);            if (mark == -1) flag = true;            else if (mark == 0) ct += y;            if (y > n - 1 || y < 0)            flag = true;         }        if (flag)        {            printf("NO\n");            continue;        }        if (ct <= n - 1)  printf("YES\n");        else   printf("NO\n");    }    return 0;} /**************************************************************    Problem: 1424    User: gbaoxing    Language: C++    Result: Accepted    Time:10 ms    Memory:1512 kb****************************************************************/