A. Flipping Game
链接：http://codeforces.com/contest/327/problem/A
题意：从 i 到 j 翻转一次使得 1 的 个数最多~
直接暴力搞~
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int N;
int a[], b[];
int main( )
{
while(scanf("%d", &N)!= EOF){
for(int i=; i<N; ++ i){
scanf("%d", &a[i]);
b[i]=a[i];
}
int ans=-;
for( int i=; i<N; ++ i ){
for( int j=i; j<N; ++ j ){
for( int k=i; k<=j ; ++ k){
b[k]=-a[k];
}
int t=;
for( int k=; k<N; ++ k ){
if(b[k]) t++;
ans=ans>t?ans:t;
b[k]=a[k];
}
}
}
printf("%d\n", ans);
}
return ;
}
B. Hungry Sequence
链接：http://codeforces.com/contest/327/problem/B
题意：生成一个排列， 如果 i < j 那么 p[i]<p[j] 且 p[j]%p[i] != 0 ~
数据范围：n < =10^5 ~ 直接生成10^5个素数即可~
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int a[], p[];
void getp( )
{
for( int i=; i<=; i+= ){
if( !a[i] ){
for( int j=i*i; j<; j+=i ){
a[j]=;
}
}
}
p[]=;
int k=;
for(int i=; i<; i+=){
if( !a[i] )p[k++]=i;
}
}
int main( )
{
getp( );
int N;
while( scanf("%d", &N)!= EOF ){
for ( int i=; i<N; ++ i ){
printf(i!=N-?"%d ":"%d\n", p[i]);
}
}
return ;
}
C. Magic Five
链接：http://codeforces.com/contest/327/problem/C
题意：给定字符串 s 和 整数 k 表示有 k 个 s 重复组成的字符串 S‘ 要从中截取一些，使得剩下的字符串能表示的整数能整除5~
思路： 等比数列求和；
例如求sum=2^1+2^2+2^3+2^4+2^5+2^6+2^7 .. + 2^n~
公式就为 若n%2==0 T(n)=T(n/2)+T(n/2)*2^(n/2);
若n%2==1 T(n)=T(n/2)+T(n/2)*2^(n/2)+ 2^n;
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef __int64 LL;
const LL Mod=1e9+;
char s[];
LL m, k, ans, x;
LL P_M(int x, int n )
{
LL rec=, t=x;
while( n ){
if(n&){
rec*=t;
rec%=Mod;
}
t*=t;
t%=Mod;
n>>=;
}
return rec;
}
LL Sum( int x, int n )
{
if( n== )
return x;
LL t=Sum( x, n/ );
t=( t+t*P_M(m, n/))%Mod;// m为公比；
if( n& ) t=(t+P_M( m, n-)*x)%Mod;// 加上an
return t;
} int main( )
{
while( scanf("%s%I64d", s, &k)!= EOF ){
int l=strlen ( s );
m=P_M(, l), x=;
for( int i=; i<l; ++ i ){
if( s[i]=='' || s[i]=='' ){
ans=(ans+x)%Mod;
}
x=(x*)%Mod;
}
ans=Sum( ans, k );
printf("%I64d\n", ans);
}
return ;
}
D. Block Tower
链接：http://codeforces.com/contest/327/problem/D
题意：堆房子，要求人最多，堆红色的时候，要求边上一定要有蓝色的~
思路：只要总数最大，过程不做要求~所以可以把每一块先变成蓝色， 再逐渐变成红色~
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
#define lega(x, a) ((x)<=(a) && 0 <(x))
char s[][];
bool vi[][];
int N, M, ans;
struct Node
{
int x, y;
bool f;
Node( ){}
Node(int _x, int _y, bool _f){
x=_x, y=_y, f=_f;
}
}p;
stack<Node>sn;
const int xx[]={,,,-};
const int yy[]={,-,,};
void DFS( int x, int y )
{
int _x,_y;
for( int i=; i<; ++ i ){
_x=x+xx[i], _y=y+yy[i];
if( lega(_x,N) && lega(_y, M) && !vi[_x][_y] ){
vi[_x][_y]=;
sn.push(Node( _x,_y, false ));
DFS( _x, _y );
}
}
} int main( )
{
while( scanf("%d%d", &N, &M)!= EOF ){
for( int i=;i<=N; ++ i ){
scanf("%s", s[i]+);
}
while(!sn.empty()){
sn.pop( );
}
memset(vi, , sizeof vi);
ans=;
for( int i=; i<=N; ++ i ){
for( int j=; j<=M; ++ j ){
if( !vi[i][j]&&s[i][j]=='.' ){
vi[i][j]=;
sn.push(Node(i, j, true));
ans-=; // 最后一个不能被拆， 减少两次操作
DFS(i, j); }
}
}
ans+=*sn.size( );
printf("%d\n", ans);
for( int i=; i<=N; ++ i ){
for(int j=; j<=M; ++ j){
if( vi[i][j] ){
printf("B %d %d\n", i, j);
}
}
}
while( !sn.empty( ) ){
p=sn.top( );
sn.pop( );
if( !p.f ){// 只要求建红色的时候边上有蓝色的， 并不是要求最后的状态是红色边上有蓝色
printf("D %d %d\n", p.x, p.y);
printf("R %d %d\n", p.x, p.y);
}
}
}
return ;
}
E. Axis Walking
链接：http://codeforces.com/contest/327/problem/E
题意： 有两个集合 A， K， 要求 A 集合的一个排列， 其前缀和不等于 k 中任意一个元素， 求有多少个排列~
思路： 设 A 集合的元素为 a1, a2, a3~~~an, 用一整数 x 的对应位表示~
DP方程,i表示选择从1–n中选择 i 个数字，dp[i][n]表示可行解
dp[0][n]=1，表示初始状态.
如x的二进制位为1111。分别表示有a1,a2,a3,a4 ，四个数~
则有 dp[1111]=dp1110]+dp[1101]+dp[1011]+dp[0111]~
#include <cstdio>
#include <cmath>
#include <iostream>
#define lowbit(x) ((x)&(-x))
using namespace std; const int Mod=1e9+;
int N, K, a[];
int b[(<<)+], dp[(<<)+];
int main( )
{
while( scanf("%d", &N)!= EOF ){
int kk[]={};
for( int i=; i<N; ++ i ){
scanf("%d", &a[i]);
b[<<i]=a[i];
}
scanf("%d", &K);
for( int i=; i<K; ++ i ){
scanf("%d", &kk[i]);
}
dp[]=, b[]=;
for( int i=; i<(<<N); ++ i ){
b[i]=b[i-lowbit(i)]+b[lowbit(i)];
if(b[i]==kk[] || b[i]==kk[]){
continue;
}
int temp=;
for( int j=i; j; j-=lowbit(j) ){
temp+=dp[i-lowbit(j)];
while( temp>=Mod )temp-=Mod;
}
dp[i]=temp;
}
printf("%d\n", dp[(<<N)-]);
}
return ;
}