注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

2755: [SCOI2012]喵星人入侵 闲扯  

2013-03-15 00:48:24|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目大意】
n*m的格子 (max(n,m)<=20 ,min(n,m)<=6)。有三种格子,炮台,障碍,和空地。炮台可以对其周围八个方向的格子造成伤害。现在喵星人从点S出发前往点T,只能走空地,对于任意一种行进路线,其代价为经过的每个格子相邻的炮台个数的和。现在要求你在这个地图上安放一些障碍和炮台(要满足炮台数量K<=15,但可以无限放置障碍),使得喵星人受到的伤害最大。喵星人会走一条伤害最小的路径。

这是闲扯不是题解,大家可以出门左转http://hzaskywalker.blog.163.com/blog/static/20379815720132811613365/

托hzaskywalker的洪福A掉了此题。截至日志发表前在衡阳八中上用时排名第一,296ms。
首先我看了题觉得是爆搜……
然后读了hza的日志前几句话后终于大彻大悟,终于吉岛喵星人一定最后只可能走一条路的,其他的路我们都可以堵上。
于是就是dp简单路径鸟……是路径上的结点就加上周围的炮台的数量,是炮台就加上周围的路径上的结点的数量,加入代价中。
我使用传统的括号表示法,一共4个状态:'#', 'X', '(', ')','|',前两个是没有插头,'X'特别还表示轮廓线这里的上方有个炮台。后两个是传统的括号,最后一个是独立插头。
这样就是f[x][y][status][k]~f[x][y]用滚动的,[status]这里是手写的哈希表,[k]存在哈希表结点中。
记录状态的时候还多记了一个当前位置的左上角是啥状态~
很开心地写了~4 * 4的讨论。
很开心地WA了~

因为没有插头的地方,可能也有路啊囧囧囧!
于是我不会做了……
果断继续围观hza的题解……(吐槽:vfk你看题解时要不要这么坑……读了几句话认为会做了就跑了……)
发现记一下轮廓线上方的那些格子们是啥状态就行了。
于是删代码几乎只剩哈希表和DP类、状态类,重新写转移啊囧……
现在一个状态里有两条轮廓线的状态:
一个是线上的:' ', '(', ')', '|'。空插头,左括号,右括号,独立插头。
一个是轮廓线上方的那些格子:'#', 'X', '.'。障碍,炮台,路径上的结点。
然后使劲写就行了……(好像@hza不是括号表示法?)

其实这种题没啥题解可言吧……
自己YY下就行了……
我写这篇只是来吐槽的……

我先把哈希表开得很大,模的值也开的很大,然后使劲写了。
写出来发现和测试数据比较下,是WA了,还TLE了……
抬头望天不会调试……
去围观了上周星期天的@lydrainbowcat的contest hunter的E题……觉得很巧妙……放松了下心情~
回来调试顿觉浑身都是力气……

然后下午过去了……
晚饭吃过了……
11点的钟声敲响了……(吐槽:11点会敲钟?)
终于发现了错误……
在dp换行的时候……本来是这样写的……

for (HashTab<status, arrayF>::node *p = g->pool; p != g->tail; p++)
{

if (p->key.get1(nCol) == ' ')
{
tsta = p->key;
tsta.newLine();
(*f)[tsta] = p->val; //!!!!
}
}

感叹号那句是错的……
至于为啥……
应该是用p->val来更新(*f)[sta]……
因为换行的缘故……本来有些不相同的状态会变得相同……这时直接赋值是不对的……
(吐槽:你这代码太难懂了!写的啥啊!)
将就着看下吧……T_T……没懂算了……只有sb vfk才会犯这么低级的错……

然后搞出来了……
我估摸着最坏情况应该是:
6 20 15
S...................
....................
....................
....................
....................
...................T

于是试了下,状态才几千而已。我为了保险还是开的30000。取模的数定的5669~
是在linux计算器里随便打数字,然后让它分解质因数,在分解质因数列表里找到的这样一个范围适中的质数。

既然是闲扯就一扯到底……目前的代码习惯是:
ThisIsVariable:称为风格A。
thisIsVariable:称为风格B。
this_is_variable:称为C语言风格。

MaxN:属于常量,使用风格A。
relax:C++语言风格的函数,使用C语言风格~类似的还有clear、push_back、dblcmp
PublicVariable:公有成员,全局变量,使用风格A。
privateVariable:私有成员,局部变量,使用风格B。
nRow, nCol, nFort:虽然这是全局变量,但实际工程中把这些变量丢到全局会导致代码很凌乱,本应该私有或者把整体封装成类,但竞赛中为了编程简便,为了程序运行效率放在全局,所以使用风格B。
struct status:轻量级类型定义为结构体,使用风格B。表示这种类型比较轻便,赋值操作可以看成O(1)的。一般没有私有成员,成员变量、成员函数使用风格B。
class HashTab:重量级类型定义为class,使用风格A。表示这种类型很重,例如数组、平衡树、哈希表等,赋值操作所需时间巨大。私有成员使用风格B,公有成员使用风格A。受保护的成员……至今没使用过……如果要写肯定用风格B。有时为了程序效率和简洁,暴露一部分私有成员,这部分成员仍使用风格B。
下划线:出现下划线有三种情况,一是写了C语言风格函数,所以写下划线保持风格统一。例如push_back。二是懒得定义结构体时暂时替代一下,比如adj_pool就代表邻接表的内存池……adj_tail表示邻接表内存池尾指针……三是这个变量定义了马上就删……常用于调试……不过你在我的程序里是找不到这样的变量了……因为被我删了……
orz:实在想不出叫啥名字的时候的替代名称……比如dijkstra时的那个堆……叫Heap的话……又不妥当……略坑……按照功能来命名应该叫ModifiablePriorityQueue——可修改优先队列。显然名字太长了。于是就叫OrzHeap……

维持代码整洁~
当我有一天忘记某题是怎么做的时候……
如果我翻开我自己当年写的代码……
发现是天书……
该如何是好?

嘛……闲扯完了……
晒一下代码~最喜欢封装了……
也可以去发芽网看:http://fayaa.com/code/view/27505/

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int MaxN = 20;
const int MaxNFort = 15;

template <class T>
inline void relax(T &a, const T &b)
{
if (b > a)
a = b;
}

int nRow, nCol, nFort;
char a[MaxN][MaxN];

struct status
{
public:
int a1, a2;

status()
{
a1 = 0, a2 = 0;
}

inline char get1(int idx) const
{
idx <<= 1;
switch ((a1 >> idx) & 3)
{
case 0:
return ' ';
case 1:
return '(';
case 2:
return ')';
case 3:
return '|';
default:
exit(1);
}
}
inline void set1(int idx, char val)
{
idx <<= 1;
switch (val)
{
case ' ':
a1 &= ~(1 << idx);
a1 &= ~(1 << (idx + 1));
break;
case '(':
a1 |= 1 << idx;
a1 &= ~(1 << (idx + 1));
break;
case ')':
a1 &= ~(1 << idx);
a1 |= 1 << (idx + 1);
break;
case '|':
a1 |= 1 << idx;
a1 |= 1 << (idx + 1);
break;
default:
exit(1);
}
}

inline char get2(int idx) const
{
idx <<= 1;
switch ((a2 >> idx) & 3)
{
case 0:
return '#';
case 1:
return 'X';
case 2:
return '.';
default:
exit(1);
}
}
inline void set2(int idx, char val)
{
idx <<= 1;
switch (val)
{
case '#':
a2 &= ~(1 << idx);
a2 &= ~(1 << (idx + 1));
break;
case 'X':
a2 |= 1 << idx;
a2 &= ~(1 << (idx + 1));
break;
case '.':
a2 &= ~(1 << idx);
a2 |= 1 << (idx + 1);
break;
default:
exit(1);
}
}

inline void newLine()
{
a1 <<= 2;
set2(nCol, '#');
a2 <<= 2;
}

inline int getHashCode() const
{
return a1 << 15 | a2;
}

friend inline bool operator==(const status &lhs, const status &rhs)
{
return lhs.a1 == rhs.a1 && lhs.a2 == rhs.a2;
}
};

struct arrayF
{
int f[MaxNFort + 1];

arrayF()
{
fill(f, f + nFort + 1, INT_MIN);
}

inline int operator[](const int &idx) const
{
return f[idx];
}
inline int& operator[](const int &idx)
{
return f[idx];
}

inline void updateBy(const arrayF &g, const int &add, const int &cost)
{
for (int i = nFort; i >= cost; i--)
if (g[i - cost] != INT_MIN)
relax(f[i], g[i - cost] + add);
}
};

const int HashMod = 5669;
const int HashPoolLen = 30000;
template <class TKey, class TVal>
class HashTab
{
public:
struct node
{
TKey key;
TVal val;
node *next;
};
node pool[HashPoolLen], *tail;
node *head[HashMod];

HashTab()
: tail(pool)
{
fill(head, head + HashMod, (node*)NULL);
}

inline void clear()
{
fill(head, head + HashMod, (node*)NULL);
tail = pool;
}

inline TVal& operator[](const TKey &key)
{
int pos = key.getHashCode() % HashMod;
for (node *i = head[pos]; i; i = i->next)
if (i->key == key)
return i->val;
tail->key = key, tail->val = TVal();
tail->next = head[pos], head[pos] = tail++;
return head[pos]->val;
}
};

inline int handle()
{
static HashTab<status, arrayF> f_t1, f_t2;
HashTab<status, arrayF> *f = &f_t1, *g = &f_t2;

status tsta;
arrayF tf;
for (int c = 0; c <= nCol; c++)
tsta.set1(c, ' '), tsta.set2(c, '#');
for (int i = 0; i <= nFort; i++)
tf[i] = 0;
(*g)[tsta] = tf;

for (int r = 0; r < nRow; r++)
{
f->clear();

for (HashTab<status, arrayF>::node *p = g->pool; p != g->tail; p++)
{
if (p->key.get1(nCol) == ' ')
{
tsta = p->key;
tsta.newLine();
(*f)[tsta].updateBy(p->val, 0, 0);
}
}
swap(f, g);

for (int c = 0; c < nCol; c++, swap(f, g))
{
f->clear();

for (HashTab<status, arrayF>::node *p = g->pool; p != g->tail; p++)
{
if (p->val[nFort] == INT_MIN)
continue;
char le = p->key.get1(c);
char up = p->key.get1(c + 1);

char leB = c > 0 ? p->key.get2(c - 1) : '#';
char leupB = p->key.get2(c);
char upB = p->key.get2(c + 1);
char riupB = c < nCol - 1 ? p->key.get2(c + 2) : '#';

int cntFort = 0;
if (leB == 'X')
cntFort++;
if (leupB == 'X')
cntFort++;
if (upB == 'X')
cntFort++;
if (riupB == 'X')
cntFort++;
int cntRoad = 0;
if (leB == '.')
cntRoad++;
if (leupB == '.')
cntRoad++;
if (upB == '.')
cntRoad++;
if (riupB == '.')
cntRoad++;

bool canBuildRoad = true;
if (le == ' ' && leB == '.')
canBuildRoad = false;
if (up == ' ' && upB == '.')
canBuildRoad = false;

tsta = p->key;
if (le == ' ' && up == ' ')
{
if (a[r][c] == '.')
{
if (canBuildRoad)
{
tsta.set1(c, '('), tsta.set1(c + 1, ')');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
tsta.set1(c, ' '), tsta.set1(c + 1, ' ');
tsta.set2(c, '#');
(*f)[tsta].updateBy(p->val, 0, 0);

tsta.set1(c, ' '), tsta.set1(c + 1, ' ');
tsta.set2(c, 'X');
(*f)[tsta].updateBy(p->val, cntRoad, 1);
}
else if (a[r][c] == 'S' || a[r][c] == 'T')
{
if (canBuildRoad)
{
tsta.set1(c, '|'), tsta.set1(c + 1, ' ');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);

tsta.set1(c, ' '), tsta.set1(c + 1, '|');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if (a[r][c] == '#')
{
tsta.set1(c, ' '), tsta.set1(c + 1, ' ');
tsta.set2(c, '#');
(*f)[tsta].updateBy(p->val, 0, 0);
}
}

if (!canBuildRoad)
continue;

if ((le == ' ' && up == '(') || (le == '(' && up == ' '))
{
if (a[r][c] == '.')
{
tsta.set1(c, '('), tsta.set1(c + 1, ' ');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);

tsta.set1(c, ' '), tsta.set1(c + 1, '(');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
else if (a[r][c] == 'S' || a[r][c] == 'T')
{
int pos = c + 1;
int sum = 1;
while (sum != 0)
{
pos++;
switch (p->key.get1(pos))
{
case '(':
sum++;
break;
case ')':
sum--;
break;
}
}
tsta.set1(c, ' '), tsta.set1(c + 1, ' '), tsta.set1(pos, '|');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if ((le == ' ' && up == ')') || (le == ')' && up == ' '))
{
if (a[r][c] == '.')
{
tsta.set1(c, ')'), tsta.set1(c + 1, ' ');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);

tsta.set1(c, ' '), tsta.set1(c + 1, ')');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
else if (a[r][c] == 'S' || a[r][c] == 'T')
{
int pos = c;
int sum = -1;
while (sum != 0)
{
pos--;
switch (p->key.get1(pos))
{
case '(':
sum++;
break;
case ')':
sum--;
break;
}
}
tsta.set1(c, ' '), tsta.set1(c + 1, ' '), tsta.set1(pos, '|');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if ((le == ' ' && up == '|') || (le == '|' && up == ' '))
{
if (a[r][c] == '.')
{
tsta.set1(c, '|'), tsta.set1(c + 1, ' ');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);

tsta.set1(c, ' '), tsta.set1(c + 1, '|');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
else if (a[r][c] == 'S' || a[r][c] == 'T')
{
tsta.set1(c, ' '), tsta.set1(c + 1, ' ');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if (le == '(' && up == '(')
{
if (a[r][c] == '.')
{
int pos = c + 1;
int sum = 1;
while (sum != 0)
{
pos++;
switch (p->key.get1(pos))
{
case '(':
sum++;
break;
case ')':
sum--;
break;
}
}
tsta.set1(c, ' '), tsta.set1(c + 1, ' '), tsta.set1(pos, '(');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if (le == ')' && up == ')')
{
if (a[r][c] == '.')
{
int pos = c;
int sum = -1;
while (sum != 0)
{
pos--;
switch (p->key.get1(pos))
{
case '(':
sum++;
break;
case ')':
sum--;
break;
}
}
tsta.set1(c, ' '), tsta.set1(c + 1, ' '), tsta.set1(pos, ')');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if (le == '(' && up == ')')
;
else if ((le == '(' && up == '|') || (le == '|' && up == '('))
{
if (a[r][c] == '.')
{
int pos = c + 1;
int sum = 1;
while (sum != 0)
{
pos++;
switch (p->key.get1(pos))
{
case '(':
sum++;
break;
case ')':
sum--;
break;
}
}
tsta.set1(c, ' '), tsta.set1(c + 1, ' '), tsta.set1(pos, '|');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if ((le == ')' && up == '|') || (le == '|' && up == ')'))
{
if (a[r][c] == '.')
{
int pos = c;
int sum = -1;
while (sum != 0)
{
pos--;
switch (p->key.get1(pos))
{
case '(':
sum++;
break;
case ')':
sum--;
break;
}
}
tsta.set1(c, ' '), tsta.set1(c + 1, ' '), tsta.set1(pos, '|');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if (le == ')' && up == '(')
{
if (a[r][c] == '.')
{
tsta.set1(c, ' '), tsta.set1(c + 1, ' ');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
else if (le == '|' && up == '|')
{
if (a[r][c] == '.')
{
tsta.set1(c, ' '), tsta.set1(c + 1, ' ');
tsta.set2(c, '.');
(*f)[tsta].updateBy(p->val, cntFort, 0);
}
}
}
}
}

int res = 0;
for (HashTab<status, arrayF>::node *i = g->pool; i != g->tail; i++)
{
if (i->key.a1 == 0)
relax(res, i->val[nFort]);
}
return res;
}

int main()
{
cin >> nRow >> nCol >> nFort;
for (int r = 0; r < nRow; r++)
for (int c = 0; c < nCol; c++)
cin >> a[r][c];

if (nCol > nRow)
{
for (int r = 0; r < nCol; r++)
for (int c = 0; c < r; c++)
swap(a[r][c], a[c][r]);
swap(nCol, nRow);
}

cout << handle() << endl;

return 0;
}


  评论这张
 
阅读(1517)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017