Div2-A

题意:有m个拼图,每个拼图有f[i]块.从中选出n个,使得 (其中块数最大减块数最小的值) 最小.

思路:把f按从小到大的顺序排序,然后顺次尝试.

#include
      
       int s[55];int main(){    int N,M,i,j;    while (scanf("%d%d",&N,&M)!=EOF)    {        for (i=1;i<=M;i++) scanf("%d",&s[i]);        for (i=1;i<=M-1;i++)         for (j=i+1;j<=M;j++)            if (s[i]>s[j])            {                int tmp=s[i];                s[i]=s[j];                s[j]=tmp;            }        int Min=10000;        for (i=1;i+N-1<=M;i++)            if (s[i+N-1]-s[i]
      

Div2-B

题意:屏幕尺寸是a:b,视频尺寸是c:d.求出保持该比例的前提下屏幕最少空余多大.

思路:显然a和b中必有一个充满,若b充满,则有dx=b=>x=b/d.从而a方向占用cx=bc/d.总的占用率为bc/ad.类似地,当a充满是占用比例为ad/bc.

注意:若a:b=c:d时应输出0/1,而不是0/20之类的.

#include
      
       int gcd(int a,int b){    if (b==0) return a;    return gcd(b,a%b);}int main(){    int a,b,c,d,p,q;    scanf("%d%d%d%d",&a,&b,&c,&d);    p=a*d;    q=b*c;    if (p>q)    {        int tmp=p;        p=q;        q=tmp;    }    p=q-p;    if (p==0) printf("0/1\n");    else    {        int tmp=gcd(p,q);        while (tmp!=1)        {            p/=tmp;            q/=tmp;            tmp=gcd(p,q);        }        printf("%d/%d\n",p,q);    }    return 0;}
      

Div2-C/Div1-A

题意:有n个问题,答对一个得一分,每连答对k个得分double一次.若答对m个,求最小得分.

思路:显然尽量不要发生double,为此,构造这样一种struct:{连对k-1个,错一个}或{错一个,连对k-1个}.若不得不发生double,则让double发生的越早越好.由于发生double的次数可能非常多,达到1e9次,不能硬算.考虑到一开始得分为0,经过连续几次double(操作为 "+k)*2" )后得分变成如下:2k,6k,14k,30k,62k,126k,可以猜测第i次之后为(2^1+2^2+2^3+......+2^i)k=(2^(i+1)-2)k.使用数学归纳法可以轻易证明这个结论.

#include
      
       __int64 pow(__int64 n,__int64 M){    if (n==0) return 1;    if (n==1) return 2;    __int64 tmp=pow(n/2,M);    if (n&1) return ((tmp*tmp)*2)%M;    else return (tmp*tmp)%M;}int main(){    __int64 N,M,K;    scanf("%I64d%I64d%I64d",&N,&M,&K);    __int64 S1=M/(K-1),S2=N-M;    if (S1<=S2) printf("%I64d\n",M);    else    {        __int64 R=M-S2*(K-1),S;        __int64 OP=R/K;        S=((pow(OP+1,1000000009)-2)*K)%1000000009;        S=(S+M-OP*K)%1000000009;        if (S<0) S+=1000000009;        printf("%I64d\n",S);    }    return 0;}
      

Div2-D/Div1-B

题意:有n个村庄,其中m个被僵尸攻击.已知僵尸会攻击与它距离小于等于d的,求僵尸可能位于哪几个村庄能产生这种现象.

思路beta1(TLE):对于m个村庄,bfs距离小于等于d的点,求m个的交集.

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct node{    int nx,step;};vector
          
            G[100010];int s[100010],aff[100010];bool inq[100010];int N,M,D,T;void bfs(int u){    queue
           
             q; int i; while (!q.empty()) q.pop(); node S; S.nx=u; S.step=0; memset(inq,false,sizeof(inq)); q.push(S); inq[u]=true; while (!q.empty()) { S=q.front(); q.pop(); s[S.nx]++; if (S.step
           
          
         
        
       
      

思路beta2:求出每个点离被僵尸攻击的村庄的最远距离,若小于等于d则ans++,距离分为两部分,一部分向儿子方向找,记为distdown,另一部分向父亲方向找,记为distup.

#include
      
       #include
       
        #include
        
         #define MAX(X,Y) (X>Y ? X:Y)using namespace std;int N,M,D,T;vector
         
           G[100010];int distup[100010],distdown[100010],father[100010],dd[100010],ff[100010];bool aff[100010];void dfsd(int u){    int i,Max=-10000000,cur;    dd[u]=-10000000;    for (i=0;i
          
           Max)        {            dd[u]=Max;            Max=cur;            ff[u]=v;        }        else dd[u]=MAX(dd[u],cur);    }    distdown[u]=Max;}void dfsu(int u){    int i,Max=-10000000,f=father[u],cur;    /*for (i=0;i
           
            2 ? Max:2; } else Max=Max>distdown[v]+2 ? Max:distdown[v]+2; }*/ if (u==ff[f]) Max=dd[f]+1; else Max=distdown[f]+1; /*if (distup[f]==0) { if (aff[f]) Max=Max>1 ? Max:1; } else Max=Max>distup[f]+1? Max:distup[f]+1;*/ if (aff[f]) cur=MAX(distup[f]+1,1); else cur=distup[f]+1; Max=MAX(Max,cur); distup[u]=Max; for (i=0;i
           
          
         
        
       
      

Div2-E/Div1-C

题意:定义因子树:叶节点均为质数,其余节点的值为该节点所有儿子的乘积.要求构造一个节点数最小的因子树,包含给定的几个数字a[i].

思路:显然在a[i]之外的数字只有可能出现在根节点或叶节点上,从而通过枚举a的构造方式求出最小值.

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 1000010#define int64 long long#define For(i,x,y) for (i=x;i<=y;i++)using namespace std;struct ww {    int64 a;    int sum;} a[10];int i,j,k,n,m,an;int f[N],p[N],sum[N],s[100],ff[10],f1[10];int64 x,g[N];inline void prepare() {    int i,j,k,u;    For(i,2,N-1)     {        if (!f[i]) f[i]=p[++*p]=i;        for (j=1;j<=*p&&p[j]<=f[i]&&p[j]*i
          
           n)     {        an=min(an,y+(sum>1));         return;    }    y+=(a[x].sum>1)+a[x].sum-f1[x];    dfs(x+1,y,sum+1);    int i;    For(i,x+1,n)     {        if (a[i].a/g[i]%a[x].a==0)         {            f1[i]+=a[x].sum; g[i]*=a[x].a; dfs(x+1,y,sum); g[i]/=a[x].a;            f1[i]-=a[x].sum;        }    }}int main() {    scanf("%d",&n);    For(i,1,n) scanf("%I64d",&a[i].a);    prepare();    For(i,1,n)     {        for (j=1,x=a[i].a;j<=*p&&x>1;j++)        for (;x%p[j]==0;x/=p[j],a[i].sum++);        if (x>1) a[i].sum++; g[i]=1;    }    sort(a+1,a+n+1,cc1);    an=N; dfs(1,0,0);    printf("%d\n",an);    return 0;}