首页 > 代码库 > 11th Iran Nationwide Internet Contest 解题报告
11th Iran Nationwide Internet Contest 解题报告
---恢复内容开始---
题目链接：http://acm.hnu.cn/online/?action=problem&type=list&courseid=283
A：模拟3n+1问题
解题思路：数比较小，直接模拟爆
解题代码：
1 #include<vector> 2 #include<list> 3 #include<map> 4 #include<set> 5 #include<deque> 6 #include<stack> 7 #include<bitset> 8 #include<algorithm> 9 #include<functional>10 #include<numeric>11 #include<utility>12 #include<sstream>13 #include<iostream>14 #include<iomanip>15 #include<cstdio>16 #include<cmath>17 #include<cstdlib>18 #include<cstring>19 #include<ctime>20 #define LL long long21 22 using namespace std;23 char str[1000];24 int a[600];25 int dp[505][505];26 int main(){27 int n ; 28 while(scanf("%d",&n) != EOF,n)29 {30 scanf("%s",str);31 //n = strlen(str);32 for(int i = 1;i <= n;i ++)33 {34 if(str[i-1] == ‘A‘)35 {36 a[i] = 1;37 }else if(str[i-1] == ‘U‘){38 a[i] = -1;39 }else if(str[i-1] == ‘G‘){40 a[i] = 2;41 }else if(str[i-1] == ‘C‘){42 a[i] = -2;43 }44 }45 memset(dp,0,sizeof(dp));46 for(int i = 3;i <= n;i ++ )47 {48 for(int j = i-2;j >= 1;j -- )49 { 50 int t = 0 ;51 for(int s = j+1; s <= i ;s ++ )52 if(dp[i][s] + dp[s-1][j] > t )53 t = dp[i][s] + dp[s-1][j];54 dp[i][j] = t ;55 if(a[i] + a[j] == 0 )56 {57 dp[i][j] = max(dp[i][j],dp[i-1][j+1] + 1);58 }59 }60 }61 printf("%d\n",dp[n][1]);62 //printf("%d\n",dp[13][1]);63 }64 return 0;65 }
B：给你两个文件名，让你比较大小，这里数字和字母是分开比较的，有前导0而且还有大数，所以判断有点繁琐。
解题思路：模拟，暴力
解题代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<ctype.h> 4 char temp11[] = "###"; 5 char str[257] ; 6 char str1[257]; 7 int ok = 0 ; 8 void solve(int fuck) 9 { 10 int t = 0 ; 11 int t1 = 0 ; 12 int len = strlen(str); 13 int len1 = strlen(str1); 14 while(t < len && t1 < len1) 15 { 16 if(isalpha(str[t]) && isalpha(str1[t1])) 17 { 18 if(str[t] == str1[t1]) 19 { 20 t ++ ; 21 t1 ++ ; 22 continue; 23 }else if(isupper(str[t]) && islower(str1[t1])) 24 { 25 if(str[t] - ‘A‘ < str1[t1] -‘a‘) 26 { 27 puts("<"); 28 return; 29 } 30 else if(str[t] - ‘A‘ > str1[t1] -‘a‘) 31 { 32 puts(">"); 33 return; 34 }else if(fuck) 35 { 36 puts(">"); 37 return; 38 } 39 t ++ ; 40 t1 ++ ; 41 }else if(isupper(str1[t1]) && islower(str[t])) 42 { 43 if(str1[t1] - ‘A‘ < str[t] -‘a‘) 44 { 45 puts(">"); 46 return; 47 }else if(str1[t1] - ‘A‘ > str[t] -‘a‘) 48 { 49 puts("<"); 50 return; 51 }else if(fuck) 52 { 53 puts("<"); 54 return; 55 } 56 t ++ ; 57 t1 ++; 58 }else{ 59 if(str1[t1] - ‘a‘ > str[t] - ‘a‘) 60 { 61 puts("<"); 62 return; 63 }else{ 64 puts(">"); 65 return; 66 } 67 } 68 }else if(isdigit(str[t]) && !isdigit(str1[t1])) 69 { 70 puts("<"); 71 return; 72 }else if(isdigit(str1[t1]) && !isdigit(str[t])){ 73 puts(">"); 74 return; 75 }else{ 76 char temp[257]; 77 char temp1[257]; 78 memset(temp,0,sizeof(temp)); 79 memset(temp1,0,sizeof(temp)); 80 int p = -1; 81 int flag ; 82 if(fuck) 83 flag = 1; 84 else flag = 0 ; 85 while(isdigit(str[t])) 86 { 87 if(flag == 0 ) 88 { 89 if(str[t] != ‘0‘) 90 { 91 flag = 1; 92 p ++ ; 93 temp[p] = str[t]; 94 } 95 }else{ 96 p ++ ; 97 temp[p] = str[t]; 98 } 99 t ++ ;100 }101 p = -1;102 if(fuck)103 flag = 1; 104 else flag = 0 ;105 while(isdigit(str1[t1])) 106 {107 if(flag == 0 )108 {109 if(str1[t1] != ‘0‘)110 {111 flag = 1; 112 p ++ ; 113 temp1[p] = str1[t1]; 114 }115 }else{116 p ++ ;117 temp1[p] = str1[t1]; 118 }119 t1 ++ ;120 }121 if(!fuck)122 {123 int len = strlen(temp);124 int len1 = strlen(temp1);125 if(len1 > len)126 {127 puts("<");128 return ;129 }else if(len > len1){130 puts(">");131 return ;132 }else{133 int k = strcmp(temp,temp1);134 if(k < 0)135 {136 puts("<");137 return; 138 }else if(k > 0 ){139 puts(">");140 return;141 }142 }143 }else{144 int k = strcmp(temp,temp1);145 if(k < 0)146 {147 puts("<");148 return; 149 }else if(k > 0 ){150 puts(">");151 return;152 }153 }154 }155 }156 if(t == len && t1 != len1)157 puts("<");158 else if(t1 == len1 && t != len)159 puts(">");160 else{161 ok = 1; 162 }163 }164 int main(){165 while(scanf("%s",str) != EOF)166 {167 if(strcmp(str,temp11) == 0 )168 break;169 scanf("%s",str1);170 if(strcmp(str,str1) == 0 )171 puts("=");172 else {173 ok = 0 ; 174 solve(0);175 if(ok)176 solve(1);177 }178 }179 return 0;180 }
C：题意：给你一串只含有 A U G C 字符组成的字符串，A U 能够连线 ，G，C能够连线，相邻不能连线，且线不能交叉，问你最多能连多少根线，
解题思路：显然这个题目是DP，dp[i][j] =max( dp[i][s] + dp[s-1][j] ,dp[i][j] ,如果ij能连线，还要加上 dp[i-1][j-1] + 1) ，比赛时因为max函数消耗太大而超时
解题代码：
1 #include<vector> 2 #include<list> 3 #include<map> 4 #include<set> 5 #include<deque> 6 #include<stack> 7 #include<bitset> 8 #include<algorithm> 9 #include<functional>10 #include<numeric>11 #include<utility>12 #include<sstream>13 #include<iostream>14 #include<iomanip>15 #include<cstdio>16 #include<cmath>17 #include<cstdlib>18 #include<cstring>19 #include<ctime>20 #define LL long long21 22 using namespace std;23 char str[1000];24 int a[600];25 int dp[505][505];26 int main(){27 int n ; 28 while(scanf("%d",&n) != EOF,n)29 {30 scanf("%s",str);31 //n = strlen(str);32 for(int i = 1;i <= n;i ++)33 {34 if(str[i-1] == ‘A‘)35 {36 a[i] = 1;37 }else if(str[i-1] == ‘U‘){38 a[i] = -1;39 }else if(str[i-1] == ‘G‘){40 a[i] = 2;41 }else if(str[i-1] == ‘C‘){42 a[i] = -2;43 }44 }45 memset(dp,0,sizeof(dp));46 for(int i = 3;i <= n;i ++ )47 {48 for(int j = i-2;j >= 1;j -- )49 { 50 int t = 0 ;51 for(int s = j+1; s <= i ;s ++ )52 if(dp[i][s] + dp[s-1][j] > t )53 t = dp[i][s] + dp[s-1][j];54 dp[i][j] = t ;55 if(a[i] + a[j] == 0 )56 {57 dp[i][j] = max(dp[i][j],dp[i-1][j+1] + 1);58 }59 }60 }61 printf("%d\n",dp[n][1]);62 //printf("%d\n",dp[13][1]);63 }64 return 0;65 }
E：一个长度为 2×n 的字符串，每次有这样的变换规律，i <= n i = i *2 ; i >= n; i = (i-n)*2 +1
解题思路：可知有个2×n的循环节
解题代码：
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月12日 星期五 09时33分05秒 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[300];28 char temp[300];29 char str1[300];30 int main(){31 int n ;32 while(scanf("%d",&n) != EOF,n)33 {34 memset(str,0,sizeof(str));35 memset(str1,0,sizeof(str1));36 memset(temp,0,sizeof(temp));37 scanf("%s",str);38 scanf("%s",&str[n]);39 scanf("%s",str1);40 int ok = 0 ;41 for(int i = 1;i <= 2*n;i ++)42 {43 int b1 = 0 ;44 int b2 = n;45 int t = -1;46 for(int j = 1;j <= n;j ++)47 {48 t ++ ;49 temp[t] = str[b2];50 b2 ++ ;51 t ++;52 temp[t] = str[b1];53 b1 ++ ; 54 }55 //puts(temp);56 if(strcmp(temp,str1) == 0 )57 {58 ok = 1 ; 59 printf("%d\n",i);60 break;61 }62 strcpy(str,temp);63 }64 if(!ok)65 printf("-1\n");66 }67 return 0;68 }
11th Iran Nationwide Internet Contest 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。