1002.Binary Number

字符串、贪心

题意

给定一段长度为$n$的01串，首位保证为1
任选定其中任意长的一段并将其反转
必须执行以上操作$k$次，求操作后得到的01串表示的二进制数最大的状态并输出

解题思路

首先考虑次数不足的情况。对于一个二进制数，高位的权重大于其所有低位权重之和。因此优先考虑将靠前的字符中的0反转为1。

接下来比较多次反转不同方案的优劣。忽略操作次数限制，考虑这个字符串：1001001001

  1. 最直观的办法是直接选定第2-3,5-6,8-9位反转为1，得到全1串。
  2. 还有一种可选的优质方法:1001001001 $\Rightarrow$ 1110110111 $\Rightarrow$ 11100111 $\Rightarrow$ 1111111111

上述两种方法对于同样3段的0，次数相同，并且第一种方法更便于考虑，故采取第一种策略，从左往右反转0。

接下来再考虑已经转化为全1串，次数溢出的情况。可以考虑在转换过程中做无效操作浪费次数，避免对最大结果造成影响。

  1. 对于起始01串，如果有0必有前导1(首位保证为1)。因此可以在反转某段0时带上前导1一起，再消耗1次操作单独转回前导1，可以浪费1次数
  2. 对于单个1做2次反转操作，可以浪费2次数
  3. 对于连续的2个1，分两次单独反转这两个1，然后一起翻回，可以浪费3次数

在以上策略的搭配下，正常情况下可以消耗任意溢出次数，并最终状态为全1

最后考虑特殊情况

  1. 当起始01串全为1，且$k=1$，此时只能反转末位1使损失最小
  2. 当01串长度为1，此时起始01串只能是"1"，其状态只由$k$的奇偶决定

(P.S.)谁赛时程序中把’='写成"=="又不想Remake于是卡签一个半小时我不说

时间复杂度

$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
int solve()
{
    string s,re;
    ll n,k;
    cin >> n >> k;
    cin >> s;
    s.push_back(0);
    ll flag=0,all1=1;
    FORLL(i,0,n-1){
        if(s[i]=='0'){
            if(flag==0&&k) {k--;flag=1;}
            if(flag) re.push_back('1');
            else re.push_back('0');
            all1=0;
        }
        else{
            re.push_back('1');
            flag=0;
        }
    }
    if(k==1&&all1) re[n-1]='0';
    if((k%2)&&n==1) re[0]='0';
    cout << re << endl;
    return 0;
}

1004.Card Game

思维题

题意

游戏规则和汉诺塔类似
有 $n$ 根柱子，起始在第1根柱子上从下到上摆放着编号 $k,k-1,\cdots,2,1$ 的卡牌
规定：每根柱子只能从下到上放编号连续且递减的卡牌
每次操作可以将一根柱子上的最顶端的卡牌移动到其他柱子上（且不能违反规定）
求对于给定的柱子根数 $n$ ，可以实现将第一根柱子上所有牌移动到第二根柱子上的最大卡牌张数 $k$

解题思路

这道题可以采用逆向思维。
起始态和最终态同构，拆解和合并过程对称，考虑从中间关键步骤分解顺推：

  1. 将最大点数的卡牌从 柱子$1$ 转移到 柱子$2$
  2. 此时有 $1$ 个空位，可以将牌数为 $2$ 的柱子（假设他们恰好是次大的）拆分合并到柱子 $2$ ，并产生一个新的空位……
  3. 每次完全合并一个柱子，就会多一个空位，空位多的状态包含了空位少的状态。考虑状态转移关系：
    1. 记：利用 $x$ 个空位可以转移到目标柱子的最大牌数为 $f(x)$
      显然： $f(0)=1$
    2. 假设目前有个 $x$ 空位，对于本轮要转移的柱子，可以先借用一个空位存储上半部分较小卡牌。存储数量为 $f(x-1)$ ，因为存储本身需要占用一个空位
    3. 利用剩余 $x-1$ 个空位，最多可以转移并合并 $f(x-1)$ 张卡牌到柱子 $2$
    4. 再利用剩余 $x-1$ 个空位，将存储的 $f(x-1)$ 张卡牌到柱子 $2$
    5. 综3.1-3.4，可以得到 $f(x)$ 的递推式： $f(x)=2f(x-1)$
      并求得 $f(x)=2^n$
  4. 第一步可以看作：利用 $0$ 个空位，将最大点数的卡牌从 柱子$1$ 转移到 柱子$2$
    最后一步可以看作：利用 $n-2$ 个空位，将最后一堆卡牌从转移到 柱子$2$
    中途每一步产生 $1$ 个空位
    由此得到结果：

$$\begin{align}
k
&=\sum\limits_{i=0}^{n-2} f(i) \newline
&=1+2+\cdots+2^{n-2} \newline
&=2^{n-1}-1
\end{align}
$$

快速幂斩了

参考程序

1
2
3
4
5
6
7
8
9
int solve()
{
    ll n;
    cin >> n;
    cout << Get_Mod(qcpow(2,n-1)-1) << endl;
    //快速幂代码略
    return 0;
}

1007.foreverlasting and fried-chicken

图论、枚举

题意

给定一个无权无向图 $G=(V,E),|V|=n,|E|=m$
求图中包含以下子图的数量：
Img

解题思路

对于这个子图，有一个度为4的点和一个度为6的点，他们有4个公共邻居。借助这个特征，在给定无向图中找点

构图，在过程中记录每个点的度数 $deg_i$

对于每个 $deg_1\ge6$ 的点 $v_1$ ，枚举 $deg_2\ge4$ 的点 $v_2$
计算公共邻居个数，记为 $nbr$
对于 $v_1,v_2$ ，其含有上述子图个数为：$C_{nbr}^4 \cdot C_{deg_1-4}^2$
（注意：如果 $v_1,v_2$ 相连，这条边是不允许被构入子图的，计算的度是要减去1）

计算每一对 $v_1,v_2$ 的个数之和即可

时间复杂度

朴素的做法的时间复杂度是 $O(n^3)$ （会有人T到飞起）
考虑用bitset对图进行状态压缩，降低求 $nbr$ 的时间复杂度
最终时间复杂度为 $O(\dfrac{n^3}{\omega})$

参考程序

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
ll C[1005][1005]={0};
//在主函数中预处理组合数C，代码略
int solve()
{
    ll n,m;
    cin >> n >> m;
    bitset<1005> G[1005];
    int deg[1005]={0};
    ll u,v;
    FORLL(i,1,m){
        cin >> u >> v;
        G[u].set(v);
        G[v].set(u);
        deg[u]++;deg[v]++;
    }
    ll re=0,nbr,deg1,deg2;
    FORLL(i,1,n) if(deg[i]>=4){
        FORLL(j,i+1,n) if(j-i&&deg[j]>=4){
            deg1=deg[i]-G[i][j];
            deg2=deg[j]-G[i][j];
            //如果vi,vj直接相连，这条边是不能构入的
            nbr=(G[i]&G[j]).count();
            if(nbr>=4){
                if(deg1>=6) re=add(re,mul(C[nbr][4],C[deg1-4][2]));
                if(deg2>=6) re=add(re,mul(C[nbr][4],C[deg2-4][2]));
            }
        }
    }

    cout << re << endl;
    return 0;
}

1009.String Problem

字符串、签到

题意

给定一个字符串 $S$，仅包含小写字母
在其中选择 $S$ 的 $k$ 个回文非空子串，且它们成对不相交，可以得到等同于 所选子串的长度之和减去子串数量 的分数：$\sum\limits_{i=1}^k len(s_i) -k$
为了让这道题成为签到题《增加题目难度》，所选子串最多包含一个字符，求对于给定字符串，可以获得的最高分数

解题思路

在增加难度后，很难想到所选的每一子串就是连续相同字符
答案即给定字符串长度减去连续相同字符段数

参考程序

1
2
3
4
5
6
7
8
9
10
11
12
int solve()
{
    string s;
    cin >> s;
    ll len=s.size();
    ll cnt=1;
    FORLL(i,1,len-1){
        if(s[i]!=s[i-1]) {cnt++;}
    }
    cout << len-cnt << endl;
    return 0;
}