牛客寒假算法基础集训营3

using namespace std;
typedef long long LL;
const LL maxn = 2e5+5;
const LL inf = 1e15;
LL T, n, m, x, y, z, cnz, jffzr, indeg1[maxn], indeg2[maxn], tot1, tot2, dist1[maxn], dist2[maxn];
struct {
    LL to, val;
    EDGE(LL to, LL w) : to(to), val(w) {}
};
vector<EDGE> edge1[maxn], edge2[maxn];
queue<LL> que;
inline LL read(){
    LL x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
LL cnz_topsrot(LL s) {
    while(!que.empty()) que.pop();
    for(LL i = 1; i <= n; ++i)
        if(indeg1[i] == 0) que.push(i);
    dist1[s] = 0LL;
    while(!que.empty()) {
        LL u = que.front(); que.pop();
        for(LL j = 0; j < edge1[u].size(); ++j) {
            LL v = edge1[u][j].to, w = edge1[u][j].val;
            dist1[v] = min(dist1[v], dist1[u] + w);
            if(--indeg1[v] == 0) que.push(v);
        }
    }
    return max(0LL, dist1[n]); 
}
LL jffzr_topsrot(LL s) {
    while(!que.empty()) que.pop();
    for(LL i = 1; i <= n; ++i)
        if(indeg2[i] == 0) que.push(i);
    dist2[s] = 0LL;
    while(!que.empty()) {
        LL u = que.front(); que.pop();
        for(LL j = 0; j < edge2[u].size(); ++j) {
            LL v = edge2[u][j].to, w = edge2[u][j].val;
            dist2[v] = min(dist2[v], dist2[u] + w);
            if(--indeg2[v] == 0) que.push(v);
        }
    }
    return max(0LL, dist2[n]);
}
int main(){
    T = read();
    while(T--) {
        n = read(), m = read();
        memset(indeg1, 0, sizeof(indeg1));
        memset(indeg2, 0, sizeof(indeg2));
        for(LL i = 0; i <= n; ++i) edge1[i].clear(), edge2[i].clear(), dist1[i] = dist2[i] = inf;
        while(m--) {
            x = read(), y = read(), z = read(), cnz = read(), jffzr = read();
            edge1[x].push_back(EDGE(y, z - cnz));
            edge2[x].push_back(EDGE(y, z - jffzr));
            indeg1[y]++, indeg2[y]++;
        }
        tot1 = cnz_topsrot(1LL);
        tot2 = jffzr_topsrot(1LL);
        if(tot1 == tot2) printf("oof!!!n");
        else if(tot1 < tot2) printf("cnznb!!!n%lldn", tot2 - tot1);
        else printf("rip!!!n%lldn", tot1 - tot2);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200005;
int n, x, a[maxn];
int main() {
    while(cin >> n) {
        memset(a, 0, sizeof(a));
        for(int i = 1; i < n; ++i) cin >> x, a[x] = 1;
        for(int i = 1; i <= n; ++i)
            if(!a[i]){cout << i << endl; break;}
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
int n; LL ans, sum;
struct node{LL a, b;} nod[maxn];
bool cmp(node x, node y) { 
    return x.b * y.a > y.b * x.a;
}
int main() {
    while(cin >> n){
        sum = ans = 0;
        for(int i = 0; i < n;++i) cin >> nod[i].a >> nod[i].b, sum += nod[i].b;
        sort(nod, nod + n,cmp);
        for(int i = 0; i < n; ++i) {
            sum -= nod[i].b;
            ans += sum * nod[i].a;
        }
        cout << ans << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T, n, m, ans, cnt;
int main() {
    while(cin >> T){
        while(T--){
            cin >> n >> m; ///行：m，列：n
            if(m & 1) ans = m - 1 + m * (n - 1) - 1;
            else ans = m - 1 + (m - 1) * (n - 1) - 1 ;
            cout << ans << endl;
        }
    }
    return 0;
}

using namespace std;
typedef long long LL;
LL n, m, dp[20][2], d[20];
LL dfs(int pos, bool if6, bool limit){ ///第pos位、当前数字是否含6：if6、当前数位的上一位是否为上界：limit。
    if(!pos) return 1;
    if(!limit && dp[pos][if6] != -1) return dp[pos][if6];
    LL up = limit ? d[pos] : 9, ans = 0;
    for(LL i = 0; i <= up; ++i) {
        if(i == 6) continue;
        ans += dfs(pos-1, false, limit && i == up);
    }
    return limit ? ans : (dp[pos][if6] = ans);
}
LL solve(LL x){
    memset(d, 0, sizeof(d));
    int len = 0;
    while(x) d[++len] = x % 10, x /= 10;
    return dfs(len, false, true);
}
int main(){
    memset(dp,-1,sizeof(dp));
    while(~scanf("%lld%lld", &n, &m)){
        printf("%lldn", (m - solve(m)) - (n - 1 - solve(n-1)));
    }
    return 0;
}

using namespace std;
typedef long long LL;
LL n, m, dp[20][10], dit[20];
void init() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1LL;
    for(int i = 1; i < 20; ++i) {
        for(int j = 0; j < 10; ++ j) {
            if(j == 6) continue;
            for(int k = 0; k < 10; ++k) {
                if(k == 6) continue;
                dp[i][j] += dp[i - 1][k];
            }
        }
    }
}
LL solve(LL x) {
    memset(dit, 0, sizeof(dit));
    int len = 0; LL ans = 0;
    while(x) {
        dit[++len] = x % 10;
        x /= 10;
    }
    for(int i = len; i >= 1; --i) {
        for(int j = 0; j < dit[i]; ++j) {
            if(j == 6) continue;
            ans += dp[i][j];
        }
        if(dit[i] == 6) break;
    }
    return ans;
}
int main(){
    init();
    while(cin >> n >> m) {
        cout << (m + 1) - solve(m + 1) - (n - solve(n)) <<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T; string str;
int main() {
    while(cin >> T){
        while(T--) {
            cin >> str;
            cout << "cnznb" << endl;
        }
    }
    return 0;
}