a：2016
2016
given a 2×2 matrix
a=(a11a21a12a22),
find an where a1=a,an=a×an−1. as the result may be large, you are going to find only the remainder after division by 7.
special note: the problem is intended to be easy. feel free to think why the problem is called <code>2016</code> if you either:
find it hard to solve;
or, solved all the other problems easily.
the input contains at most 40 sets. for each set:
the first line contains an integer n (1≤n<10100000).
the second line contains 2 integers a11,a12.
the third line contains 2 integers a21,a22.
(0≤aij<7, (a11a22−a12a21) is not a multiple of 7)
for each set, a 2×2 matrix denotes the remainder of an after division by 7.
代碼
c ：
hamiltonian path
in icpccamp, there are n cities and m directed roads between cities. the i-th road going from the ai-th city to the bi-th city is ci kilometers long. for each pair of cities (u,v), there can be more than one roads from u to v.
bobo wants to make big news by solving the famous hamiltonian path problem. that is, he would like to visit all the n cities one by one so that the total distance travelled is minimized.
formally, bobo likes to find n distinct integers p1,p2,…,pn to minimize w(p1,p2)+w(p2,p3)+⋯+w(pn−1,pn) where w(x,y) is the length of road from the x-th city to the y-th city.
the input contains at most 30 sets. for each set:
the first line contains 2 integers n,m (2≤n≤105,0≤m≤105).
the i-th of the following m lines contains 3 integers ai,bi,ci (1≤ai<bi≤n,1≤ci≤104).
for each set, an integer denotes the minimum total distance. if there exists no plan, output <code>-1</code> instead.
d：
heartstone
bobo is playing heartstone. there are n minions in the battlefield. the i-th minion has hi hit points (hp).
bobo uses two kinds of magic. the one is arcane shot and the other is frostbolt. arcane shot can deal two points damage to a minion (that is to decrease the minion's hp by two), while frostbolt can deal three points damage. a minion is killed when its hp is less or equal to zero.
let f(a) be the minimum number of frostbolt(s) required to kill all minions, if no more than a arcane shot(s) are used. bobo would like to find out f(0)+f(1)+⋯+f(m) modulo (109+7).
the first line contains 2 integers n,m (1≤n≤105,0≤m≤105).
the second line contains n integers h1,h2,…,hn (1≤hi≤104).
for each set, an integer denotes f(0)+f(1)+⋯+f(m) modulo (109+7).
g：
rolling variance
bobo learnt that the variance of a sequence a1,a2,…,an is
∑ni=1(ai−a¯)2n−1−−−−−−−−−−−−√
where
a¯=∑ni=1ain.
bobo has a sequence a1,a2,…,an, and he would like to find the variance of each consecutive subsequences of length m. formally, the i-th (1≤i≤n−m+1) rolling variance ri is the variance of sequence {ai,ai+1,…,ai+m−1}.
the first line contains 2 integers n,m (2≤m≤n≤105).
the second line contains n integers a1,a2,…,an (|ai|≤100).
for each set, (n−m+1) lines with floating numbers r1,r2,…,rn−m+1.
your answer will be considered correct if its absolute or relative error does not exceed 10−4.
思路：字首和；
h：
super fast fourier transform
bobo has two sequences of integers {a1,a2,…,an} and {b1,b2,…,bm}. he would like to find
∑i=1n∑j=1m⌊|ai−bj|−−−−−−−√⌋.
note that ⌊x⌋ denotes the maximum integer does not exceed x, and |x| denotes the absolute value of x.
the first line contains 2 integers n,m (1≤n,m≤105).
the second line contains n integers a1,a2,…,an.
the thrid line contains m integers b1,b2,…,bm.
(ai,bi≥0,a1+a2+⋯+an,b1+b2+…,bm≤106)
for each set, an integer denotes the sum.
思路：不同的數最多1000個，c++11交；
j：
defense tower
in icpccamp, there are n cities and (n−1) (bidirectional) roads between cities. the i-th road is between the ai-th and bi-th cities. it is guaranteed that cities are connected.
in the i-th city, there is a defense tower with power pi. the tower protects all cities with a road directly connected to city i. however, the tower in city i does not protect city i itself.
bobo would like to destroy all defense towers. when he tries to destroy the tower in city i, any not-destroyed tower protecting city i will deal damage whose value equals to its power to bobo.
find out the minimum total damage bobo will receive if he chooses the order to destroy the towers optimally.
the first line contains an integer n (1≤n≤105).
the second line contains n integers p1,p2,…,pn (1≤pi≤104).
the i-th of the last (n−1) lines contains 2 integers ai,bi (1≤ai,bi≤n).
for each set, an integer denotes the minimum total damage.
思路，每次取小的；