头像

qiao




离线:1分钟前


最近来访(17)
用户头像
RyanMoriarty
用户头像
所見即我
用户头像
封禁用户
用户头像
好好好
用户头像
kumo
用户头像
Lucky_1002
用户头像
阿兔
用户头像
123go
用户头像
zmy
用户头像
刷刷刷算法
用户头像
平欢
用户头像
oyas
用户头像
sola选手心态良好
用户头像
FeoBay
用户头像
箫骋


qiao
1小时前

反证法:
步骤:想要证明P
(1)证明!p为F(!P与事实矛盾)
(2)所以p为T,证毕

证明:P为F(P与事实矛盾)
只需找出一种与事实相反具体情况,
就能证明P为F
(要证明P为T则需要P的全部情况均为T,
而要证明P为F则仅需要P的一种情况为F即可)

14E9ACAB53A9A3388A33C655E46357B8.png

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

struct Node
{
    int id, w;
};

vector<Node> g[N];//邻接表
int dist[N];//当前点到某点的距离
int n;

void dfs(int u, int f, int d)
{
    dist[u] = d;
    for (auto x : g[u])//遍历邻接表(g[u]之外的结点是当前结点不能一次到达的结点)
    {
        if (x.id != f)dfs(x.id, u, d+x.w);
    }
}

LL f(int len)
{
    return 10 * len + (1LL + len) * len / 2;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n-1; i++)
    {
        int p, q, d; scanf("%d%d%d", &p, &q, &d);
        g[p].push_back({ q,d });
        g[q].push_back({ p,d });
        //无向图
    }

    //找到树直径的a端点
    dfs(1, -1, 0);

    int a = 1;
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] > dist[a])a = i;
    }

    dfs(a, -1, 0);

    //找到树直径的b端点
    int b = 1;
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] > dist[b])b = i;
    }

    int len = dist[b];//因为第二次dfs是以a为起点
    //所以dist[b]的含义是a到b的距离

    printf("%lld", f(len));

}


活动打卡代码 AcWing 1207. 大臣的旅费

qiao
2小时前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

struct Node
{
    int id, w;
};

vector<Node> g[N];
int dist[N];
int n;

void dfs(int u, int f, int d)
{
    dist[u] = d;
    for (auto x : g[u])
    {
        if (x.id != f)dfs(x.id, u, d+x.w);
    }
}

LL f(int len)
{
    return 10 * len + (1 + (LL)len) * len / 2;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n-1; i++)
    {
        int p, q, d; scanf("%d%d%d", &p, &q, &d);
        g[p].push_back({ q,d });
        g[q].push_back({ p,d });
    }

    dfs(1, -1, 0);

    int y = 1;
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] > dist[y])y = i;
    }

    dfs(y, -1, 0);

    for (int i = 1; i <= n; i++)
    {
        if (dist[i] > dist[y])y = i;
    }

    int len = dist[y];

    printf("%lld", f(len));

}



qiao
22小时前

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
char g[N][N][N];
int dir[6][3] = { 1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1 };
int n, m, l;
int t[N][N][N];

struct Node
{
    int x,y,z;
    bool equals(Node n)
    {
        int res = 1;
        if (x != n.x || y != n.y || z != n.z)res = 0;
        return res;
    }
};

bool check(Node node)
{
    if (node.x >= 0 && node.x < m && node.y >= 0 && node.y < l && node.z >= 0 && node.z < n && g[node.z][node.x][node.y] != '#')return true;
    else return false;
}

void bfs(Node s, Node e)
{
    memset(t, -1, sizeof(t));
    queue<Node> q;
    q.push(s); t[s.z][s.x][s.y] = 0;

    while (q.size())
    {
        auto u = q.front(); q.pop();
        for (int i = 0; i < 6; i++)
        {
            Node n = { u.x + dir[i][0] ,u.y+dir[i][1],u.z+dir[i][2]};
            if (t[n.z][n.x][n.y] == -1 && check(n))
            {
                t[n.z][n.x][n.y] = t[u.z][u.x][u.y] + 1;
                if (n.equals(e))return;
                q.push(n);
            }
        }
    }

}

int main()
{
    while (cin >> n >> m >> l, n || m || l)
    {
        Node s, e;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                scanf("%s", g[i][j]);
                for (int k = 0; k < l; k++)
                {
                    if (g[i][j][k] == 'S') s = { j, k, i };
                    if (g[i][j][k] == 'E') e = { j, k, i };
                }
            }
        }

        bfs(s, e);

        if (t[e.z][e.x][e.y] != -1)printf("Escaped in %d minute(s).\n", t[e.z][e.x][e.y]);
        else cout << "Trapped!" << endl;
    }

}


活动打卡代码 AcWing 1096. 地牢大师

qiao
22小时前
#include<bits/stdc++.h>
using namespace std;

const int N = 105;
char g[N][N][N];
int dir[6][3] = { 1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1 };
int n, m, l;
int t[N][N][N];

struct Node
{
    int x,y,z;
    bool equals(Node n)
    {
        int res = 1;
        if (x != n.x || y != n.y || z != n.z)res = 0;
        return res;
    }
};

bool check(Node node)
{
    if (node.x >= 0 && node.x < m && node.y >= 0 && node.y < l && node.z >= 0 && node.z < n && g[node.z][node.x][node.y] != '#')return true;
    else return false;
}

void bfs(Node s, Node e)
{
    memset(t, -1, sizeof(t));
    queue<Node> q;
    q.push(s); t[s.z][s.x][s.y] = 0;

    while (q.size())
    {
        auto u = q.front(); q.pop();
        for (int i = 0; i < 6; i++)
        {
            Node n = { u.x + dir[i][0] ,u.y+dir[i][1],u.z+dir[i][2]};
            if (t[n.z][n.x][n.y] == -1 && check(n))
            {
                t[n.z][n.x][n.y] = t[u.z][u.x][u.y] + 1;
                if (n.equals(e))return;
                q.push(n);
            }
        }
    }

}

int main()
{
    while (cin >> n >> m >> l, n || m || l)
    {
        Node s, e;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                scanf("%s", g[i][j]);
                for (int k = 0; k < l; k++)
                {
                    if (g[i][j][k] == 'S') s = { j, k, i };
                    if (g[i][j][k] == 'E') e = { j, k, i };
                }
            }
        }

        bfs(s, e);

        if (t[e.z][e.x][e.y] != -1)printf("Escaped in %d minute(s).\n", t[e.z][e.x][e.y]);
        else cout << "Trapped!" << endl;
    }

}



qiao
23小时前

CB974ADA1D96EF6A61FD48E07C673C76.png

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
//0.5e5*1e5=5e9 所以极端条件下一定会爆int
const int N = 1e5 + 10;
int n;
int tr[N];
int ans=1;

//返回该层的sum
LL sum(int l, int r)
{
    LL sum = 0;
    for (int i = l; i <= r && i <= n; i++)sum += tr[i];
    //注意:i<=n 保证最后一层不会数组越界
    return sum;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &tr[i]);

    LL MAX = sum(1, 1), t;
    //数的最大深度为:log(n+1)的上取整即ceil(log(n+1)/log(2))
    for (int i = 2; i <= ceil(log(n+1)/log(2)); i++)
    {
        t = sum(pow(2, i - 1), pow(2, i) - 1);
        if (t > MAX)
        {
            ans = i;MAX = t;
        }
    }
    cout << ans;
}



qiao
23小时前
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n;
int tr[N];
int ans=1;

LL sum(int l, int r)
{
    LL sum = 0;
    for (int i = l; i <= r && i <= n; i++)sum += tr[i];
    return sum;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &tr[i]);

    LL MAX = sum(1, 1), t;
    for (int i = 2; i <= ceil(log(n+1)/log(2)); i++)
    {
        t = sum(pow(2, i - 1), pow(2, i) - 1);
        if (t > MAX)
        {
            ans = i;
            MAX = t;
        }
    }

    cout << ans;
}



qiao
1天前

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define x first 
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10;

PII logs[N];
int vis[N];
int cnt[N];

int main()
{
    int n, d, k; cin >> n >> d >> k;
    for (int i = 0; i < n; i++)
    {
        int ts,id; scanf("%d%d",&ts,&id);
        logs[i] = { ts,id };
    }
    sort(logs, logs + n);

    for (int i = 0, j = 0; j < n; j++)
    {
        int id = logs[j].y;
        cnt[id]++;
        //通过双指针优化至O(n)
        //当区间大于题意时:减去最左侧区间直至符合题意
        while (logs[j].x - logs[i].x + 1 > d)
        {
            cnt[logs[i].y]--;
            i++;
        }
        if (cnt[id] >= k)vis[id] = 1;
        //O(n^2)做法
    /*  for (int j = i; j < n; j++)
        {
            if (logs[j].x - logs[i].x + 1 > d)break;
            if (logs[j].y == id)
            {
                cnt++;
                if (cnt >= k)vis[logs[i].y] = 1;
            }
        }*/
    }
    for (int i = 0; i <= 100000; i++)if (vis[i])printf("%d\n", i);
}



qiao
1天前

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;

const int N = 25;
char g[N][N];
int n, m;
int cnt;
int dir[4][2] = { 1,0,-1,0,0,-1,0,1 };
int vis[N][N];

bool check(int x, int y)
{
    if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')return true;
    else return false;
}

int dfs(PII s)
{
    int cnt = 1;
    for (int i = 0; i < 4; i++)
    {
        int xx = s.x + dir[i][0];
        int yy = s.y + dir[i][1];
        if (!vis[xx][yy] && check(xx, yy))
        {
            vis[xx][yy] = 1;
            cnt += dfs({ xx,yy });
        }
    }
    return cnt;
}

int main()
{
    PII s;
    while (true)
    {
        cin >> m >> n; if (m == 0 && n == 0)return 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", g[i]);
            for (int j = 0; j < m; j++)if (g[i][j] == '@')s = { i,j };
        }

        memset(vis, 0, sizeof(vis));
        cout << dfs(s) << endl;
    }



}


活动打卡代码 AcWing 1113. 红与黑

qiao
1天前
#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;

const int N = 25;
char g[N][N];
int n, m;
int cnt;
int dir[4][2] = { 1,0,-1,0,0,-1,0,1 };
int vis[N][N];

bool check(int x, int y)
{
    if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')return true;
    else return false;
}

void bfs(PII s)
{
    queue<PII> q;
    q.push(s); cnt = 1;

    while (q.size())
    {
        auto t = q.front(); q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = t.x + dir[i][0];
            int yy = t.y + dir[i][1];
            if (!vis[xx][yy]&&check(xx,yy))
            {
                cnt++;
                vis[xx][yy] = 1;
                q.push({ xx,yy });
            }
        }
    }
}

int main()
{
    PII s;
    while (true)
    {
        cin >> m >> n; if (m == 0 && n == 0)return 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", g[i]);
            for (int j = 0; j < m; j++)if (g[i][j] == '@')s = { i,j };
        }

        memset(vis, 0, sizeof(vis));
        bfs(s);
        cout << cnt << endl;
    }



}



qiao
1天前

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;

const int N = 25;
char g[N][N];
int n, m;
int cnt;
int dir[4][2] = { 1,0,-1,0,0,-1,0,1 };
int vis[N][N];

bool check(int x, int y)
{
    if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')return true;
    else return false;
}

void bfs(PII s)
{
    queue<PII> q;
    q.push(s); cnt = 1;

    while (q.size())
    {
        auto t = q.front(); q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = t.x + dir[i][0];
            int yy = t.y + dir[i][1];
            if (!vis[xx][yy]&&check(xx,yy))
            {
                cnt++;
                vis[xx][yy] = 1;
                q.push({ xx,yy });
            }
        }
    }
}

int main()
{
    PII s;
    while (true)
    {
        cin >> m >> n; if (m == 0 && n == 0)return 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", g[i]);
            for (int j = 0; j < m; j++)if (g[i][j] == '@')s = { i,j };
        }

        memset(vis, 0, sizeof(vis));
        bfs(s);
        cout << cnt << endl;
    }



}