2019 杭师大校赛 游记(未完待续)

Day -1

第 1 次参加大学的校赛

第 2 次参加 ACM 比赛

有点小激动

复习了下数据结构和图论

Day 0

由于有了学车校赛的前车之鉴,知道了要带够足够的零食(能有效消磨时间和放松压力

在楼下便利店买了点水和零食上路了

签到后打了个上机赛

真是恶意满满

A 题 [1,10] 以内随机数

非酋交了好多发没过

B 题 给定两个圆的半径和圆心 求重叠面积

一眼可做题,三角函数乱搞即可

欸,奇怪,总共就三题怎么 B 题为止才占了试卷的 1/2

继续往下翻

C 题 三页的英文阅读

一眼不可读题

到的有点晚时间不够就去撸 B 去了

上机赛完后去体验了一发杭师大的食堂

不得不说 杭师大的小姐姐真是多 而且平均身材/颜值挺好的

配置还行 共两层

中午吃了一碗大排面和奶茶

本来想在食堂找找有没有认识的巨佬的

结果面基失败 一个都没发现

吃完后去和同学集合一起进考场

(未完待续)

「CodeVS 1391」伊吹萃香 - 分层图最短路

今天校内模拟赛的最后一题

没想到竟然很水

然后就 AK 了(逃

给定一个图

n个黑白点,m条有向边

每个节点初始有一个质量weight[i]

走过每一条边需要消耗一定量的体力以及1个单位的时间

由于黑白点的存在,走过每条路需要消耗的体力也就产生了变化,假设一条道路两端路口黑白洞的质量差为delta:

  1. 从白到黑,消耗的体力值减少delta,若该条路径消耗的体力值变为负数的话,取为0

  2. 从黑到白,消耗的体力值增加delta

  3. 同色,消耗的体力值无变化

每过1个单位时间,就把每个点的黑白颜色相反

可以选择在一个点上停留1个单位的时间,如果是白点,则不消耗体力,否则消耗cost[i]的体力

1 <= N <= 5e3

1 <= M <= 3e4

爬取GitHub上用于深度学习的“不可描述”图片数据集

冲冲冲

手冲战士在行动

刚打完CSGO(白给)后在刷GitHub时偶然看到

NSFW Data Scrapper

“用于训练图像分类器的数据集”

点进去仔细一看数据分类

  • porn
  • hentai
  • sexy
  • neutral
  • drawings

再点进去仔细一看,txt格式文件里约加起来约230000个URL

Changce

今天我就要让GitHub变成我的PornHub

看了看说明文档

只支持Linux,但是正所谓“折腾才是乐趣”

想用练练python

于是写了个Windows版本的

「Codeforces 620E」New Year Tree - DFS序 + 状态压缩 + 线段树

给定一棵以1为根的有根树,有n个点

每个节点初始有一个颜色c[i]。

有两种操作:

1 v c 将以v为根的子树中所有点颜色更改为c

2 v 查询以v为根的子树中的节点有多少种不同的颜色

1 <= n, m <= 4e5

「Luogu P4151」[WC2011]最大XOR和路径 - 线性基

给定一张无向带权图,有重边和自环

求从 1 走到 N 的路径最大异或和

水知乎时看到莫队的评论提到了这道题,遂来水了(逃

「Luogu P2624」[HNOI2008]明明的烦恼 - Prufer Sequence

给出标号为 1 到 N 的点,以及某些点最终的度数

允许在任意两点间连线,可产生多少棵度数满足要求的树?

`n \le 1000`

「Luogu P3672」小清新签到题 - DP

给定自然数`n,k,x`,你要求出第`k`小的长度为`n`的逆序对对数为`x`的1 ~ n的排列

`n \le 300, k \le 10^{13}`

拉格朗日插值法

给定`n`个点`(x_i,y_i)`来确定一个多项式并将`k`代入求值

对于这个问题我们可以用高斯消元法以`\mathcal{O}(n^3)`的时间复杂度进行求解

但是有一种`\mathcal{O}(n^2)`的方法,名为拉格朗日插值法

$$ f(x)=\sum_{i=1}^{n}y_i\prod_{i \ne j}{\frac{x-x_j}{x_i-x_j}} $$

学完FFT和NTT后来水一篇拉格朗日插值法的博客

这东西就跟FFT一样烦,DP转移式推着推着发现需要用到拉格朗日插值法

「Codeforces 739B」Alyona and a tree - 倍增 + 差分

给定一棵节点数为`n`的树

这棵树的根节点为`1`

这棵树有点权`val_i`和边权`dis_i`

定义`dist(u,v)`为从`u`到`v`的简单路径上的边权和

顶点`u`控制顶点`v`,当且仅当`v`在`u`的子树中且`dist(u,v) \le val_v`

求每个顶点`u`能控制几个顶点

`1 \le n \le 2 \times 10^5`

「Luogu P1306」斐波那契公约数 - 数论 + 矩阵加速

给定正整数 `n` 和 `m`

Fibonacci数列第 `n` 项和第 `m` 项的最大公因数

`n,m \le 10^9`

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×