学步园

烦躁，不搞了，直接写报告了。

第一题，水题，意思很好理解，细节需要注意，然后，然后就没有然后了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int n,k,a[100005],sum;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]<0&&k>0)
            {
                a[i]=-a[i];
                k--;
            }
        }
        sort(a,a+n);
        if(k%2==1)a[0]=-a[0];
        for(int i=0;i<n;i++)sum+=a[i];
        cout<<sum<<endl;
    }
    return 0;
}

第二题，买东西的问题，一开始思路其实对的，由于代码风格什么的原因，各种没a。

就是挑最小的购物方案，从大往小遍历一遍，每逢那么多个后面两个不及价格就好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
bool cmp(int a,int b){return a>b;}
int main()
{
    int m,q,mi,n,a[100005],v,sum;
    while(scanf("%d",&m)!=EOF)
    {
        mi=100005;
        for(int i=0;i<m;i++)
        {
            scanf("%d",&q);
            if(q<mi)mi=q;
        }
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n,cmp);
        v=0;
        sum=0;
        for(int i=0;i<n;i++)
        {
            if(v<0)
            {
                v++;
            }
            else if(v==mi)
            {
                v=-1;
            }
            else
            {
                sum+=a[i];
                v++;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

第三题，神dp。

设f[i][j][k]数组代表j个人总和为i，下一个坐不进的人是k的情况的多少。之后就判断可不可能，然后再排列组合一下。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
double f[55][55][55];//f[i][j][k],j people sum is i ,k the next
int n,a[55],p;
double  sum,c[55];
int main()
{
    c[0]=1;
    for(int i=1; i<=50; i++)c[i]=c[i-1]*i;
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0,sizeof(f));
        sum=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            f[0][0][i]=1;
        }
        scanf("%d",&p);
        if(sum<=p)
        {
            cout<<n<<endl;
            continue;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(j!=i)
                {
                    for(int g=n; g>=1; g--)
                    {
                        for(int k=p; k>=a[i]; k--)
                        {
                            f[k][g][j]+=f[k-a[i]][g-1][j];
                        }
                    }
                }
            }
        }
        sum=0;
        for(int i=1; i<=n; i++)
        {
            for(int g=1; g<=n; g++)
            {
                if(a[i]>p)a[i]=p+1;
                for(int j=p-a[i]+1; j<=p; j++)
                    sum+=f[j][g][i]*c[g]*c[n-g-1]*g;
            }
        }
        sum/=c[n];
        printf("%.9f\n",sum);
    }
    return 0;
}

第四题，看懂题就能过，略过。

下俩题不说了，搞不动了，。。。。。。。

第七题，水模拟，不解释了。

第八题，略有技巧，先从左往右遍历，遇r输出编号，再从右往左，遇l输出编号，ok了

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
    string s;
    int l;
    while(cin>>s)
    {
        l=s.length();
        for(int i=0;i<l;i++)
        {
            if(s[i]=='r')printf("%d\n",i+1);
        }
        for(int i=l-1;i>=0;i--)
        {
            if(s[i]=='l')printf("%d\n",i+1);
        }
    }
    return 0;
}

最后一题，也是神dp，好题啊，感觉和北航校赛的某题一样的。一开始按照最长升序列（LIS）的方法来，果断超时，不过LIS有二分的做法，这题不适用。网上看到神代码之后，顿悟，下面是神代码及我自己写的注释。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MX=100000;
int n,i,j,a[MX+10],r[MX+10],b,x,res=1;
int main() {
  for (i=2; i<=MX; i++) if (a[i]==0) for (j=i; j<=MX; j+=i) a[j]=i;//标记j的最大质数约数
  scanf("%d",&n);
  for (i=0; i<n; i++) {
    scanf("%d",&b);
    x=0;
    for ( j=b; j>1; j/=a[j]) x=max(x,r[a[j]]);//找到b的质约数所在最高阶
    for (j=b; j>1; j/=a[j]) r[a[j]]=max(r[a[j]],x+1);//更新这些约数所在阶
    res=max(res,x+1);//更新最大阶数
  }
  printf("%d\n",res);
  return 0;
}