头像

TYTY


访客:1274

离线:10小时前



TYTY
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

#include<iostream>
#include<cstring>

using namespace std;


const int  N = 510;
int q[N][N];
int dist[N];
bool st[N];
int n, m;


int dijkstra(){
    memset(&dist, 0x3f3f3f3f, sizeof dist);
    dist[1] =0;



    for(int i =0; i < n-1; i++){
        int t = -1;
        for(int j =1; j <= n; j++){
            if(!st[j] && ( t==-1 || dist[t] > dist[j])){
                t = j;
            }
        }

        if(t == n) break;

        for(int k =1; k <= n; k++){
            dist[k] = min(dist[k], dist[t] + q[t][k]);
        }

        st[t] = true;
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}



int main(){
    scanf("%d%d", &n, &m);

    memset(&q, 0x3f3f3f3f, sizeof q);

    while(m--){
        int a, b, w;
        cin >> a >> b >> w;
        q[a][b] = min(q[a][b], w);
    }

    printf("%d\n", dijkstra());

    return 0;
}



TYTY
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

const int N = 1e5 +10;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];

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

bool topsort(int n ){
    int hh =0, tt = -1;

    for(int i =1; i < n ; i++){
        if(!d[i]){
            q[++tt] =i;
        }
    }

    while(hh <= tt){
        int k = q[hh++];
        for(int i= h[k]; i!= -1; i = ne[i]){
            int j = e[i];
            if( -- d[j] == 0){
                q[++tt] = j;
            }
        }
    }

    return tt == n-1;
}



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

    memset(h, -1, sizeof h);

    while(m--){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b]++;
    }



    if(!topsort(n)) cout << "-1";
    else{
        for(int i =0; i < n; i++){
            printf("%d ", q[i]);
        }
    }
    return 0;
}



TYTY
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

class Solution {
public:
    int numTrees(int n) {
        vector<int>f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = 0;
            for (int j = 1; j <= i; j ++ )
                f[i] += f[j - 1] * f[i - j];
        }
        return f[n];
    }
};


活动打卡代码 LeetCode 93. 复原IP地址

TYTY
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

class Solution {
private:
    vector<string> res;

public:
    vector<string> restoreIpAddresses(string s) {
        string ip;
        helper(s, 0, ip);
        return res;
    }
    void helper(string s, int n, string ip) {
        if (n == 4) {
            if (s.empty()) res.push_back(ip); 
        }
        else {
            for (int k = 1; k < 4; ++k) {
                if (s.size() < k) break;
                int val = stoi(s.substr(0, k));
                if (val > 255 || k != std::to_string(val).size()) continue;
                helper(s.substr(k), n + 1, ip + s.substr(0, k) + (n == 3 ? "" : "."));
            }
        }
        return;
    }

};


活动打卡代码 LeetCode 87. 扰乱字符串

TYTY
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1 == s2) return true;
        string bs1 = s1, bs2 = s2;
        sort(bs1.begin(), bs1.end()), sort(bs2.begin(), bs2.end());
        if(bs1 != bs2) return false;
        int n = s2.size();

        for(int i =1; i<n; i++){
            if(isScramble(s1.substr(i), s2.substr(i)) && isScramble(s1.substr(0, i), s2.substr(0, i))) return true;
            if(isScramble(s1.substr(0, i), s2.substr(n-i)) && isScramble(s1.substr(i), s2.substr(0, n-i))) return true;

        }

        return false;       
    }
};



TYTY
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

#include<iostream>

using namespace std;


int count1(int x){
    int res =0;
    //for(int i =x; i; i -= i & -i) res++;

    while(x){
        res += x&1;
        x >>=1;
    }

    return res;
}

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

    while(n--){
        int k;
        cin >> k;
        printf("%d ", count1(k));
    }

    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

TYTY
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

#include<iostream>

using namespace std;


const int N = 1010;

int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x1][y2+1] -=c;
    b[x2+1][y1] -=c;
    b[x2+1][y2+1] += c;
}

int main(){
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);

    for(int i =1; i <= n ; i++){
        for(int j =1; j <= m ; j++){
            scanf("%d", &a[i][j]);
        }
    }

    for(int i =1; i <= n ; i++){
        for(int j =1; j <= m ; j++){
            insert(i,j,i,j,a[i][j]);
        }
    }

    while(q--){
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;

}


活动打卡代码 AcWing 797. 差分

TYTY
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

#include<iostream>

using namespace std;

const int N = 100010;
int b[N];
void insert(int l, int r, int k){
    b[l] +=k;
    b[r+1] -=k;
}

int main(){
    int n, m;
    scanf("%d%d", &n , &m);
    for(int i =1; i<=n ; i++){
        int k;
        scanf("%d", &k);
        insert(i,i,k);
    }

    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        insert(a, b, c);
    }

    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;

}


活动打卡代码 AcWing 796. 子矩阵的和

TYTY
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1010;

int q[N][N], a[N][N];


int main(){
    int n, m, quary;
    cin >> n >> m >> quary;
    for(int i=0; i < n ; i ++){
        for(int j =0; j < m ; j ++){
            scanf("%d", &q[i][j]);
        }
    }
    memset(&a, 0 , sizeof a);

    for(int i =1; i <= n ; i ++){
        for(int j =1; j <= m ; j++){
            a[i][j] = a[i-1][j] + a[i][j-1] + q[i-1][j-1] - a[i-1][j-1];
        }
    }


    while(quary--){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2>> y2;

        cout << a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1] << endl;
    }


    return 0;
}



活动打卡代码 AcWing 795. 前缀和

TYTY
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

#include<iostream>

using namespace std;

const int N = 100010;

int q[N];

int main(){

    int n, m;
    cin >> n >> m ;

    for(int i =0; i < n ; i++) scanf("%d", &q[i]);

    for(int i =1; i < n ; i++) q[i] += q[i-1];

    while(m){
        int l, r;
        cin >> l >> r;
        cout << q[r-1] - q[l-1-1] << endl;
        m--;

    }

    return 0;
}