链接：http://211.140.156.254:2333/contest/64
我去掉了一百多分！
这次的题目怎么说呢，特别水，但是就是出现了一些很逗的错误导致炸裂。
最好笑的是SB的不只我一个：
hl666：T1没写负数读优，100炸成40
yu‘ao：T1写了判负数的但最后忘记乘上去了，100炸35
cjj：T2输出没写lld写d爆0了
zi’tai：作死写了clock导致爆0
ye‘ke’he：把T2的CODE交到T1去了，真的逗比，T1爆0
然后全部掉了一百多分
T1 水题不解释。
每次贪心让所有比他强的人互相摩擦，如果有多的挑一个比他弱的摩擦。
然后自己挑一个弱的摩擦，如果无法实现证明他GG了。
注意这里的弱指：能力值小于等于这个人（随机=获胜）
吐槽一下所有样例不开负数读优都能过（还是自己菜）
CODE
#include<cstdio>
using namespace std;
int n,t,x,h,l,i;
inline void read(int &x)
{
x=; char ch=getchar(); int flag=;
while (ch<''||ch>'') { if (ch=='-') flag=-; ch=getchar(); }
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
x*=flag;
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
read(n); read(t);
for (i=;i<n;++i)
{
read(x);
if (x<=t) ++l; else ++h;
}
for (i=;(<<i)<=n;++i)
{
if (l==）{ printf("%d",i); return ; }
h/=; l=(l-)/;
}
return ;
}
T2 一道贪心+DP的好题。
乍一看是个背包，由于数据很大不可能直接上模板，但有一个性质：体积只有1,2,3，而且当体积相同时取价值最大的一定更优
因此，考虑85分的暴力：预处理出所有的费用的前缀和。再枚举体积为3，为2的物品。大致是O(n^2)的。
所以这里可以用三分优化（不是二分，因为这是个单峰函数，并没有单调性）来选体积为2的物品，就可以A了
但这里还有另外一种做法，令f[i]表示当体积为i时，选择了多少体积为1的和体积为2的。
转移就很简单了（具体看代码）
然后我们再枚举3的个数，照样用前缀和即可，复杂度为O(m)，其实是更优异的一种算法
CODE
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=,M=;
struct dp
{
LL v;
int s1,s2;
}f[M];
int a[][N],num[],n,m,opt,x;
LL sum[N];
inline char tc()
{
static char fl[],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=; char ch=tc();
while (ch<''||ch>'') ch=tc();
while (ch>=''&&ch<='') x=x*+ch-'',ch=tc();
}
inline bool comp(int a,int b)
{
return a>b;
}
int main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
register int i;
read(n); read(m);
for (i=;i<=n;++i)
{
read(opt); read(x);
a[opt][++num[opt]]=x;
}
for (i=;i<=;++i)
sort(a[i]+,a[i]+num[i]+,comp);
for (i=;i<=num[];++i)
sum[i]=sum[i-]+a[][i];
for (i=;i<=m;++i)
{
f[i]=f[i-];
if (f[i].v<f[i-].v+a[][f[i-].s1+])
{
f[i].v=f[i-].v+a[][f[i-].s1+];
f[i].s1=f[i-].s1+;
f[i].s2=f[i-].s2;
}
if (i>=&&f[i].v<f[i-].v+a[][f[i-].s2+])
{
f[i].v=f[i-].v+a[][f[i-].s2+];
f[i].s1=f[i-].s1;
f[i].s2=f[i-].s2+;
}
}
LL ans=;
for (i=;i<=num[];++i)
{
if (i*>m) break;
ans=sum[i]+f[m-i*].v>ans?sum[i]+f[m-i*].v:ans;
}
printf("%lld",ans);
return ;
}
T3 难度很高，还是第一次打提交答案题。一道THUWC 2017的题目
你肯定是在逗我吧！（水王属性附体）
然后第一个点爆搜，其他全部乱写（至少每个点至少都有一到两分），最终水了27分。
接下来又到了看Solution的时间
好了，主要还是T1炸了，不然水个前5没什么问题