精华内容
下载资源
问答
  • 给你n*m个字符,求最大子矩阵(含有相同的字母最多是多少); w,x,y,z;可以变形成其他字母(见题意); 思路: 将求子矩阵分为3种情况:以全是a的矩阵,全是b的,c的矩阵; 然后进行类似1505的发就行了...

    Largest Submatrix

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 1974    Accepted Submission(s): 949


    Problem Description
    Now here is a matrix with letter 'a','b','c','w','x','y','z' and you can change 'w' to 'a' or 'b', change 'x' to 'b' or 'c', change 'y' to 'a' or 'c', and change 'z' to 'a', 'b' or 'c'. After you changed it, what's the largest submatrix with the same letters you can make?
     

    Input
    The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.
     

    Output
    For each test case, output one line containing the number of elements of the largest submatrix of all same letters.
     

    Sample Input
    2 4 abcw wxyz
     

    Sample Output
    3
     
    题意:
    给你n*m个字符,求最大子矩阵(含有相同的字母最多是多少);
    w,x,y,z;可以变形成其他字母(见题意);

    思路:
    将求子矩阵分为3种情况:以全是a的矩阵,全是b的,c的矩阵;
    然后进行类似1505的求发就行了;
    #include<bits/stdc++.h>
    using namespace std;
    int a[1010][1010];
    int b[1010][1010];
    int c[1010][1010];
    char s[1010][1009];
    int R[1010][1010];
    int L[1010][1010];
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            memset(c,0,sizeof(c));
            for(int i=0;i<n;i++)
            {
                scanf("%s",s[i]);
            }
            for(int i=n-1;i>=0;i--)
            {
                for(int j=0;j<m;j++)
                {
                    if(s[i][j]=='a'||s[i][j]=='w'||s[i][j]=='y'||s[i][j]=='z')
                    a[i][j]=a[i+1][j]+1;
                    if(s[i][j]=='b'||s[i][j]=='w'||s[i][j]=='x'||s[i][j]=='z')
                    b[i][j]=b[i+1][j]+1;
                    if(s[i][j]=='a'||s[i][j]=='x'||s[i][j]=='y'||s[i][j]=='z')
                     c[i][j]=c[i+1][j]+1;
    
                     R[i][j]=j;
                     L[i][j]=j;
                }
            }
    
            int Max=-1;
            for(int i=0;i<n;i++)
            {
                for(int j=1;j<m;j++)
                {
                    int t=j-1;
                    while(a[i][j]<=a[i][t]&&L[i][t]>=0)
                    {
                        L[i][j]=L[i][t];
                        t=L[i][j]-1;
                        if(t<0) break;
                    }
                }
                for(int j=m-2;j>=0;j--)
                {
                    int t=j+1;
                    while(a[i][j]<=a[i][t]&&R[i][t]>=0)
                    {
                        R[i][j]=R[i][t];
                        t=R[i][t]+1;
                        if(t>=m)break;
                    }
                }
                for(int j=0;j<m;j++)          //求最值
                Max=max(Max,(R[i][j]-L[i][j]+1)*a[i][j]);
    
                for(int j=0;j<m;j++)    //初始化
                {
                    L[i][j]=j;
                    R[i][j]=j;
                }
            }
            //b
            for(int i=0;i<n;i++)
            {
                for(int j=1;j<m;j++)
                {
                    int t=j-1;
                    while(b[i][j]<=b[i][t]&&L[i][t]>=0)
                    {
                        L[i][j]=L[i][t];
                        t=L[i][j]-1;
                        if(t<0) break;
                    }
                }
                for(int j=m-2;j>=0;j--)
                {
                    int t=j+1;
                    while(b[i][j]<=b[i][t]&&R[i][t]>=0)
                    {
                        R[i][j]=R[i][t];
                        t=R[i][t]+1;
                        if(t>=m)break;
                    }
                }
                for(int j=0;j<m;j++)          //求最值
                Max=max(Max,(R[i][j]-L[i][j]+1)*b[i][j]);
    
                for(int j=0;j<m;j++)    //初始化
                {
                    L[i][j]=j;
                    R[i][j]=j;
                }
            }
            //c
            for(int i=0;i<n;i++)
            {
                for(int j=1;j<m;j++)
                {
                    int t=j-1;
                    while(c[i][j]<=c[i][t]&&L[i][t]>=0)
                    {
                        L[i][j]=L[i][t];
                        t=L[i][j]-1;
                        if(t<0) break;
                    }
                }
                for(int j=m-2;j>=0;j--)
                {
                    int t=j+1;
                    while(c[i][j]<=c[i][t]&&R[i][t]>=0)
                    {
                        R[i][j]=R[i][t];
                        t=R[i][t]+1;
                        if(t>=m)break;
                    }
                }
                for(int j=0;j<m;j++)          //求最值
                Max=max(Max,(R[i][j]-L[i][j]+1)*c[i][j]);
    
                for(int j=0;j<m;j++)    //初始化
                {
                    L[i][j]=j;
                    R[i][j]=j;
                }
            }
            printf("%d\n",Max);
        }
        return 0;
    }
    

    展开全文
  • 题目链接 本题大意:给你n个长度为value[ i ]的长木板,让你切割成为等长的k份,问你切割的最大长度是多少。 本题思路:其实很容易可以想到先找到一个上界和一个下界,开始... 枚举值,判断是否可行,最大......

     题目链接

    本题大意:给你n个长度为value[ i ]的长木板,让你切割成为等长的k份,问你切割的最大长度是多少。

    本题思路:其实很容易可以想到先找到一个上界和一个下界,开始枚举里面的所有长度,取最长的那个即可,此时发现长度为浮点型朴素算法自然无法枚举,我们可以想到二分,局部逼近即可。

    参考代码:

    /*
        二分思维训练:
            枚举值,判断是否可行,求出最大...最小值
    */
    #include <cstdio>
    #include <algorithm>
    #define mid ((double)(l + r) / 2)
    using namespace std;
    
    const int maxn = 10000 + 5, INF = 100000;
    int n, k;
    double value[maxn];
    
    bool check(double c) {
        int num = 0;
        for(int i = 0; i < n; i ++) {
            num += (int)(value[i] / c);
        }
        return num >= k;
    }
    
    int main() {
        while(~scanf("%d %d", &n, &k) && (n + k) != 0) {
            for(int i = 0; i < n; i ++) {
                scanf("%lf", &value[i]);
            }
            double l = 0, r = INF;
            for(int i = 0; i < 100; i ++) {//进行100次二分,可以保证将解求出,并且可以很大限度保证高精度,由于double型和int型不同,需要用高精度辅助二分结束条件,所以一般卡一个不太大的二分次数上限即可完美求解
                if(check(mid)) l = mid;
                else r = mid;
            }
            printf("%.2f\n", double(l));
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/bianjunting/p/10920452.html

    展开全文
  • 题目链接:【topcoder】SRM696 div1 550 Clicounting最大团可以n2nn2^n搞,然后对这个可以做高维前缀最大值。就可以得到以某个状态的子集构成的最大团的大小。然后显而易见可以折半爆搜,然后瞎几把搞就好了。#...

    题目链接:【topcoder】SRM696 div1 550 Clicounting

    首先, 最大团是O(n2n)求解的,就是我们dfs枚举每个点选与不选,选的话就判断是否和之前选的点有边,所有点枚举完选不选后就更新一次最大团。

    考虑到如果n比较小,我们可以将边集二进制压缩,那么判断是否和之前选的点有边,只要看当前的点的边集是否完全包含之前的点即可。这时候最大团复杂度可以为O(2n)

    现在我们考虑dp1[state]表示选点的集合二进制为state1表示选,0表示不选)下的最大团大小,然后我们可以对dp1做高维前缀最大值,即可得到dp1[state]表示选点的集合二进制为state的子集下的最大团大小。

    然后本题一共38个点,10条不确定边,我们可以考虑将不确定边所连的点丢入A集合,其余点丢入B集合,如果A集合的点数少于一半,可以再从B集合随便选一些点丢入A集合,使得两边点数都不会超过20,这样我们就可以进行折半枚举了。

    考虑对B集合的点求出dp1,然后我们枚举A集合的选点情况,然后记录每种选点方案下所用未知边的状态,记为usedused为二进制状态,1表示用未知边,0表示不用),同时记录可以选的B集合的点为state(该选点方案所选的每个点都和state内为1的点有边)。然后我们可以更新答案dp2[used]=max(dp2[used],cnt+dp1[state])

    最后我们只要再对dp2做一遍高维最大值,即可得到每种选边方案下的最大团大小了。

    #include <bits/stdc++.h>
    using namespace std ;
    
    #define clr( a , x ) memset ( a , x , sizeof a )
    
    const int MAXN = 50 ;
    typedef long long LL ;
    
    vector < string > s ;
    int G[MAXN][MAXN] ;
    int n , m , p ;
    int dp1[1 << 20] ;
    int dp2[1 << 10] ;
    int edge[MAXN] ;
    int spc[MAXN] ;
    int idx[MAXN] ;
    int sta[MAXN] ;
    
    void dfs1 ( int cur , int state , int cnt ) {
        if ( cur == p ) dp1[state] = cnt ;
        else {
            dfs1 ( cur + 1 , state , cnt ) ;
            if ( ( state & edge[cur] ) != state ) return ;
            dfs1 ( cur + 1 , state | 1 << cur , cnt + 1 ) ;
        }
    }
    
    void dfs2 ( int cur , int state , int cnt , int used ) {
        if ( cur == n ) dp2[used] = max ( dp2[used] , cnt + dp1[state] ) ;
        else {
            dfs2 ( cur + 1 , state , cnt , used ) ;
            for ( int i = 0 ; i < cnt ; ++ i ) {
                if ( !~G[idx[cur]][sta[i]] ) return ;
                used |= G[idx[cur]][sta[i]] ;
            }
            sta[cnt] = idx[cur] ;
            dfs2 ( cur + 1 , state & edge[cur] , cnt + 1 , used ) ;
        }
    }
    
    int cmp ( const int& a , const int& b ) {
        return spc[a] < spc[b] ;
    }
    
    class Clicounting {
        public :
        int count ( vector < string > g ) {
            n = g.size () ;
            clr ( G , -1 ) ;
            clr ( spc , 0 ) ;
            clr ( dp1 , 0 ) ;
            clr ( dp2 , 0 ) ;
            clr ( edge , 0 ) ;
            for ( int i = m = 0 ; i < n ; ++ i ) {
                idx[i] = i ;
                for ( int j = 0 ; j < n ; ++ j ) {
                    if ( g[i][j] == '0' ) G[i][j] = -1 ;
                    else if ( g[i][j] == '1' ) G[i][j] = 0 ;
                    else if ( g[i][j] == '?' && i < j ) {
                        G[i][j] = G[j][i] = 1 << ( m ++ ) ;
                        spc[i] = spc[j] = 1 ;
                    }
                }
            }
            sort ( idx , idx + n , cmp ) ;
            for ( p = 0 ; !spc[idx[p]] && p <= n / 2 ; ++ p ) ;
            for ( int i = 0 ; i < n ; ++ i ) {
                for ( int j = 0 ; j < p ; ++ j ) {
                    if ( ~G[idx[i]][idx[j]] ) edge[i] |= 1 << j ;
                }
            }
            dfs1 ( 0 , 0 , 0 ) ;
            int n1 = 1 << p , n2 = 1 << m ;
            for ( int i = 1 ; i < n1 ; i <<= 1 ) {
                for ( int j = 0 ; j < n1 ; ++ j ) {
                    if ( j & i ) continue ;
                    dp1[j ^ i] = max ( dp1[j ^ i] , dp1[j] ) ;
                }
            }
            dfs2 ( p , n1 - 1 , 0 , 0 ) ;
            for ( int i = 1 ; i < n2 ; i <<= 1 ) {
                for ( int j = 0 ; j < n2 ; ++ j ) {
                    if ( j & i ) continue ;
                    dp2[j ^ i] = max ( dp2[j ^ i] , dp2[j] ) ;
                }
            }
            int ans = 0 ;
            for ( int i = 0 ; i < n2 ; ++ i ) {
                ans += dp2[i] ;
            }
            return ans ;
        }
    } ;
    
    int main () {
        while ( ~scanf ( "%d" , &n ) ) {
            Clicounting* it = new Clicounting ;
            s.clear () ;
            for ( int i = 0 ; i < n ; ++ i ) {
                s.push_back ( "" ) ;
                cin >> s[i] ;
            }
            printf ( "%d\n" , it->count ( s ) ) ;
        }
        return 0 ;
    }
    展开全文
  • enum操作--获取枚举里的最大值

    千次阅读 2016-09-27 16:02:00
    一个应用系统,如果程序里没有任何enum的使用,我认为它的可读性是有待...求枚举里的最大/最小枚举, 其实是对Array进行操作: enum EnumTest { ddd = 2, eee } var arr1 = Enum.GetValues(ty...

    一个应用系统,如果程序里没有任何enum的使用,我认为它的可读性是有待商榷的。

     

     

     求枚举里的最大/最小枚举值, 其实是对Array进行操作:

            enum EnumTest
            {
                ddd = 2,
                eee
            }

     

    var arr1 = Enum.GetValues(typeof(EnumTest)); //返回值是一个Array
    arr1.Length //枚举项个数 arr1.GetValue(arr1.GetLowerBound(
    0)).GetHashCode() //求最小值,即2 arr1.GetValue(arr1.GetUpperBound(0)).GetHashCode() //求枚举最大值,即3

     

    Enum.GetName方法

            //
            // 摘要: 
            //     在指定枚举中检索具有指定值的常数的名称。
            //
            // 参数: 
            //   enumType:
            //     枚举类型。
            //
            //   value:
            //     特定枚举常数的值(根据其基础类型)。
            //
            // 返回结果: 
            //     一个字符串,其中包含 enumType 中值为 value 的枚举常数的名称;如果没有找到这样的常数,则为 null。
            //
            // 异常: 
            //   System.ArgumentNullException:
            //     enumType 或 value 为 null。
            //
            //   System.ArgumentException:
            //     enumType 不是 System.Enum。- 或 -value 既不是 enumType 类型,也没有与 enumType 相同的基础类型。
            [ComVisible(true)]
            public static string GetName(Type enumType, object value);

    Enum.GetName(typeof(EnumTest), 2)  //返回值是"ddd"

    Enum.GetName(typeof(EnumTest), 2)  //返回值是null

    转载于:https://www.cnblogs.com/buguge/p/5913185.html

    展开全文
  • emmmmm刷紫书衷心奉劝一句,还是不要光看lrj给的紫书的题意,这个题意很容易就会误导人,这个题光看lrj的题意把题给想复杂了,,其实就是一个二分最大值的题。 题意:给定N条线段,线段之间可能会有部分...
  • 这种最大最小值不固定的题目,一般要枚举最大值/最小值。 可以先出 c[n][6] = b[i] - a[j]; 总共n行6列的矩阵,每行选一个数,选出n个数,这n个数最大最小值之差最小是多少。 我用的是枚举最大值: 显然...
  • 线性dp,入门题。50000个数,两段最大连续和,多case,输出最大和。
  • 经典的切蛋糕问题,这种最小值中求最大值,或者其他题中最大值最小值,基本上都是二分搜索 定义数组sum[i][j] 代表 从(1,1,)到(i,j) 这个矩阵中所有值的总和 枚举行的所有情况,复杂度是O(C(n,3)) C(n,3)...
  • 数对之差的最大值

    2019-10-04 15:46:58
    数组中的一个数字减去它右边子数组中的一个数字可以得到一个差值,所有可能的差值中的最大值。 数组{1, 4, 17, 3, 2, 9} 暴力法 直接枚举i,j (j > i) max(a[i] - a[j]) 复杂度O(n^2) 动态规划 解法一 设mx为...
  • 题意: 有两个种类, n个物品, 有m句话每句话都会说明那两个不是一个种类,且每个物品被当作每个种类的价值不一样。... 然后缩点把每个连通块缩点,每个点就有两种方案,每个方案都有一个最大值和最小值,...
  • 如果遇到题目要求最小的最大值或者使得最小值最大化,这个时候一般情况枚举很容易超时,这时我们就可以用二分搜索的思想来解决问题。
  • 题目大意:给出一组数字序列,要你出两段子数组和两者相加的最大值 解题思路:出1~i的序列的子数组和的最大值,i~n的序列的子数组和的最大值 然后枚举k, 1 关于数组连续的子数组最大和,《编程之美》上有O(n...
  •  的最大值(为方便起见,如果所有的整数均为负数,则最大子序列和为0) 例如 对于输入:-2,11,-4,13,-5,-2,答案为20,即从到 分析 这个问题之所以有意思,是因为存在很多求解它的算法。 解法一:穷举遍历 老老...
  • 然后我们把这个放车的点删去,看会不会影响最大能放车的,如果能影响,这个点就是一个important点,思路就是我们先将图按行和列分成两个集合一个二分图最大匹配(裸的匈牙利),然后我们枚举每条边进行删除操作,...
  • 枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
  • POJ1039:枚举+交点

    2019-03-31 21:31:00
    POJ1039 题解 我们把(xi,yi-1)--(xi,yi)作为一条垂直线段,那么一共有n条线段。... 如果与第i条线段不相交,那么直线与i,i-1上下两条线段的交点,横坐标最大值。 代码:1A很舒服~ #inc...
  • 有n个物品,每个物品分别对应一个重量和价值。...思路:设k的集合是S ,使得平均值最大,即 Vs/Ws 最大枚举答案x,Vs/Ws>=x,即 Vs – Ws*x>=0 成立。二分x即可。代码:#include #include #include #include #inc
  • 题目链接: ... 题目大意: 有n个牛栏,选m个放进牛,相当于一条线段上有n个点,选取m个点, 使得相邻点...二分枚举最小距离的最大值 1 #include<iostream> 2 #include<cstring> 3 #include<...
  • 各种求最大值或最小值的问题,解题时宜首先考虑起主要作用的量,如较高数位上的数值,有时局部调整和枚举各种可能情形也是必要的.在日常生活、科学研究和生产实践中,存在大量的最小与最大的问题。如:把一些物资从...
  • 最大值

    2016-10-31 15:19:59
    题目大意给定一个序列,ai opt aj(i)的最大值。 opt是and/or/xorxor一个数一个数插入进trie中每次查找一发 n log nand和or从高位向低位贪心 尽量使高位位运算后结果为1 我们可以枚举一个数作为必须在位运算中...
  • POJ-3258 River Hopscotch 二分枚举求上限

    千次阅读 2014-03-04 09:28:05
    题目链接 题意:有一条河,河的长度已知,河中间有一些石头,石头的数量知道,相邻两块...每 次二分枚举一个,判断该能够去掉多少块石头。二分枚举求上限。 #include #include #include #include #include #in
  • 题目链接:F. Drivers Dissatisfaction 题意:n个点,m条边,每条边有一个w,代表这条路的不满意度,每一条边我们可以花费c来使不满意读-1;然后问你有s,找到一棵生成树...这里树上两点的最短路经过的最大值,我们...
  • poj1050-二维数组子数组和的最大值

    千次阅读 2014-03-07 21:52:14
    题意:给定一个二维数组,有正有负,矩阵的规模不超过100*100,矩阵元素在-127到127之间,该二维数组的一个子数组,使得该数组的元素之和在所有的子数组中是最大的。 解法一: 对整个矩阵进行枚举,采用四重...
  • 题目:数组的所有子数组的和的最大值(二维) 思路:首先我们考虑的是最直接最简单的穷举法,然后又考虑了老师提出的找最大正数(优先)或最小负数(排除)方法,但是考虑到这个方法可能出错,于是我们便参考资料,...
  • 有n个矩阵,你现在可以再加最多两个(不能重合),之后被k个矩阵覆盖的面积最大值。 解析: 先用二维前缀和处理出每个点被覆盖的次数,加矩阵的话,原来k-1的地方变成k,所以设为1,k的地方减少,所以设为-1。 ...
  • 给你一个无向,所有生成树中,最大边与最小边差值最小的那个。 算法分析: 排序,从最小边开始,枚举每一条最小边,然后最小生成树,差值,然后出最小值。 代码; #include #include #include ...
  • D - Largest Group  Gym - 101915D  题意 男生p个,女生p个,男生们相互都为朋友女生们也都是... 位运算辅助出在每种情况下的 人数为多少,不断维护最大值 #include&lt;bits/stdc++.h&gt; usi...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,640
精华内容 1,056
关键字:

最大值求枚举