首页 > 代码库 > HNCPC2013 总结

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("\n");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\n",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("\n");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\n",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 long25 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:计算几何  不会

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 node17 {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                                        else58                                         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\n",++tt,ans);90       }91     return 0;92 }93  
View Code

H:排序以后二分+线段树就行

  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\n",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\n",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\n",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 __int6414 #define EPS 1e-815 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\n");25             continue;26         }27         else28         {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\n",i,j);39                         ans++;40                         if (i!=j) ans++;41                     }42                 }43             printf("%d\n",ans);44         }    45     }46     return 0;47 }
View Code

 

HNCPC2013 总结