首页 > 代码库 > 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 }
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 }
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 }
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 }
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 }
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 }
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 }
HNCPC2012 总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。