嗯，还是写一篇博客比较好！

还是写一篇博客比较好，以后可以拉给学弟学妹做还省得写题解了（哈哈哈）。

总共9道题，本菜还有三道不会，没有什么新的知识点，但就是不会，看题解也是懵逼。现场做了3个，惭愧。A题签到，居然还WA了一发抢了一血，罚时+20，后来的题貌似没有什么很水的签到了，，中间有几个题看过但没能很熟练的做出来，然后左跳右跳题，大概把所有的题都摸清题意了，没找到什么题有很好的思路。最后一个题看了半天没看懂，但扫遍了其他的题回来又咬这个题才推出了样例，就是求(n-1)! % n，没什么思路，手推了几组样例发现了规律交了一发结果OJ出问题了结果出不来，很久才出，一血。。中间有个拓排的题，很裸的模板题，但找模板找了很久。。一个搜索和一个动归的题没写出来，看题解秒懂(晕)。最不应该的是全场漏了一个很水题，图片加载不出来，看不懂题意所以没动。。。补题后熬夜写了这篇博客。

A - ytaaa FZU 2229

水题，样例三个0以为结束标志，结果第二个样例搞错了。。真是不该心急。。心理素质不行啊！代码略。

B - Calculus Midterm FZU 2177

题意：n个数（炸药）排成一列，可以给其分组，每组炸药的威力等于本组数的最大值减最小值再平方。一个动归题，写法有很多。。（竟然在网上找到了彪哥写的题解）。

思路：用d[i]表示前i个炸药的最大威力，结果就是d[n]。动态转移方程d[j]=max(d[j],d[i-1]+(ma-mi)^2);

const int N=1000+10;
int a[N],dp[N];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++)
            {
                int mi=min(a[i],a[j]);
                int ma=max(a[i],a[j]);
                dp[j]=max(dp[j],dp[i-1]+(ma-mi)*(ma-mi));
            }
        printf("%d\n",dp[n]);
    }
    return 0;
}

C - 非主流 FZU 1922

后来学长说也蛮水的。总结就是：比赛有自己的节奏，不用在意别人做哪题、做了几题。

题意：n只鸭子，每只鸭子有m种特征，具有这种特征为1，否则为0。接下来是一个n*m的0 1矩阵。，每只鸭子的另类度计算方法 sum=dist(ai,a1)+dist(ai,a2)+dist(ai,a3)+...+dist(ai,an)；如果其另类度大于等于给定的标准则答案加一。

思路：暴力肯定会超时的，结合样例明白题意后思路。。还是直接上代码吧。

int a[N][205],sum[205];
int main()
{
    int t,n,m,k;
    scanf("%d",&t);
    int t1=t;
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                if(a[i][j]) sum[j]++;
            }
         int ans=0;
         for(int i=1;i<=n;i++)
         {
             int p=0;
             for(int j=1;j<=m;j++)
             {
                 if(a[i][j]) p+=n-sum[j];
                 else p+=sum[j];
             }
             if(p>=k) ans++;
         }
         printf("Case %d: %d\n",t1-t,ans);
    }
    return 0;
}

D - 棋盘问题 POJ 1321

POJ上的提交记录是1月27日，大一寒假集训时候的题，全场就4个人做出来。我还想用二分匹配做这个题，可恨每次拉这个题都没有补。。

char w[15][15];
int n,k,ans,vis[15];
void dfs(int x,int sum)
{
    if(sum==k)
    {
        ans++;
        return ;
    }
    if(x>=n) return ;
    for(int i=0;i<n;i++)
    if(w[x][i]=='#'&&!vis[i])
    {
        vis[i]=1;
        dfs(x+1,sum+1);
        vis[i]=0;//这里特别需要注意。
    }
    dfs(x+1,sum);
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        if(n==-1&&k==-1) return 0;
        for(int i=0;i<n;i++)
            scanf("%s",w[i]);
        ans=0;
        memset(vis,0,sizeof(vis));
        dfs(0,0);
        printf("%d\n",ans);
    }  <span style="font-family: Arial, Helvetica, sans-serif;">return 0;  </span><span style="font-family: Arial, Helvetica, sans-serif;">}</span>

E - 确定比赛名次 HDU 1285

裸的拓扑排序，要求有多种可能的时候输出标号小的在前。

const int N=1000+10;
int w[N][N],ru[N];
void topsort(int map[N][N],int *ru,int n)
{
    int a[N],len=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)//正好实现了标号从小到大的功能；
        if(ru[j]==0)
        {
            a[len++]=j;
            ru[j]--;
            for(int k=1;k<=n;k++)
                if(map[j][k])
                ru[k]--;//与其相连的点入度减一； 
           break;//每次确定一个位置；
        }
      for(int i=0;i<len;i++)
      {
          printf("%d",a[i]);
          if(i!=len-1) printf(" ");
          else printf("\n");
      }
}
int main()
{
    int n,m,x,y;
    while(~scanf("%d%d",&n,&m))
    {
        memset(w,0,sizeof(w));
        memset(ru,0,sizeof(ru));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            if(!w[x][y])
            {
                w[x][y]=1;
                ru[y]++;
            }
        }
        topsort(w,ru,n);
    }
    return 0;
}

F - sequence2 HDU 5568 dp+大数

G - 子矩阵求和 HihoCoder 1286

H - Array Rearrangement HihoCoder 1330 我想说我推了很久样例还是没明白。。

I - Zball in Tina Town HDU 5391

某场BC的div.2 A题，被我暴力过了。。。求（n-1）! % n。很明显，特判一下n=4的情况，其他的素数输出n-1,否则0； 1.5s时限，没超时。

int judge(int x)
{
    for(int i=2; i<=sqrt(x); i++)
        if(x%i==0) return 0;
    return 1;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n==4)
        {
            printf("2\n");
            continue;
        }
        else
        {
            if(judge(n)) printf("%d\n",n-1);
            else printf("0\n");
        }
    }
    return 0;
}

接下来该巩固的巩固，该学的学。11月加油！

秒客网

嗯，还是写一篇博客比较好！

相关文章