BearChild's Blog

Dynamic Rankings Time Limit: 10 Sec Memory Limit: 128 MB Description 给定一个含有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，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 Input 第一行有两个正整数 　　分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]。 　　接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 　　Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。 　　C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。 Output 对于每一次询 ...

排列计数 Time Limit: 60 Sec Memory Limit: 128 MB Description 求有多少种长度为 n 的序列 A，满足以下条件： 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多，序列数对 10^9+7 取模。 Input 第一行一个数 T，表示有 T 组数据。 接下来 T 行，每行两个整数 n、m。 Output 输出 T 行，每行一个数，表示求出的序列数 Sample Input 5 　1 0 　1 1 　5 2 　100 50 　10000 5000 Sample Output 0 　1 　20 　578028887 　60695423 HINT T=500000，n≤1000000，m≤1000000 Main idea 求所有排列中恰好有m个 a[i]=i 的个数。 Solution 直接运用组合数和错排公式上一波即可。 Code 12345678910111213141516171819202122232425262728293031 ...

Meteors Time Limit: 60 Sec Memory Limit: 128 MB Description 这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。 　　BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。 Input 第一行是两个数N,M。 　　第二行有M个数，第i个数Oi表示第i段轨道上有第Oi个国家的太空站。 　　第三行有N个数，第i个数Pi表示第i个国家希望收集的陨石数量。 　　第四行有一个数K，表示BIU预测了接下来的K场陨石雨。 　　接下来K行，每行有三个数Li,Ri,Ai，表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中（如果Li<=Ri，就是Li,Li+1,…,Ri，否则就是Ri,Ri+1,…,m-1,m,1,…,Li），向区间中的每个太空站提供Ai单位的陨石样本。 Output 输出N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到，输出NIE。 Sample Input 3 5 　1 3 ...

矩阵乘法 Time Limit: 20 Sec Memory Limit: 256 MB Description 给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。 Input 第一行两个数N,Q，表示矩阵大小和询问组数； 　接下来N行N列一共N*N个数，表示这个矩阵； 　再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。 Output 对于每组询问输出第K小的数。 Sample Input 2 2 　2 1 　3 4 　1 2 1 2 1 　1 1 2 2 3 Sample Output 1 　3 HINT 矩阵中数字是10^9以内的非负整数； 　20%的数据：N<=100,Q<=1000； 　　40%的数据：N<=300,Q<=10000； 　60%的数据：N<=400,Q<=30000； 　100%的数据：N<=500,Q<=60000。 Solution 由于只有询问，我们可以方便地使用整体二分来求解。 先将原矩阵以序 ...

序列分割 Time Limit: 40 Sec Memory Limit: 128 MB Description 小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤： 1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）； 2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。 每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。 Input 输入第一行包含两个整数n，k（k+1≤n）。 　　第二行包含n个非负整数a1，a2，…，an（0≤ai≤10^4），表示一开始小H得到的序列。 Output 输出第一行包含一个整数，为小H可以得到的最大分数。 Sample Input 7 3 　4 1 3 4 0 2 3 Sample Output 108 在样例中，小H可以通过如下3轮操作得到108分： 　　1．开始小H有一 ...

修路 Time Limit: 20 Sec Memory Limit: 256 MB Description 村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 G = (V, E)， 请选择一些边，使得1 <= i <= d， i号节点和 n - i + 1 号节点可以通过选中的边连通，最小化选中的所有边 的权值和。 Input 第一行两个整数 n, m，表示图的点数和边数。接下来的 m行，每行三个整数 ui, vi, wi，表示有一条 ui 与 vi 之间，权值为 wi 的无向边。 Output 仅一行一个整数表示答案。 Sample Input 5 5 2 　　1 3 4 　　3 5 2 　　2 3 1 　　3 4 4 　　2 4 3 Sample Output 9 HINT 1 <= d <= 4 2d <= n <= 10^4 0 <= m <= 10^4 1 <= ui, vi <= n 1 <= wi <= 1000 Main idea 给定若干对点，选择若干边，询 ...

网络管理 Time Limit: 50 Sec Memory Limit: 162 MB Description M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。 　　为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。 　　该网络的结构由N个路由器和N-1条高速光缆组成。 　　每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。 　　该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 　　高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。 　　但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。 　　而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。 　　作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。 　　该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟 ...

Aeroplane chess Time Limit: 1 Sec Memory Limit: 32 MB Description Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). When Hzz is at grid i and the dice number is x, he will moves to grid i+x. Hzz finishes the game when i+x is equal to or greater than N. There are also M flight lines on the chess ma ...

LOOPS Time Limit: 5 Sec Memory Limit: 64 MB Description Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl). 　　Homura wants to help her friend Madoka save the world. But because of the plot of the Boss Incubator, she is trapped in a labyrinth called LOOPS. The planform of the LOOPS is a rectangle of R*C grids. There is a portal in each grid except the exit grid. It costs Homura 2 magic power to use a portal once. The portal in a grid G(r, c) will send Homura to the grid below G (grid(r+ ...

Easy Time Limit: 10 Sec Memory Limit: 128 MB Description 某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:( 　我们来简化一下这个游戏的规则 　有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有aa分，comb就是极大的连续o。 　比如ooxxxxooooxxx，分数就是22+4*4=4+16=20。 　Sevenkplus闲的慌就看他打了一盘，有些地方跟运气无关要么是o要么是x，有些地方o或者x各有50%的可能性，用?号来表示。 　比如oo?xx就是一个可能的输入。 　那么WJMZBMR这场osu的期望得分是多少呢？ 　比如oo?xx的话，?是o的话就是oooxx => 9，是x的话就是ooxxx => 4 　期望自然就是(4+9)/2 =6.5了 Input 第一行一个整数n，表示点击的个数 　接下来一个字符串，每个字符都是ox？中的一个 Output 一行一个浮点数表示答案 　四舍五入到小数点后4位 　如果害怕精度跪建议用long double或者ex ...