CF 191 div.2 解题报告 - c++编程基础

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 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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
#

CF 191 div.2 解题报告 (二)