2017.1.20 精英班试题讲解

阅读量：5102 次

发布时间：2019-06-13

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

选拔(select)

Time Limit:1000ms Memory Limit:128MB

题目描述

LYK对n个女生有好感。第i个女生的身高为ai。

LYK要在这些女生中选拔出一个女生来作为他的女朋友。选拔当然要排队咯。于是LYK想让这n个女生排成一行。

但LYK觉得对于两个身高相同的女生，谁排在前谁排在后其实让整个队列看上去并没有什么差别。

LYK想知道有多少个有差别的队列。

输入格式(select.in)

第一行一个数n表示女生个数。

第二行有n个数ai表示第i个女生的身高。

输出格式(select.out)

一个数表示答案。

输入样例

1 2 2

输出样例

数据范围

对于40%的数据n<=5,。

对于60%的数据n<=20。

对于80%的数据n<=1000。

对于100%的数据n<=10000，1<=ai<=n。

1 2 3 4 5 5!

1 1 3 4 5 5!/2!

1 1 1 3 4 5!/3!

1 1 1 1 3 5!/4!

1 1 2 2 3 5!/2!/2!

分子分母都分解质因子，删去相同的部分。

压位，一般压9位

2 100

30+30+30+10

2^30 2^30 2^30 2^10

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int X=1000000000;int f[50005],a[50005],i,n,A,v[50005],j,sum,k;long long ans[50005];int main(){    freopen("select.in","r",stdin);    freopen("select.out","w",stdout);    scanf("%d",&n);    for (i=1; i<=n; i++)    {        scanf("%d",&A);        a[A]++;    }    for (i=1; i<=n; i++) f[i]++;    for (i=1; i<=n; i++)        for (j=1; j<=a[i]; j++) f[j]--;    for (i=2; i<=n; i++)    {        if (!v[i])        for (j=i+i; j<=n; j+=i)        {            v[j]=1; sum=0;            k=j; while (k%i==0) k/=i,sum++;            //cout<
           <<' '<
            
             <<' '<
             
              <
              
               =10) {ans[j+1]+=ans[j]/X; ans[j]%=X;} while (ans[ans[0]]>=X) {ans[0]++; ans[ans[0]]=ans[ans[0]-1]/X; ans[ans[0]-1]%=X;} } cout<
               
                =1; i--) { j=X/10; while (ans[i]

这场故梦里

数字(number)

Time Limit:2000ms Memory Limit:128MB

题目描述

LYK收到了n个数字作为新年礼物，第i个数字的值为ai。

除了这些数字，还有一个信封，上面写着：“如果你能从这n个数中选出k个数使得它们的和为奇数，那么我将会满足你一个愿望！”

LYK觉得这不可能，此处必有玄机，于是它想在满足信封里的要求的情况下满足选出的数字的和最大。LYK想知道最大是多少。

当然不止这一年LYK收到了礼物，以后的每一年都会有这样的一个礼物，具体的，总共有m年。神奇的是这些数字并没有发生变化，而k发生了变化，LYK想知道所有年的答案是多少。

可能会存在写信人在骗它，也就是说不存在一个可行的方案，此时输出-1就可以了。

输入格式(number.in)

第一行一个数n表示LYK收到的数字个数。

第二行n个数ai表示每个数字。

第三行一个数m。

第四行m个数表示每一年的k值。

输出格式(number.out)

m行，每行输出一个答案。

输入样例

1 2 2

1 2 3

输出样例

数据范围

对于30%的数据n,m<=100。

对于60%的数据n,m<=1000。

对于另外10%的数据所有ai均为奇数。

对于再另外10%的数据所有ai均为偶数。

对于90%的数据n,m<=100000。

对于100%的数据n,m<=1000000，1<=ai<=n+2。

Note:

想拿满分的同学建议使用读入优化。

以下是读入优化模板：

void read(int &A)

{

char r; A=0;

for (r=getchar(); r<'0' || r>'9'; r=getchar());

for (;r>='0' && r<='9'; r=getchar()) A=A*10+r-'0';

}

特判：

全是偶数，都不行。

全是奇数，k是偶数，都不行；k是奇数，输出最大奇数和。

贪心：

从大到小排序，找尽可能靠前的，1……k和为奇数则为答案，和为偶数则不符合条件，从前面删掉一个偶数，后面加一个奇数；或从前面删掉一个奇数，后面加一个偶数。

只能删一个加一个。

对两种情况进行讨论。

—————A—————|—————B—————

最大pos=1 界线=k 最小

找到A中距离界线最近的偶数，与B中距离界线最近的奇数交换，计算一个答案

找到A中距离界线最近的奇数，与B中距离界线最近的偶数交换，计算另一个答案

输出最大的值

f[i]表示1~i中最靠右的偶数

if (a[i]%2==0) f[i]=a[i]; else

f[i]=(1~i-1中最靠右的偶数)f[i-1]

f[i]表示1~i中最靠右的奇数

if (a[i]%2==1) f[i]=a[i]; else

f[i]=(1~i-1中最靠右的奇数)f[i-1]

g[i]表示i~n中最靠左的偶数

if (a[i]%2==0) g[i]=a[i]; else

g[i]=(i+1~n中最靠左的偶数)g[i+1]

g[i]表示i~n中最靠左的奇数

if (a[i]%2==1) g[i]=a[i]; else

g[i]=(i+1~n中最靠左的奇数)g[i+1]

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=1000005;int a[N],F0[N],i,n,F1[N],F2[N],F3[N],m,A;long long ans[N],sum;int cmp(int i,int j) {
    return i>j;}void read(int &A){    char r; A=0;    for (r=getchar(); r<'0' || r>'9'; r=getchar());    for (;r>='0' && r<='9'; r=getchar()) A=A*10+r-'0';}int main(){   // read(n);// cout<
           
            <
            
             =1; i--) { if (a[i]%2==0) F2[i]=i; else F2[i]=F2[i+1]; if (a[i]%2==1) F3[i]=i; else F3[i]=F3[i+1]; } for (i=1; i<=n; i++) { sum+=a[i]; ans[i]=-1; if (sum%2==1) ans[i]=sum; else { if (F0[i] && F3[i+1]) ans[i]=max(ans[i],sum-a[F0[i]]+a[F3[i+1]]); if (F1[i] && F2[i+1]) ans[i]=max(ans[i],sum-a[F1[i]]+a[F2[i+1]]); } } scanf("%d",&m); while (m--) { scanf("%d",&A); printf("%I64d\n",ans[A]); } return 0;}

孤桨声远荡

测试(quiz)

Time Limit:1000ms Memory Limit:128MB

题目描述

随着WC的到来，LYK每天都在学习着新的知识。俗话说，比赛成绩=实力*经验。LYK相信它已经拥有了足够强的实力获得WC金牌。只要积累充足的经验，就能够获得强大的精神能量AK今年的WC！

于是LYK找来了n道题目想给自己做一个测试，对于第i道题目有ai分。LYK非常强大，能轻易地做出所有题目，但它觉得这样十分没意思。于是它给自己出了一道题目。

假如存在一个虚拟对手LYK2，对于每道题目它有50%的几率能够做对，做对一道题目能够获得其分数，做不对则得到0分。

LYK想知道，至少获得多少分数，使得至少有p的概率分数不低于LYK2。

输入格式(quiz.in)

第一行两个数n,p。

接下来一行n个数表示ai。

输出格式(quiz.out)

一个数表示答案。

输入样例

2 0.6

1 2

输出样例

数据范围

对于20%的数据n<=5，ai<=1000。

对于40%的数据n<=30，ai<=1000。

对于60%的数据n<=60，ai<=1000。

对于另外10%的数据n<=25，ai<=10^9。

对于再另外10%的数据n<=35，ai<=10^9。

对于再再另外20%的数据p为整数，n<=60，ai<=10^9。

对于100%的数据0<=p<=1，p小数点后至多两位，2<=n，ai>=1 。

分数至少为2^n*p，上取整 = k，对方有2^n种分数

->在2^n找第k小 n<=35 与two point 的做法类似

拿满分要用动规 dp[i]表示分数为i的方案总数

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N=(1<<20)+5;long long c[N],b[N],F,l,r,mid,sum,dp[100005];int cntc,cntb,n,i,a[105],j;double Q,p;const double eps=1e-7;void dfs(int x,long long y){    if (x==mid+1) {c[++cntc]=y; return;}    dfs(x+1,y);    dfs(x+1,y+a[x]);}void dfs2(int x,long long y){    if (x==n+1) {b[++cntb]=y; return;}    dfs2(x+1,y);    dfs2(x+1,y+a[x]);}int cmp(long long a,long long b) {
    return a
           
            x) {j=i-1; break;} for (int i=1; i<=cntb; i++) { ans+=j; while (j && b[i+1]+c[j]>x) j--; } return ans;}int main(){ freopen("quiz.in","r",stdin); freopen("quiz.out","w",stdout); scanf("%d%lf",&n,&p); for (i=1; i<=n; i++) scanf("%d",&a[i]); for (i=1; i<=n; i++) sum+=a[i]; if (p
            
             1-eps) {cout<
             
              <
              
               =a[i]; j--) dp[j]+=dp[j-a[i]]; for (i=1; i<=sum; i++) dp[i]+=dp[i-1]; for (i=0; i<=sum; i++) if (dp[i]>=F) {cout<
               <