Problem

【POI2010】Bridges

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

Description

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

Input

第一行为两个用空格隔开的整数n,mn,m
接下来mm行,每行为由空格隔开的44个整数a,b,c,da,b,c,d,第i+1i+1行表示第ii座桥连接小岛aabb,从aabb承受的风力为cc,从bbaa承受的风力为dd

Output

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

Read more »

Problem

【SDOI2014】LIS

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

Description

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

Input

输入包含多组数据。
输入的第一行包含整数TT,表示数据组数。
接下来4×T4\times T行描述每组数据。
每组数据的第一行包含一个整数NN,表示AA的项数。
接下来三行,每行NN个整数A1AnA_1\sim A_nB1BnB_1\sim B_nC1CnC_1\sim C_n

Output

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

Read more »

Problem

Tower

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

Description

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

Input

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

Output

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

Read more »

Problem

【PA2012】Tax

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

Description

给出一个NN个点MM条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点11到点NN的最小代价。
起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权。

Input

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

Output

输出一行一个整数,表示从11NN的最小代价。

Read more »

Problem

【SHOI2017】相逢是问候

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

Description

B\mathrm{B君}希望以维护一个长度为nn的数组,这个数组的下标为从11nn的正整数。
一共有mm个操作,可以分为两种:

  1. 0  l  r0\;l\;r:表示将第ll个到第rr个数(al,al+1,,ara_l,a_{l+1},\cdots,a_r)中的每一个数aia_i替换为caic^{a_i},其中cc是一个常数
  2. 1  l  r1\;l\;r:求第ll个到第rr个数的和,即i=lrai\sum_{i=l}^{r}a_i

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

Input

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

Output

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

Read more »

Problem

最大连通子块和

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

Description

给出一棵nn个点,以11为根的有根树,点有点权。
要求支持如下两种操作:

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

一棵子树的最大连通子块和指该子树所有子连通块的点权和中的最大值(本题中子连通块包括空连通块,点权和为00)。

Input

第一行两个整数nn,mm,表示树的点数以及操作的数目。
第二行nn个整数,第ii个整数wiw_i表示第ii个点的点权。
接下来的n1n-1行,每行两个整数x,yx,y,表示xxyy之间有一条边相连。
接下来的mm行,每行输入一个操作,含义如题目所述。
保证操作为M  x  y\mathrm{M}\;x\;yQ  x\mathrm{Q}\;x之一。

Output

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

Read more »

Problem

【HNOI2011】数学作业

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

Description

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

Input

只有一行且为用空格隔开的两个正整数NNMM

Output

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

Read more »

Problem

【HNOI2012】永无乡

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

Description

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

Input

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

Output

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

Read more »

Problem

【UR #5】怎样跑得更快

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

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

其中 vumodpv\equiv u\mod{p} 表示 vvuu 除以 pp 的余数相等。gcd(i,j)\gcd(i,j) 表示 iijj 的最大公约数,lcm(i,j)\mathrm{lcm}(i,j) 表示 iijj 的最小公倍数。
qq 个询问,每次给出 b1,,bnb_1,\cdots,b_n,请你解出 x1,,xnx_1,\cdots,x_n 的值。

输入格式

第一行四个整数 n,c,d,qn,c,d,q。保证 n,q1n,q\ge1
接下来 qq 行,每行 nn 个整数依次表示 b1,,bnb_1,\cdots,b_n。保证 0b1,,bn<p0\le b_1,\cdots,b_n<p

输出格式

qq 行,每行对给出的 b1,,bnb_1,\cdots,b_n,输出对应的 x1,,xnx_1,\cdots,x_n
如果有多组解输出任意一组即可。
如果无解那么这一行只用输出一个整数 1-1

Read more »

Problem

排队

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

Description

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

Input

第一行为一个正整数nn,表示小朋友的数量。
第二行包含nn个由空格分隔的正整数h1,h2,,hnh_1,h_2,\cdots,h_n,依次表示初始队列中小朋友的身高。
第三行为一个正整数mm,表示交换操作的次数。
以下mm行每行包含两个正整数aia_ibib_i,表示交换位置aia_i与位置bib_i的小朋友。

Output

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

Read more »