CF Round 1035 Div2 个人题解

A

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

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

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

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

如果 $x \le y$ ，那么我们全部使用操作 $1$ 即可。

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

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

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define eb emplace_back
10
#define ef emplace_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
int T, a, b, x, y;
25
int c[2];
26
void solve() {
27
    a=read(), b=read(), x=read(), y=read();
28
    if(a>b&&(a^1)!=b) {
29
        puts("-1");
30
        return;
31
    }
32
    if(a>b) {
33
        printf("%d\n",y);
34
        return;
35
    }
36
    ll ans=0;
37
    if(x<=y) {
38
        printf("%d\n",(b-a)*x);
39
    } else {
40
        if(a==b) {
41
            puts("0");
42
            return;
43
        }
44
        if(a&1) c[0]=y, c[1]=x;
45
        else c[0]=x, c[1]=y;
46
        printf("%d\n",(b-a)/2*(x+y)+(b-a)%2*c[(b-a)%2]);
47
    }
48
}
49
signed main() {
50
    T=read();
51
    while(T--) solve();
52
    return 0;
53
}

B

挺难的。

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

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

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

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define eb emplace_back
10
#define ef emplace_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=1e3+5;
25
int T, n;
26
double a[N];
27
PII x, y;
28
void solve() {
29
    n=read();
30
    x.fi=read(), x.se=read();
31
    y.fi=read(), y.se=read();
32
    double dis=sqrt(1.0*(y.fi-x.fi)*(y.fi-x.fi)+1.0*(y.se-x.se)*(y.se-x.se));
33
    rep(i,1,n) a[i]=1.0*read();
34
    if(n==1) {
35
        puts(a[1]==dis? "Yes":"No");
36
        return;
37
    }
38
    a[n+1]=dis;
39
    sort(a+1,a+n+2);
40
    double sum=0;
41
    rep(i,1,n) sum+=a[i];
42
    if(sum<a[n+1]) puts("No");
43
    else puts("Yes");
44
}
45
signed main() {
46
    T=read();
47
    while(T--) solve();
48
    return 0;
49
}

C

比 A 简单……

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

显然其合法并且最优。

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

显然有 $l' = 2^t > l$ ， $2^{t-1} \ge l$ 。

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

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

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

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

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define eb emplace_back
10
#define ef emplace_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
ll read() {
16
   ll a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
int T;
25
ll n, l, r, k;
26
void solve() {
27
    n=read(), l=read(), r=read(), k=read();
28
    if(n&1) {
29
        printf("%lld\n",l);
30
        return;
31
    }
32
    if(n==2) {
33
        puts("-1");
34
        return;
35
    }
36
    int i=0;
37
    while((1ll<<i)<=l||(1ll<<i)&l) i++;
38
    ll res=1ll<<i;
39
    if(res<=r) {
40
        printf("%lld\n",k<=n-2? l:res);
41
    } else puts("-1");
42
}
43
signed main() {
44
    T=read();
45
    while(T--) solve();
46
    return 0;
47
}

D

难题。

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

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

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

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

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

设 $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=0}^n f(1,i)$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define eb emplace_back
10
#define ef emplace_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
ll read() {
16
   ll a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=5e3+5;
25
int T, n;
26
ll mod, f[N][N];
27
void solve() {
28
    n=read(), mod=read();
29
    rep(i,0,n+1) rep(j,0,n+1) f[i][j]=0;
30
    f[n+1][0]=1;
31
    per(i,n,1) rep(j,0,n-i+1) {
32
        if(j) (f[i][j]+=f[i+1][j-1])%=mod;
33
        (f[i][j]+=f[i+1][j]*i%mod*(j+1)%mod)%=mod;
34
    }
35
    ll ans=0;
36
    rep(i,0,n) (ans+=f[1][i])%=mod;
37
    printf("%lld\n",ans);
38
}
39
signed main() {
40
    T=read();
41
    while(T--) solve();
42
    return 0;
43
}

E

推到一半然后失败了。

待补。

A

B

C

D

E

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

觉得这篇文章怎么样？

分享这篇文章

评论区