题解 | #长沙学院校赛题解
多米诺骨牌
https://ac.nowcoder.com/acm/contest/38762/A
本场由于出题人并没有经验给大家带来了不怎么好的体验，非常抱歉！
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都高的,没想到过了这么多
表示前i天的最大子段和数目
考虑转移
表示的前缀和数组
转移时维护一个变量表示数组的前缀最小值的数量,表示前缀最小值以及表示当前的最大子段和
接下来进行分类讨论
从到转移时,
若 则说明最大子段和发生了改变,此时最大子段和就是前缀最小值的数量
若则说明最大子段和数量发生了改变,此时最大子段和数量改变了,
若则说明最大子段和以及数量都未发生任何变化,
#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,表示以i为根且包含的最长上升路径,表示以i为根的最长下降路径。转移时对取max即可
时间复杂度
#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.平面最小距离
可以通过打表等方式发现,这种菱形式的排布一定是最优的,此时所有点的最远点曼哈顿距离均相等.
那么可以发现该种排布方式面积可以通过等差数列求和的方式计算
那么二分等高线的长度先算出面积
我们可以发现,菱形每增加一层,曼哈顿距离就增加2
我们假设当前
这样排布了5个点,那么再增加1个点曼哈顿距离将会变成3,那么3的情况持续到什么时候呢
明显看出,此时无论在哪里增加点,曼哈顿距离都会增加 则当下一层的点增加到3个点时曼哈顿距离为3的情况就达到了极限,也就是当点增加到(下一层的点数)/2时曼哈顿距离就会再增加1
所以解法就比较清晰了,二分出等高线为时面积大于的位置
设置sum(l)为等高线为l时的面积
则时将答案-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模拟过程即可,每次二分处理第一个小于的
#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.作为礼物的字符串
本题很容易想到的并查集做法,但题目数据范围为1e5,显然会tle
先考虑复制一个反串在原字符串后面
此时是回文串即
当需要连边操作时,先将区间二进制拆分成一个个大小的区间与反区间连边
即时拆分成以及
然后与反串的对应区间并查集合并,此时最多mlogn个区间,且一定时大小
从大到小枚举k每个大小的区间可以拆分成2个大小的区间与反串对应位置连边,直到区间大小为1
每个区间最多连log次边,总时间复杂度
#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方程
表示当前在，分数为，到游戏结束的期望步数
从大到小枚举第二维,可以不断的带入写成n个的方程组,最后对着n个方程组高斯消元即可
代码第三维表示它写成的线性组合前面的系数
总时间复杂度
#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;
}
