A:Repeating Characters
题意是给出一个重复次数量的R与一个字符串
输出重复后的字符串,很简单的一道题。
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int main() { int t,c,s; char ss[3000]; scanf("%d",&t); while(t--) { scanf("%d %d %s",&c,&s,ss); //cout<<c<<' '<<s<<' '<<ss<<endl; int l = strlen(ss); printf("%d ",c); for(int i=0;i<l;i++) { for(int j=0;j<s;j++) putchar(ss[i]); } printf("\n"); } return 0 ; }
BThe Rascal Triangle
题目给出一个三角形阵和对应数字的求解公式,求任意位置的数值是多少。
咋一看上去没啥规律,但是按照数组的格式写一下就会发现每一个竖行都是从1开始的等差数列,算一下等差比和项数就很容易就能求出来了。
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x3fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; int main() { int p,t; int n,m; scanf("%d",&p); while(p--) { scanf("%d%d%d",&t,&n,&m); if(n<0||m<0||n < m) { printf("%d 0\n",t); continue; } long long ans = 1 + (n - m) * m; printf("%d %lld\n",t,ans); } return 0 ; }
CProgramming The EDSAC
C和D两道题正好凑成一对,一个是小数转二进制,另一个是二进制转小数。
因为最高涉及小数点后16位,直接用double很容易就失去精度,所以两道题都选择了模拟。
事实证明这种样子的模拟我还是能轻松处理的,就是因为这里给出的数都是完全按二进制存法来的(正数向下取整,负数向下取整)所以写得比较繁琐,一开始闹出不少问题。
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x3fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; #define N 1111 int XX[17] = {0,0,0,0,0,1,5,2,5,8,7,8,9,0,6,2,5} ; int YY[17] = {0,9,9,9,9,8,4,7,4,1,2,1,0,9,3,7,5} ; string FK = "PQWERTYUIOJ#SZK*?F@D!HNM&LXGABCV" ; int jian[17]; char s[20]; int ss[20]; int ans[20]; int l,q; int main() { int t,c; scanf("%d",&t); while(t--) { scanf("%d %s",&c,&s); memset(ss,0,sizeof(ss)); memset(ans,0,sizeof(ans)); l = strlen(s); int i; if(s[0] == '-') { i = 1; ans[0] = 1; } else { i =0; ans[0] = 0; } int j = 0; ss[j] = s[i] - '0'; j++; q = 0; for(i = i + 2; i<l; i++) { ss[j] = s[i] - '0'; if(ss[j] > 0) q = 1; j++; } if(q == 0) { if(ans[0] == 1) printf("%d ? 0 F\n",c); else printf("%d P 0 F\n",c); continue; } if(ss[0] > 0) { if((ss[0] ==1&&q == 1)|| ss[0] > 1) { printf("%d INVALID VALUE\n",c); } continue; } q = 0; if(s[0] == '-') { memset(jian,0,sizeof(jian)); jian[0] = 1; for(i=16; i>=0; i--) { ss[i] = jian[i] - ss[i]; if(ss[i] < 0) { ss[i] = ss[i] + 10; jian[i-1] = jian[i-1] - 1; } } q = 1; } for(i = 1; i <= 16; i++) { for(j = 16; j > 0; j--) { ss[j] =ss[j] * 2; } for(j = 16; j > 0; j--) { if(ss[j] >= 10) { ss[j] = ss[j] - 10; ss[j-1]++; } } if(ss[0] == 1) { ss[0] = 0; ans[i] = 1; if(ans[i] == 2) ans[i] = 1; } else { ans[i] = 0; } } if(q == 1) { q = 0; for(i=0; i<17; i++) { if(ss[i] > 0) { q = 1; break; } } if(q == 1) { ans[16] += 1; int i = 16; while(i >= 0 && ans[i] > 1) { ans[i] = ans[i] - 2; i--; ans[i]++; } } } int cc = 0,tt = 0; char fr; for(i=0; i<5; i++) { cc = cc * 2 + ans[i]; } for(i=5; i<16; i++) { tt = tt * 2 + ans[i]; } if(ans[16] == 0) fr = 'F'; else fr = 'D'; printf("%d %c %d %c\n",c,FK[cc],tt,fr); } return 0 ; }
DDecoding EDSAC Data
写C的时候我只把加减法模拟出来了,写到D的时候干脆把二进制一位小数到16为小数都模拟出来直接加。
只能说是习惯去模拟了,还是简单暴力的好~~^_^~~
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int ans[17]; int cal[17]; int jian[17]; int x[16][17] = {0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,2,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,1,2,5,0,0,0,0,0,0,0,0,0,0,0,0,0,1,5,6,2,5,0,0,0,0,0,0,0,0,0,0,0,0,0,7,8,1,2,5,0,0,0,0,0,0,0,0,0,0,0,0,3,9,0,6,2,5,0,0,0,0,0,0,0,0,0,0,0,1,9,5,3,1,2,5,0,0,0,0,0,0,0,0,0,0,0,9,7,6,5,6,2,5,0,0,0,0,0,0,0,0,0,0,4,8,8,2,8,1,2,5,0,0,0,0,0,0,0,0,0,2,4,4,1,4,0,6,2,5,0,0,0,0,0,0,0,0,1,2,2,0,7,0,3,1,2,5,0,0,0,0,0,0,0,0,6,1,0,3,5,1,5,6,2,5,0,0,0,0,0,0,0,3,0,5,1,7,5,7,8,1,2,5,0,0,0,0,0,0,1,5,2,5,8,7,8,9,0,6,2,5} ; string FK = "PQWERTYUIOJ#SZK*?F@D!HNM&LXGABCV" ; char sh,fr; int zh,q; int main() { /*for(int i=0;i<16;i++) { for(int j=0;j<17;j++) { cout<<x[i][j]; } cout<<endl; }*/ int t,c,tt; scanf("%d",&t); while(t--) { scanf("%d %c %d %c",&c,&sh,&zh,&fr); //cout<<c<<' '<<sh<<' '<<zh<<' '<<fr<<endl; memset(ans,0,sizeof(ans)); memset(cal,0,sizeof(cal)); for(int i=0; i<32; i++) { if(FK[i] == sh) { tt = i; } } if(fr == 'F') cal[16] = 0; else cal[16] = 1; int i = 4; while(tt != 0) { cal[i] = tt % 2; tt = tt / 2; i--; } i = 15; tt = zh; while(tt != 0) { cal[i] = tt % 2; tt = tt / 2; i--; } /*for(int i=0;i<17;i++) { cout<<cal[i]; } cout<<endl;*/ for(i=1; i<17; i++) { if(cal[i] == 1) { for(int j=16; j>=0; j--) { ans[j] =ans[j] + x[i-1][j]; if(ans[j] >= 10) { ans[j] = ans[j] - 10; ans[j-1] += 1; } } //cout<<'a'; } } //cout<<endl; if(cal[0] == 1) { memset(jian,0,sizeof(jian)); jian[0] = 1; for(i=16; i>=0; i--) { ans[i] = jian[i] - ans[i]; if(ans[i] < 0) { ans[i] = ans[i] + 10; jian[i-1] = jian[i-1] - 1; } } } /*for(i=0; i<17; i++) { cout<<ans[i]; } cout<<endl;*/ printf("%d ",c); if(cal[0] == 1) printf("-"); printf("%d.%d",ans[0],ans[1]); i = 16; while(i != 0 && ans[i] == 0) i--; int j = 2; while(j <= i) { printf("%d",ans[j]); j++; } printf("\n"); } return 0 ; }
HMaximum in the Cycle of 1
求按照题目给出的计算方法所得出的循环中所得值为k的种数有多少因为n<=20直接各种搜时间消耗为20!肯定超时,所以推规律,得出n和k之间的关系,然后直接按规律计算就行了。
虽说我按位按样例推出了规律,但是很多细节上的东西还是稀里糊涂的。回头再推一下规律是怎么出来的。(按照需求数排列方式数*可以插空的数量*剩余空当的排列数来计算,虽说推出来需求排列数是k!,但是想不通为何,很奇怪。。)
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x3fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; ll s[22]; int c,n,k; void get() { s[0] = s[1] = 1; for(int i=2;i<=20;i++) { s[i] = s[i-1] * i; } } long long cal() { if(k == 1) return s[n-1]; ll ans = 0; ll sum; int kk = k - 2; for(int i = k;i > 1;i--) { sum = 1; for(int j = 0;j < i - 2;j++) { sum = sum * (kk - j) / (j+1); } //cout<<sum<<endl; ans += sum * s[n-i] * s[i-1]; } return ans; } int main() { get(); int t; scanf("%d",&t); while(t--) { scanf("%d%d%d",&c,&n,&k); printf("%d %lld\n",c,cal()); } return 0 ; }