11th Iran Nationwide Internet Contest 解题报告
浏览数：48 /
时间：2015年06月09日
---恢复内容开始---
题目链接：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 long 21 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 long 21 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 long 25 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 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
