You are now in a big factory. The factory could be recognized as a graph with n vertices and m edges. Every edge has its length. You have k missions to do. The i-th mission is going to vertex $a_i$ , picking a block and then sending it to vertex $b_i$ . You should complete the missions in the order from 1-st to k-th. Initially you are standing at vectex 1.
You have a gun in your hand. When you are at some vertex u, you could shoot the gun at the ground, and then a portal will be built at vertex u. When there are two portals in the factory, assuming they are at u and v, you could transfer between u and v with no cost(just like an edge connecting u and v with length 0).
You also have a remote controller in your hand. It allows you to close a portal whenever you want and wherever you are(closing one portal at a time, not all portals at the same time). What’s more, there could be at most two existing portals. So if you want to create another portal when there exists two, you must use your controller to close one before you create.
You need to find the minimum distance you have to walk in order to complete all k missions.
Mr. W got a new graph with N vertices and N - 1 edges. It’s a connected graph without cycles. Each edge should have an ugly value. To make the graph more beautiful, Mr. W hope you can help him modify it. You can delete or add one edge with an ugly value at a time and you can do it as many times as you want. But the following conditions should be satisfied at any time:
The graph is connected.
For each cycles in the graph, the XOR sum of all ugly values in the cycle is 0.
Mr. W wants to know the minimum sum of ugly values of all edges in the graph.
Mr. W is writing sequences. If he writes two positive integer sequences A and B with length K which satify $\sum_{i = 1}^{K} a_i = N ,\ \ \ \sum_{i = 1}^{K} b_i = M$, he will get $P = \prod_{i=1}^K min(a_i, b_i)$ points. You want to know the sum of total points he can get in all possible sequences he can write.
Inaka composes music. Today’s arrangement includes a chord of nn notes that are pairwise distinct, represented by a permutation $p_{1 \dots n}$ of integers from $1$ to $n$ (inclusive) denoting the notes from the lowest to the highest.
Her friend, Miyako, sneaks in and plays a trick by altering the chord with the following two operations:
Drop-2: Take out the second highest note and move it to the lowest position, i.e. change the permutation to $p_{n-1}, p_1, p_2, \dots, p_{n-3}, p_{n-2}, p_n$.
Invert: Take out the lowest note and move it to the highest position, i.e. change the permutation to $p_2, p_3, \dots, p_{n-1}, p_n, p_1$.
Any number of consecutive Drop-2 operations is considered a multi-drop. Miyako would like to change the permutation to an ordered permutation, $1, 2, \dots, n$,in the fewest number of multi-drops possible. Please help her find the number of multi-drops needed.
from collections import Counter import functools defdfs(x): global vst,cnt,a #vst[x] = True #Size[cnt] += 1 while (not vst[x]): vst[x] = True Size[cnt] += 1 x = a[x] #if (not vst[a[x]]): # dfs(a[x]) n = int(input()) a = [int(0)] + list(map(int,input().split())) Size = [int(0)] * (n + 1) vst = [False] * (n + 1) cnt = int(0) #线性筛 begin pri_pre = [int(0)] * (n + 1) primes = [] pri = [int(0)] * (n + 1) pri[1] = True for i in range(2,n+1): ifnot pri[i]: primes.append(i) for p in primes: if i * p > n: break pri[i*p] = True pri_pre[i*p] = p if i % p == 0: break #线性筛 end for i in range(1,n+1): if (not vst[i]): cnt += 1 dfs(i) ans = [] for i in range(1,cnt+1): cur = Size[i] cur_cnt = Counter() while (pri_pre[cur] != 0): cur_cnt[pri_pre[cur]] += 1 cur //= pri_pre[cur] if cur > 1: cur_cnt[cur] += 1 if (len(cur_cnt)): ans.append(cur_cnt) defcmp(x,y): return len(y) - len(x) ans = sorted(ans,key=functools.cmp_to_key(cmp)) merge_ans = Counter() for x in ans: merge_ans |= x result = 1 for p,pp in merge_ans.items(): result *= p ** pp print(result)
F.DPS
题目描述
When you are playing multiplayer games, you may want to show that you are the MVP of your team — or blame the one always wandering and watching away from the storm center. Well, there’re statistics that show you preformance, but sometimes numbers speak softer than charts. Now, you’re hired to write a program that output ASCII art histograms showing damage dealt to enemies. There are n players in the game. Given that the i-th player dealt $d_i$ damage to enemies where $\max_i d_i > 0$ is granted, you need to calculate the number $s_i$ of spaces in the bar by the following foluma: $s_i = \lceil 50 \frac {d_i} {\max_i d_i} \rceil$ Instead of formal definition of bar description, we will give an example. For some player i whose $s_i = 7$ and $d_i = 777$, the bar is shown as:
1 2 3
+-------+ | |777 +-------+
Moreover, you have to mark the player with maximal damage dealt to enemies by replacing the last space into ‘*’. If there’re multiple maximum, mark all of them. See samples for more ideas.
Mr. W have a sequence A with length N. $F(l,r) = A_l\&A_{l+1}\&…\&A_r$ Set $S(l,r) = \{ F(a,b)\ | min(l, r)\leq a \leq b \leq max(l, r) \}$ Mr.W makes Q queries. For each query he wants to know the size of S(L,R) for given L, R. L, R will not be given directly. He will give you L’ and R’. $L = (L’ \oplus lastans) \% N + 1$ $R = (R’ \oplus lastans) \% N + 1$ $\oplus$ means XOR. Lastans donates the answer of last query. It’s zero at the beginning.
