Dark`Kris

Private blog

I'm spark , hope you fire


2018校赛初赛题解

B 肥宅

裸的01背包,只不过重量和价值相等。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 23340;
int n,w;
int main()
{
    while(~scanf("%d%d",&w,&n))
    {
        int a[55]={0};
        int f[maxn]={0};
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            for(int j=w;j>=a[i];j--)
                f[j]=max(f[j],f[j-a[i]]+a[i]);
        int ans=0;
        for(int i=1;i<=w;i++)
            ans = max(ans,f[i]);
        printf("%d\n",w-ans);
    }
    return 0;
}

C 意大利炮

这个题第一思路是最短路,根据输入数据建一个无向图,跑spfa就可以了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
using namespace std;
const int maxn = 205,maxm = 1500;
int n,s,e;
int h[maxn],ed[maxm],nt[maxm],w[maxm],p;
int dist[maxn];
bool b[maxn];
void add(int x,int y,int z)
{
    ++p;
    ed[p]=y;
    w[p]=z;
    nt[p]=h[x];
    h[x]=p;
}
queue<int> que;
void que_clear()
{
    queue<int> res;
    que=res;
}
int main()
{
    while(~scanf("%d%d%d",&n,&s,&e))
    {
        que_clear();
        memset(h,0,sizeof(h));
        memset(b,0,sizeof(b));
        p=0;
        for(int i=1;i<=n;i++)
        {
            int z;
            scanf("%d",&z);
            if(i-z>0)add(i,i-z,1);
            if(i+z<=n)add(i,i+z,1);
        }
        for(int i=1;i<=n;i++)dist[i]=0xffffff;
        que.push(s);dist[s]=0;b[s]=true;
        while(!que.empty())
        {
            int u = que.front();que.pop();
            b[u]=false;
            int nowp = h[u];
            while(nowp)
            {
                int v = ed[nowp];
                if(dist[v]>dist[u]+w[nowp])
                {
                    dist[v]=dist[u]+w[nowp];
                    if(!b[v])
                    {
                        que.push(v);
                        b[v]=true;
                    }
                }
                nowp = nt[nowp];
            }
        }
        printf("%d\n",dist[e]==0xffffff?-1:dist[e]);
    }
    return 0;
}

D 睿智国

这个题有点意思。
因为这个题没给数据范围,所以读完题以后脑子里飘过了两种做法:

  1. Floyd暴力一把梭
  2. 网络流最大流一把梭

Floyd好久没写过了就写了EK,结果发现超时了。
之后换成了Dinic,结果又超时了。
刚想换ISAP,队友及时制止我,说数据范围不知道,可能不是网络流。

然后脑子里就灵光一闪想出来了正解:
假设你是村民,你肯定只走对年龄要求合适的路,换句话说,你肯定要走路长更长的路。那么这显然是一个最大生成树。先跑一遍Kruskal(顺手写了并查集版的,不知道不是并查集能不能过,应该影响不大),把所有有价值的边找出来。
之后这些有价值的边就变成了一张新的图,或者说是无根树。
对于每一对(起点,终点),肯定只存在一条路径,你只需要找出来这条路径和这条路径上的边的最小路长就可以了。那么显然可以用倍增版的LCA来解,只要在LCA向上找最先公共祖先的时候记录一下最小路长就可以了。

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 1e5+5,maxm = 5e5+5,maxans = 1e9;
struct Edge{
    int x,y,dis;
    Edge(){};
    Edge(int _x,int _y,int _z):x(_x),y(_y),dis(_z){};
}edge[maxm];
int n,m;
int h[maxn],w[maxm],nt[maxm],ed[maxm],p;
int dp[maxn],fa[maxn][25],wight[maxn][25];
int f[maxn];
bool b[maxn];

int find(int x){return f[x]==x ? x : f[x]=find(f[x]);}
bool compare(Edge e1,Edge e2){return e1.dis>e2.dis;}
void add(int x,int y,int z)
{
    p++;
    w[p]=z;
    ed[p]=y;
    nt[p]=h[x];
    h[x]=p;
}
void minest_Tree()
{
    for(int i=1;i<=n;i++)f[i]=i;
    sort(edge+1,edge+m+1,compare);
    for(int i=1;i<=m;i++)
    {
        int f1 = find(edge[i].x);
        int f2 = find(edge[i].y);
        if(f1!=f2)
        {
            f[f1]=f2;
            add(edge[i].x,edge[i].y,edge[i].dis);
            add(edge[i].y,edge[i].x,edge[i].dis);
        }
    }
}
void dfs(int x)
{
    b[x]=true;
    int nowp = h[x];
    while(nowp)
    {
        int v=ed[nowp];
        if(!b[v]){
            dp[v]=dp[x]+1;
            fa[v][0]=x;
            wight[v][0]=w[nowp];
            dfs(v);
        }
        nowp=nt[nowp];
    }
}
inline int minmin(int a,int b,int c)
{
    if(a>b)a=b;
    if(a>c)a=c;
    return a;
}
int lca(int x,int y)
{
    if(find(x)!=find(y))return -1;
    int ans = maxans;
    
    if(dp[x]>dp[y])swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(dp[fa[y][i]]>=dp[x])
        {
            ans = min(ans,wight[y][i]);
            y = fa[y][i];
        }
    }
    if(x==y)return ans;//find it
    
    for(int i=20;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i]){
            ans = minmin(ans,wight[x][i],wight[y][i]);
            x=fa[x][i];y=fa[y][i];
        }
    }
    ans = minmin(ans,wight[x][0],wight[y][0]);
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        edge[i].x = x;
        edge[i].y = y;
        edge[i].dis = z;
    }
    minest_Tree();
    for(int i=1;i<=n;i++)
    {
        if(!b[i]){
            dp[i]=1;dfs(i);
            fa[i][0]=i;wight[i][0]=maxans;
        }
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            fa[j][i]=fa[fa[j][i-1]][i-1];
            wight[j][i]=min(wight[j][i-1],wight[fa[j][i-1]][i-1]);
        }
    }
    int qes;
    scanf("%d",&qes);
    for(int i=1;i<=qes;i++)
    {
        int s,e;
        scanf("%d %d",&s,&e);
        printf("%d\n",lca(s,e));
    }
    return 0;
}

H 数据备份

这题一眼看过去是最小生成树,但是后来一想每个城市是多个数据存储点,我感觉是错解。队友跟我说你对每个点都跑一个最小生成树就好了呀。但是我觉得好难写啊,都不如最短路。于是我就想到了一个做法,单源最短路径最短路暴力一把梭。
对于每一个城市,我们都假设它是数据中心,跑一遍单源最短路径,算出来从他到其他所有点的最短路。那么这个城市的数据备份代价就是。其中dist是起点S到i的距离,cnt是在城市i中数据存储点的个数。那么我们只要找到代价最低的城市就可以了。
emmmmm没敢写spfa,怕给卡了,写了一个heap优化的dijkstra。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
using namespace std;
const long long maxn = 1e4+5 , maxm=5e4+5;
struct node{
    long long u,dis;
    
    node(long long _u,long long _dis):u(_u),dis(_dis){};
    
    bool operator <(const node& b)const{
        return dis>b.dis;
    }
};
priority_queue<node> que;
long long h[maxn],w[maxm],ed[maxm],nt[maxm],p;
long long n,m,c;
bool b[maxn];
long long dist[maxm];
int cnt[maxn];

void add(long long x,long long y,long long z)
{
    ++p;
    w[p]=z;
    ed[p]=y;
    nt[p]=h[x];
    h[x]=p;
}
void que_clear()
{
    priority_queue<node> res;
    que=res;
}
void heap_dij(int s)
{
    que_clear();
    memset(b,0,sizeof(b));
    for(int i=1;i<=c;i++)dist[i]=0x7fffffff;
    que.push(node(s,0));dist[s]=0;
    while(!que.empty())
    {
        long long u = que.top().u;que.pop();
        long long nowp = h[u];
        if(b[u])continue;
        b[u]=true;
        while(nowp)
        {
            long long v = ed[nowp];
            if(!b[v])
            {
                if(dist[v]>dist[u]+w[nowp])
                {
                    dist[v]=dist[u]+w[nowp];
                    que.push(node(v,dist[v]));
                }
            }
            nowp=nt[nowp];
        }
    }
}
long long work()
{
    long long ans=0;
    for(int i=1;i<=c;i++)
        ans += dist[i]*cnt[i];
    return ans;
}
int main()
{
    while(~scanf("%lld %lld %lld",&n,&c,&m))
    {
        memset(cnt,0,sizeof(cnt));
        memset(h,0,sizeof(h));
        p=0;
        for(int i=1;i<=n;i++)
        {
            int res;
            scanf("%d",&res);
            cnt[res]++;
        }
        for(int i=1;i<=m;i++)
        {
            long long x,y,z;
            scanf("%lld %lld %lld",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        long long ans=0x7fffffff;
        for(int s=1;s<=c;s++)
        {
            heap_dij(s);
            ans = min(ans,work());
        }
        printf("%lld\n",ans);
    }
    return 0;
}

其他

啊博主作业好多,其他的丢给队友写了,附链接: ljw的洛谷博客

谢谢阅读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading