写在前面
上周校赛，去命题和做机房配置工作了，导致鸽了一周。
A.彩虹糖的梦
对输入的 个值取最小即是凑出完整的套数。
void solve(){
int ans=1e9;
for(int i=1;i<=7;i++){
int x;cin>>x;
ans=min(ans,x);
}
cout<<ans;
}
B.球格模型(简单版)
对于无解的情况即 。
分成
和
两种情况。
对于 ，可以放在主对角线上，然后到达枚举的最右列直接放在每行的最后一列。
对于 ，可以放在主对角线上，然后到达枚举的最底行直接放在每列的最后一行。
对于剩余的部分直接放在任意一个位置即可。
void solve(){
int n,m,k;
cin>>n>>m>>k;
if(k<max(n,m)){
cout<<"-1\n";
return ;
}
vector<vector<int>>a(n+1,vector<int>(m+1,0));
if(n>=m){
int g=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j==g){
a[i][j]=1;
}else{
a[i][j]=0;
}
}
if(g<m)g++;
}
a[1][1]+=k-max(n,m);
}else{
int g=1;
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(i==g){
a[i][j]=1;
}else{
a[i][j]=0;
}
}
if(g<n)g++;
}
a[1][1]+=k-max(n,m);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
}
C.小数字
不难发现 都是要执行
操作，其他的
的操作会更优。
所以对于 时直接执行
操作，对于
执行
操作，这样执行不会超过
次，若当
还剩余操作次数时直接执行
操作。
void solve(){
i64 n,m;
cin>>n>>m;
while(m){
m--;
if(n>=4){
n=ceil(sqrt(n));
}else{
n=n-1;
}
if(n==0){
break;
}
}
cout<<n-m<<"\n";
}
D.预知
思路就是相当于把其中一堆明牌,而要保证任取两张都不会导致种类重复的最坏情况就是预知种类最多的张数。
当 时由于总牌数大于等于
，所以无解。
当
时:
1.若数组最大值为
，则无需操作。
2.若数组的次大值为
，则需要执行把最大值-1 次，这样变成
，保证任取两张都不会导致种类重复。
3.否则答案就是最大值，这样就是相当于从最大值拿一张，其他堆拿一张。
void solve(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
if(n==1){
cout<<"-1\n";
return ;
}
sort(a.begin(),a.end(),greater<int>());
int m1=a[0];
int m2=a[1];
if(m1==1){
cout<<0<<"\n";
return ;
}
if(m2==1){
cout<<m1-1<<"\n";
return ;
}
cout<<m1<<"\n";
}
E.而后单调
首先考虑数组不能有重复元素，否则必然无解。
其他的即数组没有重复元素，然后分成两种情况：1.严格单调递增 2.严格单调递减
1.我们拿出的连续 个数必然是有序的，否则此段就不能考虑。然后该段可以放进头部，中部，尾部，那总结完其实就是这段在原来的数组排序后也是一段连续的数字。所以我们可以复制一遍数组，然后对数组进行从小到大排序，把
映射
，检测当前段是否是对应映射的值即可。
2.对于严格单调递减的部分即把检查映射反过来即可。
对于上述都找不到可行解，则无解。
具体意思已经在代码中注释。
void solve(){
int n,m;
cin>>n>>m;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<int>b(a);
// 检查重复元素
map<int,int>mp;
for(int i=1;i<=n;i++){
if(mp[a[i]]){
cout<<"NO\n";
return ;
}
mp[a[i]]++;
}
sort(b.begin()+1,b.end());
//对排序后的数字把 a_i 映射为 a_{i+1}
map<int,int>to;
for(int i=1;i+m-1<=n;i++){
to[b[i]]=b[i+m-1];
}
// -> 单调递增
vector<int>pre(n+5);
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+(a[i]>a[i-1]);
}
for(int i=1;i+m-1<=n;i++){
// 满足单调
if(pre[i+m-1]-pre[i]==m-1){
if(to[a[i]]==a[i+m-1]){
cout<<"YES\n";
return ;
}
}
}
vector<int>suf(n+5);
for(int i=n;i>=1;i--){
suf[i]=suf[i+1]+(a[i]>a[i+1]);
}
for(int i=1;i+m-1<=n;i++){
if(suf[i]-suf[i+m-1]==m-1){
if(to[a[i+m-1]]==a[i]){
cout<<"YES\n";
return ;
}
}
}
cout<<"NO\n";
}
F.最大最小路
用通俗的思路考虑路径。
那么就是用 表示以
为路径的一端:
表示路径中点权都是介于
。
表示路径中点权都是介于
。
表示路径中点权都是介于
。
表示路径中点权包含了
，且包含了
。
对于点的转移，分别讨论点权和 的大小关系。
若 ，则
dp[u][0]=0;
dp[u][1]+=dp[v][1]+dp[v][0];
dp[u][2]=0;
dp[u][3]+=dp[v][3]+dp[v][2];
若 ，则
dp[u][0]=0;
dp[u][1]=0;
dp[u][2]+=dp[v][0]+dp[v][2];
dp[u][3]+=dp[v][3]+dp[v][1];
否则
dp[u][0]+=dp[v][0];
dp[u][1]+=dp[v][1];
dp[u][2]+=dp[v][2];
dp[u][3]+=dp[v][3];
考虑答案贡献时，直接算 的贡献，并且加上即每个结点
的所有子结点之间的搭配关系，我们只需要考虑一个结点
和已经算完的其他结点，然后一一继承过去即可。
对于已经算完的 ，我们分别考虑可以和当前点做哪些搭配关系。
对于
因为若以 为路径的一段已经包含要求的点集，便都可以，否则去讨论连接点
的大小关系，然后再搭配。
对于 也是同理。
void solve(){
int n,a,b;
cin>>n>>a>>b;
vector<int>w(n+1);
for(int i=1;i<=n;i++){
cin>>w[i];
}
vector<vector<int>>e(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
i64 ans=0;
vector<vector<i64>>dp(n+1,vector<i64>(4,0));
auto dfs=[&](auto dfs,int u,int fa)->void {
i64 sum0=0,sum1=0,sum2=0,sum3=0;
for(auto v:e[u]){
if(v==fa) continue;
dfs(dfs,v,u);
ans+=sum0*dp[v][3]+(w[u]<=a?sum0*dp[v][2]:0)+(w[u]>=b?sum0*dp[v][1]:0);
ans+=sum1*dp[v][2]+sum1*dp[v][3]+(w[u]>=b?sum1*(dp[v][1]+dp[v][0]):0);
ans+=sum2*dp[v][1]+sum2*dp[v][3]+(w[u]<=a?sum2*(dp[v][0]+dp[v][2]):0);
ans+=sum3*dp[v][0]+sum3*dp[v][1]+sum3*dp[v][2]+sum3*dp[v][3];
sum0+=dp[v][0];
sum1+=dp[v][1];
sum2+=dp[v][2];
sum3+=dp[v][3];
if(w[u]<=a){
dp[u][0]=0;
dp[u][1]+=dp[v][1]+dp[v][0];
dp[u][2]=0;
dp[u][3]+=dp[v][3]+dp[v][2];
}else if(w[u]>=b){
dp[u][0]=0;
dp[u][1]=0;
dp[u][2]+=dp[v][0]+dp[v][2];
dp[u][3]+=dp[v][3]+dp[v][1];
}else{
dp[u][0]+=dp[v][0];
dp[u][1]+=dp[v][1];
dp[u][2]+=dp[v][2];
dp[u][3]+=dp[v][3];
}
}
ans+=dp[u][3];
if(w[u]<=a){
dp[u][1]+=1;
}else if(w[u]>=b){
dp[u][2]+=1;
}else{
dp[u][0]+=1;
}
};
dfs(dfs,1,0);
cout<<ans<<"\n";
}
当然可以考虑用状态压缩节省代码量。
void solve(){
auto check = [&](int x) {
int mask = 0;
if (x <= a) mask |= 1;
if (x >= b) mask |= 2;
return mask;
};
vector<vector<i64>>dp(n+1,vector<i64>(4,0));
i64 ans = 0;
auto dfs = [&](auto &&self, int u, int fa) -> void {
dp[u][check(w[u])] = 1;
for (auto v : e[u]) {
if (v == fa) continue;
self(self, v, u);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if ((i | j) == 3) {
ans += dp[u][i] * dp[v][j];
}
}
}
for (int i = 0; i < 4; i++) {
dp[u][i | check(w[u])] += dp[v][i];
}
}
};
dfs(dfs, 1, 0);
cout << ans << "\n";
}
全部评论
(6) 回帖