应届本科签了中车株洲所，大家可以提问我来回答。23/8/21，人还活着，有问题可以接着问。但不保证及时回答。23/10/18，评论前可以扫下楼，看看有没有相关问题。尽量不要私信，你的问题也是大家的问题。还请不要问加班多不多，出差多不多。都是跟着项目走的。

签到题：AC数大于100的题 A 题意:给定A,B两位勇者的攻击力和生命值以及无限血量的魔王，每回合会对魔王造成等同于攻击力的伤害，回合结束后又会自相残杀，若不在同一个回合死亡，则活下来的一人会对魔王造成10倍伤害，若两人在同一回合死亡则不会造成十倍伤害，要求输出造成的伤害总和。思路:计算两个人的存活回合，若不相等，则存活回合大的造成十倍伤害。若相等，则不造成十倍伤害。两人合力造成伤害的回合等于存活回合少的回合数。 代码 B 题意：给定密码由0~9组成，知道密码中每个数的出现次数，每次输入后，密码的排列顺序会改变，求尝试解密的次数期望。思路：设这些数一共能组成n个数字，于是问题就变成了求n的大...

A 题意：给定一个长度为n的数组，可以做K次合并(合并后删除其中一个元素),要使得经过这K次操作后中位数最小。输出这个中位数。思路:操作只会让元素变大，所以最小的这个中位数就是排序后的第 个数，特判掉K=n-1即可。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48618026B 题意：给定长度为n的排列，求有多少对区间满足第K小数恰为X。思路：现在假设区间[L,R]是满足条件的最小区间，现在想要扩大区间，但是又不能改变新区间满足第K小数恰为X，所以只有a[L-1]>X 或者 a[R+1]>X区间...

#E 题意：给定一颗由n个点组成的树，第i个点的的权值 ，同时给定所有边权，边权为两个点的异或值，求有多少中满足要求的点权组合。 思路：当任意一个点的权值确定后，所有的点的权值也就通过边权间接唯一求出。 不妨设 ,进而推出所有点的权值，当 时, , 又因为 可以推导出 。所以问题就是求有几个x满足题意。 如何解决这个问题，让我们请出Kur1su。 我们把求x的问题考虑成有多少点被覆盖了n次。因为点有很多个，我们把它们看成区间**[a,b]。每次覆盖的时候就给a打上一个1标记，给b+1打上一个-1标记。对于区间[0,a-1]这一段的标记是0**，[a,b]为1，[b+1,inf]又为0。如此一...

参考视频 J 题意:在十字路口中，给定四个方向上所有车以及转向情况，每辆车完成转弯需要一秒，求在不违反交通规则的情况下最少需要多少秒使得所有车都完成转向。思路:1，车辆右转是不受限制的，使得每个方向上至多只有左转和直行两种情况。2，在一的基础上，可以知道整个十字路口不能有三盏以上的绿灯(不考虑右转的灯)。我们就可以生成一个2X4的矩阵，表示每个方向上直行和左转的车数。对于一个方向两盏绿灯只有四种情况这四种方向表示对应着易知，不考虑情况三，我们发现这是在一个2X2的矩阵里面，每次使一行或一列的两个数减一。要使所有的数都小于等于0，需要操作的最小次数是 ，现在我们考虑情况三，它无非就是对角线上减一...

参考博客,看不懂的话可以去这位巨巨的博客看。题意：给定两棵树，要求一个最大集合，使得集合里的所有元素在第一棵树上都存在祖先关系，在第二棵树上又没有祖先关系。输出这个集合的大小。思路：我们可以在第一棵树上dfs跑链，这样保证了第一棵树上的祖先关系，每个点在被放入集合的时候，都要判断这个点是否和已经在集合里面的点在第二棵树上构成祖先关系。第二棵树上的祖先关系可以通过DFS序来判断，同时用线段树来维护这个关系，用滑动窗口来维护答案。 #include<bits/stdc++.h> #define fi first #define se second #define mp make_pai...

F 题意： n份汉堡肉，m口锅,第i份汉堡肉烤熟需要时间 ,每份汉堡肉至多可以分成两次烤熟，即 ,任意时刻一口锅里至多烤一份汉堡肉，问烤熟所有汉堡肉需要的最小时间是多少并且输出每一份汉堡肉在几口锅中烤和烤的时刻（若有两口锅，按时间先后排列）。注意，这个时间指的是所有汉堡肉在这一时刻都已经被烤熟了。 思路: 首先去想这个最小时间是 然后设置每个锅的可使用时间是mintime，然后将汉堡肉按烤熟时间从大到小放进锅里面（其实可以按任意顺序），当某一口锅的时间被用满就换下一口，可以证明每份汉堡肉至多在两口锅中。然后输出答案即可。 证明： 假设红色是最大时间，紫色是第二大时间，整个矩形为可使用时间，由于...

B 题意：N个装有黑白球的盒子(每个盒子一定有且只有一个球),你需要知道所有盒子里面都是什么球，为此你需要开盒子，打开第i个盒子需要花费 的代价,同时你可以花费C的代价先知道里面有多少个黑球，现在问你期望花费。思路：只有两种策略第一种，直接全开了第二种，先知道有多少个黑球(同时你也知道有多少白球了)，然后对花费进行排序，从小到大开，能不再开后面盒的情况有且只有两种未开盒子数目等于目前剩余黑球数目 或者 未开盒子数目等于目前剩余白球数目。而这个概率恰为 (m 为未开数量)。设当前准备开第i个盒子（m=n-i+1)化简得到 。为了简便运算，i从n开始枚举。输出这两种情况的最小值就好。 //auth...

第一次打现场赛。题册一到手，翻到E题，题都没读完，A题就被xry秒了，队友鼓励师受到了极大鼓舞，然后推了一会发现暂时弄不出来就倒着看题去了，发现K可做，看榜确定是签到后就上机了。写了一发到现在没想明白WA哪里的代码就交了，由于我们是2人同一个题的防内鬼战术，xry就被我牵扯住了，调试半小时也不知道哪里不对就重新写了一遍交了，52min过了K。然后hxw就表演了半小时之内过G,J的个人表演。这个时候我队21名没法跟榜（第一次这么靠前，有点不知所措），hxw这时表示去推C的式子，我和xry就去F瞎搞去了。发午餐的时候我表示我不想搞下去了，就换去E了，搞了不知道多久出了个递推公式： ,然后分享给了队...

B:https://ac.nowcoder.com/acm/contest/9854/B题意：给你两个长度为n的序列a和b，你现在要对a中所有的数求和。同时对于b中每个元素，你可以把它加/减到a的序列和中，当然也可以不进行加/减。现在要你输出a的序列和在模y下的最大值。思路：看到y的范围不难想到dp，我们这里采用二维的形式，dp[i][j]表示第i个位置可以取到的数字大小。如此，状态转移方程也就很好想了。 if(dp[i-1][j])//有才能转移 { dp[i][(j+a[i])%y]=1; dp[i][(j+a[i]+...

在鬼扯之前先向将机会给到我们队伍的18级学长表示感谢。没有这次机会，我队本学年将没有任何比赛机会。我也不知道从何处说起。但要说起来也肯定很短。那么先说成绩？Fe。rk 544/676 铁尾。虽然自己嘴上说着这是一次锻炼，但是心里是真心想打出成绩。来说说我是如何演队友的吧！11点整，我把题册迅速翻了一遍，找到了特别短的G，一看题意，斐波那契数列里面找偶数，一看斐波那契数列，好家伙，奇奇偶。你以为我很快把它切了？不，我犯病了，我不敢敲，我把在看D的队友拉过来说了一遍我的思路，他们感觉没问题后，我又重新推了一遍，才敲上去，过样例，16min，1A.一看榜至少三百个队伍过了（我打完比赛才知道有一辆自爆...

B：https://ac.nowcoder.com/acm/contest/4370/B题意：t次查询，每次给你n个字符串，问你有没有某个串是其他更长（或者长度相等）的串的前缀。没有的话就输出Yes,若有，No。思路：查找大量字符串的前缀，很容易想到trie。唯一需要做的就是给这些字符串按照长度排个序。不过我为了处理同一个串出现多次，用了个map来维护（大可不必，只是比赛的时候慌了而已）。至此代码也就出来了。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=5e5+7;...

题目链接：https://codeforces.com/gym/102875/problem/H题意：t组数据，每组数据都是由一个长度为n的大串和m个小串与m个一点作用都没有的字符组成的，现在要问你在大串能分解成唯一的小串组合。如果可以输出"happymorsecode",如果不能由小串组成，输出"nonono",如果可以分解成很多个小串组合的情况，输出"puppymousecat"与方案数对128取模。思路:注意到一个细节，那就是m个小串长度在1~5。那么很容易联想到dp，考虑dp[i] 表示以第i位上字母为最后一个小串最后一个字母的方案数。那么对于每个位置我们最多枚举5次就OK了。但是值得...