1 条题解

  • 0
    @ 2023-11-26 16:32:49

    代码质量不高,但是思路有的。

    C++代码,__int128(NOIP新标准)。

    #include <bits/stdc++.h>
    #define int unsigned __int128           //高精度.
    using namespace std;
    const int N = 1e5 + 5;
    
    void put(int x) {                       //高精度输出.
        if(x < 10) {putchar(x + '0'); return;} 
        else {put(x / 10); putchar(x % 10 + '0');}
    }
    int read() {                            //高精度输入.
        int x = 0;
        char ch = getchar();
        while(ch < '0' || ch > '9') ch = getchar();
        while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
        return x;
    }
    
    int n, m, dr[N], book[N];
    int gcd(int x, int y) {                 //最大公约数,用以给分数约分.
        if(y == 0) return x;
        return gcd(y, x % y);   
    }
    
    struct valuex {                         //分数相关处理.
        int p, q;
        void putin(int x, int y) {p = x; q = y;}    //赋值.
        void putout() {put(p); putchar(' '); put(q);}   //输出.
        
        valuex makenew() {                  //约分.
            int px, qx; px = p; qx = q;
            int tmp = gcd(qx, px);  
            qx /= tmp;  px /= tmp;
            return (valuex){px, qx};
        }
        valuex add(valuex x, valuex y) {   //分数相加.     
            int px, qx; 
            qx = x.q * y.q;
            px = x.p * y.q + y.p * x.q;
            valuex tmp = (valuex){px, qx};
            tmp = tmp.makenew();
            return tmp;
        }
        valuex doso(valuex a, int x)    {   //分数乘某个数.
            q *= x;
            return makenew();
        }   
        valuex getin(){return (valuex){p, q};}  //得到值,基本没用.
    } nox[N];
    
    vector<int> e[N];           //vector存储图.
    int que[N];             //队列,拓扑部分.
    
    signed main() {                             //主函数.
        n = read(); m = read(); //读入.
        for(int i = 1, dt; i <= n; i++) {
            dt = read();
            for(int j = 1, to; j <= dt; j++) {
                to = read();
                e[i].push_back(to);
                dr[to]++;
            }
        }
        
        int head = 0, tail = 0;                 //找起始点.
        for(int i = 1; i <= n; i++) 
            if(dr[i] == 0)  que[++tail] = i;
        
        for(int i = head; i <= tail; i++)   nox[que[i]].putin(1, 1);
        while(head < tail) {
            head++;
            valuex temp = nox[que[head]].getin();
            valuex tmp = temp.doso(temp, e[que[head]].size());  
            for(int i = 0; i < e[que[head]].size(); i++) {
                int to = e[que[head]][i];
                dr[to]--;
                if(!dr[to]) que[++tail] = to;
                if(!book[to]) {
                    nox[to] = tmp;
                    book[to] = 1;
                }   
                else nox[to] = tmp.add(tmp, nox[to]);
            } 
        }
        
        for(int i = 1; i <= n; i++)         //没有通出节点,处理,输出.
            if(e[i].size() == 0) {
                nox[i].putout();
                printf("\n");
            }   
        return 0;
    }
    
    
  • 1

[NOIP2020 提高组] 排水系统

信息

ID
1005
难度
8
分类
高精度 | 拓扑排序图结构 点击显示
标签
递交数
6
已通过
2
通过率
33%
上传者