【题解】牛客周赛51

A

由于 $m$ 是奇数, $0 \le x < m$ 且 $2x\equiv1$$\pmod{m}$ ，因此 $2x=1$ 或 $m+1$ ，前者显然无解，因此 $x=(m+1)/2$ 。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
#define int long long
void solve()
{
    ll n;
    ll sum=0;
    cin>>n;
    cout<<(n+1)/2;

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

B

lemma： $n$ 和它的十进制下各个数位之和对 $3$ 同余。

因此拼接方式不会影响最终的数是否被3整除，直接统计各个数位之和模3的余数即可。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
#define int long long
string ss[200];
void solve()
{
    ll n;
    ll sum=0;
    cin>>n;
    rep(i,1,n) cin>>ss[i];
    rep(i,1,n)
    {
        for(auto u:ss[i])
        {
            sum+=(u-'0');
            sum%=3;
        }
    }
    if(sum) cout<<"NO\n";
    else cout<<"YES\n";
}    
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    cout<<fixed<<setprecision(15);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

C

若初始电量不高于 $t$ %，则直接超级充电即可；

否则此时有两种选择，要么直接慢充，要么故意掉电量到不高于 $t$ %来触发超级充电，两种情况去最小值即可。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
#define int long long
void solve()
{
    long double ans=0;
    long double x,y,t,a,b,c;
    cin>>x>>y>>t>>a>>b>>c;
    if(x<=t) ans=1.0*(100-x)/c;
    else ans=min(1.0*(100-x)/b,1.0*(x-t)/y+1.0*(100-t)/c);
    cout<<ans<<"\n";
}    
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    cout<<fixed<<setprecision(15);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

D

$a$ 很大无法直接存下其具体值，但由于 $\gcd(a,b)=\gcd(a-b,b)=\gcd(a-2b,b)=\dots=gcd(a\pmod{b},b)$ ，因此我们只需计算 $a\pmod{b}$ 的值，用字符串格式读入 $a$ 然后边计算边对 $b$ 取模即可，最后再计算 $gcd(a\pmod{b},b)$ 。

代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
#define int long long
void solve()
{
    ll n,ans=0;
    string a;
    ll aa=0,b;
    cin>>a;
    cin>>b;
    for(auto u:a)
    {
        aa*=10;
        aa+=(u-'0');
        aa%=b;
    }
    //cout<<aa<<"\n";
    cout<<__gcd(aa,b)<<"\n";
    

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

E

答案具有二分性质，因此可以二分答案，记当前的答案为 $mid$ ，则只需要判断能不能从左上角出发只经过权值小于等于 $mid$ 的点来到达右下角。采用dfs或者并查集判断连通性即可。

本题做法较多，也可以将点按照权值排序，然后从小到大加入，并用并查集判断什么时刻左上角和右下角联通；或者直接改一下 dijkstra也可以。

代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
#define int long long
ll fa[N],vis[N];
ll dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
ll getfa(ll x)
{
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(ll x,ll y)
{
    x=getfa(x),y=getfa(y);
    if(x==y) return;
    fa[y]=x;
  }
vector<ll> g[N];
struct node
{
    ll i,j,w;
}a[N];

void solve()
{
    ll n,ans=0;
    cin>>n;
    rep(i,1,n) rep(j,1,n)
    {
        ll w;
        cin>>w;
        a[(i-1)*n+j].i=i, a[(i-1)*n+j].j=j, a[(i-1)*n+j].w=w;
    }
    sort(a+2,a+n*n,[&](node x,node y){return x.w<y.w;});
    rep(i,1,n*n) vis[i]=0,fa[i]=i;
    vis[1]=vis[n*n]=1;
    ans=max(a[1].w,a[n*n].w);
    rep(k,2,n*n-1)
    {
        ans=max(ans,a[k].w);
        int i=(a[k].i-1)*n+a[k].j;
        vis[i]=1;
        rep(j,0,3)
        {
            ll x=dx[j]+a[k].i,y=dy[j]+a[k].j;
            if(1<=x&&x<=n&&1<=y&&y<=n &&vis[(x-1)*n+y])
            {
                merge(i,(x-1)*n+y);
            }
        }
        if(getfa(1)==getfa(n*n)) return cout<<ans<<"\n",void();
    }
    
}    
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

F

题意为维护最大子段绝对值和，区间询问。因此可以用线段树维护区间最大子段和区间最小子段和，维护区间最大子段和只需在每个节点出维护区间元素和，包含左端点的最大子段和，包含右端点的最大子段和以及整体的最大子段和，即可（或者开两棵树，但是常数会大，实现不优秀的会T）。

上述做法可能有点卡常，事实上：

$abs(a[x]+\dots+a[y])$ = $abs(presum[y]-presum[x-1])$

（presum表示前缀和）

发现由于外层有绝对值，只需让y和x-1分别取到区间中前缀和的最大值和最小值处即可，y和x-1的大小关系不会影响答案。

因此只要查询前缀和数组中区间最大值和最小值，用线段树或者st表均可。

代码：

#include <bits/stdc++.h>

using ll = long long;

template <typename T, class F = std::function<T(const T&, const T&)>>
struct SparseTable {
    int n;
    std::vector<std::vector<T>> mat;
    F func;

    SparseTable(const std::vector<T>& a, const F& f) : func(f) {
        n = static_cast<int>(a.size());
        int max_log = std::__lg(n) + 1;
        mat.resize(max_log);
        mat[0] = a;
        for (int j = 1; j < max_log; j++) {
            mat[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    // return the answer [from, to)，需要保证询问区间不为空 from < to
    T get(int from, int to) const {
        assert(0 <= from && from < to && to <= n);
        int lg = std::__lg(to - from);
        return func(mat[lg][from], mat[lg][to - (1 << lg)]);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }

    std::vector<ll> pre(n + 1);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }

    SparseTable<ll> min(pre, [&](ll i, ll j) { return std::min(i, j); });
    SparseTable<ll> max(pre, [&](ll i, ll j) { return std::max(i, j); });

    int q;
    std::cin >> q;
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        l--;

        ll ans = 0;
        for (auto x : std::vector{min.get(l, r), max.get(l, r)}) {
            for (auto y : std::vector{min.get(l + 1, r + 1), max.get(l + 1, r + 1)}) {
                ans = std::max(ans, std::abs(y - x));
            }
        }

        std::cout << ans << '\n';
    }

    return 0;
}