Znzryb's Blog
0%

Posted on Edited on

题目大意

给定一个有向带权图（NN 点 MM 边），求从源点 ss 到所有其他点的最短路径长度。数据范围较大（Nle105,Mle2times105N le 10^5, M le 2 times 10^5），需要 O(Mlog⁡N)O(M \log N) 级别的算法（如堆优化 Dijkstra）。

AC代码

Compare函数/类的使用

注意，priority_queue的比较操作符与sort，set是反的

参考题解：https://www.luogu.com.cn/problem/solution/P4779

其实总结来讲就是使用堆然后找到dis值最小的点，将其确认为确定点（已经固定了，dis值不太可能再更新了）

https://www.luogu.com.cn/record/181960419

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#include <queue>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e5+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s,vis[N];
struct cmp {
    bool operator () (pair<ll,ll> a,pair<ll,ll> b){
        if(a.second!=b.second)
            return a.second>b.second;
    }
};
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,cmp> heap;
inline void dijkstra() {
    dis[s]=0;
    heap.push(make_pair(s,0));
    while(!heap.empty()) {
        ll cn=heap.top().first,cdis=heap.top().second;  // priority_queue 需要使用.top()访问队首
        heap.pop();
        if(vis[cn])
            continue;
        vis[cn]=true;dis[cn]=cdis;                      // vis 是用来判断是不是已经确定dis的点
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            heap.push(make_pair(ni,cdis+wi));
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
//AC https://www.luogu.com.cn/record/181960419

心路历程（WA，TLE，MLE……）

未经堆优化的算法（其实不是Dijkstra）TLE

https://www.luogu.com.cn/record/181877100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e5+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s;
deque<pair<ll,ll> > q;
void dijkstra() {
    dis[s]=0;
    q.push_back(make_pair(s,0)); // curr_node curr_dis
    while(!q.empty()) {
        ll cn=q.front().first,cdis=q.front().second;
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            if(cdis+wi<dis[ni]) {
                dis[ni]=cdis+wi;
                q.push_back(make_pair(ni,cdis+wi));
            }
        }
        q.pop_front();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/181877100

Posted on Edited on

题目大意

给定一个有向带权图（NN 点 MM 边），求从源点 ss 到所有其他点的最短路径长度。如果无法到达则输出特定值（如 231−12^{31} - 1）。数据范围较小，允许 O(NM)O(NM) 算法。

AC代码

https://www.luogu.com.cn/problem/P3371

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e4+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s;
deque<pair<ll,ll> > q;
void dijkstra() {
    dis[s]=0;
    q.push_back(make_pair(s,0)); // curr_node curr_dis
    while(!q.empty()) {
        ll cn=q.front().first,cdis=q.front().second;
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            if(cdis+wi<dis[ni]) {
                dis[ni]=cdis+wi;
                q.push_back(make_pair(ni,cdis+wi));
            }
        }
        q.pop_front();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/181870206

第一次提交就基本AC了，没啥心路历程

Posted on Edited on

题目大意

给定一个字符串 SS，求有多少个三元组 (i,j,k)(i, j, k) 满足 1≤i<j<k≤∣S∣1 \le i < j < k \le |S| 且 Si=SkS_i = S_k。

AC代码与思路

image

可以想办法简化这个的计算(用前缀和)

比较具象化的就是这个

image

然后就AC了，记得开long long

AC https://atcoder.jp/contests/abc375/submissions/58758528

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans=0;
long long sum[30],cnt[30];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        int idx=s[i]-'A';
        ans+=(i*cnt[idx]-sum[idx]-cnt[idx]);
        sum[idx]+=i;
        cnt[idx]++;
    }
    cout<<ans<<endl;
    return 0;
}

心路历程（其他超时代码）

我写的逻辑简单但超时代码

https://atcoder.jp/contests/abc375/submissions/58745887

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
string s;
long long ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if(s[i]==s[j])
                ans+=j-i-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}
//TLE https://atcoder.jp/contests/abc375/submissions/58745887

优化了一下，现在只TLE 4个点了

https://atcoder.jp/contests/abc375/submissions/58746864

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans;
map<char,vector<int> > a;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        a[s[i]].push_back(i);
    }
    for(map<char,vector<int> >::iterator it=a.begin();it!=a.end();it++) {
        vector<int> temp=it->second;
        for(int i=0;i<temp.size();i++) {
            for(int j=i+1;j<temp.size();j++)
                ans+=temp[j]-temp[i]-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}
//TLE https://atcoder.jp/contests/abc375/submissions/58746864

AI的AC代码：

https://atcoder.jp/contests/abc375/submissions/58722299

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

long long count_palindromic_triples(const string &S) {
    int n = S.size();

    // 左侧和右侧字符频率计数
    unordered_map<char, long long> left_count, right_count;

    // 初始化所有字符都在右侧
    for (char c : S) {
        right_count[c]++;
    }

    long long result = 0;

    // 遍历每一个可能的中间字符
    for (int j = 0; j < n; ++j) {
        char middle_char = S[j];

        // 把当前的中间字符从右侧移到左侧
        right_count[middle_char]--;

        // 统计左右侧相同字符的三元组个数
        for (const auto& pair : left_count) {
            char char_in_left = pair.first;
            result += left_count[char_in_left] * right_count[char_in_left];
        }

        // 将当前中间字符添加到左侧计数
        left_count[middle_char]++;
    }

    return result;
}

int main() {
    string S;
    cin >> S;

    cout << count_palindromic_triples(S) << endl;

    return 0;
}

算法优化了，但WA了6个点

https://atcoder.jp/contests/abc375/submissions/58757772

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans;
int sum[30],cnt[30];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        int idx=s[i]-'A';
        ans+=i*cnt[idx]-sum[idx]-cnt[idx];
        sum[idx]+=i;
        cnt[idx]+=1;
    }
    cout<<ans<<endl;
    return 0;
}

我说怎么会没过，原来是没开long long

Posted on Edited on

题目大意

给定一个 N×NN \times N 的网格字符矩阵。对于每个 ii (1leileN/21 le i le N/2)，将以 (i,i)(i, i) 为左上角、(N+1−i,N+1−i)(N+1-i, N+1-i) 为右下角的正方形区域顺时针旋转 90 度。求最终的网格状态。

image

这题其实纯模拟是做不出来的，需要一些小的优化技巧（如上图）

更加具象化一点是这样

image

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
typedef long long ll;
const int N=3010;
int n;
char g[N][N],ans[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            int d=min(min(n+1-i,i),min(n+1-j,j));   // 即从该点到最近边框的距离
            int x=i,y=j;
            for(int _=1;_<=(d%4);_++) {
                int xi=y,yj=n+1-x;
                x=xi,y=yj;
            }
            ans[x][y]=g[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cout<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}
// AC https://atcoder.jp/contests/abc375/submissions/58737053

纯模拟的TLE代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long ll;
const int N=3010;
int n;
char g[N][N],ans[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    }
    for(int i=1;i<=n/2;i++) {
        for(int x=i;x<=n+1-i;x++) {
            for(int y=i;y<=n+1-i;y++) {
                ans[y][n+1-x]=g[x][y];
            }
        }
        for(int x=i;x<=n+1-i;x++) {
            for(int y=i;y<=n+1-i;y++) {
                g[y][n+1-x]=ans[y][n+1-x];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            putchar(g[i][j]);
        }
        putchar('\n');
    }
    return 0;
}
// https://atcoder.jp/contests/abc375/submissions/58711404

Posted on Edited on

题目大意

给定一个图，边有权值。在节点上每经过 k 条边必须休息一次（或者说每走 k 步必须停顿）。求从起点到终点的最短时间（或路径权值和），考虑休息带来的限制/代价。

AC代码

参考了官方题解思路，就是在分层图上跑最短路

image

相比于TLE代码，只加了个这个优化

while(!q.empty() && dist[n+1]==INF)

如果dist[n+1]已经确定，那就不用再跑了。

然后代码实现上有比较多的细节，主要是在初始化方面，比如说vis[i][0]也要清理什么的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// https://ac.nowcoder.com/acm/contest/91355/D
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll N=2e5+10,INF=1e18+7;
ll T,n,m,k,a[N],u,v,dist[N];
vector<ll> e[N];
bool vis[N][11];
struct edge {
    ll node,dis,nrest; // nrest 为多久没休息了
};
struct cmp {
    bool operator()(edge a,edge b) {
        if(a.dis!=b.dis)
            return a.dis>b.dis;
        return a.node<b.node;
    }
};
priority_queue<edge,vector<edge>,cmp > q;
edge make_edge(ll node,ll dis,ll nrest) {
    edge temp;
    temp.node=node;temp.dis=dis;temp.nrest=nrest;
    return temp;
}
void dijkstra(int t) {
    q.push(make_edge(1,0,0));
    while(!q.empty() && dist[n+1]==INF) {
        ll node=q.top().node,dis=q.top().dis,nrest=q.top().nrest;
        q.pop();
        if(vis[node][nrest])    // 之前访问过，弹出
            continue;
        vis[node][nrest]=true;
        dist[node]=min(dis,dist[node]);
        for(int i=0;i<e[node].size();i++) {
            if(nrest>=k)
                q.push(make_edge(e[node][i],dis+a[node],0));
            else {
                q.push(make_edge(e[node][i],dis+a[node],0));
                q.push(make_edge(e[node][i],dis+1,nrest+1));
            }
        }
    }
}
void clear() {
    priority_queue<edge,vector<edge>,cmp > empty;
    swap(empty,q);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int _=1;_<=T;_++) {
        cin>>n>>m>>k;
        clear();
        for(int i=1;i<=n+1;i++)
            e[i].clear();
        for(int i=1;i<=n;i++) {
            cin>>a[i];
        }
        fill(&dist[1],&dist[n+2],INF);
        for(int i=1;i<=n+1;i++)
            for(int j=0;j<=k;j++)
                vis[i][j]=false;
        for(int i=1;i<=m;i++) {
            cin>>u>>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        e[n].push_back(n+1);
        e[n+1].push_back(n);
        dijkstra(_);
        cout<<dist[n+1]<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128029
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128343

心路历程（WA，TLE，MLE……）

过了40% TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128029

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// https://ac.nowcoder.com/acm/contest/91355/D
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll N=2e5+10,INF=1e18+7;
ll T,n,m,k,a[N],u,v,dist[N];
vector<ll> e[N];
bool vis[N][11];
struct edge {
    ll node,dis,nrest; // nrest 为多久没休息了
};
struct cmp {
    bool operator()(edge a,edge b) {
        if(a.dis!=b.dis)
            return a.dis>b.dis;
        return a.node<b.node;
    }
};
priority_queue<edge,vector<edge>,cmp > q;
edge make_edge(ll node,ll dis,ll nrest) {
    edge temp;
    temp.node=node;temp.dis=dis;temp.nrest=nrest;
    return temp;
}
void dijkstra(int t) {
    q.push(make_edge(1,0,0));
    while(!q.empty()) {
        ll node=q.top().node,dis=q.top().dis,nrest=q.top().nrest;
        q.pop();
        if(vis[node][nrest])    // 之前访问过，弹出
            continue;
        vis[node][nrest]=true;
        dist[node]=min(dis,dist[node]);
        for(int i=0;i<e[node].size();i++) {
            if(nrest>=k)
                q.push(make_edge(e[node][i],dis+a[node],0));
            else {
                q.push(make_edge(e[node][i],dis+a[node],0));
                q.push(make_edge(e[node][i],dis+1,nrest+1));
            }
        }
    }
}
void clear() {
    priority_queue<edge,vector<edge>,cmp > empty;
    swap(empty,q);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int _=1;_<=T;_++) {
        cin>>n>>m>>k;
        clear();
        for(int i=1;i<=n+1;i++)
            e[i].clear();
        for(int i=1;i<=n;i++) {
            cin>>a[i];
        }
        fill(&dist[1],&dist[n+2],INF);
        for(int i=1;i<=n+1;i++)
            for(int j=0;j<=k;j++)
                vis[i][j]=false;
        for(int i=1;i<=m;i++) {
            cin>>u>>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        e[n].push_back(n+1);
        e[n+1].push_back(n);
        dijkstra(_);
        cout<<dist[n+1]<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128029