【题目链接】 样例输入1 5 5 6 0 4 5 1 1 3 4 1 2 2 3 1 3 1 2 1 4 样例输出1 55 样例输入2 1 -100 0 0 样例输出2 0 Hint 在第一个样本中。 在第一分钟，dlsj提交了第一个问题，然后1乘以5+6=111×5+6=11积分。 在第二分钟，dlsj提交了第二个问题，2乘4+5=132×4+5=13积分。 在第三分钟，dlsj提交了第三个问题，3乘3+4=133×3+4=13积分。 在第四分钟，dlsj提交了第四个问题，4乘2+3=114×2+3=11积分。 在第五分钟，dlsj提交了第...

【题目链接】 题目意思 给一个T表示案例个数，然后每个案例给出三个数字n(0 < n <= 100000),m(0 < m <= 100),k(0 < k <= 100000)，表示有n*m的方格，方格中有k个黑色方格，后面k行，每行给一个黑色方格的坐标(x,y)，其中保证(0 解题思路 暴力大法好。。。 up数组表示遍历到第i行时(即up更新第i次时)，每一列的黑格子所在的最高行 AC代码 #include <iostream> #include <climits> #include <algorithm>...

【题目链接】 题目意思 第一行给两个整数n m，n表示房间数，m表示每个月购买的的灯泡数，随后给出n个数，表示每个房间的灯泡数（每个灯泡只需要更换一次），每个月从第一个房间遍历到第n个房间，当该房间的灯泡数小于等于现在有的灯泡数时，更新该房间的灯泡（只更新一次）。 然后给出q次询问，问你在某一个月时，已经更换灯泡的房间数和现在剩余的灯泡。（当所有房间灯泡都更换后，不再买入新的灯泡。） 样例输入 5 4 3 10 5 2 7 10 5 1 4 8 7 2 3 6 4 7 样例输出 4 0 1 1 3 6 5 1 5 1 2 0 3 2 4 4 3 6 ...

【题目链接】 样例输入 5 3 1 2 3 4 5 1 1 3 2 5 0 1 4 5 样例输出 10 8 解题思路 一个树状数组维护前缀和，另一个树状数组维护(n-i+1)*aa[i] AC代码 #include <iostream> #define ll long long using namespace std; ll c1[100005], c2[100005], aa[100005]; ll lowbit(ll k) { return k & (-k); } void update1(ll k,ll x) { w...

【题目链接】 样例输入 1 8 2 1 1 2 2 2 1 1 1 4 2 1 1 2 2 2 2 2 1 4 0 0 1 1 1 1 1 1 样例输出 3 解题思路 纯暴力，STL的使用，一行中出现相同的pair要去重！！！ AC代码 #include <iostream> #include <map> #include <utility> #include <cstring> #include <algorithm> using namespace std; pair<int, i...

【题目链接】 样例输入 3 1 4 4 1 3 3 样例输出 10 解题思路 It’s guaranteed that a wave will not cover the other completely. 题目保证了不完全覆盖，并且保证x1<=x2与y1<=y2不同时成立，所以大大简化难度。 首先考虑n==2的情况，假设第二个点（x2,y2）已经画在坐标上了，然后第一个点（x1,y1）两种情况 1.如果x1 < x2，那么y1 > y2，那么ans += x1+y1-y2; 2.如果x1 > x2，那么y1 < y2，那...

【题目链接】 样例输入 2 3 1 4 2 样例输出 2 84 解题思路 0~2^k-1中，任何一个数对应的同或和为0的数有且仅有一个。 首先会想到第一个有2^k种放法，第二个至第n-1个有2^k-1种放法。 至于第n个，假设第一个数和倒数第二个数不相等，那么最后一个数有2^k-2种放法。 如果倒数第二个数和第一个数相等呢？显然最后一个数字有2^k-1种放法，由于在第三点时已经计算过2^k-2种放法了，所以这里认为最后一个数字是一个定值，所以我们还需要加上ans[n-2]，然后整个做法就出来了，注意先预处理2的次幂，不然容易超时。 结论：ans...

【题目链接】 题目意思 T组案例，第一行T，第二行两个数字N，M，表示有N种船只，M次询问，接下来N行，每行两个数字v[i],c[i]，每种船只的载货量为v[i]，每种船只有2^c[i]-1种，有M次询问，每次询问给出一个数字s，问有多少种载货方式填满容量s。 样例输入 1 1 2 2 1 1 2 样例输出 0 1 解题思路 针对与每种船有2 ^ c[i]-1，可以想到任何一个数字都可以由2 ^ 0+2 ^ 1+2 ^ 2+…+2 ^ (c[i]-1)中的任意项组成，因此，可以将1，2，4，8，16 ，2^(c[i]-1)个船看成一种船，然后进行01背包判断有多少种装满的方...

【题目链接】 题目意思 有肉，鱼，巧克力三种食物，对于连续的三个食物， 1.这三个食物不能都相同 2.若三种食物都有的情况，巧克力不能在中间 3.如果两边是巧克力，中间不能是肉或鱼，求方案数 样例输入 1 1 2 2 1 1 2 样例输出 0 1 解题思路 杜教BM线性递推！！！ 杜教牛逼！！！ 使用方法：暴力前几项，放入vector，直接交。 AC代码 #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include &...

【题目链接】 题目意思 每个案例给你一串01字符，0表示红灯，1表示绿灯，每一秒之后都会改变所有的灯的状态，1变0，0变1，只能通过绿灯，求任意两点距离的总和。 样例输入 3 101 011 11010 样例输出 12 15 43 Hint For the first sample test case, it’s easy to calculate that t(0,1)=1, t(0,2)=2, t(0,3)=3, t(1,2)=2, t(1,3)=3 and t(2,3)=1, so the answer is 1+2+3+2+3+1=12. For the second sa...

【题目链接】 题目意思 图灵停机问题，判断是否会停机，停机输出Yes，否则No。 Sample Input 4 2 add 1 blt 5 1 3 add 252 add 1 bgt 252 2 2 add 2 bne 7 1 3 add 1 bne 252 1 beq 252 1 Sample Output Yes Yes No No Hint For the second sample test case, note that is a 8-bit register, so after four “add 1” instructions the value of wil...

【题目链接】 题意 给你三个数字n m k，问你能否找到一个三角形面积为n * m / k，其中保证三角形三个点均为整数，并且横坐标x满足0 < x < n，纵坐标y满足0 < y < m，如果存在该三角形，输出YES，并输出三个点的坐标，否则，直接输出NO。 examples input 4 3 3 output YES 1 0 2 3 4 1 input 4 4 7 output NO 思路 1.每个坐标为整数的三角形的面积 * 2是整数。(可证明) 2.由1可得若存在满足题意的三角形，则n,m,k一定满足式子 2mn % k == 0。所以此时可以判...

PTA乙级题 1086. 就不告诉你 （15 分） 【题目链接】 特判一下前导零就好了 #include <iostream> using namespace std; int main() { int a, b; scanf("%d%d", &a, &b); while (a % 10 == 0) a /= 10; while (b % 10 == 0) b /= 10; int ans = a * b; if (ans == 0) printf("0"); bool f = false;...

PTA乙级题 1087. 有多少不同的值 （20 分） 【题目链接】 set自动去重好评 #include <iostream> #include <set> using namespace std; int main() { int n; scanf("%d", &n); set<int>s; for (int i = 1; i <= n; i++) s.insert(i / 2 + i / 3 + i / 5); printf("%d", s.size()); }