银河美术馆-Beautyyu

USACO06FEB数字三角形|题解

发表于 2018-01-30 分类于算法

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;

菜鸡啥也不会只能想办法剪剪枝了
（勉强还是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;
}

luogu1376八数码|题解

发表于 2018-01-30 分类于算法

本来是想拿这个题来练习双向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最后一篇长说说

发表于 2017-12-31 分类于生活

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

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

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

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

这个暑假真的短的要命

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

##还有漫研##

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

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

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

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

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

电竞？noip2017爆零很惨就是了

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

Hello World

发表于 2017-12-03 分类于生活

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

1

杨辉三角形

2

3

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

4

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

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

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