当前位置：个人在线分享 > SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）
  • 文章介绍

    • 有疑问？请点击复制链接咨询！

    A – Sanitize Hands

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

            模拟

    // Problem: A - Sanitize Hands
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: http://atcoder.jp/contests/abc357/tasks/abc357_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (http://cpeditor.org)

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '
'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pairpl;
priority_queue<LL , vector, greater >mi;//小根堆
priority_queue 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;
vectora(N , 0);
void init(int n){
	for(int i = 0 ; i > n >> m;
	for(int i = 0 ; i > a[i];
	}	
	int cnt = 0;
	for(int i = 0 ; i = a[i]){
			cnt ++;
			m -= a[i];
		}
		else{
			m = 0;
		}
	}
	cout << cnt <>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

     B – Uppercase and Lowercase

            题意：SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）插图(1)

            还是模拟

    // Problem: B - Uppercase and Lowercase
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: http://atcoder.jp/contests/abc357/tasks/abc357_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (http://cpeditor.org)

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '
'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pairpl;
priority_queue<LL , vector, greater >mi;//小根堆
priority_queue 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;
vectora(N , 0);
void init(int n){
	for(int i = 0 ; i > s;	
	for(auto c : s){
		if(c >= 'a' && c  s.size()){
		for(auto c : s){
			if(c >= 'a' && c <= 'z'){
				cout << c;
			}
			else{
				cout <= 'a' && c <= 'z'){
				cout << (char)(c - 32);
			}
			else{
				cout <>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

    C – Sierpinski carpet 

    题意：

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

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

    // Problem: C - Sierpinski carpet
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: http://atcoder.jp/contests/abc357/tasks/abc357_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (http://cpeditor.org)

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '
'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pairpl;
priority_queue<LL , vector, greater >mi;//小根堆
priority_queue 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;
vectora(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
vector<vector>v(7 , vector(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

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

    思路：将答案拆成加和的形式：假设N的位数为SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）插图(4)，那么最终答案为SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）插图(4),然后可以将 SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）插图(4)提出来之后，其余的是一个等比数列，因此有等比数列求和公式将答案化简为：SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）插图(4)

    注意n*x可能爆longlong

    // Problem: D - 88888888
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: http://atcoder.jp/contests/abc357/tasks/abc357_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (http://cpeditor.org)

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '
'
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 pairpl;
priority_queue<LL , vector, greater >mi;//小根堆
priority_queue 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;
vectora(N , 0);
void init(int n){
	for(int i = 0 ; i >=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;
    while(t--)
    {
    	solve();
    }
    return 0;
}

     

    E – Reachability in Functional Graph

            题意：SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）插图(5)

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

    // Problem: E - Reachability in Functional Graph
// Contest: AtCoder - SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）
// URL: http://atcoder.jp/contests/abc357/tasks/abc357_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (http://cpeditor.org)

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '
'
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 pairpl;
priority_queue<LL , vector, greater >mi;//小根堆
priority_queue 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;
vectora(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
struct SCC {
    int n;
    std::vector<std::vector> adj;//邻边
    std::vector stk;//存储同一个SCC
    std::vector 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 work() {
        for (int i = 0; i > n;
	SCC scc(n + 5);
	for(int i = 1 ; i > x;
		if(x != i){
			scc.addEdge(i , x);
		}
	}
	vectort = scc.work();
	vectordp(n + 5 , 0);
	vectorcnt(n + 5 , 0);
	vectorchan[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;
	vectorvis(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];
		vectorpath;
		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 

            题意：SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）插图(6)

            思路：很明显的线段树题目（在这几天做的题里面算简单的了）。一个区间需要维护的信息有：区间点的个数（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: http://atcoder.jp/contests/abc357/tasks/abc357_f
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (http://cpeditor.org)

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '
'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
#define i64 long long
const LL mod =  998244353;
const LL llinf = 5e18;
typedef pairpl;
priority_queue<LL , vector, greater >mi;//小根堆
priority_queue 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
struct LazySegmentTree {
    const int n;
    std::vector info;
    std::vector tag;
    LazySegmentTree(int n) : n(n), info(4 << std::__lg(n)), tag(4 << std::__lg(n)) {}
    LazySegmentTree(std::vector init) : LazySegmentTree(init.size()) {
        std::function 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 = y || r = x && r = y || r = x && r > n >> m;
	vectorv(n);
	for(int i = 0 ; i > v[i].asum;
	}
	for(int i = 0 ; i > 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  seg(v);
	for(int i = 0 ; i > 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 <>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

    本站无任何商业行为
    个人在线分享 » SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）(A~F)（最爱线段树的一集）
    admin

    admin 钻石

    分享到：

    相关推荐

    E-->