首页 > 代码库 > topcoder srm 681 div1 -3
topcoder srm 681 div1 -3
1、一个机器人有$m$个部分。有$n$台机器，第$i$个机器可以生产编号为$[a_{i},b_{i}]$区间的部分，最多可以生产$k_{i}$个部分。最多可以组装成多少个机器？
思路：二分答案。然后判断。将所有的机器按照$a_{i}$排序，$a_{i}$相同的按照$b_{i}$排序。用一个优先队列维护这些机器。这样对于第$i$个部分，拿出队列开始的机器来生产该部分；如果队列开头的机器生产的部分没用完，则将其左区间$a_{t}$设置为$a_{t}+1$然后重新塞到队列里。
#include <stdio.h>#include <string.h>#include <string>#include <iostream>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <stack>#include <assert.h>using namespace std;const int N=10000000;int n,m;int c[N],a[N],b[N];struct node{ int L,R,cnt; node(){} node(int _L,int _R,int _cnt):L(_L),R(_R),cnt(_cnt) {} int operator<(const node& A) const { if(L!=A.L) return L>A.L; return R>A.R; }};priority_queue<node> Q;int check(const int M){ if(!M) return 1; while(!Q.empty()) Q.pop(); for(int i=1;i<=n;++i) Q.push(node(a[i],b[i],c[i])); for(int i=1;i<=m;++i) { if(Q.empty()) return 0; int sum=0; while(sum<M) { if(Q.empty()) return 0; if(Q.top().L!=i) return 0; if(sum+Q.top().cnt<=M) { sum+=Q.top().cnt; Q.pop(); } else { node p=Q.top(); Q.pop(); p.cnt-=M-sum; ++p.L; if(p.L<=p.R) Q.push(p); break; } } while(!Q.empty()&&Q.top().L==i) { node p=Q.top(); Q.pop(); ++p.L; if(p.L<=p.R) Q.push(p); } } return 1;}class FleetFunding{public: int maxShips(int mm,vector<int> kk,vector<int> aa,vector<int> bb) { n=(int)kk.size(); m=mm; int sum=0; for(int i=1;i<=n;++i) { c[i]=kk[i-1]; a[i]=aa[i-1]; b[i]=bb[i-1]; sum+=c[i]; } int low=0,high=sum/m; int ans=0; while(low<=high) { int M=(low+high)>>1; if(check(M)) ans=max(ans,M),low=M+1; else high=M-1; } return ans; }};2、一个长度为$n$的数组$A$,$B_{i}=max(k|A_{i-k}<A_{i}$且$A_{i+k}<A_{i})$。返回$\sum_{i=0}^{n-1}B_{i}$。给定$0\leq x_{0},a,b < 2^{50}$。数组$A$的产生方式如下。这个题目要求内存大小是$O(1)$，即不能开数组存储$A$。
A[0] = x0for i = 1 to n-1: A[i] = ((A[i-1] XOR a) + b) AND ((2^50) - 1)
思路：首先由$A_{i}$得到$A_{i-1}$的方式为$A_{i-1}=((A_{i}+2^{50}-b)$^$a)$&$(2^{50}-1)$。然后就是一个数字一个数字暴力计算$B$值。总的累积复杂度是$O(n)$的。
#include <stdio.h>#include <string.h>#include <string>#include <iostream>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <stack>#include <assert.h>using namespace std;const int mod=1000000007;const long long M=(1ll<<50)-1;long long a,b;long long NextX(long long x){ return ((x^a)+b)&M;}long long PreX(long long x){ return ((x+M+1-b)^a)&M;}int cal(int id,long long x,int n){ int ll=id,rr=id; int ans=0; long long lx=x,rx=x; while(ll-1>=0&&rr+1<n) { lx=PreX(lx); rx=NextX(rx); if(lx<x&&x>rx) ++ans,--ll,++rr; else break; } return ans;}class LimitedMemorySeries2{public: int getSum(int n,long long x0,long long aa,long long bb) { a=aa; b=bb; int ans=0; long long t=x0; for(int i=0;i<n;++i) { ans+=cal(i,t,n); if(ans>=mod) ans-=mod; t=NextX(t); } return ans; }};
topcoder srm 681 div1 -3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。