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）即可。當然也可以用素數篩選法，篩選出素數。

代碼：

[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[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; 
} 

#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[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<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; 
 
#define m 1000000007  
 
char save[110000]; 
 
ll quick(ll a,ll n) //快速冪求a^n%m  
{ 
   ll res=1; 
 
   while(n) 
   { 
      if(n&1) 
         res=(res*a)%m; 
      n=n>>1; 
      a=a*a%m; 
   } 
   return res; 
} 
 
int save1[110000]; 
 
 
int main() 
{ 
   ll k; 
 
   save1[0]=1; 
   save1[1]=2; 
   for(int i=2;i<=100000;i++) 
      save1[i]=(save1[i-1]*2)%m; 
 
   while(scanf("%s",save)!=EOF) 
   { 
      scanf("%I64d",&k); 
      int len=strlen(save); 
 
      ll ans=0; 
      ll M=quick(2,len); 
      M=quick(M-1,1000000005); //求出分母的逆元  
      for(int i=0;i<len;i++) 
         if(save[i]=='0'||save[i]=='5') 
            ans=(ans+save1[i])%m; //先求出一個串的情況  
      ans=(ans*(quick(2,len*k)-1))%m*M%m;//根據等比數列公式  
 
      printf("%I64d\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;

#define m 1000000007

char save[110000];

ll quick(ll a,ll n) //快速冪求a^n%m
{
   ll res=1;

   while(n)
   {
      if(n&1)
         res=(res*a)%m;
      n=n>>1;
      a=a*a%m;
   }
   return res;
}

int save1[110000];

int main()
{
   ll k;

   save1[0]=1;
   save1[1]=2;
   for(int i=2;i<=100000;i++)
      save1[i]=(save1[i-1]*2)%m;

   while(scanf("%s",save)!=EOF)
   {
      scanf("%I64d",&k);
      int len=strlen(save);

      ll ans=0;
      ll M=quick(2,len);
      M=quick(M-1,1000000005); //求出分母的逆元
      for(int i=0;i<len;i++)
         if(save[i]=='0'||save[i]=='5')
            ans=(ans+save1[i])%m; //先求出一個串的情況
      ans=(ans*(quick(2,len*k)-1))%m*M%m;//根據等比數列公式

      printf("%I64d\n",ans);

   }
   return 0;
}

D. Block Tower

題目意思：

在每個.處都可以填R，得到100個人，在每個R旁邊都可以填B,得到200個人。

可以隨時銷毀一個R或者B，問你怎樣安排，能使得得到的人數最多，輸出填充的方案。

解題思路：

dfs

容易證明，每一塊聯通的.區都可以湊成一個B和其他的都是R，這樣得到的人數肯定是最多的。

一遍dfs，然後直接輸出就可以了。

代碼：

[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; 
 
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/ 
 
char save[550][550]; 
int n,m; 
bool vis[550][550]; 
int dir[4][2]={-1,0,0,1,1,0,0,-1}; 
int ans; 
 
bool iscan(int x,int y) 
{ 
   if(x<1||x>n||y<1||y>m) 
      return false; 
   return true; 
} 
struct Rec 
{ 
   char k; 
   int x,y; 
}rec[1100000]; 
 
void dfs(int x,int y) 
{ 
   int xx,yy; 
 
   for(int i=0;i<4;i++) 
   { 
      xx=x+dir[i][0],yy=y+dir[i][1]; 
 
      if(iscan(xx,yy)) 
      { 
         if(save[xx][yy]!='.') 
            continue; 
         if(vis[xx][yy]) 
            continue; 
         vis[xx][yy]=true; 
         ans++; 
         //printf("B %d %d\n",xx,yy);  
         rec[ans].k='B',rec[ans].x=xx,rec[ans].y=yy; 
         dfs(xx,yy); //先B 再D 再R  
         ans++; 
         //printf("D %d %d\n",xx,yy);  
         rec[ans].k='D',rec[ans].x=xx,rec[ans].y=yy; 
         ans++; 
         //printf("R %d %d\n",xx,yy);  
         rec[ans].k='R',rec[ans].x=xx,rec[ans].y=yy; 
      } 
   } 
} 
 
int main() 
{ 
   while(scanf("%d%d",&n,&m)!=EOF) 
   { 
      for(int i=1;i<=n;i++) 
         scanf("%s",save[i]+1); 
 
      memset(vis,false,sizeof(vis)); 
      ans=0; 
 
      for(int i=1;i<=n;i++) 
         for(int j=1;j<=m;j++) 
         { 
            if(save[i][j]=='.'&&!vis[i][j]) 
            { 
               //又一個新的聯通塊  
               vis[i][j]=true; 
               ans++; 
               //printf("B %d %d\n",i,j);  
               rec[ans].k='B',rec[ans].x=i,rec[ans].y=j; 
               dfs(i,j); //把這一塊全部掃完  
            } 
         } 
         printf("%d\n",ans); 
         for(int i=1;i<=ans;i++) 
            printf("%c %d %d\n",rec[i].k,rec[i].x,rec[i].y); 
   } 
   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;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/

char save[550][550];
int n,m;
bool vis[550][550];
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int ans;

bool iscan(int x,int y)
{
   if(x<1||x>n||y<1||y>m)
      return false;
   return true;
}
struct Rec
{
   char k;
   int x,y;
}rec[1100000];

void dfs(int x,int y)
{
   int xx,yy;

   for(int i=0;i<4;i++)
   {
      xx=x+dir[i][0],yy=y+dir[i][1];

      if(iscan(xx,yy))
      {
         if(save[xx][yy]!='.')
            continue;
         if(vis[xx][yy])
            continue;
         vis[xx][yy]=true;
         ans++;
         //printf("B %d %d\n",xx,yy);
         rec[ans].k='B',rec[ans].x=xx,rec[ans].y=yy;
         dfs(xx,yy); //先B 再D 再R
         ans++;
         //printf("D %d %d\n",xx,yy);
         rec[ans].k='D',rec[ans].x=xx,rec[ans].y=yy;
         ans++;
         //printf("R %d %d\n",xx,yy);
         rec[ans].k='R',rec[ans].x=xx,rec[ans].y=yy;
      }
   }
}

int main()
{
   while(scanf("%d%d",&n,&m)!=EOF)
   {
      for(int i=1;i<=n;i++)
         scanf("%s",save[i]+1);

      memset(vis,false,sizeof(vis));
      ans=0;

      for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
         {
            if(save[i][j]=='.'&&!vis[i][j])
            {
               //又一個新的聯通塊
               vis[i][j]=true;
               ans++;
               //printf("B %d %d\n",i,j);
               rec[ans].k='B',rec[ans].x=i,rec[ans].y=j;
               dfs(i,j); //把這一塊全部掃完
            }
         }
         printf("%d\n",ans);
         for(int i=1;i<=ans;i++)
            printf("%c %d %d\n",rec[i].k,rec[i].x,rec[i].y);
   }
   return 0;
}

E. Axis Walking

題目意思：

有n(<=24)個步伐可以走，讓你確定走的方式的種數，使得任意一步距起點到達的距離不能為k集合中的數據。

解題思路：

狀態壓縮dp.

dp[i]表示選擇i當前步伐滿足要求的走的方式的種數。

對於每一步，把它放到最後，用前面的構造出它來。

代碼：

[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  
#define m 1000000007  
using namespace std; 
 
int dp[1<<24];//dp[i]表示在i狀態的物品的排列個數  
int kk[2]; 
 
int main() 
{ 
   int n,k; 
 
   while(scanf("%d",&n)!=EOF) 
   { 
      for(int i=0;i<n;i++) 
         scanf("%d",&v[i]); 
 
      scanf("%d",&k); 
      for(int i=0;i<k;i++) 
         scanf("%d",&kk[i]); 
 
      dp[0]=1; 
      ll sum=0,lim=(1<<n)-1,w; //注意移位運算的優先級  
 
      for(int i=1;i<=lim;i++) 
      { 
         sum=w=0; 
         for(int j=0;j<n;j++) 
            if(i&(1<<j)) 
            { 
               sum+=v[j]; 
               w+=dp[i&(~(1<<j))]; //把該物品放到最後的種數  
            } 
         for(int j=0;j<k;j++) 
            if(sum==kk[j]) 
            { 
               w=0; 
               break; 
            } 
         dp[i]=w%m; 
      } 
      printf("%d\n",dp[lim]); 
   } 
 
   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
#define m 1000000007
using namespace std;

int dp[1<<24];//dp[i]表示在i狀態的物品的排列個數
int kk[2];

int main()
{
   int n,k;

   while(scanf("%d",&n)!=EOF)
   {
      for(int i=0;i<n;i++)
         scanf("%d",&v[i]);

      scanf("%d",&k);
      for(int i=0;i<k;i++)
         scanf("%d",&kk[i]);

      dp[0]=1;
      ll sum=0,lim=(1<<n)-1,w; //注意移位運算的優先級

      for(int i=1;i<=lim;i++)
      {
         sum=w=0;
         for(int j=0;j<n;j++)
            if(i&(1<<j))
            {
               sum+=v[j];
               w+=dp[i&(~(1<<j))]; //把該物品放到最後的種數
            }
         for(int j=0;j<k;j++)
            if(sum==kk[j])
            {
               w=0;
               break;
            }
         dp[i]=w%m;
      }
      printf("%d\n",dp[lim]);
   }

   return 0;
}