Skip to content

Instantly share code, notes, and snippets.

@konjac
Last active April 8, 2019 21:45
Show Gist options
  • Save konjac/7064138 to your computer and use it in GitHub Desktop.
Save konjac/7064138 to your computer and use it in GitHub Desktop.
2013年 第38届ACM/ICPC国际大学生程序设计竞赛成都站,题目大意

A:好像是说,有一个n个点,m条边的无向图,边的权值分别是1, 2, ..., m。然后要你构造一个这样的无向图,使得任意一个环的权值和 是3的倍数。 10<=N<=80,N+3<=M<=N2/7

B:给一个HTML代码,要求格式化缩进后出。

C:p是(1,2,...,n)的一个排列,现在需要通过交换的方法进行排序,交换pi和pj的cost是2*abs(i-j)-1,记最少的cost为f(p),但现在有人用了个错误的方法g(p)来计算,g(p) = sum{ max(0, i-pi)}。现在假设已知p的前k<=n个数是多少,即p1, ...,pk已经固定,问有多少个p,满足f(p) = g(p),结果模109+7, n<=100

D:有n个点,m条边的有向图,边有耗时和花费。每个点有k个平行宇宙,你可以花1的时间进行跳跃。每个平行宇宙都可以买卖盐,你的背包最多能装b公斤的盐。问在t时间内走到起点终点,最多有多少钱。直接SPFA会TLE。

F:给一个无向图,边染了黑色或白色,问能否找到一个生成树,包含的白色边的条数一个Fibonacci数。点数、边数上限都是105

G:一个人背单词,每天可以有两种选择,一是新学一个单词;二是读一段文本,看看有多少个子串是学会了的单词。模拟这个过程。单词数和文本长度都不超过5*106

H:硬盘的容量,厂商和OS的计量是不一样的,厂商认为1k=1000,OS认为1k=1024,现在给你一个厂家计算用KB、MB、GB等表示的容量,计算一下以OS的算法差了多少

I:输入某场ACM比赛的判题情况,要求输出比赛结束时候封板时候的board(带pending),和解封board的过程(即World Final那种冒泡),和最终board。

J:随机选(x, y),a <= x <= b, c <= y <= d,使得(x + y) mod m == p,a, b, c, d, m, p <= 109,输出分数表示的概率

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment