题解 | #长沙学院校赛题解

本场由于出题人并没有经验给大家带来了不怎么好的体验，非常抱歉！

A.多米诺骨牌

签到,预处理出从每个位置向左推和向右推能不能推到底

#include<bits/stdc++.h>
using namespace std;
int f1[200005];
int f2[200005];
int n,a[200005],b[200005];
void solve()
{
	cin>>n;
	for(int i = 1;i<=n;++i)
		cin>>a[i];
    for(int i = 1;i<=n;++i)
        cin>>b[i];
	f1[n] = f2[1] = 1;  
	for(int i = n-1;i>=1;--i)
		f1[i] = f1[i+1]&&(a[i]>b[i+1]);
	for(int i = 2;i<=n;++i)
		f2[i] = f2[i-1]&&(a[i]>b[i-1]);
	if(f1[1]||f2[n])
	{
		cout<<"Yes\n";
		return;
	}
	for(int i = 2;i<n;++i)
		if(f2[i]&&f1[i+1])
		{
			cout<<"Yes\n";
			return;
		}
	cout<<"No\n";
}
int main()
{
    int t = 1;
	while(t--)
		solve();
	return 0;
}

B.富婆价值最大化!

一道线性dp,本来预估难度是比F和C都高的,没想到过了这么多

$dp[i]dp[i]$表示前i天的最大子段和数目

考虑转移

$sumsum$表示$aa$的前缀和数组

转移时维护一个$cntmincntmin$变量表示$sumsum$数组的前缀最小值的数量,$summinsummin$表示前缀最小值以及$maxxmaxx$表示当前的最大子段和

接下来进行分类讨论

从$i-1i-1$到$ii$转移时,

若$sum[i]-summin>maxxsum[i]-summin\; >\; maxx$ 则说明最大子段和发生了改变,此时最大子段和就是前缀最小值的数量$dp[i]=cntmindp[i]\; =\; cntmin$

若$sum[i]-summin==maxxsum[i]-summin==maxx$则说明最大子段和数量发生了改变,此时最大子段和数量改变了$cntmincntmin$,$dp[i]=cntmin+dp[i-1]dp[i]\; =\; cntmin+dp[i-1]$

若则说明最大子段和以及数量都未发生任何变化,$dp[i]=dp[i-1]dp[i]\; =\; dp[i-1]$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll a[1000005];
ll dp[1000005];
int m,k;
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	ll summin=0;
	ll maxsum=-1e18;
	ll cntmin=1;
	for(int i = 1;i<=n;++i)
	{
		cin>>a[i];
		a[i]+=a[i-1];
		if(a[i]-summin>maxsum)
			dp[i] = cntmin,maxsum = a[i]-summin;
		else
		{
			if(a[i]-summin==maxsum)
				dp[i] = dp[i-1]+cntmin;
			else
				dp[i] = dp[i-1];	
		}
		if(a[i]<summin)
			cntmin = 1,summin = a[i];
		else if(a[i]==summin)
			cntmin++;
	}
	while(m--)
	{
		cin>>k;
        assert(k>=1&&k<=n);
		cout<<dp[k]<<'\n';
	}
	return 0;
}

C.异世界

非常经典的二分+bfs

注意:本题没有要求总时间最短,仅要求了最短路步数不变的情况下总时间最短,这点给同学们带来了歧义非常抱歉

先直接跑一遍bfs将勇者到达终点的最短路算出来,若没有勇者能到达终点,则输出-1

bfs时把k个勇者一起丢到队列里,然后跑一遍bfs就好了,由于通过路径的时间均为1,所以先到达的一定是最优的。

先二分要建的边权的最大值mid,然后将边权大于mid的边全部断开,再跑一遍bfs,对比bfs返回的步数是不是跟最短路一致.一致则符合要求,不一致则不符合要求

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int n,m,k,x,y,z,w;
int a[300005];
vector<pii> edge[300005];
int stp[300005];
int ans;
int bfs(int maxx)
{
	queue<int> q;
	for(int i = 1;i<=n;++i)
		stp[i] = 0x3f3f3f3f;
	for(int i = 1;i<=k;++i)
	{
		q.push(a[i]);
		stp[a[i]] = 0;
	}
	while(!q.empty())
	{
		int now = q.front();
		q.pop();
		for(auto x:edge[now])
		{
			if(stp[x.first]<3e5+5||x.second>maxx)
				continue;
			stp[x.first] = stp[now]+1;
			q.push(x.first);	
		}
	}
	return stp[w];
}
int main()
{
	cin>>n>>k>>w;
	for(int i = 1;i<=k;++i)
		cin>>a[i];
	cin>>m;
	for(int i = 1;i<=m;++i)
	{
		cin>>x>>y>>z;
		edge[x].push_back({y,z});
		edge[y].push_back({x,z});
	}
	ans = bfs(1e9);
	if(ans==0x3f3f3f3f)
	{
		cout<<-1<<'\n';
		return 0;		
	}
	int l = 0,r = 1e9,p;
	while(l<=r)
	{
		int mid = (l+r)>>1;
		if(bfs(mid)<=ans) r = mid-1,p = mid;
		else l = mid+1;
	}
	cout<<p+ans<<'\n';
	return 0;
 } 

D.六级阅读

遍历字符串，遇到大写字母flag置1，不输出字符。当大写变为小写的时候，输出一次"Bruce12138"。其它小写字符直接输出。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string t;cin>>t;
	int n;cin>>n;
	while(n--)
	{
		int flag=0;
		string s;cin>>s;
		for(auto i:s)
		{
			if('A'<=i&&i<='Z')
				flag=1;
			else
			{
				if(flag)
				{
					flag=0;
					cout<<"Bruce12138";
				}
				cout<<i;
			}
		}
		if(flag)
			cout<<"Bruce12138";
		cout<<endl;
	}
	return 0;
}

E.beautiful path

标准的树形dp,$dp[i][0]dp[i][0]$表示以i为根且包含$ii$的最长上升路径,$dp[i][1]dp[i][1]$表示以i为根的最长下降路径。转移时对$dp[i][1]+dp[i][0]-1dp[i][1]+dp[i][0]-1$取max即可

时间复杂度$O(n)O(n)$

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> edge[1000005];
int v[1000005];
int dp[1000005][2];
int ans;
void dfs(int now,int fa)
{
	dp[now][0] = dp[now][1] = 1;
	for(auto x:edge[now])
	{
		if(x==fa)	continue;
		dfs(x,now);
		if(v[x]>v[now])
			dp[now][0] = max(dp[x][0]+1,dp[now][0]);
		if(v[x]<v[now])
			dp[now][1] = max(dp[x][1]+1,dp[now][1]);
	}
	ans = max(ans,dp[now][0]+dp[now][1]-1);
}
int main()
{
	cin>>n;
	int x,y; 
	for(int i = 1;i<n;++i)
	{
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for(int i = 1;i<=n;++i)
		cin>>v[i];
	dfs(1,0);
	cout<<ans<<'\n';
	return 0;
}

F.平面最小距离

可以通过打表等方式发现,这种菱形式的排布一定是最优的,此时所有点的最远点曼哈顿距离均相等.

那么可以发现该种排布方式面积可以通过等差数列求和的方式$O(1)O(1)$计算

那么二分等高线的长度先算出面积

我们可以发现,菱形每增加一层,曼哈顿距离就增加2

我们假设当前

这样排布了5个点,那么再增加1个点曼哈顿距离将会变成3,那么3的情况持续到什么时候呢

明显看出,此时无论在哪里增加点,曼哈顿距离都会增加 则当下一层的点增加到3个点时曼哈顿距离为3的情况就达到了极限,也就是当点增加到(下一层的点数)/2时曼哈顿距离就会再增加1

所以解法就比较清晰了,二分出等高线为$ll$时面积大于$kk$的位置

设置sum(l)为等高线为l时的面积

则$(sum(l)-sum(l-1))\mathrm{/}2>k-sum(l-1)(sum(l)-sum(l-1))/2>k-sum(l-1)$时将答案-1即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll clac(int k)
{
	return (2ll*k*k)-(1+2*(k-1));
}
ll k;
int main()
{
	cin>>k;
	int l = 0,r = 1e9;
	while(l<=r)
	{
		int mid = (l+r)>>1;
		if(clac(mid)>=k) r = mid-1;
		else l = mid+1;	
	}
	ll ans = 2ll*(l-1);
	if((clac(l)-clac(l-1))/2>k-clac(l-1))
		ans--;
	cout<<ans<<'\n';
	return 0;
}

G.恩赐

使用multiset模拟过程即可,每次二分处理第一个小于$k_{i}k\_i$的

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int n,m,k,h,x;
multiset<ll> st;
void solve()
{
	cin>>n>>m;
	for(int i = 1;i<=n;++i)
	{
		cin>>x;
		st.insert(x);	
	}
	while(m--)
	{
		cin>>k>>h;
		auto pos = st.lower_bound(k);
		if(pos==st.begin())
			continue;
		pos--;
		ll temp = *pos;
		st.erase(pos);
		st.insert(temp+h);
	}
	cout<<*(st.rbegin())<<'\n';
		
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	t = 1;
	while(t--)
		solve();
	return 0;
}

H.作为礼物的字符串

本题很容易想到$O(n^2)O(n^2)$的并查集做法,但题目数据范围为1e5,显然会tle

先考虑复制一个反串在原字符串后面

此时$s[l:r]s[l:r]$是回文串即$s[l:r]=s[2\ast n-r+1:2\ast n-l+1]s[l:r]\; =\; s[2*n-r+1:2*n-l+1]$

当需要连边操作时,先将区间二进制拆分成一个个$2^{k}2^k$大小的区间与反区间连边

即$l=1,r=10l=1,r=10$时拆分成$l=1,r=8l=1,r=8$以及$l=9,r=10l=9,r=10$

然后与反串的对应区间并查集合并,此时最多mlogn个区间,且一定时$2^{k}2^k$大小

从大到小枚举k每个$2^{k}2^k$大小的区间可以拆分成2个$2^{k-1}2^\{k-1\}$大小的区间与反串对应位置连边,直到区间大小为1

每个区间最多连log次边,总时间复杂度$O(mlo{g}^{2}n)O(mlog^2n)$

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#define lson ( p << 1 )
#define rson ( p << 1 | 1 )
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 10;
const int base = 200001;
int fa[maxn * 40];
int n, m;

int find(int x)
{
    if ( fa[x] != x )
        fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if ( x == y )
        return;
    fa[x] = y;
    return;
}

inline int get(int x, int k)
{
    return k * base + x;
}

int main()
{
    // freopen("D:\\Codefield\\CPP\\Contest\\7\\17.in", "r", stdin);
    // freopen("D:\\Codefield\\CPP\\Contest\\7\\17.out", "w", stdout);
    scanf("%d%d", &n, &m);
    assert(n >= 1 && n <= 100000);
    assert(m >= 1 && m <= 100000);
    // scanf("%s", s + 1);
    for ( int i = 1;i <= 2 * n;i++ ) {
        for ( int k = 0;k <= 20;k++ ) {
            int tt = get(i, k);
            // printf("%d\n", tt);
            assert(tt >= 1 && tt < maxn * 2 * 40);
            fa[tt] = tt;
        }
    }
    for ( int i = 1;i <= n;i++ ) {
        merge(get(i, 0), get(2 * n - i + 1, 0));
    }
    for ( int i = 1;i <= m;i++ ) {
        int l, r;
        scanf("%d%d", &l, &r);
        assert(l >= 1 && l <= n);
        assert(r >= 1 && r <= n);
        assert(l <= r);
        int x = 2 * n - r + 1;
        int y = 2 * n - l + 1;
        for ( int j = 20;j >= 0;j-- ) {
            if ( l + (1 << j) - 1 <= r ) {
                int t1 = get(l, j);
                int t2 = get(x, j);
                merge(t1, t2);
                l += (1 << j);
                x += (1 << j);
            }
        }
    }
    for ( int i = 20;i >= 1;i-- ) {
        for ( int j = 1;j <= 2 * n;j++ ) {
            int tt = get(j, i);
            if ( tt == fa[tt] )
                continue;
            int f = find(tt);
            int x = f / base - (f % base == 0);
            int y = f % base ? f % base : base;
            int tt1 = get(j, i - 1);
            int tt2 = get(y, i - 1);
            merge(tt1, tt2);
            tt1 = get(j + (1 << (i - 1)), i - 1);
            tt2 = get(y + (1 << (i - 1)), i - 1);
            merge(tt1, tt2);
        }
    }
    int flag = 0;
    int ans = 0;
    for ( int i = 1;i <= n;i++ ) {
        int t1 = get(i, 0);
        int t2 = get(i + n, 0);
        if ( find(t1) != find(t2) ) {
            flag = 1;
        }
        else ans++;
    }
    if ( flag )
        printf("NO\n");
    else printf("YES\n");
    printf("%d\n", ans);
    return 0;
}

I.完全图的概率游戏 根据题意可以列出dp方程

$dp[i][j]dp[i][j]$表示当前在$ii$，分数为$jj$，到游戏结束的期望步数

从大到小枚举第二维,可以不断的带入写成n个$dp[i][0]dp[i][0]$的方程组,最后对着n个方程组高斯消元即可

代码第三维$kk$表示它写成$dp[k][0]dp[k][0]$的线性组合前面的系数

总时间复杂度$O(n^4)O(n^4)$

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int mod = 1e9 + 7;
int n, m;
ll dp[maxn][maxn][maxn];
int st[maxn][maxn];
ll a[maxn][maxn];
int flag = 0;
ll inv;

ll ksm(ll x, ll y)
{
    ll ret = 1;
    do {
        if ( y & 1 )
            ret = ret * x % mod;
        x = x * x % mod;
    } while ( y >>= 1 );
    return ret;
}

void guass()
{
    for ( int i = 1;i <= n;i++ ) {
        int maxx = i;
        for ( int j = i + 1;j <= n;j++ ) {
            if ( abs(a[j][i]) > abs(a[maxx][i]) )
                maxx = j;
        }
        swap(a[i], a[maxx]);
        if ( a[i][i] == 0 ) {
            flag = 1;
            break;
        }
        for ( int j = 1;j <= n;j++ ) {
            if ( j == i )
                continue;
            ll temp = (a[j][i] * ksm(a[i][i], mod - 2))%mod;
            for ( int k = 1;k <= n + 1;k++ ) {
                a[j][k] = (a[j][k] - temp * a[i][k]) % mod;
            }
        }
    }
    assert(flag == 0);
    for ( int i = 1;i <= n;i++ ) {
        printf("%lld\n", (-a[i][n + 1] * ksm(a[i][i], mod - 2) % mod + mod) % mod);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    inv = ksm(n - 1, mod - 2);
    for ( int i = 1;i <= m;i++ ) {
        int  u, v;
        scanf("%d%d", &u, &v);
        st[u][v] = st[v][u] = 1;
    }
    for ( int i = n - 1;i >= 0;i-- ) {
        for ( int j = 1;j <= n;j++ ) {
            for ( int k = 1;k <= n;k++ ) {
                if ( j == k )
                    continue;
                if ( st[j][k] ) {
                    dp[j][i][k] = (dp[j][i][k] + inv) % mod;
                }
                else {
                    if ( j + i < n ) {
                        for ( int l = 0;l <= n;l++ ) {
                            dp[j][i][l] = (dp[j][i][l] + dp[k][j + i][l] * inv) % mod;
                        }
                    }
                }
            }
            dp[j][i][0] = (dp[j][i][0] + 1) % mod;
        }
    }
    // for ( int j = n;j >= 0;j-- ) {
    //     for ( int i = 1;i <= n;i++ ) {
    //         for ( int k = 0;k <= n;k++ ) {
    //             printf("%d %d %d : %lld\n", i, j, k, dp[i][j][k]);
    //         }
    //     }
    // }
    for ( int i = 1;i <= n;i++ ) {
        for ( int j = 1;j <= n;j++ ) {
            a[i][j] = dp[i][0][j];
        }
        a[i][n + 1] = dp[i][0][0];
        a[i][i] = (a[i][i] - 1) % mod;
    }
    // for ( int i = 1;i <= n;i++ ) {
    //     for ( int j = 1;j <= n + 1;j++ ) {
    //         printf("%lld ", a[i][j]);
    //     }
    //     printf("\n");
    // }
    guass();
    return 0;
}