【清北学堂2018-刷题冲刺】Contest 6

2022-12-29 09:33:10

Task 1：子集

【问题描述】

 若一个集合S中任意两个元素x和y，都满足x⊕y<min⁡(x, y) ，则称集合S是“好的”。其中⊕为按位异或运算符。现在给定一个大小为n的集合S，其中每个数字都是正整数，请求出S所有“好的”子集中，元素个数最多的集合大小。

【输入】

 输入文件含有多组数据

 每组数据第一行读入元素个数N。接下来一行，N个正整数ai描述集合中的元素。

【输出】

 对于每组测试数据，输出一行一个整数表示答案.

subset.in subset.out
3 2
1 2 3 2
2
1 1

【样例解释】

 第一组数据中，选择集合{2,3}为最佳方案。若选择{1,2,3}，由于1⊕2=3>min(1,2) ，该集合不是“好的”。

【数据范围】

  • $1 – 4 $ \(1 ≤ N ≤ 16\)

  • $5 – 10 $ \(1 ≤ N ≤ 1000\)

  • 对于100%的数据：\(1 ≤ ai ≤ 10^9\)。

 异或又名半加，可以理解为不进位加法。

 考虑三种形式：

  • 1^1=0
  • 0^0=0
  • 1^0=1

    ​

 只考虑最高位，若要使异或结果比两个数都小，最高位只能满足情况1。所以就可以直接按照二进制最高位数拆分，每个位数作为一个集合，求最大集合。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,arr[1010],bin[40],res[40];

inline int read(){

    int s=0;

    char ch=getchar();

    while('9'<ch||ch<'0'){

        ch=getchar();

    }

    while('0'<=ch&&ch<='9'){

        s=(s<<3)+(s<<1)+ch-'0';

        ch=getchar();

    }

    return s;

}

int main(){

    freopen("subset.in","r",stdin);

    freopen("subset.out","w",stdout);

    bin[0]=1;

    for(register int i=1;i<=30;++i){

        bin[i]=bin[i-1]<<1;

    }

    while(scanf("%d",&n)==1){

        memset(res,0,sizeof(res));

        for(register int i=1;i<=n;++i){

            arr[i]=read();

            int pos=upper_bound(bin,bin+31,arr[i])-bin;

            res[pos]++;

        }

        int ans=0;

        for(register int i=0;i<=30;++i){

            ans=max(ans,res[i]);

        }

        printf("%d\n",ans);

    }

    return 0;

}

Task 2：出行

【问题描述】

 小C要从A地赶往B地，A地和B地相距L米。在A去往B的路上，还有N个咖啡站，其中第i个咖啡站在距离A地xi 米的位置（0≤x1<x2<…<xN≤L ）。小C平时步行的速度为a米/秒，而当他喝咖啡时，步行速度会是b米/秒（a<b ）。

 每当小C到达一个咖啡站，小C可以选择购买一杯咖啡，购买咖啡所花费的时间可以忽略不计。刚买的咖啡由于太烫还不能立即饮用，所以小C会继续以a米/秒的速度前进。在买完咖啡t秒后，咖啡才变得可以饮用，此时小C便开始以b米/秒的速度前进。小C喝一杯咖啡需要r秒，即从开始喝咖啡r秒后，小C的前进速度又会变回a米/秒。当然小C到达咖啡站时，也可以选择不购买咖啡。

 另外，如果小C选择在一个咖啡站停下来购买咖啡，但此时手上还有一杯没有喝或者没喝完的咖啡，那么小C会毫不犹豫地扔掉手上之前购买的咖啡。

 请求出在最优决策下，小C从A地前往B地最少需要花费多少秒。

【输入】

 第一行，五个整数L,a,b,t,r，分别表示两地间距离，小C不喝咖啡及喝咖啡时的速度，咖啡变凉的时长，以及饮用一杯咖啡需要的时间。

 第二行，一个整数N，描述A地到B地之间咖啡站的数量。

 接下来一行，N个单调上升的整数，表示第i个咖啡站与A地的距离。

【输出】

 一行，表示答案，相对误差或绝对误差与标准答案相差不超过10^-6 即被认为正确。

walk.in walk.out
80 1 2 20 10 60
3
0 20 40

【样例解释】

 最优决策下，小C会选择在第一个和第三个咖啡站买咖啡，第一次买咖啡时，小C以1米/秒的速度前进20秒，此时咖啡不再烫嘴，再以2米/秒的速度前进10秒，此时恰好到达第三个咖啡站。可以计算，最优花费为2*(10+20)=60 秒。

【数据范围】

  • \(1 – 2\) \(0 ≤ N ≤ 20\)
  • \(3 – 6\) $ 0 ≤ N ≤ 1000$
  • \(7 – 10\) $ 0 ≤ N ≤ 5*10^5$
  • 对于100%的数据：保证\(1≤L≤10^{11} ，1≤a<b≤200 ，0≤t≤300 ，1≤r≤1200\)

 考虑路径为双色线段，前一半等待后一半加速。

 首先有一点可以确定：如果当前线段起点在某个线段加速点之前，从这个线段的转移一定不是最优。

 原因：前一个点选择而加速并未使用，直接转移一定不会最优。

 其他的情况分两类：

  • 当前的线段起点在某个线段加速点之后：部分加速
  • 当前线段起点在某个线段终点之后：完全加速，直接转移

    ​

 考虑直接转移：60pts

 因为我太弱了所以并没有摸索出来第一种情况怎么优化，只做了一个对第二种情况的单调队列加速。60pts->80pts

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 500010

#define lint long long

using namespace std;

lint n,l,sl,fa,wt,dr,head=1,tail=0,f[MAXN],que[MAXN];

bool vis[MAXN];

struct node{

    lint pos;

    lint fas;

    lint fin;

}nod[MAXN];

inline lint min(lint x,lint y){

    return x<y?x:y;

}

inline void update(lint k){

    while(head<=tail && que[tail]<=k){

        --tail;

    }que[++tail]=k;

}

int main(){

    freopen("walk.in","r",stdin);

    freopen("walk.out","w",stdout);

    scanf("%lld%lld%lld%lld%lld%lld",&l,&sl,&fa,&wt,&dr,&n);

    for(int i=1;i<=n;++i){

        scanf("%lld",&nod[i].pos);

        nod[i].fas=min(l,nod[i].pos+sl*wt);

        nod[i].fin=min(l,nod[i].fas+fa*dr);

    }

    nod[++n]=(node){l,l,l};

    for(register int i=1;i<=n;++i){

        f[i]=nod[i].fin-nod[i].fas;

        for(register int j=i;j>=1;--j){

            if(nod[i].pos<=nod[j].fas)continue;

            if(nod[i].pos>=nod[j].fin){

                if(vis[j])break;

                update(f[j]);

                f[i]=max(f[i],nod[i].fin-nod[i].fas+que[head]);

                vis[j]=true;

            }else{

                f[i]=max(f[i],f[j]-(nod[j].fin-nod[i].pos)+nod[i].fin-nod[i].fas);

            }

        }

    }

    double ans=(double)f[n]/(double)fa+(double)(l-f[n])/(double)sl;

    printf("%lf\n",ans);

}

 调了一上午的100pts：不咕了在下面

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 1000010

#define int long long

using namespace std;

struct node{

	int pos;

	double val;

}que[MAXN];

double f[MAXN];//f记录到达每一个咖啡站的花费时间

int l,n,a,b,t,r,x[MAXN];

//vis用于记录对于一个能完整喝完咖啡的选择，以前是否访问过

signed main(){

	freopen("walk7.in","r",stdin);

//	freopen("walk.out","w",stdout);

	memset(que,0,sizeof(que));

	cin>>l>>a>>b>>t>>r>>n;

	for(int i=1;i<=n;++i){

		scanf("%lld",&x[i]);

	}

	double minn=1e50;

	int head=1,tail=0,p1=1,p2=1,fst=0;

	x[++n]=l;

	for(int i=1;i<=n;++i){

		//在这个点以前的选择都已经被处理过

		while(x[i]-x[p1]>=t*a+r*b && p1<i){

			//是一个可以完整喝完的选择

			minn=min(minn,(double)f[p1]+(double)r-( (double)x[p1]+(double)(r*b))/((double)a));

			p1++;

			fst=1;

		}//更新可用最小值

		if(t*a<=x[i]-x[p2] && x[i]-x[p2]<t*a+r*b && p2<i){

			double ins=(double)f[p2]+(double)t-((double)(x[p2]+a*t))/(double)b;

			while(head<=tail && ins<=que[tail].val)tail--;

			que[++tail].val=ins;

			que[tail].pos=x[p2];

			p2++;

		}

		while(head<=tail && que[head].pos<=x[i]-t*a-r*b)head++;

		f[i]=f[i-1]+((double)(x[i]-x[i-1]))/(double)a;

		f[i]=min(f[i],minn+(double)x[i]/(double)a);

		if(head<=tail){

			f[i]=min(f[i],que[head].val+(double)x[i]/(double)b);

		}

	}

	printf("%.8lf",f[n]);

}

Task 3：游戏

【问题描述】

 有一个长度为n的排列，小C可以交换任意相邻元素任意多次，但第i 次交换需要付出i 的代价。小C认为逆序对是丑陋的，若在小C操作完的序列*有x 个逆序对，那么小C就会认为这个序列的丑陋度是B*x ，其中B 是给定的常数。小C希望你告诉他最佳的操作策略，使得最终的序列丑陋度和操作所付出的代价之和最小。

【输入】

 第一行，两个整数n ，B。

 接下来一行，n 个整数，描述初始排列。

【输出】

 一行，表示代价与丑陋度的最小和。

game.in game.out
3 2 3
3 1 2

【样例解释】

 若不操作，代价+丑陋度=0+4=4

 若交换1和3，序列变成{1 3 2}，代价+丑陋度=1+2=3

 若交换1和3，再交换2和3，序列变成{1 2 3}，代价+丑陋度=3+0=3

 容易验证其他策略下，代价和丑陋度之和都不会小于3

【数据范围】

  • \(1–2\) \(1 \leq N \leq 20\) \(1\leq N\leq20\)
  • \(3-6\) \(1 ≤ N \leq 5000\)
  • \(7 - 10\) \(1 ≤ N ≤ 5*10^4\)
  • 对于100%的数据：\(0 ≤ B ≤ 10^{15}\)

 逆序对水题，只要有逆序对就一定可以交换去掉，每次交换只能去掉一个。只需要求一下逆序对总数就可以了。B和n范围差距悬殊，为了避免高精度计算，可以先把换掉第n个逆序对的最大消耗和B比较一下，再确认是部分换还是全换。

 虽然水但有一点还是很重要的，就是要熟练归并和树状数组求逆序对的方法。

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 50010

#define lowbit(x) x&-x

#define lint long long

using namespace std;

lint n,k,arr[MAXN],tree[MAXN];

inline void add(int pos,int val){

    while(pos<=n){

        tree[pos]+=val;

        pos+=lowbit(pos);

    }

}

inline lint getsum(lint pos){

    lint res=0;

    while(pos){

        res+=tree[pos];

        pos-=lowbit(pos);

    }

    return res;

}

inline lint get_rev(){

    lint res=0;

    for(register int i=n;i>=1;--i){

        res+=getsum(arr[i]);

        add(arr[i],1);

    }

    return res;

}

int main(){

    freopen("game.in","r",stdin);

    freopen("game.out","w",stdout);

    scanf("%lld%lld",&n,&k);

    for(register lint i=1;i<=n;++i){

        scanf("%lld",&arr[i]);

    }

    lint tot=get_rev(),ans=tot*k;

//  printf("tot=%lld\n",tot);

    for(register lint i=1;i<=tot;++i){

        if(i>=k)break;

        ans+=i-k;

    }

    printf("%lld\n",ans);

    return 0;

}
上一篇：Linux下NC反弹shell命令


下一篇：JS 获取某个容器控件中id包含制定字符串的控件id列表