题解 | 小白月赛74

简单的整除

https://ac.nowcoder.com/acm/contest/59284/A

小白月赛74题解

#include<bits/stdc++.h>
using namespace std;
int x;
int main()
{
    cin>>x;
    if(x%2==0||x%3==0||x%5==0||x%7==0)
        cout<<"YES\n";
    else
        cout<<"NO\n";
    
    return 0;
}

贪心，依次取 $1, 2, 3... x$ ,保证 $n$ 取完这 $x$ 个数后依然满足大于 $x$ ,然后取 $n - (x * (x + 1) / 2)$ 即可。

#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i = 1;i<=n;++i)
        {
            n-=i;
            if(n<=i)
                cout<<i+n<<' ';
            else
                cout<<i<<" ";
        }
        cout<<'\n';
    }
    return 0;
}

容易发现，实际上就是不相等数的数量

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,int> mp;
void solve()
{
    mp.clear();
    cin>>n>>m;
    int cnt = 0;
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=m;++j)
        {
            int x;
            cin>>x;
            mp[x]++;
            if(mp[x]==1)
                cnt++;
        }
    cout<<cnt<<'\n';
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

首先， $a_{i}$ 被操作一次之后就会变成 $0$ ，所以无论怎么操作都可以有无效操作(操作 $0$ 即可)。我们将操作一个非负整数的贡献(即使得总和 $n$ 减少的数量)称为 $v$ 。

容易发现，操作一个正整数 $a_{i}$ 时 $v = (n-i+1) \times a_i$ ,且若从后往前操作就一定没有后效性,即先操作后面的不会产生任何影响，而且很显然，先操作前面的只会产生负面影响(因为先操作前面的只会让后面的 $a_{i}$ 更小,则 $(n-i+1) \times a_i$ 一定变小),那么就可以直接认为每一个操作之间相互没有影响(因为要操作时直接令编号大的先操作就不会产生影响)。那么只需要找出 $v$ 最大的 $m$ 个正整数，将总和减去 $\sum_{i=1}^{m} v_i$ 即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[100005];
void solve()
{
    cin>>n>>m;
    vector<int> v;
    int ans = 0;
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        if(a[i]>=0)
            v.push_back((n-i+1)*a[i]);
        ans+=a[i];
    }
    sort(v.begin(),v.end(),greater<int>());
    for(int i = 0;i<min(m,(int)v.size());++i)
        ans-=v[i];
    cout<<ans<<'\n';
    
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

对于每一颗树计算 $m$ 天后会变成什么样子。实际上第一次被修剪到 $b$ 之后,此后就是一样的循环。首先计算出第一次被修剪到 $b$ 要多少天，即 $\lceil (k+1-h_i)/a_i \rceil$ 天，其中 $\lceil x \rceil$ 表示对 $x$ 上取整,而被修剪到 $b$ 后则为 $\lceil (k+1-b)/a_i \rceil$ 天一循环，直接模拟计算即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n,m,k,b;
int a[100005];
int h[100005];
void solve()
{
    cin>>n>>m>>k>>b;
    for(int i = 1;i<=n;++i)
        cin>>h[i];
    m--;
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        int x = (k-h[i]+a[i])/a[i];
        if(m<x)
        {
            cout<<h[i]+m*a[i]<<' ';
            continue;
        }
        int mm = m-x;
        int zq = (k-b+a[i])/a[i];
        int now = mm%zq;
        cout<<b+now*a[i]<<' ';
    }
    cout<<'\n';
}
signed main()
{
    cin>>t;
    while(t--)
        solve();
    return 0;
}

很显然的二分题，将边都按边权从小到大排序，二分最小的最大边权是多少。按边权从小到大用并查集连边,直接判断每一个集合内的点在并查集是否都在一个集合内。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int fa[1000005];
int find(int x)
{
    return x==fa[x]?fa[x]:fa[x] = find(fa[x]);
}
struct node{
    int u,v,w;
}a[1000005];
vector<int> q[1000005];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x==y)
        return;
    fa[x] = y;
}
int check(int x)
{
    for(int i = 1;i<=n;++i)
        fa[i] = i;
    for(int i = 1;i<=x;++i)
        merge(a[i].u,a[i].v);
    for(int i = 1;i<=k;++i)
    {
        int now = find(q[i][0]);
        for(auto x:q[i])
            if(find(x)!=now)
                return 0;
    }
    return 1;
}
signed main()
{
    cin>>n>>m;
    for(int i = 1;i<=m;++i)
        cin>>a[i].u>>a[i].v>>a[i].w;
    cin>>k;
    for(int i = 1;i<=k;++i)
    {
        int x;
        cin>>x;
        for(int j = 1;j<=x;++j)
        {
        	int y;
        	cin>>y;
        	q[i].push_back(y);
		}
    }
    sort(a+1,a+1+m,cmp);
    int l = 1,r = m,ans = m;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(check(mid))
        {
            ans = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }
    cout<<a[ans].w<<'\n';
    return 0;
}

首先先不考虑 $m$ 次搭桥的问题，从 $1$ 开始贪心的往后跳,跳到尽可能远的位置,直到跳到 $n$ 。这中间假设一共搭了 $x$ 次桥,那么我们直接保留节省最大的 $m$ 次即可，剩下的就直接走。

为什么这样是正确的呢,对于 $i$ 能跳到最远的 $j$ ,由于 $h_{i+1+},h_{i+2}...,h_{j-1}$ 一定小既小于 $h_{i}$ 又小于 $h_{j}$ ，那么他最远也一定只能跳到 $h_{j}$ ,那么从 $i$ 跳到 $j$ 一定比 $i + 1$ 跳到 $j$ 更优。

那么如何找到能跳到最远的位置呢?首先假设我们目前处于 $i$ ，如果右边存在一个最近的 $j$ 满足 $h_j \ge h_i$ 那么最远的位置就是 $j$ ，否则就是 $\max_{j = i+1}^{n} h_j$ 所在的位置。前者可以直接枚举寻找(我这里蠢了用的单调栈)，后者可以二分 $s t 表$ 或线段树解决。

#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<int> s;
int n,m;
int h[200005];
int pre[200005];
int nxt[1000005];
int maxn[200005][25];
int lg[200005];
int c(int x,int y)
{
    return abs(pre[y-1] - pre[x-1]);
}
int q(int l,int r)
{
	int k = lg[r-l+1]-1;
	return max(maxn[l][k],maxn[r-(1<<k)+1][k]);
}
int check(int l,int r,int maxx)
{
	int maxy = q(l,r);
	return maxy==maxx;
}
signed main()
{
    cin>>n>>m;
    for(int i = 1;i<=200000;++i)	lg[i] = lg[i-1]+(1<<lg[i-1]==i);
    for(int i = 1;i<=n;++i)
    {
        cin>>h[i];
        if(i>=2)
            pre[i-1] = abs(h[i]-h[i-1])+pre[i-2];
        maxn[i][0] = h[i];
    }
    for(int i = 1;i<=n;++i)
    {
        while(s.size()&&h[s.top()]<=h[i])
        {
            nxt[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    while(s.size())
    {
        nxt[s.top()] = n+1;
        s.pop();
    }
    for(int j = 1;j<=21;++j)
		for(int i = 1;i+(1<<j)-1<=n;++i)	    
			maxn[i][j] = max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]);
    int ans = pre[n-1];
    vector<int> v;
    for(int i = 1;i<=n;++i)
        if(nxt[i]!=n+1)
        {
        	v.push_back(c(i,nxt[i])-abs(h[i]-h[nxt[i]]));
        	i = nxt[i]-1;
		}
		else
		{
			if(i==n)
				continue;
			int l = i+1,r = n,ans = r;
			int now = q(l,r);
			while(l<=r)
			{
				int mid = (l+r)>>1;
				if(check(i+1,mid,now))
				{
					ans = mid;
					r = mid-1;
				}
				else
					l = mid+1;
			}
			v.push_back(c(i,ans)-abs(h[i]-h[ans]));
			i = ans-1;
		}
    sort(v.begin(),v.end(),greater<int>());
    for(int i = 0;i<min(m,(int)v.size());++i)
        ans-=v[i];
    cout<<ans<<'\n';
    return 0;
}

全部评论

推荐最新楼层

DamianCheng

The University of Sydney C++

你好，请问D题的n,m为什么用int会有20%的用例通过不了，用long long int就可以了呢？n和m的范围在0<n> using namespace std; typedef long long ll; int main () { int t; cin >> t; while (t) { ll n, m; cin >> n >> m; ll a[1000001]; vector<ll> vec; ll ans = 0; for (ll i = 0; i < n; ++i) { cin >> a[i]; if (a[i] > 0) { vec.push_back((n - i) * a[i]); } ans += a[i]; } sort(vec.begin(), vec.end(), greater<ll>()); for (ll i = 0; i < min(m, (ll)vec.size()); ++i) { ans -= vec[i]; } cout << ans << endl; --t; } return 0; }</ll></ll></n>

点赞回复分享

发布于 2023-06-15 19:31 澳大利亚

牛客876258997号

韩山师范学院算法工程师

c题样例 213 111 514 答案好像不对吧

点赞回复分享

发布于 10-29 22:22 广东