UIStackView的简单使用与理解

之前一直在吐槽iOS的布局方式(frame和autolayout)相比前端的flex布局方式很落后,也在想有没有其它的方式来改善。最近偶然发现UIStackView的存在(苹果爸爸原谅我😂),了解后发现其中的使用与布局方式类似于flex布局,感觉这就是苹果爸爸借鉴flex布局特点所构造的一种布局实现方式吧。

实现方式

这里我们看一下如何简单的使用stackview来创造一个拥有众多子item的水平视图。代码如下:

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    containerView = [[UIStackView alloc]initWithFrame:CGRectMake(0, 100, CGRectGetWidth(self.view.bounds), 200)];
    //子视图布局方向:水平或垂直
    containerView.axis = UILayoutConstraintAxisHorizontal;//水平布局
    //子控件依据何种规矩布局
    containerView.distribution = UIStackViewDistributionFillEqually;//子控件均分
    //子控件之间的最小间距
    containerView.spacing = 10;
    //子控件的对齐方式
    containerView.alignment = UIStackViewAlignmentFill;
    NSArray *tempArray = @[@"1",@"2",@"3",@"4"];
    for (NSInteger i = 0; i < 4; i++) {
//        UIView *view = [[UIView alloc]init];
        UILabel *label = [[UILabel alloc] init];
        label.textAlignment = NSTextAlignmentCenter;
        label.backgroundColor = [UIColor colorWithRed:random()%256/255.0 green:random()%256/255.0 blue:random()%256/255.0 alpha:1];
        label.numberOfLines = 0;
        label.text = tempArray[i];
        
        [containerView addArrangedSubview:label];
        
    }
    [self.view addSubview:containerView];
}

可以看到stackView的使用和view没有大的区别,使用时根绝需要来设置stackView的axis(布局方向),distribution(子控件依据何种规矩布局),spacing(子控件之间的最小间距),alignment(子控件的对齐方式)等属性。

这里详细说明一下个属性的主要参数:

axis:
子控件的布局方向,水平(UILayoutConstraintAxisHorizontal)或垂直(UILayoutConstraintAxisVertical), 这个不用过多解释了

UIStackViewDistribution:

UIStackViewDistributionFill :它就是将 arrangedSubviews 填充满整个 StackView ,如果设置了spacing,那么这些 arrangedSubviews 之间的间距就是spacing。如果减去所有的spacing,所有的 arrangedSubview 的固有尺寸( intrinsicContentSize )不能填满或者超出 StackView 的尺寸,那就会按照 Hugging 或者 CompressionResistance 的优先级来拉伸或压缩一些 arrangedSubview 。如果出现优先级相同的情况,就按排列顺序来拉伸或压缩。

UIStackViewDistributionFillEqually :这种就是 StackView 的尺寸减去所有的spacing之后均分给 arrangedSubviews ,每个 arrangedSubview 的尺寸是相同的。

UIStackViewDistributionFillProportionally :这种跟FillEqually差不多,只不过这个不是讲尺寸均分给 arrangedSubviews ,而是根据 arrangedSubviews 的 intrinsicContentSize 按比例分配。

UIStackViewDistributionEqualSpacing :这种是使 arrangedSubview 之间的spacing相等,但是这个spacing是有可能大于 StackView 所设置的spacing,但是绝对不会小于。这个类型的布局可以这样理解,先按所有的 arrangedSubview 的 intrinsicContentSize 布局,然后余下的空间均分为spacing,如果大约 StackView 设置的spacing那这样就OK了,如果小于就按照 StackView 设置的spacing,然后按照 CompressionResistance 的优先级来压缩一个 arrangedSubview 。

UIStackViewDistributionEqualCentering :这种是使 arrangedSubview 的中心点之间的距离相等,这样没两个 arrangedSubview 之间的spacing就有可能不是相等的,但是这个spacing仍然是大于等于 StackView 设置的spacing的,不会是小于。这个类型布局仍然是如果 StackView 有多余的空间会均分给 arrangedSubviews 之间的spacing,如果空间不够那就按照 CompressionResistance 的优先级压缩 arrangedSubview 。

alignment:

UIStackViewAlignmentFill = 默认方式, 如果子控件水平布局, 则指子控件的垂直方向填充满stackView. 反之亦然

UIStackViewAlignmentLeading = 如果子控件竖直布局, 则指子控件左边对齐stackView左边. 反之亦然, 即 UIStackViewAlignmentTop = UIStackViewAlignmentLeading。

UIStackViewAlignmentTop = UIStackViewAlignmentLeading,

UIStackViewAlignmentFirstBaseline = 根据上方基线布局所有子视图的 y 值(适用于 Horizontal 模式)

UIStackViewAlignmentLastBaseline = 根据下方基线布局所有子视图的 y 值(适用于 Horizontal 模式)

UIStackViewAlignmentCenter = 中心对齐

UIStackViewAlignmentTrailing = 如果子控件竖直布局, 则指子控件左边对齐stackView右边. 反之亦然, 即UIStackViewAlignmentBottom = UIStackViewAlignmentTrailing

UIStackViewAlignmentBottom = UIStackViewAlignmentTrailing

这里还要说明几个方法:addArrangedSubviewremoveArrangedSubviewinsertArrangedSubview,日常view的添加和子视图从复视图删除使用的是addSubviewremoveFromSuperview

其中完整方法如下:

初始化数组:
- (instancetype)initWithArrangedSubviews:(NSArray *)views;
添加子视图: 
- (void)addArrangedSubview:(UIView *)view;
移除子视图:
- (void)removeArrangedSubview:(UIView *)view;
根据下标插入视图:
- (void)insertArrangedSubview:(UIView *)viewatIndex:(NSUInteger)stackIndex;

注意: addArrangedSubview 和 insertArrangedSubview, 会把子控件加到arrangedSubviews数组的同时添加到StackView的subView数组中,但是removeArrangedSubview, 只会把子控件从arrangedSubviews数组中移除,不会从subviews中移除,如果需要调用removeFromSuperview

若我们需要删除stackView中subView数组的最后一个视图,可以用如下方式:

//removeArrangedSubview, 只会把子控件从arrangedSubviews数组中移除,
//不会从subviews中移除,如果需要可调用removeFromSuperview
UIView *view = [_containerView.subviews lastObject];
[_containerView removeArrangedSubview:view];
[view removeFromSuperview];

到此stackView的一个简单使用方式就知道了。

2018/10/10 posted in  iOS

UITableView-FDTemplateLayoutCell源码学习

  • 总结

    前言

    该框架是前百度员工孙大神开源的一个用于动态计算cell高度框架,通过该框架对cell的高度进行计算并缓存。从而优化UITableView的流畅性。

    框架文件结构


    该框架比较文件结构简单,一共只有4个类(8个文件)。

    UITableView+FDIndexPathHeightCache :以index path为key缓存高度的具体实现
    UITableVIew+FDKeyedHeightCache :以自定义的key缓存高度的具体实现
    UITableView+FDTemplateLayoutCell :对外提供的接口文件
    UITableView+FDTemplateLayoutCellDebug :给分类添加了一个fd_debugLogEnabled,通过设置该属性来控制是否打印日志。

    使用方式

    使用方式分为三种,分别为无缓存,通过index path缓存,通过key缓存。使用方式分别如下所示:

    可以看到方法的使用时机为在UITableViewDelegate委托协议中的计算高度方法中。

    不缓存高度的实现方式

    首先我们来看第一个方法- (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier configuration:(void (^)(id cell))configuration的实现方式。

    
    - (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier configuration:(void (^)(id cell))configuration {
        if (!identifier) {
            return 0;
        }
        
        UITableViewCell *templateLayoutCell = [self fd_templateCellForReuseIdentifier:identifier];
        
        // Manually calls to ensure consistent behavior with actual cells. (that are displayed on screen)
        [templateLayoutCell prepareForReuse];
        
        // Customize and provide content for our template cell.
        if (configuration) {
            configuration(templateLayoutCell);
        }
        
        return [self fd_systemFittingHeightForConfiguratedCell:templateLayoutCell];
    }
    
    

    可以看到实现主要分为三部分,第一部分为通过- (__kindof UITableViewCell *)fd_templateCellForReuseIdentifier:(NSString *)identifier方法获取一个cell。这里我们先看一下该方法如何获取的,该方法的实现如下所示:

    - (__kindof UITableViewCell *)fd_templateCellForReuseIdentifier:(NSString *)identifier {
        NSAssert(identifier.length > 0, @"Expect a valid identifier - %@", identifier);
        
        NSMutableDictionary<NSString *, UITableViewCell *> *templateCellsByIdentifiers = objc_getAssociatedObject(self, _cmd);
        if (!templateCellsByIdentifiers) {
            templateCellsByIdentifiers = @{}.mutableCopy;
            objc_setAssociatedObject(self, _cmd, templateCellsByIdentifiers, OBJC_ASSOCIATION_RETAIN_NONATOMIC);
        }
        
        UITableViewCell *templateCell = templateCellsByIdentifiers[identifier];
        
        if (!templateCell) {
            templateCell = [self dequeueReusableCellWithIdentifier:identifier];
            NSAssert(templateCell != nil, @"Cell must be registered to table view for identifier - %@", identifier);
            templateCell.fd_isTemplateLayoutCell = YES;
            templateCell.contentView.translatesAutoresizingMaskIntoConstraints = NO;
            templateCellsByIdentifiers[identifier] = templateCell;
            [self fd_debugLog:[NSString stringWithFormat:@"layout cell created - %@", identifier]];
        }
        
        return templateCell;
    }
    

    可以看到该方法通过关联属性添加了一个templateCellsByIdentifiers字典属性,来保证相同的identifier第二次获取cell的时候不再重新获取,直接取的字典属性里面的值(cell)。

    第二部分,通过configuration block让用户有机会对创建好的cell进行定制化
    第三部分,针对frame layout 和 auto layout对cell进行高度的适应计算(包括判断辅助视图来调节cell的宽度等)

    通过index Path来缓存的实现

    首先来看一下- (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier cacheByIndexPath:(NSIndexPath *)indexPath configuration:(void (^)(id cell))configuration方法的实现。

    - (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier cacheByIndexPath:(NSIndexPath *)indexPath configuration:(void (^)(id cell))configuration {
        if (!identifier || !indexPath) {
            return 0;
        }
        
        // Hit cache
        if ([self.fd_indexPathHeightCache existsHeightAtIndexPath:indexPath]) {
            [self fd_debugLog:[NSString stringWithFormat:@"hit cache by index path[%@:%@] - %@", @(indexPath.section), @(indexPath.row), @([self.fd_indexPathHeightCache heightForIndexPath:indexPath])]];
            return [self.fd_indexPathHeightCache heightForIndexPath:indexPath];
        }
        
        CGFloat height = [self fd_heightForCellWithIdentifier:identifier configuration:configuration];
        [self.fd_indexPathHeightCache cacheHeight:height byIndexPath:indexPath];
        [self fd_debugLog:[NSString stringWithFormat: @"cached by index path[%@:%@] - %@", @(indexPath.section), @(indexPath.row), @(height)]];
        
        return height;
    }
    

    该方法主要分为两部分,命中缓存的indexpath与没命中两部分处理。

    第一部分为若命中indexpath缓存时的实现:

     // Hit cache
        if ([self.fd_indexPathHeightCache existsHeightAtIndexPath:indexPath]) {
            [self fd_debugLog:[NSString stringWithFormat:@"hit cache by index path[%@:%@] - %@", @(indexPath.section), @(indexPath.row), @([self.fd_indexPathHeightCache heightForIndexPath:indexPath])]];
            return [self.fd_indexPathHeightCache heightForIndexPath:indexPath];
        }
    

    该部分主要使用- (BOOL)existsHeightAtIndexPath:(NSIndexPath *)indexPath来判断是否命中indexPath缓存,实习细节如下:

    - (BOOL)existsHeightAtIndexPath:(NSIndexPath *)indexPath {
        [self buildCachesAtIndexPathsIfNeeded:@[indexPath]];
        NSNumber *number = self.heightsBySectionForCurrentOrientation[indexPath.section][indexPath.row];
        return ![number isEqualToNumber:@-1];
    }
    
    - (void)buildCachesAtIndexPathsIfNeeded:(NSArray *)indexPaths {
        // Build every section array or row array which is smaller than given index path.
        [indexPaths enumerateObjectsUsingBlock:^(NSIndexPath *indexPath, NSUInteger idx, BOOL *stop) {
            [self buildSectionsIfNeeded:indexPath.section];
            [self buildRowsIfNeeded:indexPath.row inExistSection:indexPath.section];
        }];
    }
    
    - (void)buildSectionsIfNeeded:(NSInteger)targetSection {
        [self enumerateAllOrientationsUsingBlock:^(FDIndexPathHeightsBySection *heightsBySection) {
            for (NSInteger section = 0; section <= targetSection; ++section) {
                if (section >= heightsBySection.count) {
                    heightsBySection[section] = [NSMutableArray array];
                }
            }
        }];
    }
    
    - (void)buildRowsIfNeeded:(NSInteger)targetRow inExistSection:(NSInteger)section {
        [self enumerateAllOrientationsUsingBlock:^(FDIndexPathHeightsBySection *heightsBySection) {
            NSMutableArray<NSNumber *> *heightsByRow = heightsBySection[section];
            for (NSInteger row = 0; row <= targetRow; ++row) {
                if (row >= heightsByRow.count) {
                    heightsByRow[row] = @-1;
                }
            }
        }];
    }
    

    可以看到上述方法的主要功能是调用buildCachesAtIndexPathsIfNeeded及其函数内的子方法来将所有比当前所传入的indexPath小的section以及row所组成的数组值赋值为-1(准确的描述为将当前indexPath的section和row与当前的高度缓存数组heightsBySectionForCurrentOrientation相比,将所有下标大于等于缓存数组下标并且小于等于indexpath的元素赋值为-1);

    之后根据当前的row是否等于-1,来判断是否命中缓存。

    需要注意的是横屏和竖屏的高度可能存在不一致,所以需要设置heightsBySectionForPortraitheightsBySectionForLandscape两个数组属性来分别保存高度,之后用heightsBySectionForCurrentOrientation来透明其中的判断过程。

    若命中缓存则调用- (CGFloat)heightForIndexPath:(NSIndexPath *)indexPath该方法进行缓存高度获取。方法实现细节为:

    - (CGFloat)heightForIndexPath:(NSIndexPath *)indexPath {
        [self buildCachesAtIndexPathsIfNeeded:@[indexPath]];
        NSNumber *number = self.heightsBySectionForCurrentOrientation[indexPath.section][indexPath.row];
    #if CGFLOAT_IS_DOUBLE
        return number.doubleValue;
    #else
        return number.floatValue;
    #endif
    }
    

    第二部分为没有命中缓存时所遇到的情况:若没有命中缓存,则需要调用- (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier configuration:(void (^)(id cell))configuration方法来计算相应的高度。该方法之前已经学习过,就不再废话了。 计算好高度之后需要调用- (void)cacheHeight:(CGFloat)height byIndexPath:(NSIndexPath *)indexPath方法来进行高度的缓存。

    - (void)cacheHeight:(CGFloat)height byIndexPath:(NSIndexPath *)indexPath {
        self.automaticallyInvalidateEnabled = YES;
        [self buildCachesAtIndexPathsIfNeeded:@[indexPath]];
        self.heightsBySectionForCurrentOrientation[indexPath.section][indexPath.row] = @(height);
    }
    

    根据上述实现可看到缓存的主要实现为 向self.heightsBySectionForCurrentOrientation数组中设置当前的高度值。

    通过key来缓存的实现

    该部分的主要使用- (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier cacheByKey:(id<NSCopying>)key configuration:(void (^)(id cell))configuration方法来实现:

    - (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier cacheByKey:(id<NSCopying>)key configuration:(void (^)(id cell))configuration {
        if (!identifier || !key) {
            return 0;
        }
        
        // Hit cache
        if ([self.fd_keyedHeightCache existsHeightForKey:key]) {
            CGFloat cachedHeight = [self.fd_keyedHeightCache heightForKey:key];
            [self fd_debugLog:[NSString stringWithFormat:@"hit cache by key[%@] - %@", key, @(cachedHeight)]];
            return cachedHeight;
        }
        
        CGFloat height = [self fd_heightForCellWithIdentifier:identifier configuration:configuration];
        [self.fd_keyedHeightCache cacheHeight:height byKey:key];
        [self fd_debugLog:[NSString stringWithFormat:@"cached by key[%@] - %@", key, @(height)]];
        
        return height;
    }
    

    可以看到基本也分为两个部分,命中缓存与未命中缓存的情况。

    首先第一部分为命中缓存部分,该部分使用- (BOOL)existsHeightForKey:(id<NSCopying>)key来进行判断。
    改函数实现细节为:

    - (BOOL)existsHeightForKey:(id<NSCopying>)key {
        NSNumber *number = self.mutableHeightsByKeyForCurrentOrientation[key];
        return number && ![number isEqualToNumber:@-1];
    }
    

    可以看到该方法和indexpath的缓存类似。就不过多介绍了。

    总结

    该框架主要的功能及其实现即为上述这些:
    1.提供两种缓存方式(cacheByIndexPathcacheByKey
    2.支持frame 和 autolayout两种方式的高度计算(- (CGFloat)fd_heightForCellWithIdentifier:(NSString *)identifier configuration:(void (^)(id cell))configuration方法)。
    3.利用runtime重写tableView的reloadData方法,来判断是否重置缓存标识以及判断是否清空缓存。

  • 2018/10/8 posted in  iOS三方框架源码学习

    2015年蓝桥杯省赛C/C++ A组题解

    方程整数解

    方程: a2 + b2 + c2 = 1000
    这个方程有整数解吗?有:a,b,c=6,8,30 就是一组解。
    你能算出另一组合适的解吗?
    请填写该解中最小的数字。
    注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

    直接暴力枚举。。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        for (int i=1;i<=33;i++) {
            for (int j=i;j<=33;j++) {
                for (int k=j;k<=33;k++) {
                    if (i*i+j*j+k*k==1000) {
                        printf("%d %d %d\n",i,j,k);
                    }
                }
            }
        }
        return 0;
    }
    

    答案是10.

    星系炸弹

    在X星系的广袤空间中漂浮着许多X星人造“炸弹”,用来作为宇宙中的路标。
    每个炸弹都可以设定多少天之后爆炸。
    比如:阿尔法炸弹2015年1月1日放置,定时为15天,则它在2015年1月16日爆炸。
    有一个贝塔炸弹,2014年11月9日放置,定时为1000天,请你计算它爆炸的准确日期。
    请填写该日期,格式为 yyyy-mm-dd
    即4位年份2位月份2位日期。比如:
    2015-02-19
    请严格按照格式书写。不能出现其它文字或符号。

    这个直接excel或者手算就可以了。。

    计算:
    2014.11. 9----2015. 1. 1 53天

    2015. 1. 1 ----2017. 1. 1 731天

    2017. 1. 1 ----2017. 8. 1 212天

    2017. 8. 1 ----2017. 8. 5 4天
    53+731+212+4=1000天

    Excel电子表格法:

    打开Excel电子表格,在单元格A1中输入2014/11/9,在单元格B1中输入公式=A1+1000即可得到答案。
    但是Excel中有效日期为1900年1月1日以后的日期,1900年以前的日期无法正常显示。

    奇妙的数字

    小明发现了一个奇妙的数字。它的平方和立方正好把0~9的10个数字每个用且只用了一次。
    你能猜出这个数字是多少吗?
    请填写该数字,不要填写任何多余的内容。

    还是暴力枚举就可以了。

    #include <bits/stdc++.h>
    using namespace std;
    
    int b[10];
    
    void solu(int x,int b[])
    {
        while (x) {
            b[x%10]++;
            x/=10;
        }
    }
    
    int main()
    {
        for (int i=1,j;i<9999;i++) {
            memset(b,0,sizeof(b));
            solu(i*i,b);
            solu(i*i*i,b);
            for (j=0;j<=9;j++)
                if (b[j]!=1) break;
            //每个b[i]都等于1,j才会大于9
            if (j>9) {
                printf("%d\n",i);
                break;
            }
        }
        return 0;
    }
    

    格子中输出

    StringInGrid函数会在一个指定大小的格子中打印指定的字符串。
    要求字符串在水平、垂直两个方向上都居中。
    如果字符串太长,就截断。
    如果不能恰好居中,可以稍稍偏左或者偏上一点。
    下面的程序实现这个逻辑,请填写划线部分缺少的代码。

    #include <stdio.h>
    #include <string.h>
    
    void StringInGrid(int width, int height, const char* s)
    {
        int i,k;
        char buf[1000];
        strcpy(buf, s);
        if(strlen(s)>width-2) buf[width-2]=0;
        
        printf("+");
        for(i=0;i<width-2;i++) printf("-");
        printf("+\n");
        
        for(k=1; k<(height-1)/2;k++){
            printf("|");
            for(i=0;i<width-2;i++) printf(" ");
            printf("|\n");
        }
        
        printf("|");
        
        printf("%*s%s%*s",_____________________________________________);  //填空
                  
        printf("|\n");
        
        for(k=(height-1)/2+1; k<height-1; k++){
            printf("|");
            for(i=0;i<width-2;i++) printf(" ");
            printf("|\n");
        }   
        
        printf("+");
        for(i=0;i<width-2;i++) printf("-");
        printf("+\n");  
    }
    
    int main()
    {
        StringInGrid(20,6,"abcd1234");
        return 0;
    }
    

    很明显,填空的上面是输出上半部分,下面是输出下半部分,所以我们填的这个就是正中间那行。
    要做这题首先要知道%*s是个什么。。。
    反正当年是没填出的居多 输出控制符
    也就是说碰到*的时候我们要额外给一个整型参数控制宽度。

    我们看到第9行,buf已经完成了截断,而s没有截断,所以我们要用也只能用buf。
    然后我们算出左边右边的宽度,值得注意的是,左右的宽度表达式是不一样的。
    因为题目里说了不对称是要靠左,
    可以把abcd1234最后的4去掉看看效果。
    感觉查了这么多博客都没一个人填对的。。。唉= =

    答案:(width-strlen(buf)-2)/2,"",buf,(width-strlen(buf)-2+1)/2,""

    九数组分数

    1,2,3…9 这九个数字组成一个分数,其值恰好为1/3,如何组法?
    下面的程序实现了该功能,请填写划线部分缺失的代码。

    #include <stdio.h>
    
    void test(int x[])
    {
        int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
        int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
    
        if(a*3==b) printf("%d / %d\n", a, b);
    }
    
    void f(int x[], int k)
    {
        int i,t;
        if(k>=9){
            test(x);
            return;
        }
    
        for(i=k; i<9; i++){
            {t=x[k]; x[k]=x[i]; x[i]=t;}
            f(x,k+1);
            _________________________________ // 填空处
        }
    }
    
    int main()
    {
        int x[] = {1,2,3,4,5,6,7,8,9};
        f(x,0);  
        return 0;
    }
    

    这主要考的是回溯的基本概念 回溯资料

    简单的说这一次做的改变肯定要复原。

    答案:{t=x[k]; x[k]=x[i]; x[i]=t;}

    牌型种数

    小明被劫持到X赌城,被迫与其他3人玩牌。
    一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。
    这时,小明脑子里突然冒出一个问题:
    如果不考虑花色,只考虑点数,也不考虑自己得到的牌的先后顺序,自己手里能拿到的初始牌型组合一共有多少种呢?

    请填写该整数,不要填写任何多余的内容或说明文字。

    dfs,当然首先要知道每个数字都有四张牌。

    #include <bits/stdc++.h>
    using namespace std;
    
    int cnt[15],ans=0;
    
    void dfs(int dep,int last)
    {
        if (dep>13) {
            ans++;
            return;
        }
        for (int i=last;i<=13;i++) {
            if (cnt[i]<4) {
                cnt[i]++;
                dfs(dep+1,i);
                cnt[i]--;
            }
        }
    }
    
    int main()
    {
        dfs(1,1);
        printf("%d\n",ans);
        return 0;
    }
    

    答案:3598180

    手链样式

    小明有3颗红珊瑚,4颗白珊瑚,5颗黄玛瑙。
    他想用它们串成一圈作为手链,送给女朋友。
    现在小明想知道:如果考虑手链可以随意转动或翻转,一共可以有多少不同的组合样式呢? 请你提交该整数。不要填写任何多余的内容或说明性的文字。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    
    int res[10000][12],a[12];
    
    bool same(int a[],int b[])
    {
        for (int k=0;k<12;k++) {
            bool f=true;
            for (int i=0;i<12;i++) {
                if (a[i]!=b[(i+k)%12]) {        //因为是环形,不固定起点。所以用(i+k)%12
                    f=false;
                    break;
                }
            }
            if (f) return true;
            f=true;
            for (int i=0;i<12;i++) {
                if (a[11-i]!=b[(i+k)%12]) {     //又因为可以翻转所以 从左边或者右边都应该检查。
                    f=false;
                    break;
                }
            }
            if (f) return true;
        }
        return false;
    }
    
    int main()
    {
        int ans=0;
        a[0]=a[1]=a[2]=1;
        a[3]=a[4]=a[5]=a[6]=2;
        a[7]=a[8]=a[9]=a[10]=a[11]=3;
        do {
            bool ok=true;
            for (int i=1;i<=ans;i++) {
                if (same(res[i],a)) {
                    ok=false;
                    break;
                }
            }
            if (ok) {
                ans++;
                for (int i=0;i<12;i++) {
                    res[ans][i]=a[i];
                }
            }
        } while (next_permutation(a,a+12));
        printf("%d\n",ans);
        return 0;
    }
    
    

    首先来分析一下题目:3类珠子,一共12个,我们用字符串a="333444455555“表示,要求环形的排列数,注意理解可以随意转动或翻转,这跟直线型的有不同。举个例子:

    例如,在直线型排列中a="333444455555“ 和 b="444455555333“ 是不同的排列,原因是直线型的起点是固定的,对应位置元素只要有一个不同,则排列不同。但是在环形里面,由于可以任意转动,也就是起点不固定的,当b以第一个3为起点时往右数时,它就和a完全一样了。另外,任意翻转的意思是b不但起点不固定,而且排列的方向可以往右数,也可以往左数。

    dfs写起来比较难受,这题就用next_permutation,改函数的方法是对数组从低到高逐次进行全排列。若可以进行排列就返回true,反之false
    所以只要把所有答案都记录下来,每次都正反判断一遍即可。

    饮料换购

    乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料,凭3个瓶盖可以再换一瓶C型饮料,并且可以一直循环下去(但不允许暂借或赊账)。
    请你计算一下,如果小明不浪费瓶盖,尽量地参加活动,那么,对于他初始买入的n瓶饮料,最后他一共能喝到多少瓶饮料。

    输入:一个整数n,表示开始购买的饮料数量(0 < n < 10000)
    输出:一个整数,表示实际得到的饮料数
    例如:
    用户输入:
    100
    程序应该输出:
    149
    用户输入:
    101
    程序应该输出:
    151
    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 1000ms

    这道题简单模拟即可。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        int s,n;
        scanf("%d",&n);
        s=n;
        while (n>=3) {
            s+=n/3;
            n=n/3+n%3;
        }
        printf("%d\n",s);
        return 0;
    }
    
    2018/2/28 posted in  蓝桥杯题目

    2016年第七届蓝桥杯C/C++程序设计本科B组省赛

    1.煤球数目

    有一堆煤球,堆成三角棱锥形。具体:
    第一层放1个,
    第二层3个(排列成三角形),
    第三层6个(排列成三角形),
    第四层10个(排列成三角形),
    ....
    如果一共有100层,共有多少个煤球?

    请填表示煤球总数目的数字。

    思路:1 2 3 4 5 6……这一个等差数列的前n项和为(1+n)*n/2

    第1层的煤球数目为1

    第2层的煤球数目为1+2

    第3层的煤球数目为1+2+3

    ……

    第i层的煤球数组为(1+n)*n/2

    #include <iostream>
    using namespace std;
    int main()
    {
        int sum=0,n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            sum+=i*(i+1)/2;
        }
        cout<<sum<<endl;
        return 0;
    }
    
    

    2.生日蜡烛

    某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。
    现在算起来,他一共吹熄了236根蜡烛。
    请问,他从多少岁开始过生日party的?
    请填写他开始过生日party的年龄数

    思路:1 2 3 4 5 6……这一个等差数列的前n项和为(1+n)*n/2

    设从a岁开始过生日,到了b岁一共吹熄了236根蜡烛。

    即为:(a+b)(b-a+1)/2=236

    #include <iostream>
    using namespace std;
    int main()
    {
        for(int i=1;i<=100;i++)
            for(int j=i;j<=100;j++)
            {
                if((i+j)*(j-i+1)/2==236)
                    cout<<i<<" "<<j<<endl;
            }
        
        return 0;
    }
    
    

    3.凑算式

    如图,这个算式中A~I代表1~9的数字,不同的字母代表不同的数字。

    比如:
    6+8/3+952/714 就是一种解法,
    5+3/1+972/486 是另一种解法。

    这个算式一共有多少种解法?

    思路:暴力解决,注意每个字母代表的数字不相等。

    答案:29

    #include <iostream>
    using namespace std;
    int main()
    {
        int sum=0;
        for(int a=1; a<=9; a++)
            for(int b=1; b<=9; b++)
            {
                if(a==b) continue;
                for(int c=1; c<=9; c++)
                {
                    if(c==a||c==b) continue;
                    for(int d=1; d<=9; d++)
                    {
                        if(d==a||d==b||d==c)continue;
                        for(int e=1; e<=9; e++)
                        {
                            if(e==a||e==b||e==c||e==d) continue;
                            for(int f=1; f<=9; f++)
                            {
                                if(f==a||f==b||f==c||f==d||f==e) continue;
                                for(int g=1; g<=9; g++)
                                {
                                    if(g==a||g==b||g==c||g==d||g==e||g==f) continue;
                                    for(int h=1; h<=9; h++)
                                    {
                                        if(h==a||h==b||h==c||h==d||h==e||h==f||h==g) continue;
                                        for(int i=1; i<=9; i++)
                                        {
                                            if(i==a||i==b||i==c||i==d||i==e||i==f||i==g||i==h) continue;
                                            int t1=a*c*(100*g+10*h+i);
                                            int t2=b*(100*g+10*h+i);
                                            int t3=c*(100*d+10*e+f);
                                            int t4=10*c*(100*g+10*h+i);
                                            if(t1+t2+t3==t4)
                                                sum++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
    
        cout<<sum<<endl;
        return 0;
    }
    

    4.快速排序

    排序在各种场合经常被用到。
    快速排序是十分常用的高效率的算法。

    其思想是:先选一个“标尺”,
    用它把整个队列过一遍筛子,
    以保证:其左边的元素都不大于它,其右边的元素都不小于它。

    这样,排序问题就被分割为两个子区间。
    再分别对子区间排序就可以了。

    下面的代码是一种实现,请分析并填写划线部分缺少的代码。

    #include <stdio.h>
    
    void swap(int a[], int i, int j)
    {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    
    int partition(int a[], int p, int r)
    {
        int i = p;
        int j = r + 1;
        int x = a[p];
        while(1){
            while(i<r && a[++i]<x);
            while(a[--j]>x);
            if(i>=j) break;
            swap(a,i,j);
        }
        _______________;//填空位置
        return j;
    }
    
    void quicksort(int a[], int p, int r)
    {
        if(p<r){
            int q = partition(a,p,r);
            quicksort(a,p,q-1);
            quicksort(a,q+1,r);
        }
    }
        
    int main()
    {
        int i;
        int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
        int N = 12;
        
        quicksort(a, 0, N-1);
        
        for(i=0; i<N; i++) printf("%d ", a[i]);
        printf("\n");
        
        return 0;
    }
    
    

    思路:快速排序,填空位置为经过比较之后,将最初选的“标尺”放在中间,即:标尺左边的数小于标尺,右边的数则大于它。注意不要多填分号。

    答案:swap(a,p,j)

    网友年龄(A组)

    某君新认识一网友。 当问及年龄时,他的网友说: “我的年龄是个2位数,我比儿子大27岁, 如果把我的年龄的两位数字交换位置,刚好就是我儿子的年龄”
    请你计算:网友的年龄一共有多少种可能情况?
    提示:30岁就是其中一种可能哦. 请填写表示可能情况的种数。
    注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

    #include <iostream>
    using namespace std;
    int main()
    {
        int m = 0;
        for(int i=0;i<=9;i++)
            for(int j=0;j<=9;j++)
            {
                if(9*(i-j)==27){
                    m++;
                }
                    
            }
        cout<<m<<endl;
        return 0;
    }
    
    

    枚举一下:7

    方格填数

    如下的10个格子

    填入0~9的数字。要求:连续的两个数字不能相邻。 (左右、上下、对角都算相邻)
    一共有多少种可能的填数方案?
    请填写表示方案数目的整数。
    注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

    #include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    using namespace std;
    
    /*本来要判断八个格子,
     *但是由于是从左往右从上往下填的,
     *只要判断左、左上、上、右上
     */
    const int dx[]={0,-1,-1,-1};
    const int dy[]={-1,-1,0,1};
    const int INF=1e9;
    bool used[10];
    int ans=0;
    int a[5][5];
    
    bool alright(int n,int x,int y)
    {
        for (int i=0;i<4;i++) {
            int xx=x+dx[i],yy=y+dy[i];
            if (xx<1||yy<1||xx>3||yy>4) continue;
            if (abs(n-a[xx][yy])==1) return false;
        }
        return true;
    }
    
    void dfs(int x,int y)
    {
        if (x==3&&y==4) {
            ans++;
            return;
        }
        for (int i=0;i<=9;i++) {
            if (!used[i]&&alright(i,x,y)) {
                a[x][y]=i;
                used[i]=true;
                if (y==4) dfs(x+1,1);
                else dfs(x,y+1);
                used[i]=false;
                a[x][y]=-INF;
            }
        }
    }
    
    int main()
    {
        for (int i=1;i<=3;i++) {
            for (int j=1;j<=4;j++) {
                a[i][j]=-INF;
            }
        }
        dfs(1,2);
        printf("%d\n",ans);
        return 0;
    }
    
    

    正确答案:1580

    消除尾一

    下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0
    如果最后一位是0,则原数字保持不变。
    如果采用代码中的测试数据,应该输出:

    00000000000000000000000001100111 00000000000000000000000001100000
    00000000000000000000000000001100 00000000000000000000000000001100

    请仔细阅读程序,填写划线部分缺少的代码。

    #include <stdio.h>
    
    void f(int x) 
    {  
        int i; 
        for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);  
        printf("   ");
    
        x = _______________________;   
    
        for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);  
        printf("\n");  
    }
    
    int main() 
    { 
        f(103);  
        f(12);  
        return 0; 
    }
    

    要消除x末尾所有的1,可以先把x加上1:

    00000000000000000000000001100111 + 1 =
    00000000000000000000000001101000

    答案为:x&(x+1)

    寒假作业

    现在小学的数学题目也不是那么好玩的。
    看看这个寒假作业:
    □ + □ = □
    □ - □ = □
    □ × □ = □
    □ ÷ □ = □
    每个方块代表1~13中的某一个数字,但不能重复。
    比如:
    6 + 7 = 13
    9 - 8 = 1
    3 * 4 = 12
    10 / 2 = 5
    以及:
    7 + 6 = 13
    9 - 8 = 1
    3 * 4 = 12
    10 / 2 = 5
    就算两种解法。(加法,乘法交换律后算不同的方案)
    你一共找到了多少种方案?
    请填写表示方案数目的整数。
    注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

    #include <bits/stdc++.h>
    using namespace std;
    
    bool used[15];
    int a[15];
    int ans=0;
    
    void dfs(int dep)
    {
        if (dep==13) {
            //必须整除,变成乘法判断
            if (a[10]==a[11]*a[12]) ans++;
            return;
        }
        if (dep==10) {
            if (a[7]*a[8]!=a[9]) return;
        }
        if (dep==7) {
            if (a[4]-a[5]!=a[6]) return;
        }
        if (dep==4) {
            if (a[1]+a[2]!=a[3]) return;
        }
        for (int i=1;i<=13;i++) {
            if (!used[i]) {
                used[i]=true;
                a[dep]=i;
                dfs(dep+1);
                a[dep]=-1;
                used[i]=false;
            }
        }
    }
    
    int main()
    {
        dfs(1);
        printf("%d\n",ans);
        return 0;
    }
    

    **答案:64 **

    剪邮票

    如【图1.jpg】, 有12张连在一起的12生肖的邮票。
    现在你要从中剪下5张来,要求必须是连着的。 (仅仅连接一个角不算相连)
    比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。

    思路:先找到5个数的组合,然后从第一个数字开始遍历,经过上下左右操作检测5个数是否都被访问一遍,如果5个数都可以遍历到则种类+1。

    在原图中向上为-4,向下为+4,向左为-1,向右为+1,但是遇到3 4 5 7 8这种4+1=5但是这种情况不符合,所以重构一下原图:

    这样,向上为-5,向下为+5,向左为-1,向右为+1,避免了每行最后一个+1后等于下一行第一个的情况。

    #include <iostream>
    using namespace std;
    int mp[12]= {1,2,3,4,6,7,8,9,11,12,13,14};
    int aa[5],vis[5],sum=0;
    int b[4]= {-1,1,-5,+5};
    void dfs(int n)
    {
        for(int i=0; i<4; i++)
        {
            int t=aa[n]+b[i];
            if(t<1||t>14||t==5||t==10) continue;
            for(int j=0; j<5; j++)
                if(!vis[j]&&aa[j]==t)
                {
                    vis[j]=1;
                    dfs(j);
                }
        }
    }
    
    int main()
    {
    
        for(int a=0; a<12; a++)
            for(int b=a+1; b<12; b++)
                for(int c=b+1; c<12; c++)
                    for(int d=c+1; d<12; d++)
                        for(int e=d+1; e<12; e++)
                        {
                            aa[0]=mp[a];
                            aa[1]=mp[b];
                            aa[2]=mp[c];
                            aa[3]=mp[d];
                            aa[4]=mp[e];
                            for(int i=0; i<5; i++)
                                vis[i]=0;
                            vis[0]=1;
                            dfs(0);
                            int flag=1;;
                            for(int i=0; i<5; i++)
                            {
                                if(vis[i]!=1)
                                {
                                    flag=0;
                                    break;
                                }
                            }
                            if(flag==0) continue;
                            else
                                sum++;
                        }
    
        cout<<sum<<endl;
    
        return 0;
    }
    

    答案:116

    四平方和

    四平方和定理,又称为拉格朗日定理:
    每个正整数都可以表示为至多4个正整数的平方和。
    如果把0包括进去,就正好可以表示为4个数的平方和。
    比如:
    5 = 02 + 02 + 12 + 22
    7 = 12 + 12 + 12 + 22
    符号表示乘方的意思)
    对于一个给定的正整数,可能存在多种平方和的表示法。
    要求你对4个数排序: 0 <= a <= b <= c <= d
    并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法
    程序输入为一个正整数N (N<5000000)
    要求输出4个非负整数,按从小到大排序,中间用空格分开
    例如,输入:
    5
    则程序应该输出:
    0 0 1 2
    再例如,输入:
    12
    则程序应该输出:
    0 2 2 2
    再例如,输入:
    773535
    则程序应该输出:
    1 1 267 838
    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 3000ms

    直接暴力解决。。

    #include <iostream>
    #include <math.h>
    using namespace std;
    int mp[12]= {1,2,3,4,6,7,8,9,11,12,13,14};
    int aa[5],vis[5],sum=0;
    int b[4]= {-1,1,-5,+5};
    
    void resolve(int n){
        for (int d = 0; d<=sqrt(n); d++) {
            for (int c=0; c<=sqrt(n); c++) {
                for (int b=0; b<=sqrt(n); b++) {
                    for (int a=0; a<=sqrt(n); a++) {
                        if (a*a+b*b+c*c+d*d==n) {
                            cout<<d<<c<<b<<a<<endl;
                            return;
                        }
                    }
                }
            }
        }
    }
    
    int main()
    {
        int n=0;
        cin>>n;
        resolve(n);
        return 0;
    }
    
    

    密码脱落

    X星球的考古学家发现了一批古代留下来的密码。
    这些密码是由A、B、C、D 四种植物的种子串成的序列。
    仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
    由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。
    你的任务是: 给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。
    输入一行,表示现在看到的密码串(长度不大于1000)
    要求输出一个正整数,表示至少脱落了多少个种子。
    例如,输入:
    ABCBA
    则程序应该输出:
    0
    再例如,输入:
    ABDCDCBABC
    则程序应该输出:
    3
    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 1000ms


    由于是对称的,所以本体可以使用动态规划来将原字符串跟逆序字符串进行比较,来求最大公共子序列(不是串,可以是不连续的)

    dp[i][j]保存的是原串的i号位置之前的所有字符跟逆序串的j号位置之前的所有字符的最大公共子序列(包括i,j号位置)

    最后用当前字符串长度n减去dp[n][n]就是结果,dp[n][n]是对所有字符进行计算之后的结果。


    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    
    char s[1010];
    int dp[1010][1010];
    
    int main()
    {
        scanf("%s",s+1);
        int n=strlen(s+1);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++) {
                if (s[i]==s[n+1-j]) {
                    dp[i][j]=dp[i-1][j-1]+1;
                } else {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        printf("%d\n",n-dp[n][n]);
        return 0;
    }
    
    2018/2/27 posted in  蓝桥杯题目

    2017第八届蓝桥杯C/C++ B组省赛

    第一题 购物单

    小明刚刚找到工作,老板人很好,只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦,但又不好推辞。

    这不,XX大促销又来了!老板夫人开出了长长的购物单,都是有打折优惠的。
    小明也有个怪癖,不到万不得已,从不刷卡,直接现金搞定。
    现在小明很心烦,请你帮他计算一下,需要从取款机上取多少现金,才能搞定这次购物。

    取款机只能提供100元面额的纸币。小明想尽可能少取些现金,够用就行了。
    你的任务是计算出,小明最少需要取多少现金。

    以下是让人头疼的购物单,为了保护隐私,物品名称被隐藏了

    --------------------
    ****     180.90       88折
    ****      10.25       65折
    ****      56.14        9折
    ****     104.65        9折
    ****     100.30       88折
    ****     297.15       半价
    ****      26.75       65折
    ****     130.62       半价
    ****     240.28       58折
    ****     270.62        8折
    ****     115.87       88折
    ****     247.34       95折
    ****      73.21        9折
    ****     101.00       半价
    ****      79.54       半价
    ****     278.44        7折
    ****     199.26       半价
    ****      12.97        9折
    ****     166.30       78折
    ****     125.50       58折
    ****      84.98        9折
    ****     113.35       68折
    ****     166.57       半价
    ****      42.56        9折
    ****      81.90       95折
    ****     131.78        8折
    ****     255.89       78折
    ****     109.17        9折
    ****     146.69       68折
    ****     139.33       65折
    ****     141.16       78折
    ****     154.74        8折
    ****      59.42        8折
    ****      85.44       68折
    ****     293.70       88折
    ****     261.79       65折
    ****      11.30       88折
    ****     268.27       58折
    ****     128.29       88折
    ****     251.03        8折
    ****     208.39       75折
    ****     128.88       75折
    ****      62.06        9折
    ****     225.87       75折
    ****      12.89       75折
    ****      34.28       75折
    ****      62.16       58折
    ****     129.12       半价
    ****     218.37       半价
    ****     289.69       8折
    --------------------
    

    需要说明的是,88折指的是按标价的88%计算,而8折是按80%计算,余者类推。
    特别地,半价是按50%计算。

    请提交小明要从取款机上提取的金额,单位是元。
    答案是一个整数,类似4300的样子,结尾必然是00,不要填写任何多余的内容。

    特别提醒:不许携带计算器入场,也不能打开手机。

    解答: 就是基本的运算。

    #include<stdio.h>
    main()
    {
        float a;
        a = 180.90*0.88+10.25*0.65+56.14*0.9+104.65*0.9+100.3*0.88+297.15*0.5+26.75*0.65+130.62*0.5 
        +240.28*0.58+270.62*0.8+115.87*0.88+247.34*0.95+73.21*0.9+101*0.5+79.54*0.5+278.44*0.7+199.26*0.5 
        +12.97*0.9+166.30*0.78+125.50*0.58+84.98*0.9+113.35*0.68+166.57*0.5+42.56*0.9+81.90*0.95 
        +131.78*0.8+255.89*0.78+109.17*0.9+146.69*0.68+139.33*0.65+141.16*0.78+154.74*0.8+59.42*0.8 
        +85.44*0.68+293.70*0.88+261.79*0.65+11.30*0.88+268.27*0.58+128.29*0.88+251.03*0.8+208.39*0.75 
        +128.88*0.75+62.06*0.9+225.87*0.75+12.89*0.75+34.28*0.75+62.16*0.58+129.12*0.5+218.37*0.5+289.69*0.8; 
        printf("%f",a);
    } 
    

    算出来结果为5136.859375 取钱应为5200

    第二题 等差素数列

    2,3,5,7,11,13,....是素数序列。

    类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。
    上边的数列公差为30,长度为6。

    2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。
    这是数论领域一项惊人的成果!

    有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:

    长度为10的等差素数列,其公差最小值是多少?

    注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字。

    先用素数筛筛出素数,然后暴力

    #include <stdio.h>
    #include <memory.h>
    #include <iostream>
    using namespace std;
    int p[100010];
    int prim[100010];
    int len=0;
    void isp()
    {
        //构造素数数列
        memset(p,0,sizeof(p));
        p[0]=1;p[1]=1;p[2]=0;
        for(int i=0;i<10000;i++)
        {
            if(p[i])
                continue;
            for(int j=i;j*i<10000;j++)
            {
                p[i*j]=1;
            }
            prim[len++]=i;
        }
        
    }
    int main()
    {
        isp();
        for(int i=0;i<len;i++)
        {
            int ss=prim[i];  //记录当前素数
            for(int c=1;c<1000;c++)     //c为公差
            {
                int j;
                for(j=1;j<10;j++)
                {
                    if(p[ss+c*j])
                        break;
                }
                if(j>=10)
                {
                    cout<<c<<' '<<ss<<endl;
                    return 0;
                }
            }
        }
    }
    

    答案为210.

    第三题 承压计算

    X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。

    每块金属原料的外形、尺寸完全一致,但重量不同。
    金属材料被严格地堆放成金字塔形。

                                 7 
                                5 8 
                               7 8 8 
                              9 2 7 2 
                             8 1 4 9 1 
                            8 1 8 8 4 1 
                           7 9 6 1 4 5 4 
                          5 6 5 5 6 9 5 6 
                         5 5 4 7 9 3 5 5 1 
                        7 5 7 9 7 4 7 3 3 1 
                       4 6 4 5 5 8 8 3 2 4 3 
                      1 1 3 3 1 6 6 5 5 4 4 2 
                     9 9 9 2 1 9 1 9 2 9 5 7 9 
                    4 3 3 7 7 9 3 6 1 3 8 8 3 7 
                   3 6 8 1 5 3 9 5 8 3 8 1 8 3 3 
                  8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9 
                 8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4 
                2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9 
               7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6 
              9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3 
             5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9 
            6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4 
           2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4 
          7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6 
         1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3 
        2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8 
       7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9 
      7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6 
     5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1 
    X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 
    

    其中的数字代表金属块的重量(计量单位较大)。
    最下一层的X代表30台极高精度的电子秤。

    假设每块原料的重量都十分精确地平均落在下方的两个金属块上,
    最后,所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
    电子秤的计量单位很小,所以显示的数字很大。

    工作人员发现,其中读数最小的电子秤的示数为:2086458231

    请你推算出:读数最大的电子秤的示数为多少?

    注意:需要提交的是一个整数,不要填写任何多余的内容。

    只要把第i行的第j个平均分给第i+1行的第j个和第i+1行的第j+1个

    #include <stdio.h>
    #include <iostream>
    using namespace std;
    double num[35][35];
    int main()
    {
        for(int i=1;i<=29;i++)
            for(int j=1;j<=i;j++)
                cin>>num[i][j];
        for(int i=1;i<=29;i++){
            for(int j=1;j<=i;j++)
            {
                num[i+1][j]+=num[i][j]/2;
                num[i+1][j+1]+=num[i][j]/2;
            }
        }
        double maxn=-1;
        double minn=INT_MAX;
        for(int i=1;i<=30;i++)
        {
            if(maxn<num[30][i]) maxn=num[30][i];
            if(minn>num[30][i]) minn=num[30][i];
        }
        printf("%lf",maxn*2086458231/minn);  //进行单位的的换算
    }
    

    第四题 方格分割

    6x6的方格,沿着格子的边线剪开成两部分。
    要求这两部分的形状完全相同。

    如图:p1.png, p2.png, p3.png 就是可行的分割法。

    试计算:
    包括这3种分法在内,一共有多少种不同的分割方法。
    注意:旋转对称的属于同一种分割法。

    请提交该整数,不要填写任何多余的内容或说明文字。

    应该把边当成走廊,因为剪出的是中心对称,所以必定经过(3,3)
    所以可以从(3,3)开始出发两个人以中心对称的方式出发,当走到边界的时候两个人走的路线就是剪开的线路
    因为是中心对称,这样出来的答案应该除以4

    #include <stdio.h>
    #include <iostream>
    using namespace std;
    int visited[10][10];
    int ans=0;
    int dir[4][2]={0,1,1,0,0,-1,-1,0};
    void dfs(int x,int y)
    {
        if(x==0||y==0||x==6||y==6)
        {
            ans++;
            return ;
        }
        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(visited[nx][ny])
                continue;
            visited[nx][ny]=1;
            visited[6-nx][6-ny]=1;
            dfs(nx,ny);
            visited[nx][ny]=0;      //上次路线假设情况求取后 ,将路线标记置为0
            visited[6-nx][6-ny]=0;  //同上对称图形也将路线标记置为0
        }
    }
    int main()
    {
        memset(visited,0,sizeof(visited));
        visited[3][3]=1;
        dfs(3,3);
        printf("%d %d\n",ans,ans/4);
    }
    

    第六题 最大公共子串

    最大公共子串长度问题就是:
    求两个串的所有子串中能够匹配上的最大长度是多少。

    比如:"abcdkkk" 和 "baabcdadabc",
    可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

    下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。

    请分析该解法的思路,并补全划线部分缺失的代码。

    #include <stdio.h>
    #include <string.h>
    
    #define N 256
    int f(const char* s1, const char* s2)
    {
        int a[N][N];
        int len1 = strlen(s1);
        int len2 = strlen(s2);
        int i,j;
    
        memset(a,0,sizeof(int)*N*N);
        int max = 0;
        for(i=1; i<=len1; i++){
            for(j=1; j<=len2; j++){
                if(s1[i-1]==s2[j-1]) {
                    a[i][j] = __________________________;  //填空
                    if(a[i][j] > max) max = a[i][j];
                }
            }
        }
    
        return max;
    }
    
    int main()
    {
        printf("%d\n", f("abcdkkk", "baabcdadabc"));
        return 0;
    }
    

    基础dp,答案:a[i-1][j-1]+1

    第七题 日期问题

    小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。

    比如02/03/04,可能是2002年03月04日、2004年02月03日或2004年03月02日。

    给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?

    输入

    一个日期,格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)

    输出

    输出若干个不相同的日期,每个日期一行,格式是"yyyy-MM-dd"。多个日期按从早到晚排列。

    样例输入

    02/03/04

    样例输出

    2002-03-04

    2004-02-03

    2004-03-02

    资源约定:
    峰值内存消耗(含虚拟机) < 256M
    CPU消耗 < 1000ms

    注意:
    main函数需要返回0;
    只使用ANSI C/ANSI C++ 标准;
    不要调用依赖于编译环境或操作系统的特殊函数。
    所有依赖的函数必须明确地在源文件中 #include
    不能通过工程设置而省略常用头文件。

    提交程序时,注意选择所期望的语言类型和编译器类型。

    只有年/月/日的,月/日/年的,日/月/年三种情况

    #include <cstdio>
    #include <cstring>
    using namespace std;
    int time[150][15][35];
    bool pd(int n,int y,int r)
    {
        int rn=0;
        if(n%400==0||(n%100!=0&&n%4==0))
            rn=1;
        if(n==1||n==3||n==5||n==7||n==8||n==10||n==12)
            if(r>31) return 0;
        if(n==4||n==6||n==9||n==11)
            if(r>30) return 0;
        if(n==2)
            if(r>28+rn) return 0;
        return 1;
    }
    
    int main()
    {
        int a,b,c;
        //memset(time,0,sizeof(time));
        scanf("%d/%d/%d",&a,&b,&c);
        if(a>=60&&b<=12&&c<=31)
            time[a-60][b][c]=1;
        if(a<60&&b<=12&&c<=31)
            time[a+40][b][c]=1;
        
        if(c>=60&&a<=12&&b<=31)
            time[c-60][a][b]=1;
        if(c<60&&a<=12&&c<=31)
            time[c+40][a][b]=1;
        
        if(c>=60&&b<=12&&a<=31)
            time[c-60][b][a]=1;
        if(c<60&&b<=12&&a<=31)
            time[c+40][b][a]=1;
        for(int i=0;i<=100;i++)
            for(int j=1;j<=12;j++)
                for(int k=1;k<=31;k++)
                    if(time[i][j][k]==1)
                    {
                        if(pd(i,j,k))
                        {
                            
                            printf("%d-",i+1960);
                            if(j<9)
                                printf("0%d-",j);
                            else
                                printf("%d-",j);
                            if(k<9)
                                printf("0%d\n",k);
                            else
                                printf("%d\n",k);
                        }
                    }
    }
    
    

    第八题 包子凑数

    小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。

    每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。

    当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。

    小明想知道一共有多少种数目是包子大叔凑不出来的。

    这题可以使用欧几里得拓展算法:
    对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然
    存在整数对 x,y ,使得 gcd(a,b)=ax+by。

    简单的说就是当所有的输入的最大公约数都为1时,为有限个,否则为无限个。

    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    bool judge(int x,int y)
    {
        int t;
        while(y>0)
        {
            t=x%y;
            x=y;
            y=t;
        }
        if(x==1)
            return true;
        return false;
    }
    
    int a[110],n;
    bool dp[10010];
    int main()
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        int  flag=0;
        for(int i=0;i<n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(judge(a[i],a[j]))
                {
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                break;
        }
        if(flag!=1)
        {
            printf("INF\n");
            return 0;
        }
        dp[0]=1;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j+a[i]<10000; j++)
                if(dp[j])
                    dp[j+a[i]]=1;
        }
        int ans=0;
        for(int i=0; i<10000; i++)
        {
            if(dp[i]!=1)
                ans++;
        }
        printf("%d\n",ans);
        return 0;
    }
    
    

    第九题 分巧克力

    儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
    小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:
    1. 形状是正方形,边长是整数

    2. 大小相同

    例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

    当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?

    输入
    第一行包含两个整数N和K。(1 <= N, K <= 100000)

    以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
    输入保证每位小朋友至少能获得一块1x1的巧克力。

    输出
    输出切出的正方形巧克力最大可能的边长。

    样例输入:
    2 10

    6 5

    5 6

    样例输出:
    2

    资源约定:
    峰值内存消耗(含虚拟机) < 256M
    CPU消耗 < 1000ms

    #include <stdio.h>
    #define N 100005
    using namespace std;
    int n,k;
    struct cho
    {
        int h;
        int w;
    };
    cho c[N];
    bool judge(int len)
    {
        int sum=0;
        for(int i=0;i<len;i++)
        {
            sum+=(c[i].h/len)*(c[i].w/len);
            if(sum>=k)
                return 1;
        }
        return 0;
    }
    int main()
    {
        scanf("%d%d",&n,&k);
        int low=1;
        int high=100000;
        int mid;
        for(int i=0; i<n; i++)
            scanf("%d%d",&c[i].h,&c[i].w);
        while(low<high-1)
        {
            mid=(low+high)/2;
            if(!judge(mid))
                high=mid;
            else
                low=mid;
        }
        printf("%d\n",mid-1);
        return 0;
    }
    
    

    第十题 k倍区间

    给定一个长度为N的数列,A1, A2, ... AN,如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。

    你能求出数列中总共有多少个K倍区间吗?

    输入

    第一行包含两个整数N和K。(1 <= N, K <= 100000)

    以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

    输出

    输出一个整数,代表K倍区间的数目。

    例如,
    输入:
    5 2
    1

    2

    3

    4

    5

    程序应该输出:
    6

    资源约定:
    峰值内存消耗(含虚拟机) < 256M
    CPU消耗 < 2000ms

    可通过滑动窗口的方法来解,提前对数据进行处理可缩短执行时间

    #include <stdio.h>
    using namespace std;
    int a[100010];
    long long dp[100010];
    int main()
    {
        int n,k,i,j;
        scanf("%d%d",&n,&k);
        dp[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            dp[i]=dp[i-1]+a[i];     //累加之前的数字
        }
        int ans=0;
        for(i=1;i<=n;i++)
        {
            for(j=0;j<=n-i;j++)
            {
                if((dp[j+i]-dp[j])%k==0)    //通过调整i,j来循环判断,这里i表示区间的长度,j为向右滑动步数。
                    ans++;
            }
        }
        printf("%d\n",ans);
        return 0;
    }
    
    
    2018/2/26 posted in  蓝桥杯题目

    Longest Word in Dictionary through Deleting

    比较字符的大小时,若字符串a的首字符大于b的首字符则a比较大,不对后续字符进行判断。

    class Solution {
    public:
        string findLongestWord(string s, vector<string>& d) {
                string ans;
                for (int i = 0; i < d.size(); i++) {
                    int pi = 0, pj = 0;
                    for (; pi < s.size() && pj < d[i].size(); pi++) {
                        pj += s[pi] == d[i][pj];
                    }
                    if (pj == d[i].size() && (ans.size() < d[i].size() || (ans.size() == d[i].size() && ans > d[i])))
                        ans = d[i];
                }
                return ans;
            }
    };
    
    2018/1/22 posted in  leetcode