2018.5.3 Test
得分：9+8+100=117
昨天刚看过T3。。
T1
离散化区间后好像很好想到(O(n^2))？调不出来算了。。
做不下去 先不改了
T2
也不想改。再说。。
T3 UOJ.206.[APIO2016]Gap(交互)
T=1 容易看出是每次要确定两个数。然后就是这样了。
T=2 调用函数覆盖的数尽量少。
一次n+1的调用可以找出所有数所在的区间，这个区间中有n-2个数把它分成n-1份。(我也不知道该怎么说了 反正就是这样)
所以 $ Ansgeq ceil((r-l)/(n-1)) $。(鸽巢原理)
以这个为区间大小查询，就可以确定出可能产生答案的A[]了。
#include "gap.h"
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long LL;
const int N=1e5+5;
const LL INF=1e18;
LL A[N<<1];
long long findGap(int T, int N)
{
LL l=0,r=INF,mn,mx;
int h=1,t=N;
if(T==1)
{
for(; h<=t; )
{
MinMax(l,r,&mn,&mx);
A[h++]=mn, A[t--]=mx;
l=mn+1, r=mx-1;
}
}
else
{
MinMax(l,r,&mn,&mx);
LL delta=ceil(1.0*(mx-mn+1)/(N-1)),Max=mx;
A[h++]=mn;
l=mn+1, r=mn+delta;
for(; l<r; l=r+1, r=std::min(r+delta,Max))
{
MinMax(l,r,&mn,&mx);
if(mn==-1) continue;
A[h++]=mn, A[h++]=mx;
}
A[h++]=Max, N=h-1;
}
long long res=0;
for(int i=1; i<N; ++i) res=std::max(res,A[i+1]-A[i]);
return res;
}
考试代码
T1
#include <map>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod (1000000007)
#define ADD(x,v) (x)+=(v),x>=mod?x-=mod:0
const int N=505;
int n,A[N],B[N],f[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace Spec1
{
int f[N];
void Solve()
{
f[0]=1;
for(int i=1; i<=n; ++i)
for(int j=0; j<i ;++j)
if(A[i]>A[j]) ADD(f[i],f[j]);
long long ans=0;
for(int i=1; i<=n; ++i) ans+=f[i];
// for(int i=1; i<=n; ++i) printf("%d:%d
",i,f[i]);
printf("%d",int(ans%mod));
}
}
namespace Spec2
{
// int f[2][1000005];
std::map<int,int> f[2];
void Solve()
{
int now=0,las=1;
f[las][0]=1;
long long ans=0,sum;
for(int i=1; i<=n; ++i)
{
sum=0;
for(int j=0; j<A[i]; ++j) sum+=f[las][j], f[now][j]=f[las][j];
sum%=mod;
for(int j=A[i]; j<=B[i]; ++j) f[now][j]=sum, ADD(sum,f[las][j]), ans+=f[now][j];
now^=1, las^=1;
}
printf("%d",int(ans%mod));
}
}
int main()
{
freopen("1.in","r",stdin);
n=read();
for(int i=1; i<=n; ++i) A[i]=read(),B[i]=read();
bool f=1;
for(int i=1; i<=n; ++i) if(A[i]!=B[i]) {f=0; break;}
if(f) {Spec1::Solve(); return 0;}
long long sum=0;
for(int i=1; i<=n; ++i) sum+=B[i]-A[i];
if(sum<=1000000) {Spec2::Solve(); return 0;}
return 0;
}
T2
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#define gc() getchar()
#define vt std::vector<N>
const int N=3e5+5,M=6e5+5;
int n,m,Enum,H[N],to[M],nxt[M],len[M];
long long Max,dep[N],f[N];
std::vector<int> v[N],tmp;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int u,int v,int w){
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
namespace Spec1
{
double Calc(double x)
{
double res=0;
for(int i=H[1]; i; i=nxt[i])
res+=fabs((double)len[i]-x);
return res;
}
void Solve()
{
std::sort(len+1,len+1+Enum);
printf("%lld",(long long)Calc(len[Enum>>1])); return;
double l=0,r=Max,lmid,rmid;
while(r>l+0.01)
{
lmid=l+(r-l)/3, rmid=r-(r-l)/3;
if(Calc(lmid)>Calc(rmid)) l=lmid;
else r=rmid;
}
printf("%lld",(long long)Calc((int)(l+0.5)));//long long!
}
}
void Get_dep(int x,int f,int d)
{
dep[x]=d;//this...
for(int i=H[x]; i; i=nxt[i])
if(to[i]!=f) Get_dep(to[i],x,d+len[i]);
}
void Merge(int i,int j)
{
tmp.clear();
int p1=0,l1=v[i].size(),p2=0,l2=v[j].size();
// printf("Merge(%d,%d):%d %d
",i,j,l1,l2);
while(p1<l1 && p2<l2)
if(v[i][p1]<=v[j][p2]) tmp.push_back(v[i][p1++]);
else tmp.push_back(v[j][p2++]);
while(p1<l1) tmp.push_back(v[i][p1++]);
while(p2<l2) tmp.push_back(v[j][p2++]);
v[i]=tmp;
}
void DFS(int x,int fa,int pur)
{
if(x>n) {f[x]=std::abs(dep[x]-pur), v[x].push_back(dep[x]-pur); return;}
long long sum=0;
for(int t,i=H[x]; i; i=nxt[i])
if((t=to[i])!=fa)
{
DFS(t,x,pur), sum+=f[t], Merge(x,t);
// printf("son:f[%d]:%lld sum:%lld
",t,f[t],sum);
}
long long val=v[x][v[x].size()-1>>1];
// printf("%d(%d,%d):
",x,p,v[x][p]);
// for(int i=0; i<v[x].size(); ++i) printf("%d ",v[x][i]);putchar('
');
f[x]=std::abs(val);
for(int i=0; i<v[x].size(); ++i) f[x]+=std::abs(val-v[x][i]);
// printf("f[%d]:%lld sum:%lld
",x,f[x],sum);
f[x]=std::min(f[x],sum);
}
double Calc(double x)
{
DFS(1,1,x);
return f[1];
}
void Spec()
{
long long res=1e16;
for(int i=0; i<=Max; ++i){
for(int j=1; j<=n+m; ++j) v[j].clear();
DFS(1,1,i),res=std::min(res,f[1]);
}
printf("%lld",res);
}
int main()
{
freopen("2.in","r",stdin);
n=read(),m=read();
for(int u,i=2; i<=n+m; ++i) u=read(),AddEdge(u,i,read());
Get_dep(1,1,0);
for(int i=1; i<=n+m; ++i) Max=std::max(Max,dep[i]);
if(n==1) {Spec1::Solve(); return 0;}
Spec(); return 0;
double l=0,r=Max,lmid,rmid;
while(r>l+0.01)
{
lmid=l+(r-l)/3, rmid=r-(r-l)/3;
printf("%.3lf,%.3lf->",l,r);
if(Calc(lmid)>Calc(rmid)) l=lmid;
else r=rmid;
printf("%.3lf %.3lf
",l,r);
}
printf("%d %lld
",(int)(l+0.5),Max);
printf("%lld",(long long)Calc((int)(l+0.5)));//long long!
return 0;
}