题目大意： 输入n个数字，每个数字是长度为k的二进制数。现在每输入一个数，可以选择与上一次的结果进行同或或者是异或，问最大的结果。 思路： 显然dp是不行的。因为具有后效性。 没想到是个结论题，首先是可以发现同或的性质：同或=异或以后按位取反 那么我们可以将所有的数先异或起来。然后我们需要知道哪些数字需要按位取反。 这里需要知道一个知识点就是：对于一个二进制数x，按位取反 = x xor (2k−12^k-12k−1) 由于相同的数字异或结果为0。因此我们只要知道2k−12^k-12k−1的个数是偶数还是奇数就可以了。 因此答案就是：max(异或前缀和，异或前缀和 xor (2k−1)(2^k...

今年的题目如果只会模拟的话，也是可以拿普及一等的。虽然不太明白为啥今年的题目风格变成这样，但是也说明了一点：思维比算法往往更加重要。当然不是说算法不重要，只是我觉得很多时候算法限制了我们的思维。很多题目其实不用算法也可以做，但是一味地往算法上套，对我们的能力提升是帮助不大的。 T1 分糖果 简单的模拟题。但是10910^9109的数据量肯定是会炸的。因此看看有没有数学方法可以套。 可知最多可以拿的糖果数量是n-1。 那么先对k=L%n，至少是可以拿到k颗糖果的。现在考虑能多拿几颗。由于最多是R颗糖，如果n-1-k+L<=R，那么就可以拿到n-1颗糖果。否则我的数量就是R%n颗了。 代码：...

A string game 比较简单的一题。 显然首先需要对操作次数x进行取模n的操作，然后我们从x%n这个位置开始输出到最后，接着从0开始到x%n-1输出。就可以了。 代码： ">using namespace std; string s; int n; long long x; int main() { cin>>n>>x; cin>>s; x%=n; for(int i=x;i<s.size();i++)cout<<s[i]; for(int i=0;i<x;i++)cout<<s[i]; return 0; } ...

USACO2007月赛银组的一道题目，比较简单。 题目描述：有N头奶牛，已知最高奶牛的身高H和它的编号I。给出R个限制，每个限制给出一对数{A,B}表示A能看到B，这里的能看到表示B和至少一样高（有可能B比A高），并且[A,B]中间的奶牛高度都要比A和B矮。问这些奶牛最高的可能身高。思路：要让奶牛身高尽量高。那么对于某个纸条A->B来说，我们只希望[A+1,B-1]范围内的奶牛高度只比A和B低1。那么我们可以得到一个朴素算法，对于每次的纸条A->B，我们令[A+1,B-1]的奶牛高度都-1。这样我们可以保证最后得到的结果是尽量高的。复杂度是O(n^2)。考虑到n最大为10000，O...

题目描述：有一堆石子，一个无游标的天平，已知石子的重量，石子可以放天平的任意一边，问能否用石子称出某个询问的重量。 思路：首先可以发现石子最多100个，每个最重100，因此最大的能称出来的重量为10000。如果输入的询问重量超过10000，可以直接输出NO。显然会往01背包方向考虑。由于石子可以放天平两边进行减法，我们可以将石子再复制一份负数重量的。然后做01背包。那么一共有2*n颗石子，问他们组合可以有哪些重量。这是一个01背包。重量最大为10000。这里注意负数石子的处理，用一维滚动的01背包是不行的，因为负数的时候会导致逆序记录的背包出问题。不过可以用二维的。 如果一定要用一维的，显然正...

题目描述：有个X*Y的蛋糕，现在要均分成N块。每次切一刀都会把一个蛋糕分成2块，问这样切N-1次，得到的蛋糕中长宽比的最大值的最小值是多少。 思路：N<=10数据很小。考虑dfs。由于每个人分到蛋糕面积需要相同，显然我们不能随便切。假设当前蛋糕为X * Y，需要分N块。那么如果我们如果竖着切（分成左右两块），我们只能选择X/N * i的位置切。横着切（分成上下两块）同理，只能选择Y/N * i的位置切。这里i是整数。假设我们竖着切在X/N * i的位置上，我们会分成左右两块，而且我们可以分别确定左右两块要切多少刀。左边需要i-1刀分成i块，右边需要N-i-1刀分成N-i块。那么我们可以令...

前一阵子搞教材和其他事情，把博客给落下了。最近趁着找题目的机会，再争取多记录点博客题目。每日一题最近不能按顺序了，找题目优先了。只能先这样了。 题目描述：有两个人分别地图上的两个位置，现在两个人要相遇，问最短时间。一个人走8个方向每次一步，另一个走4个方向每次两步。(n,m<=1000) 思路：经典bfs问题。两个人相遇问题，显然一个比较常用的方法是离线处理。先bfs第一个人，记录下他到每个点的最少时间。接着bfs第二个人，也记录到每个点的最少时间。那么如果两人能在某个点相遇，相遇时间就是两人中时间大的那个。最后枚举所有的点，找一个最小的值。注意走两步的处理，在下面的代码中我处理成了走一...

很有意思的一道题，感觉csp2020的T3和T4都比较有质量，属于考思维的题目。题目链接：https://www.luogu.com.cn/problem/P7078 题目大意：有n条蛇，每条蛇都有一个体力值a[i]还有一个编号（1~n的编号）。这些蛇需要决斗，每轮决斗都是最强蛇考虑要不要吃掉最弱蛇。蛇的强弱我们以他们剩余的体力值作为判断，体力越多越强。假设有两条蛇体力相同，则编号大的更强。那么对于每轮决斗，最强蛇有两种决策：1.如果选择吃，那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值，实力最弱的蛇被吃掉，退出接下来的决斗。之后开始下一轮决斗。2.如果选择不吃，决斗立刻结束。每条蛇希望在...

T2挺良心，想法和写法都比较容易实现。题目链接：https://www.luogu.com.cn/problem/P7076 题目大意：存在编号为0~2^k-1种小动物，现在有m条饲养指南，每一条饲养要求为：若动物园里养了某种小动物的编号的二进制上pj位为1，则需要购买编号为qj的饲料。饲料一共有c种。现在给出n种动物园已经饲养的动物，请你计算需要购买的饲料，对于买过来的饲料，可能存在某些饲料可以养更多其他的动物（当前动物园还没有），请计算在不多购买饲料的情况下，有多少种新动物可以养。 0<=k<=64，n,m<=10^6,c<=10^8思路：先将已有的动物编号进行二进...

由于冲突没打上比赛，赛后只做了前两题。  A 二进制？十进制！  题目大意：给两个十进制数，把它们转换成二进制以后再以十进制的运算方法相加。思路：水题。直接转换十进制转二进制存到数组中，按位相加即可。没有进位，直接输出。 代码： #include<bits/stdc++.h> using namespace std; int A[111],B[111]; int main() { int a,b; cin>>a>>b; int t1,t2; t1=t2=0; while(a){ A[++t1]=a%2; a=a/2; } while(b){ B[++t2]=...

愚人节欢乐多。这场比赛娱乐为主，但是还是觉得自己好菜。有些题目感觉莫名其妙的  A 出愚人节欢乐赛  题目描述很长，不过都是废话。我把无可奉告复制了一下，交了上去AC了。不过好像其实啥都不用输出。  B 你这题，狗屁不通  这题属实恶心，看了眼毫无营养的题目描述，感觉应该是输出当前时间，然后看提示是UTC时间。百度了一下，wa了。换了几个模板，还是wa。想着会不会是04/01，交上去还是wa就这？结束后，看了别人代码，发现确实是04/01，在原代码上加了0，A了。今天白天再把昨天A的代码交了，又Wa了。后来发现，应该是根据当前的时间加0的。跟你当前提交时间有关系。例如现在是10点8分，那么UT...

前三题蛮简单，第4题不会了。这里放上前4题的题解。  A 炼金术师  题目大意：给一块无限长的画布，共有n次机会，每次可以从画布左端涂上一种长度为a[i]的颜色，第i次选择的颜色为为i。后涂的颜色会覆盖先涂的颜色。问给出n次的长度，一共可以产生多少种颜色。 思路：由于后涂的覆盖先涂的，因此我们可以倒着处理。从后往前遍历每次的长度，因此我们只需要维护一个最大值maxi表示当前的最大涂色长度，若当前的长度a[i]>maxi说明后面的涂色没能完全覆盖本次的涂色，因此我们就更新maxi，并且让答案+1 代码： #include<bits/stdc++.h> using namespa...

这次小白赛由于放在周六，所以没时间去打。稍微做了几题，看了一下题解，好像大部分是码量较大的题。这里稍微做了几道记录一下。  A 拼三角  题目大意：给6根棍子，问能不能找出3根组成一个三角形，同时剩下的3根也能组成三角形？思路：一开始的时候觉得拍个序找最小的3根组成三角形和较大的3根组成三角形就可以了。结果返回一发wa，后来发现是有反例的。那么还是暴力枚举吧，枚举其中的3根，然后看剩下的3根是否能同时组成三角形。复杂度O(n^4)代码： #include<bits/stdc++.h> using namespace std; int main() { int t; cin>&...

一不小心先开了T3，憋了好几天。题解一开始也看不懂，对我来说太难了。 题目链接：https://www.luogu.com.cn/problem/P7077 题目大意：给n个数a[i],给m个函数g[i]，其中函数有3种类型：type1：p v 给a[p]加上vtype2： v 对n个数同时乘上vtype3: 调用若干个函数（在1-m范围内），保证不会出现递归 给出一个序列Q是函数的调用序列，问调用完以后的a[i]数组是多少？n,m<=10^5，调用的函数不会超过10^6 思路:这题如果直接模拟的话，还是可以得到一个比较暴力的思路的。 先说说我的暴力做法： 假设只有type1，可以直接模...