非常的菜 被初中踩成了弱智
T1 game
题目大意：
n轮游戏 在第$i$轮已经获胜$j$轮继续获胜的概率为 p i j
每一轮可以选择放弃（即100%失败）
求最优策略下 获胜场数的期望
思路：
可以发现并不需要放弃
直接dp即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #define inf 2139062143 11 #define ll long long 12 #define MAXN 1100 13 using namespace std; 14 inline int read() 15 { 16 int x=0,f=1;char ch=getchar(); 17 while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();} 18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 19 return x*f; 20 } 21 //yyc score=0 22 int n; 23 double a[MAXN][MAXN],dp[MAXN][MAXN],ans; 24 int main() 25 { 26 freopen("game.in","r",stdin); 27 freopen("game.out","w",stdout); 28 n=read(); 29 for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) scanf("%lf",&a[i][j]); 30 dp[1][1]=1.0; 31 for(int i=2;i<=n+1;i++) for(int j=1;j<=i;j++) 32 dp[i][j]=dp[i-1][j]*(1.0-a[i-1][j])+dp[i-1][j-1]*a[i-1][j-1]; 33 for(int i=1;i<=n+1;i++) ans+=(i-1)*dp[n+1][i]; 34 printf("%.2lf",ans); 35 }
T2 cake
题目大意：
n个物品 每个物品体积即背包$\le 10^9$ 求背包内最大体积
思路：
本来是一个折半搜索裸题
1 #include<bits/stdc++.h> 2 #define LL long long 3 #define M 1200020 4 using namespace std; 5 namespace IO{ 6 const int BS=(1<<20)+5; int Top=0; 7 char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1; 8 char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;} 9 void flush(){fwrite(OT,1,OS-OT,stdout);} 10 void Putchar(char c){*OS++ =c;if(OS==fin)flush(),OS=OT;} 11 void write(int x){ 12 if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-'); 13 while(x) SS[++Top]=x%10,x/=10; 14 while(Top) Putchar(SS[Top]+'0'),--Top; 15 } 16 int read(){ 17 int nm=0,fh=1; char cw=getchar(); 18 for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh; 19 for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); 20 return nm*fh; 21 } 22 }using namespace IO; 23 int n,m,val[50][2],p[2][M],maxn,tp[2],sz[2],ans; 24 void dfs(int pos,int now,int kd){ 25 if(now>m) return; 26 if(pos==tp[kd]+1){p[kd][++sz[kd]]=now;return;} 27 dfs(pos+1,now,kd),dfs(pos+1,now+val[pos][kd],kd); 28 } 29 int main(){ 30 freopen("cake.in","r",stdin); 31 freopen("cake.out","w",stdout); 32 n=read(),m=read(),ans=m; 33 for(int i=1;i<=n;i++) val[++tp[i&1]][i&1]=read(); 34 dfs(1,0,0),sort(p[0]+1,p[0]+sz[0]+1); 35 dfs(1,0,1),sort(p[1]+1,p[1]+sz[1]+1); 36 for(int i=0,j=sz[1];i<=sz[0];i++){ 37 while(j>0&&p[0][i]+p[1][j]>m) j--; 38 ans=min(ans,m-p[0][i]-p[1][j]); 39 }printf("%d\n",ans);return 0; 40 }
但是我非常菜的直接dfs剪枝得了90分
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #define inf 2139062143 11 #define ll long long 12 #define MAXN 50 13 #define MOD 1000000007 14 using namespace std; 15 inline int read() 16 { 17 int x=0,f=1;char ch=getchar(); 18 while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();} 19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 //yyc score=0 23 int n,m,a[MAXN],ans=inf,s[MAXN]; 24 map <int,bool> vis; 25 void dfs(int x,int sum) 26 { 27 //cout<<x<<" "<<sum+a[x]<<endl; 28 if(sum+a[x]>m||vis[sum+a[x]]) return ;vis[sum+a[x]]=1,ans=min(ans,m-sum-a[x]); 29 if(x==1) {ans=min(ans,m-sum-a[x]);return ;} 30 if(sum+s[1]-s[x+1]<=m) {ans=min(ans,m-sum-s[1]+s[x+1]);return ;} 31 for(int i=x-1;i;i--) 32 if(sum+a[x]+a[i]<=m) dfs(i,sum+a[x]); 33 } 34 int main() 35 { 36 freopen("cake.in","r",stdin); 37 freopen("cake.out","w",stdout); 38 n=read(),m=read(); 39 for(int i=1;i<=n;i++) a[i]=read(); 40 sort(a+1,a+n+1); 41 for(int i=n;i;i--) s[i]=s[i+1]+a[i]; 42 vis[0]=1; 43 for(int i=n;i;i--) dfs(i,0); 44 printf("%d\n",ans); 45 }
T3 grid
题目大意：
一个矩阵 规定一些子矩阵内最大值为k 求满足条件矩阵的方案数
思路：
离散化之后处理每个矩阵的大小
然后容斥
（std）
1 #include<bits/stdc++.h> 2 typedef long long i64; 3 const int P=1e9+7; 4 int T,h,w,m,n; 5 int xs[33],ys[33],xp,yp,vs[33],vp,ts[33]; 6 int rc[33][5],mv[33][33],as[33][33]; 7 void mins(int&a,int b){if(a>b)a=b;} 8 int pw(int a,int n){ 9 int v=1; 10 for(;n;n>>=1,a=i64(a)*a%P)if(n&1)v=i64(v)*a%P; 11 return v; 12 } 13 int main(){ 14 int ans=0; 15 scanf("%d%d%d%d",&h,&w,&m,&n); 16 xp=yp=vp=0; 17 xs[xp++]=1; 18 xs[xp++]=h+1; 19 ys[yp++]=1; 20 ys[yp++]=w+1; 21 vs[vp++]=m; 22 for(int i=0;i<n;++i){ 23 for(int j=0;j<5;++j)scanf("%d",rc[i]+j); 24 xs[xp++]=rc[i][0]; 25 xs[xp++]=rc[i][2]+1; 26 ys[yp++]=rc[i][1]; 27 ys[yp++]=rc[i][3]+1; 28 vs[vp++]=rc[i][4]; 29 vs[vp++]=rc[i][4]-1; 30 } 31 std::sort(xs,xs+xp); 32 xp=std::unique(xs,xs+xp)-xs-1; 33 std::sort(ys,ys+yp); 34 yp=std::unique(ys,ys+yp)-ys-1; 35 std::sort(vs,vs+vp); 36 vp=std::unique(vs,vs+vp)-vs; 37 for(int i=0;i<xp;++i) 38 for(int j=0;j<yp;++j)as[i][j]=(xs[i+1]-xs[i])*(ys[j+1]-ys[j]); 39 for(int t=0;t<n;++t){ 40 rc[t][0]=std::lower_bound(xs,xs+xp,rc[t][0])-xs; 41 rc[t][2]=std::lower_bound(xs,xs+xp,rc[t][2]+1)-xs; 42 rc[t][1]=std::lower_bound(ys,ys+yp,rc[t][1])-ys; 43 rc[t][3]=std::lower_bound(ys,ys+yp,rc[t][3]+1)-ys; 44 rc[t][4]=std::lower_bound(vs,vs+vp,rc[t][4])-vs; 45 } 46 for(int S=0;S<(1<<n);++S){ 47 for(int i=0;i<xp;++i) 48 for(int j=0;j<yp;++j)mv[i][j]=vp-1; 49 int s=1; 50 for(int t=0;t<n;++t){ 51 int v=rc[t][4]; 52 if(S>>t&1)s=-s,--v; 53 for(int i=rc[t][0];i<rc[t][2];++i) 54 for(int j=rc[t][1];j<rc[t][3];++j)mins(mv[i][j],v); 55 } 56 for(int i=0;i<vp;++i)ts[i]=0; 57 for(int i=0;i<xp;++i) 58 for(int j=0;j<yp;++j)ts[mv[i][j]]+=as[i][j]; 59 for(int i=0;i<vp;++i)s=i64(s)*pw(vs[i],ts[i])%P; 60 ans=(ans+s)%P; 61 } 62 printf("%d\n",(ans+P)%P); 63 return 0; 64 }
T4 road
题目大意：
一棵树 一个点S
Q次独立的询问 每次可以从S修一条简单路径使该路径上边权为0 求修改后 a - b 上路径权值和最小
思路：
由于边权可能为负 以S为根建树 每次只能从lca(a,b)引一条最长的链 所以用倍增维护每个点向上连续的最小值
查询的时候判断链是向左还是向右即可
（由于min设成了inf导致挂掉了）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<vector> 9 #define ll long long 10 #define MAXN 200100 11 #define inf 2139062143 12 using namespace std; 13 inline int read() 14 { 15 int f=1,x=0;char ch=getchar(); 16 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 17 while(isdigit(ch)) {x=x*10+ch-'0',ch=getchar();} 18 return x*f; 19 } 20 int n,q,s,cnt,tot,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1]; 21 int dep[MAXN],f[MAXN][22],g[MAXN][22],dis[MAXN],sz[MAXN],hsh[MAXN]; 22 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;} 23 void dfs(int x,int fa) 24 { 25 sz[x]=1,hsh[x]=++tot; 26 for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1]; 27 for(int i=1;(1<<i)<=dep[x];i++) g[x][i]=min(g[x][i-1],dis[x]-dis[f[x][i-1]]+g[f[x][i-1]][i-1]); 28 for(int i=fst[x];i;i=nxt[i]) 29 if(to[i]!=fa) 30 { 31 f[to[i]][0]=x,dep[to[i]]=dep[x]+1,dis[to[i]]=dis[x]+val[i]; 32 if(val[i]<0) g[to[i]][0]=val[i]; 33 dfs(to[i],x);sz[x]+=sz[to[i]]; 34 } 35 } 36 int lca(int u,int v) 37 { 38 if(dep[u]<dep[v]) swap(u,v);int t=dep[u]-dep[v]; 39 for(int i=21;i>=0;i--) if((1<<i)&t) u=f[u][i]; 40 if(u==v) return u; 41 for(int i=21;i>=0;i--) 42 if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; 43 return f[u][0]; 44 } 45 int work(int x,int anc) 46 { 47 int t=dep[x]-dep[anc],tmp=0,res=0; 48 for(int i=21;i>=0;i--) 49 if((1<<i)&t) 50 res=min(res,tmp+g[x][i]), 51 tmp+=dis[x]-dis[f[x][i]],x=f[x][i]; 52 return res; 53 } 54 int main() 55 { 56 freopen("road.in","r",stdin); 57 freopen("road.out","w",stdout); 58 n=read(),q=read(),s=read();int a,b,c,l3,res,sum; 59 for(int i=1;i<n;i++) {a=read(),b=read(),c=read();add(a,b,c);add(b,a,c);} 60 dfs(s,0); 61 while(q--) 62 { 63 a=read(),b=read(),c=lca(a,b),res=sum=dis[a]+dis[b]-(dis[c]<<1); 64 printf("%d\n",min(work(a,c)+dis[b]-dis[c],work(b,c)+dis[a]-dis[c])); 65 } 66 }
T5 bride
题目大意：
思路：
爆搜然后状态压缩计算答案
（不过好像题目锅了）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<vector> 9 #define ll long long 10 #define MAXN 200100 11 #define inf 2139062143 12 using namespace std; 13 inline int read() 14 { 15 int f=1,x=0;char ch=getchar(); 16 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 17 while(isdigit(ch)) {x=x*10+ch-'0',ch=getchar();} 18 return x*f; 19 } 20 int n,k,A,w[15],h[15],a[15],t[15],q[15],r,tmp[15]; 21 double ans=1.0; 22 void solve() 23 { 24 for(int i=1;i<=n;i++) tmp[i]=max(0,h[i]-10*a[i]); 25 double res=0.0,p;int cnt=0,sum=0;r=0; 26 for(int i=1;i<=n;i++) 27 if(tmp[i]>0) q[r++]=i; 28 for(int i=0;i<(1<<r);i++) 29 { 30 p=1.0;cnt=sum=0; 31 for(int j=0;j<r;j++) 32 if((1<<j)&i) p*=tmp[q[j]]/100.0,cnt++,sum+=w[q[j]]; 33 else p*=(1.0-tmp[q[j]]/100.0); 34 if(cnt>(n/2)) res+=(p*((double)sum/(sum+A))); 35 } 36 ans=min(ans,res); 37 } 38 void dfs(int x,int rst) 39 { 40 if(x==n||rst==0) {for(int i=x;i<=n;i++) a[i]=rst;solve();return ;} 41 for(int i=0;i<=rst;i++) {a[x]=i;dfs(x+1,rst-i);} 42 } 43 int main() 44 { 45 freopen("bride.in","r",stdin); 46 freopen("bride.out","w",stdout); 47 n=read(),k=read(),A=read(); 48 for(int i=1;i<=n;i++) w[i]=read(),h[i]=read(); 49 dfs(1,k);printf("%.6lf",ans); 50 }
T6 climb
题目大意：
一些人在树上走 每个人在树上走了一些链（从根开始）
求每个点分别为多少个人经过
思路：
对于每个人相当于对链并+1 由于只查询一次 只需要树上差分
按照dfs序排序 对相邻的两个的lca -1
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<vector> 9 #define ll long long 10 #define MAXN 200100 11 #define inf 2139062143 12 using namespace std; 13 inline int read() 14 { 15 int f=1,x=0;char ch=getchar(); 16 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 17 while(isdigit(ch)) {x=x*10+ch-'0',ch=getchar();} 18 return x*f; 19 } 20 int n,m,cnt,tot,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1]; 21 int dep[MAXN],fa[MAXN],sz[MAXN],hsh[MAXN],bl[MAXN]; 22 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;} 23 void dfs(int x) 24 { 25 sz[x]=1; 26 for(int i=fst[x];i;i=nxt[i]) 27 if(to[i]!=fa[x]) 28 { 29 dep[to[i]]=dep[x]+1;dfs(to[i]);sz[x]+=sz[to[i]]; 30 } 31 } 32 void dfs(int x,int anc) 33 { 34 bl[x]=anc,hsh[x]=++tot;int hvs=0; 35 for(int i=fst[x];i;i=nxt[i]) 36 if(to[i]!=fa[x]&&sz[to[i]]>sz[hvs]) hvs=to[i]; 37 if(!hvs) return ;dfs(hvs,anc); 38 for(int i=fst[x];i;i=nxt[i]) 39 if(to[i]!=fa[x]&&to[i]!=hvs) dfs(to[i],to[i]); 40 } 41 struct Ask {int pos,val;}g[MAXN]; 42 bool cmp(Ask a,Ask b) {return a.val<b.val||(a.val==b.val&&hsh[a.pos]<hsh[b.pos]);} 43 int lca(int u,int v) 44 { 45 while(bl[u]!=bl[v]) {if(dep[bl[u]]<dep[bl[v]]) swap(u,v);u=fa[bl[u]];} 46 return dep[u]>dep[v]?v:u; 47 } 48 int sum[MAXN]; 49 void work(int x) 50 { 51 for(int i=fst[x];i;i=nxt[i]) if(to[i]!=fa[x]) {work(to[i]);sum[x]+=sum[to[i]];} 52 } 53 int main() 54 { 55 freopen("climb.in","r",stdin); 56 freopen("climb.out","w",stdout); 57 n=read(),m=read(); 58 for(int i=2;i<=n;i++) {fa[i]=read()+1;add(i,fa[i]);add(fa[i],i);} 59 for(int i=1;i<=m;i++) g[i].pos=read()+1,g[i].val=read(); 60 dfs(1);dfs(1,1);sort(g+1,g+m+1,cmp); 61 for(int i=1,tmp=1;i<=m;tmp=++i) 62 { 63 while(g[i].val==g[i+1].val&&i<=m) i++; 64 for(int j=tmp;j<=i;j++) sum[g[j].pos]++; 65 for(int j=tmp;j<i;j++) sum[lca(g[j].pos,g[j+1].pos)]--; 66 } 67 work(1); 68 for(int i=1;i<=n;i++) printf("%d\n",sum[i]); 69 }
或者说是线段树合并裸题
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<vector> 8 #define maxm 200004 9 #define maxn 100005 10 using namespace std; 11 int read() { 12 int x=0,f=1;char ch=getchar(); 13 for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; 14 for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; 15 return x*f; 16 } 17 vector<int> pt[maxn]; 18 int n,m; 19 struct seg{int son[2],sum;bool val;}t[maxn*40]; 20 int rt[maxn],fg[maxn]; 21 struct Edge {int to,nxt;}e[maxm]; 22 int head[maxn],cnt; 23 void add(int u,int v) {e[cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt++;return;} 24 int merge(int x,int y) { 25 if(!x) return y;if(!y) return x; 26 if(t[x].sum<t[y].sum) swap(x,y); 27 if(t[x].val) {return x;} 28 t[x].son[0]=merge(t[x].son[0],t[y].son[0]); 29 t[x].son[1]=merge(t[x].son[1],t[y].son[1]); 30 t[x].sum=t[t[x].son[0]].sum+t[t[x].son[1]].sum; 31 t[x].val=t[t[x].son[0]].val&t[t[x].son[1]].val; 32 return x; 33 } 34 int hsh[maxn],tot,d[maxn],g[maxn],sz,ans[maxn]; 35 void add(int &x,int l,int r,int pos) { 36 if(!x) x=++sz,t[sz]=t[x]; 37 if(l==r) {t[x].val=1;t[x].sum=1;return;} 38 int mid=(l+r)>>1; 39 if(pos<=mid) {add(t[x].son[0],l,mid,pos);} 40 else {add(t[x].son[1],mid+1,r,pos);} 41 t[x].sum=t[t[x].son[0]].sum+t[t[x].son[1]].sum;t[x].val=t[t[x].son[0]].val&t[t[x].son[1]].val; 42 return; 43 } 44 void dfs(int x,int pre) { 45 if(fg[x]) for(int i=0;i<fg[x];i++) add(rt[x],1,tot,pt[x][i]); 46 for(int i=head[x];i>=0;i=e[i].nxt) { 47 int to=e[i].to;if(to==pre) continue; 48 dfs(to,x);rt[x]=merge(rt[x],rt[to]); 49 } 50 ans[x]=t[rt[x]].sum; 51 } 52 int main() { 53 freopen("climb.in","r",stdin); 54 freopen("climb.out","w",stdout); 55 memset(head,-1,sizeof(head)); 56 n=read(),m=read(); 57 for(int i=2;i<=n;i++) { 58 int tmp=read()+1; 59 add(i,tmp);add(tmp,i); 60 } 61 for(int i=1;i<=m;i++) { 62 d[i]=read()+1;g[i]=read(); 63 hsh[++tot]=g[i]; 64 } 65 sort(hsh+1,hsh+tot+1); 66 tot=unique(hsh+1,hsh+tot+1)-hsh-1; 67 for(int i=1;i<=m;i++) { 68 g[i]=lower_bound(hsh+1,hsh+tot+1,g[i])-hsh; 69 pt[d[i]].push_back(g[i]); 70 fg[d[i]]++; 71 } 72 dfs(1,0); 73 for(int i=1;i<=n;i++) printf("%d\n",ans[i]); 74 return 0; 75 }
