目录
?Div.2,我竟然在50分钟内C题做掉了,想着B题做了基本上不会掉分了这把,B题要考什么我也清楚,以为给点时间就能拿下,万万没想到。。。
战况:
——————
我的B题有什么问题呢,我其实没看见题里面那个ai是大于等于0的!!
由题意的意思,就是2的ai次方,那么0就是2的零次方,即是1啦!!
1 2 4 8 16 32 64 128 256 512 1024
我怕溢出,所以算组合数时先除了分母。
然后自测了下发现了,8个里面选3个时算出来是55.9999,所以改用double。
然而数小时打印没问题,数大了,double打印就成了科学计数法了。。
然后我又用ceil函数向上取整吧(这道题int直接算不会溢出的)。
(组合数是算不出小数的。)
最终防溢出策略:
给你一些2的幂,只给指数,让你判断能组合多少个三角形。
1 2 4 8 16 32 64 128 256 512 1024
这些是2的幂,可以发现2+4 < 8,4 + 4 < 8 ,即前面的和不可能大于后面的,所以无法构成三角形。
这些很好想的。
所以只有两种情况:三同4 4 4 或者 两同带一小4 4 2 ,4 4 1
void solve()
{
int n; cin >> n;
vector<int>arr(n);
unordered_map<int, double>mmp;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
mmp[arr[i]]++;
}
vector<int>prev(n+1);
for (int i = 0; i <= n; i++)
{
if (i == 0)prev[i] = mmp[i];
else
prev[i] = prev[i - 1] + mmp[i];
}
double ans = 0;
for (auto x : mmp)
{
if (x.second >= 2)
{
//选两个
if(x.first>0)
ans += max(x.second / 2.0 * (x.second - 1) * prev[x.first-1] , (double)0.0);
//三个内部选
if (x.second >= 3)
{
ans += x.second / 6.0 * (x.second - 1) * (x.second - 2);
}
}
}
ll o = ceil(ans);
cout << o << endl;
}