牛客周赛 Round 86--D题    链接：https://ac.nowcoder.com/acm/contest/104637/D 来源：牛客网    思路：   结论：对于任意的x,y，最多不会超过三次操作   原因：由于当a==b时，a^b==0，所以只需要第一次操作和第二次操作时，都取原先的x和y进行相同的操作（记为c和d，且c==d），那么第三次操作一定可以取c,d，作c^d，结果为0   下面为分类讨论   对于一次操作取到0：x==y（这样x^y=0）或x&y==0   对于二次操作取到0：记 x op y == a （op为某个操作），有 a&y==0 ||...

赛后复盘--对于E题只能通过33.33%的思考，线段的排序优先级问题   链接：https://ac.nowcoder.com/acm/contest/103948/E 来源：牛客网  题目描述      在数轴上，一共有 n 条线段，小红已经将所有线段都染成了红色。小紫准备至少选择一条线段，将它们都染成紫色，并且使得不存在两个红色的线段相交，也不存在两个紫色的线段相交。  小紫能成功吗？如果可以，请你帮小紫输出一个染色方案，如果不可以，请输出-1。        思路   对于每一条线段，存储其左端点l，右端点r，以及其编号index   然后开一个vector<int&gt...

链接：https://ac.nowcoder.com/acm/contest/102896/F 来源：牛客网  题目描述（简化）    有一个 n 行 m 列的二维垂直网格迷宫，我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格。每个方格要么是空方格 ‘.’，要么是障碍物方格 ‘#’。特别的，迷宫的边缘外视作无法被摧毁的边界。 每一个障碍物的初始耐久均为 h。方向向下的水流如果接触到障碍物，会使其下方的障碍物每秒损失 1 点耐久。当耐久为 0 时，再次造成耐久损失，则视为摧毁该障碍物。摧毁后，障碍物的位...

牛客周赛 round 82 A--F   A.夹心饼干   一个string   #include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; if(s[0]==s[2]) cout<<"YES"; else cout<<"NO"; return 0; } B.食堂大作战1.0   一个set求size() #include<bits/stdc++.h> using n...

F-怎么写线性SPJ_牛客周赛 Round 82   推导思路请看大佬写的这一篇：牛客周赛 Round 82 解题报告 | 珂学家_牛客博客   借鉴此思路，写一个十分简化的F题C++代码   #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; cout<<__lg(n)+1<<endl; for(int i=1;i<=n;i++){ cout<<__lg(i&(-i))+1&lt...

链接：https://ac.nowcoder.com/acm/problem/50505 来源：牛客网  题目描述      有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。 我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。      输入描述:  第一行两个数N和Q，N表示树的节点数，Q表示要保留的树枝数量。 接下来N-1行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝...

链接：https://ac.nowcoder.com/acm/contest/24213/1040 来源：牛客网  题目描述       在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。   题目给...

思路：贪心+分类讨论   链接：https://ac.nowcoder.com/acm/problem/235246 来源：牛客网  题目描述       我国历史上有个著名的故事： 那是在2300年以前。齐国的大将军田忌喜欢赛马。他经常和齐王赛马。他和齐王都有三匹马：常规马，上级马，超级马。一共赛三局，每局的胜者可以从负者这里取得200银币。每匹马只能用一次。齐王的马好，同等级的马，齐王的总是比田忌的要好一点。于是每次和齐王赛马，田忌总会输600银币。  田忌很沮丧，直到他遇到了著名的军师――孙膑。田忌采用了孙膑的计策之后，三场比赛下来，轻松而优雅地赢了齐王200银币。这...

牛客周赛--round 80--F题--构造+贪心（应该算是贪心吧）   链接：https://ac.nowcoder.com/acm/contest/101196/F 来源：牛客网  题目描述    集训队有 2×n 名队员备战鹿瓜杯比赛。已知第 i 名队员的实力为 i ，现在需要准备 n 场训练赛，将实力相近的队员匹配到一起进行训练。  每场训练赛为两人进行对局，每个队员都需要参加且仅参加一场训练赛。每一场训练赛的不和谐度为参赛双方的实力之差的绝对值。请你判断，在所有训练赛的组合方式中，是否存在不和谐度之和恰好为 k 的情况。如果有，输出任意一种组合...

牛客周赛--round 80--G题--dp+逆元   链接：https://ac.nowcoder.com/acm/contest/101196/G 来源：牛客网  题目描述      小红和小紫正在对弈。在围棋规则中，每吃掉对方的一枚棋子，就需要将这枚棋子放入棋盖中。然而，棋盖空间不大，她们任何一方吃子数量达到 x 就输了。 当然，我们不需要考虑具体的对弈局面，模型简化如下，每个回合将会依次执行以下两步： 小红有 p1 的概率吃掉对方一枚棋子； 小紫有 p2 的概率吃掉对方一枚棋子。  谁吃子数量达到 x 就输了。小红执黑先手，她想知道自己最终获胜的...

牛客周赛--round 80--G题--dp+逆元   链接：https://ac.nowcoder.com/acm/contest/101196/G 来源：牛客网  题目描述      小红和小紫正在对弈。在围棋规则中，每吃掉对方的一枚棋子，就需要将这枚棋子放入棋盖中。然而，棋盖空间不大，她们任何一方吃子数量达到 x 就输了。 当然，我们不需要考虑具体的对弈局面，模型简化如下，每个回合将会依次执行以下两步： 小红有 p1 的概率吃掉对方一枚棋子； 小紫有 p2 的概率吃掉对方一枚棋子。  谁吃子数量达到 x 就输了。小红执黑先手，她想知道自己最终获胜的...

链接：https://ac.nowcoder.com/acm/problem/25879 来源：牛客网  题目描述     数据总库的信号墙有n个电极插头，每个插头有一个信号ai,   小T可以使在区间[ l,r ]内的所有信号加上一个值k。   对于区间[ l,r ]的信号强度有一个计算公式：   我们定义      则信号强度就为：      你可以认为f(i)就是第i个插头的信号强度。   现在小T一会儿修改信号值，一会儿询问信号强度，你是数据库的管理员，为了不被小TD，所以你要告诉他信号强度是多少。    输入描述:  第一行两个整数n,Q 第二行n个整数...

链接：https://ac.nowcoder.com/acm/contest/26896/1010 来源：牛客网  题目描述       Keven 特别喜欢线段树，他给你一个长度为 n 的序列，对序列进行m次操作。   操作有两种：   1 l r k：表示将下标在 [l , r] 区间内的数字替换成 [k,k+1,…,k+r−l]   2 l r ：表示查询区间 [l , r] 的区间和    输入描述:    第一行两个整数 n、m，表示序列的长度和操作次数（1<...

链接：https://ac.nowcoder.com/acm/contest/26896/1036 来源：牛客网  题目描述       萧芸斓是Z国的公主，平时的一大爱好是采花。   今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。   花园足够大，容纳了 n 朵花，花有 c 种颜色（用整数 1−c 表示），且花是排成一排的，以便于公主采花。 公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能...