头像

ylimhs

重庆工程学院




离线:5小时前


活动打卡代码 AcWing 903. 昂贵的聘礼

ylimhs
11小时前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int w[N][N];
int dist[N];
bool st[N];
int level[N];//纪录等级
int m , n ;


/*
建立虚拟源点 跑一边dijkstra();
*/

int dijkstra(int down, int up)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[0] = 0 ;

    for(int i = 1;  i <=n + 1 ; i ++)
    {
        int t = - 1;
        for(int j = 0 ;  j <= n ; j ++)
          if(!st[j] && (t== -1 || dist[t] > dist[j]))
          t = j ;

          st[t] = true;

          for(int j = 1 ; j <= n ; j ++)
           if(level[j] >= down &&level[j] <= up)
             dist[j] = min(dist[j] , dist[t] + w[t][j]);
    }
    return dist[1];
}
int main()
{
    cin >> m >> n ;

    memset(w,0x3f,sizeof w);
    for(int i = 1; i <= n ; i ++) w[i][i] = 0 ;

    for(int i = 1; i <= n ; i ++)
    {
        int price , cnt;
        cin >> price >> level[i] >> cnt;
        w[0][i] = min(price,w[0][i]);
        while(cnt--)
        {
            int id , cost;
            cin >> id >> cost;
            w[id][i] = min(cost,w[id][i]);
        }
    }
    int res = 0x3f3f3f3f;
    for(int i = 0; i <=level[1] ; i ++) res = min(res, dijkstra(i,i+m)) ;
    cout << res ;


    return 0 ;
}


活动打卡代码 AcWing 920. 最优乘车

ylimhs
11小时前
#include <iostream>
#include <sstream>
#include <memory.h>
#include <queue>

using namespace std;

const int N = 510;

int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5
输出样例:
2
*/
int g[N][N];
int dist[N];
bool st[N];

int dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }

        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }

        st[t] = true;
    }

    return dist[n];
}


int main()
{
    cin >> m >> n;
    memset(g, 0x3f, sizeof g);
    string line;
    getline(cin, line);
    while (m--) {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p;

        //每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
        for (int i = 0; i < cnt; i++) {
            for (int j = i + 1; j < cnt; j++) {
                g[stop[i]][stop[j]] = 1;
            }
        }
    }

    int ret = dij();


    if ( ret > 0x3f3f3f3f/2) cout << "NO" << endl;
    else cout << ret-1 << endl;

    return 0;
}




活动打卡代码 AcWing 240. 食物链

ylimhs
22小时前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N  = 50010;
int p[N],d[N];
int n , k ;

int find(int x){
    if(p[x] != x)
    {
        int root = find(p[x]);
        d[x]+=d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int main()
{
    cin >> n >> k;

    for(int i = 1; i <= n ; i ++) p[i] = i ;

    int res  = 0 ;
    while(k--)
    {
       int D ,x , y ;
       cin >> D >> x >> y;

       if(x > n || y > n) res ++ ;
       else 
       {
           int px = find(x),py = find(y);
           if(D == 1)
           {
               if( px == py && (d[x] - d[y] )% 3) res ++;
               else if(px != py)
                   {
                       p[px] = py;
                       d[px] = d[y]-d[x];
                   }

           }else
           {
               if(px == py && (d[x] - d[y] -1) %3)res ++;
               else
               {
                   if(px != py)
                   {
                       p[px]=py;
                       d[px] = d[y]- d[x] + 1;
                   }
               }
           }
       }


    }
    cout << res << endl;

    return 0 ;

}


活动打卡代码 AcWing 1126. 最小花费

ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2010,M=2010;;
double g[N][N];
double dist[N];
bool state[N];
int n , m ;

void dijkstra(int x)
{
    //memset(dist,-0x3f,sizeof dist);
    dist[x] = 1 ;
     for(int i = 1; i <= n ; i ++)
     {
         int t = - 1;
         for(int j = 1; j <= n ; j ++)
         if(!state[j] && (t==-1 || dist[t] < dist[j]))
         t= j ;

         state[t] = true;

         for(int j = 1; j <= n ; j ++)
           dist[j] = max(dist[j],dist[t] * g[t][j]);
     }

}

int main()
{
    cin  >> n >> m ;
    memset(g,-0x3f,sizeof g);
    while(m--)
    {
        int a,b;
        int c;
        cin >> a>>b >> c;
        g[a][b] = g[b][a] =max(g[a][b],(100.0-c) / 100);

    }

    int s,f;
    cin >> s>>f;
      dijkstra(s);
    printf("%.8lf",100 / dist[f]);


    return 0 ;
}


活动打卡代码 AcWing 1128. 信使

ylimhs
1天前
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 20010;
int dist[N];
bool st[N];
int n , m;
int h[N],e[N],w[N],idx,ne[N];
void add(int a, int b , int c)
{
    e[idx] = b, ne[idx] = h[a],w[idx] = c , h[a] = idx ++;
}


int dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    memset(dist,0x3f,sizeof dist);
    heap.push({0,1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.y,distance = t.x;
        //cout << ver << endl;
        if(st[ver])  continue;
        st[ver] = true;

        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i ++)
    {
        if(dist[i]==0x3f3f3f3f) return -1;
        res = max(res,dist[i]);

    }
    return res;

}


int main()
{

    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin >> a>>b >> c;
        add(a,b,c),add(b,a,c);
    }
    cout << dijkstra() << endl;

    return 0 ;
}


活动打卡代码 AcWing 1129. 热浪

ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2550;

int dist[N];
bool state[N];
int g[N][N];
int n,C,s,f;

int dijkstra(int start)
{
    memset(dist,0x3f,sizeof dist);
    dist[start] = 0;
    state[start] = false;
    for(int i = 1 ; i < n ; i ++)
    {
        int t = - 1;
        for(int j = 1; j <= n ; j ++)
         if(!state[j] && (t == -1 || dist[t] > dist[j]))
         t =j;
         state[t] = true;
         for(int j = 1; j <= n ; j ++)
           dist[j] = min (dist[j] , dist[t] + g[t][j]);
    }
    return dist[f];
}


int main()
{
   cin >> n>> C >> s >>f;

    memset(g,0x3f,sizeof g);

    while(C--)
    {
        int a, b ,c;
        cin >> a >> b >>c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }

    cout << dijkstra(s) << endl;

    return 0 ;
}



ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
typedef long long LL;
struct Node{
    int l ,r;
    LL sum , add;
}tr[N * 4];
int n,m ;
int w[N];

void pushup(int u )
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void eval(Node &u, LL add)
{
    u.sum = (LL)(u.sum + (u.r - u.l + 1) * add);
    u.add +=add;
}

void pushdown(int u )
{
    eval(tr[u<<1],tr[u].add);
    eval(tr[u<<1|1],tr[u].add);
    tr[u].add = 0;
}
void build(int u , int l , int r)
{
    if( l  == r)
    {
        tr[u] = {l,r,w[r],0};
    }
    else
    {
        tr[u] = {l,r};
        int mid = l+ r>>1;
        build(u << 1, l , mid), build (u << 1| 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u ,int l ,int r ,LL add)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        eval(tr[u],add);
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid ) modify(u << 1, l , r , add);
        if(r > mid)modify(u<<1 | 1, l , r, add);
        pushup(u);
        }
}

LL query(int u ,int l ,int r)
{
    if(tr[u].l >= l  && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = 0;
        if(l <= mid) res = (LL)(res + query(u << 1 , l , r));
        if(r > mid) res = (LL)(res + query(u<<1 | 1, l , r));
        return res;
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n ; i ++)cin>>w[i];
    build(1,1,n);

    while(m--)
    {
        char op[2];
        int l ,r ,d;
        scanf("%s%d%d",op,&l,&r);
        if(*op == 'Q')
        {

            printf("%lld\n",query(1,l,r));
        }
        else
        {
            cin >> d;
            modify(1,l,r,d);
        }
    }


    return 0 ;
}




ylimhs
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;

struct Node{
    int l ,r ;
    LL sum,add;//懒标记
}tr[N * 4];
int n ,m;
int w[N];
void pushup(int u )
{
    tr[u].sum = tr[u<<1].sum + tr[u << 1 | 1].sum;
}
void eval(Node &u , LL add)
{
    u.sum = (LL)(u.sum + (u.r - u.l + 1) * add);
    u.add = u.add + add;
}
void pushdown(int u)
{
    eval(tr[u<<1] , tr[u].add);
    eval(tr[u<<1 |1 ] , tr[u].add);
    tr[u].add = 0;

}

void build(int u , int l ,int r)
{
    if(l == r)
    {
        tr[u] = {l,r,w[r],0};
    }
    else
    {
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u<<1 , l , mid ) , build(u<<1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u ,int l, int r , int add)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        eval(tr[u],add);
    }
    else
    {

        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1 , l , r, add);
        if(r > mid) modify(u<<1|1, l , r, add);
        pushup(u);
    }
}

LL query(int u , int l)
{
    if(tr[u].l == l && tr[u].r == l )
    {
        return tr[u].sum ;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = 0 ;
        if(l <= mid)res +=query(u<<1 , l);
        if(l > mid)res +=query(u<<1 | 1, l);

        return res;
    }
}

int main()
{
    cin >> n >> m ;
    for(int i =1 ; i <= n;  i++) cin >> w[i];

    build(1,1,n);


    while(m--)
    {
        char op[2];
        int l ,r ,d;
        scanf("%s%d",op,&l);
        if(*op == 'Q')
        {
             printf("%lld\n", query(1, l));
        }
        else
        {
            cin >> r >>d ;
            modify(1,l,r,d);
        }
    }


    return 0;
}



活动打卡代码 AcWing 241. 楼兰图腾

ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2000100;
int tr[N * 2];
int w[N];
int n ;
int lower[N],Greater[N];//記錄小和大

int lowbit(int x)
{
    return x & -x;
}

void add(int x , int v)
{
    for(int i = x ;i <= n ; i +=lowbit(i))
    {
        tr[i] +=v;
    }
}

LL sum(int x)
{
    LL res = 0;
    for(int i = x; i  ; i -=lowbit(i))
    res +=tr[i];
    return res;
}

int main()
{
    cin >> n ;

    for(int i = 1; i <=n ; i++) cin >> w[i];

    for(int i = 1; i <=  n ;i ++)
    {
        int y = w[i];
        lower[i] = sum(y-1);
        Greater[i] = sum(n)-sum(y);//总共的减去小=的数 就是大于

        add(y,1);
    }

    memset(tr,0,sizeof tr);

     LL resv = 0 , resa = 0;

    for(int i = n ; i ; i --)
    {
        int  y  = w[i];

        resa += lower[i]*sum(y-1);
        resv += Greater[i] * (sum(n) - sum(y));
        add(y,1);

    }

    printf("%lld %lld", resv,resa);
    return 0 ;
}



ylimhs
2天前
#include <iostream>

using namespace  std;
const int N = 1e6 + 10;
int p[N];
int Size[N];
int find(int x) 
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n , m;
    cin >> n>> m ;
    for(int i = 1; i <= n; i++)
    {
        p[i] = i;
        Size[i] = 1;
    }
    while(m--)
    {
       string op;
        int a, b;
       cin >> op;
        if(op == "C")
        {
            cin >>a >>b;

            int pa = find(a),pb = find(b);
            if(pa != pb)
            {
            p[pa]=pb;
            Size[pb]+=Size[pa];

            }

        }
        else if(op =="Q1")
        {
            cin >>a>>b;
             int pa = find(a),pb = find(b);
            if(pa == pb)puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << Size[find(a)]<<endl;
        }
    }
    return 0;


}