A -Repeating Characters
A题看样例就可以写了,直接重复就可以了:
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int QuickMod(int a, int b, int n); char num[50]; int main() { int t, n, ca; scanf("%d", &t); while(t--) { mem(num, 0); scanf("%d%d%s", &ca, &n, num); int len = strlen(num); printf("%d ", ca); for(int i = 0; i < len; ++i) { for(int j = 0; j < n; ++j) printf("%c", num[i]); } printf("\n"); } return 0; } int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; }
B -The Rascal Triangle
B题有好几种推法的,我是直接从每一行的第一个开始推,对于第i行,它的第二个数字==1+(n-1)。第二个数==1+(n-1)+(n-3),就这样一直推就可以了,我写的是分成前后两部分算,后来发现直接不管前半部分还是后半部分都适用这个公式,一路算过去就可以了,一个for:
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define maxn 50001 int QuickMod(int a, int b, int n); int main() { int t, ca, n, m; scanf("%d", &t); while(t--) { scanf("%d%d%d", &ca, &n, &m); printf("%d ", ca); long long ans = 1; if(m <= n/2) { int base = 1; for(int i = 1; i <= m; ++i) { ans += (n-base); base += 2; } printf("%lld\n", ans); } else { int cha = n - m - 1; int base = 1; for(int i = 0; i <= cha; ++i) { ans += (n-base); base += 2; } printf("%lld\n", ans); } } return 0; } int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; }
D -Decoding EDSAC Data
D题麻烦的题目,我们一直在搞C题,C题虽然说是和D题是相反的,但是我们的方法在精度这块儿卡死了。好多D都
过了,就先去搞D。D题我们是直接一对一的把这些符号转换成二进制,再把二进制转换成小数(-1.0特判)。一直
没有对负数的二进制求补,所以不对,后来对负数的二进制求了补就出答案了。可是写的太少,在怎么输出这里卡
了好久,最后还是先确定了这个数字应该输出几位,用C++的输出搞定了:
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define ll long long #define eps 1e-20 map <char , string> mm; void init() { mm['P'] = "00000"; mm['Q'] = "00001"; mm['W'] = "00010"; mm['E'] = "00011"; mm['R'] = "00100"; mm['T'] = "00101"; mm['Y'] = "00110"; mm['U'] = "00111"; mm['I'] = "01000"; mm['O'] = "01001"; mm['J'] = "01010"; mm['#'] = "01011"; mm['S'] = "01100"; mm['Z'] = "01101"; mm['K'] = "01110"; mm['*'] = "01111"; mm['?'] = "10000"; mm['F'] = "10001"; mm['@'] = "10010"; mm['D'] = "10011"; mm['!'] = "10100"; mm['H'] = "10101"; mm['N'] = "10110"; mm['M'] = "10111"; mm['&'] = "11000"; mm['L'] = "11001"; mm['X'] = "11010"; mm['G'] = "11011"; mm['A'] = "11100"; mm['B'] = "11101"; mm['C'] = "11110"; mm['V'] = "11111"; } int main() { init(); int T, ca, x; char op1, op2; cin >> T; while(T--) { cin >> ca >> op1 >> x >> op2; printf("%d ",ca); if(op1 == '?' && x == 0 && op2 == 'F') { printf("-1.0\n"); continue; } string tmp = ""; tmp = mm[op1]; string s; for(int i = 15; i >= 5; i--) { if(x%2 == 0) s += '0'; else s += '1'; x /= 2; } reverse(s.begin(), s.end()); tmp += s; if(op2 == 'F') tmp += '0'; else tmp += '1'; int flag=0; if(tmp[0] == '1') { flag = 1; int k; for(int i = 16; i >= 1; i--) { if(tmp[i]=='1') { k = i; break; } } k--; for(int i = 1; i <= k; i++) { if(tmp[i]=='1') tmp[i] = '0'; else tmp[i] = '1'; } } int pos = 1; for(int i=16; i>=1; i--) { if(tmp[i] != '0') { pos = i; break; } } double ans=0,k=0.5; for(int i = 1; i <= pos; i++) { if(tmp[i]=='1') ans+=k; k /= 2; } if(flag == 1) putchar('-'); cout << setiosflags(ios::fixed) << setprecision(pos) << ans << endl; } return 0; }
G -Rancher's Gift
这道题目是一道几何题目,比赛的时候没看懂题目,纠结了就没有做,后来看了,额,就是赤裸裸的计算,给出
A,B,C, D的坐标求出这五个多变形的面积和中间那个四边形的周长。刚刚A掉了,我的方法比较烦,求出了四个
交点的坐标,推导的时候比较繁一点,推出来就是套公式了。剩下的就是算面积而已。分成三角形来算。水了
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define ll long long #define eps 1e-20 double findx(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy) { double fz = (bx - ax)*(cx*dy - cy*dx) - (dx - cx)*(ax*by - ay*bx); double fm = dy*(bx - ax) - cy*(bx - ax) - by*(dx - cx) - ay*(cx - dx); return fz/fm; } double findy(double x, double ax, double ay, double bx, double by) { double fz = (x - ax)*(by - ay); double fm = (bx - ax); return (fz/fm) + ay; } double dis(double x1, double y1, double x2, double y2) { return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)); } double sum(double x1, double y1, double x2, double y2, double x3, double y3) { double len1 = dis(x1, y1, x2, y2); double len2 = dis(x1, y1, x3, y3); double len3 = dis(x2, y2, x3, y3); double S = (len1+len2+len3)/2.0; return sqrt(S * (S - len1) * (S - len2) * (S - len3)); } int main() { double ax, ay, bx, by, cx, cy, dx, dy; ax = 0; ay = 0; by = 0; double abx, aby, bcx, bcy, cdx, cdy, dax, day; double x1, y1, x2, y2, x3, y3, x4, y4; int t, num; scanf("%d", &t); while(t--) { scanf("%d%lf%lf%lf%lf%lf", &num, &bx, &cx, &cy, &dx, &dy); abx = (ax + bx)/2.0; aby = (ay + by)/2.0; bcx = (bx + cx)/2.0; bcy = (by + cy)/2.0; cdx = (cx + dx)/2.0; cdy = (cy + dy)/2.0; dax = (dx + ax)/2.0; day = (dy + ay)/2.0; x1 = findx(ax, ay, bcx, bcy, dx, dy, abx, aby); y1 = findy(x1, ax, ay, bcx, bcy); x2 = findx(ax, ay, bcx, bcy, bx, by, cdx, cdy); y2 = findy(x2, ax, ay, bcx, bcy); x3 = findx(cx, cy, dax, day, bx, by, cdx, cdy); y3 = findy(x3, cx, cy, dax, day); x4 = findx(cx, cy, dax, day, dx, dy, abx, aby); y4 = findy(x4, cx, cy, dax, day); // cout << x1 <<' ' << y1 << endl; // cout << x2 <<' ' << y2 << endl; // cout << x3 <<' ' << y3 << endl; // cout << x4 <<' ' << y4 << endl; double s1, s2, s3, s4, ss; s1 = sum(ax, ay, bx, by, x2, y2)/160; s2 = sum(bx, by, cx, cy, x3, y3)/160; s3 = sum(cx, cy, dx, dy, x4, y4)/160; s4 = sum(ax, ay, dx, dy, x1, y1)/160; ss = (sum(x1, y1, x2, y2, x3, y3) + sum(x1, y1, x3, y3, x4, y4))/160; int lensum = (int)ceil((dis(x1, y1, x2, y2) + dis(x2, y2, x3, y3) + dis(x3, y3, x4, y4) + dis(x4, y4, x1, y1)) * 16.5); printf("%d %.3lf %.3lf %.3lf %.3lf %.3lf %d\n", num, s1, s2, s3, s4, ss, lensum); } }
H -Maximum in the Cycle of 1
H题就是一个排列组合的问题,对于n,对于找到1之前的最大的数字K,求这样的序列有多少个。我们分情况讨论如
果是1的话,那么就是(n-1)!。然后当k大于1的时候,我们就求和,1-k-1一步的情况,然后1-x-k-1, 1-k-x-1
两步的情况,1-x-y-k-1,1-x-k-y-1,1-y-x-k-1,1-y-k-x-1,三步的情况,就这样一直加下去就可以了,其余的数
字全排列就行,就是i步的情况A[i]*C[k-2][i-1]*A[n-i-1];
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define ll long long ll A[19]; ll C[19][19]; void init() { A[0] = 1; A[1] = 1; for(int i = 2; i < 19; ++i) A[i] = i*A[i-1]; C[0][0] = 1; C[1][0] = 1; C[1][1] = 1; for(int i = 2; i < 19; ++i) for(int j = 0; j <= i; ++j) C[i][j] = (A[i]/((A[i-j]*A[j]))); // for(int i = 0; i < 19; ++i) // cout << A[i] << endl; // for(int i = 0; i < 19; ++i) // { // for(int j = 0; j <= i; ++j) // cout << C[i][j] <<' '; // cout << endl; // } } int main() { init(); int t, ca, n, k; scanf("%d", &t); while(t--) { scanf("%d%d%d", &ca, &n, &k); ll ans = 0; printf("%d ", ca); if(k == 1) { printf("%lld\n", A[n-1]); continue; } for(int i = 1; i <= k-1; ++i) ans += (A[i]*C[k-2][i-1]*A[n-i-1]); printf("%lld\n", ans); } return 0; }