北京建筑大学2024年程序设计竞赛（同步赛）

阅读量：

A	寿命修改https://ac.nowcoder.com/acm/contest/85333/A

前置知识：线段树区间修改区间查询

本题除了在某些青蛙寿命小于零时要标记为死亡以外，就是一道线段树裸题；

对于已死亡的青蛙，递归到叶子节点处理，由于递归深度为log n,所以最差情况下时间复杂度为O(n logn)

算法的总体复杂度为 O(mlog⁡(n)+nlog⁡(n))

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6 + 10;
    
 const ll inf = 2e18;
    
 struct node{
    
     int l,r;
    
     ll sum;
    
     int alive;
    
     ll lazy;
    
     ll minn;
    
 }tr[N<<2];
    
 int a[N];
    
  
    
 void push_up(int p)
    
 {
    
     tr[p].sum = tr[lc].sum + tr[rc].sum;
    
     tr[p].minn = min(tr[lc].minn,tr[rc].minn);
    
     tr[p].alive = tr[lc].alive + tr[rc].alive;
    
 }
    
 void push_down(int p)
    
 {
    
     tr[lc].sum+=tr[lc].alive * tr[p].lazy;
    
     tr[rc].sum+=tr[rc].alive * tr[p].lazy;
    
     tr[lc].minn+=tr[p].lazy;
    
     tr[rc].minn+=tr[p].lazy;
    
     tr[lc].lazy += tr[p].lazy;
    
     tr[rc].lazy += tr[p].lazy;
    
     tr[p].lazy = 0;
    
 }
    
 void kill(int p) {
    
     if (tr[p].minn > 0)
    
     return;
    
     if (tr[p].l == tr[p].r){
    
     tr[p].sum = 0;
    
     tr[p].minn = inf;
    
     tr[p].alive = 0;
    
     return;
    
     }
    
     push_down(p);
    
     kill(lc);
    
     kill(rc);
    
     push_up(p);
    
 }
    
 void build(int p,int l,int r) {
    
     tr[p].l = l, tr[p].r = r;
    
     if (l == r){
    
     tr[p].sum = a[l];
    
     tr[p].alive = 1;
    
     tr[p].minn = a[l];
    
     tr[p].lazy = 0;
    
     return;
    
     }
    
     int mid = l+r>>1;
    
     build(lc,l,mid),build(rc,mid+1,r);
    
     push_up(p);
    
 }
    
 void update(int p,int l,int r,ll x)
    
 {
    
     if(tr[p].l>=l && tr[p].r<=r)
    
     {
    
     tr[p].lazy+=x;
    
     tr[p].sum+=tr[p].alive * x;
    
     tr[p].minn+=x;
    
     kill(p);
    
     return;
    
     }
    
     push_down(p);
    
     int mid = tr[p].l + tr[p].r >> 1;
    
     if (l <= mid)
    
     update(lc, l, r, x);
    
     if (r > mid)
    
     update(rc, l, r, x);
    
     push_up(p);
    
 }
    
 ll query(int p,int l,int r)
    
 {
    
     if(tr[p].l>=l && tr[p].r<=r)
    
     {
    
     return tr[p].sum;
    
     }
    
     push_down(p);
    
     int mid = tr[p].l + tr[p].r >> 1;
    
     ll ans = 0;
    
     if(l<=mid)
    
     ans+=query(lc,l,r);
    
     if(r>mid)
    
     ans+=query(rc,l,r);
    
     return ans;
    
 }
    
  
    
  
    
 void solve() {
    
     int n;
    
     cin >> n;
    
     int m;
    
     cin >> m;
    
     for(int i = 1;i<=n;i++)cin >> a[i];
    
     build(1,1,n);
    
     int op,l,r;
    
     ll x;
    
     while(m--)
    
     {
    
     cin >> op;
    
     if(op==1)
    
     {
    
         cin >> l >> r >> x;
    
         update(1,l,r,x);
    
     }
    
     else
    
     {
    
         cin >> l >> r;
    
         cout<<query(1,l,r)<<'\n';
    
     }
    
     }
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
     // cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/6sFi8LQMVXu5yIhr1eJ4jxKlkoGg.png)

B	因数之和

经典拆分因子，时间复杂度为O(nlogn)

最后对结果进行前缀和处理，实现O(1)查询；

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6 + 10;
    
 int a[N];
    
 int b[N];
    
 const int M = 1e6;
    
 void solve() {
    
     int n;
    
     cin >> n;
    
     for(int i = 1;i<=M;i++)
    
     {
    
     for(int j = i;j<=M;j+=i)
    
     {
    
         a[j]+=i;
    
     }
    
     }
    
     for(int i = 1;i<=M;i++)b[i] = b[i-1] + (a[i]>=2*i);
    
     int L,R;
    
     while(n--)
    
     {
    
     cin >> L >> R;
    
     cout<<b[R] - b[L-1]<<'\n';
    
     }
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
     // cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/6jWo8zD1imvX0dRMyOFUbIBxsPVl.png)

C	汉诺塔

待补；

D	归零

签到题；

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6 + 10;
    
 int f(int x)
    
 {
    
     int cnt = 0;
    
     while(x)
    
     {
    
     cnt+=x%10;
    
     x/=10;
    
     }
    
     return cnt;
    
 }
    
 int a[N];
    
 void preWork()
    
 {
    
     for(int i = 0;i<10;i++)a[i] = 1;
    
     for(int i = 10;i<=1000000;i++)
    
     a[i] = a[i-f(i)]+1;
    
 }
    
 void solve() {
    
     int n;
    
     cin >> n;
    
     cout<<a[n]<<'\n';
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
     preWork();
    
      cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/aEQMAUXJVK7tY5d3oO1ClSNy8p0w.png)

E	激活锚点

kruskal板子

对所有锚点求最小生成树，然后再找到起点到任一锚点的最近距离加上就可以。

（不能对所有节点一起求最小生成树，因为起点点不是锚点，起点只能连接一个边）

复制代码

 #include<bits/stdc++.h>

    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6+10;
    
 struct edge{
    
     int from,to;
    
     double val;
    
     bool operator<(const edge& b)const{
    
     return val<b.val;
    
     }
    
 };
    
 int p[N];
    
 int find(int x)
    
 {
    
     if(x!=p[x])p[x] = find(p[x]);
    
     return p[x];
    
 }
    
 void solve()
    
 {
    
     vector<pair<double,double>>a;
    
     int x,y,n;
    
     cin >> x >> y >> n;
    
     double res = 1e9;
    
     for(int i = 1;i<=n;i++)p[i] =i;
    
     a.resize(n+1);
    
     for(int i = 1;i<=n;i++)
    
     {
    
     cin >> a[i].first >> a[i].second;
    
     res = min(res,sqrt(1.0 * (x-a[i].first) * (x-a[i].first) + 1.0*(y-a[i].second) * (y-a[i].second)));
    
     }
    
     vector<edge>b;
    
     for(int i = 1;i<=n;i++)
    
     {
    
     for(int j = i+1;j<=n;j++)
    
     {
    
         b.push_back({i,j,sqrt((a[i].first-a[j].first) * (a[i].first - a[j].first) + (a[i].second - a[j].second) * (a[i].second - a[j].second))});
    
     }
    
     }
    
 //    for(auto i:b)
    
 //    {
    
 //        cout<<i.from<<" "<<i.to <<" "<<i.val<<endl;
    
 //    }
    
     sort(alls(b));
    
     int m = b.size();
    
     int cnt = 0;
    
     for(int i = 0; i < m; i++)
    
     {
    
     int pa = find(b[i].from);
    
     int pb = find(b[i].to);
    
     if(pa != pb){
    
         //cout<<b[i].from<<" "<<b[i].to<<endl;
    
         res += b[i].val;
    
         p[pa] = pb;
    
         ++cnt;
    
     }
    
     if(cnt==n-1)break;
    
     }
    
     cout<<res<<'\n';
    
 }
    
 int main()
    
 {
    
     cout<<fixed<<setprecision(10);
    
     ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    
     int _ = 1;
    
     cin >> _;
    
     while(_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/NJrsiV8AIEnvhb2cf64dtwFjx039.png)

F	买蛋糕

签到题；

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6 + 10;
    
 void solve() {
    
     int n;
    
     cin >> n;
    
     int a,b,c;
    
     int ans = 0;
    
     for(int i = 0;i<n;i++)
    
     {
    
     cin >> a >> b >> c ;
    
     ans+=(a+b+c)>=100;
    
     }
    
     cout<<ans<<'\n';
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
 //     cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/mnf9hYHNJas7RbTiKzZ4U3CoXFO1.png)

G	区间翻转

签到题；

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6 + 10;
    
 void solve() {
    
     int n,m,k,L,R;
    
     cin >> n >> m >> k;
    
     while(k--)
    
     {
    
     cin >>L >> R;
    
     if(m<=R && m>=L)
    
     {
    
         m = R-m+L;
    
 //            cout<<m<<endl;
    
     }
    
     }
    
     cout<<m<<'\n';
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
 //     cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/PmAHQnlTwL8sC4N2MYBWv3FU7kzS.png)

H	点燃星海

就是求连通块数量，dfs跑一遍就好；

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e3 + 10;
    
 int n,m;
    
 char g[N][N];
    
 bool vis[N][N];
    
 void dfs(int i,int j)
    
 {
    
     if(vis[i][j])return;
    
     vis[i][j] = true;
    
     if(g[i][j]=='0')return;
    
     dfs(i,(j+1)%m);
    
     dfs(i,(j-1+m)%m);
    
     dfs((i+1)%n,j);
    
     dfs((i-1+n)%n,j);
    
 }
    
 void solve() {
    
     cin >> n>> m;
    
     int ans = 0;
    
     for(int i = 0;i<n;i++)cin >> g[i];
    
     for(int i = 0;i<n;i++)
    
     {
    
     for(int j = 0;j<m;j++)
    
     {
    
         if(g[i][j]=='1' && !vis[i][j]) {
    
             ++ans;
    
             dfs(i,j);
    
         }
    
     }
    
     }
    
     cout<<ans<<'\n';
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
 //     cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/C6S8GVzxeBb54UjTX0cyLtPKAWhF.png)

I	洗牌

不要被吓到，看数据范围模拟即可；

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6 + 10;
    
 void solve() {
    
     int n,l,r;
    
     cin >> n;
    
     string s;
    
     for(char i = '1';i<='1'+54;i++)
    
     {
    
     s+=i;
    
     }
    
     while(n--)
    
     {
    
     cin >>l >> r;
    
     l--,r--;
    
     string y = s.substr(l,r-l+1);
    
     s.erase(l,r-l+1);
    
     s = y + s;
    
     }
    
     for(int i = 0;i<54;i++)cout<<int(s[i]-'0')<<" ";
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
 //     cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/szuAFkGJPSDn9blCpeXT5RwZtUVq.png)

J	初等元素论

待补；

K	翻转排序

易知交换a[i],a[j]可以通过翻转区间[i,j],[i+1,j-1]实现(j-i>=2时)；

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e6 + 10;
    
 void solve() {
    
     int n,m,k,L,R;
    
     cin >> n >> m >> k;
    
     while(k--)
    
     {
    
     cin >>L >> R;
    
     if(m<=R && m>=L)
    
     {
    
         m = R-m+L;
    
 //            cout<<m<<endl;
    
     }
    
     }
    
     cout<<m<<'\n';
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
 //     cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/K0dEw6NbJTfpFlOC4ujh9tDQLgMv.png)

L	分煎饼

计算几何 + 二分，待补；

M	画图

模拟

复制代码

 #include<bits/stdc++.h>

    
  
    
 #define ll long long
    
 #define alls(x) x.begin(),x.end()
    
 #define ull unsigned long long
    
 #define lowbit(x) x&-x
    
 #define lc p<<1
    
 #define rc p<<1|1
    
 #define PII pair<int,int>
    
 #define vi vector<int>
    
 using namespace std;
    
 const int mod = 998244353;
    
 const int N = 1e3 + 10;
    
 int n, m;
    
 int a[N][N];
    
  
    
 void line(int x1, int x2, int y1, int y2) {
    
     if (x1 == x2) {
    
     if (y1 > y2)swap(y1, y2);
    
     for (int i = y1; i <= y2; i++)a[x1][i] = 1;
    
     return;
    
     }
    
     if (y1 == y2) {
    
     if (x1 > x2)swap(x1, x2);
    
     for (int i = x1; i <= x2; i++)a[i][y1] = 1;
    
     return;
    
     }
    
     if (x1 > x2) {
    
     swap(x1, x2);
    
     swap(y1, y2);
    
     }
    
     if (y1 < y2) {
    
     for (int i = x1, j = y1; i <= x2; i++, j++)
    
         a[i][j] = 1;
    
     } else {
    
 //        cout << "HERE" << endl;
    
     for (int i = x1, j = y1; i <= x2; i++, j--)a[i][j] = 1;
    
     }
    
 }
    
  
    
 void solve() {
    
     cin >> n >> m;
    
     int k;
    
     cin >> k;
    
     int op, x1, x2, y1, y2;
    
     while (k--) {
    
     cin >> op >> x1 >> y1 >> x2 >> y2;
    
     if (op == 1) {
    
         line(x1, x2, y1, y2);
    
     } else {
    
         line(x1, x1, y1, y2);
    
         line(x2, x2, y1, y2);
    
         line(x1, x2, y1, y1);
    
         line(x1, x2, y2, y2);
    
     }
    
     }
    
     //cout<<"HELLO"<<endl;
    
     for (int i = 1; i <= n; i++) {
    
     for (int j = 1; j <= m; j++) {
    
         if (a[i][j])cout << "x";
    
         else cout << '.';
    
     }
    
     cout << '\n';
    
     }
    
 }
    
  
    
 int main() {
    
     cout << fixed << setprecision(6);
    
     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
     int _ = 1;
    
 //     cin >> _;
    
     while (_--)solve();
    
 }
    
    
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/Eo0Xtnks1KHgYVcRBp4lJQ9wUNAe.png)

全部评论 (0)

还没有任何评论哟~

北京建筑大学2024年程序设计竞赛（同步赛）

A寿命修改https://ac.nowcoder.com/acm/contest/85333/A 前置知识：线段树区间修改区间查询本题除了在某些青蛙寿命小于零时要标记为死亡以外，就是一道线段树裸题；...

2024年广州大学程序设计竞赛新生赛（同步赛）题解

比赛链接 A.在ACM里打ACM Solution 模拟题意即可，需要记录的信息是：总的罚时pen，总共ac的题目数量acc，对13个题都记录两个数，一个是fail表示非ac提交的额外罚时，一个是is...

牛客浙江理工大学 2024 年程序设计竞赛（同步赛） F（leetcode）

链接：登录—专业IT笔试面试备考平台牛客网来源：牛客网题目描述给定一个仅由小写字母构成的字符串SSS。对于所有位置iii，求出S[i,...,∣S∣]S[i,...,S]S[i,...,∣S∣...

【2024年浙江工商大学程序设计竞赛新生赛（同步赛）部分题解】

比赛链接 C.交换题目大意给定一个长度为n的数组a。一开始你有一个总和s=0。现在你需要做n次操作，第i次操作的流程如下（1\leqslanti\leqslantn：选择一个下标p\in[1,...

[HBCPC2024] 2024 年湖北省大学生程序设计竞赛重现赛题解

比赛链接:HBCPC2024 还是和@cyx20110930组的队，只不过用我的号交的。（rk.26）这次我也橙了开心.jpg 由于@cyx20110930在车上，电脑又快没电了，所以他只上线1h。但...

新疆大学ACM-ICPC程序设计竞赛五月月赛（同步赛）

五一期间，怎么能闲着，好久都没打大型个人赛了，来一场找找感觉总的难度感觉还可以，最终六题收场，海星 ARedRover 思路：其实这题可能在刚开场的时候，给人一种签到题的感觉，由于排在第一个，大家一...

北京信息科技大学第十一届程序设计竞赛（重现赛）

Akotori和糖果链接：<https://ac.nowcoder.com/acm/contest/940/A 来源：牛客网题目描述 kotori共有n块糖果，每块糖果的初始状态是分散的，她想把这...

bnuoj 中国地质大学（北京）第三届程序设计竞赛

4047魔方系列——相同高度此题相当于求最少移动块数， include<stdio.h intmain intn,i; intsum,avg,num; inta[550]; whilescanf%d...

2019年广东工业大学腾讯杯新生程序设计竞赛（同步赛）

同步赛链接 A原初的信纸最值，STL）题意：找n个数的最大值. 参考代码： voidsolve intn; std::cinn; std::vector<intan; forauto&c:a st...

2021年浙大城市学院新生程序设计竞赛（同步赛） D Diseased String

题目链接：DDiseasedString2021年浙大城市学院新生程序设计竞赛（同步赛）nowcoder.com 题目描述 Youaregivenastringsssoflengthnconsisti...

是否确定退出登录?

北京建筑大学2024年程序设计竞赛（同步赛）

全部评论 (0)

相关文章推荐

北京建筑大学2024年程序设计竞赛（同步赛）

2024年广州大学程序设计竞赛新生赛（同步赛）题解

牛客浙江理工大学 2024 年程序设计竞赛（同步赛） F（leetcode）

【2024年浙江工商大学程序设计竞赛新生赛（同步赛）部分题解】

[HBCPC2024] 2024 年湖北省大学生程序设计竞赛重现赛题解

新疆大学ACM-ICPC程序设计竞赛五月月赛（同步赛）

北京信息科技大学第十一届程序设计竞赛（重现赛）

bnuoj 中国地质大学（北京）第三届程序设计竞赛

2019年广东工业大学腾讯杯新生程序设计竞赛（同步赛）

2021年浙大城市学院新生程序设计竞赛（同步赛） D Diseased String