七海ノ心象素描

所有的为时已晚都是恰逢其时

CF Round 1035 Div2

个人题解

如月七海
如月七海 局外人
2025年07月24日
预计阅读 7 分钟
1533 字

A

操作 2 会让奇数-1，偶数+1。

不难发现只有当 aa 为奇数时，我们能让 aa 减小，且只能减少 11。

如果 a>ba > b，那么当且仅当 aoplus1=ba \\oplus 1 = b 有解。

下面讨论 a<ba < b 的情况。

如果 xleyx \\le y，那么我们全部使用操作 11 即可。

否则我们肯定是两种操作交替使用。

关于第一次和最后一次用哪种操作，判断 aa 与 b−ab-a 的奇偶即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int T, a, b, x, y;
int c[2];
void solve() {
    a=read(), b=read(), x=read(), y=read();
    if(a>b&&(a^1)!=b) {
        puts("-1");
        return;
    }
    if(a>b) {
        printf("%d\n",y);
        return;
    }
    ll ans=0;
    if(x<=y) {
        printf("%d\n",(b-a)*x);
    } else {
        if(a==b) {
            puts("0");
            return;
        }
        if(a&1) c[0]=y, c[1]=x;
        else c[0]=x, c[1]=y;
        printf("%d\n",(b-a)/2*(x+y)+(b-a)%2*c[(b-a)%2]);
    }
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

B

挺难的。

一个精妙的转化：nn 条路径加上 overlinePQ\\overline{PQ}，一定构成一个 n+1n+1 边形。

不管它是凹是凸，其充要条件是任意 nn 条边长度大于剩下那条边。

我们取最长的那条边判一下即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=1e3+5;
int T, n;
double a[N];
PII x, y;
void solve() {
    n=read();
    x.fi=read(), x.se=read();
    y.fi=read(), y.se=read();
    double dis=sqrt(1.0*(y.fi-x.fi)*(y.fi-x.fi)+1.0*(y.se-x.se)*(y.se-x.se));
    rep(i,1,n) a[i]=1.0*read();
    if(n==1) {
        puts(a[1]==dis? "Yes":"No");
        return;
    }
    a[n+1]=dis;
    sort(a+1,a+n+2);
    double sum=0;
    rep(i,1,n) sum+=a[i];
    if(sum<a[n+1]) puts("No");
    else puts("Yes");
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

C

比 A 简单……

如果 nn 是奇数，那么容易想到一种构造方法：全填 ll。此时一定有解。

显然其合法并且最优。

如果 nn 是偶数，考虑一种构造方法：我们填 n−2n-2 个 ll，后面填 22 个 l′l'。其中 l′l' 是满足大于 ll 且l&l'=0的最小的数。这样与和、异或和都是 00。如果 l′>rl' > r 就无解。

显然有 l′=2t>ll' = 2^t > l，2t−1gel2^{t-1} \\ge l。

下证最优性：后两个数不可能更小了，前 n−2n-2 个数不可能更小了，ll 不可能更多了。于是最优。

下证无解性：此时 \[l,r\] 夹处在 \[2^{t-1},2^{t}\] 中间，不可能有与和为 00 的数。故此时无解，既题目无解。

当 n=2n=2 的时候，不存在与和、异或和相等的两个正整数。

考虑每一位的运算，显然。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
ll read() {
   ll a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int T;
ll n, l, r, k;
void solve() {
    n=read(), l=read(), r=read(), k=read();
    if(n&1) {
        printf("%lld\n",l);
        return;
    }
    if(n==2) {
        puts("-1");
        return;
    }
    int i=0;
    while((1ll<<i)<=l||(1ll<<i)&l) i++;
    ll res=1ll<<i;
    if(res<=r) {
        printf("%lld\n",k<=n-2? l:res);
    } else puts("-1");
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

D

难题。

一开始根本无从下手。尝试 DP，发现无法消除“已经选了哪些点”的后效性。

一个高妙的转化：不考虑每个 a_ia\_i 填什么，而是考虑每个操作删掉了哪个点。题目要求的其实是每个删点方案对应的操作区间数量之和。

我们能发现每个操作区间的右端点是唯一确定的，如果要删除点 ii，只需要在 \[i,n\] 中选择一个右端点（对应一个操作），在 \[1,i\] 中选一个左端点（任意）。但是每个右端点只能被选择一次，有后效性。

考虑 DP。设 f(i,j)f(i,j) 表示考虑了区间 \[1,i\] 中的所有点，\[i,n\] 还剩下 jj 个右端点可以选的方案数。

发现无法转移。因为随着 ii 的增长，可能会有的右端点不再能选。

设 f(i,j)f(i,j) 表示考虑区间 \[i,n\] 所有点即可，此时空出来的点以后肯定能选。

讨论当前点删不删即可转移

f(i,j) = \[j>0\]f(i+1,j-1) + f(i+1,j) \\times i \\times (j+1)

答案 sum_i=0nf(1,i)\\sum\_{i=0}^n f(1,i)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
ll read() {
   ll a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=5e3+5;
int T, n;
ll mod, f[N][N];
void solve() {
    n=read(), mod=read();
    rep(i,0,n+1) rep(j,0,n+1) f[i][j]=0;
    f[n+1][0]=1;
    per(i,n,1) rep(j,0,n-i+1) {
        if(j) (f[i][j]+=f[i+1][j-1])%=mod;
        (f[i][j]+=f[i+1][j]*i%mod*(j+1)%mod)%=mod;
    }
    ll ans=0;
    rep(i,0,n) (ans+=f[1][i])%=mod;
    printf("%lld\n",ans);
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

E

推到一半然后失败了。

待补。

觉得这篇文章怎么样？

点个赞，让更多人看到！

分享这篇文章

知识因分享而增值

Twitter Telegram 微博 QQ Facebook LinkedIn

分类

比赛
题解

标签

dp
位运算
构造
计数
贪心

版权声明：本文作者为 如月七海，首发于nanami7.top。

遵循 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

评论区

本评论区由 EveSunMaple自主开发