rank 19 mark 70
题纲：T1：接力比赛（DP优化（随机化+上界递增优化））；T2：树上竞技：计数类DP；T3：思维（暴力找max距离的优化：从最大距离的一遍反着找最近的距离点对）；T4：神仙图DP....
由于进度问题，我不想写博客了，具体的题目可以看：https://tg.hszxoj.com/contest/509
题解：
T1:
随机化，边界取不会T的最大
struct node
{
ll w, v;
}p[maxn], q[maxn];
int main()
{
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
n = read(); m = read();
for(int i=1; i<=n; i++)
{
p[i].w = read(); p[i].v = read();
s1 += p[i].w;
}
for(int i=1; i<=m; i++)
{
q[i].w = read(); q[i].v = read();
s2 += q[i].w;
}
W1 = min(s1, s2); W2 = max(s1, s2);
for(int i=1; i<=W2; i++)
{
dp1[i] = dp2[i] = -1e12;
}
//f1[0] = 1;
W = 3.5e5;
for(int i=1; i<=n; i++)
{
for(int j=W; j>=p[i].w; j--)
{
//printf("%d %lld\n", j, j-p[i].w);
//printf("hefa : %d %d\n", f1[j], f1[j-p[i].w]);
//f1[j] = f1[j] | f1[j-p[i].w];
//if(f1[j-p[i].w])
//{
dp1[j] = max(dp1[j], dp1[j-p[i].w]+p[i].v);
//printf("dp1[%d] = %lld\n", j, dp1[j]);
//}
}
}
//f2[0] = 1;
for(int i=1; i<=m; i++)
{
for(int j=W; j>=q[i].w; j--)
{
//printf("%d %lld\n", j, j-q[i].w);
//printf("hefa: %d %d\n", f2[j], f2[j-q[i].w]);
//f2[j] = f2[j] | f2[j-q[i].w];
//if(f2[j-q[i].w])
//{
dp2[j] = max(dp2[j], dp2[j-q[i].w]+q[i].v);
//printf("dp2[%d] = %lld\n", j, dp2[j]);
//}
}
}
for(int i=1; i<=W1; i++)
{
//if(f1[i] && f2[i])
//{
ans = max(ans, dp1[i]+dp2[i]);
//printf("dp1[%d] = %lld dp2 = %lld\n", i, dp1[i], dp2[i]);
//}
}
printf("%lld\n", ans);
return 0;
}
边界优化，sort一下效果更好
int n, m;
ll s1, s2, W, ans, dp1[N], dp2[N], W1, W2;
bool f1[N], f2[N];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct node
{
ll w, v;
bool operator < (const node &T) const
{
if(w == T.w) return v < T.v;
return w < T.w;
}
}p[maxn], q[maxn];
int main()
{
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
n = read(); m = read();
for(int i=1; i<=n; i++)
{
p[i].w = read(); p[i].v = read();
//s1 += p[i].w;
}
for(int i=1; i<=m; i++)
{
q[i].w = read(); q[i].v = read();
//s2 += q[i].w;
}
sort(p+1, p+1+n);
sort(q+1, q+1+m);
memset(dp1, -64, sizeof(dp1));
memset(dp2, -64, sizeof(dp2));
dp1[0] = dp2[0] = 0;
//W1 = min(s1, s2); W2 = max(s1, s2);
//for(int i=1; i<=W2; i++)
//{
//dp1[i] = dp2[i] = -1e12;
//}
//f1[0] = 1;
//W = 3.5e5;
for(int i=1; i<=n; i++)
{
s1 += p[i].w;
for(int j=s1; j>=p[i].w; j--)
{
//printf("%d %lld\n", j, j-p[i].w);
//printf("hefa : %d %d\n", f1[j], f1[j-p[i].w]);
//f1[j] = f1[j] | f1[j-p[i].w];
//if(f1[j-p[i].w])
//{
dp1[j] = max(dp1[j], dp1[j-p[i].w]+p[i].v);
//printf("dp1[%d] = %lld\n", j, dp1[j]);
//}
}
}
//f2[0] = 1;
for(int i=1; i<=m; i++)
{
s2 += q[i].w;
for(int j=s2; j>=q[i].w; j--)
{
//printf("%d %lld\n", j, j-q[i].w);
//printf("hefa: %d %d\n", f2[j], f2[j-q[i].w]);
//f2[j] = f2[j] | f2[j-q[i].w];
//if(f2[j-q[i].w])
//{
dp2[j] = max(dp2[j], dp2[j-q[i].w]+q[i].v);
//printf("dp2[%d] = %lld\n", j, dp2[j]);
//}
}
}
W = min(s1, s2);
for(int i=1; i<=W; i++)
{
//if(f1[i] && f2[i])
//{
ans = max(ans, dp1[i]+dp2[i]);
//printf("dp1[%d] = %lld dp2 = %lld\n", i, dp1[i], dp2[i]);
//}
}
printf("%lld\n", ans);
return 0;
}
T2:
暴力分：https://www.cnblogs.com/Catherine2006/p/16600202.html(from Catherine_leah)
T3:
细节（1）double开够（2）因为表针是一个环，所以pos=0-->=n,pos=n+1-->=0,if(h>=12)h-=12
int n;
double sz[50100],fz[50100];
inline double get_hour(double x,double y,double z){return x*30.0+y*0.5+z*0.5/60.0;}
inline double get_minu(double x,double y,double z){return y*6.0+z*0.1;}
inline double Dis(double x,double y)
{
if(x<y)swap(x,y);
return ((x-y)>180.0)?(360.0-x+y):(x-y);
}
char sre[10];
int main()
{
freopen("unreal.in","r",stdin);
freopen("unreal.out","w",stdout);
n=re();
_f(i,1,n)
{
double h=re(),m=re(),s=re();
if(h>=12)h-=12;
sz[i]=get_hour(h,m,s);
fz[i]=get_minu(h,m,s);
}
double myasn=1000000000.00;
sort(fz+1,fz+1+n);
sort(sz+1,sz+1+n);
for(double i=0;i<12;i+=1)
for(double j=0;j<60;j+=1)
for(double k=0;k<60;k+=0.01)
{
double t1=get_hour(i,j,k);
double t2=get_minu(i,j,k);
double ft1=(t1<180.0)?(t1+180.0):(t1-180.0);
double ft2=(t2<180.0)?(t2+180.0):(t2-180.0);
int p1=upper_bound(sz+1,sz+1+n,ft1)-sz;
int p2=upper_bound(fz+1,fz+1+n,ft2)-fz;
int pp1=p1-1;
int pp2=p2-1;
if(p1==n+1)p1=1;
if(p2==n+1)p2=1;//就是随便算一个？
if(pp1==0)pp1=n;
if(pp2==0)pp2=n;
//p1 and p1-1-->算和t的距离差
//p2 and p2-1
double ans1=Dis(t1,sz[p1]);
ans1=max(ans1,Dis(t1,sz[pp1]));
double ans2=Dis(t2,fz[p2]);
ans2=max(ans2,Dis(t2,fz[pp2]));
if(ans1>ans2)myasn=min(myasn,ans1);
else myasn=min(myasn,ans2);
}
chu("%lf",myasn);
return 0;
}