杭州网络赛的两道水题，4414是暴力搜索，找到满足条件的十字架，4417是简单的线段树，需要查找区间中满足条件的数的个数。

代码如下：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4   5 using namespace std;  6   7 const int maxn = 55;  8 int mp[2][maxn][maxn];  9 char rec[maxn][maxn]; 10  11 void cntVer(int n) { 12     memset(mp[0], -1, sizeof(mp[0])); 13  14     int cnt = 0; 15  16     for (int i = 0; i < n; i++) { 17         cnt = 0; 18         for (int j = 0; j < n; j++) { 19             if (rec[i][j] == 'o') { 20                 if ((cnt & 1) && cnt != 1) { 21                     mp[0][i][j - (cnt >> 1) - 1] = cnt >> 1; 22                 } 23                 cnt = 0; 24             } else { 25                 cnt++; 26             } 27         } 28         if ((cnt & 1) && cnt != 1) mp[0][i][n - (cnt >> 1) - 1] = cnt >> 1; 29     } 30  31 //    puts("ver"); 32 //    for (int i = 0; i < n; i++) { 33 //        for (int j = 0; j < n; j++) { 34 //            printf("%d ", mp[0][i][j]); 35 //        } 36 //        puts(""); 37 //    } 38 } 39  40 void cntHor(int n) { 41     memset(mp[1], -1, sizeof(mp[1])); 42  43     int cnt = 0; 44  45     for (int i = 0; i < n; i++) { 46         cnt = 0; 47         for (int j = 0; j < n; j++) { 48             if (rec[j][i] == 'o') { 49                 if ((cnt & 1) && cnt != 1) { 50                     mp[1][j - (cnt >> 1) - 1][i] = cnt >> 1; 51                 } 52                 cnt = 0; 53             } else { 54                 cnt++; 55             } 56         } 57         if ((cnt & 1) && cnt != 1) mp[1][n - (cnt >> 1) - 1][i] = cnt >> 1; 58     } 59  60 //    puts("hor"); 61 //    for (int i = 0; i < n; i++) { 62 //        for (int j = 0; j < n; j++) { 63 //            printf("%d ", mp[1][i][j]); 64 //        } 65 //        puts(""); 66 //    } 67 } 68  69 bool judge(int x, int y) { 70     if (mp[0][x][y] != mp[1][x][y]) return false; 71     for (int i = 1; i <= mp[0][x][y]; i++) { 72         if (rec[x + 1][y + i] == '#' || rec[x - 1][y + i] == '#') return false; 73         if (rec[x + 1][y - i] == '#' || rec[x - 1][y - i] == '#') return false; 74     } 75     for (int i = 1; i <= mp[1][x][y]; i++) { 76         if (rec[x + i][y + 1] == '#' || rec[x + i][y - 1] == '#') return false; 77         if (rec[x - i][y - 1] == '#' || rec[x - i][y + 1] == '#') return false; 78     } 79  80     return true; 81 } 82  83 int deal(int n) { 84     int cnt = 0; 85  86     for (int i = 1; i < n - 1; i++) { 87         for (int j = 1; j < n - 1; j++) { 88             if (~mp[0][i][j] && ~mp[1][i][j] && judge(i, j)) cnt++; 89         } 90     } 91  92     return cnt; 93 } 94  95 int main() { 96     int n; 97  98 //    freopen("in", "r", stdin); 99     while (~scanf("%d", &n) && n) {100         for (int i = 0; i < n; i++) {101             scanf("%s", rec[i]);102         }103         cntVer(n);104         cntHor(n);105         printf("%d\n", deal(n));106     }107 108     return 0;109 }
        
       
      

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 #define lson l, m, rt << 1 7 #define rson m + 1, r, rt << 1 | 1 8  9 using namespace std;10 typedef vector
          
            vi;11 typedef pair
           
             pii;12 const int maxn = 100001;13 14 vi rec[maxn << 2];15 int ht[maxn];16 17 void build(int l, int r, int rt){18 rec[rt].clear();19 for (int i = l; i <= r; i++){20 rec[rt].push_back(ht[i]);21 }22 int m = (l + r) >> 1;23 24 sort(rec[rt].begin(), rec[rt].end());25 // for (vi::iterator ii = rec[rt].begin(); ii != rec[rt].end(); ii++){26 // printf("%d ", *ii);27 // }28 // puts("end\n");29 if (l == r) return ;30 31 build(lson);32 build(rson);33 }34 35 int query(int L, int R, int key, int l, int r, int rt){36 if (L <= l && r <= R){37 pii tmp;38 39 tmp = equal_range(rec[rt].begin(), rec[rt].end(), key);40 return tmp.second - rec[rt].begin();41 }42 int m = (l + r) >> 1;43 int ret = 0;44 45 if (L <= m) ret = query(L, R, key, lson);46 if (m < R) ret += query(L, R, key, rson);47 48 return ret;49 }50 51 int main(){52 int n, m;53 int T;54 55 scanf("%d", &T);56 for (int i = 1; i <= T; i++){57 scanf("%d%d", &n, &m);58 for (int j = 0; j < n; j++){59 scanf("%d", &ht[j]);60 }61 printf("Case %d:\n", i);62 build(0, n - 1, 1);63 for (int j = 0; j < m; j++){64 int l, r, k;65 66 scanf("%d%d%d", &l, &r, &k);67 printf("%d\n", query(l, r, k, 0, n - 1, 1));68 }69 }70 71 return 0;72 }
           
          
         
        
       
      

 

 ——written by Lyon