A: 容易发现这要求所有子集中元素的最高位 1 的位置相同, 并且满足这个条件也是一定合法的. 统计一下即可.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- #define N 1010
- int n,cnt[40];
- int main()
- {
- freopen("subset.in","r",stdin);
- freopen("subset.out","w",stdout);
- while (scanf("%d",&n)>0)
- {
- memset(cnt,0,sizeof(cnt));
- for (int i=1;i<=n;i++)
- {
- int x=read();
- for (int j=30;~j;j--)
- if (x&(1<<j)) {cnt[j]++;break;}
- }
- for (int i=1;i<31;i++) cnt[0]=max(cnt[0],cnt[i]);
- printf("%d\n",cnt[0]);
- }
- return 0;
- }
- View Code
B: 考虑暴力 dp, 令 f[i] 为到达第 i 个咖啡站所花费的最短时间, 枚举上次买咖啡的地点转移. 可以发现这里转移分三种情况: 咖啡未冷却 (事实上这一种似乎没有必要转移); 咖啡已冷却而未喝完; 咖啡未喝完. 每种转移都是一段连续的区间, 可以二分找到分界点线段树暴力查询. 进一步发现每次分界点单调递增, 只需要维护两个指针即可. 这样就可以改为用单调队列优化了, 然而感觉很容易写挂还是搞了一棵线段树, 卡进 0.5s 感觉非常稳.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define N 500010
- #define ll long long
- #define inf 1000000000000
- ll read()
- {
- ll x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- ll l,d[N];
- double f[N],mn[N],ans,tree[N<<2],c[N],e[N],u,v;
- int n,a,b,t,r,L[N<<2],R[N<<2],Q[N];
- double calc(ll x)
- {
- if (x<=t*a) return (double)x/a;
- if (x<=t*a+r*b) return (double)(x-t*a)/b+t;
- return (double)(x-r*b)/a+r;
- }
- void build(int k,int l,int r)
- {
- L[k]=l,R[k]=r;tree[k]=inf;
- if (l==r) return;
- int mid=l+r>>1;
- build(k<<1,l,mid);
- build(k<<1|1,mid+1,r);
- }
- double query(int k,int l,int r)
- {
- if (l>r) return inf;
- if (L[k]==l&&R[k]==r) return tree[k];
- int mid=L[k]+R[k]>>1;
- if (r<=mid) return query(k<<1,l,r);
- else if (l>mid) return query(k<<1|1,l,r);
- else return min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
- }
- void ins(int k,int p,double x)
- {
- if (L[k]==R[k]) {tree[k]=x;return;}
- int mid=L[k]+R[k]>>1;
- if (p<=mid) ins(k<<1,p,x);
- else ins(k<<1|1,p,x);
- tree[k]=min(tree[k<<1],tree[k<<1|1]);
- }
- int main()
- {
- freopen("walk.in","r",stdin);
- freopen("walk.out","w",stdout);
- cin>>l>>a>>b>>t>>r;
- n=read();
- for (int i=1;i<=n;i++) d[i]=read(),c[i]=(double)d[i]/a,e[i]=(double)d[i]/b;
- mn[0]=inf;ans=(double)l/a;if (n==0) {printf("%.7lf",ans);return 0;}
- build(1,1,n);
- int p=1,q=1,head=0,tail=0;
- double u=t*(1-(double)a/b),v=r*(1-(double)b/a);
- for (int i=1;i<=n;i++)
- {
- f[i]=c[i];
- while (d[p]<d[i]-t*a) p++;
- while (d[q]<d[i]-t*a-r*b) q++;
- while (head<=tail&&Q[head]<p) head++;
- f[i]=min(f[i],f[Q[head]]-c[Q[head]]+c[i]);
- f[i]=min(f[i],query(1,q,p-1)+e[i]+u);
- f[i]=min(f[i],mn[q-1]+c[i]+v);
- mn[i]=min(mn[i-1],f[i]-c[i]);
- while (head<=tail&&f[i]-c[i]<=f[Q[tail]]-c[Q[tail]]) tail--;
- Q[++tail]=i;
- ins(1,i,f[i]-e[i]);
- ans=min(ans,f[i]+calc(l-d[i]));
- }
- printf("%.7lf",ans);
- return 0;
- }
- View Code
C: 每次相邻交换可以且最多减少一个逆序对. 算出逆序对个数剩下的怎么搞都行了.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- #define N 50010
- #define ll long long
- int n,a[N],tree[N];
- ll m,B;
- int query(int k){int s=0;while (k) s+=tree[k],k-=k&-k;return s;}
- void ins(int k){while (k<=n) tree[k]++,k+=k&-k;}
- int main()
- {
- freopen("game.in","r",stdin);
- freopen("game.out","w",stdout);
- n=read();cin>>B;
- for (int i=1;i<=n;i++)
- {
- a[i]=read();
- m+=i-query(a[i])-1;
- ins(a[i]);
- }
- if (B>m) cout<<m*(m+1)/2;
- else cout<<B*(B+1)/2+(m-B)*B;
- return 0;
- }
- View Code
- result:300 rank1
来源: http://www.bubuko.com/infodetail-2794259.html