[20180814]校内模拟赛

阅读量：5086 次

发布时间：2019-06-13

本文共 3960 字，大约阅读时间需要 13 分钟。

T1 覆盖(cover)

问题描述

二维平面上有n个点，第i个点为\((x_i,y_i)\)。你可以选出若干个点，选出的每个点可以覆盖以这个点为原点的

坐标系的四个象限之一内的点和这个象限边界上的点。求至少需要选出几个点才能覆盖所有点。

输入格式

多组数据，第一行一个正整数T。

每组数据第一行一个正整数n。

接下来n行，每行两个整数\(x_i,y_i\)。

输出格式

对于每组数组输出一行一个整数，表示答案。

样例

样例输入

145 0-5 00 50 -5

样例输出

Solution

如果恰好有点位于所有点的左下角(或右上角或右下角或左下角)，答案为1；

否则，答案为2；

#include
    
     #include
     
      #include
      
       #include
       
        inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 100005#define inf (1e9+5)int T,n,x[MN],y[MN],Xmax,Xmin,Ymax,Ymin;bool flag;int main(){    freopen("cover.in","r",stdin);    freopen("cover.out","w",stdout);    T=read();register int i;    while(T--){        n=read();        Xmax=Ymax=-inf;        Xmin=Ymin=inf;flag=0;        for(i=1;i<=n;i++){            x[i]=read();y[i]=read();            Xmax=std::max(Xmax,x[i]);            Xmin=std::min(Xmin,x[i]);            Ymax=std::max(Ymax,y[i]);            Ymin=std::min(Ymin,y[i]);        }        for(i=1;i<=n;i++){            if((x[i]==Xmax||x[i]==Xmin)&&(y[i]==Ymax||y[i]==Ymin)){                flag=1;break;            }        }        puts(flag==1?"1":"2");    }    return 0;}

T2 匹配(match)

问题描述

你有n个数字对\((a_i,b_i)\)和m个数字\(c_i\)，数字对i和数字j能匹配的条件是\(c_j\)≤\(a_i\)+\(b_i\)

匹配后会产生max(\(c_j\)-\(b_i\),0)的权值。一个数字对最多与一个数字匹配，一个数字最多与一个数字对匹配。

你需要在最大化匹配对数的情况下最小化权值和。

输入格式

第一行两个正整数n,m。

第二行n个正整数，表示\(a_i\)

第三行n个正整数，表示\(b_i\)

第四行m个正整数，表示\(c_i\)

输出格式

输出两个整数，分别表示最大匹配对数和最小的权值和。

样例

样例输入

5 52 5 3 6 26 2 1 3 26 8 7 8 6

样例输出

3 8

数据范围

对于 100%的数据，n,m ≤ 2*10^5 ，ai ,bi ,ci ≤ 10^9 。

Solution

考虑贪心，显然如果\(c_i < c_j\)，那么\(c_i\)就会比\(c_j\)更优。

所以如果我们知道最大匹配对数p的话，就只要取前p小的\(c_i\)进行匹配

预处理出每个\(c_i\)对应的可以匹配的区间，然后从小到大模拟一遍，即可得到最大匹配数

最后一步，依然是贪心，优先考虑\(c_i\)值较大的，把可取的所有b值中最大的匹配给它

可以证明这样是最优的。

要找最大值，开个priority_queue就行了

复杂度O(nlogn)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 200005int n,m,a[MN],b[MN],c[MN],id[MN],last[MN];bool cmp(const int&x,const int&y){    return a[x]+b[x]>a[y]+b[y];}std::priority_queue
         
           Q;long long ans=0;int main(){ freopen("match.in","r",stdin); freopen("match.out","w",stdout); n=read(),m=read(); register int i,j; for(i=1;i<=n;i++) a[i]=read(); for(i=1;i<=n;i++) b[i]=read(); for(i=1;i<=m;i++) c[i]=read(); for(i=1;i<=n;i++) id[i]=i; std::sort(c+1,c+m+1); std::sort(id+1,id+n+1,cmp); int len=std::min(n,m); for(i=len,j=0;i;i--){ while(a[id[j+1]]+b[id[j+1]]>=c[i]&&j+1<=n) j++; last[i]=j; } int pos=MN,num=0; for(i=1;i<=len;i++){ if(last[i]==0||pos==1) break; pos=std::min(pos-1,last[i]);num++; } len=num;num=1; printf("%d ",len); for(i=len;i;i--){ for(;num<=last[i];) Q.push(b[id[num++]]); ans+=std::max(c[i]-Q.top(),0);Q.pop(); } printf("%lld\n",ans); return 0;}

T3 裁剪(tailor)

问题描述

你有一个字符串A，但你不喜欢串A,你喜欢的是串B。

于是你想要删掉A中的若干个字符，使得B在A中的出现次数尽量多。在这里，B在A中的出现次数定义为最多能选出多少个A的不相交子串满足这些子串都等于B。

你需要对每个x求出从A中删去x个字符后B的最大出现次数。

输入格式

第一行一个小写字符串A。

第二行一个小写字符串B。

输出格式

一行∣A∣+1个整数，第i个表示x=i-1时的答案。∣A∣表示字符串A的长度。

样例

样例输入

axbaxxbab

样例输出

0 1 1 2 1 1 0 0

Solution

\(f_{i,j}\)表示前i个字符删了j个的答案，分情况转移:

删除第i个字符，且对答案没有影响：\(f_{i-1,j}\)—>\(f_{i,j+1}\)

保留第i个字符，但对答案没有影响：\(f_{i-1,j}\)—>\(f_{i,j}\)

对答案有影响：预处理第i个字符后至少删几个才能形成一个B串，得到\(t_i\)，那么

\[ f_{i,j}+1—>f_{i+len(b)+t_i,j+t_i} \]

#include
    
     #include
     
      #include
      
       #include
       
        #define MN 2005char a[MN],b[505];int la,lb;int f[MN][MN],t[MN];inline void rw(int &a,int b){if(a
        
         =0){            rw(f[i+1][j],f[i][j]);            rw(f[i+1][j+1],f[i][j]);            t[i+1]