平板电视与可动态更新的堆

家电下乡高价回收,笔记本、电脑、洗衣机……

嗯……不是那个平板电视。

平板电视介绍

Policy-Based Data Structures,简称平板电视,是C++ STD库函数的一套数据结构的总称。平板电视的功能强大,囊括了以下丰富内容:

  • 基于树规则的数据结构,包括了比STL跑的快到不知道哪里去的红黑树、根本手写不了的斐波那契堆、以及SPLAY TREE 
  • 基于字典树规则的数据结构(主要是Trie树)
  • 基于链表规则的数据结构(没有了解过)
  • 基于Hash规则的数据结构(Hashtable)
  • 还有本篇的重点:支持动态修改的堆(优先队列)

平板电视的使用主要是各种牛逼的树和优先队列。使用平板电视需要注意环境:在程序中引入头文件<bits/extc++.h>,如果编译通过就可以使用平板电视。

  • ACM/ICPC全部支持(理论上)
  • 做不出的OJ题(注意POJ全不支持)
  • 自己写程序爱用就用

我喜欢的是平板电视里的堆

使用平板电视的堆需要注意:PBDS的模板名与STD的完全一致,所以不能同时使用using namespace std; using namespace __gnu_pbds;,只能用一个或者最安全就是不要用整个namespace。

优先队列的模板

优先队列的模板如下:

template<
    typename Value_Type,
    typename Cmp_Fn = std::less<Value_Type>,
    typename Tag = pairing_heap_tag,
    typename Allocator = std::allocator<char> >
class priority_queue;

此处的四个参数分别是:数据类型、比较函数、堆种类和内存分配器。堆的种类共有5种:pairing_heap_tag, binary_heap_tag, binomial_heap_tag, rc_binomial_heap_tag, or thin_heap_tag

优先队列的使用

对于默认的堆,只需要用__gnu_pbds::priority_queue<int> pq;就可以声明了。默认和STD一样是大根堆,有pushtoppopclearemptybeginend等方法,可以和STD的优先队列一样使用。

不同的是,平板电视的优先队列的push方法会返回一个指针迭代器__gnu_pbds::priority_queue< TypeName >::point_iterator。这个指针迭代器会一直指着插入的数据,可以随时访问值,但注意不能直接修改它。

如果要修改某个值,可以调用modify方法,这个方法接受两个参数,第一个参数是指针迭代器,第二个是要更新的值(变大变小都可以)。

参考代码:

// A priority queue of integers.
priority_queue<int> p;

// Insert some values into the priority queue.
priority_queue<int>::point_iterator it = p.push(0);

p.push(1);
p.push(2);

// Now modify a value.
p.modify(it, 3);

assert(p.top() == 3);

可以将位于堆底的0修改成3,并且这个值在修改后冒到堆顶,并且指向它的迭代器也跟着过来了。

需要注意的是,如果指针迭代器对应的值已经被弹出堆,这个时候访问指针迭代器就会造成segment fault。

使用样例

由于GCC的页面出bug了,暂时没法阅读examples文件。链接:https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_examples.html

跑得非常快

在某道卡时间(其实根本不卡)的题目中使用cin cout读入、输出数据,平板电视优先队列来实现Dijkstra算法,全部跑完只用了572ms,根本没有被卡时间,跑的快的不得了!

(然后由于一些傻逼错误导致WA27%,找了四个多小时都没出错在哪,后来跟别人拍来拍去才知道自己题意没理解对……)

C++11 std骚操作

bits库

<bits/stdc++.h>包括了C++的所有标准库。

<bits/extc++.h>史诗般的外挂,包含了__gnu_pbds的所有内容,包括gp_hash_tablerope等。打死我都不要自己写数据结构了!

类型推导

编译器根据右边的表达式自动判断返回类型。

然而这玩意随便用用就能自损一千,特别好用的地方就是声明迭代器循环变量。

基于范围的for循环

不用写那么多东西,太爽了!但是记得要将循环变量用引用声明,否则随随便便就能TLE。

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int main() {
  vi v = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9};
  for (auto &i : v) {
    cout << i;
  }
  return 0;
}

运行结果:

1145141919

容器去重

<algorithm>里有一个unique函数,会将升序排序的容器中所有的除了第一次出现的元素全部扔掉。

用法:先排序,然后调用unique(start, end);

#include <bits/stdc++.h>
using namespace std;

#define trav(a, A) for (auto &a : A)
#define all(A) A.begin(), A.end()
typedef vector<int> vi;

int main() {
  vi v = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9};
  sort(all(v));
  auto last = unique(all(v));
  v.erase(last, v.end());
  trav(it, v) {
    cout << it << " ";
  }
  return 0;
}

输出结果:

1 4 5 9

bitset

初始化:bitset<length> foo; 构造函数可以用一个数或01字符串做参数。

对象函数:

  • []运算符或test(pos)访问某一位。
  • all()判断是否全为1。
  • any()none()判断是否有1。
  • count()返回所有1的个数
  • set()reset()flip()改变某一位的值。若无参数传入,则对所有的位执行同样的操作。
  • to_string()to_ulong()变成01字符串和整数。

hash

C++11启支持对string类、bitsetvector<bool>的hashing,使用方法如下:

#include <bits/stdc++.h>
using namespace std;

int main() {
  string str1 = "That's good.";
  string str2 = "That's goood.";
  hash<string> h;
  
  cout << h(str1) << endl << h(str2);
  return 0;
}

运行结果:

2177240917276858684
14580988214652125085

闷声发大财

赚 大 了

事情是这样的:

  • 早上线代课无聊刷微博
  • 网路冷眼推了一本屌炸天的Problem Solving书
  • 下载欣赏 -> 卧槽这内容神了
  • 给作者(world final玩家+coach+助理研究员+Google员工)发了封邮件,说想把他的东西写进自己的模板里
  • 然后作者竟然把他们用的模板直接推给我了

绝了!还用什么NJU模板!

所以之前你看到的aunt想要自己写模板的事情吹了。

最长回文子序列与最长回文子串

两种截然不同的问题。

最长回文子序列 (subsequence)

解决方法是动态规划。$dp[i][j]$表示区间$[i, j]$中最长的回文子序列的长度,那么可以获得递推公式
$$dp[i][j] = \begin{cases} dp[i+1][j-1] + 2 & s[i] == s[j] \\ \max(dp[i][j-1], dp[i+1][j]) & s[i] \neq s[j] \\ 1 & i == j \end{cases}$$

那还挺简单的

最长回文子串 (substring)

超暴力解法

对于每一个起始位置和结束位置,枚举所有可能的情况然后判断。时间复杂度$O(n^3)$。

暴力解法

列举每一个中心位置判断。时间复杂度$O(n^2)$。

Manacher算法

不知道哪个傻逼翻译成马拉车算法,我还以为和马+车有关系。

算法概述

  1. 首先通过插入相同的字符将$n$位的字符串转换为$2n+1$位的字符串,那么所有的回文串一定是奇数长度的。
  2. 维护数组$len$,$len[i]$记录以$i$为中心的最长回文串的右端到$i$的距离。$$len[i] = r – i + 1$$
  3. 以$i$为中心的最长回文串的长度是$len[i] – 1$(考虑对称性)。

计算方式

从左往右计算$len$数组,假设在计算$len[i]$时,前面所有位置中右端最远的回文串的中心为$mc$,$mr = mc + len[mc] – 1$。取$i$关于$mc$的对称点$j = 2mc – i$。

  1. 如果$i <= mr$
    1. 如果$i + len[j] < mr$,说明以$i$、$j$为中心的回文串关于$mc$完全对称,且是以$mc$为中心的回文串的子串。$len[i] = len[j]$。
    2. 如果$i + len[j] \ge mr$,需要对$mr$右侧的字符串进行手动匹配。
  2. 如果$i > mr$,得不到信息,只能手动匹配。

算法分析

你觉得我是$O(n^2)$的?其实我是线性的!

因为$mr$只能增长不能减小,所以复杂度是$O(n)$的。(如果放在期末考试里我绝对证不出来。)

例题

HDU3068,纯模板题。

因为没有判断取$mr-mc$和$len[j]$中较小的那一个WA了一发。找了一个反例是jojojooooj

#include <bits/stdc++.h>
using namespace std;
char ori[110005] = {};
char s[250005] = {};
int len[250005] = {};
int tot = 0, mc = 0, mr = 0, ans = 0;

int getString() {
  s[0] = '#';
  int tot = (int) strlen(ori);
  for (int i = 0; i < tot; ++i) {
    s[(i << 1) + 1] = ori[i];
    s[(i << 1) + 2] = '#';
  }
  return tot << 1;
}

int main() {
  while (scanf(" %s", ori) != EOF) {
    mc = mr = 0;
    ans = 1;
    tot = getString();
    for (int i = 0; i <= tot; ++i) {
      int j = (mc << 1) - i;
      if (i <= mr) {
        len[i] = min(mr - i + 1, len[j]);
        int pl = i - len[i], pr = i + len[i];
        while (pl >= 0 && pr <= tot && s[pl] == s[pr]) {
          len[i]++;
          pl--; pr++;
        }
      } else {
        len[i] = 1;
        int pl = i - len[i], pr = i + len[i];
        while (pl >= 0 && pr <= tot && s[pl] == s[pr]) {
          len[i]++;
          pl--; pr++;
        }
      }
      if (i + len[i] > mr) {
        mc = i;
        mr = i + len[i] - 1;
      }
      if (len[i] > ans) {
        ans = len[i] - 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

模板1-头文件与std库

本文是aunt正在策划的第二代ACM模板的第1部分。由于使用了一些垃圾的网站上扒下来的未测试代码,这篇文章的内容可能很糟糕!

但是他自己写的肯定都很吼

常用函数与头文件

  • scanfprintf,来自<cstdio>
  • powsqrtexp、三角函数等,来自<cmath>
  • memsetmemcpy等内存、字符串操作函数来自<cstring>
  • sortupperbound等算法函数来自<algorithm>
  • rand等来自<ctime>
  • cincout不是很喜欢用!
  • 数据结构:<vector><stack><set><queue>

include这么多,不如<bits/stdc++.h>(C++11)多方便。

“我为什么不喜欢用<bits/stdc++.h>?就是因为里面关键词太多了。”

——某队友

常见常量定义

“用你马的#define!”

—— Codeforces的出题/验题组是这么认为的。

  • $e$(自然常数):const double e = exp(1.0);
  • $\pi$:const double pi = acos(-1.0);
  • $\epsilon$(偏置值):const double eps = 1e-6;
  • $\inf$ :const int INF = 0x3f3f3f3f;

为什么不能用#define呢?

  • 代码可读性极差
  • 静态检查失效,无法捕捉异常
  • 没有静态常量的CPU处理加速
  • 淦,#define哪来类型安全???

常见容器与常见用法

std标准数据结构迭代器的使用方法:for (vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)。但是为什么不用C++11起支持的for (auto &bar : foo)循环体呢?

vector – 变长数组

  • 构造函数
    • vector<int> foo;
  • 迭代器
    • begin&end:正向迭代。
    • rbegin&rend:反向迭代。
  • 容量
    • size:返回大小。
    • empty:判断是否为空。
  • 元素访问
    • [n]at(n):访问某一个元素。
    • frontback:返回首末端元素。
  • 修改
    • push_back:在末尾新增元素,在C++11中建议使用emplace_back
    • pop_back:删除末尾元素;
    • insert:在指定位置后插入元素。第二个变量可以是值,也可以是两个迭代器等等。位置必须使用迭代器。函数返回插入的第一个元素的迭代器。在C++11中建议使用emplace
    • erase危险(易导致段错误) 删除指定位置的元素。函数返回下一个元素的新位置或者是数组末尾。
    • clear:清空数组。

deque – 双向队列

  • 构造函数:
  • 大部分内容与vector一致(包括[]访问方式)。除了deque还可以从头部访问:
    • push_frontemplace_front:从头部插入元素。
    • pop_front:从头部删除元素。

stack – 栈

  • 构造函数:stack<int> foo;
  • empty:判断是否为空。
  • size:返回大小。
  • top:返回栈顶元素。
  • push:压入元素。C++11推荐emplace
  • pop:弹出元素。

queue – 队列

  • 构造函数:queue<int> foo;
  • empty:判断是否为空。
  • size:返回大小。
  • front:返回队首元素。
  • back:返回队尾元素。
  • push:压入元素。C++11推荐emplace
  • pop:弹出元素。

priority_queue – 优先队列

除构造函数不同,其余皆与queue完 全 一 致。常用的构造方法有:

  • priority_queue <int> pq;最默认的构造方法,数字越大优先级越高。
  • priority_queue <int, vector<int>, less<int> > pq2; 从大到小。
  • priority_queue <int, vector<int>, greater<int> > pq3; 从小到大。
  • priority_queue <int, vector<int>, cmp() > pq4; 自定义。

注意:比较函数需要结构体定义了比较运算符<或创造重新定义了()运算符的比较结构体。

set – 集合

注意:set元素自动排序(实质是红黑树)。

  • 构造函数:set<int> foo;
  • 迭代器、容量与vector一致。元素不能通过[]at访问。
  • 操作函数:
    • find:寻找指定元素,返回它的迭代器或数组末尾。如foo.find(1);。删除时建议这么做:foo.erase(foo.find(1));
    • count:返回元素个数。
    • lower_bound:返回主键大于等于参数的第一个元素的迭代器或末尾。
    • upper_bound:返回主键大于等于参数的最后一个元素的迭代器或末尾。

map – 映射

注意:集合的元素都是pair类型,可以用指定pair两元素类型的构造函数创造,但是为什么不用统一的std函数make_pair呢?

  • 构造函数:map<int, string> foo;
  • 迭代器、容量:与vector一致。数组中的所有元素按主键升序排序。下面是插入元素的多种方式:
    • foo.insert(pair<int, string>(1, "bar"));
    • foo.insert(map<int, string>::value_type(2, "bar2"));
    • foo.insert(make_pair(3, "bar3"));
    • foo[1] = "bar3";
  • 元素访问:map每个元素有两个键值,访问方式为foo[1]->firstfoo[1]->second
  • 操作函数同set。

常见库函数与常见用法

数组初始化

马的 又TLE了!

——aunt已经因为下面代码太好用导致无数次TLE……

  • 置零:memset(a, 0, sizeof(a));
  • 置$-1$:memset(a, -1, sizeof(a));
  • 置$\inf$:memset(a, 0x3f, sizeof(a));

永远记得上面的初始化时间复杂度是$O(n)$的……

结构体定义

You have no class. – C++ to C

class foo{
 public:
  int bar;
  foo() {
    bar = 0;
  }
  foo(int bar) : bar(bar) {
    // do nothing
  }
  bool operator<(const foo &b) const {
    return bar < b.bar;
  }
}

比较函数与排序

  • sort、容器使用(升序):
    bool cmp(foo a, foo b) {
      return a < b;
    }
    
  • qsort用:
    int cmp(const void *a, const void *b) {
      return *(foo *)a < *(foo *)b ? -1 : 1;
    }
    

又难用还跑的慢的函数有存在的必要吗?

据徐臣所说,加上实际考证……sort会根据数据自动选择合适的排序方式,跑的比qsort快的不知道到哪里去了……所以qsort根本没有使用的必要。

常见骚操作

读入过滤

  • 按位读入:scanf("%1d", &foo);
  • 字符过滤(by徐臣):while(ch < 'a' || ch > 'z') ch = getchar();
  • 字符过滤v2:scanf(" %c", &c);

读入外挂

早就想抄一份了!但是直接扒网上的感觉也不太放心……(未测试代码警告

普通版

inline bool scan_d(int &num) {
  char in;
  bool IsN = false;
  in = getchar();
  if (in == EOF) {
    return false;
  }
  while (in != '-' && (in < '0' || in > '9')) {
    in = getchar();
  }
  if (in == '-') {
    IsN = true;
    num = 0;
  } else num = in - '0';
  while (in = getchar(), in >= '0' && in <= '9') {
    num *= 10, num += in - '0';
  }
  if (IsN) num = -num;
  return true;
}
inline bool scan_lf(double &num) {
  char in;
  double Dec = 0.1;
  bool IsN = false, IsD = false;
  in = getchar();
  if (in == EOF) return false;
  while (in != '-' && in != '.' && (in < '0' || in > '9'))
    in = getchar();
  if (in == '-') {
    IsN = true;
    num = 0;
  } else if (in == '.') {
    IsD = true;
    num = 0;
  } else num = in - '0';
  if (!IsD) {
    while (in = getchar(), in >= '0' && in <= '9') {
      num *= 10;
      num += in - '0';
    }
  }
  if (in != '.') {
    if (IsN) num = -num;
    return true;
  } else {
    while (in = getchar(), in >= '0' && in <= '9') {
      num += Dec * (in - '0');
      Dec *= 0.1;
    }
  }
  if (IsN) num = -num;
  return true;
}

豪华版

namespace fastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
//fread->read
bool IOerror = 0;
inline char nc() {
  static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, BUF_SIZE, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
    //{printf("IO error!\n");system("pause");for (;;);exit(0);}
  }
  return *p1++;
}
inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
inline void read(int &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc());
  if (IOerror)return;
  if (ch == '-')sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
  if (sign)x = -x;
}
inline void read(ll &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc());
  if (IOerror)return;
  if (ch == '-')sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
  if (sign)x = -x;
}
inline void read(double &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc());
  if (IOerror)return;
  if (ch == '-')sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
  if (ch == '.') {
    double tmp = 1;
    ch = nc();
    for (; ch >= '0' && ch <= '9'; ch = nc())tmp /= 10.0, x += tmp * (ch - '0');
  }
  if (sign)x = -x;
}
inline void read(char *s) {
  char ch = nc();
  for (; blank(ch); ch = nc());
  if (IOerror)return;
  for (; !blank(ch) && !IOerror; ch = nc())*s++ = ch;
  *s = 0;
}
inline void read(char &c) {
  for (c = nc(); blank(c); c = nc());
  if (IOerror) {
    c = -1;
    return;
  }
}
//getchar->read
inline void read1(int &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())if (ch == '-')bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar());
  if (bo)x = -x;
}
inline void read1(ll &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())if (ch == '-')bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar());
  if (bo)x = -x;
}
inline void read1(double &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())if (ch == '-')bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar());
  if (ch == '.') {
    double tmp = 1;
    for (ch = getchar(); ch >= '0' && ch <= '9'; tmp /= 10.0, x += tmp * (ch - '0'), ch = getchar());
  }
  if (bo)x = -x;
}
inline void read1(char *s) {
  char ch = getchar();
  for (; blank(ch); ch = getchar());
  for (; !blank(ch); ch = getchar())*s++ = ch;
  *s = 0;
}
inline void read1(char &c) { for (c = getchar(); blank(c); c = getchar()); }
//scanf->read
inline void read2(int &x) { scanf("%d", &x); }
inline void read2(ll &x) {
#ifdef _WIN32
  scanf("%I64d",&x);
#else
#ifdef __linux
  scanf("%lld",&x);
#else
  puts("error:can't recognize the system!");
#endif
#endif
}
inline void read2(double &x) { scanf("%lf", &x); }
inline void read2(char *s) { scanf("%s", s); }
inline void read2(char &c) { scanf(" %c", &c); }
inline void readln2(char *s) { gets(s); }
//fwrite->write
struct Ostream_fwrite {
  char *buf, *p1, *pend;
  Ostream_fwrite() {
    buf = new char[BUF_SIZE];
    p1 = buf;
    pend = buf + BUF_SIZE;
  }
  void out(char ch) {
    if (p1 == pend) {
      fwrite(buf, 1, BUF_SIZE, stdout);
      p1 = buf;
    }
    *p1++ = ch;
  }
  void print(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x)*s1++ = '0';
    if (x < 0)out('-'), x = -x;
    while (x)*s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)out(*s1);
  }
  void println(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x)*s1++ = '0';
    if (x < 0)out('-'), x = -x;
    while (x)*s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)out(*s1);
    out('\n');
  }
  void print(ll x) {
    static char s[25], *s1;
    s1 = s;
    if (!x)*s1++ = '0';
    if (x < 0)out('-'), x = -x;
    while (x)*s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)out(*s1);
  }
  void println(ll x) {
    static char s[25], *s1;
    s1 = s;
    if (!x)*s1++ = '0';
    if (x < 0)out('-'), x = -x;
    while (x)*s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s)out(*s1);
    out('\n');
  }
  void print(double x, int y) {
    static ll mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
                       1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL,
                       100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL};
    if (x < -1e-12)out('-'), x = -x;
    x *= mul[y];
    ll x1 = (ll) floor(x);
    if (x - floor(x) >= 0.5)++x1;
    ll x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];
    print(x2);
    if (y > 0) {
      out('.');
      for (size_t i = 1; i < y && x3 * mul[i] < mul[y]; out('0'), ++i);
      print(x3);
    }
  }
  void println(double x, int y) {
    print(x, y);
    out('\n');
  }
  void print(char *s) { while (*s)out(*s++); }
  void println(char *s) {
    while (*s)out(*s++);
    out('\n');
  }
  void flush() {
    if (p1 != buf) {
      fwrite(buf, 1, p1 - buf, stdout);
      p1 = buf;
    }
  }
  ~Ostream_fwrite() { flush(); }
} Ostream;
inline void print(int x) { Ostream.print(x); }
inline void println(int x) { Ostream.println(x); }
inline void print(char x) { Ostream.out(x); }
inline void println(char x) {
  Ostream.out(x);
  Ostream.out('\n');
}
inline void print(ll x) { Ostream.print(x); }
inline void println(ll x) { Ostream.println(x); }
inline void print(double x, int y) { Ostream.print(x, y); }
inline void println(double x, int y) { Ostream.println(x, y); }
inline void print(char *s) { Ostream.print(s); }
inline void println(char *s) { Ostream.println(s); }
inline void println() { Ostream.out('\n'); }
inline void flush() { Ostream.flush(); }
//puts->write
char Out[OUT_SIZE], *o = Out;
inline void print1(int x) {
  static char buf[15];
  char *p1 = buf;
  if (!x)*p1++ = '0';
  if (x < 0)*o++ = '-', x = -x;
  while (x)*p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf)*o++ = *p1;
}
inline void println1(int x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(ll x) {
  static char buf[25];
  char *p1 = buf;
  if (!x)*p1++ = '0';
  if (x < 0)*o++ = '-', x = -x;
  while (x)*p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf)*o++ = *p1;
}
inline void println1(ll x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(char c) { *o++ = c; }
inline void println1(char c) {
  *o++ = c;
  *o++ = '\n';
}
inline void print1(char *s) { while (*s)*o++ = *s++; }
inline void println1(char *s) {
  print1(s);
  *o++ = '\n';
}
inline void println1() { *o++ = '\n'; }
inline void flush1() {
  if (o != Out) {
    if (*(o - 1) == '\n')*--o = 0;
    puts(Out);
  }
}
struct puts_write {
  ~puts_write() { flush1(); }
} _puts;
inline void print2(int x) { printf("%d", x); }
inline void println2(int x) { printf("%d\n", x); }
inline void print2(char x) { printf("%c", x); }
inline void println2(char x) { printf("%c\n", x); }
inline void print2(ll x) {
#ifdef _WIN32
  printf("%I64d",x);
#else
#ifdef __linux
  printf("%lld",x);
#else
  puts("error:can't recognize the system!");
#endif
#endif
}
inline void println2(ll x) {
  print2(x);
  printf("\n");
}
inline void println2() { printf("\n"); }
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace fastIO;

最小圆(球)覆盖问题

如果早知道,只要贪心就能Y……

原题

43rd ACM-ICPC Nanjing Problem D

题意

在三维地图中选一个点,使得这个点到所有点的距离的最大值最小。点的个数$N<100$,时间限制3s。

思路

很明显就是最小球覆盖问题。 一开始以为是二分题,穷举所有可能的半径,判断球是否相交,相交就在$[l, mid]$区间内搜索,否则在$[mid, r]$区间内搜索。想想还挺对的(误)结果样例都过不了。

然后徐臣开始了他的骚操作:每次选出3个点找到球面的中垂线,然后覆盖球的球心肯定在上面,重复判断更新答案,$O(n^4)$。最后没写出来(写得出来有鬼了)

然后是我的烂操作:二分半径,然后将球心放在第一个点上,列举所有点,如果点不在球内,就二分找到最近的能够将它覆盖的球心位置,然后把球心移过去。最后判断所有点是否在球心内,然后继续二分,$O(n^2 \lg n)$。然后也是样例都没过。

最后剩下10分钟反正做不出就开始扫雷+数独了。

随机增量法

算法原理

首先随机排序,打乱输入的顺序。然后按顺序处理规模逐渐增大的子问题。

具体实现

(2维的比3维简单多了,类比一下就可以了)

随机排序后首先选择前2个点,求出他们的最小外接球(就是两点连线中点),然后依次判断后面的点。对于点$p_i$:

  • $p_i$在球上或球内,什么都不做;
  • $p_i$在球外,则一定在新的最小包围球的边界上。以$p_1 p_i$为直径建立新的球,判断其他点是否在球上或球内。
    • $p_j$在球上/球内,什么都不做;
    • $p_j$在球外,则一定与$p_1$和$p_i$共球面。找到这个最小的球面(三点平面过圆心),然后判断其他点是否在球上或球内。
      • $p_k$在球上/球内,什么都不做;
      • $p_k$在球外,则一定与$p_1$、$p_i$、$p_j$共球面。由于4个点确定一个球,此处找到的最大半径的球是最终答案。

昏睡数学

淦啊我要疯了这是人能做的吗???

已知直径

球心就是直径的中点。

已知3个点

要求过3个点的球最小,说明圆心与三点共面,只要求出三角形外心即可。求三角形外心首先要求出平面方程:设三点为$A$、 $B$、 $C$,外心坐标为$O(x_0, y_0, z_0)$,平面$ABC$的法向量为$$\vec{n} = \vec{AB} \times \vec{AC}$$

则对于任意的点$P \in ABC$,有$$ \vec{AP} \cdot \vec{n} = 0 $$

将$O$点带入点面式方程,化简得平面方程$$Ax+By+Cz+D=0$$

由$O$是三角形外心,得方程组

$$ \begin{cases}
2(x_a – x_b) x + 2(y_a – y_b) y + 2(z_a – z_b) z = (x_a^2+y_a^2+z_a^2) + (x_b^2+y_b^2+z_b^2) \\
2(x_a – x_c) x + 2(y_a – y_c) y + 2(z_a – z_c) z = (x_a^2+y_a^2+z_a^2) + (x_c^2+y_c^2+z_c^2) \\
Ax + By + Cz + D = 0
\end{cases} $$

用Gauss消元法即可求出球心坐标。

已知4个点

吐了!但只要排除共线、共面的情况,直接求解线性方程组就可以了!

$$ \begin{cases}
2(x_a – x_b) x + 2(y_a – y_b) y + 2(z_a – z_b) z = (x_a^2+y_a^2+z_a^2) + (x_b^2+y_b^2+z_b^2) \\
2(x_a – x_c) x + 2(y_a – y_c) y + 2(z_a – z_c) z = (x_a^2+y_a^2+z_a^2) + (x_c^2+y_c^2+z_c^2) \\
2(x_a – x_d) x + 2(y_a – y_d) y + 2(z_a – z_d) z = (x_a^2+y_a^2+z_a^2) + (x_d^2+y_d^2+z_d^2)
\end{cases} $$

模拟退火法

物理原理

样卷学习法学的物理,不懂!

算法原理

模拟退火法就是纯贪心的修改版。在搜索到某个局部最优解之后,普通的贪心算法就结束搜索了,但是模拟退火法会以一定的概率进行下一次搜索,这个概率随着时间的变化而减小。

伪代码

我的理解:

while (T > T_min)
  delta = S(n+1) - S(n)
  if (delta > 0)
    n++
  else
    if (exp(delta / T) > rand(0, 1))
      n++
      T = r * T // annealing
    else
      break

Wiki的理解:

Let s = s0
For k = 0 through kmax (exclusive):
  T ← temperature(k ∕ kmax)
  Pick a random neighbour, snew ← neighbour(s)
  If P(E(s), E(snew), T) ≥ random(0, 1):
    s ← snew
Output: the final state s

具体实现

选择任意一个点作为初始解,然后将所有点按到当前圆/球心的距离排序,向距离最远的点靠近。每次靠近的距离都会减小(相当于模拟退火法的概率逐渐减小),最后圆/球心原来越靠近最优解,半径趋近稳定。

对于每次靠近,靠近的距离都是相差的距离乘以一个祖传比例系数$r/temp$,其中$r$是当前位置的最大距离,$temp$是当前温度。至于为什么是这个系数,淦啊全世界是不是只有中国人用这个方法解决问题,我连篇论文都找不到!

复杂度分析

时间复杂度$O(n \lg T)$,其中$T$是选定的初始温度。$T$越大,答案越精确,花费时间越长。

补题

POJ 2069 Super Star (模拟退火)

网上找了好几个题解对着抄都WA,直接贴题解跑也WA,哭了 CSDN全是复读机真是垃圾

POJ是真坑爹,不支持C++0x和1x,不能用时间做随机种子(会RE),输出用%lf就WA,搞了半天改成%f就对了……

#include <cstdio>
#include <cmath>
#include <ctime>
#include <algorithm>
using namespace std;
const double e = exp(1.0);
const double eps = 1e-6;

class point {
 public:
  double x, y, z;
};

int n = 0;
point s[105] = {};

double getDis(point &a, point &b) {
  double dis2 = 0;
  dis2 += pow(a.x - b.x, 2);
  dis2 += pow(a.y - b.y, 2);
  dis2 += pow(a.z - b.z, 2);
  return sqrt(dis2);
}

double getMaxDis(point &c) {
  double maxDis = 0, nexDis = 0;
  for (int i = 0; i < n; ++i) {
    nexDis = getDis(c, s[i]);
    if (nexDis > maxDis) {
      maxDis = nexDis;
    }
  }
  return maxDis;
}

point getNextC(point &c, double temp) {
  int chosen = 0;
  double maxR = getDis(c, s[0]), nexR = 0;
  for (int i = 1; i < n; ++i) {
    nexR = getDis(c, s[i]);
    if (nexR > maxR) {
      maxR = nexR;
      chosen = i;
    }
  }
  return (point) {
      c.x + (s[chosen].x - c.x) / maxR * temp,
      c.y + (s[chosen].y - c.y) / maxR * temp,
      c.z + (s[chosen].z - c.z) / maxR * temp
  };
}

double getRandPct() {
  return (double) (rand() % 10000) / 10000.0;
}

double solve() {
  point c = (point) {0, 0, 0};
  double ans = getMaxDis(c);
  double temp = 1e5, rate = 0.998;
  while (temp > eps) {
    point nc = getNextC(c, temp);
    double nAns = getMaxDis(nc);
    if (nAns < ans) {
      c = nc;
      ans = nAns;
    } else {
      if (exp((ans - nAns) / temp) > getRandPct()) {
        c = nc;
        ans = nAns;
      }
    }
    temp *= rate;
  }
  return ans;
}

int main() {
  srand(12450); // f*ck POJ!
  while (scanf("%d", &n) != EOF && n != 0) {
    for (int i = 0; i < n; ++i) {
      scanf("%lf%lf%lf", &s[i].x, &s[i].y, &s[i].z);
    }
    printf("%.5f\n", solve()); // f*ck POJ!
  }
  return 0;
}

NowCoder 203A – Knight (搜索/贪心)

题意

无限大的棋盘,每次移动都是“日”字对角线形移动$(+1,+2)$,问你走到目的地的最小移动次数。

思路

目的地$(x,y)$可能非常远,直接搜索肯定boom,所以先贪心把距离减小然后再小范围地搜索。之后就各种RE WA反正做不对……

上网搜索题解之后发现这题可以完全不搜索直接贪心。

首先棋盘是完全对称的,可以改成只往右上方走,因为只能沿着日字形对角线走,所以可以再缩小范围,只对$y=x$上方的区域求解。首先沿着$y=2x$一路向上窜,然后:

  • 终点在$y=2x$上方的,用$(+1,+2)$和$(-1,+2)$重复向上直到距离终点纵向距离$<4$。
    • 距离为1,撤销一次$(-1,+2)$(或$(+1,+2)$),此时距离终点$(1,3)$,两步可以解决。
    • 距离为2,多走两步$(+2,+1)$和$(-2,+1)$解决。
    • 距离为3,多走三步$(+1,+2)$,$(+1,+2)$和$(-2,-1)$解决。
  • 终点在$y=2x$右侧的,把刚才的$(+1,+2)$改成两次$(+2,+1)$,直到横向距离$<3$。
    • 距离为1,撤销一次$(+2,+1)$,距离终点$(3,1)$,两步解决。
    • 距离为2,多走两步$(+1,+2)$和$(+1,-2)$解决。

然后WA了。emmm 治疗眼瞎之后发现有两个点$(1,3)$和$(2,2)$不满足上述条件(没有可以撤销的),需要特判。最后-10过了。

代码

#include <bits/stdc++.h>
using namespace std;
 
int solve(int x, int y) {
  if (x == 0 && y == 1) {
    return 3;
  } else if (x == 2 && y == 2) {
    return 4;
  } else {
    int st = 0, ret = 0;
    if (y >= 2 * x) {
      st = x, x -= st, y -= 2 * st, ret += st;
      st = y / 4, y -= st * 4, ret += st * 2;
      assert(x == 0);
      ret += y;
    } else {
      if (y & 1) {
        st = 1, x -= 2, y -= 1, ret += st;
      }
      st = y / 2, x -= st, y -= 2 * st, ret += st;
      st = x / 3, x -= st * 3, ret += st; // substitution
      ret += x;
    }
    return ret;
  }
}
 
int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    int x = 0, y = 0;
    scanf("%d%d", &x, &y);
    if (x < 0) x = -x;
    if (y < 0) y = -y;
    if (x > y) swap(x, y);
    printf("%d\n", solve(x, y));
  }
  return 0;
}

NowCoder 203H – Travel (排列组合)

题意

地图为一棵树,进行m次旅游,每次游览至少一座城市。为了方便,每次旅游游览的城市必须是连通的。此外,所有城市恰好只浏览一次。求总方案数。

思路

树长什么样根本不影响题解。只要找到$m-1$条边把这棵树断开即可。答案为$$\binom{n-1}{m-1} \times m!$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    exgcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
ll getInv(ll a, ll p) {
  ll d, x, y;
  exgcd(a, p, d, x, y);
  return d == 1 ? (x + p) % p : -1;
}
 
ll frac[100005] = {};
ll inv[100005] = {};
 
void init() {
  frac[0] = frac[1] = 1;
  for (int i = 2; i <= 100000; ++i) {
    frac[i] = frac[i - 1] * i % modulo;
  }
  for (int i = 0; i <= 100000; ++i) {
    inv[i] = getInv(frac[i], modulo);
  }
}
 
ll C(ll n, ll k) {
  return (frac[n] * inv[k] % modulo) * inv[n - k] % modulo;
}
 
int n = 0, m = 0, tmp = 0;
ll ans = 0;
 
int main() {
  init();
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; ++i) {
      scanf("%d%d", &tmp, &tmp);
    }
     
    ans = C(n-1, m-1) * frac[m] % modulo;
    printf("%lld\n", ans);
  }
  return 0;
}

NowCoder 203D – Shopping (贪心)

题意

你有$n$个商品要买,总共有$m$个购物车。如果购物车内买了个凳子,那么这个购物车最贵的商品半价。问你最小的花费是多少。

思路

最多只能有$m$或者凳子数量个商品半价。半价商品一定是最贵的。

代码

#include <bits/stdc++.h>
using namespace std;
 
int n = 0, m = 0;
int s[1005] = {};
double total = 0;
 
int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    total = 0;
    scanf("%d%d", &n, &m);
 
    int tmp = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
      scanf("%d%d", s + i, &tmp);
      if (tmp == 1) cnt++;
    }
 
    m = min(m, cnt);
    sort(s, s+n);
 
    for (int i = 1; i <= m; ++i) {
      total += (double) s[n - i] / 2;
    }
    for (int i = 0; i < n - m; ++i) {
      total += s[i];
    }
 
    printf("%.1lf\n", total);
 
  }
  return 0;
}