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