ABC 467 - LeAf146

LeAf146

公告

叶子的博客，随便看看吧。

Learn More

标签

服务器网络字符串 ACM Agnet AI Blog Blogging codeforces

995 字

4 分钟

ABC 467

2026-07-24

ACM

/

Blog

A. Obesity #

给定 $Weight$ 和 $Height$ ，BMI 的计算公式是 $BMI=Weight(kg) \div Height(cm)\div Height(cm)$ ，超重的标准是 $BMI\geq 25$ ，问是否超重。

注意给的 $H$ 是 $cm$ 。。。

1
signed main(){
2
    int h,w;cin>>h>>w;
3
    if(w*100*100>=25*h*h)cout<<"Yes\n";
4
    else cout<<"No\n";
5
    return 0;
6
}

B. Keep the Change #

有 $N$ 家商店，在 $i\text{th}$ 家商店购买了价值 $A_{i}$ 的商品，支付了 $B_i(B_{i}\geq A_{i})$ 。若 $S_i=$ keep，则不收零钱，若 $S_i=$ take，则收零钱。问少收了多少零钱。

模拟。当 keep 时，给 ans 加上对应的 $B_{i}-A_{i}$ 即可。

1
signed main(){
2
    int n;cin>>n;
3
    int ans=0;
4
    for(int i=0;i<n;i++){
5
        int a,b;string s;
6
        cin>>a>>b>>s;
7
        if(s=="take")continue;
8
        else ans+=(b-a);
9
    }
10
    cout<<ans<<endl;
11
    return 0;
12
}

C. Adjacent Sums (easy)#

给定由 $0$ 和 $1$ 组成的长度为 $N$ 的数组 $A$ 和长度为 $N-1$ 的数组 $B$ 。每次操作可以选择 $1\leq i\leq N$ ，使得 $A_i=A_{i}+1$ 。问最少多少次操作可以满足对于所有 $1\leq i\leq N-1$ ，有 $(A_{i}+A_{i+1})\equiv B_{i}\pmod 2$ 。

$(A_{i}+A_{i+1})\equiv B_{i}\pmod 2 \implies A_{i}\oplus A_{i+1}=B_{i}$ 所以对于确定的 $A_0$ 和 $B$ ，可以得到整个目标 $A$ 。计算当 $A_0=0$ 和 $A_0=1$ 时需要的操作数，取较小值即可。

1
signed main(){
2
    int n,m;cin>>n>>m;
3
    vector<int> a(n),b(n-1),pre(n);
4
    for(int i=0;i<n;i++)cin>>a[i];
5
    for(int i=0;i<n-1;i++)cin>>b[i];
6
    for(int i=1;i<n;i++)pre[i]=pre[i-1]^b[i-1];
7
    int ans0=0,ans1=0;
8
    for(int i=0;i<n;i++){
9
        if(a[i]!=pre[i])ans0++;
10
        if(a[i]!=1^pre[i])ans1++;
11
    }
12
    cout<<min(ans0,ans1)<<endl;
13
    return 0;
14
}

D. Concentric Circles #

给定四个点 $P,Q,R,S$ ，问是否有两个圆 $C_{1}$ 和 $C_2$ （两个圆可以重合），满足：

$P,Q$ 位于 $C_1$ 的圆周上。
$R,S$ 位于 $C_2$ 的圆周上。
$C_1$ 和 $C_2$ 有相同的圆心。

计算几何会回报每一个踏踏实实推式子的人 🤗。 $C_1$ 的圆心位于 $P,Q$ 的中垂线上， $C_2$ 的圆心位于 $R,S$ 的中垂线上，两圆若有相同圆心，则必定位于两中垂线交点处。具体求中垂线以及交点方法见代码。

1
#define int __int128
2
struct line{
3
    int a,b,c;
4
    line(int a,int b,int c):a(a),b(b),c(c){}
5
};
6
line getline(pair<int,int> p1,pair<int,int> p2){
7
    int x1=p1.first,x2=p2.first,y1=p1.second,y2=p2.second;
8
    int dx=x2-x1,dy=y2-y1;
9
    int a=2*dx,b=2*dy;
10
    int c=-dx*(x1+x2)-dy*(y1+y2);
11
    return line(a,b,c);
12
}
13
void solve(){
14
    pair<signed,signed> p,q,r,s;
15
    cin>>p.first>>p.second>>q.first>>q.second;
16
    cin>>r.first>>r.second>>s.first>>s.second;
17
    line l1=getline(p,q),l2=getline(r,s);
18
    if(l1.a*l2.b-l2.a*l1.b!=0){
19
        cout<<"Yes\n";
20
        return;
21
    }
22
    if((l1.a*l2.c==l2.a*l1.c)&&(l1.b*l2.c==l2.b*l1.c))cout<<"Yes\n";
23
    else cout<<"No\n";
24
}

F.Email Scheduling Optimization #

给定两个长度为 $N$ 的正整数序列 $A$ 和 $B$ 。以及 $Q$ 次操作。每个操作可以将 $A$ 或 $B$ 中的一个元素更改为指定值。每次操作后问如下问题：给 $N$ 家公司发送邮件并收回复。向 $j\text{th}$ 家公司发送花费 $A_j$ 分钟，回复在发送后 $B_j$ 分钟到达。同一时间只能写一封邮件，问收发这 $N$ 封邮件花费的最短时间。

先考虑子问题。由于同一时间只能写一封邮件而可以等待多封不同邮件，显然按照 $B_{i}$ 降序排列最优。接下来的问题就是：动态修改 $A_i$ 或 $B_i$ 后，维护按 $B$ 降序排列时的 $\text{max}\left( \sum_{j=1}^iA_{j} +B_{i}\right)$ 。

考虑使用线段树。由于 $B_{i}\leq 10^9$ 而 $N+Q\leq 2\times10^5$ ，所以要离散化 $B$ 后构造线段树。先读入所有可能的 $B_{i}$ 后，降序排序去重 $B$ 得到线段树的大小。对于任意 $B$ 值，维护 $sumA=\sum_{B_{j}=B} A_{j},maxVal=sumA+B$ 。而最终答案就是根节点的 $maxVal$ 。

合并节点 l 和 r 时，易得，sumA 的取值应该为 $l.sumA+r.sumA$ ，maxVal 的取值应该为 $\text{max}(l.maxVal,l.sumA+r.maxVal)$ 。当修改 $A_i$ 为 $x$ 时，由于 $B_i$ 不变，只需要把本次修改的差值 $x-A_{i}$ 加到对应的 $B_i$ 的 $sumA$ 中即可。当修改 $B_i$ 为 $x$ 时，则需要在原来的 $B_i$ 的 $sumA$ 中减去当前的 $A_i$ ，再把当前的 $A_i$ 加回到修改后的 $x$ 对应的 $sumA$ 中去。

1
class SegTree{
2
    struct Node{
3
        int sumA,maxVal;
4
        Node():sumA(0),maxVal(-LLONG_MAX){}
5
        Node(int s,int m):sumA(s),maxVal(m){}
6
    };
7
    int n,n4,root,end;
8
    vector<Node> tree;
9
    vector<int> revB;
10
    vector<int> count;
11
    inline int ls(int x){return x<<1;}
12
    inline int rs(int x){return x<<1|1;}
13
    Node merge(Node l,Node r){
14
        return Node(l.sumA+r.sumA,max(l.maxVal,l.sumA+r.maxVal));
15
    }
16
    void build(int l,int r,int p){
17
        if(l==r){
18
            tree[p]=Node();
19
            return;
20
        }
21
        int m=l+(r-l)/2;
22
        build(l,m,ls(p));
23
        build(m+1,r,rs(p));
24
        tree[p]=merge(tree[ls(p)],tree[rs(p)]);
25
    }
26
    void update(int l,int r,int pos,int val,int cnt,int p){
27
        if(l==r){
28
            tree[p].sumA+=val;
29
            count[l]+=cnt;
30
            if(count[l]==0)tree[p].maxVal=-LLONG_MAX;
31
            else tree[p].maxVal=tree[p].sumA+revB[l];
32
            return;
33
        }
34
        int m=l+(r-l)/2;
35
        if(pos<=m)update(l,m,pos,val,cnt,ls(p));
36
        else update(m+1,r,pos,val,cnt,rs(p));
37
        tree[p]=merge(tree[ls(p)],tree[rs(p)]);
38
    }
39
public:
40
    SegTree(int sz,vector<int> rb){
41
        n=sz;
42
        n4=n*4;
43
        tree=vector<Node>(n4,Node());
44
        count=vector<int>(n,0);
45
        revB=rb;
46
        root=1;
47
        end=n-1;
48
        build(0,end,root);
49
    }
50
    void update(int pos,int val,int cnt){
51
        update(0,end,pos,val,cnt,root);
52
    }
53
    int getans(){
54
        return tree[root].maxVal;
55
    }
56
};
57
signed main(){
58
    int n,q;cin>>n>>q;
59
    vector<int> A(n),B(n);
60
    vector<tuple<int,int,int>> qs(q);
61
    vector<int> allB;
62
    for(int i=0;i<n;i++)cin>>A[i];
63
    for(int i=0;i<n;i++){
64
        cin>>B[i];
65
        allB.push_back(B[i]);
66
    }
67
    for(int i=0;i<q;i++){
68
        int op,x,y;cin>>op>>x>>y;
69
        x--;
70
        qs[i]={op,x,y};
71
        if(op==2) allB.push_back(y);
72
    }
73
    sort(allB.rbegin(),allB.rend());
74
    allB.erase(unique(allB.begin(),allB.end()),allB.end());
75
    int m=allB.size();
76
    SegTree st(m,allB);
77
    for(int i=0;i<n;i++)st.update(lower_bound(allB.begin(),allB.end(),B[i],greater<int>())-allB.begin(),A[i],1);
78
    for(auto [op,i,x]:qs){
79
        if(op==1){
80
            int p=lower_bound(allB.begin(),allB.end(),B[i],greater<int>())-allB.begin();
81
            st.update(p,x-A[i],0);
82
            A[i]=x;
83
        }else{
84
            int oldp=lower_bound(allB.begin(),allB.end(),B[i],greater<int>())-allB.begin();
85
            st.update(oldp,-A[i],-1);
86
            B[i]=x;
87
            int p=lower_bound(allB.begin(),allB.end(),B[i],greater<int>())-allB.begin();
88
            st.update(p,A[i],1);
89
        }
90
        cout<<st.getans()<<endl;
91
    }
92
    return 0;
93
}