<!-- wp:heading {"level":1} -->
<h1>牛客编程巅峰赛S2第3场</h1>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>-> 青铜&白银&黄金
https://ac.nowcoder.com/acm/contest/9246
钻石&王者
https://ac.nowcoder.com/acm/contest/9247
2020-11-24 20:00:00 至 2020-11-24 21:00:00
时长: 1小时
AC 2/3
Rank 195/696
罚时 01:44:59
A (555/1916) 00:20:15 (-1)
B (205/1349) 00:59:44 (-4)
C (56/187)</p>
<!-- /wp:paragraph -->
<!-- wp:heading -->
<h2>A 牛牛打怪</h2>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>牛牛在各个平台被各种传奇游戏的广告轰炸，所以他决定去玩一玩这类的游戏。这类游戏挂机就可以升级，所以牛牛每天都能变强。在第i天里，牛牛能杀死防御力小于等于i的怪物。但由于牛牛还要刷题，所以牛牛每天最多杀一只怪物。这个游戏共有n只怪物，每只怪物的防御力为DEF[i]，牛牛想知道最少要到第几天才能把这n只怪物都杀死。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>A.1 比赛时AC</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型
* @param DEF int整型vector
* @return int整型
*/
int Minimumdays(int n, vector<int>& DEF) {
// write code here
sort(DEF.begin(),DEF.end());
for(int i=1;i<n;i++){
if(DEF[i]<=DEF[i-1]){
DEF[i]=DEF[i-1]+1;
}
}
return max(n,DEF[n-1]);
}
};<!-- /wp:code -->
<!-- wp:paragraph -->
<p>思路这样解释比较形象：
从小到大排列后，如果有相同数值的会形成一个平台。
而一天内最多只能打一个，
所以平台内的第二天需要增高一个台阶，
后面类似，小于等于前一个的数值将被更改为前一个的数值加一。
if(DEF[i]<=DEF[i-1]) DEF[i]=DEF[i-1]+1;</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>A.2 讲解</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型
* @param DEF int整型vector
* @return int整型
*/
int Minimumdays(int n, vector<int>& DEF) {
// write code here
sort(DEF.begin(),DEF.end());
int cnt=DEF[0],i;
for(i=1;i<DEF.size();i++){
cnt=max(DEF[i],cnt+1);
}
return cnt;
}
};<!-- /wp:code -->
<!-- wp:heading -->
<h2>B 简单的公式</h2>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>现在有3个数组a，b，c
a[1]=2,a[2]=6,对所有的n>=3,$latex a[n] = 2<em>a[n-1] + 3</em>a[n-2]$。
b[1]=7,b[2]=35,对所有的n>=3,$latex b[n] = 3<em>b[n-1] + 10</em>b[n-2]$。
对所有的n>=1,有c[n] = a[n]*b[n]。
现在给你一个正整数n,返回c[n]%1000000007的值。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>B.1 比赛时AC</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 返回c[n]%1000000007的值
* @param n long长整型 即题目中的n
* @return int整型
*/
int Answerforcn(long long n) {
// write code here
long long a=15,b=n-1,c=1000000007;
long long ans = 14,base=a;
base = base % c;
if(b==0){
return 14%c;
}
while(b){
if(b & 1)
ans = (ans*base) % c;
b = b >> 1;
base = (base * base) % c;
}
return ans%c;
}
};<!-- /wp:code -->
<!-- wp:paragraph -->
<p>其实这道题算作弊了。。
一开始没想到怎么算通项公式，
直接用特征方程来解的。</p>
<!-- /wp:paragraph -->
<!-- wp:quote -->
<p>$latex x_n=p\cdot x_{n-1}+q\cdot x_{n-2}\rightarrow x^2-px-q=0$<!-- /wp:quote --> <!-- wp:paragraph --> <p>后面算出$latex c_n=14\cdot 15^{n-1}$之后超时了一次。
解得 $latex x=a,b$
通项公式为$latex x_n=\alpha\cdot a^{n-1}+\beta\cdot b^{n-1}$
其中$latex \alpha,\beta$由初始条件$latex x_1,x_2$求得。
$latex \alpha=\frac{x_2-bx_1}{a-b},\beta=\frac{x_2-ax_1}{b-a}$</p>
然后莫名其妙觉得余数会循环(并不会循环)。浪费了很多时间
搜了下“幂取模”，搜到了模板 | 整数快速幂 & 快速幂取模,。</p> <!-- /wp:paragraph --> <!-- wp:code -->
// time：O(logN)
// 这里不考虑指数为负数的情况
int pow_mod(int a,int b,int c)
{
int ans = 1,base=a;// ans：结果；base：底数
base = base % c;
//【考虑0次方的情况】
if(b==0)
{
return 1%c;// 任意a的0次幂都是1,故直接用1%c即可
}
while(b)
{
if(b & 1) // 与运算，判断奇偶性
ans = (ans*base) % c;
b = b >> 1;// 右移一位，相当于除2
base = (base * base) % c;
}
return ans;
} <!-- /wp:code -->
<!-- wp:paragraph -->
<p>就直接套进来了，一开始还忘记改b=0的情况了，后来改成14，终于AC了，2020-11-24 20:59:44，还差16秒结束，终于赶上了一道。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>B.2 讲解</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 返回c[n]%1000000007的值
* @param n long长整型 即题目中的n
* @return int整型
*/
typedef long long ll;
int mod=1e9+7;
ll power(ll a,ll b){
ll res=1;
while(b){
if(b%2==1)res=res*a%mod;
b/=2;
a=a*a%mod;
}
return res;
}
int Answerforcn(long long n) {
// write code here
return 14*power(15,n-1)%mod;
}
};<!-- /wp:code -->
<!-- wp:heading -->
<h2>C Tree VI</h2>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>系统中有一棵n个点的完全k叉树，现给出它的DFS先序遍历序列$latex a_i$ ，请你还原这棵树，并返回加密后的答案。
答案加密方法：所有边两个端点异或的和，即$latex \sum\limits_{i=1}^{n-1}u_i\ xor\ v_i$ ，其中$latex (u_i, v_i)$为一条树上的边。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>下面给出完全二叉树的定义：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层所有的结点都连续集中在最左边。
请你根据这个定义进行适度推广，得到完全k叉树的含义。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>C.1 比赛时</h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>又没做到这一题，太惨了。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>C.2 讲解</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
*
* @param k int整型 表示完全k叉树的叉数k
* @param a int整型vector 表示这棵完全k叉树的Dfs遍历序列的结点编号
* @return long长整型
*/
typedef long long ll;
ll kk,nn,temp=1,res=0;
vector<int> aa;
void dfs(int x,int cnt){
int i;
for(i=1;i<=kk;i++){
if(kk*x+i<nn){
temp++;
res+=aa[temp-1]^aa[cnt-1];
dfs(kk*x+i,temp);
}
else return;
}
}
long long tree6(int k, vector<int>& a) {
// write code here
kk=k ,nn=a.size(),aa=a;
dfs(0,1);
return res;
}
};<!-- /wp:code -->
<!-- wp:paragraph -->
<p>引入BFS 辅助思考</p>
<!-- /wp:paragraph -->
<!-- wp:heading -->
<h2>D 整除问题</h2>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>给定 $latex a, b, c, d$，求所有 $latex x\times y$ 被 2021 整除的 $latex (x, y)$ 数对个数，其中 $latex a\le x\le b, c\le y\le d$ 。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>D.1 讲解</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 寻找所有能整除 2021 的数对个数
* @param a long长整型
* @param b long长整型
* @param c long长整型
* @param d long长整型
* @return long长整型
*/
long long f(long long a, long long b){
return a/2021b+b/2021a-a/2021(b/2021)+(a/43-a/2021)(b/47-b/2021)+(a/47-a/2021)*(b/43-b/2021);
}
long long findPairs(long long a, long long b, long long c, long long d) {
// write code here
return f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1);
}
};<!-- /wp:code -->
<!-- wp:paragraph -->
<p>容斥原理</p>
<!-- /wp:paragraph -->
