10.8 模拟赛

非常的菜 被初中踩成了弱智

T1 game

题目大意：

n轮游戏 在第$i$轮已经获胜$j$轮继续获胜的概率为 p i j

每一轮可以选择放弃（即100%失败）

求最优策略下 获胜场数的期望

思路：

可以发现并不需要放弃

直接dp即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define inf 2139062143
#define ll long long
#define MAXN 1100
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//yyc score=0
int n;
double a[MAXN][MAXN],dp[MAXN][MAXN],ans;
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) scanf("%lf",&a[i][j]);
    dp[1][1]=1.0;
    for(int i=2;i<=n+1;i++) for(int j=1;j<=i;j++)
        dp[i][j]=dp[i-1][j]*(1.0-a[i-1][j])+dp[i-1][j-1]*a[i-1][j-1];
    for(int i=1;i<=n+1;i++) ans+=(i-1)*dp[n+1][i];
    printf("%.2lf",ans);
}

T2 cake 

题目大意：

n个物品 每个物品体积即背包$le 10^9$ 求背包内最大体积

思路：

本来是一个折半搜索裸题

#include<bits/stdc++.h>
#define LL long long
#define M 1200020
using namespace std;
namespace IO{
    const int BS=(1<<20)+5; int Top=0;
    char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1;
    char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}
    void flush(){fwrite(OT,1,OS-OT,stdout);}
    void Putchar(char c){*OS++ =c;if(OS==fin)flush(),OS=OT;}
    void write(int x){
        if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-');
        while(x) SS[++Top]=x%10,x/=10;
        while(Top) Putchar(SS[Top]+'0'),--Top;
    }
    int read(){
        int nm=0,fh=1; char cw=getchar();
        for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
        for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
        return nm*fh;
    }
}using namespace IO;
int n,m,val[50][2],p[2][M],maxn,tp[2],sz[2],ans;
void dfs(int pos,int now,int kd){
    if(now>m) return;
    if(pos==tp[kd]+1){p[kd][++sz[kd]]=now;return;}
    dfs(pos+1,now,kd),dfs(pos+1,now+val[pos][kd],kd);
}
int main(){
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);
    n=read(),m=read(),ans=m;
    for(int i=1;i<=n;i++) val[++tp[i&1]][i&1]=read();
    dfs(1,0,0),sort(p[0]+1,p[0]+sz[0]+1);
    dfs(1,0,1),sort(p[1]+1,p[1]+sz[1]+1);
    for(int i=0,j=sz[1];i<=sz[0];i++){
        while(j>0&&p[0][i]+p[1][j]>m) j--;
        ans=min(ans,m-p[0][i]-p[1][j]);
    }printf("%d
",ans);return 0;
}

但是我非常菜的直接dfs剪枝得了90分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define inf 2139062143
#define ll long long
#define MAXN 50
#define MOD 1000000007
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//yyc score=0
int n,m,a[MAXN],ans=inf,s[MAXN];
map <int,bool> vis;
void dfs(int x,int sum)
{
    //cout<<x<<" "<<sum+a[x]<<endl;
    if(sum+a[x]>m||vis[sum+a[x]]) return ;vis[sum+a[x]]=1,ans=min(ans,m-sum-a[x]);
    if(x==1) {ans=min(ans,m-sum-a[x]);return ;}
    if(sum+s[1]-s[x+1]<=m) {ans=min(ans,m-sum-s[1]+s[x+1]);return ;}
    for(int i=x-1;i;i--)
        if(sum+a[x]+a[i]<=m) dfs(i,sum+a[x]);
}
int main()
{
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    for(int i=n;i;i--) s[i]=s[i+1]+a[i];
    vis[0]=1;
    for(int i=n;i;i--) dfs(i,0);
    printf("%d
",ans);
}

T3 grid

题目大意：

一个矩阵 规定一些子矩阵内最大值为k 求满足条件矩阵的方案数

思路：

离散化之后处理每个矩阵的大小

然后容斥

（std）

#include<bits/stdc++.h>
typedef long long i64;
const int P=1e9+7;
int T,h,w,m,n;
int xs[33],ys[33],xp,yp,vs[33],vp,ts[33];
int rc[33][5],mv[33][33],as[33][33];
void mins(int&a,int b){if(a>b)a=b;}
int pw(int a,int n){
    int v=1;
    for(;n;n>>=1,a=i64(a)*a%P)if(n&1)v=i64(v)*a%P;
    return v;
}
int main(){
    int ans=0;
    scanf("%d%d%d%d",&h,&w,&m,&n);
    xp=yp=vp=0;
    xs[xp++]=1;
    xs[xp++]=h+1;
    ys[yp++]=1;
    ys[yp++]=w+1;
    vs[vp++]=m;
    for(int i=0;i<n;++i){
        for(int j=0;j<5;++j)scanf("%d",rc[i]+j);
        xs[xp++]=rc[i][0];
        xs[xp++]=rc[i][2]+1;
        ys[yp++]=rc[i][1];
        ys[yp++]=rc[i][3]+1;
        vs[vp++]=rc[i][4];
        vs[vp++]=rc[i][4]-1;
    }
    std::sort(xs,xs+xp);
    xp=std::unique(xs,xs+xp)-xs-1;
    std::sort(ys,ys+yp);
    yp=std::unique(ys,ys+yp)-ys-1;
    std::sort(vs,vs+vp);
    vp=std::unique(vs,vs+vp)-vs;
    for(int i=0;i<xp;++i)
    for(int j=0;j<yp;++j)as[i][j]=(xs[i+1]-xs[i])*(ys[j+1]-ys[j]);
    for(int t=0;t<n;++t){
        rc[t][0]=std::lower_bound(xs,xs+xp,rc[t][0])-xs;
        rc[t][2]=std::lower_bound(xs,xs+xp,rc[t][2]+1)-xs;
        rc[t][1]=std::lower_bound(ys,ys+yp,rc[t][1])-ys;
        rc[t][3]=std::lower_bound(ys,ys+yp,rc[t][3]+1)-ys;
        rc[t][4]=std::lower_bound(vs,vs+vp,rc[t][4])-vs;
    }
    for(int S=0;S<(1<<n);++S){
        for(int i=0;i<xp;++i)
        for(int j=0;j<yp;++j)mv[i][j]=vp-1;
        int s=1;
        for(int t=0;t<n;++t){
            int v=rc[t][4];
            if(S>>t&1)s=-s,--v;
            for(int i=rc[t][0];i<rc[t][2];++i)
            for(int j=rc[t][1];j<rc[t][3];++j)mins(mv[i][j],v);
        }
        for(int i=0;i<vp;++i)ts[i]=0;
        for(int i=0;i<xp;++i)
        for(int j=0;j<yp;++j)ts[mv[i][j]]+=as[i][j];
        for(int i=0;i<vp;++i)s=i64(s)*pw(vs[i],ts[i])%P;
        ans=(ans+s)%P;
    }
    printf("%d
",(ans+P)%P);
    return 0;
}

T4 road

题目大意：

一棵树 一个点S 

Q次独立的询问 每次可以从S修一条简单路径使该路径上边权为0 求修改后 a - b 上路径权值和最小

思路：

由于边权可能为负 以S为根建树 每次只能从lca(a,b)引一条最长的链 所以用倍增维护每个点向上连续的最小值

查询的时候判断链是向左还是向右即可

（由于min设成了inf导致挂掉了）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define MAXN 200100
#define inf 2139062143
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0',ch=getchar();}
    return x*f;
}
int n,q,s,cnt,tot,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1];
int dep[MAXN],f[MAXN][22],g[MAXN][22],dis[MAXN],sz[MAXN],hsh[MAXN];
void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
void dfs(int x,int fa)
{
    sz[x]=1,hsh[x]=++tot;
    for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1];
    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]);
    for(int i=fst[x];i;i=nxt[i])
        if(to[i]!=fa)
        {
            f[to[i]][0]=x,dep[to[i]]=dep[x]+1,dis[to[i]]=dis[x]+val[i];
            if(val[i]<0) g[to[i]][0]=val[i];
            dfs(to[i],x);sz[x]+=sz[to[i]];
        }
}
int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);int t=dep[u]-dep[v];
    for(int i=21;i>=0;i--) if((1<<i)&t) u=f[u][i];
    if(u==v) return u;
    for(int i=21;i>=0;i--)
        if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return f[u][0];
}
int work(int x,int anc)
{
    int t=dep[x]-dep[anc],tmp=0,res=0;
    for(int i=21;i>=0;i--)
        if((1<<i)&t)
            res=min(res,tmp+g[x][i]),
            tmp+=dis[x]-dis[f[x][i]],x=f[x][i];
    return res;
}
int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    n=read(),q=read(),s=read();int a,b,c,l3,res,sum;
    for(int i=1;i<n;i++) {a=read(),b=read(),c=read();add(a,b,c);add(b,a,c);}
    dfs(s,0);
    while(q--)
    {
        a=read(),b=read(),c=lca(a,b),res=sum=dis[a]+dis[b]-(dis[c]<<1);
        printf("%d
",min(work(a,c)+dis[b]-dis[c],work(b,c)+dis[a]-dis[c]));
    }
}

T5 bride

题目大意：

思路：

爆搜然后状态压缩计算答案

（不过好像题目锅了）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define MAXN 200100
#define inf 2139062143
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0',ch=getchar();}
    return x*f;
}
int n,k,A,w[15],h[15],a[15],t[15],q[15],r,tmp[15];
double ans=1.0;
void solve()
{
    for(int i=1;i<=n;i++) tmp[i]=max(0,h[i]-10*a[i]);
    double res=0.0,p;int cnt=0,sum=0;r=0;
    for(int i=1;i<=n;i++)
        if(tmp[i]>0) q[r++]=i;
    for(int i=0;i<(1<<r);i++)
    {
        p=1.0;cnt=sum=0;
        for(int j=0;j<r;j++)
            if((1<<j)&i) p*=tmp[q[j]]/100.0,cnt++,sum+=w[q[j]];
            else p*=(1.0-tmp[q[j]]/100.0);
        if(cnt>(n/2)) res+=(p*((double)sum/(sum+A)));
    }
    ans=min(ans,res);
}
void dfs(int x,int rst)
{
    if(x==n||rst==0) {for(int i=x;i<=n;i++) a[i]=rst;solve();return ;}
    for(int i=0;i<=rst;i++) {a[x]=i;dfs(x+1,rst-i);}
}
int main()
{
    freopen("bride.in","r",stdin);
    freopen("bride.out","w",stdout);
    n=read(),k=read(),A=read();
    for(int i=1;i<=n;i++) w[i]=read(),h[i]=read();
    dfs(1,k);printf("%.6lf",ans);
}

T6 climb

题目大意：

一些人在树上走 每个人在树上走了一些链（从根开始）

求每个点分别为多少个人经过

思路：

对于每个人相当于对链并+1 由于只查询一次 只需要树上差分 

按照dfs序排序 对相邻的两个的lca -1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define MAXN 200100
#define inf 2139062143
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0',ch=getchar();}
    return x*f;
}
int n,m,cnt,tot,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1];
int dep[MAXN],fa[MAXN],sz[MAXN],hsh[MAXN],bl[MAXN];
void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
void dfs(int x)
{
    sz[x]=1;
    for(int i=fst[x];i;i=nxt[i])
        if(to[i]!=fa[x])
        {
            dep[to[i]]=dep[x]+1;dfs(to[i]);sz[x]+=sz[to[i]];
        }
}
void dfs(int x,int anc)
{
    bl[x]=anc,hsh[x]=++tot;int hvs=0;
    for(int i=fst[x];i;i=nxt[i])
        if(to[i]!=fa[x]&&sz[to[i]]>sz[hvs]) hvs=to[i];
    if(!hvs) return ;dfs(hvs,anc);
    for(int i=fst[x];i;i=nxt[i])
        if(to[i]!=fa[x]&&to[i]!=hvs) dfs(to[i],to[i]);
}
struct Ask {int pos,val;}g[MAXN];
bool cmp(Ask a,Ask b) {return a.val<b.val||(a.val==b.val&&hsh[a.pos]<hsh[b.pos]);}
int lca(int u,int v) 
{
    while(bl[u]!=bl[v]) {if(dep[bl[u]]<dep[bl[v]]) swap(u,v);u=fa[bl[u]];}
    return dep[u]>dep[v]?v:u;
}
int sum[MAXN];
void work(int x)
{
    for(int i=fst[x];i;i=nxt[i]) if(to[i]!=fa[x]) {work(to[i]);sum[x]+=sum[to[i]];}
}
int main()
{
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    n=read(),m=read();
    for(int i=2;i<=n;i++) {fa[i]=read()+1;add(i,fa[i]);add(fa[i],i);}
    for(int i=1;i<=m;i++) g[i].pos=read()+1,g[i].val=read();
    dfs(1);dfs(1,1);sort(g+1,g+m+1,cmp);
    for(int i=1,tmp=1;i<=m;tmp=++i)
    {
        while(g[i].val==g[i+1].val&&i<=m) i++;
        for(int j=tmp;j<=i;j++) sum[g[j].pos]++;
        for(int j=tmp;j<i;j++) sum[lca(g[j].pos,g[j+1].pos)]--;
    }
    work(1);
    for(int i=1;i<=n;i++) printf("%d
",sum[i]);
}

或者说是线段树合并裸题

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#define maxm 200004
#define maxn 100005
using namespace std;
int read() {
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
vector<int> pt[maxn];
int n,m;
struct seg{int son[2],sum;bool val;}t[maxn*40];
int rt[maxn],fg[maxn];
struct Edge {int to,nxt;}e[maxm];
int head[maxn],cnt;
void add(int u,int v) {e[cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt++;return;}
int merge(int x,int y) {
    if(!x) return y;if(!y) return x;
    if(t[x].sum<t[y].sum) swap(x,y);
    if(t[x].val) {return x;}
    t[x].son[0]=merge(t[x].son[0],t[y].son[0]);
    t[x].son[1]=merge(t[x].son[1],t[y].son[1]);
    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;
    return x;
}
int hsh[maxn],tot,d[maxn],g[maxn],sz,ans[maxn];
void add(int &x,int l,int r,int pos) {
    if(!x) x=++sz,t[sz]=t[x];
    if(l==r) {t[x].val=1;t[x].sum=1;return;}
    int mid=(l+r)>>1;
    if(pos<=mid) {add(t[x].son[0],l,mid,pos);}
    else {add(t[x].son[1],mid+1,r,pos);}
    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;
    return;
}
void dfs(int x,int pre) {
    if(fg[x]) for(int i=0;i<fg[x];i++) add(rt[x],1,tot,pt[x][i]);
    for(int i=head[x];i>=0;i=e[i].nxt) {
        int to=e[i].to;if(to==pre) continue;
        dfs(to,x);rt[x]=merge(rt[x],rt[to]);
    }
    ans[x]=t[rt[x]].sum;
}
int main() {
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    memset(head,-1,sizeof(head));
    n=read(),m=read();
    for(int i=2;i<=n;i++) {
        int tmp=read()+1;
        add(i,tmp);add(tmp,i);
    }
    for(int i=1;i<=m;i++) {
        d[i]=read()+1;g[i]=read();
        hsh[++tot]=g[i];
    }
    sort(hsh+1,hsh+tot+1);
    tot=unique(hsh+1,hsh+tot+1)-hsh-1;
    for(int i=1;i<=m;i++) {
        g[i]=lower_bound(hsh+1,hsh+tot+1,g[i])-hsh;
        pt[d[i]].push_back(g[i]);
        fg[d[i]]++;
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) printf("%d
",ans[i]);
    return 0;
}