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】

【input】

7 6

1 2

1 6

2 5

3 1

4 7

2 4

【output】

【数据范围】

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

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

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

【题解】

10.2清北刷题记-LMLPHP

【代码实现】

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】

【数据范围】

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

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

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

【题解】

10.2清北刷题记-LMLPHP

【代码实现】

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

【output】

【input】

5 3

10 20

5 10

10 20

6 9

25 30

【output】

【数据范围】

对于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清北刷题记-LMLPHP

【代码实现】

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;
}

小蜜蜂

10.2清北刷题记

10.2 Morning

Problem A. distance

【题目描述】

【输入描述】

【输出描述】

【输入输出样例】

【数据范围】

【题解】

【代码实现】

Problem B. graph

【题目描述】

【输入描述】

【输出描述】

【输入输出样例】

【数据范围】

【题解】

【代码实现】

Problem C. sweet

【题目描述】

【输入格式】

【输出格式】

【输入输出样例】

【数据范围】

【题解】

【代码实现】