求一个cf雷神号号，绝不乱搞

来源：蜘蛛抓取(WebSpider) 时间：2015-02-06 11:53 标签： 求一个cf的土豪账号
ACM_codeforces（73）
转载请注明出处，谢谢&&&
by---cxlove
题目：给出一个地图，某些位置有一些老鼠，有两个炸弹，攻击范围每一秒都能向4个方向扩散，不能穿过墙。炸弹会在d秒后爆炸，问是否能找到两个位置，放置炸弹，能炸死所有老鼠(= = 大概意思就这样
首先把所有的R找出来，可以通过R的个数剪枝一次。
我们可以发现d其实是很小的，也许这是一个突破口吧
每一个炸弹极限情况下能在d秒扩散的范围是可以算出来，就是一个菱形的东东吧。
那么两个炸弹最多覆盖的范围也可以算出来，这里可以 小剪一下。对于R很多的情况，直接pass掉了，good
那么再考虑可行的范围，一个炸弹能到达的位置，肯定是曼哈顿距离小于d
以每只老鼠为中心，先把所有可行的点拿出来(= =至少得覆盖一只老鼠才会开始考虑吧
其实这里也是可以剪枝一下的，我们考虑当一个炸弹扩散，最极端的情况是，最外面一圈是炸弹，然后再用最外面一圈去扩散，相当于炸弹扩散2*d次，可以算出最多有多少个位置可行，那么如果可行的位置过多，说明老鼠过于分散，也是不可行。
然后对于可行解去BFS，记录能到达哪些老鼠，对于每一个可能的可行解都用set记录了到达的老鼠标号。
最后两两枚举，合并set，判断是否能搞定所有老鼠。
TLE了好久，加上一个小剪枝就过了，果然是合并set太矬了
其实复杂度是可行的
BFS的状态数目最多大概为226吧，那个可能可行解上限大概是1200左右
#include&iostream&
#include&cstdio&
#include&map&
#include&cstring&
#include&cmath&
#include&vector&
#include&algorithm&
#include&set&
#include&string&
#include&queue&
#define inf 1600005
#define M 40
#define N 1005
#define maxn 2000005
#define eps 1e-7
#define zero(a) fabs(a)&eps
#define Min(a,b) ((a)&(b)?(a):(b))
#define Max(a,b) ((a)&(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD
#define lson step&&1
#define rson step&&1|1
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts(&OK&);
#define pi acos(-1.0)
#define lowbit(x) ((x)&(-(x)))
#pragma comment(linker, &/STACK:,&)
#define vi vector&int&
int row,col,d;
char str[N][N];
vector&pair&int,int& &rat,
int p[N][N];
set&int&s[N];
int way[4][2]={0,1,0,-1,1,0,-1,0};
bool flag[N][N];
bool check(int x,int y){
if(x&=0&&y&=0&&x&row&&y&col&&str[x][y]!='X')
int main(){
freopen(&input.txt&,&r&,stdin);
freopen(&output.txt&,&w&,stdout);
while(scanf(&%d%d%d&,&row,&col,&d)!=EOF){
rat.clear();mem(p,-1);
for(int i=0;i&i++){
scanf(&%s&,str[i]);
for(int j=0;j&j++)
if(str[i][j]=='R'){
rat.pb(mp(i,j));
p[i][j]=rat.size();
//剪枝，两个位置，扩展d次，可以算出最多覆盖多少个格子
int t=d+1;
if(rat.size()&2*(2*sqr(t)-2*t+1)){
puts(&-1&);
for(int i=0;i&rat.size();i++){
for(int j=-d;j&=d;j++){
for(int k=-d;k&=d;k++){
if(abs(j)+abs(k)&d)
int x=rat[i].first+j;
int y=rat[i].second+k;
if(check(x,y)) tmp.pb(mp(x,y));
sort(tmp.begin(), tmp.end());
int size=unique(tmp.begin(), tmp.end())-tmp.begin();
if(size& 2*(2*sqr(t)-2*t+1) ){
puts(&-1&);
for(int i=0;i&i++){
queue&pair&pair&int,int&,int& &
while(!que.empty()) que.pop();
mem(flag,false);
flag[tmp[i].first][tmp[i].second]=
que.push(mp(mp(tmp[i].first,tmp[i].second),0));
while(!que.empty()){
pair&pair&int,int&,int&u=que.front(),v;
que.pop();
if(str[u.first.first][u.first.second]=='R')
s[i].insert(p[u.first.first][u.first.second]);
if(u.second&=d)
for(int i=0;i&4;i++){
v.first.first+=way[i][0];
v.first.second+=way[i][1];
v.second+=1;
if(check(v.first.first,v.first.second)&&!flag[v.first.first][v.first.second]){
flag[v.first.first][v.first.second]=
que.push(v);
for(int i=0;i&size&&!i++){
for(int j=i+1;j&size&&!j++){
//唔，这个剪枝，直接从T到100ms，果然我乱用set太慢了
if(s[i].size()+s[j].size()&rat.size())
set&int&temp(s[i]);
for(set&int&::iterator it=s[j].begin();it!=s[j].end();it++)
temp.insert(*it);
if(temp.size()==rat.size()){
printf(&%d %d %d %d\n&,tmp[i].first+1,tmp[i].second+1,tmp[j].first+1,tmp[j].second+1);
if(!ans) puts(&-1&);
for(int i=0;i&i++) s[i].clear();
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1057572次
积分：16123
积分：16123
排名：第447名
原创：434篇
评论：939条
(1)(1)(4)(1)(3)(12)(16)(13)(2)(7)(8)(20)(11)(2)(29)(22)(27)(58)(130)(44)(9)(5)(10)(7)

我要回帖

更多关于 求一个cf的土豪账号 的文章

 

随机推荐