首页 > 代码库 > MemSQL Start[c]UP 2.0 - Round 1
MemSQL Start[c]UP 2.0 - Round 1
搞了好久才把大部分题目题解看完了，真是太弱了。
A题简单暴力题一个一个匹配，对应位置字母要么相同，要么是‘.‘.
B题给定一个矩阵，左下角(0,0)，右上角(n, m)，取4个不同的点连成一段折线，要有最长的折线长度。
排除n == 0 和m == 0 ，剩下的情况中总共由4中情况：
枚举一下就可以了
1. (0,0)->(n,m)->(0, m)->(n, 0)
2. (0,0)->(n,m)->(n, 0)->(0, m)
3.(n,m-1)->(0,0)->(n,m)->(0,1)
4.(0,m-1)->(n,0)->(0,m)->(n,1)
代码：
1 //Template updates date: 20140718 2 #include <iostream> 3 #include <sstream> 4 #include <cstdio> 5 #include <climits> 6 #include <ctime> 7 #include <cctype> 8 #include <cstring> 9 #include <cstdlib> 10 #include <string> 11 #include <stack> 12 #include <set> 13 #include <map> 14 #include <cmath> 15 #include <vector> 16 #include <queue> 17 #include <algorithm> 18 #define esp 1e-6 19 #define inf 0x3f3f3f3f 20 #define pi acos(-1.0) 21 #define pb push_back 22 #define lson l, m, rt<<1 23 #define rson m+1, r, rt<<1|1 24 #define lowbit(x) (x&(-x)) 25 #define mp(a, b) make_pair((a), (b)) 26 #define bit(k) (1<<(k)) 27 #define iin freopen("pow.in", "r", stdin); 28 #define oout freopen("pow.out", "w", stdout); 29 #define in freopen("solve_in.txt", "r", stdin); 30 #define out freopen("solve_out.txt", "w", stdout); 31 #define bug puts("********))))))"); 32 #define Inout iin oout 33 #define inout in out 34 35 #define SET(a, v) memset(a, (v), sizeof(a)) 36 #define SORT(a) sort((a).begin(), (a).end()) 37 #define REV(a) reverse((a).begin(), (a).end()) 38 #define READ(a, n) {REP(i, n) cin>>(a)[i];} 39 #define REP(i, n) for(int i = 0; i < (n); i++) 40 #define VREP(i, n, base) for(int i = (n); i >= (base); i--) 41 #define Rep(i, base, n) for(int i = (base); i < (n); i++) 42 #define REPS(s, i) for(int i = 0; (s)[i]; i++) 43 #define pf(x) ((x)*(x)) 44 #define mod(n) ((n)) 45 #define Log(a, b) (log((double)b)/log((double)a)) 46 #define Srand() srand((int)time(0)) 47 #define random(number) (rand()%number) 48 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a) 49 50 using namespace std; 51 typedef long long LL; 52 typedef unsigned long long ULL; 53 typedef vector<int> VI; 54 typedef pair<int,int> PII; 55 typedef vector<PII> VII; 56 typedef vector<PII, int> VIII; 57 typedef VI:: iterator IT; 58 typedef map<string, int> Mps; 59 typedef map<int, int> Mpi; 60 typedef map<int, PII> Mpii; 61 typedef map<PII, int> Mpiii; 62 double ans[4]; 63 64 int main() { 65 66 int n, m; 67 cin>>n>>m; 68 if(n == 0) { 69 printf("%d %d\n", 0, 1); 70 printf("%d %d\n", 0, m); 71 printf("%d %d\n", 0, 0); 72 printf("%d %d\n", 0, m-1); 73 } else if(m == 0) { 74 printf("%d %d\n", 1, 0); 75 printf("%d %d\n", n, 0); 76 printf("%d %d\n", 0, 0); 77 printf("%d %d\n", n-1, 0); 78 } else { 79 ans[0] = m + 2*sqrt(pf(n)+pf(m)); 80 ans[1] = n + 2*sqrt(pf(n)+pf(m)); 81 ans[2] = sqrt(pf(n)+pf(m))+sqrt(pf(n)+pf(m-1))*2; 82 ans[3] = sqrt(pf(n)+pf(m))+sqrt(pf(n-1)+pf(m))*2; 83 int tmp = 0; 84 REP(i, 4) 85 if(ans[tmp] < ans[i]) 86 tmp = i; 87 if(tmp == 0) { 88 printf("%d %d\n", 0, 0); 89 printf("%d %d\n", n, m); 90 printf("%d %d\n", n, 0); 91 printf("%d %d\n", 0, m); 92 } else if(tmp == 1) { 93 printf("%d %d\n", 0, 0); 94 printf("%d %d\n", n, m); 95 printf("%d %d\n", 0, m); 96 printf("%d %d\n", n, 0); 97 } else if(tmp == 3) { 98 printf("%d %d\n", 1, m); 99 printf("%d %d\n", n, 0);100 printf("%d %d\n", 0, m);101 printf("%d %d\n", n-1, 0);102 } else {103 printf("%d %d\n", n, m-1);104 printf("%d %d\n", 0, 0);105 printf("%d %d\n", n, m);106 printf("%d %d\n", 0, 1);107 }108 }109 return 0;110 }
C题:有n种卡片，每种m张,魔术师每次从中选取n张然后给观众选取，自己再从中选出一张，问最后选得的和观众相同的概率是多少？
分析：由于最后选得的相同的卡片肯定是n种中一种，而且是哪种不重要，这样只需考虑，该种卡片在选出的n张牌占多少？
选出卡片中该种有i张，然后最后魔术师和观众选中该种卡片，这样概率就是：C(m,i)*C((n-1)m, n-i)*(i/n)^2/C(nm,n) 1<=i<=min(n, m)
由于对应n种卡片都是上面这样计算的，所以上面结果*n就是最后结果了。
最后计算时候可以用log这样乘除法转化为+，-,对于概率计算很方便，对结果取一下e^ans放就可以了。
1 //Template updates date: 20140718 2 #include <iostream> 3 #include <sstream> 4 #include <cstdio> 5 #include <climits> 6 #include <ctime> 7 #include <cctype> 8 #include <cstring> 9 #include <cstdlib>10 #include <string>11 #include <stack>12 #include <set>13 #include <map>14 #include <cmath>15 #include <vector>16 #include <queue>17 #include <algorithm>18 #define esp 1e-619 #define inf 0x3f3f3f3f20 #define pi acos(-1.0)21 #define pb push_back22 #define lson l, m, rt<<123 #define rson m+1, r, rt<<1|124 #define lowbit(x) (x&(-x))25 #define mp(a, b) make_pair((a), (b))26 #define bit(k) (1<<(k))27 #define iin freopen("pow.in", "r", stdin);28 #define oout freopen("pow.out", "w", stdout);29 #define in freopen("solve_in.txt", "r", stdin);30 #define out freopen("solve_out.txt", "w", stdout);31 #define bug puts("********))))))");32 #define Inout iin oout33 #define inout in out34 35 #define SET(a, v) memset(a, (v), sizeof(a))36 #define SORT(a) sort((a).begin(), (a).end())37 #define REV(a) reverse((a).begin(), (a).end())38 #define READ(a, n) {REP(i, n) cin>>(a)[i];}39 #define REP(i, n) for(int i = 0; i < (n); i++)40 #define VREP(i, n, base) for(int i = (n); i >= (base); i--)41 #define Rep(i, base, n) for(int i = (base); i < (n); i++)42 #define REPS(s, i) for(int i = 0; (s)[i]; i++)43 #define pf(x) ((x)*(x))44 #define mod(n) ((n))45 #define Log(a, b) (log((double)b)/log((double)a))46 #define Srand() srand((int)time(0))47 #define random(number) (rand()%number)48 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)49 50 using namespace std;51 typedef long long LL;52 typedef unsigned long long ULL;53 typedef vector<int> VI;54 typedef pair<int,int> PII;55 typedef vector<PII> VII;56 typedef vector<PII, int> VIII;57 typedef VI:: iterator IT;58 typedef map<string, int> Mps;59 typedef map<int, int> Mpi;60 typedef map<int, PII> Mpii;61 typedef map<PII, int> Mpiii;62 double nCr(int n, int m) {63 double res = 0;64 Rep(i, 1, m+1)65 res += -log(i)+log(n-i+1);66 return res;67 }68 void solve(int n, int m) {69 int M = min(n, m);70 double ans = 0;71 Rep(i, 1, M+1) {72 double tmp = 2*(log(i)-log(n))+log(n)+nCr(m, i)+nCr((n-1)*m, n-i)-nCr(n*m, n);73 ans += exp(tmp);74 }75 printf("%.9f\n", ans);76 }77 int main() {78 int n, m;79 cin>>n>>m;80 solve(n, m);81 return 0;82 }
D题：有k件衣服，每件必须先后并且连续经过3种操作，洗涤，烘干，折叠，分别由3种机器来完成，其中机器数目为n1,n2,n3,一个机器只能同时对一件衣服进行对应操作。其中衣服完成每种操作的时间为t1,t2,t3.求最后完成所有衣服3种操作的最短时间。
分析：由于每种操作最多可能处理ni件衣服所以第ni+1件衣服和第1件衣服的开始处理时间必须相差ti，根据这个可以推理最终完成时间。
代码：
//Template updates date: 20140718#include <bits/stdc++.h>#define esp 1e-6#define inf 0x3f3f3f3f#define pi acos(-1.0)#define pb push_back#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define lowbit(x) (x&(-x))#define mp(a, b) make_pair((a), (b))#define bit(k) (1<<(k))#define iin freopen("pow.in", "r", stdin);#define oout freopen("pow.out", "w", stdout);#define in freopen("solve_in.txt", "r", stdin);#define out freopen("solve_out.txt", "w", stdout);#define bug puts("********))))))");#define Inout iin oout#define inout in out#define SET(a, v) memset(a, (v), sizeof(a))#define SORT(a) sort((a).begin(), (a).end())#define REV(a) reverse((a).begin(), (a).end())#define READ(a, n) {REP(i, n) cin>>(a)[i];}#define REP(i, n) for(int i = 0; i < (n); i++)#define VREP(i, n, base) for(int i = (n); i >= (base); i--)#define Rep(i, base, n) for(int i = (base); i < (n); i++)#define REPS(s, i) for(int i = 0; (s)[i]; i++)#define pf(x) ((x)*(x))#define mod(n) ((n))#define Log(a, b) (log((double)b)/log((double)a))#define Srand() srand((int)time(0))#define random(number) (rand()%number)#define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> PII;typedef vector<PII> VII;typedef vector<PII, int> VIII;typedef VI:: iterator IT;typedef map<string, int> Mps;typedef map<int, int> Mpi;typedef map<int, PII> Mpii;typedef map<PII, int> Mpiii;int n, n1, n2, n3, t1, t2, t3;const int maxn = 10000 + 100;int w[maxn];int main() { scanf("%d%d%d%d%d%d%d", &n, &n1, &n2, &n3, &t1, &t2, &t3); Rep(i, 1, n+1) { int c = 0; if(i > n1) c = max(c, w[i-n1]+t1); if(i > n2) c = max(c, w[i-n2]+t2); if(i > n3) c = max(c, w[i-n3]+t3); w[i] = c; if(i == n) cout<<c+t1+t2+t3<<endl; } return 0;}
E题：给定3个串s1,s2,s3,对每一个l(1<=l<=min(|s1|,|s2|,|s3|))求三元组(i,j,k)的个数，三元组是指满足
s1[i,i+l-1], s2[j,j+l-1],s3[k,k+l-1]是完全相同字符串的条件。
分析：表示知道用后缀数组处理，然后就不知道怎么做了，看了题解还是有点不明白，先留个坑，
F题：给定一个数组a[1...n]，为1....n的数的排列， n<=300000,是否存在两个数a，b，a+b/2在这数组中位于这两个数之间。实际就是判断是否三个数构成等差数列。
分析：这题要用线段树+hash来维护，首先容易知道，a,b,c构成等差那么 a，b之差与b,c之差是相等的，那么过程是这样的依次每次取出一个数a[i]，然后把a[i]和n-a[i]+1插入到两棵线段树中；如果不存在两个数与a[i]构成等差数列，例如数组中10个元素，对于2,5,8，5不能和2,8构成等差，2,8在数组中位置要么在5前面，要么在5后面，如果2,8在前面，那么将2,8以及10-2+1 = 9,10-8+1=3插入后，两棵线段树相应位置均会被增加相同元素，这样对应的线段树就应该都是序列2...8,那么比较两棵线段树相应区间hash值就可以了。同样对于2,8出现在5后面也可以判断。
一旦遇到hash值不同的情况说明存在等差数列。
代码：
1 //Template updates date: 20140718 2 #include <bits/stdc++.h> 3 #define esp 1e-6 4 #define inf 0x3f3f3f3f 5 #define pi acos(-1.0) 6 #define pb push_back 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 #define lowbit(x) (x&(-x)) 10 #define mp(a, b) make_pair((a), (b)) 11 #define bit(k) (1<<(k)) 12 #define iin freopen("pow.in", "r", stdin); 13 #define oout freopen("pow.out", "w", stdout); 14 #define in freopen("solve_in.txt", "r", stdin); 15 #define out freopen("solve_out.txt", "w", stdout); 16 #define bug puts("********))))))"); 17 #define Inout iin oout 18 #define inout in out 19 20 #define SET(a, v) memset(a, (v), sizeof(a)) 21 #define SORT(a) sort((a).begin(), (a).end()) 22 #define REV(a) reverse((a).begin(), (a).end()) 23 #define READ(a, n) {REP(i, n) cin>>(a)[i];} 24 #define REP(i, n) for(int i = 0; i < (n); i++) 25 #define VREP(i, n, base) for(int i = (n); i >= (base); i--) 26 #define Rep(i, base, n) for(int i = (base); i < (n); i++) 27 #define REPS(s, i) for(int i = 0; (s)[i]; i++) 28 #define pf(x) ((x)*(x)) 29 #define mod(n) ((n)) 30 #define Log(a, b) (log((double)b)/log((double)a)) 31 #define Srand() srand((int)time(0)) 32 #define random(number) (rand()%number) 33 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a) 34 35 using namespace std; 36 typedef long long LL; 37 typedef unsigned long long ULL; 38 typedef vector<int> VI; 39 typedef pair<int,int> PII; 40 typedef vector<PII> VII; 41 typedef vector<PII, int> VIII; 42 typedef VI:: iterator IT; 43 typedef map<string, int> Mps; 44 typedef map<int, int> Mpi; 45 typedef map<int, PII> Mpii; 46 typedef map<PII, int> Mpiii; 47 48 const int maxn = 300000 + 100; 49 const int L = 100003; 50 51 LL b[maxn]; 52 53 int n; 54 int a[maxn]; 55 LL ans; 56 struct SegTree { 57 LL h[maxn<<2]; 58 void build(int l, int r, int rt) { 59 if(l == r) { 60 h[rt] = 0; 61 return; 62 } 63 int m = (l+r)>>1; 64 build(lson); 65 build(rson); 66 } 67 void PushUp(int l, int r, int rt) { 68 int m = (l+r)>>1; 69 int ll = r-m; 70 h[rt] = h[rt<<1]*b[ll]+h[rt<<1|1]; 71 } 72 void update(int l, int r, int rt, int pos) { 73 if(pos == l && pos == r) { 74 h[rt] = b[1]; 75 return; 76 } 77 int m = (l+r)>>1; 78 if(pos <= m) 79 update(lson, pos); 80 else update(rson, pos); 81 PushUp(l, r, rt); 82 } 83 void query(int L, int R, int l, int r, int rt) { 84 if(L > R) 85 return; 86 if(L <= l && R >= r) { 87 ans = ans*b[r-l+1]+h[rt]; 88 return; 89 } 90 int m = (l+r)>>1; 91 if(L <= m) 92 query(L, R, lson); 93 if(R > m) 94 query(L, R, rson); 95 } 96 } t1, t2; 97 int main() { 98 99 scanf("%d", &n);100 b[0] = 1;101 Rep(i, 1, n+1) {102 scanf("%d", a+i);103 b[i] = b[i-1]*L;104 }105 t1.build(1, n, 1);106 t2.build(1, n, 1);107 Rep(i, 1, n+1) {108 int v = a[i];109 int l = min(v-1, n-v);110 ans = 0;111 t1.query(v-l, v-1, 1, n, 1);112 LL tmp = ans;113 ans = 0;114 t2.query(n-v-l+1, n-v, 1, n, 1);115 if(tmp != ans) {116 puts("YES");117 return 0;118 }119 t1.update(1, n, 1, v);120 t2.update(1, n, 1, n-v+1);121 }122 puts("NO");123 return 0;124 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。