题意:
题目讲的是普遍的足球赛的赛制。
第一阶段是淘汰赛,如果队伍数量是偶数,就每两队踢一局,输的淘汰,赢得留下;
第二阶段是循环赛,如果队伍数量是奇数,每一支队伍都要和其余的每一支队伍踢一局,输的淘汰,赢得留下;
最终,剩下的最后一支队伍获胜。
要求输入比赛场数N (1 ≤ N ≤ 1018),输出所需队伍数M;若求不出队伍数,则输出-1
。
分析:
根据两个阶段,可以推出场数和队伍数的方程:
因为(1 ≤ N ≤ 1018),所以(0<=k<=62)。这样,可以枚举k,二分m,最后所有符合条件的就是答案了。
注意,数据边界,小心溢出。
这题的测试数据很强,一共有123组,昨晚提交了30分钟才测完Accepted。
总结:
像这种给出方程,及其中一个未知数,要在符合条件的范围内求另一个未知数,就可以枚举再二分查找。已知上下界范围,先设好left和right的值,再二分。
AC代码:
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> using namespace std; typedef long long LL; LL a[100005]; LL c; void Solve(LL n) { LL k; for(k=0;k<63;k++){ LL l=1,r=3*1e9; if(k>=30) r=1000000000000000000>>k;//这里的判断很重要,如果不写,就会卡在test38. test38 Input:576460752303423487 Output:576460752023423488 while(l<=r){ LL mid=(l+r)>>1; LL ans=(((LL)1<<k)-1)*mid*2+mid*(mid-1); if(ans>2*n) r=mid-1; else if(ans<2*n) l=mid+1; else{ if(mid&1) a[c++]=mid*((LL)1<<k); break; } } } } int main() { LL n,i; while(cin>>n){ c=0; Solve(n); sort(a,a+c); if(c==0) puts("-1"); else{ for(i=0;i<c;i++) cout<<a[i]<<endl; } } return 0; }