Python“黑魔法”之 Meta Classes

zh

接触过 Django 的同学都应该十分熟悉它的 ORM 系统。对于 python 新手而言,这是一项几乎可以被称作“黑科技”的特性:只要你在 models.py 中随便定义一个 Model 的子类,Django 便可以:

  • 获取它的字段定义,并转换成表结构
  • 读取 Meta 内部类,并转化成相应的配置信息。对于特殊的 Model(如 abstractproxy),还要进行相应的转换
  • 为没有定义 objectsModel 加上一个默认的 Manager

开发之余,我也曾脑补过其背后的原理。曾经,我认为是这样的:

启动时,遍历models.py中的所有属性,找到Model的子类,并对其进行上述的修改。

当初,我还以为自己触碰到了真理,并曾将其应用到实际生产中——为 SAE 的 KVDB 写了一个类 ORM 系统。然而在实现的过程中,我明显感受到了这种方法的丑陋,而且性能并不出色(因为要遍历所有的定义模块)。

那么事实上,Django 是怎么实现的呢?

自古以来我们制造东西的方法都是“自上而下”的,是用切削、分割、组合的方法来制造。然而,生命是自下而上地,自发地建造起来的,这个过程极为低廉。 ——王晋康《水星播种》

这句话揭示了生命的神奇所在:真正的生命都是由基本物质自发构成的,而非造物主流水线式的加工

那么,如果 类 也有生命的话,对它自己的修饰就不应该由调用者来完成,而应该是自发的

幸而,python 提供了造物主的接口——这便是 Meta Classes,或者称为“元类”。

READ MORE

【译】响应式图片的现状

zh

原文链接:戳这里

Web 是一种可视化的媒体。绚丽的视觉效果,很大程度上离不开图片文件所作出的贡献。虽然(Whilst)其中的许多效果都可以用 CSS 和 内联 SVG 来实现,互联网上的许多站点仍需要图片文件。

从去年的统计来看,每个站点中,图片平均占了一半的页面体积,并且随着时间的推移,图片体积有持续增加的趋势;就 2014 年而言,图片的大小便增长了 **21%**。

与此同时,互联网终端的种类、数量也在增长。从 72 ppi(市场份额正在下降)到 600 ppi,不同设备的分辨率(resolution)有着天壤之别。

创建能在任何设备中都有着高质量的图片,其实再容易不过了——用 1000 ppi 的质量保存图片,然后就可以不用再理他了(译者注:原文是 call it a day)。生成的图片,即使是在分辨率最高的设备上查看也是十分清晰的(crisp)。但是,在图片质量提升的同时,图片文件的大小也会相应地增加。要知道,页面加载时间可是影响用户体验的首要因素——因此,保证站点能够及时地呈现在用户面前是我们义不容辞(incrumbent)的责任。高质量的图片,即使是在宽带环境下加载也要耗费几十秒,更不用说(let alone)是移动端的设备了——简直就是无法使用。

响应式图片的目的,不是要为设备提供尽可能高质量的图片(这一点,我们很容易做到),而是要为设备提供它所能支持的最高质量的图片,仅此而已(nothing more)。

从这篇指南中,你将了解到响应式图片的工作原理(what works),响应式图片仍然存在的问题和陷阱(pitfall),以及如何将响应式图片运用到网站中。

READ MORE

【译】“为什么有这么多的编程语言?”

zh

原文链接:戳这里

在过去的一周中,几位同事曾两次问了我这个问题。听起来,这像是一个糟糕的问题,但事实上并不是这样的。

最简短的答案就是:尽管我们并不需要这么多语言,但我们还是想要(want)它们。 让我们再探索得更深一些吧。

READ MORE

Wisecity 商赛总结——也谈前端自动化测试

zh
mybirth:5MfFa8SHlDQ1RpMhYDlStQ==:WZKJhI2CFBLPFLiabJ79JQ==:u2HTG9NSTMvRZDLFnJZhaqMpbrFfdof94RwPAWvK8KpXc7bS2vb9rI0MPdzbJIpjUeb1NSN6NCdLeEUiIxjhWZb9oj2Rhw91/8kFWroDj1bpfAVTFhWRw0fd60lQUDYXqhEh6Ufk3p4NCY7eIMXSXvZ3eA1BY1BAT30doE7P8mkjgAG1qoal0+yOvMF2suJ/sf4iN7ctR2HUFI7lPYKtboNgrW4m64ZIu921m4nB+Ww2FEUi/Zuu7de6NwgMi70PyeMrQhQINU2X8mvFFcEKr5am/9H+5dgsCR9WvG6Gh+eDmYM/VdQkGSmuviie0kG9YGCXRfwhOoMJzGg4+BQAWRjRGNR98CkcAVaBAEBqNlVwRDRMRTICVnlJeQJrTLqxKp1ODZz/57JZL5ekH6AnaPo9guhPmLFWaFYIiaZkoDLmlOnEVf4GTOsHXTA7UFZ//E+I3YXlRGkxggYMl8bbun5LT3sW5Cmqg8OCrbZ0xWThyZ+HgjqcFmfjKxKXNglgElNtVhGJ1ePrIDTVrgr2pYKeZdykSliYpV09kJSFD5hNuh/y2EFxtRZcxnn8akFAlgq9mvHDTObE9Mvy+yhKeuu8eMIR/jOlaV8lv91Jcc026ysyMipIJKHOUeRjNawVk0c4Ta2HL9bhcLCxten6luiWUU+WEh+rqqn03wHKhcJy4nCEKWZppH7jJGQNLY+p4MyH5sAdZLsEHe3O3I24k9OtIueWdyI7Um83j7g2zPNKeh/Fn6wSacnW1BO+5hexXw9k2OWJfM2BRarm86mELoS28HdxVDdQL0jA/ykS17sUw1N4MtkzNTSJJXZGZL7yBzS9cP/RGX+/B3z9eurm3UkpfRpf7DfFTC0FW0kgYSPoggPtMICMUOl2t6FtCHTkUZyDDfTcQHsx35rPS3b92OTCMt/K/Yv1VtqfnvC5zdobnBIwARIHTgzt957cs+n/CrN/vfKXxjAmwkxksijKFN6bQrvDrSiCPyJaLs5VSCnG5ytdCRRcEOeL0QQOjf9jKvrkEIZzVR2hSVzSYfYb9/Zzc1JZvX5CBdLG8gHAksjpB3GqhISyNPvyJOZrs4Z003eltQLgMdkU9I7mWd438mS0PqMuTxu/AG3dJAx6BIN3UYKoh3R+cIyISs/KqIxhNDpX5xIVsTEIS4wBfL7c6vPjIUoYGHW7xY1OLXJB+uWAMlkTvUlZlSvnf9W/l/ueh4Q1FjdgxIrUDlTMqB1YCmYaokRNucqXYjQohX8YXSZUh/85qJbr5Nxp/xhLu8E1WnCGxaWUxgfxoaYZ427R7q+t1Gz+JqNjx8twQ7PVc3m6VkBT0W1Ijai1wkFw2qjCC0zkGu3DxIr6e9bGSdouGYE8EgWAO+s4KJhzFRjfNVL2KnXk4FkSGdcpQMeuPsF7CFUG7zjT7i4ArfFJpTMKAGnYOtqNe619iQKvxgOmTV5FkXIwBzkiiDUAr3zO3frQH1Pf9Tl6LEEFyFJUY2uqwJdvscPVBn5I1cGI52uB5VGEVwTAnfm7Y+k4i0au5AHipR59mHzoMfZrg4Ss8CRaynNKi4pi5G4HdMknlhISaeGmbqg+Qsy7+bCNrxr8DQu6DVQ384fWcn0/tGJw4T7umHgfhaUr/0xw+lVAtXCpydE+f+wRErxUTcydkdUBRpBGg2QnLDx1QUIRfP5gpxQs8yq+jrdVAIJAG5G/iPLJnZ6mhFT4BAS/m81zzerepgwRZPnoLcpqSCRtclXVKz7p6XQPrBK192+sCte/LonlcEG61Rgv9UL2qTNo7Wav19INs4RRY6u1GXD1XtUFeB3IdoPcKjlquO2M36awoCOHgtWd1p+30vLslWjvP/cLFvEnd4D37waJ18WzVz/SxrNl2oXqXKZYYIUFU4YH6TbTu+/YERGtMTmgksEzVAzBf/bs7/e5vGv3nrCFoov1gi/22SA9iOliDoyta3iiTA27rzXwMD+tYv3XgNNFEeq2CsgtIAliIC3IsDjPZ7Z/vyyeLqJNZPEdFOKt7K5ZO3ojXnnXY47WBUQ+KXGv0qwo3RapvBNoPAlP+utRE0BcJd3k90i7pn6TCBh7MgKYcdxhlzOUkcmS9hzBsvVNUK4XAEbtYM90pxE+lNRkW8UE9cR4lv4nBlSguG/IeTj8GyTuJBIGOGREHxb4jkxTglWrNGVgg7jCHMFV9JtJYClaMbXk+7MMfyob8MQV0vwXc5AZsxDOEiZo32JQaKCkyyQhalSBdCyq5n9UMZbrEklSwwudo/bTDbFAk6uCHU41aVzE9qEglNglLoQv39QJVJLHr10/Mqclklvk0YkGbmvIpTmmXS2z/ytd8NjZUYj5SDQmApCT4QzhCuciF9N8yn43k0UasmzC4KbgAikbQ6dSMWQV55cjuCs4miVSDJ4t91EOjp9/UrDbNW4FGZGEh6QH9EqGyn1dtQ8IoPFgmKyCLtpwBThw+8NhkkZK52rVvkSOvZnha6++5zFaNmX6KGryhEgOiBUQA1JWvkzOnq6S9CeZXDHYJR5OecaWi29qSdS337K8DKJqnhqRK8NpW0SEmkCG/9JaWGFGEU9XbQ6mBiHvyx9Oy5eFqB4y1a145j9mPzMl2wIQG/jbLFy+otGakS2k6mSGk8AzdDvtaVLbDgqp+iO7CtWzfidVU2WL9+P5u5dIiReKrN/5eJPG7oBMQqIgy2pvqrYcy39/mPOOok4NxmfNn9P7niweGWYRnx8B7ytyblhX388wWhUKCzJAKHlyT6+c6tF8i1OGhqPaCJ6vDVS9ynLI38SwB/0iw1fQCCtUQg38EQ8ginwkXw+P5d+VnQQdUxlV/oW58CHHJ348z+vJj8uDGzJnjTBsFM+sfvNYb4K9bbqzLsef1y9i3BiNYgcj14iz9bGuBUQiJs5wZENg/Axy6bxydrBbMUEbXlT2kpFl0RfONoud8hmSgilOszslDy1Y1fVL0D2J9TQ/HpYYXI1Tb9tjTLE3t01NmnCR6NHroYGZ1cq2o8Gf/itDh5qNJOds6lA/54vmZh9hcJWr5/Ka8ESqevp8l0q1sy+CYuCJfCCxj8W8V+RAUNyMNt1LyDqDscuJ5XZLKSQZiLjkIrpi8LFetJ54rNXnqKeyO8QDfvvtqdFRjBeFReKOkfZ41QmnfiVoqgEGn9Wfsn0PHntEVqC1Mdicems75e0qxkGXwjxLL08oOWWKMkTSCpLTS6zKjTItglQFlOo/BGO/8ey25ogOjAijbaQ8hr/xx93e5aC4JciSMZUOuJNK9Sb6c/PbCIKJP3rvhZbIeF97Ye3CC0AIeZgkBcEnxJLXd3aolK+EGXQAQ5sLrP9PiuXOqUQSQ9H4vLR13CqavEb5OL5LOC9aCLKMVl31VlZtTBirFOhKghhn+K3why3O7VsH0H9/2q/+5chfLmagCmie9fY0JPPUIbLf8MGoCyYjTA+/sVSWAHgoBjPmDAUHBdC32aUXo9dyiOwkzAGp7IFIqAp8jxwfVetCYx7vDjB1plYM1CfpRw/2+G9A3dmWmXnzgttG0HIILptMHQFFVsR/FY8PgVMJbdn6iSqK1PwgD/7CQjt+5bJfZE7xdYSjvhMKecNtRWBWSdMUagMPdtYVHtsvzt22kifMCvwiKprJ8Ini6nIdEQ/fKYfQkyb17do0dUv8kk7yDTV8gC7I3Pf7hLeBkj9jJCyRvF/7BBLS8wbwOVtK5XinjrV7LkS++cmrmWin3I1KUZwANKXxll8RLUe3RRCrWhmF11fPISSJ4PVhAbxd2rizIOWrXrMcwOi2/7SLIDZ9fae+LhHI3yVYF1IpAdYKmCUkRJ71aIhvcsxJVJEG10r0C/pPp7KYKo2dEkfjM12ktru3j0INdZsHKFeLbIuvYSkh0bRiJWrTRllMO7r4h3OMhgZoRGRB6yYXqnktQZhacLgJZ1Y0O1NMVyzQFNyVd/dFKklJgSVEtAmiFEMvBTkc8Ey8mwyw+jBj6MKKuDzvL1CfBM9AWVYgZfVXGU2IPGuXvedvPjEWdIL0JzieOe8bmvxYlje79/wMGRJMy42sRmmbwYatGJN+KiXEgtgo09Dg7z3v1P+kYR7YuKQuqqfwhIupuzhP1euz5uNBgMIzmqzY8f5+fhv2K7qTMMUn762ZsYVuGEztgwCw1uE+qQytCLQ2tamALCBQXEFmpqTd3TGfZWTHDENnd95Cwjme6El8jItIh4KmRJ/LcqEGPig/Vf4KcgWGpYIN2Aa3SjpJ2+/rya/LU3cpp8HvEQulQoJbMqsdI1gOy3UyEr8+pIoWJjqOmrJ6ejjbEm2FkN35S3+Vd2kIz3+Uzj6n/RaTcWzBHX1MOkgw0lFhGLFna+CHfWKb4tiFuruPGG+Q0ZQNr/sGpwVloty1Kg8oA4LauS+E3/1lvNUqPVZIGFmDhgF1vzI3/E9FWwNYvw8w/Q3nVNXcQ2hB2KfZaeuh7oUIEpidUJTb7SPscNxn1nkfPgqTFuHifz7m0vbV2+oQgYuKykE+zUYNnXzBnoV4L3Hdc1mDP8XEu7Sav4K0HYcsTFx+yCuJsiva/EwhTdGj00Ulo4J3lfdfeXWekl0wZusvorqP4u6TzgmbX3NZtSfgicaz1e/ykL0+ljPNV129nSRQ+poCgII7RpURbhElUfTdrwUuEwa92PT5lHzo+5OjwYFx/QIW5/LzZqN9KzIsWSbHIZWsA+xmWy6Gj+Xayv4suswA+S9/nu/+KHuTTul5fDW/HOukZZl5+tGEsdZSNnLBK2SNIoC+OXWBtSrrFL9hIpgKVx3RpsLzhV9Hqyq37o+9hs1Tl74pWP0OdbpQOdy69iQvePRAK6fuJrnC7uk0Wh1DbY/rP9SJZEPQV1Eb7ZsOx6O0x3t1ESyDB6F4MwaJoDXrPi9D5AAnaMrsBAIGMWTz0wz22aYZ/p+W0Vucee94B5oYdlP0XDnUpzJ5Vve7AKo/XFnF1qQ5Zs5lum/Mb+htR6fLP6KsWTKjbztq3kTZGpTRtv31aMKT1iy8NHQ+hE7jsTAnnPaSA7WRHq4MU7OMx7ge1TaShHgfKMYqQnXetZnkOhXsWt1WqXGJEhqOSvVHY2dZV8uiuvjzOztw3VYUnGKXo+L9MYKf49HQpPcHcyjnRf9SsJvAfdd00TkytbfwgChBhtlZX0in9xuakRFUIn3wRQQv024738H6bWYqdRH0bc4yFUFQOFnpLp8drI+W8MO+6UcumkBQPUGd0G+bBJr/aVSWW/GF1T1t3R8KE9Yt0VgQtX9Ne/rHsf+PEiUnWCNeRpKRbGTB081c8qA85btX7TUl5ppZFgP2WaK5+wIet2UPnfAPFybGHoMABZq7MzrjykGc5q/zofOyDWjhMN8v559eWCVrSSyvIySkb5DopsfdmB9Ynlu7xKuIbS18qe68at4keBRPHdHEutfCrB1ECubi2uIIf+JLPLU7FF+um01/zG/MzLfXDG9nTZBYeuyQkY8UcZbcfhdx/gTHm2NrWHnFAnN+G82vtwDSEbGfd54qntxiORHfGRtDCXtNb2QMQODz3/lv+iyoX/M1LMW9VK2dwfXuJYQJmvSgxzWqngeS3fdp3MntKX7nGUKZLQRJGjQUTEhjarQDThW3WZbtLK1kLTP2bYejQ4yljFehEysZUSsrvzXNtYUwzxeFvU8SS9b96xmBhVZayyav+uBMZW4s6uYvMAtadtaMTs5GDtUEMqZUIrl9c6Dyd2DT/URRbaE7WlVPxTXQOSn1PrKihEjo50HweQVAvismZH1wHGzYrx5Tq7+LRMrHXT+3MHBZ47buke/vKpNH7BTI6VckAvmJ/n4NNu25cJckpaknJ8WE1haJJRLaDTynPnmqkz3JRE5jdDVUV6SlJa4hSQAAE4W8nCLhDXCj2z9KUketaFUNDm2uDwDYHiBLyvaKDBFk937WxqpG0htrd56lfh3rM/LztzlGTdoEBaApUy9ls5PJax+xdOtyw70w69CKaK/dfuzyYIPNXJm1iWjLZ7eoAOCgCnQ8lh3H6BH5y0eoQHGJQiD+1f4L8Z0CENPtCm7ye6F6ASYXuCr9cQsOLI0Cc42ufPbpgICsfl8PRlnTJNh+lejEoMiztKCOZIphaWRSFcR8z8TqAU1KWj1EbmlOTKS+KOcuxl2xOBiM2/IdVwuAAjACuv4JJHHEoXwuW99UnE2nbdZmjtVKeH8ndaDcJw9Lpkn5LYlDpr8N54yEDr0bMRqB4QrRVV19d/vupuKMfy2XeODkRm/Shl4FIwoYYPgjD9AkgddRPSpirGVXktnPG5JjrYaun+wAUwIasUd5ZP3AlC7DQzTi9av5EkKZsaaJiiFyONpxI9ynpKAImqgvI5fHxfUw8u4y3ivEwNH5I1qlDUfajPQJuI8W1ADWXvs3QNekvVw4nRIfflHCgQCJaobblgdHcddbLmQwUG0/26Lwt6LxCYtwihI5f9N1dNXABC6jWn/Ztacc/k4DqtOfEvdJs4xmY4WxzHk6lX98FHyiAYENMQge4H5ziO+doQgoFJnugXVJNX1iTmvA0oASJFH1kM+BCFArBRRVd2jh4mlvYM7PATGRx5i3AIYTBdlPIcUFtcyVdKnxaoPkL9o9qBxmtP7EPtxpHpLUineNm5TgZw8XCK9dK8q6Yri87LMY+R9nQFpSu6Qfs22QZEaiaFLA8X+HY8aLWvFVzW2hVPGT4l9e4mKahYJ4UFdOP5pKO0BYoXeRikPGtMuN+OZIDvknWEGolXBuvJN+BpTZkMb5BSS/zv5g/g5anniyYTJ/TF1zG4BH6Fff7ThVa0AZsZndlcXqYt41iC/CI0bgqEYeVyre0Ouj3CK1x8Z73k0b9S3+zJmHWe5cmlW+MgcgaTbxElof+JwDHlelhYuqtNqA6WVd0/Pnh01ekQsRdCS4Vbv0VvUFA5NM8mpLae0rZkpeVnbziPyRaXYA7ivrwZRSGD//cZLvO2wwVpDZywhKkO8CNR7GT0Syc6H9wlcolGvWDBD2rkufwU53NKJC/JBZ4BfchZ5hCqkGV0qAgEoCP7BK9zNYCOWHT6SYSBa+BTEowY9sjtiblSko9vgZlMN+8OgAduSWct+g0wAo89OPQoOZ8Oz+8Wv7iOXh1o/LyHX9GrTB6XI7szAACy/UmrPBN74ItDY4Utch4PTh3ZQH58JSlORx1tih2v5p/pID39B7VnC9cK2HpuXPJYM22vLYiqtVKkNLIWr4NYcKUTz26a1JGtGMUryqcB5Qctcf1WoRYfjfJnu0xbvq32Qj589k+toTEf9mhtv2HhVIvoEUMRD9HiNyyKd4ckhocJi2DYhbCkE2IzmrqnQMZAPE1fiW9CuJQNfsKXj8ieJI3kIh43atU16XjDhwPbQMa3slrORmZgNw6LNEHMibDuk8OZydWfF5su5djrjZBDlbn5oM+FWAJlbupDAxr5F1YkhEO/c0Lir2qtg+vNVr+e4FpsecVZCsP3zH9sCbaJpqTBRP2UDyLXyGd5VtcCJLfdwqARMhzK0qr6iLvtGw2bMYZD4v7x9tpgqGzK5jmAsXiza7pvf6xQsKbzr94q4x4iH+OwZOLC20UsaCkc4RHeRxFVd2OoDAVQikjUSYxJrpQ1IA3Uw8rO2XkenJx46frN05ZZIbaKilDKggGR+hEmjd6Q7TzXnBhIddl3CCbOMlVqDEoRJpPATCMjCFohBqCRh6p3O7fA7qWqSOjEq4kuGAv7eYF7d2MPNL/aApSf+R05i7PWiKvXNNAQZGLlBeD+4dfJGCfHH+//B8Xns0KcFEzT25KPTsEB/hb70G/fa47oXaXJPfMTFZaJmHq3Tkop4n7WJbRO0a0NK7QJeLfljGnpij/9TCZlnsJodVFUo48BTI9I+rb1nyx6GKZn7rtDiFJ175W0H8s2nUCf8wcCxN+U4XwdF+T+QGokImB7KWbwlZBzd/uBFm+/TXWICPUn1/a2/0GAKfrZb1sD0Cdf9lbV9zDdEWVZwwKFcT0SzUK4UWqz74M0qvLro4wavMoxh9Vg/g2sSlqNRVfLl2H7kcK7/iL6wXwvtSL505q+tzVa+8NH2Ob4Fg6hy8qywhKWIMFPpNEldrz/vlYzWAVAcNZtzZozu9cd7w052OYUX++Gta8o2SAvg6s1wYBTqORYFpoOvQ/0+r+IIjGOrzHVtqIYIIdkERRmX53qCT305MneqUedhgq6htoT8jzyC72NO2RDJFIqwKegU+Kzi6pU6NvwbPR/wEg8HRFYWQQKz9BWES/Bm0RmMZZx0OM6oE8MwsDVHrt2ebt59nJ8A44tFC6QFljjzfYH8n87bsVZu9yMspy7PpejuQVaGgqb0b6oV+2wPFqKoIyHjj8WIVXu7etoZAkiba/Q+LTSxIfcJnfC/ycfvsbH6peminmAK050+U/GCZY2pTb6Vo0nuduTertRKUc9sNnfxaRoPKvnhL3CgVsIGJHCONQxFJh/2L+PRWs9Cr/FAefy9PLBYIAE+55gJejvm/UhpmJ9jZPn5707Kh4NEMP22YC8HRXrR0G7JtwpLLGF7SvOz84RBXCGajdjLIsnlKfPErD8Tcw0xomp2dpPqHJb/3x2VV/8+gywZxZTjje5H+2zvckS+5YJBtk2JPbQVu7sfu7+lPMAXIhjHd2G7qXptQDLl1tOgTLFmfpatfDJ4TBhnDYCgSLwKIMbdbP6NwKpn9r/O39ajxV4iXJlNLbpRU3TKKce/L8qVgIBIIivMlGP6MzdL+SahUmUT4P6TxObyXlx5B/VUI3Bj/Ti2I8qSjIiZwpTxHKHaTVP219SrQP4y3btrrjPis4vsC4eS6IBnn160kT17Jb1VczA1IQ2vChq9YHkdzFkorJmVLGTsCKgWowwl4PhNz3aGUedWo62+cQGfVZgTkiIuxbpKVS+/U6J8MFcqMTGdNUJExJ1lbfv05+/jtMbGBS5PcjfkdUpU40uFwA9Kxj3CkHxzoRah16sTVq4RqJ39EqAyTZCUmhVABSL78CQqhcePeMod/9RGHz0BLdF0iCPMGoYwdZItw5G98qwUnUB8hho/c/rdR0x2Yt7Yapre36PqK1mjHABfRILOige7rRyEsAD7KphOuJ8Q8KUiQXHLR2Kq5tDUbmR1PbTsWhQoyWLTGRqxq60tWUcOulRkRPPQjdeAX0dRHi4GYQkWZ4hxNqHVKl7Yqc2i2QsTAZXrIvEYiW4PrdEtmo7/q75OTBJs4LHGMjjZZmqSInpghZm5rZ/KEl+Fci5F2c3dT5hrFOvMnejLcKtEC1e56/WH7gceIQ8ZPblhz7QFHaC+9n+uEtUlRH4DP/emGRAmLkNytAIx1z20w69vxfkHnt86ZwkvwvhbSGFM1Q26a5WMtR4EAU2QNWy1roHSpgs8sEjANAdolFttVB6SXFh89pphbQAjR2p/6eUYZlXpGnzyk5jCypP47JEBV7bm90JbL+fZW+FisASdWuav37aHMWQudG/zrmRDjfQrh1oqYLG3/8tgkZH0uDqVNx9kCuE59Z5G6iYs3wXhoi7miooy838kECWjRsqmVZl87pdCr135+NBlQBuDaeHg5xizDXEAMvo5zX9VAhraJK06o/NGSbps15h/Zm/1fRN0NXkhaM9CtkTKkZoCPhYV+AqtYNSc0mcaQ27igSxz4GABK4Xo7CkTP9femU9WLJy6qtbJZhQ64qr1/ExrgYQcjcUHKnt53TtX15cX6y+eDrfbs5i0aHYcsxqRJnsEeVpgHnrlWBDK7kIsoVron8gqTbp9qnYGTK9S4Y0lX93U4caYlRR9umMdV4AipzeL1MfH72kSHfhh2rgZq56l7CRXJlOJmXBhNLLvLpgKJt8mrBwtoU5+3CnQcOv9fwdlBCuuaUUVgrv4YA2JuDTtohBekVR9IUvfeJCThB2ACGghPy1EQdDbwBJ2fows02yEKee9Wrn3WnSXxVoKV+lq8dhI2NjqyAmi/MHP4zeZiDR2Q4kJlFLtn7sWeIL4VCHnOw99Pqw47tqNFtu3OdPma4EnwiQ5zbBkLYE/ONrICuYDLmT/aKknYeWXb1XT91VCnVlDZVpjdI6eQxJoapwMDvbsNFs893JFOAXHCFmAmikGdWd9ja0lvXXn/lCQX7sMBy51Yt4uthCJVUpJFRZlKOwaZS31n4W9wWksqtf4s/HL2dzE+8oKzY955z7LoK8m1wzUbLySVH+K2vixOMPj+jD0TWJR2UONhDh9rH0QuD4qFU0Tcrpd6sG++Cr15t9jtTAbkmytedM7dTr3OsFx4EtuQYD7OHeEEW/iYVYoOct6C2A3TGkNqQE3BMfb0uHFuDgirLc0WUPQTGn6mGp/S8yQ1iDvVdoA8/2zbI4Y/ki6zSL+AxWr4wI/pIg/1W+ene7vVdWuZuY716LPO/IFgM4rPQnzGs2j/pHMhi+y+CunUXsFJ+OUjPN1J3FgETZmHi9StumAqcIlMAuztF6UDcpNyhS/wCEds77mJggp33jfErJ9A/heCuZJP03RHI7j8FJaGH2hiHL4K590HPybnr3Z1OMj2Bw8A8q09yvXWyCNcVFrN47VWkL3/oA5m86OpVB4oXf6JBeAT21h7AtACN0S0EcVjod6ZtifONA+8+SbeDt5wMP10MYdtc/RBXFd8JiDHNwFZYo7C3uSKLvvQQEHW8SKj5migTqm5M8SmAC+KGWJFvUrTpckr/Fk0Q1u0Y3cOnCmFGuC+2VTFKcDuxadfvUhywk93oNQB+BnR0odKY5jcryXQzS2s1ecYoPFUnzdJtU4WUMiYFRvWcG0FUE5mfMav6h0xvufyBbO1IdNw4XMT2qDDvbM9/8npc963xz3/uWwPDwLf6EMp6BluVlnZmy8Ms7+BfXpF1siI+LH1eyMRoFBtnQk9dC7V0enRoa5eLjgMnHvzHCWLwKX66IBo1tzOfAse+yHKggjrb/6mYDvwSn1KbCcbeKuU4nH4zA+WWnWbhZert7sd6R/sQqpUMITPbKdBjLmh6AFIh3H768kptGECZ5Ae5c2yVTK61YLR05zhe2N0f5fSZrHbCOOYb+dqiDwGC+2hURzGusBJkNQToOupwC/mdB9sSiaUD6bREL6jGZ40+QV1U79V4n2MvzYVCCopGc0+ecl3KEFoA0/ODeedxRcvtOuMY+24FIsmzHhgDMtYzI3tQivlpAU0txV3yNhar6DfOvgO7DVF0obSI94ruiOVUuiAqeqCgqEY2x8c1lWp8KFuU1XZ9qeWmcCq1Zgr4aGocRoahOcM6WYjVeKYdm9cPcbyD5hkUbqpRl+w5A33RMpoYb6eYz+MrCvKf9qUx/VKNyoZLTByjGDAZOhMOxaPS3ihYh5vPeUKh5Rc3YRux6VypUwWnoj8DNAaSy6KNemNTME9y82SNYylCD3Rs8N+eXOUndTT/ywhKhHcbay4VMbKrBvRa9DoDe4s6eXPJdcGHDyuBoqzdX9MakcWsMcby2RNhR7RTdYj7JQDSgPlgNzX9jz47n7THoOAnMXbqDRk1PIpPhAfh/AD6K2811drH4pkBb2740tIr6EIaGr/xQQxipgktJPrYgSCGUEwDIbd3pgH565XDDICtHb3Nn75LyDo1zU4R5P/UZRaAv4fnO1p
**THIS CONTENT IS ENCRYPTED**
 
DECRYPTING...
READ MORE

记一次 DoS 诈骗网站的经历

zh
mybirth:hUeY3Bw1xWsNki6GswV0JQ==:rTdeAcCAcNTUPlnCHEl9uw==:o/cJgP1HZz8wBO99Y9rtiS0x6K8LFBVFXxLEzGH7fsXwPmvfGPN655m4iUevblFp9jKiBjLVD1p9yuu5oEUeHIczoiYroD7BtX2DFtNlbUEuYT07BdZJsKy8+uVh7o4ev3VPBzLPrSMxpgnBHB4b82zM/ykZay+0T4yIo6Dyk2vTDVLiobkhxVnpcP8I3B8McDyVh3WCIacdLUFJ8Yrha8Ui+MliC5k5dqy/aicefA4LjVJkwNlx27Y8vd7IrrCHFeGga7t/Vb144JCBZws4CGtNi8PdDeRZzQaUlCBHUF7PbTSPoUDHoZMRt45m5F+gp88aE4tWxExGWvq2QngyHC1uWT6DSYGypm6K9gsTrzOnY8JwGNam60axeR7z6zQCoGXIKtgwj1F87HjZJE9wQZ7N7ED2r+dN2TMF8+c9ZgefraaAmS3w4a/XDx7alZ9/ma94FXWzaYJdtSuN7MpNpnuvjIp55NhSmsejUmFUusrkS2MUonpZfAXR2PAfEXFJp7bhNnIaBoC68jihUH64Us9HMGEbejo7NC1el/gFYVLPXNo4lUSmMK6UajuTUbro7im4BVR7oyN6y99epy5B9Zo+6d3QlvNnLKr0AQs+c4lFQncXJqD3r9c8K6OwkDGzRdkmq4Q6TKG6gFrnAoXrP3HFTq3pfKDUl8WcrEpxoGdvJzpA4eXXeCG8cgNzBgObA/i7ekevL7M9rlTLk2rf3kwgb247o9ZHZygh2TlfDoG+5UiJwanlPGnWFWX0pxnmXjWISZ53C0Ho/0pY2L8JyyhyRyhLf/Q1j7e1UmFtrbA5lQXoqzyw9Ar7F/vWDy8jZlru699FHxjlQRMl+DH+hSqT1JiZZPPASaYSo2hZqeoOx5bXzrg1bmLe4yTyDI0EtHDuHMr9Le143qynNk7/cz/xVlifDHGG0XFxp6XXGn+dpjlGLgU5SQRKeUw1dfkh6/FymjJ750XkUDHcwtFy/KzqC62UlcNqsUfSfTL6ouV2LYLqxyAo2mVqY0ZGYhFtpHnAnYe5aJogRxu3C59H/Dl5EI33uI7UqTiFoihQG6wj13yJziYSqu/PA3isI/EGeiYguCIj7n9JjS59cDDgpuu9vWxtwJwqZXFGPhTW4vIqu2xQM19s1QnhIWty+wLtHNBvRsguPcaO9HILAprGDA+UepOGdQhLzwXX05HxfO/o7nJx6N1jL+rmESLn7sIhWR0B8cLEngkINJXbR+yUpSC4yX41E9k4Y8+rbqad/gNWrNpAOWYWKQYvWdLr3zTQUvm/CMfBkG/aoYtdIcpMYIlo0+2A30r6oGILNSE4hSu/BOmks4fhkcuZ28DNuzxELd2UJGhKKOGkv6CdX5mCAXK6n/B440P3Asu1jFOwxChJVprsAkanQ+RVxvvTcgGlo8cVMuqwWxjKH0hlh9uo9K2JK4/NUH3qez1x4x8q/015K+K5fDiO4NoENDvgwK/WK0FcUxviFayLA3BPdWJaVgqX0Zevcx/lm95wWOa9098IP2nSApb+DsV2YhdHGDsaWQAO5D0pQNVLiJsD6aBV9Esgz7BDQjyI3N8NnW6na60QjXU7KJKAhBoiJD7xw10qCBfkwj+Y039QLlLFge2qwsQyNc5uSSTj3hvGAF8zwchYlFzqTIWSQuzvyxOz/tQCSiGKP6jZ3aqizvnaD+p8WegKpmINhMVt7SCwv/BkgX37oNnoiCdzFH25ifxHk7pi381+PdbS5qx8qv9ADpAnU0cGid483rp8U9LrUhjwYFtxGGWjBnnqaCRJNV3RuFXuAzrpGpegL2Q4U3l5RWFvekALeg0D5i51jR45HVqWJeIoQ9yL8C5Tz7TAhmUHYnHOrZUplj/OhVkcxi5n3+ajQkceSCBO6T8wgg30axFwmfu36DWxxXRL6CbcLaDHgtf+6o1Xp20WtqqlBO9EZ6nwg/Y8Txgr0BTS3ABkQlNZJdVTlM6vgp9E4Te7eLP9lGmbiqzIqDrHnUVF3d4ZH+kbM/ujk6HHNdhLoUv1UEzgYbrtV0XDT3gguRl+470EN8LxipmoUPvfX1RU13tMHOlHcYlkMJw0nSQ1O2kP59vHGo+Y4V23vM82ZoHE7Q0RnIlldJye+7eQ2AvUWlIaja5mC2Xwnc6qSdStqEZqJcsLYXvRqbN/I4756k/sdmV8lbB5OwW6NMByOqqogjYHTfFN/E7TTldtFjvFkGZiFQ+jg4/PAVlvJrBY4/iSYvigQ9kHFfmoBXZuNPSCA0YlU+0a57to8VLEodbjLz9+FnYzwm13nRnYuL7tIUbGre7ciFzot/o4WNq4zRNPf57obbckobw2MXmlBEEiet16fQQvT22nob53ECwLYjyJNorEE2B9mKd/d1c8OdWsuDI28njbo7wG1nmAiMEaT5qy5/KItQYfh05K0CBHKf4oqCskQuS/OglYhbswjLeEN1cjj4fpWD2LXlT8JQkViG3v+Oe2rJxmFf39t6DGrGIP5VoeN2qE67gMkQDGywcRppipKQCAi+ARLjiK47YR6bOxj3GIagY7Kp7pVKxuzKRYkpm2x4/7GetgZHigUDhdATGhH/m531M5+puDT3Ps2Mm+HSE6Ubk6yoiYidmJHqYpIYay/778MRJkf3dfMtSaomrxoM2HXLDSHkXRRS3umtkodDC9pJiYds4m9AYJ2Ej7Q//XZloNE0svNDAvixnhI8Sv94RKyqmO1hTCo126ZAKB5eDXBYVIaTpf9lG8xZ3OgA8byTs4wlDLRtbNVQGwO7CHSIfUwg+VZTADD+UU+6+tB3K8z0XDr3sxvTWOwgXpx2dTpgjXS4q0LqAqbvVhV9Q623GtuAJ9AQEtKqzbL5edKzvmEGv8sWazURcLwrTbhBYxo3aE/G7Y1gZJBcGU8562Rriej3/LnmSNUJSuyZRNyT0ReuDMA1LHyDDoMyMY6Qq6mHfZL4qcBpKJxOKSU3Me5ODoJnsYWfdY+9/Zpx0IoeCccijU1u190O2snpIBP5vgzp57cyLSCcesG8WOtbp6uV+jb12yOu6t+JrNFw7pfTewaOcycT4LCiql5veTNncyPBxv0My4FJO8GHAV1sD2gO2UYszQozYkW4tcxsS4s8x+vfzYA7dqY73HI2cAYi+mzrEh5gD6skdSZgy1MWiVN0nPnp1FA6t/52XMTBqPjXyU/imbNauOAV0JnCRfbr9SKpTCiphdGrVhJhaAPnYeKgc0w5S8LEi7tbqaYNjymC1y7ZOZZ1nPquk8pTFJ6tWAKXc51AYo6/El0zyIZDmKDmhvYwq1G7rWWolvlaJx34LXCqOJYBVobSg1e26f5RXcy8q0Hb6m8As2cb4aefDf4M/MTsc/MujNJPjh5BKDiuwzxycVbLNqKnrcJKZ/p6mizr0i/OfRM3CiRFUagjULKYdUeWIBFHz8FeCdHcofGh0q2aeo3k52mDM3rJsdV+43fmkQDmfBesfPvEEN331uXyR/pXW+JLD5Zyo6nrkaVV2rqLLhaGqyAOQ9jRb6XPBLewy0luCYbeB3GaBhrFwf9NX6/omiktByGVsOrSzxLyZRO4ntkRr0g4iwYs+/7eugrd1xmhdhLjDJTolSGfytu2U10+WB9YCeoNtvxxEajn24B3w0zjCcAv5NoyP7JnSbWADD3/iZcI5DHoW8CaJeedVfv98VNlAVxXWR+FEBFh4xMq/d79AR24ojdrTLseqovlN1YXatB0he9MgvDVPEh9stIbUwPlFVGL8PDuc1VQLBSKWuAJ2tcEbLlT5izki8bPunp6wYmKXofX2MIUChxhg3Kzo3WbHm6zxQBwKnK/8T+u8GCfmo4WZfWAr5t/sG3p6Mf0h+HXUEVddqWJXMpdjiEOlUZqvMi9Z5PULCeyqvIVp7kxZKSEGC1DVyE/LTEri4eOluPTviVeqJ+bvfu2kZZQh620gCy/nTezjjXwIVmt1ncY6bNohq7KsRWC+FQsmlQr3fTGfgle8yVBYMo/yqev3f4XV1yvhlgZH59ZUjKbGHQRyENsTMGG2DaZgbEvULhA021QavlMKMc62Rmczo4QBJKWEcWWmZg5g0nMdPKaWIC6VI9yqZVX6VMXCdO08xdJGrpJwCbIQT4C3ayakEeRdHscwoLELkoSbIuLP/qYl6pOG47yknt2P+fxpF6Y1DhJWIUbIymSxAuaUdNPj1hDKxAdzSMgysgBnx0Qic08aRTTlqe0sW5Ystvl3rzbi39ZjvRt9uM9+yMetuCHb+FYFNa6SUXWRhF2ZUn5iv3ezJMCQtQxxpCN1IwT0yjgcwUAFpCHz6ledhw6eWe0tAq4xGxfuZhz2J8jpchqd7xzmNtaYfooU8UVeqH/EW0qmWjWjtYtAhshj9zg1Y+SP/l6c5lqkKZn75/mJ51rMxk4DUlBVkx/JcvTejDQZwyfjzc3Nu4tPZlxvCymYiuun3fHlDKVqVQQqTZrqsOotjG8aOQ/O2F2ioORz301xdkP2Mw97uI0N28p/Yk/I+2ubfUnL3+2ur5xc9IvSXdd0GmQP8sYp9lKPGQ2PipaJKlG5KrqE7rhK/62wwqqpHfM7z+c0KkAWJ1rACAWzG9nQzPp6PLRsLGHfK9BVh7+7f9K2fYmjnJ7UJoRQhn4dRsVe3eJmg6qmwb4NBUNR3JTNFK8BTcpsnWSmil/O4EQS4WDP79qOGEfbmpHeLHPShlC1ecvPtJI0QUTHJ4fYOCazz+U347+xnVeQwN/HlnDOofQ9qxHGIgEC2IAyDVVYc3T5N6E3Eqo3C/nnnuHsWTEucincE6AMwuGoY/SKwrT2O6RrUIbN6nosBYaOrpwmlPZ68JuprqZt8VJHg0rIi7WIcS8rTc36JRaELYLkQNVhRwvZmDnceVablFc9ipIzXCskst0JMppXlZdYnq01lgcI0UUcnL88IBZOof7UORyKdFMzm6RsITentyaIY8GVbVNPNDwWCzWvD9udU2UbNiDtPOJwcT9wtffbnvZ8LGon3ejgi76Ut8LiQYPpJ8AzJmGvs7f7G+M5xi6pMxSlQE6csxpn+PDKUlg92m314ST21IqxgMD+P42nXqWVpZXHXQVrVa8qTb5XTLjiCs5yBfJuP22g0acY4mntegftPx55HVejanLG3dwKjmzHgSW+bKsqjZd/Mry/xzHcLg8GD6b03AbYJA0C/NP5CfviKe3gCS/ThhwFOt+8b+vvBdaEMlhJxN/sryssF4Z5nTwVhkC4FDz81Pa+OLzwo6cb+7BNfT2hSUCoEb6RVemA4YJnVeL78wlbiheaG+5gTM9FzJIyv0YYFl3BCUEm6j8cnrVzLdOJfD7itkzTnWzRuA1kPHNQAykorElcDTyTdF26P9g1CkBPrBbevsepCoDI3x4st16YtaD06eVL+plqsgWoa2kPBbe92cZhTEio62shbWTTggZSjJPYs7mA/EoQGNyRtRrUDkRmXXdP86hZ+5gD39bguGCgwOiQrpL7SBKaju5WpU31fakRB/rRwF/RVZtUjLKlGruEbvqKNBwrAKe/ZOfq/2CI0OmTt/Mj/zNeZE94QbkPb+71wtKYxsH3iSiiqAnN1ee55uSfYkj1+o5KhfCUHxVlm1ru5CIHDtbrxzjAarpWQLTK6LFPbMLLi+vQyLahwMQ6zWM2/DvEBBczygdTx9nfK2dfm5gvTZ2eJ8YH6/2zzUrq3a59M43NeGBCH2TEBmF0kFDYIU3njTew7p4dLBiATAeA1eC/9dWDXt/VYKTDyZR2e0wXRj/pGiB/1xwB0m9eerbSK+Vb8HiyekEOgKbV4Y4n7oL/9yCXfp9J1YCDuwJ0OS8HA2qykgqBh/CbsjcT0eWyqOlrdkBSHAi+YL7m6AJVx7ZVLo8FvSp56ApkTQuB9LDDTf/NcnC5I6V/Wz3JQsmD6H5tkSy6VlDj7pvvfyF2lHJBMIjAv9rReQdFon81XKhYqRw07rZQMQHSWdL1xO8CGoFJ3jA1U8DHANUzzhtXtxAwjc4gawyPTQ166bo58UBJTssgByOKfuUCfXlxqnhsRz4jdDobX6iQFeBeH3yrCGdh4VNt6NTIm5C5JP4crCgMI47QQOd0rhQbd7NlKEu1IHPKnlY0IMQYVqBhUgOj9q/Vn1iPWJgemby0Pd5yVvoCx7Yl7j4PBRK+rDwCoOS1H9TOrjYsm8VwvUk12lVOH7+l/oOQH5NPDClZ9kxYNh++cLy4KHfF++8sne/rT0P2kOnQpM8l0aGBWCQ65LH7wP58TnqT4awtLndhA/+7jBmOa66tUH34ZuvnCB9AsyUeGGIRIOsFoaQlDAoQoxLsM5lmD6yOqVt5kOIImzE3q+Sehuohhc5CPnnhId+kGTMdTfo68lUoTQsFj7oY44lBUWuZhU25Nf5plqm/NLY4iej6ta2s+jCkYlmXsioLE64G50cFS47S0Lfv/4a7SYK/tNiNcN5f6freodItgVITZVnCITi+6hNvWMd9xwLw7jjMOI9tyL22TDkbXOb4xIXgsA2squb6wRN3u6l0ZyzpoaRmnyJK4gW33jz/V9EQVC5PhjoYm1dJVF3Fgy0C5x7wYo2Adv+dKuIudMSawtD0XEzD0nxWJRiTLMs280e1k8K2isKvNmRdfpt16wIQEiTa6rR1OhBtl1YGJsFXW6wr7Vb92KSdNQO86GYmh0b8ruEQUhlZUbFhBaLWVpULQ7UkiW7bOkoBoIgZqCNcGPt+Wsj51mfb7rNUfAmC51Fn6P9NdtcP60TDh4Q/JU2qT7EpgmiXNCqiaWxyKhhe7XJwikISuZVhon8gZI65E7+YNmYEMcBntO7pwsCfi8jE+9XFRhLx0Zh4SvFpeCHfakpXeMn2MQrbiah4PcFhAQ2o4srPmiqYIqLJMmhSM4sSNek2DXOHbmSS3BO2Io2jjCp/jsjOjguOS+AI+fY+Js0M6xchN915Y7k1tNBQe3rgI6d0dTVHnOSoPtsI+xI7NyYgoSaufHsngEgesHA+QcdCUeHmSepd1RFOc5gvNRMZbJPfj6zAtovbnFpx0z6zkudN/fUfwmb7PY5urNp8R9r7Kf5S6xNjJM5TK3GMJh3EECIaiguHCwUd1aQ3Qz6Kk9Rx63urbV7eEw0qMqFzfHRkyjObhe8n8YHls7h/ePkkdJun9hArrddu/o/IrwNBJ7NGWRwBBpkqvoIXzPKWVZbacfRYHIgf6jmUqzUgxrPLknIAO3oiDTp7q3viexRdsDhnHS0WDo6Z5A8mJmo5J5/8eFJQfXZOp3ZIsDzZM9ekefoHRk2dYcvERMO8+Gw4NrO4TqvdX0m246E97TCngwWMEhW3HE3oItwSChUEgquQCQ7pl7i+WiuWqsqJ6LFa+Pxt9krpl+Va1rQzpGfMYsG7VT/800zKGP+ZZCvGWwXdRdwHNYLiOio2LltEUdvuVRE0uVGLrGHo7YuzkXFEcqFeIKDKAQIF0Xp4fBPcD8gqLSu8M8GprYoTKEyqykJJxYhMabtMHGoeD/Y+qwSEZN1HswMrLDYWsIbRKtkQ9bc4OxDVkOfjTBwy2t0Gwh4Tv762QUqX2xd2uc0yyjHTiE996vdE7l9LR5tuVDFlpnhF5sQ+voqFl1caSb+yNYoul3ibMgDKsc55MDNMslAceGWM6QaAqCumC7r/wOEkYDfg0zkZY0uxLFR/RkJoC2wU76xgEgE88NBvNVaGzNii9JMhVXsHSGhwBRc8WPo0NrDwORPWtibcKoGnf/XEJEo29onHMiuVlzE1pk03D6r1Jc3TSoqXrH1tjn21W8zQUk8dRM/thdy/+fnPWr/cf+sCCTKn683F6SLsktkqKysS+50HfiLd7aWfy393bxOHmbSc5D7tKSJM8diJWf2h9JpYAYcojiPDrpewSVjxtMe2vYz4P8MH0qXM/P9Ph48LoW5InlWdAi1TDzXZAS8mdomax9mtHaL2f32YoVwyTeBG93CCZkiAClCCC+aTYhWltHIi244LT87JAN+uhVdPn88LT8rTAMICYZPPJy2IgyV5fo8X0SOj4QYJH4FQmLESBrTjV1rSoOQOyhsdCrbczYLM=
**THIS CONTENT IS ENCRYPTED**
 
DECRYPTING...
READ MORE

LCA 之离线 Tarjan 算法

zh

真是巧妙的算法!

比起树上倍增,Tarjan 算法实现起来更为简单,一个 DFS 加并查集即可。缺点便是:需要先把所有的查询都读进来,并且要储存结果。复杂度为 $O(n+q)$。

Code

var
sets: array [1..100] of longint;
visited: array [1..100] of Boolean;
a: array [1..100, 1..100] of Boolean;
questions: array [1..1000] of record
x, y: longint;
ans: longint;
end;
qn, n, i, m, x, y, root: longint;

function find(x: longint): longint;
begin
if x = sets[x] then exit(x);
sets[x] := find(sets[x]);
exit(sets[x]);
end;

procedure dfs(x: longint);
var
i: longint;
begin
visited[x] := true;
//对于两个节点都已访问到的询问,其结果已经出来了
for i := 1 to qn do
begin
if visited[questions[i].x] and visited[questions[i].y] then
if questions[i].x = x then
questions[i].ans := find(questions[i].y)
else if questions[i].y = x then
questions[i].ans := find(questions[i].x);
end;
for i := 1 to n do
begin
if not a[i, x] or visited[i] then continue;
dfs(i);
sets[find(i)] := x;
end;
end;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

read(n, m);
for i := 1 to n do
sets[i] := i;
for i := 1 to m do
begin
read(x, y);
a[x, y] := true;
a[y, x] := True;
end;
read(root);
qn := 0;
while not eof do
begin
inc(qn);
read(questions[qn].x, questions[qn].y);
end;
dfs(root);
for i := 1 to qn do
writeln(questions[i].ans);

close(input); close(output);
end.
READ MORE

LCA 树上倍增

zh
var
a: array [1..100, 1..100] of boolean;
depth: array [1..100] of longint;
father: array [1..100, 0..16] of longint;
n, m, i, x, y: longint;
root: longint;

procedure dfs(x: longint);
var
i: longint;
j: longint;
begin
depth[x] := depth[father[x][0]]+1;
j := 1;
while 1<<j<=depth[x]-1 do
begin
father[x][j] := father[father[x][j-1]][j-1];
inc(j);
end;
for i := 1 to n do
begin
if not a[x][i] or (father[x][0] = i) then continue;
father[i][0] := x;
dfs(i);
end;
end;

procedure swap(var x, y: longint);
var
t: longint;
begin
t := x;
x := y;
y := t;
end;

function lca(x, y: longint): longint;
var
t, j: longint;
begin
if depth[x] < depth[y] then
swap(x, y);

t := depth[x] - depth[y];
for j := 0 to 15 do
if t and (1<<j) <> 0 then
x := father[x][j];
if x = y then
exit(x);
for j := 15 downto 0 do
if father[x][j] <> father[y][j] then
begin
x := father[x][j];
y := father[y][j];
end;
lca := father[x][0];
end;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

read(n, m);
for i := 1 to m do
begin
read(x, y);
a[x, y] := true;
a[y, x] := true;
end;
read(root);
father[root][0] := root;
dfs(root);
while not eof do
begin
read(x, y);
writeln(lca(x, y));
end;

close(input); close(output);
end.
READ MORE

RMQ(二进制方法)

zh

问题描述

已知数组 a 以及若干个查询 $(x, y)$,求 $a[x..y]$ 之间的最小值。

分析

不难发现:若取 t 使得$2^t\leq y-x+1$且$2^{t+1}>y-x+1$,则有:

$$[x, x+t]\bigcup[y-t+1,y]=[x,y]$$

运用二进制的思想,我们只需预处理出 $i..i+2^k-1$ 之间的最小值,即可快速完成查询。设 $dp[i][j]$ 为 $i..i+2^j-1$ 之间的最小值,则有:

$$dp[i][j]=min(dp[i][j-1],dp[i+2^{j-1}][j-1])$$

Code

var
a: array [1..100000] of longint;
dp: array [1..100000, 0..20] of longint;
n, i: longint;

function min(x, y: longint): longint;
begin
if x < y then exit(x) else exit(y);
end;

procedure init;
var
i, j: longint;
begin
for i := 1 to n do dp[i, 0] := a[i];
j := 1;
while 1<<j-1<=n do
begin
for i := 1 to n-1<<(j-1) do
dp[i, j] := min(dp[i, j-1], dp[i+1<<(j-1), j-1]);
inc(j);
end;
end;

function query(x, y: longint): longint;
var
t: longint;
begin
t := 0;
while (1<<(t+1)<=y-x+1) do inc(t);
query := min(dp[x][t], dp[y-(1<<t)+1][t]);
end;

var
x, y: longint;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

readln(n);
for i := 1 to n do read(a[i]);
init;
while not eof do
begin
read(x, y);
writeln(query(X, y));
end;

close(input); close(output);
end.
READ MORE

树状数组

zh

介绍

所谓树状数组,就是将线性的数组预处理成树状的结构以降低时间复杂度。先来看一幅经典的图:

其中的 a 数组为原生数组,c 数组为辅助数组,计算方式为:

$$c_1=a_1——{(1)}_{10}={(1)}_2$$ $$c_2=a_2+c_1——{(2)}_{10}={(10)}_2$$ $$\ldots$$

不难发现,$c_k$存储的实际上是从 $k$ 开始向前数 $k$ 的二进制表示中右边第一个 $1$ 所代表的数字个元素的和。这样写的好处便是可以利用位运算轻松计算 sum。上代码。

Code

var
n, i: longint;
a, c: array [1..10000] of longint;

//计算x最右边的1所代表的数字。
//如:lowbit(0b1100)=0b100
function lowbit(x: longint): longint;
begin
lowbit := x and (-x);
end;

//给a[index]加上x
procedure add(index, x: longint);
begin
inc(a[index], x);
while index<=n do
begin
inc(c[index], x);
inc(index, lowbit(index));
end;
end;

//求a[1~index]的和
function sum(index: longint): longint;
begin
sum := 0;
while index>0 do
begin
inc(sum, c[index]);
dec(index, lowbit(index));
end;
end;

var
s: longint;
op: longint;
x,y: longint;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

readln(n);
for i := 1 to n do
begin
read(a[i]);
add(i, a[i]);
end;

while not eof do
begin
read(op);
if op = 1 then //添加操作
begin
read(x, y);
Add(x, y);
end
else //求和操作
begin
read(s);
writeln(sum(s));
end;
end;

close(input); close(output);
end.
READ MORE

二进制的启示

zh

在学习数论时我们都知道:只用 2 的幂次可以组合出所有的正整数。这便是二进制的魅力——状态简单而又变化万千。

引子

实际算法中,常常有一些线性的但数据量特别大的问题,如区间求和、求最小值等。很多时候,为了把时间复杂度从 $O(n^2)$ 甚至更高的地方降下来,我们需要对数据进行一些预处理,以提高计算的速度。在这其中,有很大一部分是来自二进制运算特点的启发。

目录

  1. 树状数组
  2. RMQ
  3. LCA&树上倍增
READ MORE