头像

纯纯正能量




离线:2小时前


最近来访(23)
用户头像
川_1
用户头像
一万小时定律
用户头像
陌上花开Charlie
用户头像
Cabin-65--
用户头像
王不语
用户头像
Spare
用户头像
xiayutao
用户头像
DracoMalfoy
用户头像
yxc的接班人
用户头像
晴明
用户头像
Gzm1317
用户头像
Yuet_cy
用户头像
小猪快跑ya
用户头像
AcWing2AK
用户头像
vv._
用户头像
WA_自动机
用户头像
wangyc
用户头像
有马公生
用户头像
Self.
用户头像
2Yan2


线性筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ) // primes[j] <= n / i ===  primes[j] * i < n                                                             
        {
            st[primes[j] * i] = true;  // primes里面的素数,一定比当前的 i 小,我们是用 素数筛其他数。i是素数则i的倍数一定不是素数,此时他的倍数是用比他小的素数充当的素数
            if (i % primes[j] == 0) break; // 当if条件成立是,此时primes[j] 一定是i 的最小因子,每个数只会筛一次,所以是线性的。
        }
    }
}

作者:yxc
链接:https://www.acwing.com/blog/content/406/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。





#include <iostream> // 克鲁斯卡尔,有点无情。
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 100;

int fa[N], s[N];
int n, m;

struct node {
    int x, y, w;
} edge[N];

bool cmp(node a, node b) {
    return a.w < b.w;
}

int find(int x)  // 并查集
{
    return fa[x]==x?x:fa[x]=find(fa[x]);//并查集
}

int main()
{
    int k;
    cin >> k;
    while (k --) {
        cin >> n;
        for (int i = 1; i < n; i ++) {
            int x, y, w;
            cin >> x >> y >> w;
            edge[i] = {x, y, w};
        }

        sort(edge, edge + n, cmp);

        for (int i = 1; i <= n; i ++) {
            fa[i] = i;
            s[i] = 1;
        } 
        // for(int i=1;i<n;i++)
        //     scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
        long long ans = 0;

        for (int i = 1; i < n; i ++) {
            int x = find(edge[i].x), y = find(edge[i].y), w = edge[i].w;
            if (x == y) {
                continue;
            }
            ans += (long long) (s[x] * s[y] - 1) * (w + 1); // 妙;
            fa[x] = y;
            s[y] += s[x];
        }
        cout << ans << endl;
    }
    return 0;
}



C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx; // 见邻接表
int color[N];

void add (int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c, int limit) {
    color[u] = c;

    for (int i = h[u]; ~i; i = ne[i]) {
        if (w[i] <= limit) continue;
        int j = e[i];
        if (color[j]) { // 染过颜色了
            if (color[j] == c) return false;  // 染色相同的话就矛盾了,错误
        } else if (!dfs(j, 3 - c, limit)) return false; // 当前点没有染色,染成另一个颜色,就是相对的集合。
    }
    return true;
}
bool check(int limit) {
    memset(color, 0, sizeof color);

    for (int i = 1; i <= n; i ++) {
        if (color[i] == 0) {
            if (!dfs(i, 1, limit))
                return false;
        }
    }
    return true;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    int l = 0, r = 1e9;
    while (l < r) { 
        int mid = l + r >> 1;
        if (check(mid)) r = mid; // 分析在比mid大的一定满足二分性
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}





数据库创建完成之后需创建 pojo 层 用来解析数据库,中间内容如果 数据库 关键字命名含有下划线,pojo里面采用驼峰命名





API 需要写3个地方 1 controller (contorller 调用 service ) 2 在 service 写一个接口 3 在 service 里面的 impl 写一个具体的接口实现


活动打卡代码 AcWing 3531. 哈夫曼树

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

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

    priority_queue<int, vector<int>, greater<int>> heap;//最小值的优先队列,小根堆,top()返回最小值
    while (n -- ) {             //priority_queue<int> 大根堆
        int x;
        cin >> x;
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1) {
        int x = heap.top();//哈夫曼树的建树方法,每次取最小的两个数先加,再将和加入堆中
        heap.pop();
        int y = heap.top();
        heap.pop();
        int sum = x + y;
        res += sum;//求结果,每次加入sum时,就会把x + y上提一层所以累加到res上
        heap.push(sum);
    }

    cout << res;
    return 0;
}


活动打卡代码 AcWing 3477. 简单排序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

int main() {
    int n;
    set<int> a;
    cin >> n;
    while (n -- ) {
        int x;
        cin >> x;
        a.insert(x);
    }

    for (auto x : a) {
        cout << x << ' ';
    }
    return 0;
}


活动打卡代码 AcWing 3428. 放苹果

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int m, n;
int ans;


int dfs(int u, int sum, int last) { // last 的作用保证组合递增,因为1 5 1 和 1 1 5,
    if (u == n) {                   // 是同一组数据,这样就不用管了。可以自己推一下案例。
        if (sum == 0) {
            return 1;
        }
        return 0;
    }
    int res = 0;
    for (int i = last; i <= sum; i ++) {
        res += dfs(u + 1, sum - i, i);
    }

    return res;
}
int main() {
    while (cin >> m >> n) {
        cout << dfs(0, m, 0) << endl;
    }    
    return 0;
}


活动打卡代码 AcWing 693. 行程排序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>  // 找头节点
#include <unordered_map> // 数组模拟哈西表


using namespace std;

int main()
{
    int T;
    cin >> T;
    for (int cases = 1; cases <= T; cases ++) {
        int n;
        cin >> n;
        unordered_map<string, string> next;
        unordered_set<string> S;

        while (n -- ) {
            string a, b;
            cin >> a >> b;
            next[a] = b;
            S.insert(b);
        }

        string head;
        for (auto [a, b]: next) {
            if (!S.count(a)) {
                head = a;
                break;
            }
        }
        printf("Case #%d: ", cases);

        while(next[head].size()) {
            cout << head << '-' << next[head] << ' ';
            head = next[head];
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3311. 最长算术

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n, T;
int a[200010];//看清开多大数组

int judg() { // 双指针
    int res = 0;
    for (int i = 0; i < n; i ++) {
        int j = i + 2;
        while (j < n && a[j] - a[j - 1] == a[j - 1] - a[j - 2]) // 想等判断
            j ++;
        res = max(res, j - i);
        i = j - 2;  // 画图理解
    }
    return res;
}
int main() {
    cin >> T;
    for (int cases = 1; cases <= T; cases ++) {
        cin >> n;
        for (int i = 0; i < n; i ++) {
            cin >> a[i];
        }

        printf("Case #%d: %d\n", cases, judg());
    }
    return 0;
}