A. Flipping Game
题目意思：
给N个数值为0和1的数，要求更改一个区间的所有数（0变1,1变0），使得最后的1最多。输出最多的1的个数。
解题思路：
暴力。
先预处理下，从第一个到第i个中1的个数，直接枚举更改的区间，计算即可。
代码：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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）即可。当然也可以用素数筛选法，筛选出素数。
代码：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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次方即可。
代码：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include