Doraemon's Blog

计蒜客之前比赛的一道题目，记录一下 G Millionaire Madness A close friend of yours, a duck with financial problems, has requested your help with a matter that will help him pay off his debts. He is the nephew of an extremely wealthy duck, who has a large vault, filled with mountains of coins. This wealthy duck has a certain coin in his possession which has a lot of sentimental value to him. Usually, it is kept under a protective glass dome on a velvet cushion.However, during a recent relocating of the coins in t ...

写这个代码花了一个小时，因为刚学了一点点OS模块，还不是很熟悉，写完后功能也都有，但是！！！导出为exe文件时不小心误删了py文件，气死我了！又重新写了一遍。 新加了GUI界面的整理页面小程序，效果如下图所示 GitHub项目地址 Here 效果图： {height=”400”,width=”400”} CODE1（不含有重命名）12345678910111213141516171819202122232425262728293031323334353637383940414243444546import osfrom shutil import copyfiledef create(): print('------创建文件夹------') for i in var_list: Path_now = os.path.join(Path, i).replace('\\', '/') if(not os.path.exists(Path_now)): os.m ...

前言 趁着还没忘记录一下吧🐷 哈希能干些啥？学一个新算法首先一定要知道学这个能干些啥对吧，我们是为了用某个东西而去学这个东西而不是盲目目的的学，现在假如给你两段字符串让你去比较他们是否相同，如果暴力做法就是从头到尾扫一遍，都相同则相同，复杂度为O(N)，假如数据量非常大，而且字符串长度很大，现在题目就变成了给你n个字符串，现在又给你t个字符串问你每一个字符串是否在这n个字符串中，平常做法时间复杂度O(tt个字符串每一个字符串长度\n)，若用哈希预处理时间复杂度降到O(t*字符串长度+n)，也就是把那n个字符串预先处理一下，使得接下来比较每一个字符串时时间复杂度变成O(1)，让我们来看一下具体怎么操作吧 思想其实哈希和二进制思想是类似的，如果让你比较两个二进制串是否相同，你肯定会想到把二进制转成十进制比较起来会更方便，因为复杂度降低到了O(1)，不用你去逐位比较了，那字符串也是可以像二进制那样转换成为一个数字的，例如：abcd这个字符串可以转换成为ap^3^+b\p^2^+c*p^1^+d*p^0^，这里的p值是多少先不说，每一个字符都是有acall值的，我们可以直接利用这一点把每 ...

最友好的一次积分赛2333应该也是最后一个个人积分赛了，不知道最后一次会不会是团队赛，再说吧，已经八月十五了，自从集训以来每天都有训练，虽然晚上一般都是有些时间去记录一些题解的，但是懒癌晚期的我真的不想去写，终于今天下定决心，趁着这两天我要补一下题解，把最近有意义的题目记录一下，也算是一个复习吧🎉 D 何不好的晨练描述 何不好是一名晨练爱好者，每天他都要一大早出门进行晨跑锻炼，何不好生活的城市很大， 同时也比较繁荣，路边高楼耸立，道路上车辆往来，川流不息。 晨练的同时还可以欣赏路边的风景，于是，何不好打算每天选择 M 条路段，其中包括 N 个路口。 但何不好想要从起点开始不重复的跑完所有路段，并且跑回起点，苦于是学渣的他不知道 能不能完成这个条件，于是他向你寻求帮助。 输入数据 第一行给定两个整数 N , M 。 接下来 M 行，每行有两个整数 U，V 代表路段相连的两个路口。 1 ≤ N ≤ 100,000. 0 ≤ M ≤ 100,000. 毎对儿 U, V 互不相同，且 U, V 不同。 输出数据 若能完成这个条件则输出Yes，否则输出No。 样例输入 4 4 1 2 2 ...

题目面板 提取码：k2fu A. 胡图图的数学难题这道题很有意思让你求斐波那契数列的平方和，一篇易懂的题解 得到公式以后直接一个矩阵快速幂就解决了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)using namespace std;typedef long long ll;const ll MOD=1e9+7;struct node{ ll mat[2][2]; void set(){ memset(mat,0,sizeof mat); for(int i=0;i<2;i++) mat[i][i]=1; } node operator * (const node &o){ node ans; for(int ...

dfs标记的位置太重要了，放在不同位置产生的效果都有巨大的差别，记录今天的一些dfs记忆化搜索题目 A- Function Run Fun题目链接 12345678910111213141516171819202122232425#include<stdio.h>#include<string>#include<string.h>#include<algorithm>#include<iostream>typedef long long ll;using namespace std;ll used[50][50][50];ll w(int x,int y,int z){ if(x<=0||y<=0||z<=0) return 1; if(x>20||y>20||z>20) return w(20,20,20); if(used[x][y][z]) return used[x][y][z]; if(x<y&&y<z) return used[x][y] ...

学习了最短路后，感觉自己理解真的很一般，只会一些模板题目，稍微变一下就死了，而且发现我的思维很死，只会写套路题，做那些稍微灵活一点的题目感觉就很吃力，希望以后能有好转 B 张仙女的愧疚 张仙女最近痴迷于游戏，可是他每周都得为学弟们准备一场积分赛。但，不是谁都能成为 时间管理大师。在游戏的诱惑下，他不小心出了几道难题，导致学弟们的心态可能爆炸，终于 他感到了深深的愧疚。决定这次一定友好一点。 他想到了一个有趣且简单的问题，准备交给学弟们解决。 给你一个数组N，数组的下标从1开始，数组中的每个数的值为A**i，你需要在这个数组中 找到两个数，使他们的数值和与他们的下标的差的绝对值相等，两个数为一组，张仙女想考考 你，在这个数组中你最多能找到可以满足题意的几组数。 输入 单组输入 第一行为数组的大小N(2 ⩽ N ⩽ 200000) 接下来一行N个以空格区分开的数表示数组中的值A**i1 ≤ A**i ≤ 109 (1 ≤ i ≤ N) 输出数据 一个数字，表示答案 样例输入 6 2 3 3 1 3 1 样例输出 3 分析题意很简单求数组里面有多少对数满足数值和等于下标差，列出等式a[ ...

前两天打了第二场积分赛，难度明显比上次高，感觉更考验思维了，收集了一些我认为有价值的题目，因为太懒了，不想自己写思路题解了，搬来了别人的代码和题解，以后争取养成保存代码的习惯🐷 A 徐半仙的数学难题 描述 徐半仙经常修炼。但是每次修炼所能提升的功力确是不确定的（可能是功力还不够深厚 吧）。 每次修炼结束之后，徐半仙的脑海中就会浮现出两个数字，n和m，他的师父跟他说他每 次修炼增加的功力就是由这两个数决定的。每次增加的功力为(n!!!)%m，即n的阶乘的阶乘的 阶乘对m取模之后的值。 徐半仙想让你帮他写一个程序，通过n和m得到他每次修炼之后提升了多少功力。如果这 次修炼后提升的功力为0，输出baigei 输入数据 多组输入，第一行一个正整数t(1 ≤ t ≤ 105)表示数据组数 每组数据包含两个整数n, m(0 ≤ n ≤ 109, 1 ≤ m ≤ 109) 输出数据 对于每组数据，如果答案为0，输出baigei，否则输出答案（每次修炼后提升的功力） 样例输入 1234522 65532 2 样例输出 1232baigei 提示 在样例中,(2!!!) = ...

A - Red and Black There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles. Write a program to count the number of black tiles which he can reach by repeating the moves described above. Input The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H ...

集训开始了对矩阵快速幂的讲解，但是讲解的非常不好，基本没讲，这导致我这个之前就不知道矩阵快速幂的蒟蒻不得不自己乖乖的去网上查资料学习，找到了两个比较不错的视频讲解，具体可以看清单里面的转载，我来记录一下矩阵快速幂的基本用法🐷 矩阵乘法学习过线性代数或者离散数学的应该都知道矩阵之间的乘法怎么做，知道的可以跳过，矩阵相乘有一个前提条件，就是前一个矩阵的列数必须等于后一个矩阵的行数两个矩阵才能做乘法运算，这是因为矩阵是不满足交换律的，他们相乘得到的矩阵的元素等于这个元素所在的行对应第一个矩阵的行元素依次乘以这个得到的矩阵元素列数对应第二个矩阵的列元素，很绕口，举个例子，假如两个矩阵相乘后得到了新的矩阵，这个矩阵的第一个元素是在第一行第一列对吧，那么这个元素就是第一个矩阵的第一行和第二个矩阵的第二列元素依次相乘再累加的结果，这样你就知道为什么第一个矩阵的列数必须和第二个矩阵行数相同了吧。 那在纸上你肯定会算了，怎么把它转化成代码呢？ CODE123456789101112131415161718192021222324252627282930struct mat{ ll m[2 ...