转跳到内容
⭐⭐12周年勋章结果颁布！！（欢迎来抢红包）⭐⭐
🌟SS同盟12周年庆开始啦！快来看！🌟
🎊点我参加SS同盟12周年庆全坛活动～🎊

随性而为

【会员】中级会员
 查看个人资料  查看他们的动态

  • 内容数

    352

  • 加入

  • 最后访问

 内容类型 

帖子发自 随性而为

    每 日 算 法 挑 战 【第8期】

    在 三次元同好会

    发布于

    用二叉树的思路：

    struct{

      int max，min/*代表这一段地址的开始和结束*/，*p/*可以用p=new int[max-min]来存储这一段地址中的数据*/；

      struct btree *lchild，*rchild，*parent；

      int base/*判断是否是最底层，每当创造新结点就令该结点的base为1，令其父结点base变0*/

    }btree

    基本的结构：结点A表示的地址段和其左右结点的地址段的大小关系为  左子树地址段<父节点地址段<右子树地址段

    malloc B L：struct *temp1，将B从根节点开始逐层比较，在这个过程中如果出现（结点A.min<B<结点A.max）则表示需要分配的地址重复，函数执行失败，否则，若A.min>B则temp=A.lchild,若A.max<B则temp=A.rchild，直到最底层，同理struct *temp1对B+L也如此操作，若temp==temp1表明他们在同一个未被分配的地址区间，创造一个结点New和已有的树建立联系,,New.min=B,New.max=B+L,同时New.p=new int[New.max-New.min]，若temp!=temp1，说明max和min之间夹杂着已被分配的空间，函数执行失败.

    access p:没什么好说的……，就是逐层判断，看p在那个结点的max和min之间，然后访问那个结点的数组，如果找不到对应的max和min，说明未被分配，函数失败

    free p：如果p必须是一开始分配时的基地址时，则逐层和min比较，找到了，则将该结点右子树数据复制给该结点，然后释放该结点的右子树（这样做不会改变基本的结构），如果p没什么严格要求的话，就逐层判断p是否在min，max之间，找到了，则该结点的max=p。如果以上两种情况都i没有找到，则函数执行失败

    list ：如果是这个结构的话好像就是树的中序遍历？当然要是也要显示free的起始和长度的话可以在btree结构体中加一个变量，但这样对这个变量操作有点烦，不如创一个数组记录每段的min和max，排序一下再遍历输出

     

    每 日 算 法 挑 战 【第8期】

    在 三次元同好会

    发布于 · ，由随性而为修改

    我还是更倾向于用数组的

    struct a{

        int data;

        int used;

        int start

    }

    struct a[2^32]，一开始a.used都为0，表示未分配

    malloc B L时先查找a到a[B+L],如果有一个used为1则不成功,否则a到a[B+L]中used都为1，start都为B,返回B，如果需要记录什么数据就a[B+i]=?;

    access p就是先看a[p].used,再判断是否读a[p].data;

    free p就是看a[p].start是否为p,如果是的话就把之后start为p的重置了；

    list就是int start,count把整个数组遍历一遍综合看a[p].used和a[p].start，每次走完一段就输出start和count，然后刷新这两个变量

    （还没学操作系统，基本上就这样？可能有些地方理解错误了，望指出，动脑是不可能动的，这辈子都不可能的）

     

    每 日 算 法 挑 战 【第6期】

    在 三次元同好会

    发布于 · ，由随性而为修改

    22 小时前, Muriya Tensei 说道:

    暴力点，第三行打表，然后遍历前两行就行了，但是表要打M/3讲道理有点长

    (有没有测试案例啊)写了一串感觉很不靠谱

     

    22 小时前, yhz012 说道:

    数学一点的描述可以是

    给定数组ABC，求系数abc，使得abc各分量都是01，且 sum a = sum b = sum c = 1，sum aA+bB+cC = M

    所以这个是个01规划问题……，如果求精确解估计最好也只能伪多项式级别了

     

      

    什么我以为连easy都会有问题的（x

    因为真的太暴力了（

    退一万步说sort一下之后也可以拉到O(n^2)的（

    先把ABC 花O(nlogn)sort出来 

    
for a in A:
  tempC = C[-1]
  for b in B:
    while a + b + tempC > M:
      tempC = tempC.prev
    if a + b + tempC == M:
      count = count + 1

    这样BC实际上是一起跑的，所以事实上只有2个循环，能拉到O(n^2)

    嗯这里我假定了ABC所有元素都不同，如果相同稍微改一下上面的代码问题应该也不大

    或者舍得空间复杂度的话直接写哈希表 

    
for a in A:
  dict = dict + {M - a: a}
for b in B:
  for c in C:
    if b + c in dict:
      count = count + 1

    这个改相同元素很简单 

    
for a in A:
  dict[M - a] = dict[M - a] + 1
for b in B:
  for c in C:
    if b + c in dict:
      count = count + dict[b + c]

    避免误解，这里的dict始终都是hashmap，key存在的时候返回value，key不存在的时候返回0，所以前面打表A的时候我手懒判断M-a存不存在了（理解意思就好（x

    浏览了下题目和大佬的初步分析，我感觉没必要用哈希表啊，如果想要o(n^2)的话，可以这样

    for(i=0;i<=N;i++)

         for(j=0;j<=N;j++)

              if((M-i*A-j*B)%C==0&&(M-i*A-j*B)/C<=N)

                       count ++;

    应该是可以跑hard难度的？extreme难度……，你这M怎么记录呢，unsigned long long好像也只能记到2^64-1

    （理解错题目的意思了，尴尬）

    （01规划已经看见大佬提了好多次了，看来是时候取学习一下了）

    ps:昨天练了一天的车，真jb累，第一次跑还被教练冷嘲热讽的

    有喜欢热血运动番的同志吗！？

    在 动漫讨论区

    发布于 · ，由随性而为修改

    11 小时前, 媚仙狐 说道:

    噗 现在回到是还不算挖坑 主要是咱感觉好像也就咱自己在回帖？

    估计可能黑条太多了 大多数人都懒得回？ 而且没人回很容易就沉下去了 新来的人自然是愿意回复自己感兴趣而且在前面的帖子

    关于黑条……当时我样样都不会，不知道有图床，还不会隐藏内容（其实现在也不会233），也没有考虑到会让人眼花什么的，所以布局上就让人感觉不适

    其实对于动漫来说，我觉得讨论未完结的话题热度比完结的要高很多，更何况像这种比较老的动漫要回复也大概只是“童年回忆”“确实经典”……什么的，不知道如何回复他们，就算回复了也是挺尬的，自然而然互动就少了

    其实相较于引起共鸣，我还是很在意有多少人看见帖子后去看动漫的，毕竟我还是很希望这部作品被越来越多的人知道的，这也是做推荐的初衷了

    大家究竟多频繁登录论坛呢？

    在 暗の广场

    发布于

    6 小时前, 梦幻妖精 说道:

    哎呀，大水怪大受打击！:wn011:

    看来今天也要发挥水怪的极限才行！:goutou:

    主要是论坛有点久了，可能会不会普通区里面有深度的帖子比较少？

    这可能是一个原因吧，也有可能是我在任何地方潜水潜惯了，话虽这么说，但讲道理、这个论坛是除qq微信以来我发言最多的地方（甚至微信都可能没这个论坛多？）:mx067:

    大家究竟多频繁登录论坛呢？

    在 暗の广场

    发布于 · ，由随性而为修改

    抱歉，我不认识你:goutou:，新手区有一段时间没去了（去了看到想回复的但又不能回复多难受啊）

    就以这段时间而言，我基本上都是每天登陆签到之后挂个一天半天的，主要就是为了等通知吧，如果有人回复了我，我就尽量回复过去，其他时间就是干别的事情，毕竟能让我主动回复的帖子不多（除非有红包，比如这个帖子）                                                      

                                                                                                                                                                ————一个老潜水怪的自我修养

×
×
  • 新建...

重要消息

为使您更好地使用该站点，请仔细阅读以下内容： 使用条款

  我接受