ACM

近日刷题记录

AtCoder

ABC371C Make Isomorphic

给你简单的无向图 $G$ 和 $H$ ，每个图都有 $N$ 个顶点：顶点 $1$ 、 $2$ 、 $\ldots$ 、 $N$ 。图 $G$ 有 $M_G$ 条边，其第 $i$ 条边 $(1\leq i\leq M_G)$ 连接顶点 $u_i$ 和 $v_i$ 。图 $H$ 有 $M_H$ 条边，它的第 $i$ 条边 $(1\leq i\leq M_H)$ 连接顶点 $a_i$ 和 $b_i$ 。

您可以在图 $H$ 上执行以下操作，次数不限，可能为零。

选择一对满足 $1\le i<j\leq N$ 的整数 $(i,j)$ 。支付 $A_{i,j}$ 点成本，如果 $H$ 中的顶点 $i$ 和 $j$ 之间没有边，则添加一条；如果有，则删除。

求使 $G$ 和 $H$ 同构所需的最小总成本。

因为 $n<=8$ 所以可以直接暴力，遍历 $h$ 图的每一种与 $g$ 图的对应方式

 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N = 1e3 + 7, mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    bool g[N][N], h[N][N];
    memset(g, false, sizeof(g));
    memset(h, false, sizeof(h));
    int mg, mh;
    cin >> mg;
    for (int i = 0; i < mg; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = true;
    }
    cin >> mh;
    for (int i = 0; i < mh; i++) {
        int u, v;
        cin >> u >> v;
        h[u][v] = h[v][u] = true;
    }
    int cost[N][N];
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> cost[i][j];
            cost[j][i] = cost[i][j];
        }
    }
    int p[n + 1];
    for (int i = 1; i <= n; i++) p[i] = i;
    int ans = 1e9;
    do {
        int tmp = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (g[i][j] ^ h[p[i]][p[j]]) tmp += cost[p[i]][p[j]];
            }
        }
        ans = min(ans, tmp);
    } while (next_permutation(p + 1, p + 1 + n));
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

ABC371E I Hate Sigma Problems

记录每一个数相同的数上次出现的位置，即可得到其对答案作出的贡献

 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;

int n;
vector<int>a(N),nxt(N),last(N);

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll sum=0,cnt=0;
    map<int,int>vis;
    for(int i=1;i<=n;i++){
        if(!vis[a[i]]){
            vis[a[i]]=1;
            cnt++;
        }
        sum+=cnt;
        nxt[last[a[i]]]=i;
        last[a[i]]=i;
    }
    ll ans=sum;
    for(int i=1;i<=n;i++){
        int t=nxt[i];
        if(!t)t=n+1;
        sum-=t-i;
        ans+=sum;
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

ABC373D Hidden Weights

You are given a directed graph with $N$ vertices and $M$ edges. The $j$-th directed edge goes from vertex $u_j$ to vertex $v_j$ and has a weight of $w_j$.

Find one way to write an integer between $-10^{18}$ and $10^{18}$, inclusive, to each vertex such that the following condition is satisfied.

  • Let $x_i$ be the value written on vertex $i$. For all edges $j=1,2,\dots,M$, it holds that $x_{v_j} - x_{u_j} = w_j$.

It is guaranteed that at least one such assignment exists for the given input.

加边时，加双向边，权值相反，接着直接对某个点开始跑 $bfs$

 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;

ll n,m;
struct Node{
    int v,w;
};
vector<Node>edge[N];
ll ans[N],vis[N];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,-w});
    }
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        queue<int>q;
        q.push(i);
        vis[i]=1;
        while(!q.empty()){
            int u=q.front();
            for(auto i:edge[u]){
                if(!vis[i.v]){
                    vis[i.v]=1;
                    ans[i.v]=ans[u]+i.w;
                    q.push(i.v);
                }
            }
            q.pop();
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

ABC373E How to Win the Election

啥吊题，一眼看出来排序完二分答案，调一年没调出来

二分检测时，看当前位加上 $mid$ 票后，是否还有 $>=m$ 个人的票可能比他多

 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

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

#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N = 2e5 + 7, mod = 1e9 + 7;

ll n, m, k;
ll a[N], b[N];
ll s[N];

bool check(ll f, int pos) {
    ll lft = k - f;
    int x = upper_bound(b + 1, b + 1 + n, a[pos] + f) - b - 1;
    int y = n - m + 1;
    if (n - x >= m) return false;
    if (b[y] > a[pos]) 
        return 1ll * (x - y + 1) * (a[pos] + f + 1) - (s[x] - s[y - 1]) > lft;
    return 1ll * (x - y + 1) * (a[pos] + f + 1) - (s[x] - s[y - 2] - a[pos]) > lft;
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == m) {
        for (int i = 1; i <= n; i++) cout << "0 ";
        return;
    }
    memcpy(b, a, (n + 1) * sizeof(ll));
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + b[i];
    k -= s[n];
    for (int i = 1; i <= n; i++) {
        ll l = 0, r = k, ans = 1e18;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (check(mid, i)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << (ans < 1e18 ? ans : -1) << " ";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

NowCoder

K-th Number

二分答案检测过程中，记录从头到尾每个子区间的比 $mid$ 大的数的个数，然后再遍历数组，看每个位置的数能否作为第 $k$ 大的数进入数组 $b$ ,最后看找的数是否大于 $m$ 个

 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

int n,k;
ll m;
int a[N],s[N];

bool check(int f){
    ll sum=0;
    int l=0;
    for(int i=1;i<=n;i++)s[i]=s[i-1]+(a[i]>=f);
    for(int i=1;i<=n;i++){
        while(s[i]-s[l]>=k)l++;
        sum+=l;
    }
    return sum>=m;
}

void solve(){
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=1,r=1e9,ans=1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

[SCOI2010]传送带

三分两条传送带上的点，这两点间走直线，其余部分走传送带

 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
const double eps=1e-4;

double ax,ay,bx,by,cx,cy,dx,dy;
double p,q,r;
double fx,fy,ex,ey;

double dis(double x,double y,double a,double b){
    return sqrt(eps+(x-a)*(x-a)+(y-b)*(y-b));
}

double chec(double x){
    fx=cx+(x/dis(cx,cy,dx,dy)*(dx-cx)),fy=cy+(x/dis(cx,cy,dx,dy)*(dy-cy));
    return dis(fx,fy,ex,ey)/r+(dis(cx,cy,dx,dy)-x)/q;
}

double check(double x){
    ex=ax+(x/dis(ax,ay,bx,by)*(bx-ax)),ey=ay+(x/dis(ax,ay,bx,by)*(by-ay));
    double l=0,r=dis(cx,cy,dx,dy);
    for(int i=1;i<=1000;i++){
        double lm=l+(r-l)/3,rm=r-(r-l)/3;
        if(chec(lm)>=chec(rm))l=lm;
        else r=rm;
    }
    return chec(l)+x/p;
}

void solve(){
    cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r;
    double l=0,r=dis(ax,ay,bx,by);
    for(int i=1;i<=1000;i++){
        double ml=l+(r-l)/3,mr=r-(r-l)/3;
        if(check(ml)>=check(mr)){
            l=ml;
        }
        else r=mr;
    }
    printf("%.2lf",check(l));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

小咪买东西

01 分数规划

对 $double$ 类二分，限制二分循环次数来控制二分结束即可

我们二分的是单位价格（即总价值/总花费）
判断条件即为在这个单位条件下，买 $k$ 个商品能否仍然保持当前单位价格为正

 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

int n,k;
int c[N],v[N];
double w[N];

bool check(double x){
    for(int i=1;i<=n;i++)w[i]=v[i]-x*c[i];
    sort(w+1,w+1+n,greater<double>());
    double s=0;
    for(int i=1;i<=k;i++){
        s+=w[i];
    }
    return s>0;
}

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>c[i]>>v[i];
    double l=0,r=1e9;
    for(int i=1;i<=100;i++){
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    cout<<int(r)<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e6+7, mod=1e9+7;

int n;
int a[N],mx[N];
stack<int>s;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>0;i--)mx[i]=max(mx[i+1],a[i]);
    for(int i=1;i<=n;i++){
        while(!s.empty()&&s.top()>mx[i]){
            cout<<s.top()<<" ";
            s.pop();
        }
        s.push(a[i]);
    }
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

[NOIP2016]蚯蚓

如果全部在同一个队列或堆中进行存取，会超时。
可以考虑分三个队列来储存，一个存的是原数据，切割后的两部分分开存在另外两个队列中。
同时要考虑随时间变长这个过程，所以只存储原长，在取出时，加上当前时间增长的长度，存进去时，减掉增长的长度。

 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

#include <bits/stdc++.h>
using namespace std;
#define ls (now<<1)
#define rs (now<<1|1)
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
const int N = 1e5 + 7, mod = 1e9 + 7;

int n, m, q, u, v, t;
double p;
queue<int> qu[3];
int a[N];

void solve() {
    cin >> n >> m >> q >> u >> v >> t;
    p = static_cast<double>(u) / v;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n, greater<int>());
    for (int i = 1; i <= n; i++) qu[0].push(a[i]);
    
    for (int i = 1; i <= m; i++) {
        int mx = INT_MIN, pos = 0;
        for (int j = 0; j < 3; j++) {
            if (!qu[j].empty() && qu[j].front() > mx) {
                mx = qu[j].front();
                pos = j;
            }
        }
        int len = qu[pos].front() + (i - 1) * q;
        qu[pos].pop();
        if (i % t == 0) cout << len << " ";
        int l = len * p;
        int r = len - l;
        qu[1].push(l - q * i);
        qu[2].push(r - q * i);
    }
    cout << endl;
    
    int cnt = 1;
    while (!qu[1].empty() || !qu[0].empty() || !qu[2].empty()) {
        int mx = INT_MIN, pos = 0;
        for (int j = 0; j < 3; j++) {
            if (!qu[j].empty() && qu[j].front() > mx) {
                mx = qu[j].front();
                pos = j;
            }
        }
        if (cnt % t == 0) cout << qu[pos].front()+m*q << " ";
        qu[pos].pop();
        cnt++;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Running Median

对顶堆
开两个堆，按小到大各存一半，多出来的那个即为中位值

 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

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;

int p, n, a[N];
multiset<int> s1, s2;

void balance() {
    while (s1.size() > s2.size() + 1) {
        s2.insert(*s1.rbegin());
        s1.erase(prev(s1.end()));
    }
    while (s2.size() > s1.size()) {
        s1.insert(*s2.begin());
        s2.erase(s2.begin());
    }
}

void solve() {
    cin >> p >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    s1.clear();
    s2.clear();
    int cnt=0,ans[N];
    for (int i = 1; i <= n; i++) {
        if (s1.empty() || a[i] <= *s1.rbegin()) {
            s1.insert(a[i]);
        } else {
            s2.insert(a[i]);
        }
        balance();
        if (i % 2 == 1) {
            ans[++cnt]=*s1.rbegin();
        }
    }
    cout<<p<<" "<<cnt<<"\n";
    for(int i=1;i<=cnt;i++){
        cout<<ans[i]<<" ";
        if(i%10==0&&i!=cnt)cout<<endl;
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

任务

可以看到 $x$ 的系数远大于 $y$, 那么在对原数据排序时，优先 $x$.

遍历每一个任务，将能完成当前任务的所有机器都插入堆中，用二分在堆中找到 $y$ 最小的机器，再继续向下遍历

 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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

struct Node{
    int x,y;
    bool operator < (const Node& a){
        if(x==a.x)return y>a.y;
        return x>a.x;
    }
};

ll n,m,cnt,ans;
Node ma[N],as[N];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>ma[i].x>>ma[i].y;
    for(int i=1;i<=m;i++)cin>>as[i].x>>as[i].y;
    sort(as+1,as+1+m);
    sort(ma+1,ma+1+n);
    multiset<int>s;
    for(int i=1,j=1;i<=m;i++){
        while(j<=n&&as[i].x<=ma[j].x)s.insert(ma[j++].y);
        auto it=s.lower_bound(as[i].y);
        if(it!=s.end())cnt++,ans+=500*as[i].x+2*as[i].y,s.erase(it);
    }
    cout<<cnt<<" "<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

叠积木

维护附加信息的并查集

开 $fa[N]$ 并查集 $d[i]$ $i$ 下方的积木数 $cnt[i]$ $i$ 所在的联通块的数量

 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 <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=3e5+7, mod=1e9+7;

int q, x, y;
int fa[N], cnt[N], d[N];

int find(int x) {
    if (fa[x] == x) return x;
    int t = find(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = t;
}

void unite(int a, int b) {
    int fx = find(a), fy = find(b);
    if (fx != fy) {
        fa[fx] = fy; 
        d[fx] = cnt[fy];
        cnt[fy] += cnt[fx];
    }
}

void solve() {
    cin >> q;
    for (int i = 1; i < N; i++) {
        fa[i] = i;
        d[i] = 0;
        cnt[i] = 1;
    }
    while (q--) {
        char op;
        cin >> op;
        if (op == 'M') {
            cin >> x >> y;
            unite(x, y);
        } else {
            cin >> x;
            find(x);
            cout << d[x] << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
补题
Licensed under CC BY-NC-SA 4.0
最后更新于 Sep 11, 2025 16:27 +0800
© 2024 - 2025 KiritoXD
发表了95篇文章 · 总计15万2千字
永远相信美好的事情即将发生。
使用 Hugo 构建
主题 Stack 由 Jimmy 设计