首页 > 代码库 > HNCPC2012 总结

HNCPC2012 总结

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 jin(double x)17 {18      if(x - x/1 < 0.5)19         return x/1  ;20     else return x/1 +1; 21 }22 int main()23 {24     25     int n ; 26     scanf("%d",&n);27     for(int i = 1;i <= n;i++)28     {29         int x, y ,z ; 30         scanf("%d %d %d",&x,&y,&z);31         32      33         x = jin(1.0*x * z/(x+y) + 1.0*(x-y) *z/(x+y)); 34         y = z - x; 35         printf("%d\n",x);36     }37     return 0;38 }
View Code

B:水模拟

 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 char str[10004];17 int sta[100005];18 int change(int l,int r)19 {20     int ans = 0 ;21     for(int i= l; i <= r ; i ++)22     {23         ans *= 10 ; 24         ans += str[i] - 0;25     }26     return ans;27 }28 int main()29 {30    int t ;31    scanf("%d",&t); 32    while(t--)33    {34        int n ;35     int s = 0 ; 36     scanf("%d",&n);37     for(int i = 1;i <= n;i++)38     {39      scanf("%s",str);40      if(str[0] == L)41      {42        sta[i] = 1; 43        s -- ;44      }45      else if(str[0] == R)46      {47        sta[i] = 0 ;48        s ++;49      }50      else {51 52         //int k = change(8,p);53         int k ; 54         scanf("%s",str);55         scanf("%d",&k);56         //printf("%d\n",k);57         sta[i] = sta[k];58         if(sta[i])59         {60             s -- ;61         }else s ++ ;   62      }63     } 64     printf("%d\n",s);65    }   66    return 0 ;67 }
View Code

C:细节题 ,用map代码量可能会少一点

  1 // File Name: c.cpp  2 // Author: darkdream  3 // Created Time: 2014年10月07日 星期二 10时06分00秒  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 bstr[1000]; 28 char str[200][5][200]; 29 char str1[200][5][200]; 30 int lstr;  31 int lstr1; 32 void solve(char s[][5][200],int &num) 33 { 34      int p = 0 ; 35      if(bstr[1] == }) 36          return; 37  38      while(bstr[p] != }) 39      { 40         //printf("%d\n",p); 41         num ++ ; 42         int i ;  43         p ++ ;  44         for(i = p ;bstr[i] != : ;i ++)  45         { 46             s[num][1][i-p] = bstr[i];     47         } 48         //printf("%d %s",i,s[num][1]);     49         s[num][1][i-p] = \0; 50         p  = i+1 ;  51         //printf(" %s\n",s[num][1]);     52          53         for(i = p ;bstr[i] != ,&& bstr[i] != };i ++)  54         { 55             s[num][2][i-p] = bstr[i]; 56         } 57     //    printf("%d\n",p);         58         s[num][2][i-p] = \0; 59         p = i;   60      } 61 } 62 int srt[200]; 63 int srt1[200]; 64 int cmp(int a,int b) 65 { 66     if(strcmp(str[a][1],str[b][1]) < 0) 67         return 1; 68     return 0 ;  69 } 70 int cmp1(int a,int b) 71 { 72     if(strcmp(str1[a][1],str1[b][1]) < 0) 73         return 1; 74     return 0 ;  75 } 76 char *push[200]; 77 char *change[200]; 78 char *sub[200]; 79 int lp,lc,ls; 80 int solve() 81 { 82    lp = lc = ls = 0; 83    int p = 1 ;  84    for(int i = 1; i <= lstr1 ;i ++) 85    { 86        int ok = 0 ; 87        int x = srt1[i]; 88        for(int j = p;j <= lstr; j ++) 89        { 90           int y = srt[j]; 91           if(strcmp(str[y][1],str1[x][1]) == 0 ) 92           { 93              for(int s = p ;s < j;s ++) 94              { 95                 ls ++; 96                 sub[ls] = str[srt[s]][1]; 97                //printf("%s\n",str[srt[p]][1]); 98              }  99              p = j+1;100              if(strcmp(str[y][2],str1[x][2]) != 0 )101              {102                 lc ++;103                 change[lc] = str[y][1];104              }105              ok = 1; 106              break;107           }108        }109        if(!ok)110        {111           lp ++ ;112           push[lp] = str1[x][1];113           //printf(" %d %s************************\n",x,str1[x][1]);114        }115    }116    for(;p <= lstr; p ++)117    {118      ls ++ ; 119      sub[ls] = str[srt[p]][1];120      //printf("%s\n",str[srt[p]][1]);121    }122    if(lp != 0 )123    {124      printf("+");125      for(int i = 1;i <= lp ;i ++)126          printf(i == 1?"%s":",%s",push[i]);127      printf("\n");128    }129    if(ls != 0 )130    {131      printf("-");132      for(int i = 1;i <= ls ;i ++)133          printf(i == 1?"%s":",%s",sub[i]);134      printf("\n");135    }136    if(lc != 0 )137    {138      printf("*");139      for(int i = 1;i <= lc ;i ++)140          printf(i == 1?"%s":",%s",change[i]);141      printf("\n");142    }143    if(lp == 0 && ls == 0 && lc ==  0 )144    {145       return 0;    146    }147    return 1;148 }149 int main(){150   int n ; 151   scanf("%d",&n);152   while(n--)153   {154      lstr = 0 ; 155      lstr1 = 0 ;156      scanf("%s",bstr);157      solve(str,lstr);158      /*for(int i = 1;i <= lstr;i ++)159      {160        printf("%s %s ***",str[i][1],str[i][2]);161      }162      printf("***\n");*/163      scanf("%s",bstr);164      solve(str1,lstr1);165      /*for(int i = 1;i <= lstr1;i ++)166      {167        printf("%s %s ***",str1[i][1],str1[i][2]);168      }*/169      for(int i =1;i <= lstr;i ++)170          srt[i] = i ; 171      sort(srt+1,srt+1+lstr,cmp);172      for(int i =1;i <= lstr1;i ++)173          srt1[i] = i ; 174      sort(srt1+1,srt1+1+lstr1,cmp1);175      if(!solve())176          printf("No changes\n");177      printf("\n");178   }179 return 0;180 }
View Code

D:从小数点后枚举这一位 是 0 ,还是  1  装换成大数浮点形 平方以后和 n 比较,确定这一位 ,一直确定到 130位就行

  1 #include <cstdio>  2 #include <cstring>  3 #include <iostream>  4 #include <sstream>  5 #include <algorithm>  6 #include <cmath>  7 using namespace std;  8 int a1[10010],a2[10010],b[10000],c[10000],l1,l2,s[110000];  9 int l3,l4,l5,point,point2,point3,point1; 10 char ans[1000]; 11 char ss[23]; 12 int chengfa() 13 { 14     int pos,i,j; 15     memset(s,0,sizeof(s)); 16     for (i=1;i<=l4;i++) 17         for (j=1,pos=i;j<=l4;j++) 18             s[pos++]+=a2[i]*a2[j]; 19     pos-=1; 20     for (i=1;i<=pos;i++) 21     if (s[i]>=10) 22     { 23         if (i==pos) pos++; 24         s[i+1]+=s[i]/10; 25         s[i]%=10; 26     } 27     return pos; 28 } 29 void jia() 30 { 31     int p=1,i; 32     if (point > point1) 33     { 34         for (i=1;i<=point - point1;i++) 35             a2[p++]=a1[i]; 36         int tt=1; 37         for (i=point - point1+1;i<=l1;i++) 38             a2[p++]=a1[i]+c[tt++]; 39         point2=point; 40     } 41     else 42     { 43         for (i=1;i<=point1-point;i++) 44             a2[p++]=c[i]; 45         int tt=i; 46         for (i=1;i<=l1;i++) 47             a2[p++]=a1[i]+c[tt++]; 48         point2=point1; 49     } 50     int kk=0; 51     p--; 52     for (i=1;i<=p;i++) 53     { 54         a2[i]+=kk; 55         kk=a2[i]/10; 56         a2[i]%=10; 57     } 58     if (kk!=0) a2[++p]=kk; 59     l4=p; 60 } 61 int gobj() 62 { 63     int sl=l5,bl=l2; 64     if (sl-point3>bl) return 1; 65     else if (sl-point3<bl) return -1; 66     while (sl>0 && bl>0) 67     { 68         if (s[sl]>b[bl]) return 1; 69         if (s[sl]<b[bl]) return -1; 70         sl--;bl--; 71     } 72     if (sl==0) return 0; 73     else return 1; 74 } 75 int main() 76 { 77     int T,n; 78     scanf("%d",&T); 79     while (T--) 80     { 81         memset(ans,0,sizeof(ans)); 82         memset(a1,0,sizeof(a1)); 83         memset(a2,0,sizeof(a2)); 84         memset(c,0,sizeof(c)); 85         memset(b,0,sizeof(b)); 86         scanf("%d",&n); 87         getchar(); 88         scanf("%s",&ss); 89         int m=sqrt(n); 90         int mm=m; 91         int j=1; 92         l1=0; 93         point=0; 94         while (mm) 95         { 96             a1[j++]=mm % 10; 97             mm/=10; 98             l1++; 99         }100         point=0;101         mm=n;102         j=1;l2=0;103         while (mm)104         {105             b[j++]=mm%10;106             mm/=10;107             l2++;108         }109         c[1]=1;l3=1;110         int i;111         for (i=1;i<=130;i++)112         {113             for (j=1;j<=l3;j++)114                 c[j]*=5;115             int kk=0;116             for (j=1;j<=l3;j++)117             {118                 c[j]+=kk;119                 kk=c[j]/10;120                 c[j]=c[j]%10;121             }122             if (kk) c[++l3]=kk;123             point1=i;124             jia();125             /*for (j=l4;j>0;j--)126             {127                 if (point2==j) cout<<".";128                 printf("%d",a2[j]);129             }130             cout<<endl;*/131             l5=chengfa(); //平方后长度132             point3=2*point2; //平方后小数点位置133             /*for (j=l5;j>0;j--)134             {135                 if (point3==j) cout<<".";136                 printf("%d",s[j]);137             }138             cout<<endl;*/139             int re=gobj();140             if (re==1) //1:s>b -1:s<b141                 ans[i-1]=0;142             else if (re==-1)143             {144                 ans[i-1]=1;145                 memset(a1,0,sizeof(a1));146                 for (j=1;j<=l4;j++)147                     a1[j]=a2[j];148                 l1=l4;149                 point=point2;150             }151             else break;152         }153         for (j=i;j<=130;j++)154             ans[i]=0;155         ans[130]=\0;156         //cout<<ans<<endl;157         cout<<strstr(ans,ss) - ans << endl;158     }159     return 0;160 }
View Code

E:这题字典树或者 字符串排序(只对下标排序都行  见:http://www.cnblogs.com/zyue/p/4007476.html)

 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 string str[1005];17 int b[1005];18 bool cmp(int a, int b)19 {20      return str[a] < str[b];21 }22 int main()23 {24    int t ; 25    scanf("%d",&t);26    while(t--)27    {28          int n ; 29          scanf("%d",&n);30          for(int i = 1;i <= n;i ++)31             cin >> str[i] ;32          for(int i =1;i <= n;i ++)33            b[i] = i ; 34       sort(b+1,b+1+n,cmp);35      /* for(int i = 1;i <= n;i ++)36           printf("%d ",b[i]);37       printf("\n");38        */   39       int k = 0 ;40       int tk ; 41       int ans = 0 ; 42       for(int i = 2;i <= n;i ++)43       {44            int len1 = str[b[i-1]].size();45            int len2 = str[b[i]].size();46            for(int j = 0 ;j < len1;j++)47            {48                  if(str[b[i-1]][j] != str[b[i]][j])49                  {50                        tk = j + 1;       51                       break;52                  }53          }54          ans += max(k,tk);55         //  printf("%d %d %d\n",k,tk,ans);56          k = tk;  57           58       } 59       ans += k ; 60       printf("%d\n",ans);61    }62    return 0 ;63 }
View Code

F:这个题我们可以看到 点数只有  16个点  我们可以 二进制枚举出要选点所有的情况以后 然后再用prime求出一种情况的答案。比较求得最大值

不过这里有个地方要注意,两点之间可能有多条边,如果是链接矩阵的话要判断一下再加边入阵。

  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 inf = 1<<30 ; 14  15 int n,m,k,tmp; 16 int a[100],g[50][50],dist[100],vis[100],s[100]; 17  18  19 int work1() 20 { 21     int now ,pos=0,cost=0,MIN=inf,num; 22     //memset(vis,0,sizeof(vis)); 23       for(int i = 0 ; i < tmp; i++ ) 24       { 25                 now =s[i] ;    26               dist[now] = g[1][now] ; 27                 vis[now]=0; 28             //  printf("%d ",dist[now]) ; 29       }  // puts(""); 30     vis[1]=1;num=0; 31     for(int i = 1 ; i < tmp ; i++) 32     { 33           MIN=inf ; 34            for(int j = 0 ; j < tmp;j++) 35            { 36                      now = s[j] ; 37                      if(MIN > dist[now] && !vis[now])  38                      { 39                              MIN=dist[now] ; 40                              pos=now ; 41                      } 42            }  43             cost += MIN ;   44             vis[pos]=1; 45             for(int j = 0 ; j < tmp; j++) 46             { 47                    now= s[j] ; 48                    if(dist[now] > g[pos][now] && !vis[now]) 49                        dist[now] = g[pos][now] ;  50             } 51     } 52     int sum = 0; 53     for(int i = 0 ; i < tmp ; i++) 54      {   now = s[i] ; 55          sum += a[now] ; 56          if(vis[now]) num++; 57     }   58     if(cost <= k && num == tmp)   59      return sum ; 60     else  return 0 ;  61 } 62  63 int  print_subset(int x) 64 { 65      tmp =0 ; 66   for(int i=0;i<n;i++) 67    if(x&(1<<i)) 68    { 69            s[tmp++]=i+1; 70             71    } 72    if(s[0]!=1 ) 73      return 0; 74    else return 1;   75 } 76  77 int main() 78 { 79        int t ,u,v,w; 80        scanf("%d",&t) ; 81        while(t--) 82        { 83                   scanf("%d%d%d",&n,&m,&k); 84                   for(int i = 1 ; i <= n ; i++) 85                     for(int j = 1 ; j <= n ;j++) 86                       g[i][j]=inf ; 87                   for(int i = 1 ; i <= n ; i++) 88                     scanf("%d",&a[i]) ;    89                   90                   for(int i = 1 ; i <= m ; i++) 91                   { 92                            scanf("%d%d%d",&u,&v,&w) ; 93                            if(g[u][v]>w) 94                            g[u][v]=g[v][u]=w ;           95               } 96               int ans = 0 ; 97                       98                    for(int i=0;i<(1<<n);i++) 99                 {100                    int flag = print_subset(i);101                         if(tmp==1)102                     {    103                       ans = max(ans,a[1]) ;104                       continue; 105                     } 106                       int ans1 ;107                       if(flag )108                           {  109                           ans1 = work1() ;110                           if(ans1 > ans)111                           {112                                 ans = ans1; 113                              /*     for(int j = 0 ; j < tmp ; j++)114                        printf("%d  ",s[j]) ;115                         puts("");  */116                           }117                          118                           } 119                       else  continue ;120                       121                     }122                 123                  printf("%d\n",ans) ;124        } 125     return 0;126 } 
View Code

 

J:注意到点只有 1000 ,所以直接暴力DP就行  dp[i] 表示为到a[i]这个点最长的公共递增长度。

每一次输入b[j],从头开始枚举,a[i] < b[j] 且 长度最长的值,到了 b[j] = a[i],更新dp[i] 即可

 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 a[1004];17 int b[1004];18 int dp[1004];19 int main()20 {21   int numa,numb;22   int t; 23   scanf("%d",&t);24   while(t--)25   {26         scanf("%d",&numa);27         for(int i= 1;i<= numa;i ++)28            scanf("%d",&a[i]);29         30       scanf("%d",&numb);31       memset(dp,0,sizeof(dp));32         for(int i= 1;i<= numb;i ++)33            {34                  scanf("%d",&b[i]);35                  int mx = 0 ; 36                  for(int j = 1;j <= numa ;j ++)37                  {38                      if(b[i] > a[j])39                      {40                          mx = max(mx,dp[j]);41                      }else if(b[i] == a[j]){42                          dp[j] = mx+1;43                      }44                  }  45            }46         int mx = 0 ;47         for(int i= 1;i <= numa;i ++)48         {49                mx = max(dp[i],mx);50         }51         printf("%d\n",mx);52   } 53   return 0 ; 54 }
View Code

 

HNCPC2012 总结