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;
}
CCPC2018秦皇岛打铁记

CCPC2018秦皇岛打铁记

来到了石家庄、秦皇岛,为小朋友们做现场的表演。

秦皇岛真是一个疗养胜地。肯德基麦当劳必胜客饺子馆又贵又好吃,海边风景很不错(屁也没看到),比赛机壁纸挺好看的,第一次打铁也很好玩

Play

直接贴几张好看的照片得了

挺干净的(以及对面那家店真的不是拆腻斯大叔的店吗)
沙雕乐园
emmmmmmmmmmmmmmmm
我应该滚去种田

Contest

出题人在开幕式上说到,出的题目难度有梯度,然后就翻车翻的不要不要的了。

第一大水题

题意

给你一个区间时间$[L, R)$,问你在这个区间中有多少次时针和分针重合。

思路

好简单啊!$ans=R-L$。WA

如果经过了11点那么$ans=R-L-1$。WA

如果经过了23点那么也减一!WA

emmm……暴力穷举,AC。

第二大水题

题意

三种人对应三种颜色,对应的字符串是”XX is RBG.”三个人的句子cat之后去掉特殊字符,全部变成小写,随意插入小写字母,问你得到的字符串对应的原来的字典序最小的字符串是什么。

思路

暴力穷举所有可能的字符串(36种),一一匹配即可。因为没有排序WA了一发。

此时比赛开始只经过了一个小时不到。

第三大水题

题意

给你一棵无根树,问你能否给他一个根让它变成$k$-perfect的,即除了叶子节点以外所有的点都有相同的后代数,且每个叶子到根的距离相等。

思路

超 简 单 的
只要暴力比较度数找到唯一一个只出现了1次的度数就肯定是根了!度数+1的全都是内部节点,度数为1的全都是叶子!

然后WA了。

冷静思考后发现有可能是链,所以特判了一下,还是WA

找了半小时后找到了个神TM的反例

7
1 2
1 3
1 4
2 5
3 6
4 7

当时三个人一脸懵逼然后把朴素的暴力判断改成跑一遍DFS,交上去还是WA

然后经过一个多小时的撕逼之后聪明的徐臣发现$n=1$的时候TMD应该输出1,交上去TLE了

然后经过半个多小时的重写我们把DFS改成了BFS,交上去还是TLE

然后经过半个多小时的思考让BFS跑的超快,结果交上去100ms WA了

然后我们开始怀疑人生运用排列组合的知识改程序想反例但是交上去的全是WA和TLE

最后我们以-30+成功打铁(还好有队伍-82)

打铁感想

最后祝你,No response的原地爆炸当场去世,再见。
P.S. 不用PC^2用OJ还不给看已提交代码的我也当场去世了拜拜了您那

搞毛啊!怎么东西全没了!

发生啥事!怎么我最喜欢的沙雕博主的内容全没了!

由于JB Online太卡了,aunt决定把他的博客从JB Online的服务器里剥离出来,结果备份的东西没法一键恢复了……

于是呢……我准备重新开一个博客……
然后也不用嘤语了233333
(更沙雕了!)

现在我给wp配了markdown和2FA,简直太爽了!
(杠精肯定要说你Markdown没大写了)

可是问题又来了,Markdown没法居中啊(现在已经想办法搞好了)
那就这样吧懒得搞了
以前的内容我尽量补回来(翻译)吧2333
说完这句话aunt就摸鱼去了