结果：
我觉得是（OJ上也是）：
4 | Miemeng | 100 03:29:05 | 75 03:29:05 | 30 03:29:05 | 205 03:29:05 |
事实上……
| 23 | Miemeng | 100 | 0 | 30 | 130 |
好死了……为啥不开$\text{C++11}$
ZJ一下：
题不算难。
T1打表找规律成功！
T2码了一个$30$分暴力，后来为了要$20$分的特殊性质写了一个神奇$\text{C++11}$
然后就0了。
T3暴力还挺稳。
TJ时间：
T1
打表找到规律。
只想说一句话：爆龙龙就去化一波柿子。
化柿子的过程：
给的是这个：
$$\sum \limits_{i=0}^{p} \left \lfloor \frac{iq}{p} \right \rfloor$$
化下：
$$
\begin{array}{rl}
= & \sum \limits_{i=0}^{p} \frac{iq-iq\%p }{p} \\
= & \sum \limits_{i=0}^{p} iq-\sum \limits_{i=0}^{p} iq\%p \over p \\
= & \frac{pq(p+1)}{2} - \sum \limits_{i=0}^{p} iq\%p \over p
\end{array}
$$
但是有个$\sum$化不掉，此时就需要更加神奇的化柿子方法。
只考虑：
$$ \sum \limits_{i=0}^{p} iq\%p$$
设$r=gcd(p,q)$
于是可打表得:
$$
\begin{array}{rl}
& \sum \limits_{i=0}^{p} iq\%p\\
= & (p-r)\times(p/r)\times r \over 2\\
= & (p-r) \times p \over 2
\end{array}
$$
最后柿子长这样：
$$
\begin{array}{rl}
& \frac{pq(p+1)}{2} - \frac{p \times (p-r)}{2} \over p \\
= & \frac{q(p+1)- p+r}{2}
\end{array}
$$
如果不化简会爆龙龙……
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
using namespace std;
LL gcd(LL a,LL b){
return b==0?a:gcd(b,a%b);
}
int main(){
#ifndef LOCAL
freopen("simplecalc.in" ,"r",stdin);
freopen("simplecalc.out","w",stdout);
#endif
LL T,q,p;
cin>>T;
while(T--){
cin>>p>>q;
LL gcn=gcd(p,q);
cout<<((p+1)*q-(p-gcn))/2<<endl;
}
}
T2
分收益和损失两部分。
收益的我们要尽量花费少，所以按花费排序。
损失的我们可以按照X国的军队做，按损失量排序。（也可以按获取量排序，这样我们也可以保证答案更优。）
而且我们一定要先收益再损失。
写个厉害的比较函数……
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define N 1111111
using namespace std;
int check(LL a,LL b){
if(a*b<=0)return 0;
if(a<0 && b<0)
return 2;
if(a>0 && b>0)
return 1;
}
struct YB{
LL bef,aft;
friend bool operator < (const YB &a,const YB &b){
LL dela=a.aft-a.bef,
delb=b.aft-b.bef,
cek=check(dela,delb);
if(cek==0)
return dela>delb;
else if(cek==1)
return a.bef<b.bef;
else return a.aft>b.aft;
}
}bs[N];
LL bn;
int main(){
#ifndef LOCAL
freopen("reformat.in" ,"r",stdin);
freopen("reformat.out","w",stdout);
#endif
cin.sync_with_stdio(false);
cin>>bn;
for(int i=1;i<=bn;i++)
cin>>bs[i].bef>>bs[i].aft;
sort(bs+1,bs+bn+1);
// for(int i=1;i<=bn;i++)cout<<bs[i].bef<<" "<<bs[i].aft<<endl;
LL lft=0,ans=0;
for(int i=1;i<=bn;i++){
if(lft<bs[i].bef){
ans+=bs[i].bef-lft;
lft=bs[i].aft;
}
else{
lft-=bs[i].bef;
lft+=bs[i].aft;
}
}
cout<<ans<<endl;
}
T3
我太弱了。