Codeforces 486(#277 Div 2) 解题报告

A：比较简单判断奇偶一个公式即可

 1 // File Name: a.cpp
 2 // Author: darkdream
 3 // Created Time: 2014年11月11日 星期二 22时43分28秒
 4 
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 
26 using namespace std;
27 
28 int main(){
29    LL n ;
30    scanf("%lld",&n);
31    if(n % 2 == 0 )
32        printf("%d
",n/2);
33    else printf("%d
",n/2 -n);
34 return 0;
35 }

View Code

B：默认 A 所有为 1 先把M[i][j] = 0 的i 行 j列覆盖成 0 然后再要得到的A 矩阵运算看能否得出 M

 1 // File Name: b.cpp
 2 // Author: darkdream
 3 // Created Time: 2014年11月11日 星期二 23时03分52秒
 4 
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 
26 using namespace std;
27 int M[200][200];
28 int A[200][200];
29 int n , m ;
30 int dfsr(int k )
31 {
32   for(int i = 1;i <= n;i ++)
33       if(M[i][k] == 0 )
34           return 0 ;
35   return 1;
36 }
37 int dfsc(int k )
38 {
39   //printf("%d
",k);
40   for(int i = 1;i <= m;i ++)
41   {
42 //      printf("***%d %d
",k,i);
43       if(M[k][i] == 0 )
44           return 0 ;
45   }
46   return 1;
47 }
48 int main(){
49    scanf("%d %d",&n,&m);
50    for(int i = 1;i <= n;i ++)
51        for(int j = 1;j <= m;j ++)
52        {
53           scanf("%d",&M[i][j]);
54           A[i][j] = 1; 
55        }
56    for(int i = 1;i <= n;i ++)
57     for(int j = 1;j <= m;j ++)
58     {
59       if(M[i][j] == 0)
60       {
61         //printf("***
");
62         for(int s = 1;s <= m ;s ++)
63         {
64             A[i][s] = 0 ; 
65         }
66         for(int s = 1;s <= n ;s ++)
67         {
68             A[s][j] = 0 ; 
69         }    
70       }
71     }
72    for(int i = 1;i <= n;i ++)
73    {
74        for(int j = 1;j <= m;j ++)
75        {
76            int tmp = 0 ; 
77            for(int s = 1 ; s <= m ;s ++ )
78                tmp |= A[i][s];
79            for(int s = 1 ; s <= n ;s ++ )
80                tmp |= A[s][j];
81            if(tmp != M[i][j])
82            {
83               puts("NO");
84               return 0 ; 
85            }
86        }
87    }
88    printf("YES
");
89    for(int i = 1;i <= n;i ++)
90    {
91       for(int j = 1;j <= m ;j ++)
92             printf("%d ",A[i][j]);
93       printf("
");
94    }
95 return 0;
96 }

View Code

C：这个字符串已知改变的值是已经确定了的。我们只需要看他怎么样移动才能够覆盖掉半边要改变的位置，如果他在左边他只改变左边的是最优的，如果在右边，只

改变右边的也是最优的，如果穿过中线或者边界一定不是最优的了。

 1 // File Name: c.cpp
 2 // Author: darkdream
 3 // Created Time: 2014年11月11日 星期二 23时28分50秒
 4 
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 
26 using namespace std;
27 char str[100005];
28 int num[100005];
29 int vis[100005];
30 int dp[400005];
31   int n , p ; 
32 int solve(int t)
33 {
34     if(t <= 0 )
35     {
36       return n + t;  
37     }
38     if(t > n)
39         return  t- n ;
40 }
41 int main(){
42   scanf("%d %d",&n,&p);
43   scanf("%s",&str[1]); 
44   int sum = 0 ;
45   int num = 0 ; 
46   for(int i = 1;i <= n/2;i ++)
47   {
48      if(str[i] == str[n-i+1])
49          continue;
50      num ++ ; 
51      int mi = min(str[i],str[n-i+1]) ;
52      int mx = max(str[i],str[n-i+1]);
53      sum += min(mx - mi,mi + 26 -mx);
54      vis[i] = 1; 
55      vis[n-i+1] = 1; 
56   }
57   if(sum == 0 )
58   {
59      printf("0
");
60      return 0 ;
61   }
62   
63      int be = 0 ; 
64      int en = 0 ;
65      int qd ;
66      int zd;
67      if(p > n/2)
68      {
69        qd = n/2 +1;
70        zd = n;
71      }else {
72        qd = 1; 
73        zd = n/2;
74      }
75      
76      for(int i = qd;i <= zd;i ++)
77      {
78          if(!be && vis[i] ==1 )
79              be = i ; 
80          if(vis[i])
81             en = i ; 
82      }
83      //printf("%d %d
",be,en);
84      if(p >= en)
85          sum +=  p - be;
86      else if(p <= be)
87          sum +=  en - p;
88      else sum += min(p-be,en-p) + en -be;
89      printf("%d
",sum);
90 return 0;
91 }

View Code

D：从值最小的点开始每个点都要暴搜整颗树，从某个点开始遍历，这个点要是所有遍历到点的最小值且遍历到的点要满足 val[x] - val[这个点] <= d ，子树用树形DP求出，，每搜过一颗树把根标记掉，下次就不能走了。这样就可以得到所有的子树

  1 // File Name: d.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年11月12日 星期三 19时23分45秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 #define maxn 100005 
 26 using namespace std;
 27 int F1[maxn];
 28 int F2[maxn];
 29 int a[maxn];
 30 int vis[maxn];
 31 vector<int> LIS;
 32 int L;
 33 int find(int x)
 34 {
 35    int l = 0; 
 36    int r = LIS.size() - 1;
 37    int m; 
 38    while(l <= r )
 39    {
 40       m = (l + r) >>  1; 
 41      if(x < LIS[m])
 42      {
 43          l = m  + 1;      
 44      }else r = m - 1;
 45    }
 46    //printf("%d %d %d %d
",l,m,a[m],x);
 47    return l; 
 48 }
 49 int main(){
 50      int n; 
 51      scanf("%d",&n);
 52      for(int i = 1;i <= n;i ++)
 53      {
 54         scanf("%d",&a[i]);
 55         int p = upper_bound(LIS.begin(),LIS.end(),a[i]-1) - LIS.begin();
 56         if(p == LIS.size())
 57         {
 58            LIS.push_back(a[i]);
 59         }else{
 60            LIS[p] = a[i];
 61         }
 62         F1[i] = p + 1;  
 63      }
 64      L = LIS.size();
 65      //printf("%d
",L);
 66      LIS.clear();
 67      for(int i = n;i >= 1;i --) 
 68      {
 69         int p = find(a[i]);
 70         if(p == LIS.size())
 71             LIS.push_back(a[i]);
 72         else LIS[p] = a[i];
 73         F2[i] = p+1;
 74         //printf("%d %d
",i,F2[i]);
 75      }
 76 /*     for(int i = 1;i <= n;i ++)
 77          printf("%d*",F1[i]);
 78      printf("
");
 79 */     memset(vis,0,sizeof(vis));
 80      for(int i = 1;i <= n;i ++)
 81      {
 82         // printf("%d ",F2[i]);
 83        if(F1[i] + F2[i] -1== L)
 84            vis[F2[i]] ++ ; 
 85      }
 86      /*for(int i = 1;i <= n;i ++)
 87          printf("%d ",vis[i]);
 88      printf("
");*/
 89      //printf("
");
 90      for(int i = 1;i <= n;i ++)
 91      {
 92        if(F1[i] + F2[i] -1 < L)
 93           printf("1");
 94        else if(vis[F2[i]] == 1)
 95            printf("3");
 96        else printf("2");
 97      }
 98     
 99 return 0;
100 }

View Code

E：

题解：

官方解法2：http://codeforces.com/blog/entry/14678

YYN解法：http://blog.csdn.net/u013368721/article/details/41030775

数列a[i]

F1[i] 表示以a[i]结尾的最长LIS的长度顺序遍历二分求得

F2[i] 表示以a[i]开头的最长LIS的长度逆序遍历二分求得

L是LIS长度,

然后 YYN 和管方的做法就不用了

YYN：

然后分类：

1)F1[i] + F2[i] - 1 < L

2)F1[i] + F2[i] - 1 == L 且 F1[i] 不唯一（这里如何计数唯一和不唯一需要把所有 F1[i] + F2[i] == L 的统计一遍）

3）F1[1] + F2[i] - 1 == L 且 F1[i] 唯一

官方2：

再设一个数列 F[i] 表示如果没有 a[i] LIS 的长度， F[i] = max( 1 <= u <i < v <= n &&a[v] > a[u] |F1[u] + F2[v])

F[i] 需要用到一次线段树和数组离线来统计

然后就是分类

1） F1[i] + F2[i] -1 < L

2) F[i] == L

3) F[i] == L-1

显然 YYN的做法更巧妙 YM + ORZ

YYN做法代码：

  1 // File Name: e.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年11月12日 星期三 00时35分31秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 
 26 using namespace std;
 27 struct node{
 28   int v, p ;
 29   node(int _v ,int _p)
 30   {
 31     v = _v;
 32     p = _p;
 33   }
 34 };
 35 int len = 0 ; 
 36 vector<int>LI;
 37 vector<node> LIS[100005];
 38 int ans[100005];
 39 int np[100005];
 40 int n;
 41 void solve()
 42 {
 43    for(int i = 0;i < len - 1; i ++)
 44    {
 45       int k = LIS[i].size();
 46       if(k == 1)
 47       {
 48          ans[LIS[i][0].p] = 2; 
 49       }
 50    }
 51    int num = LIS[len-1].size();
 52    if(num == 1 )
 53    {
 54          ans[LIS[len-1][0].p] = 2; 
 55    }else{
 56      for(int i = 0 ;i < num;i ++)
 57      {
 58          ans[LIS[i][0].p] = 1; 
 59      }
 60    }
 61    int be = 0;
 62    int en = num -1;
 63    for(int i = len - 2;i >= 1;i --)
 64    {
 65        int num = LIS[i].size(); 
 66        int tbe = -1 ; 
 67        int ten = -1;
 68        int j = 0; 
 69        int s = be; 
 70        {
 71           node tmp = LIS[i][j];
 72           if(tmp.v < LIS[i+1][s].v && tmp.p < LIS[i+1][s].p)
 73           {
 74              if(tbe == -1)
 75              {
 76                 tbe = j ; 
 77              }
 78              ten = j; 
 79           }else if(tmp.v > LIS[i+1][s].v){
 80               
 81           }
 82        }
 83        be = tbe;
 84        en = ten;
 85        if(be == en)
 86        {
 87            ans[LIS[i][be].p] = 2; 
 88        }else
 89          for(int j= be;j <= en;j ++)
 90          {
 91             ans[LIS[i][j].p] = 1; 
 92          }
 93         
 94    }
 95 }
 96 int main(){
 97    int n;
 98    scanf("%d",&n);
 99    len = 0 ; 
100    for(int i = 1;i <= n;i ++)
101    {
102       int t; 
103       scanf("%d",&t);
104       int p = upper_bound(LI.begin(),LI.end(),t) - LI.begin();
105       if(p == LI.size())
106       {
107           LI.push_back(t);
108           len ++;
109       }
110       else LI[p] = t;
111       np[x] = LI[p+1].size() - 1;
112       LIS[p].push_back(node(t,i));
113    }
114    solve();
115    for(int i =1;i <= n;i ++)
116        printf("%d",ans[i]+1);
117 return 0;
118 }

View Code

没有梦想，何谈远方