银河美术馆-Beautyyu

1

观察易得 答案实际上是一个杨辉三角形分别乘上对应数字的和

杨辉三角形

直接打表即可

    int yanghui[13][13] = {{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,0,0,0,0,0,0,0,0,0},
{0,1,2,1,0,0,0,0,0,0,0,0,0},
{0,1,3,3,1,0,0,0,0,0,0,0,0},
{0,1,4,6,4,1,0,0,0,0,0,0,0},
{0,1,5,10,10,5,1,0,0,0,0,0,0},
{0,1,6,15,20,15,6,1,0,0,0,0,0},
{0,1,7,21,35,35,21,7,1,0,0,0,0},
{0,1,8,28,56,70,56,28,8,1,0,0,0},
{0,1,9,36,84,126,126,84,36,9,1,0,0},
{0,1,10,45,120,210,252,210,120,45,10,1,0},
{0,1,11,55,165,330,462,462,330,165,55,11,1}
};

生成杨辉的代码

for (int i = 1;i <= 12;++ i){
        yanghui[i][1] = yanghui[i][i] = 1;
        for (int j = 2;j < i;++ j){
            yanghui[i][j] = yanghui[i - 1][j - 1]+yanghui[i - 1][j];
        }
    }printf("{");
    for (int i = 0;i <= 12;++ i){
        printf("{");
        for (int j = 0;j <= 11;++ j)
            printf("%d,",yanghui[i][j]);
        printf("%d},\n",yanghui[i][12]);
    }
    printf("}\n");

2

然后这道题就成了求1-n的全排列
这里我用了swap实现全排列

void dfs(int handle,int weight){
    for (int i = handle;i <= n;++ i){
        swap(arr[i],arr[handle]);
        dfs(handle + 1,weight + arr[handle] * yanghui[n][handle]);
        swap(arr[i],arr[handle]);
    }
    return ;
}

3

但这样不保证字典序
通过观察可以发现 杨辉三角满足轴对称
例如n = 4 时a b c d和a c b d和d b c a和d c b a这样不同的排序可以得到相同的sum
因此我在输出时强行把它变成字典序

if (handle > n && weight == m){
        for (int i = 1;i <= n;++ i)
        {
            if (i <= n / 2 && arr[n - i + 1] < arr[i])
                swap(arr[i],arr[n - i + 1]);
            printf("%d ",arr[i]);
        }
        exit(0);
    }

这个方法不确保答案的正确性 但在n<=12的规模下还是不会出问题的

4

最后加上一行剪枝if (weight >= m) return;

##看楼下的dalao都用了奇妙的操作

菜鸡啥也不会 只能想办法剪剪枝了
（勉强还是ac了
首先 通过观察可知这题其实是在求全排列
对于所有的排列方式 求出最小花费
我习惯通过swap的交换来实现全排列
此外就是 当当前花费已经大于已知的最佳答案 即减去这条枝 这样一个简单的剪枝
而这个剪枝在 尽快找到一个较优解 的情况下可以剪去更多的废枝
所以在开始搜索前通过**距离原点的远近**排序 可以稍微地“尽快找最优解”（虽然这有点玄学 我解释不了 但对于这题确实有效）

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>
using namespace std;
struct cheeseNode{
    double x,y;
}chee[16];
int n;
double ans = 2100000000.0;
double cou_dis(cheeseNode& al,cheeseNode& be){
     return sqrt((al.x - be.x)*(al.x - be.x)+(al.y - be.y)*(al.y - be.y));
}
void dfs(int handle,double dis){
    if (handle > n){
        ans = min(ans,dis);
        return;
    }
    if (dis >= ans) return;
    for (int i = handle;i <= n;++ i){
        swap(chee[i],chee[handle]);
        dfs(handle + 1,dis + cou_dis(chee[handle],chee[handle - 1]));
        swap(chee[i],chee[handle]);
    }
    return ;
}
bool cmp (cheeseNode al,cheeseNode be){
    return ((al.x * al.x + al.y * al.y) < (be.x * be.x + be.y * be.y));
}
int main (){
    // freopen ("workbroad.in","r",stdin);
    // freopen ("workbroad.out","w",stdout);
    cin >> n;
    double al,be;
    for (int i = 1;i <= n;++ i){
        scanf("%lf%lf",&al,&be);
        chee[i] = (cheeseNode){al,be};
    }
    sort(chee + 1,chee + n + 1,cmp);
    dfs(1,0);
    printf("%.2lf",ans);
    return 0;
}

本来是想拿这个题来练习双向bfs的 结果一开始连朴素写法都写不出来
终于坎坷地打完代码 所以来发个题解
双向bfs+map判重
如果不加双向会t一个点 加完就能ac
代码比较丑 大家将就看看吧

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <queue>
#include <map>//个人惯用的头文件
using namespace std;
struct xxx{
    string str;
    short i;
};//i表示0在串中的位置
bool check(int i,int d){//d是0移动的方向 详见下方dic数组
    if((i + d > 8)||(i + d < 0)) return 0;
    if((i % 3 == 0)&&(d == -1)) return 0;
    if((i % 3 == 2)&&(d == 1)) return 0;
    return 1;
}//分别判断0的位置进行变化后是否合法 
int dic[4] = {1,-1,3,-3};//0变化的四种方向
map <string,int> m1,m2;
queue <xxx> q1,q2;//两个队列和map别用于两个bfs方向
xxx st,ed;//起始和终止状态存储
int c,c1 = 1,c2 = 1,cc = 0;//分别表示计数器、当前层级正方向的状态总数、当前层级负方向的状态总数、当前层级
int bfs(){
    while (!q1.empty()){
        ++ cc;//更新当前层级
        xxx lx,x;//lx用于取出队首 x用于变化操作

        c = c1;
        c1 = 0;
        for (int i = 1;i <= c;++ i){//遍历当前层级正方向的所有状态
            lx = q1.front();q1.pop();//取队头

            for (int z = 0;z < 4;++ z){//四种移动方向
                x = lx;//重置x
                int d = dic[z];
                if(!check(x.i,d)) continue;//判断移动是否合法
                swap(x.str[x.i],x.str[x.i + d]);
                x.i += d;//更新x的状态

                if (m1[x.str]) continue;
                q1.push(x);m1[x.str] = 1;++ c1;//判断是否重复 不重复时将新状态存入队 且更新c1

                if (m2[x.str]) return cc * 2 - 1;//判断是否在上一层的反方向上出现过该状态 有则返回（当前层级+上一层层级）（即cc*2 - 1）
            }
        }
        //-------------------------------以下是反方向的处理 与正方向相同
        c = c2;
        c2 = 0;
        for (int i = 1;i <= c;++ i){
            lx = q2.front();q2.pop();

            for (int z = 0;z < 4;++ z){
                x = lx;
                int d = dic[z];
                if(!check(x.i,d)) continue;
                swap(x.str[x.i],x.str[x.i + d]);
                x.i += d;

                if (m2[x.str]) continue;
                q2.push(x);m2[x.str] = 1;++ c2;

                if (m1[x.str]) return cc * 2;//这里应为判断同层级的正方向是否出现过该状态 有则返回（当前层级+当前层级）
            }
        }
    }
}
int main (){
    cin >> st.str;
    for (int i = 0;i < 9;++ i){
            if(st.str[i] == '0')    st.i = i;
    }//读入 处理0的位置
    ed = (xxx){"123804765",4};
    q1.push(st);m1[st.str] = 1;
    q2.push(ed);m2[st.str] = 1;//初始化
    if(st == ed){
        printf("0");
        return 0;
    }//特判是否只有一个状态
    printf("%d",bfs());//进入bfs
    return 0;
}

##2017年最后一次发长说说##
这篇东西是在群里扯皮的同时写的

等我出来了 就把你工程删掉 ——致泽州和焖鱼

其实一年很快的
这一年开始的时候 应该还是初三上
emmmmm那是大概根本就没有考虑到毕业 没有想过毕业是个什么操作
然后突然就是初三下了 突然就百日誓师了 突然就猝不及防的毕业了
初三下是过的最长的一个学期 其实也是最开心的一段时间 有很多人和自己一样 就是一起念书一起念书 仿佛就是一群志同道合的人（错觉？学习是不可能学习的（逃
然后啊 当时一起偷卷子 一起抱着十几个台湾饭团边吃边写作业 感觉真的很棒 特别是离开六班之后才更加清楚（现在实在是颓废的不行
毕业后连续几个星期里 情绪就 非常压抑 一直没有恢复 不管是在南绿岛玩或者是毕业晚会 其实都很疲倦很疲倦
所以还是毕业了啊。。。
终于有一天还是毕业了

##说说暑假##
大家一到暑假 就变了很多很多 包括自己也是

这个暑假真的短的要命

是的 所以初中任何某某某老师说的好好学习 明年的暑假就轻松了都是骗局
先是七月中旬 第一次碰到了那些暴躁老哥和藏污纳垢的地方就卫生而言确实
然后就在济南 复活了微笙这么个社团
后来是夏令营 嗯 一个作息不清不楚毫不养生的夏令营
再然后就是军训 头三天可以说是特别累的 不过后来就好些（明明是膝盖疼然后强行观训emmm
然后暑假就没了

##还有漫研##

从开始写到现在 我一直都在群里扯皮emmm
最开始早在七月上旬就进了纳新群 然后认识了一群神仙 嗯 很棒

这里各个都是人才 说话又好听。。

皮这一下很开心
虽然在群里水了两个月 但说实话 知道百团的前不久 才突然想进超元气 然后就进了 看起来很随便 嗯
前天元旦晚会刚过 六兆年也特别特别好看 总之 大家都超级厉害（可我就不一样 我特别弱

emmm对于vc圈 去年也是个多事的年份吧
先是元旦 墨兰和果汁算是正式和乌龟撕裂了
果然 拜年祭上乌龟没上
后来的后来 好像是九月份 墨兰也退圈了 本来还有人说过’流水的staff 铁打的pv师’这样的（心情复杂
这件事又涉及到了存娘啊。。存娘今年又一首sh的’逃亡’ 和’反派’一起算是打破了存娘定律？？
也不是没有好事啊 今年禾念家的六个孩子都上了梅奔的主场开演唱会 昨天尘儿也在mixing room有了一场演唱会 （他们都超棒 啊啊啊
然后今年又是一个新接生的龙牙（但他大概是三次元歌手？？
天依的v4c和v4j两件衣服都好看！！！算是摆脱了i画的宛如童装的衣服（嘛

纳兰老师现在是望x的声库制作人 虽然对那几个人设无感 但纳兰老师的作品还是值得期待的
对了 还有初音v4c
##他们都那么棒

电竞？noip2017爆零 很惨就是了

就这些了 因为扯皮的缘故居然写了一个小时多
其实现在都2018了（逃

2017-12-3 早上 做出了这么一个能看的网页

使用Hexo博客生成器 material主题风格 以imgchr作为图床
Hexo很好用 但往往容易踩坑
误装低版本的nodejs 嗯 还有在学校用的电脑带着Remnit病毒 总之就是很惨了
查了不少博客 觉得github的issues和官方文档其实真的好用
然而SSH设置最后是在百度经验上学会的emmmm
贴一段hello world

#include <bits\stdc++.h>
using namespace std;
int main (){
  printf("Hello World!");
  return 0;
}

Young simple sometimes naive —-Chairman Jiang