A. Table with Numbers

题目链接

题意

有一个$l \cdot h$的表格和一个数组$a$，从中选出$2 \cdot k$个数组成$k$个数对，问最多可以有几个数对在表格内

分析

我们设$l$和$h$中较大的那个数为$mx$，较小的数是$mn$，如果$mn \leq a_i \leq mx$那么这个数只能放在mx那一列/行，那么剩下的那个数就要从小于等于$mn$中选择，如果不够和处在$mx$的数配对的话答案就是$a$中小于$mn的个数$而如果足够那就是小于等于$mx$的数除以$2$向下取整

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
    int n,x,y;
    cin>>n>>x>>y;
    vector<int>vt(n+1),flag(n+1);
    int mn=min(x,y);
    int mx=max(x,y);
    int z=0,p=0;
    for(int i=1;i<=n;i++){
        cin>>vt[i];
        if(vt[i]<=mn){
            z++;
            p++;
        }
        else if(vt[i]<=mx ){
            p++;
        }
    }
    cout<<min(z,p/2)<<endl;
}

B. The Curse of the Frog

题目链接

题意

一只青蛙在一个数轴上，要从$0$要跳到$x$，他有$n$中跳跃方式，每种跳跃方式有三个参数:

  • $a$:一次最多能跳$a$格
  • $b$:每使用这个跳跃方式$b$次就会回退
  • $c$:每次回退$c$格
    问最少回退几次才能跳到$x$

分析

我们先把所有“免费”能前进的格子数前进了，即$\sum_{i=1}^n (b_{i}-1)*a_{i}$，再算还剩多少格，跳接下来的格子肯定是选“净前进格子数最大的”，即$max((b_i-1) \cdot a_i -c_i)$，最后就用还要前进的格子数除以这个最大值即可(向上取整)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void solve(){
    int n;
    ll x;
    cin>>n>>x;
    ll f=0;
    ll mx=0;
    for(int i=1;i<=n;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        f += a*(b-1);
        ll js = a*b - c;
        mx=max(mx,js);
    }
    if(f >= x){
        cout<<0<<endl;
        return;
    }
    if(mx <= 0){
        cout<<-1<<endl;
        return;
    }
    ll nd = x - f;
    ll ans = (nd + mx - 1) / mx;
    cout<<ans<<endl;
}

C1. XOR Convenience (Easy Version)

题目链接

题意

输入一个整数$n$，构造出一个排列$p$使得$p_i \oplus i = p_j (2 \leq i \le j \leq n)$ 对于所有$(2 \leq i \leq n-1)$成立

分析

我们把$p_n$设为$1$，那么$p_i(2 \leq i \leq n-1)$就可以设为$i \oplus 1$，照此方法:

  • $i$为奇数$p_i=i-1$
  • $i$为偶数$p_i=i+1$
    $i$为$1$时则选择未选的数
    这样必定能构成一个排列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
    int n;
    cin>>n;
    vector<int>vt(n+2),flag(n+1);
    vt[n]=1;
    flag[1]=1;
    for(int i=2;i<=n-1;i++){
        vt[i]=(i^1);
        flag[i^1]=1;
    }
    for(int i=1;i<=n;i++){
        if(flag[i]==0){
            vt[1]=i;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<vt[i]<<" \n"[i==n];
    }
}

C2. XOR-convenience (Hard Version)

题目链接

题意

在ev的基础上$i$要满足$(1 \leq i \leq n-1)$，如果无法构成排列则输出$-1$

分析

  • 当$n$等于$2$的幂次时，一定不成立，因为$n$不论异或哪个数都会大于$n$，如果$p_n=n$那么$p_{n-1}$一定要等于$n \oplus (n-1)$那么$p_{n-1}$一定会大于$n$，综上$n$是$2$的幂次一定不成立
  • 当$n$为奇数时，参考ev的构造方式，会发现$p_1=n-1$满足条件
  • 当$n$为偶数且不为$2$的幂次时，参考ev的构造方式，这时候$p_1=n$，考虑$n=2^x+r(x是能取到的最大值，比如n的二进制数是1100，那么x就是3，r就是4)$，我们把$p_1和p_r$交换，交换后$p_1=r+1,p_r=n$，$p_1 \oplus 1=r$满足条件，$p_r \oplus r=2^x$,而$2^x$一定在$r$后，所以满足条件

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void solve(){
    int n;
    cin>>n;
    if(((n-1)&n)==0){
        cout<<-1<<endl;
        return;
    }
    vector<int>vt(n+2),flag(n+1);
    vt[n]=1;
    flag[1]=1;
    for(int i=2;i<=n-1;i++){
        vt[i]=(i^1);
        flag[i^1]=1;
    }
    for(int i=1;i<=n;i++){
        if(flag[i]==0){
            vt[1]=i;
        }
    }
    if(n%2==1){
        for(int i=1;i<=n;i++){
            cout<<vt[i]<<" \n"[i==n];
        }   
    }
    else{
        int len=32-__builtin_clz(n);
        int r=n-(1<<(len-1));
        swap(vt[1],vt[r]);
        for(int i=1;i<=n;i++){
            cout<<vt[i]<<" \n"[i==n];
        }
    }
}

D1. Little String (Easy Version)

题目链接

题意

输入一个长度为$n$的二进制字符串$s$，和一个整数$c$，你要找出能构造多少个排列$p$满足以下条件

  • 如果$s_i=’0’$，那么找不到$l$和$r(1 \leq l \leq r \leq n)$满足$MEX([p_l,p_{l+1}, \dots ,p_r])=i$
  • 如果$s_i=’1’$，那么能找到$l$和$r(1 \leq l \leq r \leq n)$满足$MEX([p_l,p_{l+1}, \dots ,p_r])=i$
    如果没有这样的排列或者排列的数量能被$c$整除则输出$-1$，否则将答对$1e9+7$取模

分析

观察到如果$s_1=’0’$或$s_n=’0’$则一定找不到排列，直接输出-1
我们考虑从$0$到$n-1$开始添加数，观察到

  • 当$s_i=’1’$时只能在原来的排列的头或尾中插入，对答案的贡献是$*2$
  • 当$s_i=’0’$时只能在原来的排列中间插入，对答案的贡献是$*(i-1)$
    如果看结果是否会被$c$整除可以多定义一个答案变量对$c$取模看结果是否为$0$，如果为$0$则输出$-1$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int mod=1e9+7;
void solve(){
    int n,k;
    cin>>n>>k;
    int flag=0;
    int mx=1e9+7;
    string s;
    cin>>s;
    if(s[0]=='0' || s[n-1]=='0'){
        cout<<-1<<endl;
        return;
    }
    int ans=1,c=1;
    for(int i=0;i<n-1;i++){
        if(s[i]=='1'){
            ans=(ans*2)%mod;
            c=(c*2)%k;
        }
        else{
            ans=(ans*i)%mod;
            c=(c*i)%k;
        }
    }
    if(c==0){
        cout<<-1<<endl;
        return;
    }
    cout<<ans<<endl;
}