首页 > 代码库 > MemSQL Start[c]UP 2.0 - Round 2
MemSQL Start[c]UP 2.0 - Round 2
反正晚上睡不着，熬到1点开始做比赛，6个题目只做了2个题目，而且手速还比较慢，待提升空间还很大呢。
A题：给定两个0，1串(len<=100000), 但是不是普通的二进制串，而是q进制串，q = (√5 + 1)/2,比较这两个串的大小。
分析：q的长度很大，即使用大数似乎也不怎么合理，其实我写了半天大数，用最大长度数据测试发现根本出不了结果，也许我写的太挫了，也学时间就耗在上面了。
最终只能另想方法，而且题目中也说明了q^2 = q+1,所以很容易想到利用这个来做这个题， 观察到对于一个串中连续2个1，可以转化为高位的1个1，而且大小不变。这个题目比较大小的难点在于，会存在100 和011相等的情况，也就是不能通过一步步比较最高位来判断大小，低位也会影响。所以关键在于如何消除这种影响，我想到的方法就是从低位开始将连续2个1消去，变成高位1，如00110变成01000就好了，但是有一个问题就是遇到这种情况，001110，不止2个1连着，这样如果将最低2个1消除，会使得高位有2个1,001(2)000,这事就应该将连续一段最后两个1消除。这样做了一次之后还不够，需要反过来在做一次，比如这种情况，01111100，第一遍之后变成10011100，反过来遇到连续2个1，则变成高位，第二遍变成10100100，至于为什么这样做，因为第一遍之后会给后面的连续的1空出至少2个空间，这样第二遍的时候就不会有高位2个1的情况。
具体实现用到了bitset，只是因为最近学到了它，想熟练一下只用。
代码：
1 //Template updates date: 20140718 2 #include <bits/stdc++.h> 3 #define in freopen("solve_in.txt", "r", stdin); 4 using namespace std; 5 6 const int maxn = 100000 + 100; 7 bitset<maxn> a, b; 8 void solve(bitset<maxn> &x) { 9 for(int i = 0; i < maxn - 10; i++) {10 if(x[i] && x[i+1] && !x[i+2]) {11 x[i] = x[i+1] =0;12 x[i+2] = 1;13 i++;14 }15 }16 for(int i = maxn-11; i >= 0; i--) {17 if(x[i] && x[i+1]) {18 x[i+2] = 1;19 x[i] = x[i+1] = 0;20 }21 }22 }23 int main() {24 25 cin>>a>>b;26 solve(a);27 solve(b);28 for(int i = maxn-11; i >= 0; i--){29 if(a[i] > b[i]){30 puts(">");31 return 0;32 }33 else if(a[i] < b[i]){34 puts("<");35 return 0;36 }37 }38 puts("=");39 return 0;40 }
B题：有2个服务器，每个服务器上分别存储则会2个表，分别有m，n行，其中每个服务器会有很多分区，第一个服务器上第i个分区存储着ai行，第二个服务器第i个分区存储着bi行。
每次操作可以将任何分区上的行复制到其他任何分区，且花费为复制过去的行的数目。求最少的花费，使得对于第1个服务器上表的每行和第2个服务器上的表每个行都至少同时出现在一个分区上。
分析：
先对a[i], b[i]排序，suma[i]表示第一个服务器上前i个分区的行之和，sumb[i]类似。
问题可以这样考虑，第一个服务器上行最终状态是分成了x堆，第二个服务器上行移动到这些堆里面，这里花费为x*sumb[n],第一个服务器的花费应当是，a[i]中最大的x个作为不动分区，其他分区移动到这x个堆上面，花费为suma[x-1],枚举x，去最小值。
同理，可对第二个服务器作为x个堆算出最优值。
代码：
1 //Template updates date: 20140718 2 #include <bits/stdc++.h> 3 4 #define in freopen("solve_in.txt", "r", stdin); 5 using namespace std; 6 const int maxn = 100000 + 100; 7 double a[maxn], b[maxn], sum1[maxn], sum2[maxn]; 8 9 int main() {10 11 int n, m;12 cin>>m>>n;13 double ans = 1e25;14 for(int i = 1; i <= m; i++) {15 scanf("%lf", &a[i]);16 sum1[i] = sum1[i-1]+a[i];17 }18 for(int i = 1; i <= n; i++) {19 scanf("%lf", b+i);20 sum2[i] = sum2[i-1]+b[i];21 }22 sort(a+1, a+m+1);23 sort(b+1, b+n+1);24 for(int i = 1; i <= m; i++) {25 sum1[i] = sum1[i-1]+a[i];26 }27 for(int i = 1; i <= n; i++) {28 sum2[i] = sum2[i-1]+b[i];29 }30 for(int i = 1; i <= m; i++) {31 double tmp = sum2[n]*i+sum1[m-i];32 ans = min(ans, tmp);33 }34 for(int i = 1; i <= n; i++) {35 double tmp = sum1[m]*i+sum2[n-i];36 ans = min(ans, tmp);37 }38 printf("%.0f\n", ans);39 return 0;40 }
C题：有n支选票，投给ai，如果要这个人把票投给自己，那么需要花费bi，自己的标号为0。求最少的花费，使得自己选票比选票数目最多的那个人还要多。
分析：研究了半天别人代码，发现大抵方法是这样的：首先统计每个人得到的票数，及花费。然后将每个人票花费从小到大排序，统计出每个人的票数排序。
然后就是枚举我需要得到的票数i了，每次从票数比我多的人中减去一票，如果没有达到i，那么才弄个剩下的票数中选出花费最小的一些票。
更新剩下的票数，并选出最小的一些个时用到了树状数组，看了@JayYe的代码，自己仿写了一遍，我不会这一题啊。自己看了还不是很理解~~GG
另外， 好像还可以用三分？
树状数组实现代码：
值得学习的是， 里面查询最小k个的花费时的函数，二进制位从高到低枚举，每次cnt + num[res] < k ,则说明该高位应该加进去。
1 #include <bits/stdc++.h> 2 #define in freopen("solve_in.txt", "r", stdin); 3 #define lson rt<<1, l, m 4 #define rson rt<<1|1, m+1, r 5 #define lowbit(x) ((x)&(-(x))) 6 using namespace std; 7 const int maxn = 100000+10; 8 const int maxm = 10000+10; 9 10 map<int, multiset<int> > mps; 11 typedef map<int, multiset<int> > :: iterator it; 12 13 int n; 14 int x[maxn], y[maxn], cost[maxn], pos[maxm], val[maxm], num[maxm]; 15 int sz[maxn], r[maxn]; 16 int cnt, tot; 17 bool cmp(int a, int b) { 18 return sz[a] > sz[b]; 19 } 20 void update(int x, int v) { 21 int tmp = cost[x]; 22 while(x < maxm) { 23 num[x] += v; 24 val[x] += v*tmp; 25 x += lowbit(x); 26 } 27 } 28 int query1(int x) { 29 int res = 0; 30 while(x > 0) { 31 res += num[x]; 32 x -= lowbit(x); 33 } 34 return res; 35 } 36 int query2(int x) { 37 int res = 0; 38 while(x > 0) { 39 res += val[x]; 40 x -= lowbit(x); 41 } 42 return res; 43 } 44 int findup(int x) { 45 int res = 0; 46 int tmp = 0; 47 for(int i = 15; i >= 0; i--) { 48 res += (1<<i); 49 if(res >= tot || tmp + num[res] >= x) 50 res -= (1<<i); 51 else tmp += num[res]; 52 } 53 return res + 1; 54 } 55 #define bug puts(">>>>>>>>>>>><<<<<"); 56 int main() { 57 58 cin>>n; 59 for(int i = 0; i < n; i++) { 60 scanf("%d%d", x+i, y+i); 61 if(x[i]) 62 mps[x[i]].insert(y[i]); 63 } 64 for(int i = 0; i < n; i++) { 65 cost[++tot] = y[i]; 66 } 67 sort(cost+1, cost+tot+1); 68 tot = unique(cost+1, cost+tot+1)-cost; 69 for(int i = 1; i < tot; i++) { 70 pos[cost[i]] = i; 71 } 72 for(int i = 0; i < n; i++) { 73 update(pos[y[i]], 1); 74 } 75 for(it s = mps.begin(); s != mps.end(); s++) { 76 r[cnt++] = s->first; 77 sz[s->first] = (s->second).size(); 78 } 79 sort(r, r+cnt, cmp); 80 int j = 0; 81 int nn = 0, ans = 0x7f0f0f0f, ccost = 0; 82 for(int i = n; i >= 1; i--) { 83 while(j < cnt && sz[r[j]] >= i) j++; 84 for(int k = 0; k < j; k++) { 85 nn++; 86 int tmp = *mps[r[k]].begin(); 87 ccost += tmp; 88 mps[r[k]].erase(mps[r[k]].begin()); 89 update(pos[tmp], -1); 90 } 91 int cc = ccost; 92 int kk = max(i-nn, 0); 93 if(kk > 0) { 94 int p = findup(kk); 95 int t1 = query2(p-1); 96 cc += t1 + (kk-query1(p-1))*cost[p]; 97 } 98 ans = min(ans, cc); 99 }100 printf("%d\n", ans);101 return 0;102 }