A题 奇偶数 题目链接
首先，看样例就知道：绝对不能暴力。
那怎么办？——二分呗！
二分应该都会，但如果代码这么写：
#include<bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
scanf("%d%d",&n,&k);
int l=1,r=n,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}
printf("%d\n",r);
return 0;
}恭喜你，大鸭蛋。
为什么？拿样例数据2(11 6)一试就知道了：3不符合，但4符合，这是什么鬼？难道二分不对？
遇事不能慌，先手算一下，设x=mid：
如果x为偶数，则该数字会在path(x)、path(x+1)、path(2x)、path(2x+1)、path(2x+2)、path(2x+3)、path(4x)、path(4x+1)……中出现
如果x为奇数，则该数字会在path(x)、path(2x)、path(2x+1)、path(4x)、path(4x+1)、path(4x+2)、path(4x+3)、path(8x)……中出现
发现什么了吗？
即便奇数比偶数小，也有可能是偶数符合，奇数不符合！
怎么解决？很简单，先判断一下mid+1即可，附程序：
#include<bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
scanf("%d%d",&n,&k);
int l=1,r=n,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(check(mid+1))
l=mid+1;
else
if(check(mid))
l=mid;
else
r=mid-1;
}
printf("%d\n",r);
return 0;
}程序主函数解决了，怎么写check？
这里提供两种做法：
1.深搜(dfs)/宽搜(bfs)
思路：从mid往上推，分两种情况：
1.如果mid是偶数，则mid+1和mid*2都有可能
2.如果mid是奇数，则只有mid*2有可能，因为mid+1是偶数，不会-1
问题：怎么存储求解出的数字？
排除重复数据，肯定会有人想到用桶，那么对不起，再友好的数据也会让桶炸掉，80分，这怎么办？
可以使用set，效率高，自带排除重复功能。
好了，思路清晰，写就是啦！（附宽搜代码）
bool check(int mid)
{
queue<int> q;
set<int> s;
q.push(mid);
s.insert(mid);
while(!q.empty())
{
if(s.size()>=k)
return true;
int l=q.front();
q.pop();
s.insert(l);
if(!(l&1)&&l+1<=n)
q.push(l+1);
if(l<<1<=n)
q.push(l<<1);
}
return s.size()>=k;
}特别注意！！！这个思路不是正解，只是数据友好，所以能AC（不过宽搜在小数据情况下可能比正解还快）
2.(我也说不清它叫啥)
思路：深搜宽搜都过不了10^9 10^9，那有没有方法可以呢？
有，还真有！
之前手算了经过mid的数字，这里再写一下：
x是偶数：path(x)、path(x+1)、path(2x)、path(2x+1)、path(2x+2)、path(2x+3)、path(4x)、path(4x+1)……
x是奇数：path(x)、path(2x)、path(2x+1)、path(4x)、path(4x+1)、path(4x+2)、path(4x+3)、path(8x)……
没发现规律？没事，化简一下：
x是偶数：path(x)-path(x+1)、path(2x)-path(2x+3)、path(4x)-path(4x+7)、path(8x)-path(8x+15)……
x是奇数：path(x)、path(2x)-path(2x+1)、path(4x)-path(4x+3)、path(8x)-path(8x+7)……
还没发现规律？没事，分成左端点和右端点来看：
x是偶数：左端点：path(x)、path(2x)、path(4x)、path(8x)、path(16x)……
右端点：path(x+1)、path(2x+3)、path(4x+7)、path(8x+15)、path(16x+31)……
x是奇数：左端点：path(x)、path(2x)、path(4x)、path(8x)、path(16x)……
右端点：path(x)、path(2x+1)、path(4x+3)、path(8x+7)、path(16x+15)……
发现规律了吧！！！
左端点：x、2x、2(2x)、2[2(2x)]……
右端点：偶数：x+1、2(x+1)+1、2[2(x+1)+1]+1……
奇数：x、2x+1、2(2x+1)+1、2[2(2x+1)+1]+1……
可以直接计算左端点(l)和右端点(r)，再把总数+=（r-l+1）即可。
代码实现：
bool check(int mid)
{
int l=mid,r,sum=0;
switch(l&1)
{
case 0:r=mid+1; break;
case 1:r=mid; break;
}
while(l<=n&&sum<k)
{
sum+=min(r,n)-l+1;
l<<=1;
r<<=1;
r++;
}
return sum>=k;
}最后，附正解的完整AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,k;
bool check(int mid)
{
int l=mid,r,sum=0;
switch(l&1)
{
case 0:r=mid+1; break;
case 1:r=mid; break;
}
while(l<=n&&sum<k)
{
sum+=min(r,n)-l+1;
l<<=1;
r<<=1;
r++;
}
return sum>=k;
}
int main()
{
scanf("%d%d",&n,&k);
int l=1,r=n,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(check(mid+1))
l=mid+1;
else
if(check(mid))
l=mid;
else
r=mid-1;
}
printf("%d\n",r);
return 0;
}B题 最强大脑 题目链接
先扯一句题外话：图片里的游戏叫祖玛。
这题超级简单，一边输入一边判断即可。
附AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k1,k2=0,sum=0,ans=0;
scanf("%d",&n);
while(n--)
{
scanf("%d",&k1);
if(k1==k2)
sum++;
else
{
if(ans<sum)
ans=sum;
sum=1;
}
k2=k1;
}
if(sum>ans)
ans=sum;
printf("%d\n",ans);
return 0;
}C题 三角形问题 题目链接
这题n是5000，不大，但是暴力枚举肯定是不行的，要优化。
怎么优化？——找规律。
看第一行，很容易就能找到规律，第n+1行的第一个数字为：
\begin{equation} \frac{n*(n-1)}{2}+1 \end{equation}
规律出来了，直接暴力枚举至要查询的数字或位置即可
注意事项：
1.公式算的是第n+1行，不是第n行！！！
2.搞清楚那条边是x，哪条边是y！！！(我就差点搞反了，见AC代码)
#include<bits/stdc++.h>
using namespace std;
void build1(int n)
{
int k,x,y;
for(k=0;k*(k+1)/2+1<=n;k++);
x=k;
k-=1;
k=k*(k+1)/2+1;
for(y=1;x>0;x--,y++)
{
if(n==k)
{
printf("%d %d\n",y,x); //此处差点搞反
return;
}
k++;
}
}
void build2(int x,int y)
{
y--;
int n=y*(y+1)/2+1,k;
y+=2;
for(k=1;k<x;k++)
{
n+=y;
y++;
}
printf("%d\n",n);
}
int main()
{
int t;
scanf("%d",&t);
if(t==1)
{
int n;
scanf("%d",&n);
build1(n);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
build2(x,y);
}
return 0;
}