您的位置: 首页  >  文章  >  10.2清北刷题记

10.2清北刷题记

分类: 文章 • 2024-06-16 13:58:22

10.2 Morning

Problem A. distance

【题目描述】

有一个n个点m条边的无权无向联通图，满足图中不存在长度大于等于3的环，并且图中没有重边和自环。

定义两个点u,v的距离d(u,v)为这两个点之间最短路上的点数,求

                min{max d(u,v)}

【输入描述】

第一行两个数n,m，表示图的点数和边数 接下来m行，每行两个正整数描述一条边

【输出描述】

一行一个正整数,表示答案

【输入输出样例】

【input】

3 2

1 2

1 3

【output】

2

【input】

7 6

1 2

1 6

2 5

3 1

4 7

2 4

【output】

3

【数据范围】

对于30%的数据，n,m<=20

对于60%的数据，n,m<=1000

对于100%的数据，n,m<=100000

【题解】

10.2清北刷题记

【代码实现】

30分代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 10050;
const int maxm = 10050;
int n, m;
int d[maxn][maxn];
int ans = 1e9;

int main()
{
    freopen("distance.in", "r", stdin);
    freopen("distance.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            d[i][j] = (int)1e9;
        }
    }

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        d[x][y] = d[y][x] = 1;
    }

    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (i == j || j == k || k == i)
                {
                    continue;
                }
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    /*for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (d[i][j] == (int)1e9)
            {
                printf("I ");
                continue;
            }
            printf("%d ", d[i][j]);
        }
        printf("\n");

    }*/

    for (int i = 1; i <= n; ++i)
    {
        int maxl = -1;
        for (int j = 1; j <= n; ++j)
        {
            if (d[i][j] >= (int)1e9)
            {
                continue;
            }
            maxl = max(maxl, d[i][j]);
        }
        ans = min(ans, maxl);
    }
    printf("%d", ans + 1);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

60分代码

#include <queue>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 100005
#define PII pair<int,int>

int n,m,cnt,ans=0x3f3f3f3f;
int head[MAXN];
int dis[MAXN],vis[MAXN];
priority_queue <PII,vector<PII>,greater<PII> >que;

struct node{
    int to,nxt;
}map[2*MAXN];

void add(int u, int v)
{
    map[++cnt] = (node){v,head[u]};
    head[u] = cnt;
}

void heap_Dij(int i)
{
    dis[i] = 1;
    que.push(make_pair(1,i));
    while(!que.empty())
    {
        int u = que.top().second;   que.pop();
        if(vis[u])  continue;
        vis[u] = 1;
        for(int k=head[u];k;k=map[k].nxt)
        {
            int v = map[k].to;
            if( dis[v] > dis[u]+1)
            {
                dis[v] = dis[u]+1;
                que.push(make_pair(dis[v],v));
            }
        }
    }
}

int main(void)
{
    freopen("distance.in","r",stdin);
    freopen("distance.out","w",stdout);
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin >> u >> v;
        add(u,v);   add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof vis);
        memset(dis,0x3f,sizeof dis);
        heap_Dij(i);
        sort(dis+1,dis+1+n);
        ans = min(ans,dis[n]);
    }
    cout << ans;
    return 0;
}

100分代码

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

const int N = (int)1e5;
typedef int arrv[N + 10];
typedef int arre[2 * N + 10];

int n, tot, j, k;
arrv g;
arre pt, nt;

void Link(int x, int y) {
    pt[++tot] = y, nt[tot] = g[x], g[x] = tot;
    pt[++tot] = x, nt[tot] = g[y], g[y] = tot;
}

void Dfs(int x, int fa, int dis) {
    if (dis > k) k = dis, j = x;
    for (int i = g[x]; i; i = nt[i])
        if (pt[i] != fa) Dfs(pt[i], x, dis + 1);
}

int main() {
    freopen("distance.in", "r", stdin);
    freopen("distance.out", "w", stdout);

    scanf("%d%d\n", &n, &k);
    for (int i = 1; i < n; ++i) scanf("%d%d\n", &j, &k), Link(j, k);

    j = k = 0;
    Dfs(1, 0, 1);
    Dfs(j, 0, 1);
    if (~k & 1) printf("%d\n", k / 2 + 1);
    else printf("%d\n", (k + 1) / 2);

    return 0;
}

Problem B. graph

【题目描述】

给定一张n个点m条边的无向图,每条边有一个权值

求一条从S到r的路径,使得这条路径上权值最大的边比上权值最小的边的比值最小

【输入描述】

第一行两个正整数n和m,表示图的边数和点数。

接下来的m行每行三个正整数x,y,z,表示连接x和y的一条权值为z的边。

最后一行两个正整数S,T。

【输出描述】

如果S到T没有通路,那么输出“ IMPOSSIBLE”(不含引号)。否则输出一个形如A/B的既约分数,表示最小的比值。

【输入输出样例】

【input】

4 2

1 2 1

3 4 2

1 4

【output】

IMPOSSIBLE

【input】

3 3

1 2 10

1 2 5

2 3 8

1 3

【output】

5/4

【input】

3 2

1 2 2

2 3 4

1 3

【output】

2

【数据范围】

对于20%的数据，n,m<=5

对于30%的数据，n<=100,m<=200,最大边权不超过100

对于100%的数据，n<=500,m<=5000,0<w<30000,x!=y,S!=T

【题解】

10.2清北刷题记

【代码实现】

20分代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 5008;
int n, m, s, t, MX, MN, vis[maxn];
float ans = 99999.00;
typedef pair<int,int> pii;
vector <pii> G[maxn];

void dfs(int u, int mx, int mn){
    if(u == t){
        if(ans > mx/float(mn)){
            ans = mx/float(mn);
            MX = mx;
            MN = mn;
        }
        return;
    }
    for(int i=0 ; i<G[u].size() ; i++){
        int v = G[u][i].first, d = G[u][i].second;
        if(!vis[v]){
            vis[v] = 1;
            dfs(v, max(mx, d), min(mn, d));
            vis[v] = 0;
        }
    }
}

int gcd(int a, int b){
    return b ? gcd(b, a%b) : a;
}

int main(){
    freopen("graph.in","r",stdin); freopen("graph.out","w",stdout);
    scanf("%d%d", &n, &m);
    if(m >= 200){
        printf("IMPOSSIBLE\n");
        return 0;
    }
    for(int i=1 ; i<=m ; i++){
        int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        G[u].push_back(make_pair(v, d));
        G[v].push_back(make_pair(u, d));
    }
    vis[s] = 1;
    scanf("%d%d", &s, &t);
    dfs(s, -1, 0x3f3f3f3f);
    if(ans == 99999.00) printf("IMPOSSIBLE\n");
    else{
        if(MX%MN==0) printf("%d\n", MX/MN);
        else{
            int g = gcd(MX, MN);
            printf("%d/%d\n", MX/g, MN/g);
        }
    }
}

30分代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int S,T;
int N,M,to[20001],hd[20001],nxt[20001],val[20001],tot;
void puts(int x,int y,int v)
{   
    ++tot;
    to[tot]=y;
    val[tot]=v;
    nxt[tot]=hd[x];
    hd[x]=tot;
}
int read()
{ 
    int x;char ch;
    while( ch = getchar() , ( ch < '0' || ch > '9' ) ) ;
    x=ch-'0';
    while( ch = getchar() , ( ch >='0' && ch <='9' ) ) 
      x=x*10+ch-'0';
    return x;
}
int dp[2][2000];
int V[10001],Q[100001],L,R;
int Ans_up=1000007,Ans_down=1;
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    N=read(),M=read();
    for(int i=0;i<M;i++)
    {
        int x=read(),y=read();V[i]=read();
        puts(x,y,V[i]),puts(y,x,V[i]);
    }
    S=read(),T=read();
    for(int k=0;k<M;k++)
    {
        memset(dp,0,sizeof(dp));
        L=0,Q[R=1]=S,dp[0][S]=100000007;
        while( L < R )
        {
            int x=Q[++L];
            for(int i=hd[x];i;i=nxt[i])
              if( val[i] > dp[1][to[i]] && val[i] <= V[k] )
              {
                 bool flag=0;
                 if( dp[0][to[i]] < dp[0][x] || !dp[0][to[i]] )
                    dp[0][to[i]]=min(val[i],dp[0][x]),flag=1;
                 if( dp[1][to[i]] < dp[1][x] || !dp[1][to[i]] )
                    dp[1][to[i]]=min(val[i],dp[1][x]),flag=1;
                 if( val[i] == V[k] && ( dp[1][to[i]] < dp[0][x] || !dp[1][to[i]] ) )
                    dp[1][to[i]]=min(val[i],dp[0][x]),flag=1;
                 if( flag ) Q[++R]=to[i];
              } 
        }
        if( dp[1][T] && Ans_up * dp[1][T] > Ans_down * V[k] )
            Ans_up=V[k],Ans_down=dp[1][T];
    }
    if( Ans_up > 1000000 ) printf("IMPOSSIBLE");
    else
    {
        if( !( Ans_up % Ans_down ) ) printf("%d",Ans_up/Ans_down);
        else 
          {
          for(int i=1;i<=Ans_up;i++)
              if( !(Ans_up%i) && !(Ans_down%i) )
                 Ans_up/=i,Ans_down/=i;
          printf("%d/%d",Ans_up,Ans_down);
          }
    }
}

100分代码

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

const int N = (int)1e4;
typedef int arr[N + 10];

int n, m, S, T;
arr ufs;
int bestnum, bestdenom;

struct edge {
    int x, y, w;
}e[N + 10];

int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]); }

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

bool cmp(const edge &a, const edge &b) { return a.w < b.w; }

int main() {
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].w);
    scanf("%d %d", &S, &T);

    sort(e + 1, e + m + 1, cmp);

    bestnum = 30001, bestdenom = 1;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) ufs[j] = j;
        int j = i;
        for ( ; j <= m; ++j) {
            int fx = find(e[j].x), fy = find(e[j].y);
            if (fx != fy) ufs[fx] = fy;
            if (find(S) == find(T)) break;
        }

        if (find(S) == find(T)) {
            if (e[j].w * bestdenom < e[i].w * bestnum)
                bestnum = e[j].w, bestdenom = e[i].w;
        }
    }

    if (bestnum == 30001) printf("IMPOSSIBLE\n");
    else {
        int g = gcd(bestnum, bestdenom);
        bestnum /= g, bestdenom /= g;
        if (bestdenom == 1) printf("%d\n", bestnum);
        else printf("%d/%d\n", bestnum, bestdenom);
    }

    return 0;
}

Problem C. sweet

【题目描述】

有一个小朋友去买糖。商店当中一共有种不同的糖果,其中每一种糖果有两种选择:大糖果和小糖果,各自只有一个,并且各自有一个价格,满足大糖果一定比小糖果贵。对于仼何一种糖果,大糖果给小朋友带来的愉悦程度是2,小糖果给小朋友带来的愉悦程度是1。由于小朋友不太喜欢口味相同的糖果混搭,所以对于一种糖果,他不会同时买大糖果和小糖果。

现在小朋友想要获得p点愉悦程度,但是想花費最少的钱,请你帮帮他。

【输入格式】

第一行两个正整数n和p 接下来n行,每行两个正整数ai和bi,表示第i种糖果小糖果和大糖果的价格。

【输出格式】

第一行输出为了获得点愉悦程度需要的最少花费。

接下来n行,第i行输岀0,1,2中的某一个数,输出0表示不买这一类糖果,输出1表示买小糖果,输出2表示买大糖果。如果有多种最优方案,输出其中一种即可。

【输入输出样例】

【input】

2 3

1 2

1 2

【output】

3

1

2

【input】

5 3

10 20

5 10

10 20

6 9

25 30

【output】

14

0

1

0

2

0

【数据范围】

对于30%的数据,n<10

对于50%的数据,n<1000,1<a<10,100<b<1000

对于10%的数据,n≤20000,ai<bi,p≤2×n,b≤2^31-1

【题解】

10.2清北刷题记

10.2清北刷题记

【代码实现】

30分代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iostream>

#define ri register int
#define ll long long

using namespace std;

inline void read(int &x)
{
    x = 0;
    bool f = 0;
    char ch = getchar();
    while(!isdigit(ch)) f = ch == '-', ch = getchar();
    while(isdigit(ch)) x = (x<<1) + (x<<3) + ch - 48, ch = getchar();
    if(f) x = -x;
}

const int MAXN = 1050;
int n, m, p, v[MAXN][3], dp[MAXN][3][MAXN<<1];

int min(int a, int b, int c)
{
    int ans = a;
    if(b < ans) ans = b;
    if(c < ans) ans = c;
    return ans;
}

bool vis[MAXN][3], ansvis[MAXN][3];
ll ans = 1e18;

void dfs(int x, int res, ll val)
{
//  printf("dfs %d %d %d\n", x, res, val);

    if(x > n)
    {
        if(res == 0 && val == ans)
        {
            for(ri i = 1; i <= n; i++)
            {
                if(vis[i][0]) printf("0\n");
                else if(vis[i][1]) printf("1\n");
                else printf("2\n");
            }
            exit(0);
        }
        return;
    }

    if(val > ans) return;
//  if((n-x+1)*2 < res) return;

    vis[x][1] = 1;
    if(res >= 1 && dp[x][1][p-res+1] == val+1ll*v[x][1]) dfs(x+1, res-1, val+1ll*v[x][1]);
    vis[x][1] = 0;

    vis[x][2] = 1;
    if(res >= 2 && dp[x][2][p-res+2] == val+1ll*v[x][2]) dfs(x+1, res-2, val+1ll*v[x][2]);
    vis[x][2] = 1;

    vis[x][0] = 1;
    if(dp[x][0][p-res] == val) dfs(x+1, res, val);
    vis[x][0] = 0;
}

int main()
{
    freopen("sweet.in", "r", stdin);
    freopen("sweet.out", "w", stdout);
    read(n), read(p);
    for(ri i = 1; i <= n; i++)
        read(v[i][1]), read(v[i][2]);

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;

    for(ri i = 1; i <= n; i++)
        for(ri j = 0; j <= i*2; j++)
        {
            dp[i][0][j] = min(dp[i-1][0][j], dp[i-1][1][j], dp[i-1][2][j]);
            if(j >= 1) dp[i][1][j] = min(dp[i-1][0][j-1], dp[i-1][1][j-1], dp[i-1][2][j-1]) + v[i][1];
            if(j >= 2) dp[i][2][j] = min(dp[i-1][0][j-2], dp[i-1][1][j-2], dp[i-1][2][j-2]) + v[i][2];
        }

    ans = min(dp[n][0][p], dp[n][1][p], dp[n][2][p]);
    printf("%lld\n", ans);

    dfs(1, p, 0);

    return 0;
}

50分代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL N,p,a[210000],b[210000];
LL f[1001][2002];LL pre[1001][2002];
LL read () {
    LL X=0,w=1;char ch=0;
    while(ch<'0'||ch>'9')   { if(ch=='-')   w=-1;ch=getchar(); }
    while(ch>='0'&&ch<='9') { X=(X<<1)+(X<<3)+ch-'0';ch=getchar(); }
    return X*w;
}
inline void dfs (LL N,LL p) {
    if(N==0)
        return ;
    dfs(N-1,p-pre[N][p]);
    cout << pre[N][p] << endl;
}
inline void work () {
    memset(f,0x7f,sizeof(f));
    f[0][0]=0;
    for(LL i=1;i<=N;i++) 
        for(LL j=0;j<=p;j++) {
            if(f[i-1][j]<f[i][j])
                f[i][j]=f[i-1][j],pre[i][j]=0;
            if( j>=1 && f[i-1][j-1]+a[i]<f[i][j])
                f[i][j]=f[i-1][j-1]+a[i],pre[i][j]=1;
            if( j>=2 && f[i-1][j-2]+b[i]<f[i][j])
                f[i][j]=f[i-1][j-2]+b[i],pre[i][j]=2;
        }
    cout << f[N][p] << endl;
    dfs(N,p);
}
int main () {
    freopen("sweet.in","r",stdin);
    freopen("sweet.out","w",stdout);
    N=read();p=read();
    for(LL i=1;i<=N;i++)
        a[i]=read(),b[i]=read();
    work();
    return 0;
}

100分代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#define R "%d"
#define RL "%lld"
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define FOR(x, l, r) for (ll x = (l), end = (r); x <= end; ++x)
#define ROF(x, l, r) for (ll x = (l), end = (r); x >= end; --x)
using namespace std;

typedef int LL;
typedef long long ll;

const LL oo = (LL)2e9;
const ll INF = (ll)1e17;

const LL N = (LL)6e5;
typedef ll arr[N + 10];

struct node {
    ll x, y, z;
}a[N + 10], b[N + 10];

ll i, j, k, p, n, ma, mb, w, ans = INF, cal, mx, mxn, s, prv, prls, prmxn;
arr pr, mi, mip, sa;

bool cmp_a(const node &a, const node &b) { return a.x < b.x; }

bool cmp_b(const node &a, const node &b) { return a.x + a.y < b.x + b.y; }

LL main() {
    freopen("sweet.in", "r", stdin);
    freopen("sweet.out", "w", stdout);
    scanf(RL RL "\n", &n, &w);
    FOR (i, 1, n) {
        scanf(RL RL "\n", &j, &k);
        if (k > 2 * j) a[++ma] = (node){j, i, 1}, a[++ma] = (node){k - j, i, 2};
        else b[++mb] = (node){j, k - j, i};
    }
    sort(a + 1, a + ma + 1, cmp_a), sort(b + 1, b + mb + 1, cmp_b);

    mi[mb + 1] = oo;
    ROF (i, mb, 1)
        if (mi[i + 1] < b[i].x) mi[i] = mi[i + 1], mip[i] = mip[i + 1];
        else mi[i] = b[i].x, mip[i] = i;

    FOR (i, 1, ma) sa[i] = sa[i - 1] + a[i].x;

    FOR (ls, 0, Min(w, mb << 1)) {
        if (ls & 1) {
            p = (ls + 1) >> 1, s += b[p].x + b[p].y;
            if (b[p].y > mx) mx = b[p].y, mxn = p;
            if (w - ls > ma) continue;
            ll go = -1, ck = 0;;
            if (s - mx < s - b[p].x - b[p].y + mi[p + 1]) go = 0, ck = s - mx + sa[w - ls];
            else go = 1, ck = s - b[p].x - b[p].y + mi[p + 1] + sa[w - ls];
            if (ck < ans) {
                ans = ck;
                if (go == 0) {
                    prv = 0, prls = ls, prmxn = mxn;
                }
                else {
                    prv = 1, prls = ls;
                }
            }
        }
        else {
            p = ls >> 1;
            if (w - ls > ma) continue;
            ll ck = s + sa[w - ls];
            if (ck < ans) {
                ans = ck;
                prv = 2, prls = ls;         
            }
        }
    }

    printf(RL "\n", ans);

    p = ((prls & 1) ? (prls + 1) >> 1 : prls >> 1);
    if (prv == 0) {
        FOR (i, 1, p)
            if (i != prmxn) pr[b[i].z] = 2;
            else pr[b[i].z] = 1;
        FOR (i, 1, w - prls) pr[a[i].y] = Max(pr[a[i].y], a[i].z);
    }
    else if (prv == 1) {
        FOR (i, 1, p - 1) pr[b[i].z] = 2;
        pr[b[mip[p + 1]].z] = 1;
        FOR (i, 1, w - prls) pr[a[i].y] = Max(pr[a[i].y], a[i].z);
    }
    else {
        FOR (i, 1, p) pr[b[i].z] = 2;
        FOR (i, 1, w - prls) pr[a[i].y] = Max(pr[a[i].y], a[i].z);
    }

    FOR (i, 1, n) printf(RL "\n", pr[i]);

    return 0;
}

相关推荐