标签：cal getc pre == 代码 bool break space ret
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份。(我也不知道该怎么说了 反正就是这样)
所以 $ Ans\geq ceil((r-l)/(n-1)) $。
以这个为区间大小查询，就可以确定出可能产生答案的A[]了。
#include "gap.h"
#include
#include
#include
typedef long long LL;
const int N=1e5+5;
const LL INF=1e18;
LL A[N1];
long long findGap(int T, int N)
{
LL l=0,r=INF,mn,mx;
int h=1,t=N;
if(T==1)
{
for(; h+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+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+1]-A[i]);
return res;
}
考试代码
T1
#include
#include
#include
#include
#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; ifor(int j=0; jif(A[i]>A[j]) ADD(f[i],f[j]);
long long ans=0;
for(int i=1; i// for(int i=1; i
printf("%d",int(ans%mod));
}
}
namespace Spec2
{
// int f[2][1000005];
std::mapint,int> f[2];
void Solve()
{
int now=0,las=1;
f[las][0]=1;
long long ans=0,sum;
for(int i=1; i0;
for(int j=0; jfor(int j=A[i]; j1, las^=1;
}
printf("%d",int(ans%mod));
}
}
int main()
{
freopen("1.in","r",stdin);
n=read();
for(int i=1; ibool f=1;
for(int i=1; iif(A[i]!=B[i]) {f=0; break;}
if(f) {Spec1::Solve(); return 0;}
long long sum=0;
for(int i=1; iif(sum1000000) {Spec2::Solve(); return 0;}
return 0;
}
T2
#include
#include
#include
#include
#include
#define gc() getchar()
#define vt std::vector
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::vectorint> 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\n",i,j,l1,l2);
while(p1if(v[i][p1]else tmp.push_back(v[j][p2++]);
while(p1while(p2void 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\n",t,f[t],sum);
}
long long val=v[x][v[x].size()-1>>1];
// printf("%d(%d,%d):\n",x,p,v[x][p]);
// for(int i=0; i
f[x]=std::abs(val);
for(int i=0; i// printf("f[%d]:%lld sum:%lld\n",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; ifor(int j=1; j1,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; i1,1,0);
for(int i=1; iif(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\n",l,r);
}
printf("%d %lld\n",(int)(l+0.5),Max);
printf("%lld",(long long)Calc((int)(l+0.5)));//long long!
return 0;
}
APIO2016
标签：cal getc pre == 代码 bool break space ret
原文地址：https://www.cnblogs.com/SovietPower/p/8986604.html