#include <stdio.h> #include <string.h> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; #define pb push_back char p[15]; int f[15]; int m, n, inp; double prob[30]; char c[30]; double dp[1010][15]; void kmpProcess() { int i = 0, j; j = f[0] = -1; while(i <= m) { while(j >= 0 && p[i] != p[j]) j = f[j]; i++; j++; f[i] = j; } } double solve(int i, int j) { if(j == m) return 1; if(i == n) return 0; if(dp[i][j] != -1) return dp[i][j]; else { double res = 0; for (int k = 0; k < inp; k++) { int jj = j; while(jj >= 0 && p[jj] != c[k]) jj = f[jj]; res += (prob[k] * solve(i+1, jj + 1)); } return dp[i][j] = res; } } int main(void) { while(true){ cin >> inp >> n ; if(inp == 0 && n == 0) break; for(int i = 0 ; i < inp ; i++){ char cc[5]; double x; scanf("%s %lf", cc, &x); prob[i] = x; c[i] =cc[0]; } scanf("%s", p); string t = p; m = t.size(); for(int i = 0 ; i < n + 2 ; i++) for(int j = 0 ; j < m + 2; j++) dp[i][j] = -1; kmpProcess(); double res = solve(0, 0) * 100.0; printf("%.2lf%%\n", res); } return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; class Main { static String[] prefix = new String[102]; static String[] sufix = new String[102]; static long[] ans = new long[102]; static char[] pattern; static char[] text; static int[] f = new int[100005]; static int n, m; static void kmpProcess() { int i = 0, j; j = f[0] = -1; while (i < m) { while (j >= 0 && pattern[i] != pattern[j]) j = f[j]; i++; j++; f[i] = j; } } static int kmpSerach() { int res = 0; int i = 0, j = 0; n = text.length; while (i < n) { while (j >= 0 && text[i] != pattern[j]) j = f[j]; i++; j++; if (j == m) { res++; j = f[j]; } } return res; } static void makePrefix(int i) { prefix[i] = prefix[i - 1]; int remaining = m - 1 - prefix[i].length(); if (remaining > 0) { int last = remaining > prefix[i - 2].length() ? prefix[i - 2] .length() : remaining; prefix[i] += prefix[i - 2].substring(0, last); } } static void makeSufix(int i) { sufix[i] = sufix[i - 2]; int remaining = m - 1 - sufix[i].length(); if (remaining > 0) { int first = remaining > prefix[i - 1].length() ? 0 : prefix[i - 1] .length() - remaining; sufix[i] = sufix[i - 1].substring(first) + sufix[i]; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder out = new StringBuilder(); String l; prefix[0] = sufix[0] = "0"; prefix[1] = sufix[1] = "1"; int c = 1; while ((l = br.readLine()) != null) { Arrays.fill(ans, 0); int N = Integer.parseInt(l); pattern = br.readLine().toCharArray(); m = pattern.length; kmpProcess(); if (pattern.length == 1) ans[pattern[0] - '0']++; int i = 2; while (i <= N) { ans[i] = ans[i - 1] + ans[i - 2]; if (m > 1) { makePrefix(i); makeSufix(i); text = (sufix[i - 1] + prefix[i - 2]).toCharArray(); ans[i] += kmpSerach(); } i++; } out.append("Case " + c++ + ": " + ans[N] + "\n"); } System.out.print(out); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; class Main { static String[] prefix = new String[102]; static String[] sufix = new String[102]; static long[] ans = new long[102]; static char[] pattern; static char[] text; static int[] f = new int[100005]; static int n, m; static void kmpProcess() { int i = 0, j; j = f[0] = -1; while (i < m) { while (j >= 0 && pattern[i] != pattern[j]) j = f[j]; i++; j++; f[i] = j; } } static int kmpSerach() { int res = 0; int i = 0, j = 0; n = text.length; while (i < n) { while (j >= 0 && text[i] != pattern[j]) j = f[j]; i++; j++; if (j == m) { res++; j = f[j]; } } return res; } static void makePrefix(int i) { prefix[i] = prefix[i - 1]; int remaining = m - 1 - prefix[i].length(); if (remaining > 0) { int last = remaining > prefix[i - 2].length() ? prefix[i - 2] .length() : remaining; prefix[i] += prefix[i - 2].substring(0, last); } } static void makeSufix(int i) { sufix[i] = sufix[i - 2]; int remaining = m - 1 - sufix[i].length(); if (remaining > 0) { int first = remaining > prefix[i - 1].length() ? 0 : prefix[i - 1] .length() - remaining; sufix[i] = sufix[i - 1].substring(first) + sufix[i]; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder out = new StringBuilder(); String l; prefix[0] = sufix[0] = "0"; prefix[1] = sufix[1] = "1"; int c = 1; while ((l = br.readLine()) != null) { Arrays.fill(ans, 0); int N = Integer.parseInt(l); pattern = br.readLine().toCharArray(); m = pattern.length; kmpProcess(); if (pattern.length == 1) ans[pattern[0] - '0']++; int i = 2; while (i <= N) { ans[i] = ans[i - 1] + ans[i - 2]; if (m > 1) { makePrefix(i); makeSufix(i); text = (sufix[i - 1] + prefix[i - 2]).toCharArray(); ans[i] += kmpSerach(); } i++; } out.append("Case " + c++ + ": " + ans[N] + "\n"); } System.out.print(out); } }
#include <stdio.h> #include <string.h> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; #define pb push_back pair<int, pair<int, int> > inp[100000 + 5]; int tree[100000 + 5]; int n; int read(int idx){ int res = 1 << 30; while(idx > 0){ res = min(res, tree[idx]); idx -= (idx & -idx); } return res; } void update(int idx, int val){ while(idx <= n){ tree[idx] = min(tree[idx], val); idx += (idx & -idx); } } int main() { int t; scanf("%d", &t); while(t--){ scanf("%d", &n); for(int i = 0 ; i < n ; i++){ scanf("%d %d %d", &inp[i].first, &inp[i].second.first, &inp[i].second.second); } sort(inp, inp + n); int maxx = 1 << 30; fill(tree, tree + n + 3, maxx); int res = 0; for(int i = 0 ; i < n ; i++){ int cur = read(inp[i].second.first); if(cur > inp[i].second.second){ res++; } update(inp[i].second.first, inp[i].second.second); } printf("%d\n", res); } return 0; }
#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <ctype.h> #include <stack> #include <iostream> #include <queue> #include <set> #include <map> #include <iterator> using namespace std; struct node{ int v; int i; int j; int q; }; typedef node node; int tree[30001]; node inp[230000]; int n; int maxVal; bool operator <( node a, node b ) { if ( a.v == b.v ) { return a.j > b.j; } return a.v > b.v; } int read(int idx){ int sum = 0; while(idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, int val){ while(idx <= maxVal){ tree[idx] += val; idx += (idx & -idx); } } int main() { int m; scanf("%d", &n); maxVal = n; for(int i = 0 ; i < n ; i++){ scanf("%d", &inp[i].v); inp[i].i = i + 1; inp[i].j = -1; tree[i] = 0; } scanf("%d", &m); int res[m]; for(int i = 0 ; i < m ; i++){ scanf("%d %d %d", &inp[i + n].i , &inp[i + n].j, &inp[i + n].v); inp[i + n].q = i; } sort( inp, inp + n + m ); for(int i = 0 ; i < n + m ; i++){ if(inp[i].j == -1){ update(inp[i].i, 1); }else{ int result = read(inp[i].j) - read(inp[i].i - 1); res[inp[i].q] = result; } } for(int i = 0 ; i < m ; i++) printf("%d\n", res[i]); return 0; }
#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <ctype.h> #include <stack> #include <iostream> #include <queue> #include <set> #define MAXN 10000000 + 5 using namespace std; int tree[MAXN]; int inp[200000 + 5]; int n; int maxVal; int read(int idx){ int sum = 0; while(idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, int val){ while(idx <= maxVal){ tree[idx] += val; idx += (idx & -idx); } } int main() { int t; scanf("%d", &t); while(t--){ scanf("%d", &n); maxVal = 0; for(int i = 0 ; i < n ; i++){ scanf("%d", &inp[i]); maxVal = max(maxVal, inp[i]); } long long res = 0; memset(tree, 0, sizeof(tree)); for(int i = n - 1; i >= 0 ; i--){ res += read(inp[i] - 1); update(inp[i], 1); } printf("%lld\n", res); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.StreamCorruptedException; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; import javax.tools.FileObject; public class Main { static LinkedList<Integer> [] adjList = new LinkedList[50]; static int [] value = new int[50]; static int [] dp = new int[50]; static int go(int i){ if(adjList[i].size() == 0) return value[i]; else if(dp[i] != 0) return dp[i]; else{ for (Integer j : adjList[i]) dp[i] = Math.max(dp[i], go(j) + value[i]); return dp[i]; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder out = new StringBuilder(); int T = Integer.parseInt(br.readLine()); String [] inp = new String[50]; int c = 0; String [] sp; boolean [] isStart = new boolean[50]; br.readLine(); for (int i = 0; i < adjList.length; i++) adjList[i] = new LinkedList<Integer>(); while(T-- > 0){ Arrays.fill(dp, 0); c = 0; while((inp[c] = br.readLine()) != null && inp[c].length() != 0) c++; for (int i = 0; i < c; i++) { adjList[i].clear(); sp = inp[i].split(" "); int cur = sp[0].charAt(0) - 'A'; value[cur] = Integer.parseInt(sp[1]); isStart[cur] = sp.length == 2 ? true :false; for (int j = 0; sp.length == 3 && j < sp[2].length(); j++) { int k = sp[2].charAt(j) - 'A'; adjList[k].add(cur); } } int max = 0; for (int i = 0; i < c; i++) { if(isStart[i]){ max = Math.max(max, go(i)); } } out.append(max + "\n"); if(T > 0) out.append("\n"); } System.out.print(out); } }
#include <stdio.h> #include <string.h> #include <iostream> #include <vector> #include <queue> using namespace std; struct Trie { int pref; Trie * edges[26]; vector<int> word; }; string currWord; Trie *start; int idx; string dic[50005]; int s; vector<pair<int, int> > adjList[50050]; int currIdx; int w; int shortest_paths[26][26]; int shortest_paths2[26][26]; int temp[50050]; int parent[50050]; string output[26][26]; vector<int> dist(50050, 1 << 30); void dijestra(int start) { priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > pq; pq.push(make_pair(0, make_pair(start, 0))); parent[start] = -1; for (int i = 0; i < w + 30; i++) { dist[i] = 1 << 30; } dist[start] = 0; while (!pq.empty()) { pair<int, pair<int, int> > front = pq.top(); pq.pop(); int d = front.first, u = front.second.first; int dd = front.second.second; if (d == dist[u]) { for (int j = 0; j < (int) adjList[u].size(); j++) { pair<int, int> v = adjList[u][j]; int cmp = dist[u] + v.first; if (dd > 1) cmp -= dic[u].size(); if (cmp < dist[v.second]) { dist[v.second] = cmp; pq.push( make_pair(dist[v.second], make_pair(v.second, dd + 1))); parent[v.second] = u; } } } } } void addWord() { Trie * node = start; int pos = 0; while (pos != (int) currWord.size()) { int curr = currWord[pos] - 'a'; if (node->edges[curr] == NULL) { node->edges[curr] = new Trie(); } node->pref++; node->word.push_back(idx); node = node->edges[curr]; pos++; } node->word.push_back(idx); } void getPref() { Trie * node = start; int pos = s; while (pos != (int) currWord.size()) { int curr = currWord[pos] - 'a'; if (node->edges[curr] == NULL) { return; } else { pos++; node = node->edges[curr]; } } for (int i = 0; i < (int) node->word.size(); i++) { if (node->word[i] != currIdx) adjList[currIdx].push_back( make_pair(s + dic[node->word[i]].size(), node->word[i])); } } int main() { char c[70]; int tCase = 1; while (scanf("%d", &w) != EOF && w != 0) { for (int i = 0; i < w + 50; i++) { adjList[i].clear(); } start = new Trie(); idx = 0; for (int i = 0; i < w; i++) { scanf("%s", c); currWord = dic[i] = c; addWord(); idx++; } for (int i = 0; i < w; i++) { currWord = dic[i]; currIdx = i; for (int j = 0; j < (int) dic[i].size() - 1; j++) { s = j; getPref(); } } for (int i = 0; i < 26; i++) { char cc = i + 'a'; for (int j = 0; j < w; j++) { if (cc == dic[j][0]) { adjList[i + w].push_back(make_pair(0, j)); } } } int q; scanf("%d\n", &q); char c1[q]; char c2[q]; bool v[26]; memset(v, false, sizeof(v)); for (int l = 0; l < q; l++) { scanf("%c %c\n", &c1[l], &c2[l]); v[c1[l] - 'a'] = true; } for (int i = w; i < w + 26; i++) { if(!v[i - w]) continue; dijestra(i); int min[26]; for (int j = 0; j < 26; j++) min[j] = 1 << 30; int min_i[26]; for (int j = 0; j < w; j++) { int cc = dic[j][dic[j].size() - 1] - 'a'; if (dist[j] == 0) dist[j] = dic[j].size(); if (dist[j] < min[cc]) { min[cc] = dist[j]; min_i[cc] = j; } } for (int j = 0; j < 26; j++) { if (min[j] != 1 << 30) { shortest_paths2[i - w][j] = min[j]; shortest_paths[i - w][j] = min_i[j]; if (min[j] == 0) { shortest_paths2[i - w][j] = dic[min_i[j]].size(); } } else { shortest_paths2[i - w][j] = 0; shortest_paths[i - w][j] = -1; } } for (int j = 0; j < 26; j++) { int cur = shortest_paths[i - w][j]; output[i - w][j] = ""; if (cur != -1) { while (cur != -1 && cur < w) { output[i - w][j] = " " + dic[cur] + output[i - w][j]; cur = parent[cur]; } } } } for(int i = 0 ; i < q ; i++){ printf("%d.%d %d", tCase, i+1, shortest_paths2[c1[i] - 'a'][c2[i] - 'a']); cout << output[c1[i] - 'a'][c2[i] - 'a'] << endl; } tCase++; memset(shortest_paths, 0, sizeof(shortest_paths)); memset(shortest_paths2, 0, sizeof(shortest_paths2)); memset(parent, 0, sizeof(parent)); } return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Main { static int n,m , s = 1050, t = 1060; static int MAXN = 1100; static int [][] AdjMatric = new int[MAXN][MAXN]; static LinkedList<Integer> [] AdjList = new LinkedList[MAXN]; static int max_flow(){ int res = 0; while(true){ int pathCap = findPath(); if(pathCap == 0) break; else res += pathCap; } return res; } static int findPath(){ Queue<Integer> q = new LinkedList<>(); boolean []v = new boolean[AdjList.length]; q.add(s); v[s] = true; int [] from = new int[AdjList.length]; Arrays.fill(from, -1); boolean f = false; while(!q.isEmpty()){ int curr = q.poll(); for(int i = 0; i < AdjList.length ; i++){ if(AdjMatric[curr][i] > 0 && !v[i]){ q.add(i); v[i] = true; from[i] = curr; if(i == t){ f = true; break; } } } if(f) break; } int where = t; int prev; int pathCap = 1 << 30; while(from[where] > -1){ prev = from[where]; pathCap = Math.min(pathCap, AdjMatric[prev][where]); where = prev; } where = t; if(pathCap == 1 << 30) return 0; while(from[where] > -1){ prev = from[where]; AdjMatric[prev][where] -= pathCap; AdjMatric[where][prev] += pathCap; where = prev; } return pathCap; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder out = new StringBuilder(); String [] sp; String l; for (int i = 0; i < AdjList.length; i++) { AdjList[i] = new LinkedList<Integer>(); } while(true){ sp = br.readLine().split(" "); n = Integer.parseInt(sp[0]); m = Integer.parseInt(sp[1]); if(n ==0 && m == 0) break; for (int i = 0; i < AdjList.length; i++) { Arrays.fill(AdjMatric[i], 0); AdjList[i].clear(); } int dist= 0; sp = br.readLine().split(" "); for (int i = 0; i < sp.length; i++){ dist += Integer.parseInt(sp[i]); AdjMatric[s][i + 1] = Integer.parseInt(sp[i]); } for (int i = 1; i <= m; i++) { sp = br.readLine().split(" "); for (int j = 1; j < sp.length; j++) { AdjMatric[Integer.parseInt(sp[j])][i + 20] = 1; AdjMatric[i + 20][t] = 1; AdjList[Integer.parseInt(sp[j])].add(i); } } int res = max_flow(); if(res != dist) out.append("0\n"); else{ out.append("1\n"); for (int i = 1; i <= n; i++) { boolean f = false; for (int j : AdjList[i]) { if(AdjMatric[i][j + 20] == 0){ if(f) out.append(" "); f = true; out.append(j + ""); } } out.append("\n"); } } } System.out.print(out); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Main { static int s = 37, t = 38; static int [][] AdjMatric = new int[45][45]; static LinkedList<Integer> [] AdjList = new LinkedList[45]; static int max_flow(){ int res = 0; while(true){ int pathCap = findPath(); if(pathCap == 0) break; else res += pathCap; } return res; } static int findPath(){ Queue<Integer> q = new LinkedList<>(); boolean []v = new boolean[AdjList.length]; q.add(s); v[s] = true; int [] from = new int[AdjList.length]; Arrays.fill(from, -1); boolean f = false; while(!q.isEmpty()){ int curr = q.poll(); for(int i = 0; i < AdjList.length ; i++){ if(AdjMatric[curr][i] > 0 && !v[i]){ q.add(i); v[i] = true; from[i] = curr; if(i == t){ f = true; break; } } } if(f) break; } int where = t; int prev; int pathCap = 1 << 30; while(from[where] > -1){ prev = from[where]; pathCap = Math.min(pathCap, AdjMatric[prev][where]); where = prev; } where = t; if(pathCap == 1 << 30) return 0; while(from[where] > -1){ prev = from[where]; AdjMatric[prev][where] -= pathCap; AdjMatric[where][prev] += pathCap; where = prev; } return pathCap; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder out = new StringBuilder(); String [] sp; String l; for (int i = 0; i < AdjList.length; i++) { AdjList[i] = new LinkedList<Integer>(); } while(true){ for (int i = 0; i < AdjList.length; i++) { Arrays.fill(AdjMatric[i], 0); AdjList[i].clear(); } int dist= 0; l = br.readLine(); while(l != null && !l.matches("")){ sp = l.split(" "); AdjMatric[s][sp[0].charAt(0) - 'A'] = sp[0].charAt(1) - '0'; dist += sp[0].charAt(1) - '0'; for (int i = 0; i < sp[1].length() - 1; i++) { AdjMatric[sp[0].charAt(0) - 'A'][sp[1].charAt(i) - '0' + 26] = 1; AdjMatric[sp[1].charAt(i) - '0' + 26][t] = 1; AdjList[sp[0].charAt(0) - 'A'].add(sp[1].charAt(i) - '0'); } l = br.readLine(); } int res = max_flow(); if(res != dist) out.append("!\n"); else{ char [] output = new char[10]; Arrays.fill(output, '_'); for (int i = 0; i < 26; i++) { for (int j : AdjList[i]) { if(AdjMatric[i][j + 26] == 0) output[j] = (char) (i + 'A'); } } out.append(new String(output) + "\n"); } if(l == null) break; } System.out.print(out); } }