A. Order Something Else

题意

ABC 特有的 A 题题意，容易读错。

有一件商品价格为 PP 元，你可以原价购买，或者多买一件其他商品后以 QQ 元购买。
其他商品的价格为 D1,D2,…,DnD_1,D_2,\ldots,D_n。
请问入手这个商品最少要花多少钱？

解法

答案为 min⁡{P,Q+min⁡Di}\min\{P,Q+\min D_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
26
27
28
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int a[200];

int main(){
    int n=read(),p=read(),q=read();
    for(int i=0;i<n;i++){
        a[i]=read();
    }
    printf("%d\n",min(p,q+*min_element(a,a+n)));
    return 0;
}

B. Strictly Superior

题意

ABC 特有的 B 题题意，语焉不详大模拟。

有 nn 个产品，每个产品有自己的价格 PiP_i 和能执行的功能集合 FiF_i。

两个产品 (i,j)(i,j) 被称为完爆，当且仅当满足如下三个条件：

  • Pi≤PjP_i\le P_j；
  • Fi⊇FjF_i \supseteq F_j；
  • Pi<PjP_i<P_j 或 Fi⊃FjF_i \supset F_j。

求是否有两个产品构成完爆关系？

解法

如果你看不懂这三个条件到底在说什么，不用管，直接三个各自判断一遍，然后且即可。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct Product{
    int p;
    bool func[105];
}a[105];

int main(){
    int n=read(),m=read();
    for(int i=0;i<n;i++){
        a[i].p=read();
        int k=read();
        while(k--){
            a[i].func[read()]=1;
        }
    }

    bool ans = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int ii=i,jj=j;
            // ii 比较便宜，p_ii <= p_jj
            if(a[ii].p>a[jj].p)swap(ii,jj); // 满足了条件 1


            bool flag = 1; // ii 是否有 jj 所有的功能
            bool extra = 0; // ii 是否有 jj 没有的功能
            for(int k=1;k<=m;k++){
                if(!a[ii].func[k] && a[jj].func[k]){
                    flag = 0;
                }
                if(a[ii].func[k] && !a[jj].func[k]){
                    extra=1;
                }
            }

            if(!flag)continue; // 不满足条件 2
            if(a[ii].p<a[jj].p || extra){
                ans=1;
                break;
            }
        }
        if(ans)break;
    }

    if(ans)YES;
    else NO;
    return 0;
}

C. Reversible

题意

两个字符串 S1,S2S_1,S_2 称为本质不同的，当且仅当 S1≠S2S_1 \ne S_2 且 S1≠reverse⁡(S2)S_1 \ne \operatorname{reverse}(S_2)。
给定 nn 个字符串，求出里面有几个是本质不同的。

解法

显然用 set 维护即可。（如果你拒绝使用 STL，可以用哈希+哈希表维护。）

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
34
35
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

set<string> vis;
int ans = 0;
int main(){
    int n=read();
    for(int i=0;i<n;i++){
        string x;cin>>x;
        if(!vis.count(x)){
            ans++;
            vis.insert(x);
            reverse(x.begin(),x.end());
            vis.insert(x);
        }
    }

    printf("%d\n",ans);
    return 0;
}

D. Peaceful Teams

题意

有 NN 个人，MM 组敌人，敌人不能分在一个队里面。

请问：把 NN 个人分进 TT 个队，有几种不同的方案？我们称两个方案为不同的，当且仅当存在两个人在一个方案分在同队，在另一个方案分在不同队伍。

解法

暴力 DFS，从 1∼T1\sim T，枚举每个队里面有哪些人，用位运算代表这个集合。

复杂度 O(能过)O(\text{能过})。（利用我贫瘠的数学知识，无法证明复杂度对不起）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int t,n,m;
int bad[105];
int remain;
ll ans;

void dfs(int dep){
    if(remain==0)return;
    if(dep==t-1){ // 最后一个队，全放进去
        for(int i=0;i<m;i++){ 
            if((remain&bad[i])==bad[i]){
                return;
            }
        }
        ans++;
        return;
    }

    for(int S0=remain;S0;S0=(S0-1)&remain){ // 枚举子集
        bool ok = 1;
        for(int i=0;i<m;i++){
            if((S0&bad[i])==bad[i]){
                ok=0;
                break;
            }
        }
        if(!ok)continue;

        remain &= ~S0;
        dfs(dep+1);
        remain |= S0;
    }
}

int main(){
    n=read(),t=read(),m=read();
    for(int i=0;i<m;i++){
        int a=read(),b=read();
        bad[i]= (1<<a)|(1<<b);
    }

    for(int i=1;i<=n;i++)remain|=(1<<i);

    dfs(0);

    for(int i=2;i<=t;i++)ans/=i;
    printf("%lld\n",ans);
    return 0;
}

E. NAND repeatedly

题意

你好，请问喜欢不满足结合律的运算吗？

A⊼BA \barwedge B 为与非运算。A⊼B=¬(A∧B)A \barwedge B = \neg (A \wedge B)。具体来说，1⊼1=0,0⊼1=1,1⊼0=1,0⊼0=11 \barwedge 1=0,0 \barwedge 1=1,1 \barwedge 0=1,0 \barwedge 0=1。注意此运算不满足结合律。

现在给出一个 0−10-1 序列 A1,A2,…,AnA_1,A_2,\ldots,A_n。定义 f(i,j)=(((Ai⊼Ai+1)⊼Ai+2)… )⊼Ajf(i,j)=(((A_i \barwedge A_{i+1}) \barwedge A_{i+2})\dots)\barwedge A_{j}，特别的，若 i=ji=j，f(i,j)=Aif(i,j)=A_i。

求对于所有 1≤i≤j≤n1\le i \le j \le n，f(i,j)f(i,j) 的总和。

解法

f(i,j)f(i,j) 的总和等价于 f(i,j)=1f(i,j)=1 的 (i,j)(i,j) 个数。

进行动态规划。设 dp[i][0/1]dp[i][0/1] 代表第 ii 位时运算结果已经是 0/10/1 时，后面有几个右端点（包括 ii）可以满足 f(?,j)=1f(?,j)=1。（这里的运算结果指的是第 ii 位前面的某些位已经与非过，到 ii 位时变为了 0/10/1）

有转移方程式：

dp[i][1]=1+dp[i+1][1⊼Ai+1]dp[i][0]=dp[i+1][0⊼Ai+1]dp[i][1]=1+dp[i+1][1\barwedge A_{i+1}]\\ dp[i][0]=dp[i+1][0\barwedge A_{i+1}]

最终答案为

∑i=1ndp[i][Ai]\sum_{i=1}^n{dp[i][A_i]}

复杂度 O(n)O(n)。

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
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e6+5;
ll dp[N][2];
char s[N];

int main(){
    int n=read();
    scanf("%s",s);

    dp[n-1][1]=1;
    for(int i=n-2;i>=0;i--){
        if(s[i+1]=='1')dp[i][1]=1+dp[i+1][0];
        else           dp[i][1]=1+dp[i+1][1];

        if(s[i+1]=='1')dp[i][0]=dp[i+1][1];
        else           dp[i][0]=dp[i+1][1];
    }

    ll ans = 0;
    for(int i=0;i<n;i++){
        ans += dp[i][s[i]-'0'];
    }
    printf("%lld\n",ans);
    return 0;
}

F. Make 10 Again

题意

有 n (1≤n≤100)n\ (1\le n \le 100) 个骰子，每个骰子等概率骰出 1∼ai (1≤ai≤106)1\sim a_i\ (1\le a_i\le 10^6) 中的一个数。求：有多少概率骰子上的 nn 个数中某些的和为 1010？

由于概率是一个分数，请进行分数取模。

解法

前置知识：乘法逆元。
分数取模：

pq≡pq−1(modM)\dfrac{p}{q} \equiv pq^{-1} \pmod M

这个东西有很良好的性质，取模之后随便乘除都是正确的。这里我们选择线性求出 1∼1061\sim 10^6 的逆元即可。（观察到等会分母一定小于 10610^6）。

这题正解是状压 dp。

设 dp[i][S]dp[i][S] 表示骰到第 ii 个骰子时，当前骰子上的数能且仅能表示集合 SS 的概率。这里 SS 用状态压缩，且 S⊆{0,1,2,3,4,5,6,7,8,9,10}S\subseteq \{0,1,2,3,4,5,6,7,8,9,10\}。

初始条件 dp[0][{0}]=1dp[0][\{0\}]=1。

接下来我们考虑从 dp[i]dp[i] 转移到 dp[i+1]dp[i+1]。

如果第 i+1i+1 颗骰子骰出了 k (k≤10)k\ (k\le 10)，则新的能表示的集合

S′=S∪{x∣x−k∈s}S'=S\cup \{x|x-k\in s\}

则 dp[i+1][S′]dp[i+1][S'] 需要加上 dp[i][S]⋅1ai+1dp[i][S] \cdot \dfrac{1}{a_{i+1}}

对于骰出 1010 以上的情况，显然 SS 不会变化。
则往 dp[i+1][S]dp[i+1][S] 加上 dp[i][S]⋅ai+1−10ai+1dp[i][S] \cdot \dfrac{a_{i+1}-10}{a_{i+1}} 即可。

最终答案为 ∑10∈Sdp[n][S]\displaystyle \sum_{10\in S}dp[n][S]。

复杂度 O(10n210)O(10n2^{10})。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int MOD = 998244353;
const int N = 105;
int a[N];

ll dp[N][2048];
int inv[1'000'000+10];

void init(int n){
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
}

// 返回 p/q 的取模结果
ll frac(ll p,ll q){ 
    return (p*inv[q])%MOD;
}

int main(){
    init(1e6+5);

    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }

    dp[0][1]=1;

    for(int i=0;i<n;i++){
        for(int j=0;j<2048;j++){
            for(int k=1;k<=min(10,a[i+1]);k++){ // 如果骰出的是 k
                int newj = 0; // 新的 j
                for(int m=0;m<=10;m++){
                    if((j>>m)&1) newj |= (1<<m);
                    if(m-k>=0 && ((j>>(m-k))&1)) newj |= (1<<m);
                }

                dp[i+1][newj] += dp[i][j] * frac(1,a[i+1]);
                dp[i+1][newj] %= MOD;
            }
            if(a[i+1]>10){
                dp[i+1][j]+=dp[i][j]*frac(a[i+1]-10,a[i+1]);
                dp[i+1][j]%=MOD;
            }
        }
    }

    ll ans = 0;
    for(int i=1024;i<2048;i++){
        ans = (ans+dp[n][i])%MOD;
    }
    printf("%lld\n",ans);
    return 0;
}