最近这两场好无奈啊。。。

今天这场最后30分钟敲1001，压力倍增，虽然思路比较明确，但是代码打起来不怎么容易。

但是还是好在25分钟左右debug结束。提交wa，再提交，依然WA.......最后5分钟，还是没有AC掉。

一开始以为是精度问题，后来才sb的发现原来数组开小了。

在压力环境下保证代码的效率和质量真不是一件容易的事情。不过数组开小了，真是不可原谅。

1001：Map

题目相当于几条链表。把链表排成几行。

然后枚举每一列的状态会被操作多少次。

然后把和累加起来，然后直接除以状态总数。

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include <map>
using namespace std;
#define LL long long
#define lcm(a,b) (a*b/gcd(a,b))
int su[1010][1100];
int a[10100];
int have[1010];
int pre[10100];
int next[11000];
vector<int>vec;
int maxlen;
int pan(int p,int t)
{
    int n=vec.size();
    for(int i=0;i<n;i++)
    {
        if(t&(1<<i))
        {
            if(su[i][p]==0)return 0;
        }
    }
    return 1;
}
double use(int p,int t)
{
    int n=vec.size();
    int s,x,y;
    x=have[p];
    y=0;
    s=0;
    for(int i=0;i<n;i++)
    {
        if(t&(1<<i))
        {
            y++;
            s+=a[su[i][p]];
        }
    }
    if(y>1)
    {
        return 1.0*y*s/x+s;
    }
    else return s;
}
void dos()
{
    int n=vec.size();
    int t=1<<n;
    t--;
    double ans=0;
    double pp=1.0;
    for(int i=0;i<n;i++)
    {
        pp*=1.0*(su[i][0]+1);
    }
    pp--;
    for(int i=1;i<=maxlen;i++)
    {
        for(int j=1;j<=t;j++)
        {
            if(pan(i,j)==0)continue;
            double sum=use(i,j);
            double ch=1.0;
            for(int k=0;k<n;k++)
            {
                if(j&(1<<k))
                {
                    ch*=1.0*(su[k][0]-i+1);
                }
                else
                {
                    ch*=1.0*min((su[k][0]+1),i);
                }
            }
            ans+=sum*ch;
        }
    }
    printf("%.3f\n",ans/pp);
}
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        memset(have,0,sizeof(have));
        memset(pre,0,sizeof(pre));
        memset(next,-1,sizeof(next));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }

        int u,v;
        while(m--)
        {
            scanf("%d%d",&u,&v);
            u++;
            v++;
            pre[v]=u;
            next[u]=v;
        }
        vec.clear();
        for(int i=1;i<=n;i++)
        {
            if(pre[i]==0)vec.push_back(i);
        }
        memset(su,0,sizeof(su));
        maxlen=0;
        for(int i=0;i<vec.size();i++)
        {
            int k=1;
            for(int j=vec[i];j!=-1;j=next[j])
            {
                su[i][k]=j;
                have[k]++;
                k++;
            }
            su[i][0]=k-1;
            maxlen=max(maxlen,k-1);
        }
        dos();
    }
    return 0;
}

从前往后扫，如果不满足不下降，就把后面的合并到前面去，如果还不满足，继续合并。

最后算出结果即可。

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define eps 1e-9
#define zero(x) (fabs(x)<eps?0:x)
#define maxn 110000
struct list
{
    int x;
    int y;
    double f;
    int pre;
}p[maxn];
int a[maxn];
double su(int x,int y)
{
    return (1.0*x)/(1.0*x+1.0*y);
}
void dos(int n)
{
    p[0].f=0.0;
    p[0].pre=-1;
    p[0].x=0;
    p[0].y=0;
    for(int i=1;i<=n;i++)
    {
        p[i].f=su(p[i].x,p[i].y);
     //   cout<<i<<" "<<p[i].x<<" "<<p[i].y<<" "<<p[i].f<<endl;
        if(zero(p[i].f-p[i-1].f)>=0)
        {
            p[i].pre=i-1;
            continue;
        }
        for(int j=i-1;j!=-1;j=p[j].pre)
        {
            p[i].x+=p[j].x;
            p[i].y+=p[j].y;
            p[i].pre=p[j].pre;
            p[i].f=su(p[i].x,p[i].y);
            if(zero(p[i].f-p[p[i].pre].f)>=0)break;
        }
    }
    double sum=0.0;
    for(int i=n;i!=-1;i=p[i].pre)
    {
        double ps=0;
        double f=p[i].f;
        ps+=f*f*1.0*p[i].y;
        f=1.0-f;
        ps+=f*f*1.0*p[i].x;
        sum+=ps;
    }
    printf("%.6f\n",sum);
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ls=0;
        int leap=1;
        for(int i=1;i<=n;i++)
        {
            if(ls==0)
            {
                if(a[i]==0)continue;
                else
                {
                    ls++;
                    p[ls].x=1;
                    p[ls].y=0;
                    continue;
                }
            }
            if(leap==a[i])
            {
               if(leap==0)p[ls].y++;
               else p[ls].x++;
            }
            else
            {
                leap=leap^1;
                if(leap==1)
                {
                    ls++;
                    p[ls].x=0;
                    p[ls].y=0;
                }
                i--;
            }
          //  cout<<ls<<" "<<p[ls].x<<" "<<p[ls].y<<endl;
        }
        if(p[ls].y==0)ls--;
     //   cout<<"__"<<ls<<endl;
        if(ls==0)
        {
            printf("%.6f\n",1.0*ls);
            continue;
        }
        dos(ls);
    }
    return 0;
}

很明显可以发现，我们交叉放苹果和肥料是最优的，一共两种放法。

直接模拟一下就好。

1007：Series 1

脱脱的最后的系数是一个杨辉三角。然后+，-交替。

不过是大数sad，要用到java。。。

悲伤

import java.util.Scanner;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger[] bit = new BigInteger[3300];
        BigInteger ans,temp,sn;
    
        int i,cas,n,j,k;
        cas = cin.nextInt();
        for(i = 1;i <= cas;i ++)
        {
            ans = BigInteger.ZERO;
            temp = BigInteger.ONE;
            n = cin.nextInt();
            sn = BigInteger.valueOf(n-1);
            for(j = 1;j <= n;j ++)
                bit[j] = cin.nextBigInteger();
            for(j = 0;j < n;j ++)
            {
                if(j%2 == 0)
                    ans = ans.add(temp.multiply(bit[n-j]));
                else 
                    ans = ans.subtract(temp.multiply(bit[n-j]));
                temp = temp.multiply(sn).divide(BigInteger.valueOf(j+1));
                sn = sn.subtract(BigInteger.ONE);
            }
            System.out.println(ans);
        }
    }
}

这个题目就不吐槽了。。。

很明显一开始看错题了。。。

就是一个水的模拟题，不用理会。。。。