1010 Bragging Dice 题意： YahAHa和Peanut各掷一次骰子，YahAHa先手，进行声明；Peanut则可以挑战，如果符合声明，则YahAHa胜利，反之。Peanut也可以继续声明，但声明的骰子数和点数有一个要比之前的声明大。 另外有三条规则： 如果没有人声明“有x个1点的筛子”，那么1点可认为是任意点数 如果一个杯子中所有筛子点数相同，就认为杯子中还有一个同点数的筛子 如果一个杯子中筛子的点数各不相同，则认为各个点数的筛子个数为0 优先满足第三条规则，两个玩家都知道两个杯子中每个筛子的点数。 问在最优策略下YahAHa是否能够获胜。 思路： 除杯中的筛子点数全部不同，...

1006 Maex 题意： 给定一棵n个节点的树，给每个节点标上0~n-1的权重，求各子树MEX和的最大值 思路： 易知MEX的最大值有一条链构成，统计子树大小然后从上往下去搜索每个叶子即可。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; int n; const int N=5e5+10; vector<ll> v[N]; ll son[N],siz1[N]; ll dfss(int u,int fa){ son[u]=1; for(auto y:v[u]){ if(y==...

1004 Black Magic 题意： 有（0，0），（0，1），（1，0），（1，1）四种方块。相邻的方块间连接的是黑色的，则看作是联通的。求联通块的最大最小数量。 思路： 最小的情况是，（1，1）连在一起，左右两边用（0,1）,(1,0)连成一个连通块，剩下的（0，1）（1，0）连接。 最大的情况是，我们将所有的（1，0） 放在最左边，再将所有的 （0，1）放在最右边，再尽量用（1，1） 将 （0，0） 隔开即可 代码： #include<bits/stdc++.h> using namespace std; int e,l,r,b,t; int ma(int e,int l...

1004 Quel'Thalas 题意： 问最少需要画多少条不过原点的直线，能经过第一象限中（0，0）到（n,n）这个正方形上除（0，0）的所有的点。 思路： 作 2 n条x+y=bx + y = bx+y=b的直线即可。故答案为 2n。 代码： #include <bits/stdc++.h> using namespace std; int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); printf("%d\n",2*n); } return 0; }  1001 Theram...

1007 Even Tree Split 题意： 给定一个有n个节点的树，保证n是偶数。 您将删除一些边（至少1条），并且必须让每个剩余的连通块具有偶数个顶点。求删除的方法数，模998244353。 思路： 一个节点的子树数目为偶数时可以删一条。用dfs求出最多删除的边数，每条边都是选或不选，最后的方法数即为：2cnt−12^{cnt}-12cnt−1种情况。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10, M = N * 2,mod = 9...

2022牛客多校第一场  A Villages：Landlines G Lexicographical Maximum D Mocha and Railgun  A Villages：Landlines 题意： 在一维坐标上存在着 n 个建筑物，其中一个为发电站，剩余 n-1 个为用电建筑物 ，你可以建造一些电塔来联通发电站与建筑物。发电站与用电建筑物都有自己的接收范围，在该范围中建造电塔使该建筑物联入电力系统（无需电线），电塔之间的连接需要电线，当所有建筑物联入时，需要最短的电线长度。 思路： 将接受范围看作区间，区间出现交集则不需要加电线。将区间排序后，将所有区间连通，注意更新区间右端。 ...

C Concatenation 题意： 给定 n 个仅包含 0，1，2，3，4的字符串，问怎么将他们拼接起来，使得最后得到的字符串，字典序最小。 思路： 出题人在题面里面刻意说了他卡了排序的做法，只允许线性的算法过。但最后用sort,再加了读入的优化就可以过了。 代码： #include<bits/stdc++.h> using namespace std; const int N=2e6; string s[N]; bool cmp(string a,string b){ return a+b<b+a; } int n; int main(){ ios::sync_with...

G Icon Design 思路： n为5的小模拟，我是按规律输出的。 代码： #include<bits/stdc++.h> using namespace std; int n; int main(){ scanf("%d",&n); for(int i=1;i<=13*n+19;i++) cout<<'*'; cout<<endl; for(int i=1;i<=n;i++){ cout<<'*'; for(int j=1;j<=13*n+17;j++) cout<<'.'; cout<<'...

2022牛客多校第七场  C Constructive Problems Never Die F Candies G Regular Expression  C Constructive Problems Never Die 题意： 给定一个长度为n的序列a，要找到一个序列p，满足p[i]!=a[i] (1<=i<=n) 思路： 先将没出现过a数组的元素存在vector里，若将a数组中没连在一起的数字每个向前移动，其他的都填上没出现的数字即可。 代码： #include <bits/stdc++.h> using namespace std; const int max...

F Longest Common Subsequence 题意： 给出初始x和a,b,c,p，通过x=(ax2ax^2ax2+bxbxbx+ccc)%p不断更新的x构成长度n+m的序列，前n个数为一个序列，后m个数为另一个序列，问这两个序列的最长公共子序列长度。 思路： 打表找规律后发现，序列中会出现一个之前出现的数字，说明出现了循环，两个序列一旦出现相同的数，后面的数就一定相同。 第一个序列将每一个数出现的第一个位置存unordered_map容器，map会超时。 第二个序列遍历每个数开始的最长公共子序列长度。 代码； #include<bits/stdc++.h> using ...

A Car Show 题意： 给定一个长度为n的数组，求包含1~n所有数的区间数量。 思路： 用一个set容器存里面区间的数，用双指针遍历每一个符合条件的区间，每有一个符合的区间，左指针右移；若区间不符合条件，则右指针右移。用哈希表存包含的数。注意开longlong 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+3; ll n,m; ll a[N],vis[N]; int main(){ scanf("%lld%lld",&n,&m); s...

M Maimai DX 2077 题意： 有五种得分，满分是最高分的累积和。给定每种音符的出现次数和的分情况，如果没有miss每对于一种特殊音符可以加额外分，请输出最终得分 / 满分的百分比。 思路： 根据题意模拟即可 代码： #include<bits/stdc++.h> using namespace std; long double a,b,c,d,e; long double an,bn,a0,b0; int main(){ for(int i=1;i<=4;i++){ scanf("%llf%llf%llf%llf%llf",&a,&b,&c...

H Wheel of Fortune 题意： 给定两个英雄的血量和双方七个随从的血量，此时尤格萨隆释放命运之轮，随机释放炎爆术直至一分死亡。求获胜的概率。 思路： 发现不管是敌方随从还是己方随从只能挡子弹，对游戏获胜没有影响。 这时只需要考虑英雄血量，获胜概率是由全砸对面脸的概率，到砸自己脸到10一下对面死亡的。对面需要被砸死，砸死次数bbb=⌈B10⌉\lceil \frac{B} {10}\rceil⌈10B​⌉,自己被砸死需要aaa=⌈A10⌉\lceil \frac{A} {10}\rceil⌈10A​⌉次，获胜的可能有砸b，b+1，···，b+a-1次，可以看作a被砸到的时候插到b次...

2022牛客多校第四场 N Particle Arts 题意： 有n个粒子携带焦耳能量，它们之间会发生随机碰撞。碰撞的两个粒子分别带a,b的焦耳能量，会湮灭并且产生两个新的粒子携带a&ba\&ba&b和a∣ba|ba∣b的能量，求粒子能量收敛时的方差。 思路： 我们可知a&b+a∣b=a+ba\&b+a|b=a+ba&b+a∣b=a+b,两个粒子碰撞可看作把二进制上的每一位上1和0分散到两个粒子。而达到收敛的情况则是把任意粒子碰撞能量不变，现在就是构造最终状态的粒子。统计每一位的1，然后然后按每一位有就加，重新组成n个粒子。 本题卡数据范围要用_...