topcoder srm 480 div1

Bertha 。 2022-03-29 08:48 73阅读 0赞

problem1 [link][]

直接模拟即可。

problem2 [link][link 1]

首先，网关一定是安装在client与server之间的链路上。而不会安装在client与client之间的链路上。对于一条路径c1->c2->c3->c4->s，且不存在任何一个其他的client使得c4到该client存在链路且该client可以到达s。假设c1->c2之间的链路安装了，那么c4->s之间的链路还要安装。所以只需要在c4->s之间的链路安装即可。

所以所有的安装位置一定是在client与server之间的链路上。且对于某个安装的链路c->s不存在其他的$c^\{'\}$使得c->$c^\{'\}$存在链路且$c^\{'\}$可以到达s。

problem3 [link][link 2]

每一段解码选择的区间为\[L,R\]，那么设\[L,R-1\]之间的数字为num,R位置的字符为letter。这个可以表示为二元组\{num,letter\}。这里L位置的字符一定不能是0,所以num一定大于0.

对于连续的两段解码区间$\[L\_\{1\},R\_\{1\}\],\[L\_\{2\},R\_\{2\}\](R\_\{1\}+1=L\_\{2\})$,必须满足$R\_\{1\} \\ne R\_\{2\}$

对于某一段\{num,letter\}，假设是\{6,3\}，第一次解码之后是333333。那么第二次解码有可能是一下几种情况：

（1）当前段所有数字，即333333作为后面一段数字的num出现，比如假设后面是两个4，即33333344,那么下一次解码可能是$\\underset\{3333334\}\{\\underbrace\{44........44\}\}$

（2）当前段的前几个3作为下一次解码的某一段的num，后面的一个3是letter，再后面的剩余的3作为下一次解码的number出现，比如前面有两个6，后年有两个4，即66633333344,下一次解码可能是

$\\underset\{66\}\{\\underbrace\{33........33\}\}\\underset\{33333\}\{\\underbrace\{44........44\}\}$ 前面必须有未使用完的数字作为num

$\\underset\{663\}\{\\underbrace\{33........33\}\}\\underset\{3333\}\{\\underbrace\{44........44\}\}$ 当前段还有数字作为后面的（即44）的num

$\\underset\{6633\}\{\\underbrace\{33........33\}\}\\underset\{333\}\{\\underbrace\{44........44\}\}$ 当前段还有数字作为后面的（即44）的num

$\\underset\{66333\}\{\\underbrace\{33........33\}\}\\underset\{33\}\{\\underbrace\{44........44\}\}$ 当前段还有数字作为后面的（即44）的num

$\\underset\{663333\}\{\\underbrace\{33........33\}\}\\underset\{3\}\{\\underbrace\{44........44\}\}$ 当前段还有数字作为后面的（即44）的num

$\\underset\{6633333\}\{\\underbrace\{33........33\}\}\\underset\{4\}\{\\underbrace\{44........44\}\}$ 当前段没有数字作为后面的（即44）的num

所以动态规划的状态需要保留两个信息：第一个，前一段第二次解码的letter是什么；第二，前面是否还有未使用的数字作为当前段的num。

code for problem1

import java.util.*;
    import java.math.*;
    import static java.lang.Math.*;
    
    public class InternetSecurity {
    
    
    	public String[] determineWebsite(String[] address, String[] keyword, String[] dangerous, int threshold) {
    		final int n = address.length;
    		List<List<String>> keys = new ArrayList<>();
    		for (int i = 0; i < n; ++ i) {
    			List<String> list = new ArrayList<>();
    			String[] p = keyword[i].split("\\W+");
    			for (String s : p) {
    				String t = s.trim();
    				if (t.length() > 0) {
    					list.add(t);
    				}
    			}
    			keys.add(list);
    		}
    
    		Set<String> allDanger = new HashSet<>(Arrays.asList(dangerous));
    
    		List<Integer> result = new ArrayList<>();
    		boolean flag = true;
    		boolean[] tag = new boolean[n];
    		while (flag) {
    			flag = false;
    			for (int i = 0; i < n; ++ i) {
    				if (tag[i]) {
    					continue;
    				}
    				int cnt = 0;
    				for (String s : keys.get(i)) {
    					if (allDanger.contains(s)) {
    						++ cnt;
    						if (cnt >= threshold) {
    							break;
    						}
    					}
    				}
    				if (cnt >= threshold) {
    					result.add(i);
    					flag = true;
    					tag[i] = true;
    					allDanger.addAll(keys.get(i));
    				}
    			}
    		}
    		Collections.sort(result);
    		String[] ans = new String[result.size()];
    		for (int i = 0; i < ans.length; ++ i) {
    			ans[i] = address[result.get(i)];
    		}
    		return ans;
    	}
    }

code for problem2

import java.util.*;
    import java.math.*;
    import static java.lang.Math.*;
    
    public class NetworkSecurity {
    	
    	public int secureNetwork(String[] clientCable, String[] serverCable) {
    		final int n = clientCable.length;
    		final int m = serverCable[0].length();
    		boolean[][] g = new boolean[n + m][n + m];
    		for (int i = 0; i < n; ++ i) {
    			for (int j = 0; j < n; ++ j) {
    				if (clientCable[i].charAt(j) == 'Y') {
    					g[i][j] =true;
    				}
    			}
    			for (int j = 0; j < m; ++ j) {
    				if (serverCable[i].charAt(j) == 'Y') {
    					g[i][n + j] = true;
    				}
    			}
    		}
    		for (int i = 0; i < n + m; ++ i) {
    			for (int j = 0; j < n + m; ++ j) {
    				for (int k = 0; k < n + m; ++ k) {
    					if (g[j][i] && g[i][k]) {
    						g[j][k] = true;
    					}
    				}
    			}
    		}
    		int result = 0;
    		for (int i = 0; i < n; ++ i) {
    			for (int j = 0; j < m; ++ j) {
    				if (serverCable[i].charAt(j) == 'Y') {
    					boolean tag = true;
    					for (int k = 0; k < n; ++ k) {
    						if (g[i][k] && g[k][n + j]) {
    							tag = false;
    							break;
    						}
    					}
    					if (tag) {
    						++ result;
    					}
    				}
    			}
    		}
    		return result;
    	}
    }

code for problem3

import java.util.*;
    import java.math.*;
    import static java.lang.Math.*;
    
    public class StringDecryption {
    	final static int mod = 1000000009;
    
    	String S = null;
    
    	public int decrypt(String[] code) {
    		StringBuilder sb = new StringBuilder();
    		for (String s: code) {
    			sb.append(s);
    		}
    		S = sb.toString();
    		final int n = S.length();
    		long[][][] f = new long[n + 1][11][2];
    		f[0][10][0] = 1;
    		for (int i = 1; i <= n; ++ i) {
    			final int cur = getChar(i);
    			for (int j = 0; j <= i - 2; ++ j) {
    				//当前段为{[j+1,i-1],i}
    				//前一段为{[xxx,j-1],j}
    				if (getChar(j + 1) == 0) {  //当前段个数不能有前导0
    					continue;
    				}
    				if (getChar(j) == cur) {  //前一段跟当前段的数字不能相同
    					continue;
    				}
    				final long X = get(j + 1, i - 1);
    				for (int k = 0; k < 11; ++ k) {
    					for (int t = 0; t < 2; ++ t) {
    						if (cur == 0 && t == 0) {  //当前段数字为0时 第二次解码必定是跟前一段连在一起
    							continue;                //因为对当前段第一次解码后 全是0
    						}
    						final long val = f[j][k][t];
    						f[i][k][1] = (f[i][k][1] + val) % mod; //当前段直接作为开始或者是跟在前一段的开始
    						if (k == cur) {
    							continue;
    						}
    						if (cur > 0 && X > 1) {
    							if (t == 1) {
    								f[i][cur][1] = (f[i][cur][1] + val) % mod;
    							}
    							f[i][cur][1] += val * (X - 2) % mod;
    							f[i][cur][1] %= mod;
    						}
    						if (X > 1 || t == 1) {  //最后一个数字作为结束
    							f[i][cur][0] = (f[i][cur][0] + val) % mod;
    						}
    					}
    				}
    			}
    		}
    		long result = f[n][getChar(n)][0];
    		if (result < 0) {
    			result += mod;
    		}
    		return (int)result;
    	}
    
    	int getChar(int pos) {
    		if (pos == 0) {
    			return 10;
    		}
    		return S.charAt(pos - 1) - '0';
    	}
    
    	long get(int ll, int rr) {
    		long result = 0;
    		long b = 1;
    		for (int i = rr; i >= ll; -- i) {
    			result = calMod(result + b * getChar(i));
    			b = calMod(b * 10);
    		}
    		return result;
    	}
    
    	long calMod(long x) {
    		if (x >= mod) {
    			x %= mod;
    			if (x <= 1) {
    				x += mod;
    			}
    		}
    		return x;
    	}
    }

[link]: https://community.topcoder.com/stat?c=problem_statement&pm=11064&rd=14159
[link 1]: https://community.topcoder.com/stat?c=problem_statement&pm=10736&rd=14159
[link 2]: https://community.topcoder.com/stat?c=problem_statement&pm=10748&rd=14159