题意:给你一个字符串。每次取出第一个字符或最后一个字符,放到新的字符串(初始为空)后面。求最小字典序的新字符串。
比如样例:ACDBCB。按这样的顺序拿:头尾尾尾头尾。这样得到ABCBCD。可以证明没有比它字典序更小的了。
一开始我先YY了个很傻比的贪心。第一个字符和最后一个字符比较。取小的。然后O(n)扫一遍。(画外音:你煞笔啊、gold的题目就给你这么水掉啊!、、)本着这种态度很快就发现样例都过不了。先取出A、B。然后是取队头的C还是队尾的C呢。这时就发现光比较这一个字符的大小是不够的。要比较整个字符串和整个字符串反转过来的字符串的字典序大小,才能决定取哪个。
那么想到了什么呢?很明显就是后缀数组。
把这个字符串反转一遍接在原字符串后面,中间加一个分隔符(最好是小于'A'的,比如'@')。然后求出rank数组。
下标 0 1 2 3 4 5 6 7 8 9 10 11 12
字符 A C D B C B @ B C B D C A
那么维护两个指针,一个从0开始,一个从n+1(反转的字符串的起点)开始。比较rank的大小,每次取小的先输出。OK!
(fread、fwrite蛮好的、轻松rank3)
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; const int maxn=100000; int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],sa[maxn],str[maxn]; char s[maxn],buf[maxn],*p=buf,buf2[maxn],*o=buf2; inline bool cmp(int *r,int a,int b,int l){ return r[a]==r[b] && r[a+l]==r[b+l]; }inline void da(char *r,int *sa,int n,int m){ int i,j,p,*x=tmp1,*y=tmp2,*t; for(i=0;i<m;i++)cs[i]=0; for(i=0;i<n;i++)cs[x[i]=r[i]]++; for(i=1;i<m;i++)cs[i]+=cs[i-1]; for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i; for(j=1,p=1;p<n;j<<=1,m=p){ for(p=0,i=n-j;i<n;i++)y[p++]=i; for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j; for(i=0;i<n;i++)cv[i]=x[y[i]]; for(i=0;i<m;i++)cs[i]=0; for(i=0;i<n;i++)cs[cv[i]]++; for(i=1;i<m;i++)cs[i]+=cs[i-1]; for(i=n-1;i>=0;i--)sa[--cs[cv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; }for(i=0;i<n;i++)rank[sa[i]]=i; }int main(){ fread(p,1,maxn,stdin); int t=0,n=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')n=n*10+*p++-48; for(int i=1;i<=n;i++){ while(*p<'A'||*p>'Z')p++; s[t++]=*p++; }s[t++]='A'-1; for(int i=n-1;~i;i--) s[t++]=s[i]; s[t++]='\0'; da(s,sa,t,256); int j=0,k=n+1,c=0; for(int i=1;i<=n;i++)str[c++]=rank[j]>rank[k]?k++:j++; for(int i=0;i<n;i++){ if(i&&i%80==0)*o++='\n'; *o++=s[str[i]]; }fwrite(buf2,1,o-buf2,stdout); return 0; }
题意:修改区间内的数、询问区间内任意子段和的期望值。
然后我们尝试把每次的答案求出来。然后对这个式子乱搞。发现对于每个数a[i],维护a[i],i*a[i],i*i*a[i]就好了、
那么线段树维护就行了。好了没了。(其实是我懒得写题解了、、、
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ls (rt<<1) #define rs (rt<<1|1) #define mid (l+r>>1) #define lson l,mid,ls #define rson mid+1,r,rs #define root 1,n,1 typedef long long ll; const int maxn=500005; ll a[maxn]={0},b[maxn]={0},c[maxn]={0},add[maxn]={0}; char buf[5000000],*pt=buf,buf2[5000000],*o=buf2; inline ll getint(){ ll r=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++; if(*pt=='-')f=-1, pt++; while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48; return r*f; }inline char getop(){ while(*pt!='C'&&*pt!='Q')pt++; return *pt; }inline void print(ll x){ char str[30],*p=str; if(!x)*o++=48; else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;} }inline void pushup(ll rt){ a[rt]=a[ls]+a[rs], b[rt]=b[ls]+b[rs], c[rt]=c[ls]+c[rs]; }inline void pushdown(ll l,ll r,ll rt){ ll lc=mid-l+1, rc=r-mid, rr=mid, ll=mid+1; if(add[rt]){ add[ls]+=add[rt]; a[ls]+=lc*add[rt]; b[ls]+=(l+rr)*lc*add[rt]>>1; c[ls]+=(rr*(rr+1)*(rr<<1|1)-(l-1)*l*(l-1<<1|1))/6*add[rt]; add[rs]+=add[rt]; a[rs]+=rc*add[rt]; b[rs]+=(ll+r)*rc*add[rt]>>1; c[rs]+=(r*(r+1)*(r<<1|1)-(ll-1)*ll*(ll-1<<1|1))/6*add[rt]; add[rt]=0; } }void update(ll L,ll R,ll d,ll l,ll r,ll rt){ if(L<=l&&r<=R){ add[rt]+=d; a[rt]+=(r-l+1)*d; b[rt]+=(l+r)*(r-l+1)*d>>1; c[rt]+=(r*(r+1)*(r<<1|1)-(l-1)*l*(l-1<<1|1))/6*d; return; }pushdown(l,r,rt); if(L<=mid) update(L,R,d,lson); if(mid<R) update(L,R,d,rson); pushup(rt); }void query(ll L,ll R,ll&A,ll&B,ll&C,ll l,ll r,ll rt){ if(L<=l && r<=R){ A=a[rt],B=b[rt],C=c[rt]; return; }pushdown(l,r,rt); ll SA=0,SB=0,SC=0,TA,TB,TC; if(L<=mid) query(L,R,TA,TB,TC,lson), SA+=TA, SB+=TB, SC+=TC; if(mid<R) query(L,R,TA,TB,TC,rson), SA+=TA, SB+=TB, SC+=TC; A=SA,B=SB,C=SC; }inline ll gcd(ll a,ll b){ return (!b)?a:gcd(b,a%b); }int main(){ fread(pt,1,5000000,stdin); ll n,q,u,v,w,TA,TB,TC,A,B,C; for(n=getint(),q=getint();q;q--){ if(getop()=='C'){ u=getint(),v=getint(),w=getint(); update(u,v-1,w,root); }else{ u=getint(),v=getint(); query(u,v-1,TA,TB,TC,root); A=(u+v-1)*TB+TA*(v-v*u)-TC; B=(v-u+1)*(v-u)>>1; C=gcd(A,B); print(A/C);*o++='/';print(B/C);*o++='\n'; } }fwrite(buf2,1,o-buf2,stdout);return 0; }
原来省选题也有裸背包啊、、
if (F[i-1][j]) then F[i][j+c[i]]=F[i][j-c[i]]=1
好了水掉了
#include<cstdio> int f[52][1005]={0},n,st,ed,c[52]; int main(){ scanf("%d%d%d",&n,&st,&ed); for(int i=1;i<=n;i++)scanf("%d",&c[i]); f[0][st]=1; for(int i=1;i<=n;i++) for(int j=0;j<=ed;j++){ if(!f[i-1][j]) continue; if(j+c[i]<=ed) f[i][j+c[i]]=1; if(j-c[i]>=0) f[i][j-c[i]]=1; }int An; for(An=ed;~An;An--) if(f[n][An]) break; printf("%d\n",An); }
自己YY出来了?估计应该是比较简单的网络流入门题吧。。
既然每个点(i,j)最多只能通过c[i][j]个蜥蜴。那么很自然地想到拆点。(i,j)→(i,j)'连上容量为c[i][j]的边。(i,j)为入点。(i,j)'为出点。
对于所有有蜥蜴的点,从S给它连一条容量为1的边。对于所有可以跳到外面的点,连到T,容量是c[i][j]。
然后n^4枚举在内部跳来跳去的情况。最后跑网络流就好了。
连T的边的时候我一直在傻×、、一开始算的是到(0,0)的距离≤d、、果然还是太弱了哎、、
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000,maxm=500000,inf=1000000009; int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn],id[25][25]; int S,T,n,m,k,tot=0,cnt=0,N=0; char s[25]; inline void ae(int x,int y,int z){ p[tot]=y; c[tot]=z; n1[tot]=h[x]; h[x]=tot++; p[tot]=x; c[tot]=0; n1[tot]=h[y]; h[y]=tot++; }inline int bfs(){ memset(d,0xff,sizeof(d)); int r=d[q[0]=S]=0; for(int l=0;l<=r;l++) for(int k=h[q[l]];~k;k=n1[k]) if(c[k] && !~d[p[k]]) d[q[++r]=p[k]]=d[q[l]]+1; return ~d[T]; }int dfs(int x=S,int lmt=inf){ if(x==T) return lmt; int flow; for(int &k=g[x];~k;k=n1[k]){ if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){ c[k]-=flow; c[k^1]+=flow; return flow; } }return 0; }int main(){ scanf("%d%d%d",&n,&m,&k); k; S=0; T=801; memset(h,0xff,sizeof(h)); for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++) if(s[j]-'0'){ id[i][j]=++cnt; ae((id[i][j]<<1)-1,id[i][j]<<1,s[j]-'0'); if(min(min(i,n-i+1),min(j,m-j+1))<=k)ae(id[i][j]<<1,T,s[j]-'0'); }for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int ii=1;ii<=n;ii++) for(int jj=1;jj<=m;jj++){ if(!id[i][j]||!id[ii][jj]) continue; if((ii-i)*(ii-i)+(jj-j)*(jj-j)<=k*k) ae(id[i][j]<<1,(id[ii][jj]<<1)-1,inf); }for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++) if(s[j]=='L'){ N++; if(id[i][j]) ae(S,(id[i][j]<<1)-1,1); }int An=0,f=0; while(bfs()){ memcpy(g,h,sizeof(h)); while(f=dfs()) An+=f;} printf("%d\n",N-An); return 0; }
【吐槽:我不想保护出题人。。。】
首先把读入的a数组变成前缀和。然后就可以发现y数组其实就是这个东西这就是确保杀死j~i(j≤i)这一段僵尸的最小速度。伤害的和是a[i]-a[j-1],第j个~第i个之间的距离是di-dj,还要加上x[i]才是与家的距离。很绕吗?自己脑补吧。。
观察这个式子比较像求直线的斜率。那么我们把它转化为两点之间的斜率好了。把跟i有关的看成一个点,跟j有关的看成一个点。
那么就是(x[i]+d*i,a[i])和(d*j,a[j-1])两个点。然后只要求斜率了!!!
那么用单调栈维护一个凸壳就好了!!!计算斜率的时候二分。二分的时候先判是不是在凸壳的外部,然后取栈里面最上面那个就好了。
很好。nlogn了。
这是样例,有线连着的点是转化过的(d*j,a[j-1])。其中虚线是最后形成的凸壳。
查询第i次的时候就是先转化为(x[i]+d*i,a[i])这个点,然后二分凸壳上的点求最大的斜率就好。
比如查询第一次。凸壳(黄线)中只有(2,0)这个点。要查询的是(5,3)。很明显斜率只能是1。
查询第二次。查询的点是(5,4)。凸壳中有两个点(2,0),(4,3)。选前者的算出的斜率1.3333比后者的1要优。
然后以此类推就可以解决全部询问。
这道题在八中上rank1了我会告诉你们?介于是rank1我就不发rank1的代码了、、这个是目前rank10的、、
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef double D; D a[100005],x[100005],d,An=0; struct P{D x,y;P(){};P(D _x,D _y):x(_x),y(_y){};}p[100005]; D cross(P a,P b,P c){ return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);} int st[100005],top=0,n; int main(){ scanf("%d%lf",&n,&d); for(int i=1;i<=n;i++){ scanf("%lf%lf",&a[i],&x[i]); a[i]+=(p[i].y=a[i-1]); p[i].x=i*d; }for(int i=1;i<=n;i++){ while(top&&cross(p[st[top]],p[i],p[st[top-1]])<0)top--; st[++top]=i; P s(x[i]+i*d,a[i]); int j=1,l=1,r=top,mid; while(l<=r){ mid=l+r>>1; if(cross(p[st[mid]],p[st[mid-1]],s)<0)j=max(j,mid),l=mid+1;else r=mid-1; }An+=(s.y-p[st[j]].y)/(s.x-p[st[j]].x); }printf("%.0lf\n",An); return 0; }
第一问先求1到n的最短路。第二问求破坏一些路使得1到n的最短路变大。每条路被破坏都要花费一定的代价Ci。求min∑Ci。
我学会了写spfa好开心啊!我学会了写dinic好开心啊!==
破坏边使不连通明显最小割水掉嘛、、
好了言归正传、先求出所有的最短路。然后判断每条边是不是在1~n的最短路上。是的话就连边。然后再新建的图上做最小割。
一开始建图建错了、、应该这么建:首先以1为源点跑spfa,记录d[0][i]为1~i的最短路。然后以n为源点跑spfa,记录d[1][i]为n~i的最短路。
如果i在1~n的最短路上那一定满足d[0][i]+d[1][i]==d[0][n](这也是第一问的答案、、)且d[0][i]+w(i,j)=d[0][j]。
然后就没了、、继续fread然后刷到rank5、、、
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxm=250000,maxn=505,inf=2000000009; struct edge{int t,c,next;}E[maxm]; char buf[3000000],*pt=buf; int p[maxm],w[maxm],c[maxm],n1[maxm],h[maxn],v[maxn],d[2][maxn],q[maxm],V[maxn],level[maxn],n,m,tot=0,tt=0,S,T,An=inf; inline int getint(){ int r=0; while(*pt<'0'||*pt>'9')pt++; while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r; }inline void ae1(int u,int v,int t,int cc){ p[tot]=v; w[tot]=t; c[tot]=cc; n1[tot]=h[u]; h[u]=tot++; p[tot]=u; w[tot]=t; c[tot]=cc; n1[tot]=h[v]; h[v]=tot++; }inline void ae2(int a,int b,int c){ E[tt].t=b; E[tt].c=c; E[tt].next=V[a]; V[a]=tt++; E[tt].t=a; E[tt].c=0; E[tt].next=V[b]; V[b]=tt++; }inline int bfs(){ memset(level,0xff,sizeof(level)); int head=0,tail=1; q[0]=S; level[S]=1; while(head<tail){ int u=q[head++]; if(u==T)return 1; for(int p=V[u];p!=-1;p=E[p].next) if(E[p].c>0 && level[E[p].t]==-1) level[E[p].t]=level[u]+1,q[tail++]=E[p].t; }return 0; }int dfs(int u=S,int lmt=inf){ if(u==T) return lmt; int ret=0, delta; for(int p=V[u];p!=-1;p=E[p].next){ if(E[p].c>0 && level[E[p].t]==level[u]+1){ delta=dfs(E[p].t,min(lmt-ret,E[p].c)); E[p].c-=delta; E[p^1].c+=delta; ret+=delta; if(ret==lmt) return ret; } }if(!ret) level[u]=-1; return ret; }inline int dinic(){ int ret=0;S=1,T=n; for(int i=1;i<=n;i++)for(int j=h[i];~j;j=n1[j]) if(d[0][p[j]]+d[1][p[j]]==An && d[0][i]+w[j]==d[0][p[j]]) ae2(i,p[j],c[j]); while(bfs())ret+=dfs(); return ret; }inline void spfa(int SS,int f){ for(int i=1;i<=n;i++)d[f][i]=inf; memset(v,0,sizeof(v)); int head=0,tail=1; q[0]=SS; v[SS]=1; d[f][SS]=0; while(head<tail){ int u=q[head++]; v[u]=0; for(int i=h[u];~i;i=n1[i]) if(d[f][u]+w[i]<d[f][p[i]]){ d[f][p[i]]=d[f][u]+w[i]; if(!v[p[i]]) v[p[i]]=1, q[tail++]=p[i]; } } }int main(){ fread(pt,1,3000000,stdin); n=getint(),m=getint(); memset(h,-1,sizeof(h)); memset(V,-1,sizeof(V)); for(int u,v,t,c,i=1;i<=m;u=getint(),v=getint(),t=getint(),c=getint(),ae1(u,v,t,c),i++); spfa(1,0); spfa(n,1); for(int i=1;i<=n;i++) An=min(An,d[0][i]+d[1][i]); printf("%d\n%d\n",An,dinic()); return 0; }
果然是3越多越好、、滚回去学小学奥数算了、、、
然后就是高精度了、、比较脑残选择了手写、、更加脑残的选择了压位和快速幂、、然后跑的还行、、
代码越写越短了、、不过还有更短的比不过、、呵呵、、、
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; struct Hugeint{ ll len,num[10000]; Hugeint(){ len=1ll; memset(num,0,sizeof(num));} }An;ll n,two,thr,p[]={1,10,100,1000}; Hugeint Mul(Hugeint a,Hugeint b){ Hugeint c; c.len=a.len+b.len+1; for(ll i=1;i<=a.len;i++) for(ll j=1;j<=b.len;j++) c.num[i+j-1]+=a.num[i]*b.num[j]; for(ll i=1;i<c.len;i++) if(c.num[i]>9999) c.num[i+1]+=c.num[i]/10000, c.num[i]%=10000; while(c.num[c.len]>9999) c.len++, c.num[c.len]+=c.num[c.len-1]/10000, c.num[c.len-1]%=10000; while(c.num[c.len]==0&&c.len>1) c.len--; return c; }Hugeint pow(ll b,ll p){ Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll; bb.num[1]=b; while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);} return ans; }inline int len(int x){ int r=0; while(x)r++,x/=10; return r; }void print(Hugeint a){ if(a.len<=25){ printf("%lld",a.num[a.len]); for(ll i=a.len-1;i;i--)printf("%04lld",a.num[i]); return;} printf("%lld",a.num[a.len]); for(ll i=a.len-1;i>=a.len-24;i--)printf("%04lld",a.num[i]); if(len(a.num[a.len])<4) printf("%lld\n",a.num[a.len-25]/p[len(a.num[a.len])]); }int main(){ scanf("%lld",&n); two=0,thr=n/3; if(n%3)two=2/(n%3),thr=(n-4/(n%3))/3; An=Mul(pow(2,two),pow(3,thr)); printf("%lld\n",(An.len-1<<2)+len(An.num[An.len])); print(An); return 0; }
排序、然后在上下3个中选、dp就好
然后我顺便学了写fread、真好、又快又实用又好写
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const ll inf=10000000000009LL; #define abs(x) (((x)<0)?(-(x)):(x)) #define A(x,y) ((x==y)?inf:abs((x)-(y))) ll n,a[100005],b[100005],f[100005]; char buf[2000000],*p=buf; inline int getint(){ ll r=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')r=r*10+*p++-48;return r; }int main(){ fread(p,1,2000000,stdin); n=getint(); for(ll i=1;i<=n;i++)a[i]=getint(),b[i]=getint(); sort(a+1,a+n+1); sort(b+1,b+n+1); f[1]=A(a[1],b[1]); f[2]=min(f[1]+A(a[2],b[2]),A(a[1],b[2])+A(a[2],b[1])); for(ll i=3;i<=n;i++)f[i]=min(f[i-1]+A(a[i],b[i]),min(f[i-2]+A(a[i-1],b[i])+A(a[i],b[i-1]),min(f[i-3]+A(a[i],b[i-1])+A(a[i-1],b[i-2])+A(a[i-2],b[i]),f[i-3]+A(a[i],b[i-2])+A(a[i-1],b[i])+A(a[i-2],b[i-1])))); printf("%lld\n",f[n]==inf?-1LL:f[n]); return 0; }
类似记忆化dp、、
f[i][j]表示i~j这一段最少要涂几次。每次递归计算、头尾如果相同可以最先涂、所以可以减1、然后合并上来就行、、
最近写的代码怎么都这么短?还是我太弱了只会刷水?唉、、囧、、、
#include<cstdio> #include<algorithm> #include<cstring> const int inf=1000000009; int F[60][60]={0},l; char s[60]; int f(int l,int r){ if(l==r) return 1; if(F[l][r]) return F[l][r]; F[l][r]=inf; for(int i=l;i<=r;i++) F[l][r]=std::min(f(l,r),f(l,i)+f(i+1,r)); return F[l][r]-=(s[l]==s[r]); }int main(){ scanf("%s",s); l=strlen(s); printf("%d\n",f(0,l-1)); return 0; }
弱弱的dp我也会做!哈哈哈
设f[i][j]表示高度为i时,在第j个树上能吃到的果子数的最大值。m[i]表示高度为i时吃到的果子数的最大值。w[i][j]表示高度为i,第j颗树上的果子树。
那么方程显而易见:f[i][j]=max(f[i+1][j],m[i+d])+w[i][j]。
读入文件好像奇大、好可怕、话说一开始MLE了、、囧不得不开short、、
orz读入优化、瞬间提升5s、
#include<cstdio> #define max(a,b) (((a)<(b))?(b):(a)) int n,h,d,k,t,i,j,f[5005][5005]={0},m[5005]={0}; short a[5005][5005]={0}; inline void read(int &x){ char ch; for(ch=getchar();ch<'0'||ch>'9';ch=getchar()); x=ch-'0'; for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0'; }int main(){ for(read(n),read(h),read(d),i=1;i<=n;i++)for(read(t),j=1;j<=t;j++)read(k),a[i][k]++; for(i=h;~i;i--){ if(i+d<=h) t=m[i+d]; else t=0; for(j=1;j<=n;j++) f[i][j]=max(f[i+1][j],t)+a[j][i], m[i]=max(m[i],f[i][j]); }printf("%d",m[0]); return 0; }