精华内容
下载资源
问答
  • 字典序最小

    2018-07-30 17:26:00
    #include<bits/stdc++.h> using namespace std; #define maxn 110 int solve(const char* s,int p,int q){ int n=strlen(s); for(int i=0;i<n;i++) if(s[(p+i)%n]!=s[(q+i)%n]) return s[(...
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 110
    int solve(const char* s,int p,int q){
        int n=strlen(s);
        for(int i=0;i<n;i++)
        if(s[(p+i)%n]!=s[(q+i)%n])
        return s[(p+i)%n]<s[(q+i)%n];
        return 0;
    }
    int main(){
        int t;
        char s[maxn];
        //freopen("input.txt","r",stdin);
        cin>>t;
        while(t--){
            cin>>s;
            int ans=0;
            int n=strlen(s);
            for(int i=1;i<n;i++)
            if(solve(s,i,ans)) ans=i;
            for(int i=0;i<n;i++)
            putchar(s[(i+ans)%n]);
            cout<<endl;
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/mch5201314/p/9391706.html

    展开全文
  • 字典序最小最小割

    2020-05-16 20:20:00
    但是有时,需要求字典序最小的最小割。 我们可以把所有的边从小到大排序,并遍历。 如果当前边可以删除,那么就删除它,否则继续。 一条边\((u,v,w)\)能被删除有2个条件: 这条边满流,且u到v不存在增广路(即bfs(u,...

    通常,构造最小割时,我们对残量网络进行bfs,设能够到达的集合为S,不够到达的集合为T (遍历时考虑反向边),则从S指向T的边被割掉。
    但是有时,需要求字典序最小的最小割。
    我们可以把所有的边从小到大排序,并遍历。
    如果当前边可以删除,那么就删除它,否则继续。
    一条边\((u,v,w)\)能被删除有2个条件:
    这条边满流,且u到v不存在增广路(即bfs(u,v)找不到路径)。

    首先,把这条边删除(即它和它的反向边流量都设为0)。
    删除它之后,需要进行退流。
    就是分别从T到v,u到S,进行w的增广。
    增广的过程和dinic类似。

    退流代码:

    void tuiliu(int x,int y,ll z)
    {
    	while(z>0)
    	{
    		bfs(x,y);
    		for(int i=1;i<=N;i++)
    			dy[i]=fr[i];
    		while(1)
    		{
    			ll rt=dfs(x,y,z);
    			if(rt==-1)
    				break;
    			z-=rt;
    		}
    	}
    }
    
    展开全文
  • 字典序最小问题

    2020-08-10 21:41:16
    字典序最小问题 /* 字典序最小问题 给一个定长为N的字符串S,构造一个字符串T,长度也为N。 起初,T是一个空串,随后反复进行下列任意操作 从S的头部删除一个字符,加到T的尾部 从S的尾部删除一个字符,加到T的尾部 ...

    字典序最小问题

    /*
    字典序最小问题
    给一个定长为N的字符串S,构造一个字符串T,长度也为N。
    起初,T是一个空串,随后反复进行下列任意操作

    1. 从S的头部删除一个字符,加到T的尾部
    2. 从S的尾部删除一个字符,加到T的尾部
      目标是最后生成的字符串T的字典序尽可能小
      1≤N≤2000
      字符串S只包含大写英文字母
      输入:字符串S 6 A C D B C B
      输出:字符串T ABCBCD
      POJ - 3617 要求每80个字符换行输出
      */
    package _90贪心;
    import java.util.Scanner;
    
    public class 字典序最小 {
    public static void main(String[] args) {
    	Scanner in=new Scanner(System.in);
    	StringBuilder sc=new StringBuilder();
    	int n=in.nextInt();//输入字典数长度
    	for(int i=0;i<n;i++) {
    		sc.append(in.next());//添加入
    	}
    	String s=sc.toString();//转化为字符串  
    //	String s1=in.nextLine();
    	  f(s);
    }
    private static void f(String s1) {
    	// TODO Auto-generated method stub//要建立StringBuilder才能翻转
    	String s2=new StringBuilder(s1).reverse().toString();//先翻转然后转化为字符串
    	int n=s1.length();
        StringBuilder xin=new StringBuilder();//建立新字符对象,存储结果
        while(xin.length()<n) {//不能超出长度
        	if(s1.compareTo(s2)<=0) {//s与ss比较 小于0的就运行
        		xin.append(s1.charAt(0));//添入
        		s1=s1.substring(1);//删头
        		
        	}else {
        		xin.append(s2.charAt(0));//添入
        		s2=s2.substring(1);//删头
        	}
        }
         System.out.println(xin.toString());//输出
    }
    }
    /*
    //字符满80个就换行
    if (rs.length() % 80 == 0) {
      System.out.println(rs.substring(cnt * 80, (cnt + 1) * 80));
      cnt++;
    }
    }
    //余数部分
    if (rs.length() > cnt * 80) {
    System.out.println(rs.substring(cnt * 80));*/
    
    展开全文
  • 字典序最小序列

    千次阅读 2019-04-30 15:27:26
    给定一个字符串序列,拼接之后字典序最小。 解法:自定义比较器,调用Arrays.sort()来排序之后拼接返回 public class LowestLexicography { public static class MyComparator implements Comparator<String>...

    给定一个字符串序列,拼接之后字典序最小。
    解法:自定义比较器,调用Arrays.sort()来排序之后拼接返回

      public class LowestLexicography {
    	public static class MyComparator implements Comparator<String> {
    	//贪心考虑a+b是否大于b+a
    	
    		@Override
    		public int compare(String a, String b) {
    			return (a + b).compareTo(b + a);
    		}
    	}
    
    	public static String lowestString(String[] strs) {
    		if (strs == null || strs.length == 0) {
    			return "";
    	}
    	//先排序,然后相加
    	Arrays.sort(strs, new MyComparator());
    	String res = "";
    	for (int i = 0; i < strs.length; i++) {
    		res += strs[i];
    	}
    	return res;
    }
    

    类似题目(剑指offer):
    题目描述
    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
    例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

     public class Solution {
            public String PrintMinNumber(int [] numbers) {
                String str = " ";
                for (int i=0; i<numbers.length; i++){
                    for (int j=i+1; j<numbers.length; j++){
        				// Integer.valueOf()的作用是字符串转成int
        				int a = Integer.valueOf(numbers[i] + "" + numbers[j]);
                        // 两个字符串不是简单的加法,而是字符串拼接
        				int b = Integer.valueOf(numbers[j] + "" + numbers[i]);//精华所在
        				if (a > b) {// 按位比较,小的放在最前面
                            int t = numbers[i];
                            numbers[i] = numbers[j];
                            numbers[j] = t;
                        }
                    }
                }
            for (int i = 0; i < numbers.length; i++) {
    			// String.valueOf()的作用是int转字符串
    			str += String.valueOf(numbers[i]);// 此操作还是字符串拼接
            }
            return str;
        }
    }
    
    展开全文
  • E. Minimal Labels 题意: 给出 m 条有向边,组成有向无环图,输出一个 1 到 ...要求最后字典序尽可能小。 solution: 拓扑排序的变形。这题要统计的是每个点的出度,比如说某个点出度为 0 ,那么它的标号一定很...
  • 字典序最小的ABAB

    2020-01-06 21:38:49
    题意:要你找两个数A,B,使得它们在序列中排列是ABAB,如果有多对,找字典序最小的。 题解:我们假设这四个数在序列中的位置是x1,x2,y1,y2,那么我们可以枚举每一对x2,y2(在枚举前先从后往前扫,预处理每一个a[i]...
  • 文章目录字典序最小问题 字典序最小问题
  • 贪心 字典序最小问题

    2018-09-16 21:23:11
    贪心 字典序最小问题 题目大意:给你一个长为N的字符串S,并提供下列2种操作 把S的第一个字母添加到字符串T的末尾,并从S中删除 把S的最后一个字母添加到字符串T的末尾,并从S中删除 让你构造出字典序...
  • 比如选择货物下标字典序最小的一组。例如货物的质量为4 3 2 1,卡车能够装载的质量为5时,第一次会选择4 1而不是2 3。
  • 最小生成树-字典序最小 求满足字典序最小的最小生成树,并输出。 #include #include #include #include #include using namespace std; const int MAXN = 110; struct Node { int u; int v; int w; }; Node...
  • POJ3617字典序最小问题

    2020-07-18 10:59:06
    字典序最小问题 问题描述:给定长度为N的字符串S,要构造一个长度为N的字符串T。期初,T是一个空串,随后反复进行下列任意操作: 1>从S的头部删除一个字符,加到T的尾部; 2>从S的尾部删除一个字符,加到T的...
  • 增加一个条件:使得最早得到字典序最小的字符串 思想:我每次都比较字符串开头和结尾,小的字符输出,我最终得到的就是字典序最小的字符串。 如果你是这样的思想对于没有我自己增加的条件来说是可以的。 修改后的...
  • 来源:JZOJ #332 ...需要用到一种工具:堆,这样能保证一遍求完一定是字典序最小的拓扑序。当然了,使用 c++c++c++ 党福利:STL!!!STL!!!STL!!! 开一个优先队列(堆),不过默认是大根堆,...
  • 字符串互换后字典序最小

    千次阅读 2020-04-19 19:48:34
    问题:给出一个字符串,以及可以互换的位置对,求出互换后字典序最小的。 比如给出字符串dcab,以及可以互换的位置对[[0,3],[1, 2],[0, 2]],则互换后字典序最小的是abcd 思路:第一种方法是广度优先搜索,初始状态...
  • LeetCode 1081. 不同字符的最小子序列 给出一个由a-z组成的字符串S,求他的一个子序列,满足如下条件: ...例如:babbdcc,出现过的字符为:abcd,而包含abcd的所有子序列中,字典序最小的为abdc。 ...
  • /*** 字典序最小的问题* 给定长度为N的字符串s,要构造一个长度为N的字符串T,开始T是一个空的字符串,随后反复进行下列的操作** 从S的头部删除一个字符,添加到T的尾部* 从S的尾部删除一个字符,添加到T的尾部* ...
  • 给你一个列表,L个可以交换的对(相邻的才能交换),问最后list表的字典序最小 解析: 发现不能交换的两种物品,其组成的相对位置不会改变。相同种类物品之间也不会改变。所以将这些相对位置建成边。跑一个字典序...
  • 字典序最小的子序列

    千次阅读 2017-07-18 16:15:42
    2、是所有满足条件1的串中,字典序最小的。 例如:babbdcc,出现过的字符为:abcd,而包含abcd的所有子序列中,字典序最小的为abdc。 Input输入1行字符串S,所有字符均为小写,字符串的长度为L。(1 Output输出...
  • 请填写出所有符合要求的排列中,字典序最小的那个。 例如:22AA3344 比 A2A23344 字典序小。当然,它们都不是满足要求的答案。 “A”一定不要用小写字母a,也不要用“1”代替。字符间一定不...
  • POJ 3617 字典序最小

    2017-12-08 15:07:11
    错误原因 是 每次只比较 首尾两个元素 而忽略了总体字典序最小的问题 此种 当C相等时应继续比较 B A 进而选择右侧的C而不是当C相等时随便选取一个C for(i = 0, j = n-1; i ; ){ if(S[i] [j]){ // res...
  • 给一个字符串s,你可以至多选择两个不同位置的字符进行交换(可以不交换),问所有可能中字典序最小的串。 输入:aaazbcdeadcd 输出:aaaabcdezdcd 题目解析: 字典序最小 即与当前字符串相比最小的字符串 那么只...
  • 给一个全是小写字母的字符串str,删除多余字符,使得每种字符只保留一个,并且让最终结果字符串字典序最小。 输入 dbcacbca 输出 dabc 思路 首先统计各个字符出现的数目 int count[26] 标记数组表明结果中是否...
  • 贪心-字典序最小问题

    2019-03-05 20:08:47
    题目://字典序最小问题,给定一个长为n的字符串s,构造一个字符串t,长度也为n //起初t是一个空串,随后反复进行下列任意操作 比较s的头部和尾部字符,那个小就把哪个添加到t里面去 public static void main...
  • 题目大意:输入n,代表有一个长度为n的字符串。 起初,T是一个空串,随后反复进行下列任意操作: ...思路:这题主要要知道当前后一样时该选哪个,因为要字典序最小,所以应该更快的 选到小的字母,所...
  • 贪心算法——字典序最小问题

    万次阅读 2014-01-19 15:22:33
    贪心算法——字典序最小问题   问题主题:字典序最小 问题描述: 给定长度为N的字符串S,要构造一个长度为N字符串T。T是一个空串,反复执行下列任意操作: l 从S的头部删除一个字符,加到T的尾部; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,904
精华内容 3,561
关键字:

字典序最小