前言
- 又是深刻的教训啊。
- 评测竟然不开c++11……本来T3送分题写挂已经够惨了结果T2用lambda还CE了kuku。
- 昨天还因为没有挂分开心，原来……
- 不是不报，时候未到。
- 傻逼kx挂3个假对拍跟lsc一样没脸，早晚总榜超越lsc达到rank1。
T1
- 高考数学题，然而我不会……
- egin{array}{lcl}2sumlimits_{i=0}^p frac{iq}{p}=sumlimits_{i=0}^p frac{iq}{p}+sumlimits_{i=0}^p frac{(p-i)q}{p}=(p+1) imes q-sumlimits_{i=0}^p [(p|qi)?0:1]=(p+1) imes q-p+gcd(p,q)end{array}
- 时间复杂度$Theta(TlogN)$，空间复杂度$Theta(1)$。
#include<cstdio> #define ll long long int gcd(int x,int const y){ return y?gcd(y,x%y):x; } inline int read(){ int ss(0);char bb(getchar()); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } int main(){ freopen("simplecalc.in","r",stdin); freopen("simplecalc.out","w",stdout); int T=read(); while(T--){ int p=read(),q=read(); printf("%lld ",(1ll*p*q-p+q+gcd(p,q))>>1); } return 0; }
T2
- 正贡献按格式化之前的容量排序，负贡献的按格式化之后的容量排序。
- 其实已经可以直接得出答案了。但是还可以二分答案将$Theta(N)$的复杂度优化成$Theta(NlogN)$= =
#include<cstdio> #include<algorithm> #define ll long long using namespace std; ll const lar=1e18; inline int read(){ int ss(0);char bb(getchar()); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } int const N=1e6+5; int n,m; bool vis[N]; struct node{ int lt,gt; }a[N]; inline ll _min(ll x,ll y){ return x<y?x:y; } inline bool check(ll x){ for(register int i=1;i<=n;++i){ if(x<a[i].lt)return 0; x+=a[i].gt; } return 1; } inline bool cmp(node skyh,node yxs){ return skyh.gt<0?(yxs.gt<0?(skyh.gt+skyh.lt>yxs.gt+yxs.lt):0):(yxs.gt<0?1:skyh.lt<yxs.lt); } int main(){ freopen("reformat.in","r",stdin); freopen("reformat.out","w",stdout); n=read(); ll l=lar,r=0; for(register int i=1;i<=n;++i){ l=_min(l,a[i].lt=read()),r+=a[i].lt; a[i].gt=read()-a[i].lt; } sort(a+1,a+n+1,cmp); while(l<r){ ll mid=l+r>>1; if(check(mid))r=mid; else l=mid+1; } printf("%lld",l); return 0; }
T3
- 打对就是送分题。
#include<cstdio> #define ll long long using namespace std; inline int read(){ int ss(0),pp(0);char bb(getchar()); for(;bb<48||bb>57;bb=getchar())pp=bb=='-'; while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return pp?-ss:ss; } int const N=1e5+5; int T,n,m,tot,la,fs; int a[N],b[N],c[N],d[N]; int vis[N],tr[N],fk[N],q[N],now; int main(){ freopen("truth.in","r",stdin); freopen("truth.out","w",stdout); int T=read(); for(register int u=1;u<=T;++u){ n=read(),la=m=tot=now=fs=0; register char bb; for(register int i=1;i<=n;++i){ bb=getchar(); while(bb^'+'&&bb^'-'&&bb^'$')bb=getchar(); switch(bb){ case '+':a[i]=1;break; case '-':a[i]=0;break; case '$':a[i]=2,b[i]=read();la=i;break; } } if(!la){ for(register int i=1;i<=n;++i)la=la==a[i]; puts(la?"inconsistent":"consistent"); continue; } for(register int i=la+1;i<=n;++i)c[++m]=a[i],d[m]=b[i]; for(register int i=1;i<=la;++i)c[++m]=a[i],d[m]=b[i]; for(register int i=1,st,ct,hh[2];i<=n;++i){ ++tot,st=i; while(c[i]^2)++i; la=ct=hh[0]=hh[1]=0; for(register int j=st;j<i;++j) ct+=la,la=la==c[j]; hh[la]=ct+la; la=1,ct=0; for(register int j=st;j<i;++j) ct+=la,la=la==c[j]; hh[la]=ct+la; if(d[i]>=0 && d[i]<=n){ if(vis[d[i]]^u)q[++now]=d[i],vis[d[i]]=u; tr[d[i]]+=hh[1],fk[d[i]]+=hh[0]; } fs+=hh[0]; } if(vis[fs]!=u){puts("consistent");goto ac;} for(register int i=1;i<=now;++i) if(fs-fk[q[i]]+tr[q[i]]==q[i]){puts("consistent");goto ac;} puts("inconsistent"); ac:; for(register int i=1;i<=now;++i) tr[q[i]]=fk[q[i]]=0; } return 0; }