CF 191 div.2 解题报告

A. Flipping Game

题目意思：

给N个数值为0和1的数，要求更改一个区间的所有数（0变1,1变0），使得最后的1最多。输出最多的1的个数。

解题思路：

暴力。

先预处理下，从第一个到第i个中1的个数，直接枚举更改的区间，计算即可。

代码：

[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
#define ll __int64
using namespace std;

int save[120];
int dp[120];

int main()
{
   int n;

   while(scanf("%d",&n)!=EOF)
   {
      dp[0]=0;
      for(int i=1;i<=n;i++)
      {
         scanf("%d",&save[i]);
         dp[i]=dp[i-1]+save[i]; //dp[i]表示1-i之间1的个数
      }
      int ans=0;
      for(int i=1;i<=n;i++)
         for(int j=i;j<=n;j++)
         {
            int t=dp[j]-dp[i-1]; //i-j之间1的个数

            t=j-i+1-t; //i-j之间0的个数
            ans=max(ans,dp[i-1]+t+dp[n]-dp[j]); //整个区间1的个数
         }
      printf("%d\n",ans);
   }
   return 0;
}

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
#define ll __int64
using namespace std;

int save[120];
int dp[120];

int main()
{
int n;

   while(scanf("%d",&n)!=EOF)
   {
      dp[0]=0;
      for(int i=1;i<=n;i++)
      {
         scanf("%d",&save[i]);
         dp[i]=dp[i-1]+save[i]; //dp[i]表示1-i之间1的个数
      }
      int ans=0;
      for(int i=1;i<=n;i++)
         for(int j=i;j<=n;j++)
         {
            int t=dp[j]-dp[i-1]; //i-j之间1的个数

            t=j-i+1-t; //i-j之间0的个数
            ans=max(ans,dp[i-1]+t+dp[n]-dp[j]); //整个区间1的个数
         }
      printf("%d\n",ans);
   }
   return 0;
}

B. Hungry Sequence

题目意思：

构造一个数列，数列为单调递增，且任意两个不能相互整除。个数至多有100000（10^5)个，每个元素不超过10000000(10^7).

解题思路：

构造。

由于只要求任意两个不相互整除即可，所以直接构造10^6+i (i~1-10^5）即可。当然也可以用素数筛选法，筛选出素数。

代码：

int save[110000];

int main()
{
int n;

   while(scanf("%d",&n)!=EOF)
   {
      for(int i=1;i<=n;i++)
         printf("%d ",1000000+i);
      putchar('\n');
   }

return 0;
}

C. Magic Five

题目意思：

给你一个数字串，可以连接k次。现在可以删除任意个数字（不能全部删），使得得到的数能够被5整除。求出不同删除的种数。

解题思路：

快速幂+求逆元

先考虑一个串，当第i个位置含有0或者5的时候，把他作为最后一个，则前面可删可不删共有2^i种。

当有k个串时，容易证明他们构成等比数列。因为10^9+7为质数，求逆元的时候直接分母的m-2次方即可。

代码：

补充：软件开发 , C++ ,