题解 | 小白月赛74

小白月赛74题解

A.

#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;
}

B.

贪心，依次取 $1,2,\mathrm{3...}x1,2,3...x$ ,保证 $nn$ 取完这 $xx$ 个数后依然满足大于 $xx$,然后取$n-(x\ast (x+1)\mathrm{/}2)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;
}

C.

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

#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;
}

D.

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

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

E.

对于每一颗树计算 $mm$ 天后会变成什么样子。实际上第一次被修剪到 $bb$ 之后,此后就是一样的循环。首先计算出第一次被修剪到 $bb$ 要多少天，即$\lceil (k+1-h_i)\mathrm{/}{a}_i\rceil \backslash lceil\; (k+1-h\_i)/a\_i\; \backslash rceil$天，其中$\lceil x\rceil \backslash lceil\; x\; \backslash rceil$表示对$xx$上取整,而被修剪到 $bb$ 后则为$\lceil (k+1-b)\mathrm{/}{a}_i\rceil \backslash lceil\; (k+1-b)/a\_i\; \backslash 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;
}

F.

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

#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;
}

G.

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

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

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

#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;
}