吴国庆

分类

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6) 题解(38)

/ 注册

全部文章（共106篇）

【每日一题】7月27日乌龟棋

题解：每一步最多有4种选择，并且题目保证全部卡片用光后一定会正好走到终点，那么我们直接记忆化搜索就可以dp[i][j][k][l] 表示当前1，2，3，4卡片还剩i,j,k,l个得到的最大分数。时间复杂度为O(404040*40) 代码： #include<bits/stdc++.h>...

2020-07-26

0 723

[每日一题]矩阵取数游戏

解题报告：看到每行取数的得分 = 被取走的元素值 * 2^i，由于i是递增的。所以第一想法就是把大的留在最后，即每次取每行首尾最小的那个，但是样例二则轻易的否定这种做法。考虑到其实每行的贡献是独立的，相当于把每次操作拆成n次操作，那么我们考虑怎么得到一行的最大值。可以发现每次操作的区间是不断缩...

2020-07-10

0 737

毒瘤xor[每日一题]

异或操作，直接考虑如何构造x对应二进制的每一位能使 x ^ a[i] 最大。那么x的第i位为0时当前位的贡献为[l,r]内a[j]的第i位为1的个数*2^i。所以我们只需要预处理出a[i]对应二进制为的前缀1的个数，然后每次询问枚举每一位分类讨论就好了 #include<bits/stdc++...

2020-07-09

0 696

【题解】西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛 BCDEF

B 先选出n-1种颜色C(n,n-1)=n剩下的就是n-1个不同的数放n个位置然后从n-1种颜色种选择一个作为重复的颜色 C(n-1,1)=n-1在从n个位置选择两个放重复颜色，C(n,2)最后n-2个位置为(n-2)!整理： #include<bits/stdc++.h> #defi...

2020-06-21

1 751

德玛西亚万岁

题解：由于本题数据范围较小，很容易想到状态压缩Dp的方式进行模拟，我们让dp[i][S]表示第i行的勇士状态为S(将s拆成二进制位，1表示该为有勇士)时的方案数，那么最后总的答案就为 ,所以直接枚举就可以啦！注意要过滤掉其中一些非法状态，就是题目所说的那些，为了检测方便，可以将每行的状态转换为一个...

2020-06-02

0 607

旅游

题解：分析一下题目的每次操作，其实就是u节点选后，与其相连的点都不能在选，然后要求选择最多的点，那么这就是一个树的最大独立集问题，我们用得dp[][]解决，并且由于题目要求S点必须选择，那么我们将点S设为根够令dp[i][0]表示i节点不选时，以i为根的子树的最大独立集，dp[i][1]则为选时...

2020-06-01

0 710

小AA的数列

题解：很套路的一道题：由于所求的是异或之和，我们知道位运算不产生进位，所以每个数位与位之间的贡献是独立的，不想不影响，那么我们考虑按位计算对答案的贡献即可，令pre[i][j]表示前i个数中第j位为1的个数，那么当我们枚举所有区间的左端点i时，如果pre[i-1][j]是奇数，那么所有能对答案...

2020-05-26

0 740

[JSOI2007]建筑抢修

题解：很明显的贪心题目，首先我们考虑按t2排序，因为我们先完成t2小的，那么这会比先完成t2大的留给后面人的时间更多。但是这样会出现一个问题就是由一个项目虽然她的t2很小，但是他的t1占用了后面太多的时间，使后面又任务不能及时完成。那么这时候我们就需要给程序填加一个反悔的功能：即当我们发现一个任...

2020-05-26

0 639

[CQOI2009]中位数图

题目描述给出1-n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。题解：由于题目所给的是一个排列，即1~n每个数值出现一次，那么一个连续的子序列要想包含b只有3中情况，假设b在pos i ~ pos pos ~ j i ...

2020-05-21

0 769

图的遍历

题解：假设图联通，那么由于每次走两步，相当于在规定一个起点后只能走奇偶性相同的点，所以，对于每一个连通块，我们只需要01染色后，看一下有没有相同颜色连边的情况，如果有，那就说明奇偶性不同的点能够到达，也就是说，我们可以遍历整张图，如果没有，那么我们直接加一条即可，然后如果图不连通，那么首先，我们最...

2020-05-20

0 774