F Sum of numerators(数论)
描述：
题目大意：
给出 n 和 k ，计算所给式子最简的所有分子和；
思路：
我们举一组例子：
n=10,k=2;
先不化简：
所有的分子是
1，2，3，4，5，6，7，8，9，10
分母是 4；
先求一次和；
这时对所有的偶数除 2(奇数对和无影响)
偶数变为
1，2，3，4，5
分母是 4/2=2 序列长度为10/2=5；
减去因为化简而多出的贡献
再对偶数化简一次(分母还是2的倍数)
偶数变为
1，2
分母是 2/2=1 序列长度为5/2=2；
减去因为化简而多出的贡献
这时虽然还有偶数，但是分母不为2的倍数，化到了最简；
从这个例子里我们就能找到规律，先求出不化简的总和，再根据 n 和 k的大小不断减去多算的贡献
代码：
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+100; const int p = 1e4; const double eps = 1e-8; ll n,k; ll t; int main() { cin>>t; while(t--) { cin>>n>>k; ll sum=(n+1)*n/2; while(n>1&&k>0) { n/=2; k--;//分母每次除2对应k减1 sum-=(n+1)*n/2; } cout<<sum<<endl; } return 0; }
L Monster Tower(模拟)
大意：
打怪，给出怪物塔的总层数 n 和能达到的层数 k
当打死一层的怪会获得怪的能力值，本层消失，本层上边的层数减一，求通关的最小能力值
思路：
打怪的顺序是唯一的，所以维护一个有 k 个元素的小根堆，每次处理最小的元素，如果现有能力值大于怪的能力值，加上怪的能力值，否则更新初始值；
每遇到一个打不过的怪，最小可能初始值 = 怪的能力值-前面获得的能力值总和，用这个值去更新之前的 初始值，取其中大的；
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+100; const int p = 1e4; const double eps = 1e-8; ll t,n,k; ll a[N]; priority_queue<ll,vector<int>,greater<int> >pmin; ll sta,now; int main() { cin>>t; while(t--) { cin>>n>>k; sta=0;now=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<=n;i++) { if(pmin.empty()||pmin.size()<k) pmin.push(a[i]);//注意判空 else { ll s=pmin.top(); pmin.pop(); if(now>=s) { now+=s; }//总能力值大于怪的能力值 else { sta=max(sta,s-now); now+=s; }//更新初始值，注意更新方式 pmin.push(a[i]); } } while(!pmin.empty()) { ll s=pmin.top(); pmin.pop(); if(now>=s) { now+=s; } else { sta=max(sta,s-now); now+=s; } } cout<<sta<<endl; } return 0; }
