某省选
胡雨菲让我做的，她自己已经AK了...
在loj(*oj？)上面搜索shoi2017即可。
洛谷上也有，搜六省联考就行
第一题:大水题枚举 P3745
看题目就很水:(其实是因为胡雨菲给我讲了做法)，我们分析可知:烦躁度只与最晚的出成绩日期有关。然后我们枚举出成绩日期，得出一个烦躁度。取min即可。注意C＝＝10^16时，我们判断得出把10^5个课程向前挪10^5次，每次产生10^5烦躁度，也才10^15，故只需输出solve(a[1])即可。随便搞两个前缀和，然后这题就A了。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = ; LL A,B,C,n,m,a[N],b[N],suma[N],sumb[N],sum2[N];
bool flag;///if(flag)舍弃A操作 LL solve(LL x)
{
//printf("x=%lld\n",x);
LL ans=;
LL p;
p=upper_bound(a+,a+n+,x)-a;
//printf("p=%lld\n",p);
ans+=(x*(p-)-suma[p-])*C;
//printf("ans+=%lld\n",ans);
p=upper_bound(b+,b+m+,x)-b;
//printf("p=%lld\n",p);
if(flag)
{
ans+=B*(sumb[m]-sumb[p-]-x*(m-p+));
}
else
{
LL l=x*(p-)-(sumb[p-]);
LL r=sumb[m]-sumb[p-]-x*(m-p+);
if(l>=r) ans+=A*r;
else
{
ans+=A*l;
r-=l;
ans+=r*B;
}
}
//printf("ans=%lld\n\n",ans);
return ans;
} int main()
{
scanf("%lld%lld%lld",&A,&B,&C);
scanf("%lld%lld",&n,&m);
for(LL i=;i<=n;i++) scanf("%lld",&a[i]);
for(LL i=;i<=m;i++) scanf("%lld",&b[i]);
sort(a+,a+n+);
sort(b+,b+m+);
for(LL i=;i<=n;i++) suma[i]=suma[i-]+a[i];
for(LL i=;i<=m;i++) sumb[i]=sumb[i-]+b[i];
for(LL i=m;i>=;i--) sum2[i]=sum2[i+]+b[i];
flag=bool(B<=A); if(C==)
{
printf("%lld",solve(a[]));
return ;
} LL ans=; for(LL i=;i<=a[n];i++)
{
ans=min(ans,solve(i));
}
printf("%lld",ans);
return ;
}
AC代码
这是我A的第一道紫题，但是我给的评级是黄题，水，太水了。
第二题:SB线段树 P3747
看得出来，明显是个线段树，但是就是不会写…...打个暴力15分水过。后来花了一整天的时间研究正解没研究出来...难度担当啊。
第三题:某组合数 P3746
胡雨菲博客里写的，不用化式子，直接看它的组合意义即可。As for me,打个基本的暴力，0分......凄惨。
第四题:拆图题 P3748
题意:把一个无根树删两条链，使联通块最多。算法标签上写着DP。我特判了5个点＋x＝＝2，44分，还行。
第⑤题:玩灯泡 P3750
太困难了，太困难了，我写n＝＝k的情况，贪心模拟，5分......
第⑥题:寿司 P3749
据说是困难的网络流题，我果然还是选择打暴力吧。暴力却也打不出来......特判了前两个点拿10分。
总计：100+44+15+10+5+0=174分 174分！