NIRVANA

Problem

【POI2010】Bridges

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

$\mathrm{YYD}$为了减肥，来到了瘦海。
这是一个巨大的海，海中有$n$个小岛，小岛之间有$m$座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。
现在$\mathrm{YYD}$想骑单车从小岛$1$出发，骑过每一座桥，到达每一个小岛，然后回到小岛$1$。
霸中同学为了让$\mathrm{YYD}$减肥成功，召唤了大风，由于是海上风变得十分大，经过每一座桥都有不可避免的风阻碍$\mathrm{YYD}$，$\mathrm{YYD}$十分$\mathrm{ddt}$，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。

Input

第一行为两个用空格隔开的整数$n,m$。
接下来$m$行，每行为由空格隔开的$4$个整数$a,b,c,d$，第$i+1$行表示第$i$座桥连接小岛$a$和$b$，从$a$到$b$承受的风力为$c$，从$b$到$a$承受的风力为$d$。

Output

如果无法完成减肥计划，则输出NIE，否则第一行输出最大风力的最小值。

Problem

【SDOI2014】LIS

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

给定序列$A$，序列中的每一项$A_i$有删除代价$B_i$和附加属性$C_i$。
请删除若干项，使得$A$的最长上升子序列长度减少至少$1$，且付出的代价之和最小，并输出方案。
如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

Input

输入包含多组数据。
输入的第一行包含整数$T$，表示数据组数。
接下来$4\times T$行描述每组数据。
每组数据的第一行包含一个整数$N$，表示$A$的项数。
接下来三行，每行$N$个整数$A_1\sim A_n$，$B_1\sim B_n$，$C_1\sim C_n$。

Output

对每组数据，输出两行。
第一行包含两个整数$S,M$，依次表示删去项的代价和与数量；
接下来一行$M$个整数，表示删去项在$A$中的的位置，按升序输出。

Problem

Tower

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

$\mathrm{Nick}$最近在玩一款很好玩的游戏，游戏规则是这样的：
有一个$n\times m$的地图，地图上的每一个位置要么是空地，要么是炮塔，要么是一些$\mathrm{BETA}$狗，$\mathrm{Nick}$需要操纵炮塔攻击$\mathrm{BETA}$狗们。
攻击方法是：对于每个炮塔，游戏系统已经给出它可以瞄准的方向（上下左右其中一个），$\mathrm{Nick}$需要选择它的攻击位置，每一个炮塔只能够攻击一个位置，炮塔只能够向着它的瞄准方向上的某个位置发动攻击，当然炮塔也可以不进行攻击。炮塔威力强大，它可以且仅可以消灭目标位置上所有的$\mathrm{BETA}$狗。
出于安全考虑，游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔，即对于任意一个炮塔，它所有可能的攻击位置上不存在另外一个炮塔。而且，如果把炮塔的起点和终点称为炮弹的运行轨迹，那么系统不允许两条轨迹相交（包括起点和终点）。
现在，选定目标位置以后，每一个炮塔同时开炮，你要告诉$\mathrm{Nick}$，他最多可以干掉多少$\mathrm{BETA}$狗。

Input

第一行两个正整数$n,m$，表示地图的规模。
接下来礼行，每行$m$个整数，$0$表示空地，$-1,-2,-3,-4$分别表示瞄准上下左右的炮塔，若为正整数$p$，则表示该位置有$p$个$\mathrm{BETA}$狗。

Output

一个正整数，表示$\mathrm{Nick}$最多可以干掉几个$\mathrm{BETA}$狗

Problem

【PA2012】Tax

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给出一个$N$个点$M$条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点$1$到点$N$的最小代价。
起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。

Input

第一行两个整数$N,M$，表示图的点数和边数。
接下来$M$行，每行三个整数$u,v,c$，表示$u,v$间存在一条边权为$c$的无向边。

Output

输出一行一个整数，表示从$1$到$N$的最小代价。

Problem

【SHOI2017】相逢是问候

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

$\mathrm{B君}$希望以维护一个长度为$n$的数组，这个数组的下标为从$1$到$n$的正整数。
一共有$m$个操作，可以分为两种：

1. $0\;l\;r$：表示将第$l$个到第$r$个数($a_l,a_{l+1},\cdots,a_r$)中的每一个数$a_i$替换为$c^{a_i}$，其中$c$是一个常数
2. $1\;l\;r$：求第$l$个到第$r$个数的和，即$\sum_{i=l}^{r}a_i$

因为这个结果可能会很大，所以你只需要输出结果$\mod{p}$的值即可。

Input

第一行有三个整数$n,m,p,c$。
接下来一行$n$个整数，表示a数组的初始值。
接下来$m$行，每行三个整数，其中第一个整数表示了操作的类型。
如果是$0$，表示这是一个修改操作，操作的参数为$l,r$。
如果是$1$，表示这是一个询问操作，操作的参数为$l,r$。

Output

对于每个询问操作，输出一行，包括一个整数表示答案$\mod{p}$的值。

Problem

最大连通子块和

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给出一棵$n$个点，以$1$为根的有根树，点有点权。
要求支持如下两种操作：

1. $\mathrm{M}\;x\;y$：将点$x$的点权改为$y$
2. $\mathrm{Q}\;x$：求以$x$为根的子树的最大连通子块和

一棵子树的最大连通子块和指该子树所有子连通块的点权和中的最大值（本题中子连通块包括空连通块，点权和为$0$）。

Input

第一行两个整数$n$,$m$，表示树的点数以及操作的数目。
第二行$n$个整数，第$i$个整数$w_i$表示第$i$个点的点权。
接下来的$n-1$行，每行两个整数$x,y$，表示$x$和$y$之间有一条边相连。
接下来的$m$行，每行输入一个操作，含义如题目所述。
保证操作为$\mathrm{M}\;x\;y$或$\mathrm{Q}\;x$之一。

Output

对于每个$\mathrm{Q}$操作输出一行一个整数，表示询问子树的最大连通子块和。

Problem

【HNOI2011】数学作业

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

$\mathrm{小C}$数学成绩优异，于是老师给$\mathrm{小C}$留了一道非常难的数学作业题：
给定正整数$N$和$M$，要求计算$Concatenate(1\cdots N)\mod{M}$的值，其中$Concatenate(1\cdots N)$是将所有正整数$1,2,\cdots,N$顺序连接起来得到的数。
例如$N=13$，$Concatenate(1\cdots N)=12345678910111213$。
$\mathrm{小C}$想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

Input

只有一行且为用空格隔开的两个正整数$N$和$M$。

Output

仅包含一个非负整数，表示$Concatenate(1\cdots N)\mod{M}$的值。

Problem

【HNOI2012】永无乡

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

永无乡包含$n$座岛，编号从$1$到$n$，每座岛都有自己的独一无二的重要度，按照重要度可以将这$n$座岛排名，名次用$1$到$n$来表示。
某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛$a$出发经过若干座（含$0$座）桥可以到达岛$b$，则称岛$a$和岛$b$是连通的。
现在有两种操作：
$\mathrm{B}\;x\;y$：表示在岛$x$与岛$y$之间修建一座新桥。
$\mathrm{Q}\;x\;k$：表示询问当前与岛$x$连通的所有岛中第$k$重要的是哪座岛，即所有与岛$x$连通的岛中重要度排名第$k$小的岛是哪座，请你输出那个岛的编号。

Input

第一行是用空格隔开的两个正整数$n$和$m$，分别表示岛的个数以及一开始存在的桥数。
接下来的一行是用空格隔开的$n$个数，依次描述从岛$1$到岛$n$的重要度排名。
随后的$m$行每行是用空格隔开的两个正整数$a_i$和$b_i$，表示一开始就存在一座连接岛$a_i$和岛$b_i$的桥。
后面剩下的部分描述操作。
该部分的第一行是一个正整数$q$，表示一共有$q$个操作。
接下来的$q$行依次描述每个操作，操作的格式如上所述，以大写字母$\mathrm{Q}$或$\mathrm{B}$开始，后面跟两个不超过$n$的正整数，字母与数字以及两个数字之间用空格隔开。

Output

对于每个$\mathrm{Q}$操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。
如果该岛屿不存在，则输出$-1$。

Problem

【UR #5】怎样跑得更快

时间限制： $\mathrm{1\;Sec}$
空间限制： $\mathrm{256\;MB}$
大力水手问禅师：“大师，我觉得我光有力气是不够的。比如我吃菠菜可以让力气更大，但是却没有提升跑步的速度。请问怎样才能跑得更快？我试过吃白菜，没有效果。”
禅师浅笑，答：“方法很简单，不过若想我教你，你先看看这道$\mathrm{UOJ\;Round}$的$\mathrm{C}$题。”
令 $p=998244353$（$7\times 17\times 223+1$，一个质数）。
给你整数 $n,c,d$。现在有整数 $x_1,\cdots,x_n$ 和 $b_1,\cdots,b_n$ 满足 $0\le x_1,\cdots,x_n,b_1,\cdots,b_n<p$，且对于 $1\le i\le n$ 满足：

$$\sum_{j=1}^{n}\gcd(i,j)^c\cdot\mathrm{lcm}(i,j)^d\cdot x_j\equiv b_i\mod{p}$$

其中 $v\equiv u\mod{p}$ 表示 $v$ 和 $u$ 除以 $p$ 的余数相等。$\gcd(i,j)$ 表示 $i$ 和 $j$ 的最大公约数，$\mathrm{lcm}(i,j)$ 表示 $i$ 和 $j$ 的最小公倍数。
有 $q$ 个询问，每次给出 $b_1,\cdots,b_n$，请你解出 $x_1,\cdots,x_n$ 的值。

输入格式

第一行四个整数 $n,c,d,q$。保证 $n,q\ge1$。
接下来 $q$ 行，每行 $n$ 个整数依次表示 $b_1,\cdots,b_n$。保证 $0\le b_1,\cdots,b_n<p$。

输出格式

共 $q$ 行，每行对给出的 $b_1,\cdots,b_n$，输出对应的 $x_1,\cdots,x_n$。
如果有多组解输出任意一组即可。
如果无解那么这一行只用输出一个整数 $-1$。

Problem

排队

$\mathrm{Time\;Limit:\;4\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。
红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。
设第$i$个小朋友的身高为$h_i$，我们定义一个序列的杂乱程度为满足$i>j$且$h_i<h_j$的$(i,j)$数量。
幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。
为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

Input

第一行为一个正整数$n$，表示小朋友的数量。
第二行包含$n$个由空格分隔的正整数$h_1,h_2,\cdots,h_n$，依次表示初始队列中小朋友的身高。
第三行为一个正整数$m$，表示交换操作的次数。
以下$m$行每行包含两个正整数$a_i$和$b_i$，表示交换位置$a_i$与位置$b_i$的小朋友。

Output

输出文件共$m$行，第$i$行一个正整数表示交换操作$i$结束后，序列的杂乱程度。