problem1 link

首先每$n*m$一定是一個循環，所以只需要考慮時間$[0,n*m-1]$即可。這個期間一共出現了$n$個，第i個的出現時間為$m*i$，離開的時間為$\left \lceil \frac{mi}{n} \right \rceil*n$，所有答案為:

ans=$\frac{\sum_{i=0}^{n-1}(\left \lceil \frac{mi}{n} \right \rceil*n-mi)}{n}$

=$\frac{n\sum_{i=0}^{n-1}\left \lceil \frac{mi}{n} \right \rceil-\sum_{i=0}^{n-1}mi}{n}$

=$\sum_{i=0}^{n-1}\left \lceil \frac{mi}{n} \right \rceil-\frac{(n-1)m}{2}$

設$A=\sum_{i=0}^{n-1}\left \lceil \frac{mi}{n} \right \rceil=\sum_{i=0}^{n-1}\left \lfloor \frac{mi}{n} \right \rfloor+n-X$?

其中$X$是那些$mi$正好是$n$的倍數因此不需要加1的個數。

現在的問題是計算$B=\sum_{i=0}^{n-1}\left \lfloor \frac{mi}{n} \right \rfloor$

它等于$\sum_{i=0}^{n-1}\left \lfloor \frac{mi}{n} \right \rfloor=\frac{(n-1)(m-1)}{2}-\frac{gcd(n,m)-1}{2}$

這個的證明在具體數學中文版第二版第77頁到第78頁。

problem2 link

首先將所有的前綴編號，預處理轉換表$T[id][k]$表示前綴id在輸入$k$時轉換到的狀態，其中$k$表示數字以及星號。

然后設$f[i][id]$表示當前“fix”部分為$word$的前$i$個，且"unfix"部分的標號為id的最小操作次數。然后進行dp即可。

problem3 link

首先，在$n*m$個一個pattern中(n為高度，m為寬度)，位置$(x_{1},y_{1})$到位置$(x_{2},y_{2})$的最短路徑可能會經過其他重復的pattern。可以證明，如果經過該patern上面的pattern，最多只需要考慮$\left \lceil \frac{m}{2} \right \rceil^{2}$個

假設每次進入上面一個pattern是進入是第$i$列，出來時是第$j$列，$i \ne j$。那么不會出現兩個pattern進入出來時的$i,j$一模一樣，否則可以省略中間的一些pattern。這樣考慮的話不同的$i,j$對有$\frac{m(m-1)}{2}$個，所以至多向上考慮這么多即可。

進一步考慮。將pattern的最后一行按照連續的空列分成若干組，那么很明顯最多有$\left \lceil \frac{m}{2} \right \rceil$組（每隔一個空列有一個障礙格子）。跟上面同樣的考慮方法，進入的組和出來的組不會有兩個pattern是完全一樣的，否則可以省略（因為一個組是聯通的）。所以向上最多需要考慮$\left \lceil \frac{m}{2} \right \rceil^{2}$個pattern即可。

這樣就可以處理出一個$m*m$的矩陣$A[i][j]$，表示從pattern的第一行的第 $i$ 列格子到達下一個pattern的第一行的第$j$列格子的最短路徑。

這樣的話，對于那么$r_{1},r_{2}$中間有很多pattern的情況，可以進行類似矩陣冪的優化。

?

code for problem1

import java.util.*; import java.math.*; import static java.lang.Math.*;public class Starport {public double getExpectedTime(int N, int M) {long t = (long)(N - 1) * M;long r = upper(N, M) - t / 2;if (t % 2 == 0) {return r;}return r - 0.5;}long upper(long n, long d) {if (n == 1) {return 0;}long nn = n / gcd(n, d);long p = (n - 1) / nn + 1;return lower(n, d) + n - p;}long gcd(long x, long y) {if (y == 0) {return x;}return gcd(y, x % y);}long lower(long n, long m) {return ((n - 1) * (m - 1) + gcd(n, m) - 1) / 2;}}

　　

code for problem2

import java.util.*; import java.math.*; import static java.lang.Math.*;public class QuickT9 {static int[] D = new int[]{3, 3, 3, 3, 3, 4, 3, 4};int prefixIndex = 0;Map<String, Integer> map = new HashMap<>(); //串對應編號Map<Integer, String> mapRev = new HashMap<>(); //編號對應串Map<String, List<String>> mapForNext = new HashMap<>(); //數字串對應的串Map<String, String> mapToDigit = new HashMap<>(); //串對應的數字串List<String> allWords = new ArrayList<>();String word;int[][] g = null;int[][] f = null;public int minimumPressings(String[] t9, String word) {init(t9);this.word = word;final int n = word.length();f = new int[n + 1][prefixIndex];for (int i = 0; i <= n; ++ i) {Arrays.fill(f[i], -1);}f[0][0] = 0;for (int i = 0; i < n; ++ i) {bfs(i);}return f[n][0];}Queue<Integer> queue = new LinkedList<>();boolean[] inq = null;void bfs(int len) {if (inq == null) {inq = new boolean[prefixIndex + 1];}if (f[len][0] != -1) {queue.offer(0);}while (!queue.isEmpty()) {int st = queue.poll();inq[st] = false;for (int i = 0; i < 11; ++ i) {if (i < 9) {int nxt = g[st][i];int c = f[len][st] + 1;if (f[len][nxt] == -1 || f[len][nxt] > c) {f[len][nxt] = c;if (!inq[nxt]) {queue.offer(nxt);inq[nxt] = true;}}}else {int[] result = check(st, len, i == 10);int t = result[0];int c = result[1];if (t > 0) {if (f[len + t][0] == -1 || f[len + t][0] > f[len][st] + 1 + c) {f[len + t][0] = f[len][st] + 1 + c;}}}}}}void init(String[] all) {for (int i = 0; i < all.length; ++ i) {String[] t= all[i].split("\\W+");for (String p : t) {String x = p.trim();if (x.length() > 0) {allWords.add(x);}}}addPrefix("", "");for (int i = 0; i < allWords.size(); ++ i) {String originStr = "";String digitStr = "";String s = allWords.get(i);for (int j = 0; j < s.length(); ++ j) {digitStr += getDigit(s.charAt(j));originStr += s.charAt(j);addPrefix(originStr, digitStr);}}for (String s: mapForNext.keySet()) {Collections.sort(mapForNext.get(s));}g = new int[prefixIndex][9];for (int i = 0; i < prefixIndex; ++ i) {for (int j = 0; j < 9; ++ j) {if (j == 0) {g[i][j] = getNext(i);}else {g[i][j] = getAddDigit(i, j + 1);}}}}int[] check(int id, int preIndex, boolean isStar) {if (id == 0) {return new int[]{0,0};}String s = mapRev.get(id);String sub = word.substring(preIndex);if (isStar) {s = s.substring(0, s.length() - 1);}int comPre = 0;for (int i = 0; i < sub.length() && i < s.length(); ++ i) {if (sub.charAt(i) == s.charAt(i)) {++comPre;}else {break;}}return new int[]{comPre, s.length() - comPre};}int getNext(int id) {if (id == 0) {return 0;}String s = mapRev.get(id);String digitStr = mapToDigit.get(s);List<String> list = mapForNext.get(digitStr);int index = list.indexOf(s);String nextOriginStr = list.get((index + 1) % list.size());return map.get(nextOriginStr);}int getAddDigit(int id, int d) {String s = mapRev.get(id);String digitStr0 = mapToDigit.get(s);String digitStr1 = digitStr0 + (char)('0' + d);if (!mapForNext.containsKey(digitStr1)) {return id;}List<String> list = mapForNext.get(digitStr1);return map.get(list.get(0));}void addPrefix(String originStr, String digitStr) {if (!map.containsKey(originStr)) {map.put(originStr, prefixIndex);mapRev.put(prefixIndex, originStr);++ prefixIndex;}if (!mapForNext.containsKey(digitStr)) {mapForNext.put(digitStr, new ArrayList<>());}if (!mapForNext.get(digitStr).contains(originStr)) {mapForNext.get(digitStr).add(originStr);}mapToDigit.put(originStr, digitStr);}static char getDigit(char c) {int t = c - 'a' + 1;for (int i = 0; i < D.length; ++ i) {if (t > D[i]) {t -= D[i];}else {return (char)('2' + i);}}return 0;} }

　　

code for problem3

import java.util.*;public class InfiniteLab {final static int[] dx = {0, 0, 1, -1};final static int[] dy = {1, -1, 0, 0};final static int MAX_EXTENDED = 100;int n, m;String[] map;int[][] T;int[][][][] d;public long getDistance(String[] map, long r1, int c1, long r2, int c2) {if (r1 > r2) {return getDistance(map, r2, c2, r1, c1);}if (r1 < 0 || r1 >= map.length) {long det = r2 - r1;long b = (Math.abs(r1) / map.length + 1) * map.length;r1 = (r1 + b) % map.length;return getDistance(map, r1, c1 , r1 + det, c2);}this.map = map;n = map.length;m = map[0].length();T = new int[n][2];for (int i = 0; i < n; ++ i) {T[i][0] = T[i][1] = -1;for (int j = 0; j < m; ++ j) {if (map[i].charAt(j) == 'T') {if (T[i][0] == -1) {T[i][0] = j;}else {T[i][1] = j;}}}}d = new int[m][n][m][n + 1];cal();if (r2 <= n) {int t = d[c1][(int)r1][c2][(int)r2];if (t == Integer.MAX_VALUE) {t = -1;}return t;}long[][] a = new long[m][m];long[][] b = new long[m][m];for (int i = 0; i < m; ++ i) {for (int j = 0; j < m; ++ j) {a[i][j] = -1;if (d[i][0][j][n] != Integer.MAX_VALUE) {a[i][j] = d[i][0][j][n];}if (i == j) {b[i][j] = 0;}else {b[i][j] = -1;}}}long p = r2 / n - r1 / n - 1;while (p > 0) {if ((p & 1) == 1) {b = multipy(b, a);}a = multipy(a, a);p >>= 1;}long result = -1;for (int i = 0; i < m; ++ i) {for (int j = 0; j < m; ++ j) {if (d[c1][(int)r1][i][n] != Integer.MAX_VALUE&& b[i][j] != -1&& d[j][0][c2][(int)(r2 % n)] != Integer.MAX_VALUE) {long w = d[c1][(int)r1][i][n] + b[i][j] + d[j][0][c2][(int)(r2 % n)];if (result == -1 || result > w) {result = w;}}}}return result;}long[][] multipy(long[][] A, long[][] B) {long[][] result = new long[m][m];for (int i = 0; i < m; ++ i) {for (int j = 0; j < m; ++ j) {result[i][j] = -1;for (int k = 0; k < m; ++ k) {if (A[i][k] != -1 && B[k][j] != -1) {long t = A[i][k] + B[k][j];if (result[i][j] == -1 || result[i][j] > t) {result[i][j] = t;}}}}}return result;}int trans(int x, int y) {x %= n;if (map[x].charAt(y) == 'T') {return T[x][0] + T[x][1] - y;}return -1;}boolean empty(int x, int y) {return map[x % n].charAt(y) != '#';}void cal() {final int N = (2 * MAX_EXTENDED + 1) * n;int[][] f = new int[N][m];Queue<Integer> queue = new LinkedList<>();for (int sx = 0; sx < n; ++ sx) {for (int sy = 0; sy < m ; ++ sy) {final int startX =sx + MAX_EXTENDED * n;final int startY = sy;while (!queue.isEmpty()) {queue.poll();}for (int i = 0; i < N; ++ i) {Arrays.fill(f[i], Integer.MAX_VALUE);}f[startX][startY] = 0;queue.offer(startX * 100 + startY);while (!queue.isEmpty()) {int x = queue.peek() / 100;int y = queue.poll() % 100;int nxtCost = f[x][y] + 1;for (int i = 0; i < 4; ++ i) {int xx = x + dx[i];int yy = y + dy[i];if (xx >= 0 && xx < N && yy >= 0 && yy < m && empty(xx, yy) && f[xx][yy] > nxtCost) {f[xx][yy] = nxtCost;queue.offer(xx * 100 + yy);}}if (trans(x, y) != -1) {int y1 = trans(x, y);if (f[x][y1] > nxtCost) {f[x][y1] = nxtCost;queue.offer(x * 100 + y1);}}}for (int i = 0; i <= n; ++ i) {for (int j = 0; j < m; ++ j) {d[sy][sx][j][i] = f[i + MAX_EXTENDED * n][j];}}}}}}

　　

轉載于:https://www.cnblogs.com/jianglangcaijin/p/7856365.html

總結

以上是生活随笔為你收集整理的topcoder srm 490 div1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。