每日一题5.31

Fengyj

2025 CCPC 东北邀请赛

榜单地址

题目链接

B，L金牌题

Fengyj

[C++] 纯文本查看 复制代码

A题：
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define int long long
void solve()
{
    int n;
    // 2 4 6
    cin >> n;
    vector<int> a(n), r(n), l(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    stack<int> stk;

    for (int i = 0; i < n; i++)
    {

        while (!stk.empty() && a[i] % a[stk.top()] != 0)
        {
            r[stk.top()] = i - 1;
            stk.pop();
        }

        stk.push(i);
    }
    while (!stk.empty())
    {
        r[stk.top()] = n - 1;
        stk.pop();
    }

    for (int i = n - 1; i >= 0; i--)
    {
        // cerr << 1 << endl;

        while (!stk.empty() && (a[i] % a[stk.top()] != 0 || a[i] == a[stk.top()]))
        {
            l[stk.top()] = i + 1;
            stk.pop();
        }

        stk.push(i);
    }
    while (!stk.empty())
    {
        l[stk.top()] = 0;
        stk.pop();
    }
    i64 ans = 0;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << l[i] << " \n"[i == n - 1];
    // }
    // for (int i = 0; i < n; i++)
    // {
    //     cout << r[i] << " \n"[i == n - 1];
    // }
    for (int i = 0; i < n; i++)
    {

        ans += 1LL * (r[i] - i + 1) * (i - l[i] + 1);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

void solve(){
	int n,ans=0;
	cin>>n;
	vector<int>a(n+10),l(n+10,1),r(n+10,n);
	for(int i=1;i<=n;i++)cin>>a[i];
	stack<int>s1,s2;
	for(int i=1;i<=n;i++){
		while(s1.size()&&(a[i]%a[s1.top()]!=0||a[i]==a[s1.top()])){
			r[s1.top()]=i-1;
			s1.pop();
		}
		s1.push(i);
	}
	for(int i=n;i>=1;i--){
		while(s2.size()&&a[i]%a[s2.top()]!=0){
			l[s2.top()]=i+1;
			s2.pop();
		}
		s2.push(i);
	}
	for(int i=1;i<=n;i++){
		ans+=(i-l[i]+1)*(r[i]-i+1);
	}
	cout<<ans<<endl;
}

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