HNCPC2013 总结

一年以后这套题才做的像一点样子。

A：求有偏差的最长回文串，DP或者暴力都行。

  1 // File Name: a.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年10月03日 星期五 12时15分11秒
  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 n;
 28 int lstr;
 29 int lstr1;
 30 char str1[1005];
 31 char str[1005];
 32 int fx[1005];
 33 int dp[1005][1005];
 34 void change()
 35 {
 36     for(int i = 0 ;i < lstr1 ;i ++)
 37     {
 38         if(str1[i] >= 'a' && str1[i] <= 'z')
 39         {
 40             fx[lstr] = i;
 41             str[lstr++]  = str1[i];
 42 
 43         }
 44         else if(str1[i] >= 'A' && str1[i] <= 'Z')
 45         {
 46             fx[lstr] = i;
 47             str[lstr++] = str1[i] -'A' + 'a'; 
 48         }
 49     }
 50 }
 51 int ansb = 0; 
 52 int ansl = 0;
 53 void solve()
 54 {
 55     //puts(str);
 56     for(int i = 0 ;i < lstr ; i ++)
 57     {
 58         dp[i][1] = 0 ; 
 59     }
 60     for(int i = 1;i < lstr;i ++)
 61     {
 62         if(str[i] == str[i-1]) 
 63         {
 64             dp[i][2] = 0;  
 65         }else if(1 <= 2*n){
 66             dp[i][2] = 2; 
 67         }
 68         for(int j = 1;j <= i ;j ++)
 69         {
 70             if(dp[i-1][j] != -1)
 71             {
 72                 if(fx[i-1] - fx[i-j] + 1> ansl)
 73                 {
 74                     ansl = fx[i-1] -fx[i-j] + 1 ; 
 75                     ansb = fx[i-j] +1;
 76                 }
 77                 if(i-1-j >= 0 )
 78                 {
 79                     if(str[i] == str[i-1-j]) 
 80                     {
 81                         dp[i][j+2] = dp[i-1][j];
 82                     }else if(dp[i-1][j] + 1 <= 2 * n){
 83                         dp[i][j+2] = dp[i-1][j] + 2; 
 84                     }
 85                 }
 86             }
 87         }
 88     }
 89     for(int i = 1;i <= lstr;i ++)
 90     {
 91         if(dp[lstr-1][i] != -1 && fx[lstr-1] - fx[lstr-i] +1  > ansl )
 92         {
 93             ansl = fx[lstr-1] - fx[lstr-i] + 1;
 94             ansb = fx[lstr-i] + 1;
 95         }
 96     }
 97 /*    for(int i = 0;i < lstr;i ++)
 98     {
 99         for(int j = 1;j <= i+1;j ++)
100         {
101             printf("%d ",dp[i][j]);
102         }
103         printf("
");
104     }*/
105 
106 }
107 int main(){
108     int ca = 0 ; 
109     while(scanf("%d",&n) != EOF)
110     {
111         getchar();
112         ca ++ ;
113         memset(dp,-1,sizeof(dp));
114         memset(str,0,sizeof(str));
115         gets(str1);
116         lstr1 = strlen(str1);
117         lstr = 0 ; 
118         change(); 
119         ansb = 1; 
120         ansl = 1; 
121         solve();
122         printf("Case %d: %d %d
",ca,ansl,ansb);
123     }
124 
125     return 0;
126 }

View Code

B：交换节点和移动节点，反转链表，求最后的链表。

这题需要用到数组链表实现，注意细节就行

  1 // File Name: b.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年10月03日 星期五 13时30分42秒
  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 100015
 26 using namespace std;
 27 struct node{
 28     int p;
 29     int isf;
 30     int head;
 31     int st,st1;
 32     int L[maxn],R[maxn],V[maxn];
 33     int hs[maxn];
 34     void init()
 35     {
 36         head = 0 ; 
 37         p = 0;      
 38         isf = 0; 
 39     }
 40     void insert(int v)
 41     {
 42         p ++;
 43         L[p] = p-1;
 44         R[p-1] = p;
 45         V[p] = v; 
 46         hs[v] = p ; 
 47     }
 48     void change1(int v ,int v1)
 49     {
 50         st = hs[v];
 51         st1 = hs[v1];
 52         R[L[st]] = R[st];
 53         L[R[st]] = L[st];
 54         L[st] = L[st1];
 55         R[st] = st1;
 56         R[L[st1]] = st;
 57         L[st1] = st; 
 58     }
 59     void change2(int v,int v1)
 60     {
 61         st = hs[v];
 62         st1 = hs[v1];
 63         R[L[st]] = R[st];
 64         L[R[st]] = L[st];
 65         L[st] = st1;
 66         R[st] = R[st1];
 67         L[R[st]] = st;
 68         R[st1] = st;
 69     }
 70     void change3(int v ,int v1)
 71     {
 72         st= hs[v];
 73         st1 = hs[v1];
 74         int tt; 
 75         V[hs[v]] = v1;
 76         V[hs[v1]] = v;
 77         tt = hs[v];
 78         hs[v] = hs[v1];
 79         hs[v1] = tt;
 80     }
 81     void change4(int v,int v1)
 82     {
 83         isf = !isf;
 84     }
 85     LL query()
 86     {
 87        LL sum = 0 ; 
 88        bool iscount = 1; 
 89        if(isf)
 90        {
 91           int next = L[0];
 92           while(next)
 93           {
 94             //printf("%d ",V[next]);
 95             if(iscount)
 96             {
 97               sum += V[next];
 98             }
 99             iscount = !iscount;
100             next = L[next];
101           }
102        }else {
103           int next = R[0];
104           while(next)
105           {
106             //printf("%d ",V[next]);
107             if(iscount)
108             {
109               sum += V[next];
110             }
111             iscount = !iscount;
112             next = R[next];
113           }
114        }
115        //printf("
");
116        return sum;
117     }
118 }lst;
119 
120 int main(){
121     int n ,m ; 
122     int ca = 0 ; 
123     while(scanf("%d %d",&n,&m) != EOF)
124     {
125         ca ++;
126         lst.init();
127         int temp ; 
128         
129         for(int i = 1;i <= n;i ++)
130         {
131             lst.insert(i);
132         }
133         
134         lst.L[0] = lst.p;
135         lst.R[lst.p] = 0;
136         for(int i = 1;i <= m;i ++)
137         {
138           int a, b, c ;
139          // lst.query();
140 
141           scanf("%d",&a);
142           if(a ==  1)
143           {
144             scanf("%d %d",&b,&c);
145             if(lst.isf)
146             {
147                a = 2;
148             }
149           }
150           else if(a == 2)
151           {
152             scanf("%d %d",&b,&c);
153             if(lst.isf)
154             {
155                a = 1;
156             }
157           }
158           if(a == 1)
159           {
160             lst.change1(b,c);
161           }else if(a == 2){
162             lst.change2(b,c); 
163           }else if(a == 3){
164              scanf("%d %d",&b,&c);
165              lst.change3(b,c);
166           }else {
167              lst.change4(b,c);
168           }
169         }
170         printf("Case %d: %lld
",ca,lst.query());
171     }
172     return 0;
173 }

View Code

C：大水题

 1 // File Name: c.cpp
 2 // Author: darkdream
 3 // Created Time: 2014年10月03日 星期五 09时35分22秒
 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[7][60];
28 int main(){
29    int n ;
30    scanf("%d",&n);
31    for(int i = 1;i <= 5;i ++)
32    {
33       scanf("%s",&str[i][1]);
34    }
35    
36    for(int i = 0;i < 4*n-3 ;i += 4)
37    {
38       if(str[4][i+2] == '*') 
39       {
40         printf("1");
41       }else if(str[4][i+1] == '*')
42           printf("2");
43       else printf("3");
44    }
45 return 0;
46 }

View Code

D：删除插入交换矩阵行列，问最后哪些没有移动的点和移动的和是多少，不会

E：计算几何 http://blog.csdn.net/modiz/article/details/39781417

F：去年单向当多向去交T了，今年队友spfa过了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<map>
 4 #include<vector>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<stack>
 8 #include<queue>
 9 #include <iomanip>
10 #include<iostream>
11 #include<algorithm>
12 using namespace std ;
13 const int N = 500 ;
14 const int M = 60000 ;
15 const int inf=1<<30 ;
16 struct node
17 {
18     int u,v,a,b,t,next ;
19 }edge[M] ;
20 int head[N],vist[N],dist[N] ;
21 int top ,n,m,S,T;
22 
23 void add(int u,int v,int a,int b,int t)
24 {
25      edge[top].u=u;
26      edge[top].v=v;
27      edge[top].a=a;
28      edge[top].b=b;
29      edge[top].t=t;
30      edge[top].next=head[u];  
31      head[u]=top++;
32 }
33 
34 int spfa(int s)
35 {
36        int t ;
37        memset(vist,0,sizeof(vist));
38        for(int i = 0 ; i <= n ; i++) dist[i]=inf ;
39        queue<int>q ; 
40        vist[s]=1;
41        dist[s]=0;
42        q.push(s);
43        while(!q.empty())
44        {
45                   int  u = q.front() ;
46                    q.pop() ;
47                    vist[u]=0; 
48                    for(int i = head[u] ; i!=-1 ; i=edge[i].next)
49                    {
50                                 t = 0 ;
51                                 int w = dist[u]%(edge[i].a+edge[i].b) ;
52                                 if(edge[i].a < edge[i].t) continue ;
53                               if(w >= 0 && edge[i].a > w)
54                                 {
55                                        if(edge[i].a - w < edge[i].t)
56                                           t = (edge[i].a+edge[i].b)-w+edge[i].t; 
57                                        else
58                                         t= edge[i].t;
59                                 }else   t = edge[i].a+edge[i].b-w+edge[i].t; 
60                                  if(dist[edge[i].v] > dist[u]+t)
61                                  {
62                                         dist[edge[i].v] = dist[u]+t ;
63                                         if(!vist[edge[i].v])
64                                         {
65                                                vist[edge[i].v] = 1;
66                                                q.push(edge[i].v) ;
67                                         }
68                                  }      
69                    } 
70        }
71      return dist[T] ;
72 }
73 
74 
75 int main()
76 {
77       int tt=0;
78       int u,v,a,b,t ;
79       while(~scanf("%d%d%d%d",&n,&m,&S,&T))
80       {
81                    top=0;
82                  memset(head,-1,sizeof(head)); 
83                  for(int i = 1 ; i <= m ; i++)
84                  {
85                        scanf("%d%d%d%d%d",&u,&v,&a,&b,&t) ;
86                        add(u,v,a,b,t) ;
87                  } 
88                    int ans = spfa(S) ;
89                    printf("Case %d: %d
",++tt,ans);
90       }
91     return 0;
92 }
93

View Code

G：水题从两边循环搜就行。

 1 // File Name: g.cpp
 2 // Author: darkdream
 3 // Created Time: 2014年10月03日 星期五 09时04分49秒
 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[300][10];
28 int  n; 
29 
30 void solve(int k )
31 {
32      if(str[k][0] !='?' )
33      {
34           printf("%s
",str[k]);
35           return ; 
36      }
37     int  l = 0 ; 
38     int  r = 0 ;
39     int i, j ;
40     for(i = k-1 ;i >= 1; i --)
41     {
42       if(str[i][0] == '?')
43       {
44         l ++ ; 
45       }else  break;
46     }
47     if(i == 0 )
48         l = 1e9;
49     for( j = k+1 ;j <= n; j ++)
50     {
51       if(str[j][0] == '?')
52       {
53         r ++ ; 
54       }else  break;
55     }
56     if(j == n +1)
57         r = 1e9;
58     if(l == r)
59     {
60       printf("middle of %s and %s
",str[i],str[j]);
61     }else if(r >  l)
62     {
63       for(int s = 1;s <= l+1;s ++)
64           printf("right of ");
65       printf("%s
",str[i]);
66     }else {
67       for(int s = 1;s <= r+1;s ++)
68           printf("left of ");
69       printf("%s
",str[j]);
70     }
71 }
72 int main(){
73   scanf("%d",&n);
74   for(int i = 1;i <= n;i ++)
75   {
76       scanf("%s",str[i]);
77   }
78   int m ;
79   scanf("%d",&m);
80   for(int i = 1 ;i <=m;i ++)
81   {
82     int q; 
83     scanf("%d",&q);
84     solve(q);
85   }
86 return 0;
87 }

View Code

H：排序以后二分+线段树就行(最后发现这里不需要用到线段树，开头结尾分别加 1 和 -1 累加就行)

  1 // File Name: H.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年10月03日 星期五 09时41分27秒
  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 n , m , k ; 
 28 int a[100005];
 29 struct node{
 30     int l,r;
 31     int col;
 32 }tree[maxn<<2];
 33 int L(int x)
 34 {
 35     return 2 * x ;
 36 }
 37 int R(int x)
 38 {
 39     return 2*x + 1;
 40 }
 41 void pushdown(int c)
 42 {
 43     tree[L(c)].col += tree[c].col;
 44     tree[R(c)].col += tree[c].col;
 45     tree[c].col = 0 ; 
 46 }
 47 void build(int c, int l , int r)
 48 {
 49     tree[c].l = l ; 
 50     tree[c].r = r;
 51     tree[c].col = 0 ; 
 52     if(l == r)
 53     {
 54         return ;
 55     }
 56     build(L(c),l,(l+r)/2);
 57     build(R(c),(l+r)/2+1,r);
 58 }
 59 void update(int c, int l , int r)
 60 {
 61     if(r < l)
 62         return ; 
 63     //printf("%d %d %d
",c,l,r);
 64     if(tree[c].l >= l && tree[c].r <=  r)
 65     {
 66         tree[c].col ++ ; 
 67         return ; 
 68     }
 69     pushdown(c);
 70     int m = (tree[c].l + tree[c].r)/2;
 71     if(l <= m)
 72     {
 73         update(L(c),l,r);
 74     }
 75     if(r > m) {
 76         update(R(c),l,r);
 77     }
 78 }
 79 int ans; 
 80 void solve(int c)
 81 {
 82     if(tree[c].l == tree[c].r)
 83     {
 84         if(tree[c].col >= k )
 85             ans ++ ; 
 86         return;
 87     }
 88     pushdown(c);
 89     solve(L(c));
 90     solve(R(c));
 91 }
 92 int find(int k)
 93 {
 94     int l ,r ;
 95     l = 1; 
 96     r = n; 
 97     while(l <= r)
 98     {
 99         int m = (l + r )/2;
100         if(a[m] > k)
101         {
102             r = m -1;
103         }else {
104             l = m + 1; 
105         }
106     }
107     return r;
108 }
109 int main(){
110     int ca = 0 ; 
111     while(scanf("%d %d %d",&n,&m,&k) != EOF)
112     {
113         ca ++ ; 
114         for(int i = 1;i<= n;i ++)
115         {
116             scanf("%d",&a[i]);
117         }
118         sort(a+1,a+1+n);
119         build(1,1,n);
120         int la = find(1);
121         int x, y;
122         for(int i = 1;i <= m;i++)
123         {
124             scanf("%d %d",&x,&y);
125             x = find(x);
126             y = find(y);
127             update(1,la+1,x);
128             la = y;
129         }
130         ans = 0 ; 
131         solve(1);
132         printf("Case %d: %d
",ca,ans);
133     }
134     return 0;
135 }

View Code

I:看完题以后发现这种变换SPFA可搞，然后就A了。

  1 // File Name: d.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年10月03日 星期五 11时06分10秒
  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 #include<queue>
 25 #include<limits.h>
 26 #define LL long long
 27 
 28 using namespace std;
 29 struct node{
 30   int v;
 31   int st;
 32 }num[100001];
 33 struct node1{
 34   int p;
 35   int v,st;
 36   node1(int z,int x, int y)
 37   {
 38      p = z; 
 39      v = x; 
 40      st = y ; 
 41   }
 42   bool operator <(const node1 b) const {
 43       if(b.v == v)
 44           return st > b.st;
 45       return v > b.v;
 46   } 
 47 };
 48 int change[4][12];
 49 int n , m ,mx; 
 50 void spfa()
 51 {
 52   node1 temp = node1(n,0,0);
 53   priority_queue <node1> Q;
 54   Q.push(temp);
 55   while(!Q.empty())
 56   {
 57      temp = Q.top();
 58      //printf("%d %d %d",temp.p,temp.v,temp.st);
 59      Q.pop();
 60      if(num[temp.p].v != temp.v || num[temp.p].st != temp.st)
 61               continue;
 62         //      printf("****");
 63      int t ;
 64      for(int i = 0;i <= 9 ;i ++)
 65      {
 66        t = temp.p *10 + i ;
 67        if(t > mx )
 68            continue;
 69        if(num[t].v > temp.v + change[1][i] ||(num[t].v == temp.v + change[1][i] && num[t].st > temp.st + 1))
 70        {
 71         num[t].v = temp.v + change[1][i];
 72         num[t].st = temp.st + 1; 
 73         Q.push(node1(t,temp.v+change[1][i],temp.st + 1));
 74        }
 75      }
 76      for(int i = 0;i <= 9 ;i ++)
 77      {
 78        t = temp.p + i ;
 79        if(t > mx)
 80            continue;
 81        if(num[t].v > temp.v + change[2][i] ||(num[t].v == temp.v + change[2][i] && num[t].st > temp.st + 1))
 82        {
 83         num[t].v = temp.v + change[2][i];
 84         num[t].st = temp.st + 1; 
 85         Q.push(node1(t,temp.v+change[2][i],temp.st + 1));
 86        }
 87      }
 88      for(int i = 0;i <= 9 ;i ++)
 89      {
 90        t = temp.p*i ;
 91        if(t > mx)
 92            continue;
 93        if(num[t].v > temp.v + change[3][i] ||(num[t].v == temp.v + change[3][i] && num[t].st > temp.st + 1))
 94        {
 95         num[t].v = temp.v + change[3][i];
 96         num[t].st = temp.st + 1; 
 97         Q.push(node1(t,temp.v+change[3][i],temp.st + 1));
 98        }
 99      }
100   }
101 }
102 int main(){
103   int ca =0 ; 
104   while(scanf("%d %d",&n,&m) != EOF)
105   {
106       ca ++ ;
107       mx = max(n,m);
108       for(int i = 0;i <= mx;i ++)
109       {
110         num[i].v = INT_MAX ; 
111         num[i].st = INT_MAX;
112       }
113       for(int i = 1;i<= 3;i ++)
114          for(int j= 0;j <= 9 ;j ++)
115          {
116             scanf("%d",&change[i][j]);  
117          }
118        change[2][0] = 0 ; 
119        num[n].v = 0 ; 
120        num[n].st = 0; 
121        spfa();
122        printf("Case %d: %d %d
",ca,num[m].v,num[m].st);
123   }
124 return 0;
125 }

View Code

J：水队友A的

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <stack>
10 #include <list>
11 #include <vector>
12 #include <ctime>
13 #define LL __int64
14 #define EPS 1e-8
15 using namespace std;
16 int main()
17 {
18     int cas=1,x,y,i,j;
19     while (~scanf("%d%d",&x,&y))
20     {
21         printf("Case %d: ",cas++);
22         if (x>=1000)
23         {
24             printf("0
");
25             continue;
26         }
27         else
28         {
29             int ans=0;
30             int b=min(1000,y);
31             for (i=x;i<=b;i++)
32                 for (j=i+1;j<=b;j++)
33                 {
34                     if (j*j*j>y*10+3) break;
35                     int s=i*i*i+j*j*j;
36                     if (s%10==3 && s/10<=y && s/10!=i && s/10!=j)
37                     {
38                     //    printf("%d %d
",i,j);
39                         ans++;
40                         if (i!=j) ans++;
41                     }
42                 }
43             printf("%d
",ans);
44         }    
45     }
46     return 0;
47 }

View Code

没有梦想，何谈远方