模板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;
}

Z Shell与Oh My Zsh

Z Shell

官网:http://zsh.sourceforge.net

据官网所称,Z Shell (zsh)是为了交互使用而打造的,也是一个强大的脚本语言,具有很多bash、ksh、tcsh的特性。

然而实际使用中,zsh就是一个和vi一样的一般般的软件。

安装Z Shell

  • Linux: apt install zsh
  • Windows: 洗洗睡吧

设置为默认shell

可用cat /etc/shells查看所有可用shell,用chsh -s "path-to-shell"设置默认选项。注意zsh与bash配置文件不同,环境变量需要重新配置。

Oh My Zsh

vi有vim这个外挂般的存在,zsh也有OMZ这个天外飞仙一样的软件外挂

Your terminal never felt this good before.

OMZ官网(https://ohmyz.sh/)如此说到。

功能

管理zsh的配置文件,拥有海量插件和主题,让你high到不行啊

插件(选推)

z

做PA总是cd太累了,z可以帮你模糊匹配你要前往的文件夹,比如你要从nemu/src/cpu/exec前往nemu/include/cpu,只需要执行z cpu回车就可以了,z会自动从浏览记录中匹配寻找文件夹。如果有多个重名文件夹,按tab键就可以看到列表了。

autojump

与z相同的功能,但是要额外安装autojump。跳转指令是j,我更喜欢z因为不用装东西。

extract

tar/zip/rar解压缩选项太多根本记不住怎么办?现在只要一个x指令就解决问题了!

git

自带的,包括branch显示和一大堆浓缩指令,不介绍了。

zsh-autosuggestions和zsh-syntax-highlighting

功能如标题所示,用shell就和用IDE一样,太爽了!

last-working-dir

打开终端自动回到上次工作的目录,很多人推,我不知道这个有啥好用的。

主题

https://github.com/robbyrussell/oh-my-zsh/wiki/Themes

自己挑,改配置文件就可以了,不过估计基本都会选agnoster。

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;
}

Codeforces 1030E – Vasya and Good Sequences (前后缀和+DP)

题意

给你$n$个数,每个数可以任意改变二进制中1的位置,问你有多少区间$[l,r]$满足操作后异或和为0。

题解

这题真是太妙了!(直接看题解的屑)

首先贪心,计算出二进制表示中1的个数$b_i$。计算出$b_i$的后缀和,那么对于某一个区间,可以$O(1)$计算出这个区间内1的个数的和。

满足条件的区间需要具备两个条件:

  • 1的个数之和为偶数
  • 1的个数最多的那个数的1的个数小于其他数1的个数的和(贪心)

那么只要穷举所有的$l$,$r > l+64$且后缀和奇偶性相同的一定满足(因为那个最大的数最多也就64位),其他的暴力判断一下就可以了。

代码

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

ll n = 0, ans = 0;
ll oddCnt = 0, evenCnt = 0;
ll s[300005] = {};
bool sumEven[300005] = {};

ll bitCnt(ll ori) {
  ll cnt = 0;
  while (ori) {
    cnt += ori & 1;
    ori >>= 1;
  }
  return cnt;
}

int main() {
  cin >> n;
  for (ll i = 0; i < n; ++i) {
    cin >> s[i];
    s[i] = bitCnt(s[i]);
  }

  ll sum = 0;
  oddCnt = 0, evenCnt = 1, sumEven[n] = true;
  for (ll i = n - 1; i >= 0; --i) {
    sum += s[i];
    if (sum & 1) {
      ans += oddCnt;
      oddCnt++;
    } else {
      ans += evenCnt;
      sumEven[i] = true;
      evenCnt++;
    }
  }

  for (ll i = 0; i < n; ++i) {
    ll sumx = 0, maxi = 0;
    for (ll j = i; j < min(n, i + 64LL); ++j) {
      if (s[j] > maxi) {
        sumx += maxi;
        maxi = s[j];
      } else {
        sumx += s[j];
      }
      if (sumx < maxi && sumEven[i] == sumEven[j + 1]) {
        ans--;
      }
    }
  }

  cout << ans;
  return 0;
}

GCC Magic

看了出题人大佬的题解才知道GCC有一个魔法函数__builtin_popcountll(unsigned)。其功能是计算无符号数的二进制表达式中1的个数。这个函数使用了分块查表的方法,跑得非常快!

NowCoder 202F – 平衡二叉树 (贪心+递归)

题意

平衡二叉树的参数$d$表示每个节点两子树高度差不超过$d$。求高度为$n$的所有平衡二叉树中左右子树节点数差的最大值。

思路

一开始以为只要左边全满右边一条链就搞定了然后快乐WA

思考后发现右边的所有节点也要满足高度差$\le d$的条件。所以只要左边是满二叉树右边是满足平衡条件的最小二叉树就可以了。

最小二叉树节点数可用递归求出,$$C_h = C_{h-1} + 1 + C_{h-1-d}$$

然后TLE了(内心OS:出题人一定是清华的,又红又橙的题,还是树)

用记忆化搜索还因为垃圾代码越界WA找了半天……

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mt[100] = {};
ll mintree(int h, int d) {
  if (h <= 0) return 0;
  if (mt[h] >= 0) return mt[h];
  else if (h == 1) return 1;
  else return mt[h] = mintree(h - 1, d) + mintree(h - 1 - d, d) + 1;
}

int main() {
  memset(mt, -1, sizeof(mt));
  int n = 0, d = 0;
  ll ans = 0;
  scanf("%d%d", &n, &d);
  if (n == 0) {
    ans = 0;
  } else {
    ans = (1LL << (n - 1)) - 1 - mintree(n - 1 - d, d);
  }
  printf("%lld", ans);
}

HDU 6395 – Sequence (分块+快速幂)

题意

计算$F_n \mod 10^9+7$,定义如下:$$\begin{cases} F_1 &=& A \\ F_2 &=& B \\ F_n &=& C\cdot{}F_{n-2}+D\cdot{}F_{n-1}+\left\lfloor\frac{P}{n}\right\rfloor \end{cases}$$

数据范围

  • $1 \leq T \leq 20$
  • $0 \leq A, B, C, D \leq 10^9$
  • $1 \leq P, n \leq 10^9$

思路

这题太硬核了我脑子里只有$O(n)$的算法肯定跑不过嘛

如果$\left\lfloor\frac{P}{n}\right\rfloor$的值是固定的那么肯定可以快速幂解决了,但是难就难在这个值会随着$n$变化。聪明的徐臣发现了当$n$很大的时候,这个值几乎是不变的,有很长一段区间可以用快速幂解决。

那么$n$多大的时候这样计算才不会浪费呢?其实根本不会浪费因为快速幂肯定跑的快啊!

对于开始值$i$,这一段快速幂计算区间为$\left[ i, P / (P / i) \right]$(注意除法会消掉余数,所以右端点正好是保持$\lfloor\frac{P}{N}\rfloor$值不变的最大值)。用矩阵快速幂疯狂向前推就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;

class matrix{
 public:
  ll s[3][3];

  matrix(){
    memset(s, 0, sizeof(s));
  }
  matrix(ll Fn, ll Fn1, ll E) {
    s[0][0] = Fn;
    s[0][1] = Fn1;
    s[0][2] = E;
    s[1][0] = s[1][1] = s[1][2] = 0;
    s[2][0] = s[2][1] = s[2][2] = 0;
  }
  matrix(ll C, ll D) {
    s[0][0] = D;
    s[1][0] = C;
    s[0][1] = s[2][0] = s[2][2] = 1;
    s[0][2] = s[1][1] = s[1][2] = s[2][1] = 0;
  }
};

matrix mul(matrix &a, matrix &b) {
  matrix ret;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        ret.s[i][j] = (ret.s[i][j] + a.s[i][k] * b.s[k][j]) % modulo;
      }
    }
  }
  return ret;
}

ll A = 0, B = 0, C = 0, D = 0, P = 0, n = 0;

void xmul(ll &Fn, ll &Fn1, ll E, ll t) {
  matrix ret(Fn, Fn1, E);
  matrix b(C, D);
  while (t) {
    if (t & 1) {
      ret = mul(ret, b);
    }
    b = mul(b, b);
    t >>= 1;
  }
  Fn = ret.s[0][0];
  Fn1 = ret.s[0][1];
}

ll solve() {
  if (n == 1) return A;
  if (n == 2) return B;
  ll Fn1 = A, Fn = B, nex = 0, PN = 0;
  matrix res;
  for (ll i = 3; i <= n; ) {
    PN = P / i;
    if (PN == 0) {
      nex = n;
    } else {
      nex = min(n, P / PN);
    }
    xmul(Fn, Fn1, PN, nex - i + 1);
    i = nex + 1;
  }
  return Fn;
}

int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld%lld%lld", &A, &B, &C, &D, &P, &n);
    printf("%lld\n", solve());
  }
}

NowCoder 202A – 矩阵乘法 (分块)

呜呜呜这才第三道水题我就不会做了。

题意

给你$N \times P$和$P \times M$的两个矩阵A与B,其中B是二进制矩阵。求$A \times B$的所有元素的异或和。

数据范围

  • $2 \le N, M \le 2048$
  • $1 \le P \le 64$
  • $0 \le A_{ij} \le 65536$

思路

呜呜呜这数据范围这么大做屁啊!如果直接计算$C$的话需要$2^{48} $次运算怎么可能跑得过啊

想想异或运算有没有什么特别的,没有

STFW看看有没有什么快速算矩阵的方法,没有

群里问大佬,大佬说的听不懂,僵

然后Bing搜了个原题出来……

简单地说就是预处理这个矩阵来使得乘法运算的次数大幅度减少,那么在$O(NPM)$的复杂度下能够卡过去。怎么处理呢?考虑到$B$是一个二进制矩阵,$A_i$与$B_j$的相乘的结果代表$A_i$中对应列元素的和。如果直接预处理需要考虑$2^{64}$种和的情况,根本不行。

然后就可以用神奇的分块了,每$\sqrt{P} = 8$个$A_{ij}$分为一块,那么只需要处理$2^{10} \times 8 \times 2^8 = 2 \times 10^6$种和就可以了。对于每一个$C_{ij}$,只需要对对应的分块和进行至多8次加法即可求出。

总时间复杂度为$$O(N \times P \times2^8)+O(MP)+O(NM\sqrt{P})+O(NM).$$

代码

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

int n = 0, p = 0, m = 0, bk = 0;
int a[4200][70] = {};
int b[4200][70] = {};
int c[4200][4200] = {};
int apre[4200][10][260] = {};
int bpre[4200][10] = {};
char s[100] = {};

void pre() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < bk; ++j) {
      for (int k = 0; k < 256; ++k) {
        for (int p = 0; p < 8; ++p) {
          if ((k >> p) & 1) {
            apre[i][j][k] += a[i][(j << 3) + p];
          }
        }
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < bk; ++j) {
      for (int p = 0; p < 8; ++p) {
        bpre[i][j] += b[i][(j << 3) + p] << p;
      }
    }
  }
}

int getAns() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int p = 0; p < bk; ++p) {
        c[i][j] += apre[i][p][bpre[j][p]];
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j= 0; j < m; ++j) {
      ans ^= c[i][j];
    }
  }
  return ans;
}

int main() {
  scanf("%d%d%d", &n, &p, &m), bk = ((p - 1) >> 3) + 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < p; ++j) {
      scanf("%x", &a[i][j]);
    }
  }
  for (int i = 0; i < m; ++i) {
    scanf("%s", s);
    for (int j = 0; j < p; ++j) {
      b[i][j] = s[j] - '0';
    }
  }
  pre();
  printf("%d\n", getAns());
  return 0;
}