网站建设介绍文字/谷歌浏览器直接打开

1、设有一个字母表$T$，对于一个单词$w$，若对于任意的$0\leq i< |w|-1$，满足$w_{i}$在$T$中的排名小于等于$w_{i+1}$在$T$中的排名，则称$s$在$T$中是合法的。给出一个仅包含小写字母的单词集合$S$，重新排列字母表$T$得到新的字母表$T^{'}$，使得$S$中每个单词在$T^{'}$下是合法的。问是否存在这样的$T^{'}$。

思路：建立有向图。不存在环即可。可以拓扑排序或者用floyd判断。

import java.util.*;
import java.io.*;public class AlphabetOrderDiv1
{int[][] g=new int[26][26];public String isOrdered(String[] words){for(int i=0;i<26;++i) g[i][i]=1;for(int i=0;i<words.length;++i){String s=words[i];for(int j=0;j+1<s.length();++j){int x=s.charAt(j)-'a';int y=s.charAt(j+1)-'a';g[x][y]=1;}}for(int i=0;i<26;++i) {for(int j=0;j<26;++j) {for(int k=0;k<26;++k) {g[j][k]|=g[j][i]&g[i][k];}}}for(int i=0;i<26;++i) {for(int j=0;j<i;++j) {if(g[i][j]!=0&&g[j][i]!=0) return "Impossible";}}return "Possible";}
}

　　

2、有n个盒子。每个盒子有1个糖。有一个大小为$n*m$转换矩阵$T$。进行$10^{100}$次操作，每次操作如下：（1）选择一个$j,0\leq j< m$，对所有的$i,0\leq i< n$,将第$i$个盒子的糖倒入到第$T[i][j]$个盒子。问最后最少有几个盒子中有糖？

思路：首先，每进行一次操作，有糖的盒子的数目不会变多。其次，假设一开始进行的操作序列为$S$，设这时候的状态为$x$,然后进行一个操作序列$P$，随后再进行一个操作序列$S$，设这时候的状态为$y$，那么$y$时有糖的盒子是状态$x$时有糖的盒子的子集。

基于这两个结果，操作的流程为：判断当前是否存在两个盒子，使得经过某个操作序列$P$后，这两个盒子在操作后合并到同一个盒子，那么就执行该操作序列$P$。直到不存在这样的两个盒子即可。

import java.util.*;public class MovingTokens {int[][] A;int N,M;int[][] B;List<List<Integer>> T=new ArrayList<List<Integer>>();int[][] f;int K=0;boolean dfs(int x,int y,LinkedList<Integer> path){if(x==y) return true;if(f[x][y]==K) return false;f[x][y]=K;for(int j=0;j<M;++j){int xx=A[x][j];int yy=A[y][j];if(dfs(xx,yy,path)) {path.addFirst(j);return true;}}return false;}int cal(int x,int y){if(B[x][y]!=-2) return B[x][y];++K;LinkedList<Integer> path=new LinkedList<Integer>();if(dfs(x,y,path)) {T.add(path);return B[x][y]=T.size()-1;}else {return B[x][y]=-1;}}void transform(int x,int y,int[] a){int id=B[x][y];int[] b=new int[N];for(int cur=0;cur<T.get(id).size();++cur){int j=T.get(id).get(cur);for(int i=0;i<N;++i) {b[i]=a[i];a[i]=0;}for(int i=0;i<N;++i) a[A[i][j]]+=b[i];}}public int move(int n, int m, int[] moves) {A=new int[n][m];for(int i=0;i<n;++i) {for(int j=0;j<m;++j) {A[i][j]=moves[j*n+i];}}this.N=n;this.M=m;B=new int[N][N];f=new int[N][N];for(int i=0;i<N;++i) {for(int j=i+1;j<N;++j) {B[i][j]=-2;}}int[] a=new int[N];for(int i=0;i<N;++i) a[i]=1;while(true){int x=-1,y=-1;all:for(int i=0;i<N;++i) {if(a[i]!=0) {for(int j=i+1;j<N;++j) {if(a[j]!=0&&cal(i,j)!=-1){x=i;y=j;break all;}}}}if(x==-1) break;transform(x,y,a);}int cnt=0;for(int i=0;i<N;++i) {if(a[i]!=0) ++cnt;}return cnt;}
}