SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）

2024-06-08 23:28
文章标签 线段 atcoder beginner contest 357 一集 suntoryprogrammingcontest2024

本文主要是介绍SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Sanitize Hands

        题意：

        模拟

// Problem: A - Sanitize Hands
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: https://atcoder.jp/contests/abc357/tasks/abc357_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n , m;cin >> n >> m;for(int i = 0 ; i < n ; i++){cin >> a[i];}	int cnt = 0;for(int i = 0 ; i < n ; i ++){if(m >= a[i]){cnt ++;m -= a[i];}else{m = 0;}}cout << cnt << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}

 B - Uppercase and Lowercase

        题意：

        还是模拟

// Problem: B - Uppercase and Lowercase
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: https://atcoder.jp/contests/abc357/tasks/abc357_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int cnt1 = 0;string s;cin >> s;	for(auto c : s){if(c >= 'a' && c <= 'z'){cnt1++;}}if(cnt1 * 2 > s.size()){for(auto c : s){if(c >= 'a' && c <= 'z'){cout << c;}else{cout << (char)(c + 32);}}}else{for(auto c : s){if(c >= 'a' && c <= 'z'){cout << (char)(c - 32);}else{cout << (char)c;}}		}
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}

C - Sierpinski carpet 

题意：

依旧是模拟..不知道前排大佬怎么能写这么快的

// Problem: C - Sierpinski carpet
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: https://atcoder.jp/contests/abc357/tasks/abc357_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
vector<vector<string>>v(7 , vector<string>(10101));
void solve() 
{int n;cin >> n;for(int i = 1 ; i <= (int)pow(3 , n) ; i ++){cout << v[n][i] <<endl;}
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t = 1;v[0][1] = '#';for(int i = 1 ; i < 7 ; i ++){int pre = (int)pow(3 , i - 1);for(int j = 1 ; j <= 3 * pre ; j ++){if((j - 1) / pre != 1){for(int t = 0 ; t < 3 ; t ++){v[i][j] += v[i - 1][(j - 1) % pre + 1];				}}else{v[i][j] += v[i - 1][(j - 1) % pre + 1];for(int t = 0 ; t < pre ; t ++){v[i][j] += '.';}v[i][j] += v[i - 1][(j - 1) % pre + 1];}}}while(t--){solve();}return 0;
}

 

D - 88888888

        

思路：将答案拆成加和的形式：假设N的位数为x，那么最终答案为n +n * pow(10 , x)+n*pow(10,2 * x)...n * pow(10 ,( n - 1) * x),然后可以将 N提出来之后，其余的是一个等比数列，因此有等比数列求和公式将答案化简为：n * (pow(10 , n * x) - 1 )/( pow(10 ,x ) -1)

注意n*x可能爆longlong

// Problem: D - 88888888
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: https://atcoder.jp/contests/abc357/tasks/abc357_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
#define int unsigned long long
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
void solve() 
{cin >> n;int tmp = n;int len = 0;while(tmp){len ++;tmp /= 10;}int t = n % mod;int fenzi = qpow(qpow(10 , n) , len) - 1 + mod;fenzi %= mod;int bei = qpow(10 , len) - 1 + mod;int tbei = qpow(bei , mod - 2);int ans = t;t *= fenzi;t %= mod;t *= tbei;t %= mod;cout << t;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}

 

E - Reachability in Functional Graph

        题意：

        思路：将有向图通过SCC缩点形成一个有向无环图（DAG）, 然后思考答案：同一个强连通分量的点两两互相连通，然后与该连通分量相连的所有点与该连通分量上的所有点相连通，因此本题变成了DAG图上DP，直接逆拓扑序走一遍。考虑单独存储每一个强连通分量上的点，与能够连接到该连通分量上的点即可。 （SCC知识快忘记的差不多了..只记得bel从大到小就是逆拓扑序）

// Problem: E - Reachability in Functional Graph
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: https://atcoder.jp/contests/abc357/tasks/abc357_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
#define int long long
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
struct SCC {int n;std::vector<std::vector<int>> adj;//邻边std::vector<int> stk;//存储同一个SCCstd::vector<int> dfn, low, bel;//dfn : dfs的时间戳 low : 子树能跳到的最上方的点 bel : 结点位于哪块强连通分量上 int cur, cnt;SCC() {}SCC(int n) {init(n);}void init(int n) {this->n = n;adj.assign(n, {});dfn.assign(n, -1);low.resize(n);bel.assign(n, -1);stk.clear();cur = cnt = 0;}void addEdge(int u, int v) {adj[u].push_back(v);}void dfs(int x) {dfn[x] = low[x] = cur++;stk.push_back(x);for (auto y : adj[x]) {if (dfn[y] == -1) {dfs(y);low[x] = std::min(low[x], low[y]);} else if (bel[y] == -1) {low[x] = std::min(low[x], dfn[y]);}}if (dfn[x] == low[x]) {int y;do {y = stk.back();bel[y] = cnt;stk.pop_back();} while (y != x);cnt++;}}std::vector<int> work() {for (int i = 0; i < n; i++) {if (dfn[i] == -1) {dfs(i);}}return bel;}
};void solve() 
{int n;cin >> n;SCC scc(n + 5);for(int i = 1 ; i <= n ; i ++){int x;cin >> x;if(x != i){scc.addEdge(i , x);}}vector<int>t = scc.work();vector<int>dp(n + 5 , 0);vector<int>cnt(n + 5 , 0);vector<int>chan[n + 5];int ma = -1;for(int i = 1; i <= n ; i ++){//cout << t[i] << endl;cnt[t[i]]++;chan[t[i]].pb(i);ma = max(ma , t[i]);}int ans = 0;vector<int>vis(n + 5, 0);for(int i = ma ; i >= 1 ; i --){int tmp = cnt[i];ans += cnt[i] * cnt[i];ans += dp[i] * cnt[i];cnt[i] += dp[i];vector<int>path;for(auto it : chan[i]){int next;if(scc.adj[it].size() != 0){next = scc.adj[it][0];}else{continue;}int belo = scc.bel[next];if(!vis[belo]){path.pb(belo);vis[belo] = 1;dp[belo] += cnt[i];}}for(auto it : path){vis[it] = 0;}}//cout << cnt[3] << endl;cout << ans;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;while(t--){solve();}return 0;
}

F - Two Sequence Queries 

        题意：

        思路：很明显的线段树题目（在这几天做的题里面算简单的了）。一个区间需要维护的信息有：区间点的个数（act）、区间中A数组的和（asum）、区间中B数组的和（bsum）、以及区间A*B的和（tot）。区间合并非常简单，全部相加即可。主要考虑tag怎么设置，可以发现，若区间A都加上X，那么其asum += act * X ， tot += bsum * X。反之B区间也是一样。然后本题就完成了

        

// Problem: F - Two Sequence Queries
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: https://atcoder.jp/contests/abc357/tasks/abc357_f
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
#define i64 long long
const LL mod =  998244353;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
template<class Info, class Tag>
struct LazySegmentTree {const int n;std::vector<Info> info;std::vector<Tag> tag;LazySegmentTree(int n) : n(n), info(4 << std::__lg(n)), tag(4 << std::__lg(n)) {}LazySegmentTree(std::vector<Info> init) : LazySegmentTree(init.size()) {std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void apply(int p, const Tag &v) {info[p].apply(v);tag[p].apply(v);}void push(int p) {apply(2 * p, tag[p]);apply(2 * p + 1, tag[p]);tag[p] = Tag();}void modify(int p, int l, int r, int x, const Info &v) {if (r - l == 1) {info[p] = v;return;}int m = (l + r) / 2;push(p);if (x < m) {modify(2 * p, l, m, x, v);} else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info &v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;push(p);return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {if (l >= y || r <= x) {return;}if (l >= x && r <= y) {apply(p, v);return;}int m = (l + r) / 2;push(p);rangeApply(2 * p, l, m, x, y, v);rangeApply(2 * p + 1, m, r, x, y, v);pull(p);}void rangeApply(int l, int r, const Tag &v) {return rangeApply(1, 0, n, l, r, v);}void half(int p, int l, int r) {if (info[p].act == 0) {return;}if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {apply(p, {-(info[p].min + 1) / 2});return;}int m = (l + r) / 2;push(p);half(2 * p, l, m);half(2 * p + 1, m, r);pull(p);}void half() {half(1, 0, n);}
};
struct Tag {i64 adda = 0;i64 addb = 0;void apply(Tag t) {adda += t.adda;adda %= mod;addb += t.addb;addb %= mod;}
};
struct Info {int asum = 0;int bsum = 0;int tot = 0;int act = 0;void apply(Tag t) {asum += (t.adda * act) % mod;asum %= mod;tot += (bsum * t.adda) % mod;tot %= mod;bsum += (t.addb * act) % mod;bsum %= mod;tot += ((asum % mod) *( t.addb % mod)) % mod;tot %= mod;}
};
Info operator + (Info a, Info b) {Info c;c.asum = a.asum + b.asum;c.asum %= mod;c.bsum = a.bsum + b.bsum;c.bsum %= mod;c.act = a.act + b.act;c.act %= mod;c.tot = a.tot + b.tot;c.tot %= mod;return c;
}
void solve() 
{int n , m;cin >> n >> m;vector<Info>v(n);for(int i = 0 ; i < n ; i ++){cin >> v[i].asum;}for(int i = 0 ; i < n ; i ++){cin >> v[i].bsum;}for(int i = 0 ; i < n ; i ++){v[i].act = 1;v[i].tot = v[i].asum * v[i].bsum;v[i].tot %= mod;}LazySegmentTree <Info , Tag> seg(v);for(int i = 0 ; i < m; i ++){int op;cin >> op;if(op == 1){int l , r , x;cin >> l >> r >> x;Tag tmp;tmp.adda = x;seg.rangeApply(l - 1 , r , tmp);}else if(op == 2){int l , r , x;cin >> l >> r >>x;Tag tmp;tmp.addb = x;seg.rangeApply(l - 1 , r , tmp);}else{int l , r;cin >> l >> r;cout << seg.rangeQuery(l - 1 , r).tot << endl;}}
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}

这篇关于SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1043614。

相关文章

poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
hdu1689(线段树成段更新)

hdu1689(线段树成段更新)

两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
poj 1127 线段相交的判定

poj 1127 线段相交的判定

题意： 有n根木棍，每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连，当他们之间有公共点时，就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析： 线段相交的判定。 首先，模板中的线段相交是不判端点的，所以要加一个端点在直线上的判定； 然后，端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的，所以要加是否端点相等的判断。 最后
阅读更多...
HDU4737线段树

HDU4737线段树

题目大意：给定一系列数，F(i,j)表示对从ai到aj连续求或运算，(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd
阅读更多...
zoj 1721 判断2条线段（完全）相交

zoj 1721 判断2条线段（完全）相交

给出起点，终点，与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离，然后最短路。 2点可达条件：没有线段与这2点所构成的线段（完全）相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
阅读更多...
2014 Multi-University Training Contest 8小记

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包， 凸包上的点（ 注意不是端点 ） 才拥有无限的面积 注意 ：  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin
阅读更多...
2014 Multi-University Training Contest 7小记

2014 Multi-University Training Contest 7小记

1003   数学 ， 先暴力再解方程。 在b进制下是个2 ， 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2