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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

2094: [Poi2010]Ones 闲扯  

2013-03-30 22:55:28|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目大意】
BZOJ上描述是坑你的。 = =
说有一个01串,去掉前导0和结尾0,那么现在有一头一尾两个1对不对……
如果一个1,它处于开头或者结尾,且不与1相邻,那么就称之为ufo……
10001010有两个ufo……10000000000011000000有一个ufo……10000001000000有两个ufo……00000100000000000只有一个ufo
sks(n) = 1..n这n个数的二进制表示中ufo的总个数。
sks(5) = 5, sks(256) = 249
现在REP(n)表示把相同的叠在一起……啥意思呢……就是
REP(111111000001100) = {6, 5, 2, 2}
代表一开始有6个1,5个0,2个1,2个0。
现在给你REP(n),要你求REP(sks(n))。
|REP(n)| <= 10^6, n <= 2 ^ (10 ^ 9)

【闲扯】
这是闲扯不是题解……要看题解请出门左转……好吧我也列不出优良题解的传送门了。
所谓闲扯就是极其抽象的题解。

数位统计……公式好想好推……
最狗血的地方是:
1. 已知REP(a), REP(b),求REP(a + b)
2. 已知REP(a), REP(b),求REP(a - b)
老错,一堆特判,写得我快疯了……
从此得上了离散化恐惧症……

T_T 这题要说题解没啥好说的吧……使劲写就行了。调试很累人……
公式有不清楚的可以看我的主函数~
orz_handle是暴力。

反正最后还RE了一次……是因为有两个vector用完了以后放在那里没管它,结果后面又要申请内存时不够用了。把那两个vector用完后释放掉就A掉了囧。看来RE的实际意思是“这里没有多余的内存可申请了”。

说实话高精度类继承自vector<int>实在是太爽了~

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
using namespace std;

typedef pair<int, int> PII;

// getint
inline int getint()
{
char c;
while (c = getchar(), ('0' > c || c > '9') && c != '-');

if (c != '-')
{
int res = c - '0';
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return res;
}
else
{
int res = 0;
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return -res;
}
}

class BigNum : public vector<int>
{
private:
static inline void mergePos(const BigNum &lhs, const BigNum &rhs, vector<int> &pos)
{
vector<int> lhsPos, rhsPos;
lhs.GetBlockStart(back_inserter(lhsPos));
rhs.GetBlockStart(back_inserter(rhsPos));

merge(lhsPos.begin(), lhsPos.end(), rhsPos.begin(), rhsPos.end(), back_inserter(pos));
pos.erase(unique(pos.begin(), pos.end()), pos.end());
}

static inline void simplifyBlock(vector<PII> &d)
{
vector<PII>::iterator last = d.begin();
for (vector<PII>::iterator i = d.begin(), j = d.begin(); i != d.end(); i = j)
{
while (j != d.end() && i->second == j->second)
j++;
*last++ = PII(i->first, i->second);
}
d.erase(last, d.end());
}
public:
BigNum(){}
BigNum(const int &rhs)
{
*this = rhs;
}

inline void Input()
{
int n = getint();
for (int i = 0; i < n; i++)
{
int t = getint();
push_back(t);
}
}
inline void Output() const
{
printf("%d\n", (int)size());
for (int i = 0; i < (int)size(); i++)
{
printf("%d", (*this)[i]);
if (i != (int)size() - 1)
putchar(' ');
else
putchar('\n');
}
}

inline int GetLen() const
{
return accumulate(begin(), end(), 0);
}

inline int CountOne() const
{
int res = 0;
for (int i = 0; i < (int)size(); i += 2)
res += (*this)[i];
return res;
}

inline int GetFirstTwo() const
{
if ((*this)[0] == 1)
return 2;
else
return 3;
}

inline void EraseFirst()
{
front()--;
if (front() == 0)
{
erase(begin());
if (size() > 0)
erase(begin());
}
}

template <class OutputIterator>
inline OutputIterator GetBlockC(const vector<int> &pos, OutputIterator out) const
{
vector<int> res;
int sum = 0, c = size() % 2;
int j = 0;
for (int i = (int)size() - 1; i >= 0; i--)
{
sum += (*this)[i];
while (j < (int)pos.size() && sum > pos[j])
{
*out++ = c;
j++;
}
c ^= 1;
}
while (j < (int)pos.size())
*out++ = c, j++;
return out;
}
template <class OutputIterator>
inline OutputIterator GetBlockStart(OutputIterator out) const
{
vector<int> res;
int sum = 0;
*out++ = sum;
for (int i = (int)size() - 1; i >= 0; i--)
{
sum += (*this)[i];
*out++ = sum;
}
return out;
}

inline BigNum& operator+=(const BigNum &rhs)
{
if (rhs.empty())
return *this;
if (empty())
return *this = rhs;

vector<int> pos;
mergePos(*this, rhs, pos);

vector<int> lhsD, rhsD;
this->GetBlockC(pos, back_inserter(lhsD));
rhs.GetBlockC(pos, back_inserter(rhsD));

vector<PII> allD;

int add = 0;
for (int i = 0; i < (int)pos.size() - 1; i++)
{
if (add == 1)
{
if (lhsD[i] == 0 && rhsD[i] == 0)
{
allD.push_back(PII(pos[i], 1));
if (pos[i + 1] - pos[i] > 1)
allD.push_back(PII(pos[i] + 1, 0));
add = 0;
}
else if (lhsD[i] == 1 && rhsD[i] == 1)
{
allD.push_back(PII(pos[i], 1));
add = 1;
}
else
{
allD.push_back(PII(pos[i], 0));
add = 1;
}
}
else
{
if (lhsD[i] & rhsD[i])
{
allD.push_back(PII(pos[i], 0));
if (pos[i + 1] - pos[i] > 1)
allD.push_back(PII(pos[i] + 1, 1));
add = 1;
}
else
{
allD.push_back(PII(pos[i], lhsD[i] ^ rhsD[i]));
add = 0;
}
}
}
if (add == 1)
{
allD.push_back(PII(pos.back(), 1));
allD.push_back(PII(pos.back() + 1, 0));
}
else
allD.push_back(PII(pos.back(), 0));

simplifyBlock(allD);

clear();
for (int i = 1; i < (int)allD.size(); i++)
push_back(allD[i].first - allD[i - 1].first);
reverse(begin(), end());

return *this;
}
inline BigNum& operator-=(const BigNum &rhs)
{
if (rhs.empty())
return *this;
if (empty())
return *this = rhs;

vector<int> pos;
mergePos(*this, rhs, pos);

vector<int> lhsD, rhsD;
this->GetBlockC(pos, back_inserter(lhsD));
rhs.GetBlockC(pos, back_inserter(rhsD));

vector<PII> allD;

int add = 0;
for (int i = 0; i < (int)pos.size() - 1; i++)
{
if (add == 1)
{
if (lhsD[i] == 0 && rhsD[i] == 1)
{
allD.push_back(PII(pos[i], 0));
add = 1;
}
else if (lhsD[i] == 1 && rhsD[i] == 0)
{
allD.push_back(PII(pos[i], 0));
if (pos[i + 1] - pos[i] > 1)
allD.push_back(PII(pos[i] + 1, 1));
add = 0;
}
else
{
allD.push_back(PII(pos[i], 1));
add = 1;
}
}
else
{
if (lhsD[i] >= rhsD[i])
{
allD.push_back(PII(pos[i], lhsD[i] ^ rhsD[i]));
add = 0;
}
else
{
allD.push_back(PII(pos[i], 1));
if (pos[i + 1] - pos[i] > 1)
allD.push_back(PII(pos[i] + 1, 0));
add = 1;
}
}
}
allD.push_back(PII(pos.back(), 0));

simplifyBlock(allD);

clear();
for (int i = 1; i < (int)allD.size(); i++)
push_back(allD[i].first - allD[i - 1].first);
reverse(begin(), end());

return *this;
}

inline BigNum& operator<<=(const int &rhs)
{
if (size() % 2 == 0)
back() += rhs;
else
push_back(rhs);
return *this;
}
inline BigNum& operator>>=(const int &rhs)
{
int t = rhs;
while (!empty() && t > 0)
{
int delta = min(back(), t);
t -= delta;
back() -= delta;
if (back() == 0)
pop_back();
}
return *this;
}

inline BigNum& operator=(int rhs)
{
clear();

int t_n = 0;
int t[31];

while (rhs > 0)
t[t_n++] = rhs & 1, rhs >>= 1;
for (int i = 0, j = 0; i < t_n; i = j)
{
while (j < t_n && t[i] == t[j])
j++;
push_back(j - i);
}
reverse(begin(), end());

return *this;
}

inline operator int() const
{
int res = 0;
for (int i = 0; i < (int)size(); i++)
for (int j = 0; j < (*this)[i]; j++)
res = res << 1 | ((i + 1) & 1);
return res;
}
};

inline int orz_handle(const int &n)
{
if (n == 1)
return 1;
else if (n == 2)
return 2;
else
{
int res = 2;
for (int i = 3; i <= n; i++)
{
int t = i;
while (!(t & 1))
t >>= 1;

if (t == 1)
res++;
else
{
if ((t & 3) == 1)
res++;
int j = 0;
while ((1 << j) <= t)
j++;
j--;
if (!(t & 1 << (j - 1)))
res++;
}
}
return res;
}
}

int main()
{
BigNum n;
n.Input();

BigNum res = 0;

int l = n.GetLen();

if (l <= 4)
res = orz_handle((int)n);
else
{
BigNum t;

int firstTwo = n.GetFirstTwo();
if (firstTwo == 2)
{
t = 1;
t <<= l - 2;

res += t;

t = n;
t.EraseFirst();
t += 1;
res += t;
}
else if (firstTwo == 3)
{
t = 1;
t <<= l - 1;
res += t;
}

t = n;
t >>= 1;
res += t;
res += (n.size() + 1) / 2;

res -= l;
}

res.Output();

return 0;
}


  评论这张
 
阅读(1049)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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