头像

THE_NAMELESS_SPECTRE


访客:1119

离线:4天前


问题 捞贴

RT



题目讨论 AcWing 357. 求助




题目链接 AcWing 357

WA

错误的代码:

#include<bits/stdc++.h>

using namespace std;

struct E
{
    long long v, w, nxt;
};
long long n, m;
vector<long long> TIME;
vector<long long> NEED;
vector<E> edge;
vector<long long> head;
vector<long long> army;
vector<long long> deep;
vector<long long> is_need;
vector<long long> is_rest;
vector<vector<long long> > f;
vector<vector<long long> > dist;
vector<pair<long long, long long> > h;
void add(long long u, long long v, long long w)
{
    edge.push_back({v, w, head[u]});
    head[u] = edge.size() - 1;
}
long long t;
void reset()
{
    TIME.clear();
    NEED.clear();
    h.clear();
}
void resete()
{
    edge.clear();
}
void resetn(long long n)
{
    t = log2(n) + 1;
    head.clear();
    deep.clear();
    f.clear();
    dist.clear();
    is_need.clear();
    is_rest.clear();
    head.resize(2 * n, -1);
    deep.resize(2 * n, 0);
    f.resize(2 * n, vector<long long>(2 * t, 0));
    dist.resize(2 * n, vector<long long>(2 * t, 0));
    is_need.resize(2 * n, 0);
    is_rest.resize(2 * n, 0);
}
void resetm(long long m)
{
    army.clear();
    army.resize(2 * m, 0);
}
queue<long long> q;
void bfs()
{
    q.push(1);
    deep[1] = 1;
    while(q.size())
    {
        long long now = q.front();
        q.pop();
        for(long long i = head[now]; i != -1; i = edge[i].nxt)
        {
            long long y = edge[i].v;
            if(deep[y])
            {
                continue;
            }
            deep[y] = deep[now] + 1;
            f[y][0] = now;
            dist[y][0] = edge[i].w;
            for(long long j = 1; j <= t; j++)
            {
                f[y][j] = f[f[y][j - 1]][j - 1];
                dist[y][j] = dist[y][j - 1] + dist[f[y][j - 1]][j - 1];
            }
            q.push(y);
        }
    }
}
bool dfs(long long x)
{
    bool pson = false;
    if(is_rest[x])
    {
        return true;
    }
    for(long long i = head[x]; i != -1; i = edge[i].nxt)
    {
        long long y = edge[i].v;
        if(deep[y] < deep[x])
        {
            continue;
        }
        pson = true;
        if(!dfs(y))
        {
            return false;
        }
    }
    return pson;
}
bool check(long long limit)
{
    reset();
    for(long long i = 1; i <= m; i++)
    {
        long long x = army[i], cnt = 0;
        for(long long j = t; j >= 0; j--)
        {
            if(f[x][j] > 1 && cnt + dist[x][j] <= limit)
            {
                cnt += dist[x][j];
                x = f[x][j];
            }
        }
        if(f[x][0] == 1 && cnt + dist[x][0] <= limit)
        {
            h.push_back(make_pair(limit - cnt - dist[x][0], x));
        }
        else
        {
            is_rest[x] = 1;
        }
    }
    for(long long i = head[1]; i != -1; i = edge[i].nxt)
    {
        if(!dfs(edge[i].v))
        {
            is_need[edge[i].v] = 1;
        }
    }
    sort(h.begin(), h.end());
    for(long long i = 0; i < h.size(); i++)
    {
        if(is_need[h[i].second] && h[i].first < dist[h[i].second][0])
        {
            is_need[h[i].second] = 0;
        }
        else
        {
            TIME.push_back(h[i].first);
        }
    }
    for(long long i = head[1]; i != -1; i = edge[i].nxt)
    {
        if(is_need[edge[i].v])
        {
            NEED.push_back(dist[edge[i].v][0]);
        }
    }
    if(TIME.size() < NEED.size())
    {
        return false;
    }
    sort(TIME.begin(), TIME.end());
    sort(NEED.begin(), NEED.end());
    long long i = 0, j = 0;
    while(i < NEED.size() && j < TIME.size())
    {
        if(TIME[j] >= NEED[i])
        {
            i++;
            j++;
        }
        else
        {
            j++;
        }
    }
    if(i >= NEED.size())
    {
        return true;
    }
    return false;
}
long long l, r, mid;
void read()
{
    cin >> n;
    reset();
    resete();
    resetn(n);
    for(long long i = 1; i != n; i++)
    {
        long long u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
        r += w;
    }
    bfs();
    cin >> m;
    resetm(m);
    for(long long i = 1; i <= m; i++)
    {
        cin >> army[i];
    }
}
long long ans;
bool flag;
void write()
{
    cout << (flag ? ans : -1) << endl;
}
void solve()
{
    read();
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(check(mid))
        {
            r = mid - 1;
            ans = mid;
            flag = true;
        }
        else
        {
            l = mid + 1;
        }
    }
    write();
}
int main()
{
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}
/*
10
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
5 
2 8 5 4 2 

*/
/*
10
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
5
2 8 5 4 2 

9
*/
/*
50
2 1 284
3 1 2512
4 2 7246
5 4 6989
5 6 5151
7 5 6614
8 2 4101
5 9 4137
10 2 885
11 1 1754
12 6 2967
13 3 6111
14 10 8
10 15 5495
16 9 3887
17 7 1394
18 1 1479
15 19 963
20 15 3508
10 21 1669
22 13 1417
1 23 5185
24 13 6668
9 25 670
26 13 4609
27 6 919
28 11 9106
26 29 8063
30 26 5224
6 31 8273
31 32 5462
8 33 7745
8 34 7206
35 30 4374
36 35 8166
37 11 2307
32 38 3875
20 39 154
40 25 4763
11 41 530
5 42 8429
32 43 5460
40 44 9734
45 29 4937
28 46 3641
25 47 2001
48 29 8348
29 49 9483
42 50 8607
5
30 9 25 37 50 

31271
*/
/*
10
1 2 15606
3 1 2777
4 3 2008
1 5 29898
1 6 31457
7 5 4630
6 8 32496
3 9 27660
10 9 29090
4
9 5 10 3 

56750
*/



话说有一种骚气蓬勃的东西叫作bitset

C++ 代码

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int NumberOf1(int n) {
        bitset<32> u(n);
        return u.count();
    }
};


活动打卡代码 AcWing 99. 激光炸弹

#include<bits/stdc++.h>

using namespace std;

const int N = 5002;

int sum[N][N];

int main()
{
    int n, r;
    cin >> n >> r;
    memset(sum, 0, sizeof(sum));
    while(n--)
    {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        sum[x + 1][y + 1] = v;
    }
    for(int i = 1 ; i < N; i++)
    {
        for(int j = 1 ; j < N ; j++)
        {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    int ans = 0;
    for(int i = 0 ; i + r < N ; i++)
    {
        for(int j = 0 ; j + r < N ; j++)
        {
            ans = max(ans, sum[i + r][j + r] - sum[i + r][j] - sum[i][j + r] + sum[i][j]);
        }
    }
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 164. 可达性统计

#include<bits/stdc++.h>

using namespace std;

int head[60010], ver[60010], nxt[60010];
int in[30010];
int tot, n, m;
vector<int> tp;
queue<int> q;
bitset<30010> bs[30010];
void add(int u, int v)
{
    tot++;
    ver[tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        in[v]++;
    }
    for(int i = 1; i <= n; ++i)
    {
        if(in[i] == 0)
        {
            q.push(i);
        }
    }
    while(q.size())
    {
        int u = q.front();
        q.pop();
        tp.push_back(u);
        int i = head[u];
        while(i)
        {
            int v = ver[i];
            in[v]--;
            if(in[v] == 0)
            {
                q.push(v);
            }
            i = nxt[i];
        }
    }
    for(int i = tp.size() - 1; i >= 0; --i)
    {
        int u = tp[i];
        bs[u][u] = 1;
        for(int j = head[u]; j; j = nxt[j])
        {
            int v = ver[j];
            bs[u] |= bs[v];
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        cout << bs[i].count() << endl;
    }
    return 0;
}


活动打卡代码 AcWing 362. 区间

#include<bits/stdc++.h>

using namespace std;

int n, m, dist[5010], st;
bool f[5010];
queue<int> q;
int tot = 0, lt[5010], ed[15010], len[15010], nxt[15010];
void add_edge(int x, int y, int z)
{
    tot++;
    ed[tot] = y;
    len[tot] = z;
    nxt[tot] = lt[x];
    lt[x] = tot;
}
void spfa(int s)
{
    int i, x, t, y, l;
    for(i = 0; i <= n; i++)
    {
        dist[i] = -2147483647, f[i] = false;
    }
    while(!q.empty())
    {
        q.pop();
    }
    dist[s] = 0;
    f[s] = true;
    q.push(s);
    while(!q.empty())
    {
        x = q.front();
        f[x] = false;
        q.pop();
        t = lt[x];
        while(t)
        {
            y = ed[t];
            if(dist[y] < dist[x] + len[t])
            {
                dist[y] = dist[x] + len[t];
                if(!f[y])
                {
                    q.push(y);
                    f[y] = true;
                }
            }
            t = nxt[t];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    st = n + 1;
    int i, b, e, t;
    for(i = 1; i <= m; i++)
    {
        cin >> b >> e >> t;
        add_edge(b - 1, e, t);
    }
    for(i = 1; i <= n; i++)
    {
        add_edge(i, i - 1, -1);
        add_edge(st, i, 0);
        add_edge(i - 1, i, 0);
    }
    add_edge(st, 0, 0);
    spfa(st);
    cout << dist[n] << endl;
    return 0;
}


活动打卡代码 AcWing 340. 通信线路

#include<bits/stdc++.h>

using namespace std;

int n, p, k;
struct node
{
    int v, w;
    node(int a, int b)
    {
        v = a;
        w = b;
    }
};
vector<vector<node> > head;
vector<int> dist;
vector<bool> visit;
bool check(int max_cost)
{
    for(int i = 1; i <= n; ++i)
    {
        visit[i] = 0;
        dist[i] = (INT_MAX >> 1);
    }
    deque<int> q;
    int cnt = 1, sum = 0;
    q.push_back(1);
    dist[1] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop_front();
        if(dist[u] * cnt > sum)
        {
            q.push_back(u);
            continue;
        }
        visit[u] = 0;
        cnt--, sum -= dist[u];
        for(int i = 0, l = head[u].size(); i < l; ++i)
        {
            int v = head[u][i].v;
            int w = head[u][i].w;
            w = w > max_cost ? 1 : 0;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if(!visit[v])
                {
                    visit[v] = 1;
                    cnt++;
                    sum += dist[v];
                    if(q.empty() || dist[v] < dist[q.front()])
                    {
                        q.push_front(v);
                    }
                    else
                    {
                        q.push_back(v);
                    }
                }
            }
        }
    }
    return dist[n] <= k;
}

int main()
{
    iostream::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin >> n >> p >> k;
    int u, v, w;
    head.resize(n + 1, vector<node>());
    dist.resize(n + 1, 0);
    visit.resize(n + 1, false);
    int left = 0, right = INT_MIN;
    for(int i = 0; i < p; ++i)
    {
        cin >> u >> v >> w;
        head[u].push_back(node(v, w));
        head[v].push_back(node(u, w));
        right = max(right, w);
    }
    int ans = -1, mid;
    while(left <= right)
    {
        mid = (left + right) >> 1;
        if(check(mid))
        {
            ans = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}



活动打卡代码 AcWing 341. 最优贸易

#include<bits/stdc++.h>

using namespace std;

vector<int> e[100005];
int n, m, dp[100005], minw[100005], w[100005];
void dfs(int now, int MIN, int pre)
{
    int flag = 1;
    MIN = min(w[now], MIN);
    if(minw[now] > MIN)
    {
        minw[now] = MIN, flag = 0;
    }
    int MAX = max(dp[pre], w[now] - MIN);
    if(dp[now] < MAX)
    {
        dp[now] = MAX;
        flag = 0;
    }
    if(!flag)
    {
        for(int i = 0; i < e[now].size(); i++)
        {
            dfs(e[now][i], MIN, now);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    memset(minw, 127, sizeof(minw));
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].push_back(y);
        if(z == 2)
        {
            e[y].push_back(x);
        }
    }
    dfs(1, 2147483647, 0);
    cout << dp[n] << endl;
    return 0;
}



//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
#define P 131
#define ATOI(C) (unsigned long long)C-96
#define power(a, b) (power[b])
using namespace std;
typedef unsigned long long ull;
// ull power(ull a, ull b)
// {
//  ull r = 1, base = a;
//  while(b != 0)
//  {
//      if(b & 1)
//      {
//          r *= base;
//      }
//      base = base * base;
//      b >>= 1;
//  }
//  return r;
// }
ull *hmf;
ull *hmb;
ull *power;
ull n;
bool check(ull l, ull r)
{
    return hmf[r] - hmf[l] * power(P, r - l) == hmb[n - l] - hmb[n - r] * power(P, r - l) ? true : false;
}
int main()
{
    iostream::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    string S;
    ull cnt = 1;
    while(cin >> S && S != "END")
    {
        n = S.size();
        hmf = new ull[n + 1];
        hmb = new ull[n + 1];
        power = new ull[n + 1];
        power[0] = 1;
        hmf[0] = 0;
        hmb[0] = 0;
        for(ull i = 1; i <= n; i++)
        {
            hmf[i] = hmf[i - 1] * P + ATOI(S[i - 1]);
            power[i] = power[i - 1] * P;
        }
        //  for(ull i = 0; i <= n; i++)
        //  {
        //      cout << hmf[i] << ' ';
        //  }
        reverse(S.begin(), S.end());
        //  cout << endl;
        for(ull i = 1; i <= n; i++)
        {
            hmb[i] = hmb[i - 1] * P + ATOI(S[i - 1]);
        }
        //  for(ull i = 0; i <= n; i++)
        //  {
        //      cout << hmb[i] << ' ';
        //  }
        reverse(S.begin(), S.end());
        //  cout << endl;
        //  system("pause");
        //  system("cls");
        //  cout << n << endl << S << endl;
        ull maxn = 1;
        for(ull i = 0; i < n; i++)
        {
            ull left = 0, right = min(i, n - 1 - i);
            ull mid = (left + right) >> 1;
            while(left <= right)
            {
                mid = (left + right) >> 1;
                //          cout << "check(" << i - mid << "," << i + mid + 1 << "):" << check(i - mid, i + mid + 1) << endl;
                if(check(i - mid, i + mid + 1))
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            mid = (left + right) >> 1;
            maxn = max(maxn, 2 * mid + 1);
        }
        //  cout << endl;
        for(ull i = 0; i < n - 1; i++)
        {
            if(S[i] == S[i + 1])
            {
                ull left = 0, right = min(i, n - 2 - i);
                ull mid = (left + right) >> 1;
                while(left <= right)
                {
                    mid = (left + right) >> 1;
                    //              cout << "check(" << i - mid << "," << i + mid + 2 << "):" << check(i - mid, i + mid + 2) << endl;
                    if(check(i - mid, i + mid + 2))
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }
                mid = (left + right) >> 1;
                maxn = max(maxn, 2 * mid + 2);
            }
        }
        cout << "Case " << cnt << ": " << maxn << endl;
        delete []hmf;
        delete []hmb;
        cnt++;
    }
}