【超好懂的比赛题解】第十九届同济大学程序设计竞赛暨高校网络友谊赛
title : 第十九届同济大学程序设计竞赛暨高校网络友谊赛
date : 2022-5-30
tags : ACM,题解，练习记录
author : Linno
第十九届同济大学程序设计竞赛暨高校网络友谊赛
题目链接：https://ac.nowcoder.com/acm/contest/34442
A-盒饭盲盒
直接打表（感觉大家都推了一段时间）得出式子： ( n − a ) 2 n 2 + a 2 + n a \frac{(n-a)^2}{n^2+a^2+na} n2+a2+na(n−a)2
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
} B-万历十五年
待补
C-攻城
阴间题，要特判一下如果n=1和n=0都是YES，一般情况只要记录所有堡垒需要的伤害数sum,sum%(6+n)==0并且最小值大于sum/(n+6)即可
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
}
D-两串糖果
dp转移方程 d p [ i ] = m a x { d p [ j − 1 ] + r e v [ j ] [ i ] } dp[i]=max\{dp[j-1]+rev[j][i]\} dp[i]=max{dp[j−1]+rev[j][i]}，我们可以用 O ( n 2 ) O(n^2) O(n2)获得rev[j][i]表示翻转[j,i]区间后的价值量，求法就是枚举区间长度然后枚举起点。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
}signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();while(T--){Solve();}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
} E-只想要保底
题目形式很容易想到二分答案x，那么我们需要找到矩阵的某两行并起来使得每列都有大于x的那么我们考虑用一个优于 O ( n 2 ) O(n^2) O(n2)的方法来做，就可以想到bitset优化，记录前面每行的状态，查看map中是否有与当前行并起来满足条件的行即可。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
} F-捣乱的神
结论：如果n>=60时，一次合并就可以了。（可以自己动手构造试试）
其他情况下数据范围很小，暴力合并一段区间并且返回这个长度，检查是否满足题意即可。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
} G-归零
对于小于等于k/2的数，考虑将其变为0，对于大于k/2的数，考虑将其变为k，那么这个过程就要求区间的数可以有序，很容易想到用主席树做。我们得到表示[l,r]的权值线段树后，按k/2划分两部分进行求和即可得到答案。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
} H-打工人
比较裸的单调队列优化，状态转移方程 d p [ i ] = d p [ j ] + s [ j − > i ] + 2 dp[i]=dp[j]+s[j->i]+2 dp[i]=dp[j]+s[j−>i]+2
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
} I-另类排序
不会，有空再补。
J-收集者
考虑以一个某个位置的0/1结尾对答案的贡献。1可以作为开头所以另外+1，有单个令的情况对整体贡献为1，对每个位置的答案都可以由前面0、1答案的前缀和进行转移。
d p [ 0 ] = d p [ 0 ] + d p [ 1 ] d p [ 1 ] = d p [ 0 ] + d p [ 1 ] + 1 dp[0]=dp[0]+dp[1]\\ dp[1]=dp[0]+dp[1]+1 dp[0]=dp[0]+dp[1]dp[1]=dp[0]+dp[1]+1
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
} K-乐观的R家族
签到题，统计然后输出答案即可。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include}cout<<ans<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();while(T--){Solve();}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！