南京游记——南大我来哩!

转眼间,就到了十月份了,来南大也一个月了,来记录一下这一个月的所见所闻吧!

夫子庙

↑好多风铃的思贤庄

总统府

南京大学(仙林校区)

↑三只小蓝鲸

↑地科在计科旁边,暗示了什么XD?

我觉得计科的板子应该那么写

↑吕建校长讲话

南京大学(鼓楼校区)

↑居然还有个广州路门,异常亲切。后来才发现这应该是鼓楼校区扩张后新弄的门

↑真正的正门

↑大礼堂

↑北大楼

百团大[……]

继续阅读

GDOI2018退役祭

告辞,正式AFO

D0

和老师一起住,看起了港剧《盲侠大律师》,还挺好看的

随便看了看模板

什么?!毒奶老师狠狠给我奶了一口“这次能进前十”??要GG

D1

有点困,不过不成大碍

T1大水题,15min秒AC(flag)

T2 dp乱搞,样例都没过居然能有30’???

T3一直纠结如何树上操作,没把条件全部列出来,原来是个三位偏序,GG

T4概率期望?直接无视……

 

午休继续跟老师看港剧

收到成绩回来,GG,洛谷打卡,凶

打了几局R6,手感反倒不错

继续看港剧

夜宵点了份M记外卖[……]

继续阅读

【模板】左偏树(可并堆)

题目描述

如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:

操作1: 1 x y 将第x个数和第y个数所在的小根堆合并(若第x或第y个数已经被删除或第x和第y个数在用一个堆内,则无视此操作)

操作2: 2 x 输出第x个数所在的堆最小数,并将其删除(若第x个数已经被删除,则输出-1并无视删除操作)

输入输出格式

输入格式:

第一行包含两个正整数N、M,分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数,其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数,表示一条操作,格式如下[……]

继续阅读

【模板】Link Cut Tree (动态树)

题目背景

动态树

题目描述

给定n个点以及每个点的权值,要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1:后接两个整数(x,y),代表连接x到y,若x到y已经联通则无需连接。

2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。

3:后接两个整数(x,y),代表将点x上的权值变成y。

输入输出格式

输入格式:

第1行两个整数,分别为n和m,代表点数和操作数。

第2行到第n+1行,每行一个整数,整数在[1,[……]

继续阅读

[AHOI2009]中国象棋

题目描述

这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!

输入输出格式

输入格式:

一行包含两个整数N,M,之间由一个空格隔开。

输出格式:

总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。

输入输出样例

输入样例#1: 复制
[crayon-5dada06ec7295680265[……]

继续阅读

【模板】后缀自动机

题目描述

给定一个只包含小写字母的字符串 S ,

请你求出 S 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。

输入输出格式

输入格式:

一行一个仅包含小写字母的字符串 S

输出格式:

一个整数,为 所求答案

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

对于 10% 的数据, |S|<=1000

对于 100% 的数据, |S|<=10^6[……]

继续阅读

【模板】二逼平衡树(树套树)

题目描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

  1. 查询k在区间内的排名
  2. 查询区间内排名为k的值
  3. 修改某一位值上的数值
  4. 查询k在区间内的前驱(前驱定义为严格小于x,且最大的数,若不存在输出-2147483647)
  5. 查询k在区间内的后继(后继定义为严格大于x,且最小的数,若不存在输出2147483647)

注意上面两条要求和tyvj或者bzoj不一样,请注意

输入输出格式

输入格式:

第一行两个数 n,m 表示长度为n的有序序列和m个操作

第二行有n个数,表示有序序列

下面有m行,opt表示[……]

继续阅读

Dynamic Rankings

题目描述

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。

对于每一个询问指令,你必须输出正确的回答。

输入输出格式

输入格式:

第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。

第二行有[……]

继续阅读

【模板】后缀排序

题目背景

这是一道模板题。

题目描述

读入一个长度为 n 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n 。

输入输出格式

输入格式:

一行一个长度为 n 的仅包含大小写英文字母或数字的字符串。

输出格式:

一行,共n个整数,表示答案。

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

[……]

继续阅读