Problem
告訴你那些是同義詞，以及誰與誰是反義詞，最後回報是否有矛盾情況。
Sample Output
|
|
Sample Input
|
|
Solution
對於每個詞建立兩個節點 (正反兩種意思的節點)，同義詞則對兩個正做連接，只需要對建造反義祠的時候檢查，查詢每次是否會落在相同集合的操作。
|
|
UVa 11851 - Celebrity Split
Problem
家產劃分給兩個人，兩個人分配的房子總價值必須相同，剩下無法劃分的房子將換成現金分配給兩個人，求換成現金的總額最小為何？
Sample Input
|
|
Output for Sample Input
|
|
Solution
窮舉分配情況，並且試圖將後期分配肯定會失敗的情況剪掉。
|
|
UVa 11848 - Cargo Trains
Problem
在 N 個點的地圖中，有兩家運輸公司 A, B，如果它們都有在 x, y 之間部屬線路，則運輸費用將會根據參數 a 進行調整 a * Ca + (1 - a) * Cb，求從編號 0 到 N-1 的最少花費為何。
Sample input
|
|
Sample Output
|
|
Solution
每一次詢問 a 的時候，就做一次 spfa。似乎沒有別的方法可以預處理訊息。
|
|
UVa 11844 - The Melding Plague
Problem
給定每一個蛋白質在下一個時刻會變成什麼，從一開始的各種蛋白質類型的數量，是否會在哪一個時刻符合目標蛋白質種類的數量。
Sample Input
|
|
Sample Output
|
|
Solution
檢查是否有蛋白質轉換的模稜兩可情況，之後模擬出下一個時刻的蛋白質情況。
|
|
UVa 11828 - Palindrome Again
Problem
You are given a string S of length N. Can you find a string P which satisfies the following conditions?
Length of P will be N
Distance between S and P will be less than or equal to K
P will be a palindrome.
P can contain only characters ‘a’, ‘b’, …, ‘z’
You have to calculate, in how many ways you can choose P. This number can be very large, so print the answer modulo 1000000000 (109).
Notes:
A string is a sequence of characters. For this problem consider that all strings can contain only ‘a’, ‘b’, …, ‘z’, i.e. 26 available characters.
The length of the string is defined by the number of characters in the string. For example, length of “abcba” is 5.
A string is called palindrome when it is the same string when written from forwards or backwards. For example – “abcba”, “abba”, “a” are palindrome but “abc” is not a palindrome.
Distance between two string of same length is the number of mismatches of corresponding characters. For example, distance between “abcb” and “bcba” is 4 because no character of first string matches to the character of the corresponding index of second string, but distance between “abc” and “cba” is 2.
Input
Input starts with an integer T (T is around 5000), the number of test cases.
Each test case consists of two lines. First line contains two integers N(1≤N≤1000) and K (0≤K≤1000). Second line contains a string S of length N. S contains only characters from ‘a’, ‘b’, …, ‘z’.
Output
For each test case output the number of test cases followed by the number of ways the string can be chosen modulo 1000000000 (109). See sample output for exact format.
Sample Input
|
|
Output for Sample Input
|
|
Solution
題目描述：
對一個 S 字串，修改最多 K 個字符的情況下，求最多有多少不同的字符串是迴文
題目解法：
最樸素的算法，對於每個字串 S，使用 O(NK) 的算法，利用 dp[N][K] 表示對於前綴長為 N，已經修改了 K 個字符的總數為何。
先來看最樸素的寫法，一定會拿 TLE，原因是詢問的次數過多。1234567891011121314151617181920212223242526272829303132333435363738394041424344// TLEusing namespace std;int main() { int testcase, cases = 0, N, K; char s[1024]; long long dp[2][1024]; long long mod = 1000000000LL; scanf("%d", &testcase); while(testcase--) { scanf("%d %d %s", &N, &K, s); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; int froll = 0, L = N/2 + N%2; for(int i = 0; i < N; i++) s[i] = tolower(s[i]); for(int i = 0; i < L; i++) { memset(dp[!froll], 0, sizeof(dp[!froll])); int diff, cos; diff = s[i] == s[N - i - 1] ? 0 : 1; cos = i == N - i - 1 ? 1 : 2; for(int j = 0; j <= K; j++) { if(diff) { dp[!froll][j + 2] += dp[froll][j] * 24; dp[!froll][j + 1] += dp[froll][j] * 2; } else { dp[!froll][j + cos] += dp[froll][j] * 25; // using diff dp[!froll][j] += dp[froll][j]; } dp[!froll][j] %= mod; } froll = !froll; } long long ret = 0; for(int i = 0; i <= K; i++) ret = (ret + dp[froll][i])%mod; printf("Case %d: %lld\n", ++cases, ret); } return 0;}
之後，仔細拆解之後，發現由於只會考慮字串的一半，並且條件分為兩種，原本就已經匹配還是沒有匹配，而事實上我們可以分成 P, Q 兩種形式。
- P = number of characters where a[i] = a[n-i-1];
- Q = number of characters where a[i] != a[n-i-1];
所以考慮預先建表，將這兩個事件獨立分開計算，最後乘積起來就可以了。
對於 P, Q 的情況，分別建立 dp(i, j) 為目前 i 個字符，恰好修改 j 次的迴文字串數量。但是題目要求為 最多修改 K 次，因此對 P, Q 其中一種進行調整為 dp(i, j) 為目前 i 個字符，修改最多 j 次的回文字串數量。
因此對於每次詢問，可以在 O(N) 時間內完成。
|
|
UVa 11802 - All Your Bases Belong to Us
It is very easy to find number of trailing zero in n! for a particular base b. In this problem you have to do the reverse. You have to find for how many bases b, n! has k trailing zeros in base b.
Input
Input starts with a positive number T≤10000, denoting the number of test cases to follow.
Each test case contains two non-negative integers, n≤1015 and 1≤k≤1015 in a line. You may assume and n/k<500.
Output
For each input output one line containing the number of different bases. Print the solution modulo 1000000007
Sample Input
|
|
Sample Output
|
|
Solution
題目描述：
對於 n! 的 b 進制數中，尾數恰好為 k 個 0 情況為何？
題目解法：
質因數分解，找到每一個質數的次方數，根據數學組合和排容原理得到，大於等於 k 個 0 的基底情況個數為何，因此
對於 2^n1 * 3^n2 * 5^n3 * 7^n4 ... = n!，
base = pi^mi * ...，保證 (pi^mi)^k => mi * k <= ni。計算 mi (0, 1, …, ni/k)的可能情況總數乘積即可。
最後用排容原理吧！
|
|
UVa 11785 - Hypercube
Problem
In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3). It consists in groups of opposite parallel line segments aligned in each of the space’s dimensions, at right angles to each other and of the same length. An n-dimensional hypercube is also called an n-cube.
\epsfbox{p11785.eps}
In parallel computing, the vertexes are processors, and the line segments (edges) represent connections. The n-cube architecture has the following properties:
- Each node has n connections with different processors.
- Each processor has a unique identifier, between 0 and 2n - 1.
- Two processors are directly connected if and only if their identifiers differ in just one bit. For instance, in a 3-cube, processors 3 (011 in binary) and 7 (111 in binary) are directly connected.
- The number of processors is 2n
The new company WEFAIL is designing hypercubes, but they are always contracting new people, whose do not know all the hypercube properties, and sometimes they fail; thus these properties are not satisfied in all cases. Given an arbitrary graph, your task is to write a program that determines whether the graph is a hypercube or not.
Input
The input consists in several problem instances. Each instance contains one graph, which starts with a line with two positive integers: K and M, representing the number of vertexes ( 0 < K$\le$1024) and the number of edges respectively. It follows ( 0$\le$M$\le$5130) lines, representing the edges. Each edge is given by two 32 bits integers, representing the processors connected by the edge.
The end of input is indicated by a test case with K = 0.
Output
For each problem instance, the output is a single line, with the word YES if the corresponding graph is a hypercube, and NO otherwise (quotes for clarity). The output must be written to standard output.
Sample Input
|
|
Sample Output
|
|
Solution
題目描述：
判斷是否與超立方體同構
題目解法：
原本使用貪心的映射方式，然後進行超立方體的判斷，但是這樣的條件不好撰寫，其中肯定有 BUG。
最後使用全局最短路總和會相同的方式，還真是各種邪惡的題目。然而題目假使會有超出節點的編號，直接忽略報錯即可。
|
|
UVa 11766 - Racing Car Computer
Problem
The racing cars of today are equipped with so many sophisticated equipment. Introduction of a new visual transducer which is interfaced with the on-board computer can tell you on the fly how many cars are ahead of you while how many are trailing. There are N cars on a racing track. Each has an on-board computer with the new feature. During the race, every single car’s computer keeps displaying two integers, a (The number of cars in front of him) & b (The number of cars behind him) for a particular moment. It is possible that at some time, some of the cars are racing side by side i.e. they are exactly at the same location. A car will not consider any other car at the same location to be a leading or trailing car.
Now, it is suspected that some of the new transducers are not working properly inside such high speed vehicles. The report with all computers’ data generated at a particular timestamp is reported to you. You are to determine the minimum number of cars that have faulty data.
Input
Each test case begins with an integer N (1<=N<=1000), the number of cars on a track . The next N lines each has two integers - a & b (0<=a,b<=1500) for a particular car.
The last test case is followed by a line with a single 0 indicating the end of input.
Output
For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the minimum number of cars that must have faulty data according to the report.
Sample Input
|
|
Output for Sample Input
|
|
Solution
題目描述：
有n个人进行比赛，给出每个人的状况，a表示这个人前面有a个人，b表示说这个人后面有b个人。问说最少有多少个人的状态是不成立的。
題目解法：
將問題轉換成區間，來表示這個人可能所在的區間，假使前面有 a 個人，後面有 b 個人，則這個人可能所在為 [a+1, n-b]，我們允許區間內最高容量為 n - b - a (當作權重) 個人，求不相交區間的最大權重。
最後 n 扣除這個最大權重就是答案。
|
|
UVa 11765 - Component Placement
Problem
In circuit design, component placement is an important step in the design automation. Inferior placements may affect the performance and manufacturing cost.
You are given a PCB (Printed Circuit Board). It’s a large green board. You can place components on either side of the PCB. However, cost of placing a component on both sides are not the same. You are given N components. For each component ci, cost of placing it on the top layer is Xi and on the bottom layer is Yi.
These components may interact with each other. If both the components are on the same side of the PCB, the interconnection cost is negligible. But, if they are on different sides, their interconnection is costly. For each such interconnection j, the cost will be Zj.
Finally, some design issues restricts some components to be on the top side or bottom side. Now, find the minimum cost to place the components.
Input
First line contains a positive integer T (T<= 50) that denotes the number of test cases.
Each test case starts with 2 integers N (1 <= N <= 200) and M (0 <= M <= 100000, M <= N * (N-1) / 2), the number of components and number of interconnections. This will be followed by N integers in a line, each between 1 and 10000000 (inclusive), where i-th of it describes the cost of placing the component on the top layer. The next line contains N more integers, each between 1 and 10000000 (inclusive), where i-th of it denotes the cost of placing it on the bottom layer. The next line contains N more integers, each will be either 0, -1 or +1, where
-1means i-th component can only be placed on the bottom+1means i-th component can only be placed on the top0means the component can be placed on either side
Then there will be M lines, each containing three integers, p, q, and r (1 <= p, q <= N, 1 <= r <= 10000000), denoting that, p and q-th component has to be interconnected and if they are on different layers, the cost of interconnection will be r. There will be at most one interconnection between any pair or components.
Output
For each test case, output the minimum cost to place the components.
Sample Input
|
|
Output for Sample Input
|
|
Solution
題目描述：
有一些元件，設置在電路板上面時，要不放上面或者是放下面，放置的成本各有不同，假如兩個元件之間必須相連，則當他們放置在不同側的時候，會有額外的花費，如果放在同側則無需考慮。
求放置的最小成本。
題目解法：
利用最大流 = 最小割的方式，將不同側的成本反應在最小割上面。
|
|
UVa 11754 - Code Feat
題目描述：
找前 S 小的 M 符合取模結果存在於給定的集合。
題目解法：
對於取模結果窮舉，可以在 O(n)時間內利用中國餘式定理得到其最小解，但是如果窮舉情況太多，倒不如直接窮舉數字。
特別小心，M > 0 的條件，為了除去這個 bug，花了不少時間。
|
|