题目链接 题意： 给出由小写字母，'?'和'*'组成的字符串s，仅由小写字母组成的字符串t,问按照规则s能否变成t. 规则如下：首先给出定义的[好字母]的字符串，[好字母]之外的都是[坏字母],对于s中每个‘?’，规定其必须替换为一个[好字母] 对于s中的每个‘*’，规定其必须替换为0个或者多个坏字母。 思路： 显然带的会比较难搞。所以只说带的情况 我WA了好多次，原因是一开始读错题（或者题意不太清楚？），认为*只能最多替换一个[坏字母] 后来在这个思路上改，越改越复杂orz 仔细想一下，关键点有两个，一个是当前位置有三种情况{没有经过*,经过且仍在的作用域内，经过且已经出了的作用域} 如何知道的作用域呢？由于的替换是连续的，因此只 …

题意：k^D=n(%p),求最小的D (1<=K, P, N<=10^9) 思路：出题人英文水平捉鸡。。。。 扩展BSGS算法即可，注意p>=n的时候显然是无解的，判掉。 /* *********************************************** Author :111qqz Created Time :Mon 24 Jul 2017 09:43:41 PM CST File Name :2815.cpp ************************************************ */ #include <cstdio> #include …

Description 已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。 Input  每个测试文件中最多包含100组测试数据。  每组数据中，每行包含3个正整数a,p,b。  当a=p=b=0时，表示测试数据读入完全。 Output  对于每组数据，输出一行。  如果无解，输出“No Solution”（不含引号），否则输出最小自然数解。 Sample Input 5 58 33 2 4 3 0 0 0 Sample Output 9 No Solution HINT  100%的数据，a,p,b≤1e9。 2016.3.29新加数据一组 by 1430586275 思路：BSGS算法，需要注意这里没有保 …

离散对数（Discrete Logarithm）问题是这样一个问题，它是对于模方程 a^x=b(mod prime)，求满足条件的X，或者得出不存在这样的X 最暴力的思路，那么就是枚举x? 根据费马小定理，只需要枚举[0,p-1) 但是还是很大...我们不禁想到把x写成x=A*m+B的形式，m=ceil(sqrt(p)) 因此有 ，变形得到 然后预处理一边存到map中，从小到大枚举另一边看是否存在... 我们可以设 ，其中 , ，这样的话化简后的方程就是 就可以不用求出逆元，要注意只是不用求出逆元，而不是没有用到逆元的存在 就可以不用求出逆元，要注意只是不用求出逆元，而不是没有用到逆元的存在 就可以不用求出逆元，要注意只是不用求出 …

题目链接 题意： Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that BL == N (mod P) 思路：bsgs算法 详情见BSGS算法笔记 然后被map的count坑了一下？ 我想判断map中某个key是否存在，用count会TLE，find也会TLE,[]可以通过....不太懂，复杂度不都 …

题目链接 题意：有２种货币，分别为C和D.给出n种资源的代价和美丽度，每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买２个资源，问最大美丽度，不能的话输出０． 思路：首先显然三种情况。。。CC，CD,DD. CD直接扫一遍。。重点是CC和DD 一开始思路错掉了。。全程写two pointer wa4...一直调。。 最后恍然大悟。。发现two pointer非常错啊。。。 其实正解也很简单？ 先去跑步了orz 只要想办法维护每个代价的最大美丽度就好了(更准确得说，是维护小于等于某代价的最大美丽度) 直接BIT搞。维护一个前缀max...好像很稳啊？ 不过我竟然对于BIT能维护前缀max吃了一 …

题目链接 题意：有n个Ｔ恤，每个价格都不同，有三种颜色，分别用1,2,3表示，每件Ｔ恤给出前xiong和后背的颜色。现在有m个顾客排成一队，对于每个顾客，给出他喜欢的颜色，只要一个Ｔ恤的前xiong或者后背的颜色之一满足该颜色即可。顾客总希望买符合他喜欢颜色的Ｔ恤中价格最低的。现在问每个顾客买到的Ｔ恤的价格，如果某个顾客没有买Ｔ恤，输出-1 思路：贪一下？ 对于每个颜色，找到价格最低的。记录的时候顺便记录id，以标记某件有２个颜色的衣服是否卖出去了。 １A美滋滋 /* *********************************************** Author :111qqz Created Time :2017 …

题目链接 题意：初始有一个锅，每t分钟可以做好k个饼，现在需要N个饼。还可以另外建一个锅，花费d时间，建好以后两个锅可以并行烙饼。问是否应该建锅？（以期减少烙饼时间） 思路：求出两种情况下的总时间，比较一下。 只有一个锅的情况很好求。 两个锅的情况比较麻烦，不如模拟时间流逝？ 反正最多也就1E6的时间。。。模拟一下。。。稳。。 /* *********************************************** Author :111qqz Created Time :2017年05月11日 星期四 15时29分43秒 File Name :A.cpp …

2748: [HAOI2012]音量调节 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1814 Solved: 1148 [Submit][Status][Discuss] Description 一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。 音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大 …

2257: [Jsoi2009]瓶子和燃料 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1246 Solved: 756 [Submit][Status][Discuss] Description jyy就一直想着尽快回地球，可惜他飞船的燃料不够了。 有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy 的飞船上共有 N个瓶子(1<=N<=1000) ，经过协商，火星人只要其中的K 个 。 jyy 将 K个瓶子交给火星人之后，火星人用它们装一些燃料给 jyy。所有的瓶子都没有刻度，只 在瓶口标注了容量，第i个瓶子的容量为Vi（Vi 为整数，并 …