原题链接：https://ac.nowcoder.com/acm/contest/5675/I 题目描述 目前有n支队伍，每一对队伍共要进行场比赛，而每天可以安排一场比赛。对于每支队伍，它们将在各自需要比赛的第一天到达，并在各自比赛结束的一天离开。例如：当有三支队伍时，假如日程为（1,2），（1,3），（2,3），那么第一支队伍要在第1天到达，第2天离开，共停留2天，第二支队伍在第1天到达，第3天离开，共停留3天，第三支队伍在第2天到达，第3天离开，共停留2天。现在需要一张安排表，以确保每支队伍各自的停留时间尽可能少。 输入描述 第一行输入一个整数T，表示测试样例的数目；对于每个测试样例...

原题链接：https://ac.nowcoder.com/acm/contest/5675/D 题目描述 注意：本题中描述与真实战棋大不不同。xtq非常喜欢玩酒馆战棋，他注意到很多情况在后期下只有鱼人才能击败鱼人。所以他想知道如果他和对手都使用鱼人流，他什么时候才能获胜。为了简化该问题，规定现在只有四种鱼人： 1/10^9，带剧毒圣盾亡语； 1/10^9，带剧毒圣盾； 1/10^9，带剧毒亡语； 1/10^9，带剧毒。 （注：x/y表示x攻击力和y血量）攻击效果：当一个x_1/y_1的随从攻击一个x_2/y_2的随从（假定两者都没有圣盾和剧毒），则y_1变为y_1-x_2，y_2变为y...

原题链接：https://ac.nowcoder.com/acm/contest/5674/J 题目描述 某土拨鼠又双叒叕没做完作业，为了保全性命，他必须躲到教室里的桌子底下来躲避来自老师的毒打（滑稽）。教室里的桌子被排列成了的矩形。a[i][j]=1表示在(i,j)这个点有桌子。土拨鼠能藏身的矩阵符合以下三个标准： 该子矩形的四条边上没有空位； 子矩形中的空位数量与有桌子的位置的数量之差不超过1（不包括侧面的桌子）； 子矩形的长度和宽度必须大于1。问题来了，有多少子矩阵符合该要求这些要求。 输入描述 第一行输入两个整数n,m，分别表示矩形的长和宽；接下来输入一个的矩阵表示教室内的桌...

原题链接：https://ac.nowcoder.com/acm/contest/5674/E 题目描述 给定a,b,c,d,x,y的值，求 。 输入描述 输入6个整数a,b,c,d,x,y。 输出描述 输出一个整数作为答案。 数据范围 样例 样例1 输入 1 2 1 2 8 4输出 2048 样例2 输入 1 2 3 4 120 180输出 235140177 题解思路 看到本题数据范围，又看到连乘，盲猜可能要高精，但看到modulo，就可以想到边算边模可以避免使用高精。当然如果直接暴力还是会炸，所以要试着进行分解。但对于每个子问题，在幂次上，都形如：给出 ,求 。先来一长串...

原题链接：https://ac.nowcoder.com/acm/contest/5674/A 题目描述 某日，土拨鼠（Groundhog）在数学课上得知：任何正整数可以变成2的幂的形式以上为废话。输入表达式（字符串），并把字符串转化为原10进制形式。 输入描述 输入一行字符串，作为2的幂的形式，其中括号内的数或式为指数。 输出描述 输出一个整数作为结果。 数据范围 字符串长度不超过20000，原整数大小在 的范围内。 样例 输入 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) 输出 1315 题解思路 首先看数据范围可以猜到是应该...

原题链接：https://ac.nowcoder.com/acm/contest/5674/F 题目描述 土拨鼠（Groundhog）发现苹果（Apple）比以前对他更不亲近了。同时他发现他的打扮过时了。但土拨鼠过于懒惰，他只列出了接下来n天能穿的衣服。在第i天，他的第j件衣服的权值为 。在这n天里他要选择m天于苹果外出。但他想知道这m天里所穿衣服的权值的最大值与最小值的差的最小值。 输入描述 第一行输入两个整数n,m；接下来n行每行先输入一个整数k，再输入k个整数，分别表示衣服的权值。 输出描述 输出一个整数作为结果。 数据范围 衣服总量不超过 样例 输入 4 31 32...

原题链接：https://ac.nowcoder.com/acm/contest/5673/K 题目描述 Apollo开设了一家餐馆，该餐馆提供编号为1~n的n种食物，第i种食物的利润为，但食材原料价格可能过高，导致利润可能为负数。某一天，Apollo用第i种食材做了第道菜。Apollo将为顾客亲自送菜。在送菜过程中Apollo将遵循以下原则： 每位顾客至少得到一道菜； 每位顾客都应获得从第1种开始的连续种类编号的菜； 对于每位顾客，每道菜只能有一碟。 那么问题来了，Apollo的餐馆最多能容纳多少顾客?并且Apollo想知道，在容纳最多顾客时，最大利润为多少。 输入描述 第一行输入...

原题链接：https://ac.nowcoder.com/acm/contest/5673/I 题目描述 Apollo正在玩电脑游戏，该游戏共有n轮，Apollo共要玩T次。每一轮中，系统会给出两个整数 和 ，而Apollo每轮可以执行以下三个操作中的一个： 什么也不做； 如果在先前的操作中未选择 ，那么Apollo可以选择； 如果在先前的操作中未选择 ，那么Apollo可以选择。 由于Apollo已经破解了游戏（啊这，该操作可能导致其他玩家体验感降低），在游戏开始之前就知道了每轮给出的数是多少。现在Apollo想知道他可以选择的最多的整数的数量。 输入描述 第一行给出一个整数T，表...

原题链接：https://ac.nowcoder.com/acm/contest/5672/I 题目描述 定义无根树T的值为 ，其中V(T)是T的所有顶点的集合，而d(u)是T的度数。定义将森林的价值为森林中所有树的价值之和。求所有包含 N 个节点的森林的值的总和。答案对读入的M取模。 输入描述 第一行输入两个整数T,M,T表示测试样例的数量,M表示需取模的数；接下来T行每行输入一个整数N，表示森林共有N个节点。 输出描述 对于每个N输出一个对M取模的整数作为答案。 样例 输入5 10000000072345107 输出2242643240736935633 题解思路 首先，根据...

原题链接https://ac.nowcoder.com/acm/contest/5672/H 题目描述 定义一假传奇元组： （1，k）始终是传奇元组； 如果（n,k）是传奇元组，那么（n+k,k）和（n*k,k）也是传奇元组。 求当1≤n≤N，1≤k≤K时传奇元组的数量。输出的答案对 取模。 输入描述 输入两个整数N,K。 输出描述 输出一个对 取模的答案。 样例 样例1 输入 3 3输出 8 样例2 输入 3 9输出 14 题解思路 这道题看上去十分骇人，因为数据范围达到了前所未有的1e12，如果想手动模拟那是肯定不行的。如果你手动模拟了，就会发现，如果把传奇元组（n,k）...

原题链接https://ac.nowcoder.com/acm/contest/5666/B 题目描述 定义mindiv(n)表示n的大于1的最小因数。Bob用所有正整数构建了一棵无限大的树，每个正整数对应一个节点，对于所有大于1的n，在点n和点 间连边。定义δ(u,v)表示连接点u和点v的路径上的边的数量。给定m和 ，Bob想知道 。 输入描述 输入包含几个以文件结尾终止的测试样例。每个样例的第一行输入一个整数m；接下来的一行输入m个整数。 输出描述 每个样例输出一行整数作为答案。 样例 输入 31 1 143 1 2 440 0 0 0 输出 3170 题解思路 这道题目毛看...

原题链接：https://ac.nowcoder.com/acm/contest/5671/B 线性独立相关概念：https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E7%8B%AC%E7%AB%8B 题目描述 设A={0,1}，某无聊透顶的神每天从 （即维度为n，每一位由01组成的所有向量的集合）中随机选择一个二进制向量。现在他想知道n天中选取n个线性独立向量的概率。答案输出同该场比赛中有大Van题的有些许错误的A题相似。其中本题的模数为1e9+7。 输入描述 第一行输入一个T，表示测试样例的数目；接下来的T行每行输入一个数N。 输出描...

原题链接https://ac.nowcoder.com/acm/contest/5671/H 题目描述 设S(x)表示十进制表示下x的每位数字之和，当S（A）>S（B）时，(A,B)表示一个和谐对。给定N，求满足 的和谐对（A，B）的数量，答案对 取模。 输入描述 只有一行整数N（ ）。 输出描述 输出一个整数作为答案。 样例 输入100 输出967 题解思路 首先最吸引人眼球的应该是N的取值范围了，一看就会让人联想到高精度。想什么呢跟数字有关，当然是数位dp而非高精。作为数位DP，自然就有暴力枚举记忆化。根据题意，可以定义dp数组的维度[pos][A][B][l1...