头像

Crisp

历经万般红尘劫,犹如凉风轻拂面。




离线:9小时前


活动打卡代码 AcWing 2069. 网络分析

Crisp
8天前

只通过70p的数据

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 10010;
int root[N];
ll ans[N];
int findRoot(int x) {
    if(x == root[x]) {
        return x;
    }
    else {
        root[x] = findRoot(root[x]);
        return root[x];
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    int t, a, b;
    for(int i = 1; i <= n; i ++ ) root[i] = i;
    for(int i = 0; i < m; i ++ ) {
        scanf("%d%d%d", &t, &a, &b);
        if(t == 1) {
            if(a == b) continue;
            int roota = findRoot(a);
            root[roota] = findRoot(b);
        } else {
            int op = findRoot(a);
            for(int i = 1; i <= n; i ++ ) {
                if(findRoot(i) == op) {
                    ans[i] += 1ll * b;
                }
            }
        }
    }
    for(int i = 1; i <= n; i ++ ) {
        printf("%lld ", ans[i]);
    } 
    return 0;
}



活动打卡代码 AcWing 2068. 整数拼接

Crisp
8天前
#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 100010;
ll f[11][N], a[N], mul[11];
int main() {
    int n;
    ll k;
    mul[0] = 1;
    for(int i = 1; i < 11; i ++ ) mul[i] = (mul[i - 1] * 10)%k;

    scanf("%d%lld", &n, &k);
    for(int i = 0; i < n; i ++ ) {
        scanf("%lld", &a[i]);
        for(int j = 0; j < 11; j ++ ) {
            f[j][((a[i]%k) * mul[j]) % k] ++ ;
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i ++ ) {
        ll op = a[i];
        int cnt = 0;
        while(op > 0) {
            op /= 10;
            cnt ++ ;
        }
        if( ((a[i] % k) * mul[cnt] + a[i] % k ) % k == 0 ) ans -- ;
        ll x = ((k - a[i]%k) + k)%k;
        //if(x == k) x = 0;
        ans += f[cnt][x];
    }
    printf("%lld", ans);
    return 0;
}



Crisp
9天前

题目链接 acwing 2068

倒数第七行代码

cout << x << endl;

为什么加上这一行,会出现浮点错误

错误的代码:

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 100010;
ll f[11][N], a[N], mul[11];
int main() {
    int n;
    ll k;
    mul[0] = 1;
    for(int i = 1; i < 11; i ++ ) mul[i] = (mul[i - 1] * 10) % k;

    scanf("%d%lld", &n, &k);
    for(int i = 0; i < n; i ++ ) {
        scanf("%lld", &a[i]);
        for(int j = 1; j < 11; j ++ ) {
            f[j][(a[i] * mul[j])%k] ++ ;
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i ++ ) {
        ll op = a[i];
        int cnt = 0;
        while(op > 0) {
            op /= 10;
            cnt ++ ;
        }
        if( ((a[i] % k) * mul[cnt] + a[i] ) % k == 0 ) ans -- ;
        ll x = k - a[i]%k;
        cout << x << endl;
        if(x == k) x = 0;
        ans += f[cnt][x];
    }
    printf("%lld", ans);
    return 0;
}




Crisp
12天前
import java.util.*;
import java.io.*;
class Main {
    static int n;
    static int[] rcd = new int[10];
    static boolean[] st = new boolean[10];
    static Scanner cin = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void dfs(int u) throws IOException{
        if(u == n + 1) {
            for(int i = 1; i <= n; i ++ ) {
                out.write(rcd[i] + " ");
            }
            out.write("\n");
            return;
        }
        for(int i = 1; i <= n; i ++ ) {
            if(!st[i]) {
                st[i] = true;
                rcd[u] = i;
                dfs(u + 1);
                st[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        n = cin.nextInt();
        dfs(1);
        out.flush();
    }
}



Crisp
12天前

先选,然后不选,可以实现高位从低到高,以实现字典序

import java.util.*;

class Main {
    static int a, b;
    static boolean[] st = new boolean[30];
    public static void dfs(int x, int u) {
        if(u == b) {
            for(int i = 1; i <= a; i ++ ) {
                if(st[i])
                    System.out.print(i + " ");
            }
            System.out.println();
            return;
        }
        if(x > a) return;
        st[x] = true;
        dfs(x + 1, u + 1);
        st[x] = false;
        dfs(x + 1, u);
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        a = cin.nextInt();
        b = cin.nextInt();
        dfs(1, 0);
    }
}


活动打卡代码 LeetCode 142. 环形链表 II

Crisp
12天前
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
         if(head == null) return null;
        ListNode p = head;
        HashSet<ListNode> hashSet = new HashSet<>();
        while( true ) {
            if(hashSet.contains(p)) {
                return p;
            }
            hashSet.add(p);
            if(p.next == null) {
                break;
            }
            p = p.next;
        }
        return null;
    }
}


活动打卡代码 LeetCode 141. 环形链表

Crisp
12天前

学了一手HashSet的基本使用,nice

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode p = head;
        int i = 0, ans = -1;
        HashSet<ListNode> hashSet = new HashSet<>();
        while( true ) {
            if(hashSet.contains(p)) {
                ans = i;
                break;
            }
            i ++ ; 
            hashSet.add(p);
            if(p.next == null) {
                break;
            }
            p = p.next;
        }
        if(ans == -1) return false;
        else return true;
    }
}



Crisp
12天前

Java – 普通模拟

class Solution {
    public static String add(char bsc, char bhd, char ne, String ans, int x) {
        if(x == 4) {
            ans += bhd;
            ans += bsc;
        }
        else if(x == 9) {
            ans += ne;
            ans += bsc;
        }
        else {
            for(int i = 0; i < x%5; i ++ ) {
                ans += bsc;
            }
            if(x >= 5) {
                ans += bhd;
            }
        }
        return ans;
    }
    public static String intToRoman(int num) {
        int bi = 0;
        String ans = "";
        while(num > 0) {
            int op = num % 10;
            num /= 10;
            if(bi == 0) {
                ans = add('I', 'V', 'X', ans, op);
            }
            else if(bi == 1) {
                ans = add('X', 'L', 'C', ans, op);
            }
            else if(bi == 2) {
                ans = add('C', 'D', 'M', ans, op);
            }
            else {
                for(int i = 0; i < op; i ++ ) {
                    ans += "M";
                }
            }
            bi ++ ;
        }
        StringBuffer s = new StringBuffer(ans);
        return s.reverse().toString();
    }
}



Crisp
12天前

双指针

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, ans = 0;
        while(l < r) {
            ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
            int x = (height[l] < height[r]) ? l ++ : r -- ;
        }
        return ans;
    }
}


活动打卡代码 AcWing 342. 道路与航线

Crisp
14天前

spfa使用slf优化,但不知道为啥加上lll会wa

#pragma GCC optimize(2) 
#include<deque>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 25010, M = 150010;
int t, r, p, s, idx, h[N], dis[N], val[M], e[M], ne[M];
bool st[N];
void add(int x, int y, int z) {
    e[++ idx] = y;
    ne[idx] = h[x];
    h[x] = idx;
    val[idx] = z;
}
void spfa() {
    memset(st, false, sizeof st);
    memset(dis, 0x3f, sizeof dis);
    deque<int> q;
    q.push_front(s);
    st[s] = true;
    dis[s] = 0;
    while(!q.empty()) {
        int op = q.front();
        st[op] = false;
        q.pop_front();
        for(int i = h[op]; i != -1; i = ne[i]) {
            int j = e[i];
            int cnt = dis[op] + val[i];
            if(dis[j] > cnt) {
                dis[j] = cnt;
                if(st[j]) continue;
                if(q.size() && dis[j] < dis[q.front()]) {
                    q.push_front(j);
                } else {
                    q.push_back(j);
                }
                st[j] = true;
            }
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> t >> r >> p >> s;
    int x, y, z;
    for(int i = 0; i < r; i ++ ) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    for(int i = 0; i < p; i ++ ) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    spfa();
    for(int i = 1; i <= t; i ++ ) {
        if(dis[i] == INF) puts("NO PATH");
        else {
            printf("%d\n", dis[i]);
        }
    }
    return 0;
}