星殇
1小时前
#include <bits/stdc++.h>
#define PI acos(-1)
#define all(a) (a).begin(), (a).end()
#define erjinzhi(n) __builtin_popcountll(n);
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
//#pragma GCC optimize(2,"Ofast","inline")
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
const char nl = '\n';
const int N = 2e5+10;
LL get_sum(LL x1,LL y1,LL x2,LL y2){
    return (x2-x1)*(y2-y1);
}
int main()
{
    LL x1,y1,x2,y2,x3,y3,x4,y4;
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;

    LL sum1=get_sum(x1,y1,x2,y2)+get_sum(x3,y3,x4,y4);
    LL sum2 = 0;
    LL x_1,y_1,x_2,y_2;
    if(x3<x2&&x4>x1&&y3<y2&&y4>y1){//判断是否有重合部分
        x_1 = max(x1,x3);
        y_1 = max(y1,y3);
        x_2 = min(x2,x4);
        y_2 = min(y2,y4);
        sum2=get_sum(x_1,y_1,x_2,y_2);

        //cout<<x_1<<" "<<y_1<<" "<<x_2<<" "<<y_2<<nl;
    }
    cout<<sum1-sum2;
    return 0;
}


新鲜事 原文

好修为常
1小时前
这个是双链表的知识,我不知道哪里错了,可以帮忙看看吗 题目链接是827题 #include using namespace std; const int N=1e5+10; int r[N],l[N],val[N],keep; void init(){ r[0]=1; l[1]=0; keep=2;//第一个插入的数,角标是2 } void insert_k_r(int k,int x){ val[keep]=x; l[keep]=k; r[keep]=r[k]; l[r[k]]=keep; r[k]=keep; keep++; } void delete_k(int k){ l[r[k]]=l[k]; r[l[k]]=r[k]; } int main(){ init(); int num; cin>>num; while(num--){ string str; int k,x; cin>>str; if(str=="L"){ cin>>x; insert_k_r(0,x); }else if(str=="R"){ cin>>x; insert_k_r(l[1],x); }else if(str=="D"){ delete_k(k+1); }else if(str=="IL"){ cin>>k>>x; insert_k_r(l[k+1],x); }else{ cin>>k>>x; insert_k_r(k+1,x); } } for(int i=r[0];i!=1;i=r[i]) cout<



bukki
1小时前

笔记.png

代码:

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

using namespace std;

const int N=510,M=10010;

int n,m,k;
int dist[N],backup[N];

struct Edge{
    int a,b,w;
}edge[M];

void Bellman_Ford(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;

    for (int i=0;i<k;i++){

        memcpy(backup,dist,sizeof dist);

        for(int j=0;j<m;j++){//m条边
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }

}

int main(){

    cin>>n>>m>>k;

    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        edge[i]={x,y,z};//结构体的赋值
    }

    Bellman_Ford();

    if(dist[n]>0x3f3f3f3f/2) cout<<"impossible"<<endl;//注:不能用-1作为返回值来表示走不到n号点,因为有可能最近的点就是-1,结果被impossible了
    else cout<<dist[n]<<endl;

    return 0;
}

屏幕截图 2023-10-14 163714.png




vanBo
1小时前

题目描述

约翰的农场有 $n$ 个谷仓,编号 $1 \sim n$,谷仓之间有 $m$ 条[HTML_REMOVED]双向[HTML_REMOVED]道路。
所有道路的长度均为 $1$。
奶牛们可以通过这些道路从任意谷仓到达任意其它谷仓。
任意两个谷仓之间最多只包含一条道路(注意是道路,不是路径)。
不存在道路两端都连接同一个谷仓的情况。
农场中一共有 $k$ 种干草,编号 $1 \sim k$。
每个谷仓都存有一种干草,其中第 $i$ 个谷仓存有第 $a_i$ 种干草。
每种干草都至少存在于一个谷仓中。
奶牛们计划选择一个谷仓举办干草宴会。
为了让宴会足够丰盛,至少需要将 $s$ 种不同的干草汇集在宴会谷仓。
宴会谷仓本身就包含一种干草,而其它干草就需要从其它谷仓运输。
已知,将一种干草从一个谷仓运至另一个谷仓所需的运输成本等于两谷仓之间的最短路径距离。
请你帮助奶牛们计算,对于每个谷仓,如果挑选其为宴会举办地,则举办宴会需要付出的总运输成本的最小可能值是多少。

输入格式

第一行包含四个整数 $n,m,k,s$。
第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。
接下来 $m$ 行,每行包含两个整数 $u,v$,表示第 $u$ 个谷仓和第 $v$ 个谷仓之间存在一条双向道路。

输出格式

共一行,输出 $n$ 个整数,其中第 $i$ 个整数表示在第 $i$ 个谷仓举办宴会需要付出的总运输成本的最小可能值。

数据范围

前 $3$ 个测试点满足 $1 \le n \le 10$。
所有测试点满足 $1 \le n \le 10^5$,$0 \le m \le 10^5$,$1 \le s \le k \le \min(n,100)$,$1 \le a_i \le k$,$1 \le u,v \le n$,$u \neq v$。

输入样例1:

5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5

输出样例1:

2 2 2 2 3

输入样例2:

7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7

输出样例2:

1 1 1 2 2 1 1

算法思路

  • 通过多源$BFS$,计算所有节点距离存储甘草编号为$k$的节点的最小距离,该距离用$dist[]$数组来维护,通过依次遍历所有的甘草编号,可以初始化$w[i][j]$,表示节点距离存储甘草$j$的最近距离,题目所求即为此数组$w[][]$,第二维上前$s$个数据的总和
  • 该算法的优化一定程度上取决于排序取出前$s$个数据的快慢,题解$1$使用$sort()$库函数,题解$2$使用快排取数的库函数

$HINT$

  • 原先记录每个节点存储甘草编号的数组$kd[N]$,数组的大小开辟成了$K$,始终评测结果为$WA$,纠结了一整天~
  • 此处使用的是手写队列,调用库中的$queue$,会$TLE$

题解$1$

  • 时间复杂度:$O(nk \log n)$
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e+5 + 10, M = 2 * N, K = 105;

int n, m, k, s;
int h[N], e[M], ne[M], idx;
int w[N][K], dist[N];
int kd[N];
int q[N];

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

void bfs(int id)
{
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++)
    {
        if (kd[i] == id)
        {
            dist[i] = 0;
            q[++ tt] = i;
        }
    }

    while (hh <= tt)
    {
        int u = q[hh ++];
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[u] + 1)
            {
                dist[j] = dist[u] + 1;
                q[++ tt] = j;
            }
        }
    }

    for (int i = 1; i <= n; i ++) w[i][id] = min(w[i][id], dist[i]);
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &s);
    for (int i = 1; i <= n; i ++) scanf("%d", &kd[i]);

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    memset(w, 0x3f, sizeof w);
    for (int i = 1; i <= k; i ++) bfs(i);

    for (int i = 1; i <= n; i ++ ) 
    {
        sort(w[i] + 1, w[i] + k + 1);
        int res = 0;
        for (int j = 1; j <= s; j ++)
            res += w[i][j];
        printf("%d ", res);
    }

    return 0;
}

题解$2$

  • 时间复杂度:$O(nk)$
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e+5 + 10, M = 2 * N, K = 105;

int n, m, k, s;
int h[N], e[M], ne[M], idx;
int w[N][K], dist[N];
int kd[N];
int q[N];

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

void bfs(int id)
{
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++)
    {
        if (kd[i] == id)
        {
            dist[i] = 0;
            q[++ tt] = i;
        }
    }

    while (hh <= tt)
    {
        int u = q[hh ++];
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[u] + 1)
            {
                dist[j] = dist[u] + 1;
                q[++ tt] = j;
            }
        }
    }

    for (int i = 1; i <= n; i ++) w[i][id] = min(w[i][id], dist[i]);
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &s);
    for (int i = 1; i <= n; i ++) scanf("%d", &kd[i]);

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    memset(w, 0x3f, sizeof w);
    for (int i = 1; i <= k; i ++) bfs(i);

    for (int i = 1; i <= n; i ++ ) 
    {
        nth_element(w[i] + 1, w[i] + s, w[i] + k + 1);
        int res = 0;
        for (int j = 1; j <= s; j ++)
            res += w[i][j];
        printf("%d ", res);
    }

    return 0;
}



厄斐琉斯
2小时前

矩阵快速幂

矩阵快速幂算法的思想与整数快速幂算法类似,都是利用了幂的性质来减少计算的次数。对于整数快速幂,我们利用了以下性质:

a^b = a^(b/2) * a^(b/2) (当b为偶数时) a^b = a * a^(b-1) (当b为奇数时)

矩阵快速幂算法也是类似的,但是应用于矩阵的乘法。给定一个矩阵A和一个整数k,我们想要计算A的k次幂,即A^k。矩阵快速幂算法利用了以下性质:

当k为偶数时,A^k = (A^(k/2)) * (A^(k/2))。
当k为奇数时,A^k = A * (A^(k-1))。
算法的基本步骤如下:

如果k为0,返回单位矩阵(任何矩阵乘以单位矩阵都等于它本身)。
如果k为偶数,递归计算A^(k/2),然后将结果平方。
如果k为奇数,先计算A^(k-1),然后将结果与A相乘。
矩阵快速幂算法的时间复杂度是O(log k),因为每次递归都会将幂次减半,直到幂次变为0。
在递归的最底层,当k等于1时,递归将返回A本身,因为任何数(或矩阵)的1次幂都是它本身。然后,在回溯过程中,它会将结果矩阵乘以A,以计算更高次幂的值。

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int>> matrixMultiply(const vector<vector<int>>& A, const vector<vector<int>>& B, int n) {
    vector<vector<int>> C(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

vector<vector<int>> matrixPower(vector<vector<int>>& A, int n, int k) {
    if (k == 1) {
        return A;
    }
    if (k % 2 == 0) {
        vector<vector<int>> halfPower = matrixPower(A, n, k / 2);
        return matrixMultiply(halfPower, halfPower, n);
    } else {
        return matrixMultiply(A, matrixPower(A, n, k - 1), n);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n, vector<int>(n));
    vector<vector<int>> res(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    res = matrixPower(a, n, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

在这个代码中,matrixMultiply函数用于计算两个矩阵的乘积,而matrixPower函数用于递归地计算矩阵的幂。这个算法的时间复杂度是O(log k),因为它将幂次分解为一系列的平方和乘法操作。



新鲜事 原文

传递好运,大家都去理想的公司理想的岗位吧。 我毕业啦。
图片


新鲜事 原文

Hawk_yu
2小时前
https://www.acwing.com/activity/content/introduction/19/group_buy/194945/?from=app_share 蓝桥杯拼团!



jvav选手
2小时前
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取科目数量
        int n = scanner.nextInt();
        // 存储每个科目的成绩
        int[] N = new int[n];
        // 总成绩
        double sum = 0;
        // 修改成绩的科目数量
        int count = 0;
        // 读取每个科目的成绩并计算总成绩
        for (int i = 0; i < n; i++) {
            N[i] = scanner.nextInt();
            sum += N[i];
        }
        // 如果当前四舍五入后的平均分已经达到5,则无需修改,输出0
        if (sum / n + 0.5 >= 5.0) {
            System.out.println(0);
        } else {
            // 对成绩数组进行升序排序
            Arrays.sort(N);
// 遍历成绩数组,依次将每个科目的成绩修改为5,计算修改的科目数量
            for (int i = 0; i < n; i++) {
                int x = 5 - N[i];
                count++;
                sum += x;
        // 如果修改后的平均分达到5,则输出修改的科目数量并结束程序
                if (sum / n + 0.5 >= 5.0) {
                    System.out.println(count);
                    return;
                }
            }
        }
    }
}



新鲜事 原文

说谎家
2小时前
新的一年,新学期,新的开始 (ง •̀_•́)ง加油
图片



题目是:

https://www.acwing.com/problem/content/1233/


第一种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间当日h2时m2分s2秒降落。

第二种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间次日h2时m2分s2秒降落。

第三种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间第三日h2时m2分s2秒降落。

一开始对这个当地时间有疑惑,不知道每种格式的第一个当地时间是起飞地的当地时间,降落时的降落时间不清楚是起飞地的还是目的地的。
这时可以看测试用例计算解除疑惑。

输入有时有 (+1)有时没有,这时用scanf

scanf("%d(+%d)%d", &a, &b, &c);
 对于空白字符:空格、tab、回车等,scanf将忽略输入字符串的空白字符,
    直到下一个非空白字符,(并回放该非空白字符),
    若该非空白字符与格式化字符串匹配,则读入(例如:scanf("%d(+%d)%d", &a, &b, &c) 若输入1(+2)3则可以读入)
    若该非空白字符与格式化字符串不匹配,则结束此次读取,
    并将该非空白字符回存到缓存中,在下一次读取函数被调用时读取(如scanf、getchar等)

或者sscanf()

`
int get_time()
{
string line;
getline(cin, line);
//保持一致:
if (line.back() != ‘)’) line += “(+0)”;
//把字符串中的数字信息读入到变量之中
int h1, m1, s1, h2, m2, s2, d;
sscanf(line.c_str(), “%d:%d:%d %d:%d:%d (+%d)”, &h1, &m1, &s1, &h2, &m2, &s2, &d);

return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;

}
`