admin管理员组文章数量:1573663
本人未参与过ZJOI2013,前两场学校里的模拟赛用了day1day2试题,day2很开心地被初三神犇学弟虐了……
DAY1
T1 [BZOJ3110]K大数查询
直接树套树,或分治。
#include <cstdio>
#define N 50010
typedef long long ll;
int n,m,Ans[N],tt;
bool f[N];
char buf[1<<25],*p=buf;
struct stp{
int flg,l,r,g,b;
}A[N],B[N],C[N];
struct Bt{
ll d[2][N<<1][2];
inline ll qry(int g,int y){
ll res=0;
for(;y;y-=y&-y)
if(d[g][y][1]==tt) res+=d[g][y][0];
return res;
}
inline ll query(int l,int r){
ll t=(1+r)*qry(0,r)-qry(1,r),
p=l*qry(0,l-1)-qry(1,l-1);
return t-p;
}
inline void InserT(int g,int y,ll z){
for(;y<=(n<<1)+2;y+=y&-y){
if(d[g][y][1]==tt) d[g][y][0]+=z;
else d[g][y][1]=tt,d[g][y][0]=z;
}
}
inline void add(int l,int r){
InserT(0,l,1);InserT(0,r+1,-1);
InserT(1,l,l);InserT(1,r+1,-r-1);
}
}Bit;
inline void reaD(int &x){
char Ch=*p++;x=0;int f=1;
for(;Ch>'9'||Ch<'0';Ch=*p++)if(Ch=='-')f=-1;
for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=*p++);x*=f;
}
int w[20],wt;
inline void Pt(int x){
if(x==0){putchar('0');putchar('\n');return;}
if(x<0)putchar('-'),x=-x;
while(x)w[++wt]=x%10,x/=10;
for(;wt;wt--)putchar(w[wt]+'0');putchar('\n');
}
void S(int x,int y,int l,int r){
if(x>y) return;
if(l==r){
for(;x<=y;x++)if(A[x].flg==2) Ans[A[x].b]=l;
return ;
}tt++;
int mid=l+r>>1,t1=0,t2=0;ll w;
for(int i=x;i<=y;i++)
if(A[i].flg==1)
if(A[i].g<=mid) B[++t1]=A[i];
else Bit.add(A[i].l,A[i].r),C[++t2]=A[i];
else
if((w=Bit.query(A[i].l,A[i].r))<A[i].g) A[i].g-=w,B[++t1]=A[i];
else C[++t2]=A[i];
for(int i=1;i<=t1;i++) A[i]=B[i];
for(int i=1;i<=t2;i++) A[t1+i]=C[i];
S(1,t1,l,mid);
S(t1+1,t1+t2,mid+1,r);
}
int main(){
*(p+fread(buf,1,1<<25,stdin))=EOF;reaD(n);reaD(m);
for(int i=1;i<=m;i++){
reaD(A[i].flg),reaD(A[i].l),reaD(A[i].r),reaD(A[i].g);
A[i].b=i;
if(A[i].flg==1) A[i].g+=n+1;
else f[i]=1;
}
S(1,m,1,(n<<1)+2);
for(int i=1;i<=m;i++)
if(f[i]) Pt(Ans[i]-n-1);
return 0;
}
T2 [BZOJ3111]蚂蚁寻路
画出蚂蚁走过的多边形,不难发现可以把多边形分割成多个长宽不等的矩形,DP
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#define N 110
int n,m,k,A[N][N],pre[N][N],Ans=-(1<<30),f[N][N][30],g[N][N][30][2],p[N][N];
inline int max(const int &a,const int &b){return a<b?b:a;}
int main(){
scanf("%d%d%d",&n,&m,&k);k=k*2+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&A[i][j]),p[i][j]=p[i-1][j]+A[i][j];
for(int i=0;i<=m;i++)
for(int j=1;j<=n;j++)
for(int h=1;h<=k;h++) f[i][j][h]=g[i][j][h][0]=g[i][j][h][1]=-(1<<30);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
for(int w=1;w<=k;w++){
for(int h=i;h;h--)
f[j][h][w]=max(f[j-1][h][w],g[j-1][h][w-1][w&1])+p[i][j]-p[h-1][j];
g[j][1][w][0]=-(1<<30);
for(int h=2;h<=i;h++) g[j][h][w][0]=max(g[j][h-1][w][0],f[j][h-1][w]);
g[j][i][w][1]=-(1<<30);
for(int h=i-1;h;h--) g[j][h][w][1]=max(g[j][h+1][w][1],f[j][h+1][w]);
}
for(int h=i;h;h--)
Ans=max(Ans,f[j][h][k]);
}
return printf("%d\n",Ans),0;
}
T3 [BZOJ3112] 防守战线
设第i个单位放了xi个人,那么对于每个[l,r]的限制,满足∑xi,i∈[l,r]>=w,题目变成求最小的∑xi,
直接上单纯形
#include <cstdio>
#include <cmath>
#define N 1010
#define M 10010
#define inf (1<<30)
#define eps (1e-7)
int n,m;
double A[N][M],B[N],C[M],z,v;
inline void pivot(int l,int e){
B[l]/=A[l][e];
for(int i=1;i<=n;i++)if(i!=e) A[l][i]/=A[l][e];
A[l][e]=1/A[l][e];
for(int i=1;i<=m;i++)if(i!=l&&fabs(A[i][e])>eps){
B[i]-=B[l]*A[i][e];
for(int j=1;j<=n;j++)if(j!=e) A[i][j]-=A[l][j]*A[i][e];
A[i][e]=-A[i][e]*A[l][e];
}
v+=B[l]*C[e];
for(int i=1;i<=n;i++)
if(i!=e) C[i]-=A[l][i]*C[e];
C[e]=-C[e]*A[l][e];
}
inline long long Simplex(){
int l,e,i;
double tmp;
while(1){
for(i=1;i<=n;i++)
if(C[i]>eps)break;
if((e=i)==n+1) return (long long)(v+0.5);
tmp=inf;
for(i=1;i<=m;i++)
if(A[i][e]>eps&&tmp-B[i]/A[i][e]>eps) tmp=B[i]/A[i][e],l=i;
if(tmp==inf) return inf;
pivot(l,e);
}
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) scanf("%lf",&B[i]);
for(int i=1,x,y;i<=n;i++){
scanf("%d%d%lf",&x,&y,&z);
for(int j=x;j<=y;j++) A[j][i]=1;
C[i]=z;
}
return printf("%lld",Simplex()),0;
}
DAY2
T1 [BZOJ3213]抛硬币
吴大佬题解
讲下本蒟蒻的理解
令f(i)表示抛出1~i-1的序列的期望步数,p表示抛出H的概率,1-p表示抛出T的概率。
假设序列第i个为H
-有p的概率抛出H,对f(i+1)的贡献为p*1
-有(1-p)的概率抛出T,那么虽然第i位不匹配了,但可能序列的摸个前缀与之匹配(所以要KMP求出next数组),设
前缀1~k与之匹配,那么对f(i+1)的贡献为(1-p)(f(i+1)-f(k+1)+1)。
得到方程f(i+1)=f(i)+p+(1-p)(f(i+1)-f(k+1)+1)展开移项得f(i+1)=(f(i)-(1-p)f(k+1)+1)/p
DP一下,哦对还要打高精度。。。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#define N 1010
using namespace std;
typedef long long ll;
struct Int{
#define s 1000
#define w 1000000000
ll a[s];int size;
Int(){memset(a,0,sizeof(a));size=0;}
ll &operator [](ll x){return a[x];}
Int(int x){size=0;if(!x)size=1;else while(x)a[++size]=x%w,x/=w;}
friend Int operator *(Int a,Int b){
Int c;
for(int i=1;i<=a.size;i++)
for(int j=1;j<=b.size;j++)
c[i+j-1]+=a[i]*b[j],c[i+j]+=c[i+j-1]/w,c[i+j-1]%=w;
c.size=a.size+b.size-1;
for(;c[c.size+1];c.size++)c[c.size+2]=c[c.size+1]/w,c[c.size]%=w;return c;
}
friend Int operator +(Int a,Int b){
Int c;c.size=max(a.size,b.size);
for(int i=1;i<=c.size;i++) c[i]=a[i]+b[i];
for(int i=1;i<=c.size;i++) c[i+1]+=c[i]/w,c[i]%=w;
for(;c[c.size+1];c.size++) c[c.size+2]+=c[c.size+1]/w,c[c.size+1]%=w;return c;
}
friend Int operator /(Int a,int b){
Int c;ll k=0;c.size=a.size;
for(int i=a.size;i;i--)
c[i]=(a[i]+k*w)/b,k=(k*w+a[i])%b;
while(!c[c.size])c.size--;return c;
}
friend bool operator %(Int a,int b){
return a/b*Int(b)==a;
}
friend bool operator ==(Int a,Int b){
if(a.size!=b.size) return false;
for(int i=1;i<=a.size;i++)if(a[i]!=b[i])return false;
return true;
}
friend Int operator -(Int a,Int b){
Int c;c.size=max(a.size,b.size);
for(int i=1;i<=c.size;i++) c[i]=a[i]-b[i];
for(int i=1;i<=c.size;i++) while(c[i]<0)c[i+1]--,c[i]+=w;
while(!c[c.size]) c.size--;return c;
}
void print(){printf("%lld",a[size]);for(int i=size-1;i>0;i--)printf("%09lld",a[i]);}
};
struct frac{
Int x,y;
frac(){}
frac(int a,int b):x(a),y(b){}
frac(Int a,Int b):x(a),y(b){}
friend frac operator +(frac a,frac b){return frac(a.x*b.y+b.x*a.y,a.y*b.y);}
friend frac operator *(frac a,frac b){return frac(a.x*b.x,a.y*b.y);}
friend frac operator -(frac a,frac b){return frac(a.x*b.y-b.x*a.y,a.y*b.y);}
friend frac operator /(frac a,frac b){return frac(a.x*b.y,a.y*b.x);}
void splx(){
for(int i=2;i<=100;i++)
while(x%i&&y%i)x=x/i,y=y/i;
}
void print(){x.print();putchar('/');y.print();putchar('\n');}
};
int a,b,len,next[N],fail[N][2];
char A[N];
frac f[N],p[2];
int main(){
scanf("%d%d%s",&a,&b,A+1);
len=strlen(A+1);
next[1]=0;
for(int i=2,k=0;i<=len;i++){
while(A[i]!=A[k+1]&&k) k=next[k];
if(A[k+1]==A[i])k++;
next[i]=k;
}
p[1]=frac(a,b);p[0]=frac(b-a,b);
int t=A[1]=='H';fail[1][t]=2;fail[1][t^1]=1;
for(int i=2;i<=len;i++)
t=A[i]=='H',fail[i][t]=i+1,fail[i][t^1]=fail[next[i-1]+1][t^1];
f[1]=frac(0,1);
for(int i=1;i<=len;i++){
t=A[i]=='H';int k=fail[i][t^1];
(f[i+1]=((f[i]+frac(1,1)-p[t^1]*f[k])/p[t])).splx();
}
f[len+1].print();
return 0;
}
T2 [BZOJ3214]丽洁体
可以证明暴力求出A和C是最优的,那么对于中间那段求B,可以DP
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#define N 300010
#define pb push_back
using namespace std;
typedef long long ll;
map<ll,ll> flg;
vector<int> gp[N];
char rd[N];
int A[N],B[N],C[N],T[N];
ll now;
int f[N],g[N];
int lena,lenb,lenc,lent,Ans,cnt;
inline void Gets(int *a,int &len){
gets(rd+1);
int leng=strlen(rd+1);rd[leng]=' ';
now=0;
for(int i=1;i<=leng;i++){
if(rd[i]==' '){
a[++len]=flg[now]?flg[now]:flg[now]=++cnt;
now=0;
continue;
}
now=now*27+rd[i]-'a';
}
}
int main(){
Gets(T,lent);Gets(A,lena);
Gets(B,lenb);Gets(C,lenc);
int l,r,p=0;
for(l=1,p=1;p<=lena;l++)if(A[p]==T[l])p++;
for(r=lent,p=lenc;p;r--)if(C[p]==T[r+1])p--;r++;
for(int i=lenb;i;i--) gp[B[i]].pb(i);
Ans=l-lena+lent-r-lenc-1;
memset(f,0x7f,sizeof(f));memset(g,0x7f,sizeof(g));f[1]=0;
for(int i=l;i<=r;i++)
for(int j=0;j<gp[T[i]].size();j++){
int x=gp[T[i]][j];
if(x==1)g[x]=-i-1;
else if(g[x-1]+i<=f[x]) f[x]=g[x-1]+i,g[x]=f[x]-i-1;
}
printf("%d\n",Ans+f[lenb]);
return 0;
}
T3 [BZOJ3115]话旧
比BZOJ3116话旧2简单多了。。。。
两两点之前的方案数是非独立的,所以求出两两点之间的方案数相乘就好了。
因为题目说的极小值(注意是极小值)均为0,所以每条斜率为-1的直线一定会到x轴再变成斜率为1的直线。
如图所示为一组可行解,那么其他的解就是将相邻两个三角形合并的方案数。
令k为三角形个数,方案数为
2k−1
,仔细考虑下细节后DP一下。
#include <cstdio>
#include <algorithm>
#include <iostream>
#define N 1000010
#define p 19940417
using namespace std;
typedef long long ll;
int n,m;
int x[N],y[N],w[N],Ans=1,mx;
ll f[N][2];
inline void reaD(int &x){
char Ch=getchar();x=0;
for(;Ch>'9'||Ch<'0';Ch=getchar());
for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=getchar());
}
inline bool cmp(const int &a,const int &b){
return x[a]<x[b];
}
ll mit(int x){
ll res=1,a=2;
while(x){
if(x&1) res=res*a%p;
a=a*a%p;
x>>=1;
}
return res;
}
int main(){
reaD(n);reaD(m);
for(int i=1;i<=m;i++) reaD(x[i]),reaD(y[i]),w[i]=i;x[m+1]=n;w[m+1]=m+1;
sort(w+1,w+1+m,cmp);
f[0][0]=0;f[0][1]=1;
for(int i=1,X,Y;i<=m+1;i++){
X=x[w[i]]-x[w[i-1]];
Y=X-y[w[i]]-y[w[i-1]]>>1;
mx=max(mx,y[w[i-1]]+(x[w[i]]-x[w[i-1]]+y[w[i]]-y[w[i-1]]>>1));
if(x[w[i]]==x[w[i-1]]){f[i][0]=f[i-1][0];f[i][1]=f[i-1][1];continue;}
if(Y<=0){
if(y[w[i]]-y[w[i-1]]==x[w[i]]-x[w[i-1]]){
f[i][0]=f[i-1][0];
if(y[w[i-1]]==0)f[i][0]=f[i-1][1];
}
else if(y[w[i-1]]-y[w[i]]==x[w[i]]-x[w[i-1]])f[i][1]=f[i-1][1]+f[i-1][0];
else{
f[i][1]=f[i-1][0];
if(Y==0)f[i][0]=f[i-1][0]+f[i-1][1];
if(y[w[i-1]]==0)f[i][1]=f[i-1][1];
}
continue;
}
ll k=mit(Y-1);
if(y[w[i]]){
f[i][0]=f[i-1][1]*k%p;
if(y[w[i-1]])(f[i][0]+=f[i-1][0]*k*2%p)%=p;
}else f[i][0]=0;
f[i][1]=f[i-1][1]*k%p;
if(y[w[i-1]])(f[i][1]+=f[i-1][0]*k*2%p)%=p;
}
printf("%lld %d",f[m+1][0]+f[m+1][1],mx);
}
R:
做的时候蛮多算法都不会,感觉DAY2要稍微简单一点。
DAY1 T1 现场A了,但是T2没有时间想,因为刚开始就觉得不可做,T3建网络流的图到绝望。。。
DAY2是考完期末考后模拟赛的,本来就没什么心情,结果T1没想清楚,T2打挂,T3没看题。。
本文标签:
版权声明:本文标题:[BZOJ3110~3115]ZJOI2013 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1727747498a1127980.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论