5月集训Day1考试

时间：2021-08-30 09:47:40

话说这题很水啊，结果。。。

目录

最优构造树Tree

5月集训Day1考试
5月集训Day1考试
状压dp，01表示可选字母的集合，对于ls，rs有交集取交集，不然取并集；

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN=2050,MAXL=1005;
int dp[MAXN][MAXL][2];
char tmp[MAXL];

int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
int n,l;
while(scanf("%d%d",&n,&l),n && l){
memset(dp,0,sizeof(dp));
for(int i=0;i<n;++i){
scanf("%s",tmp+1);
for(int j=1;j<=l;++j)
                dp[i+n][j][0]|=1<<(tmp[j]-'A');
        }
for(int i=n-1,ls,rs;i;--i){
            ls=i<<1,rs=ls^1;
for(int j=1;j<=l;++j){
if(dp[ls][j][0] & dp[rs][j][0]){
                    dp[i][j][0]=dp[ls][j][0]&dp[rs][j][0];
                    dp[i][j][1]=dp[ls][j][1]+dp[rs][j][1];
                }
else{
                    dp[i][j][0]=dp[ls][j][0]|dp[rs][j][0];
                    dp[i][j][1]=dp[ls][j][1]+dp[rs][j][1]+1;
                }
            }
        }
int ans=0;
for(int i=1;i<=l;++i)
            ans+=dp[1][i][1];
printf("%d\n",ans);
    }
return 0;
}

柠檬的坦克游戏tank

5月集训Day1考试
5月集训Day1考试
暴力模拟O(n^3)，按一个属性排序会发现另一个是降序，并且每个集合中另一个属性升序，二分查找优化到O(nlogn)；
ps：话说为啥双堆会错。。。

#include <cstdio>
#include <algorithm>
using namespace std;
#define max(a,b) (a>b ? a:b)

const int MAXN=100005;
int maxr[MAXN],pos[MAXN],n;

struct node{
int d,r,no;
}wq[MAXN];

bool cmp(const node &a,const node &b){
return a.d>b.d;
}

inline int read();

inline int find(const int &w){
int l=1,r=n,mid;
while(r>l){
        mid=(l+r)>>1;
if(maxr[mid]>w) l=mid+1;
else r=mid;
    }
return l;
}

int main(){
    freopen("tank.in","r",stdin);
    freopen("tank.out","w",stdout);
    n=read();
for(int i=1;i<=n;++i){
        wq[i].d=read();
        wq[i].r=read();
        wq[i].no=i;
    }
sort(wq+1,wq+n+1,cmp);
for(int i=1,loc;i<=n;++i){
        loc=find(wq[i].r);
pos[wq[i].no]=loc;
        maxr[loc]=max(maxr[loc],wq[i].r);
    }
for(int i=1;i<=n;++i)
printf("%d\n",pos[i]);
    fclose(stdin);
    fclose(stdout);
return 0;
}

inline int read(){
    char c; int x;
while(c=getchar(),c<'0' || '9'<c);
x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
x=x*10+c-'0';
return x;
}

柠檬当上警察局长catch

5月集训Day1考试
5月集训Day1考试
5月集训Day1考试
树形dp+概率论，其实本来想到正解的。。。
ps：哎，忘了乘上到这个点的概率了。。。

#include <cstdio>
#include <queue>
using namespace std;
#define max(a,b) (a>b ? a:b)

const int MAXN=205,MAXM=40005,INF=int(1e9);
int n,m,s;
int he[MAXN],cnt;
int dis[MAXN],pre[MAXN];
bool vis[MAXN];
int out[MAXN];
double p[MAXN][MAXN];
double psb[MAXN],dp[MAXN][MAXN],tmp[MAXN];

struct node{
int x,d;
friend bool operator> (const node &a,const node &b){
return a.d>b.d;
    }
};
priority_queue<node,vector<node>,greater<node> > hp;

struct line{
int to,nex,w;
};

struct CFS{
int cnt,he[MAXN];
        line ed[MAXM];
void add(const int &u,const int &v,const int &w){
            ed[++cnt].nex=he[u];
            he[u]=cnt;
            ed[cnt].to=v;
            ed[cnt].w=w;
        }
}G,T;

void dijsktra(){
for(int i=2;i<=n;++i)
        dis[i]=INF;
    hp.push((node){1,0});
while(hp.size()){
int u=hp.top().x;
        hp.pop();
if(vis[u]) continue;
        vis[u]=true;
for(int i=G.he[u],v,w;i;i=G.ed[i].nex){
            v=G.ed[i].to,w=G.ed[i].w;
if(dis[v]>dis[u]+w){
                pre[v]=u;
                dis[v]=dis[u]+w;
                hp.push((node){v,dis[v]});
            }
        }
    }
}

inline void rebuild(){
for(int i=2;i<=n;++i){
        ++out[pre[i]];
        T.add(pre[i],i,0);
    }
}

void dfs(const int &u){
for(int i=T.he[u];i;i=T.ed[i].nex)
        dfs(T.ed[i].to);
if(out[u]){
for(int i=0;i<=s;++i) tmp[i]=0;
for(int i=T.he[u];i;i=T.ed[i].nex){
for(int j=s;j;--j){
for(int k=0;k<=j;++k)
                    tmp[j]=max(tmp[j],tmp[j-k]+dp[T.ed[i].to][k]);
            }
        }
for(int i=0;i<=s;++i){
for(int j=0;j<=i;++j)
                dp[u][i]=max(dp[u][i],p[u][j]+(1-p[u][j])/out[u]*tmp[i-j]);
        }
    }
else{
for(int i=0;i<=s;++i)
            dp[u][i]=p[u][i];
    }
}

int main(){
    freopen("catch.in","r",stdin);
    freopen("catch.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1,a,b,c;i<=m;++i){
scanf("%d%d%d",&a,&b,&c);
        G.add(a,b,c);
        G.add(b,a,c);
    }
    dijsktra();
    rebuild();
scanf("%d",&s);
for(int i=1;i<=n;++i){
for(int j=1;j<=s;++j)
scanf("%lf",&p[i][j]);
    }
    dfs(1);
printf("%.4lf",dp[1][s]);
    fclose(stdin);
    fclose(stdout);
return 0;
}

ps：今天才补的题解。。。
标签：

相关文章