21~23集训测试题总结

标签：ch return 21 测试题 int 23 else include dp

23集训测试题(10.8)

密码锁

这题数据量较小，可以直接暴力枚举所有密码情况并一一判断

暴力代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;
struct L
{
    int state[6] ;
    bool operator<(const L& b) const
    {
        for(int i = 1 ; i <= 5 ; ++i)
        {
            if(state[i] != b.state[i])
                return state[i] < b.state[i] ;
        }
        return false ;
    }
    bool operator==(const L& b) const
    {
        for(int i = 1 ; i <= 5 ; ++i)
            if(state[i] != b.state[i])
                return false ;
        return true ;
    }
} all[9] ;
int n = 0 ;
L now ;
bool vis[9] = {} ;
int cnt = 0 ;
bool check()
{
    memset(vis , 0 , sizeof vis) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(now == all[i])
            return false ;
        L temp = now ;
        bool flag = false ;
        for(int k = 1 ; k <= 5 ; ++k)
        {
            while(temp.state[k] != all[i].state[k])
            {
                flag = true ;
                ++temp.state[k] ;
                if(temp.state[k] == 10)
                    temp.state[k] = 0 ;
            }
            if(flag)
                break ;
        }
        if(temp == all[i])
        {
            vis[i] = true ;
            continue ;
        }
        temp = now ;
        flag = false ;
        for(int k = 1 ; k <= 4 ; ++k)
        {
            while(temp.state[k] != all[i].state[k])
            {
                flag = true ;
                ++temp.state[k] ;
                ++temp.state[k + 1] ;
                if(temp.state[k] == 10)
                    temp.state[k] = 0 ;
                if(temp.state[k + 1] == 10)
                    temp.state[k + 1] = 0 ;
            }
            if(flag)
                break ;
        }
        if(temp == all[i])
            vis[i] = true ;
        if(!vis[i])
            return false ;
    }
    return true ;
}
int main()
{
    freopen("lock.in" , "r" , stdin) ;
    freopen("lock.out" , "w" , stdout) ;
    scanf("%d" , &n) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= 5 ; ++j)
        {
            scanf("%d" , &all[i].state[j]) ;
        }
    }
    sort(all + 1 , all + n + 1) ;
    for(int a = 0 ; a <= 9 ; ++a)
    {
        for(int b = 0 ; b <= 9 ; ++b)
        {
            for(int c = 0 ; c <= 9 ; ++c)
            {
                for(int d = 0 ; d <= 9 ; ++d)
                {
                    for(int e = 0 ; e <= 9 ; ++e)
                    {
                        now.state[1] = a , now.state[2] = b , now.state[3] = c , now.state[4] = d , now.state[5] = e ;
                        if(check())
                        {
                            ++cnt ;
                        }
                    }
                }
            }
        }
    }
    printf("%d\n" , cnt) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

但是这题其实也可以使用计数DP

我们可以枚举转动幅度计数，最终状态就是正确答案当且仅当它能通过n个状态转移过来

代码

#include<iostream>
using namespace std ;
#define N 11
#define MOD 10
int n = 0 , ans = 0 , dp[N][N][N][N][N] = {} ;
int main()
{
    freopen("lock.in" , "r" , stdin) ;
    freopen("lock.out" , "w" , stdout) ;
    scanf("%d" , &n) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        int a = 0 , b = 0 , c = 0 , d = 0 , e = 0 ;
        scanf("%d%d%d%d%d" , &a , &b , &c , &d , &e) ;
        for(int j = 1 ; j <= 9 ; ++j)
        {
            ++dp[(a + j) % MOD][b][c][d][e] ;
            ++dp[a][(b + j) % MOD][c][d][e] ;
            ++dp[a][b][(c + j) % MOD][d][e] ;
            ++dp[a][b][c][(d + j) % MOD][e] ;
            ++dp[a][b][c][d][(e + j) % MOD] ;
            ++dp[(a + j) % MOD][(b + j) % MOD][c][d][e] ;
            ++dp[a][(b + j) % MOD][(c + j) % MOD][d][e] ;
            ++dp[a][b][(c + j) % MOD][(d + j) % MOD][e] ;
            ++dp[a][b][c][(d + j) % MOD][(e + j) % MOD] ;
        }
    }
    for(int i = 0 ; i <= 9 ; ++i)
        for(int j = 0 ; j <= 9 ; ++j)
            for(int k = 0 ; k <= 9 ; ++k)
                for(int u = 0 ; u <= 9 ; ++u)
                    for(int v = 0 ; v <= 9 ; ++v)
                        if(dp[i][j][k][u][v] == n)
                            ++ans ;
    printf("%d" , ans) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

消消乐

考场35分思路：

暴力枚举每一个区间并判断是否可以消除，复杂度 O(n³) 。

考场代码：

#include<iostream>
#include<stack>
using namespace std ;
int n = 0 ;
char s[2000010] = {} ;
int cnt = 0 ;
bool check(int l , int r)
{
    int cntch[27] = {} ;
    for(int i = l ; i <= r ; ++i)
        ++cntch[s[i] - 'a' + 1] ;
    for(int i = 1 ; i <= 26 ; ++i)
        if(cntch[i] % 2)
            return false ;
    stack<char> era ;
    while(l <= r)
    {
        if(era.empty() || era.top() != s[l])
            era.push(s[l]) ;
        else
            era.pop() ;
        ++l ;
    }
    return era.empty() ;
}
int main()
{
    freopen("game.in" , "r" , stdin) ;
    freopen("game.out" , "w" , stdout) ;
    scanf("%d" , &n) ;
    scanf("%s" , s + 1) ;
    for(int i = 1 ; i <= n - 1 ; ++i)
    {
        for(int j = i + 1 ; j <= n ; ++j)
        {
            if(check(i , j))
            {
                ++cnt ;
            }
        }
    }
    printf("%d\n" , cnt) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

稍微优化一些：

观察我们所枚举的区间，我们可以发现这个思路的时间瓶颈就在于枚举区间过多所以我们可以考虑减少枚举次数来进行优化，我们发现在进行 i 的枚举时我们需要向后遍历整个字符串，所以事实上我们可以省略尾节点 j 的枚举再进行遍历时同时判断，这样就可以将复杂度降至 O(n²) ，分数变为50分

50分代码：

#include<iostream>
using namespace std ;
int n = 0 ;
char s[2000010] = {} ;
int cnt = 0 ;
char st[2000010] = {}; ;
int main()
{
    freopen("game.in" , "r" , stdin) ;
    freopen("game.out" , "w" , stdout) ;
    scanf("%d" , &n) ;
    scanf("%s" , s + 1) ;
    for(int i = 1 ; i <= n - 1 ; ++i)
    {
        int top = 0 ;
        for(int j = i ; j <= n ; ++j)
        {
            if(s[j] == st[top])
                --top ;
            else
                st[++top] = s[j] ;
            if(top == 0)
                ++cnt ;
        }
    }
    printf("%d\n" , cnt) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

最终思路：

在经过刚才的优化过后，我们发现减少枚举次数（事实上是大大减少了判断次数）可以优化代码的时间复杂度，但是这种边枚举边判断的方法复杂度没有办法突破 O(n²) ，因此我们需要另找思路。再次审题，这是一道字符串的题目，并且涉及到首尾字符匹配消除，我们就很自然可以联想到 KMP 算法，因此我们考虑将字符串从头扫到尾用类似于 KMP 中 fail 数组的一个 jump 数组记录每一个字符最后失配位置并同时向前扫描字符串，用一个 dp 数组记录到当前字符的合法（即可消除的）子段数，并用 cnt 累加记录答案，时间复杂度 O(|$\Sigma$|n) 。

最终代码：

#include<iostream>
using namespace std ;
int n = 0 ;
char s[2000010] = {} ;
long long cnt = 0 ;
char st[2000010] = {};
bool vis[27] = {} ;
int jump[2000010] = {} , dp[2000010] = {} ;
int main()
{
    freopen("game.in" , "r" , stdin) ;
    freopen("game.out" , "w" , stdout) ;
    scanf("%d" , &n) ;
    scanf("%s" , s + 1) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(vis[s[i] - 'a' + 1])
        {
            int j = i - 1 ;
            while(s[j] != s[i] && j > 0)
                j = jump[j] - 1 ;
            if(j > 0)
                jump[i] = j , dp[i] = dp[j - 1] + 1 ;
            cnt += dp[i] ;
        }
        else
            vis[s[i] - 'a' + 1] = true ;
    }
    printf("%lld\n" , cnt) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

词典

考场思路：

题目要求判断每个字符串通过交换字母顺序是否能比其他字符串在交换字母顺序之后的字典序都小，在看了数据范围后，我们发现显然暴力枚举不同交换方法进行比较是一定会超时的，因此要再仔细想一下。根据题意，我们发现每个字符串中的字母都可以任意交换，即每个字符串都能排成本身的最小字典序与最大字典序，因此我们可以考虑在输入时进行预处理，将每个字符串都变成最大字典序形式，并在每次判断前将其转换成最小的与其他字符串进行比较，时间复杂度为 O(n² + nm$log$m) 。

考场代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;
int n = 0 , m = 0 ;
char dict[3005][3005] = {} ;
bool cmp(char a , char b)
{
    return a > b ;
}
bool check(int now)
{
    for(int i = 1 ; i <= n ; ++i)
    {
        if(i == now)
            continue ;
        int j = 1 ;
        while(dict[now][j] == dict[i][j])
            ++j ;
        if(dict[now][j] > dict[i][j])
            return false ;
    }
    return true ;
}
int main()
{
    freopen("dict.in" , "r" , stdin) ;
    freopen("dict.out" , "w" , stdout) ;
    scanf("%d%d" , &n , &m) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%s" , dict[i] + 1) ;
        sort(dict[i] + 1 , dict[i] + m + 1 , cmp) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        reverse(dict[i] + 1 , dict[i] + m + 1) ;
        printf("%d" , check(i)) ;
        reverse(dict[i] + 1 , dict[i] + m + 1) ;
    }
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

更优的思路：

其实，在进行字典序比较时，我们最重要的是看最大字母与最小字母，所以根据贪心思想，我们只需在输入时预处理出每个字符串中最大的与最小的字母，在判断时比较当前字符串最小字母与其他字符串的最大字母，即可得出答案，时间复杂度 O(n²) 。

优化代码：

#include<iostream>
using namespace std ;
int n = 0 , m = 0 ;
char str[3010] = {} ;
int mins[3010] = {} , maxs[3010] = {};
int main()
{
    freopen("dict.in" , "r" , stdin) ;
    freopen("dict.out" , "w" , stdout) ;
    scanf("%d%d" , &n , &m) ;
    for (int i = 1 ; i <= n ; ++i)
    {
        scanf("%s" , str) ;
        for (int j = 0 ; j < m ; ++j)
        {
            if (j == 0)
                mins[i] = maxs[i] = str[j] - 'a' ;
            else
            {
                mins[i] = min(mins[i] , str[j] - 'a') ;
                maxs[i] = max(maxs[i] , str[j] - 'a') ;
            }
        }
    }
    for (int i = 1 ; i <= n ; ++i)
    {
        bool flag = true ;
        for (int j = 1 ; j <= n ; ++j)
        {
            if (i == j)
                continue ;
            if (mins[i] < maxs[j])
                continue ;
            else
            {
                flag = false ;
                printf("0") ;
                break ;
            }
        }
        if (flag)
            printf("1") ;
    }
    return 0 ;
}

三值逻辑

考场思路：

这题似乎不是很好写，试一下暴力模拟，但是不知道怎么挂了几个点，具体见代码

考场代码：

#include<iostream>
using namespace std ;
char readch()
{
    char ch ;
    ch = getchar() ;
    while(ch != '-' && ch != '+' && ch != 'T' && ch != 'F' && ch != 'U')
        ch = getchar() ;
    return ch ;
}
struct tri
{
    short c ;   //1 : true , 2 : false , 3 : unknown
    // int operator!()
    // {
    //     if(c == 1)
    //         return 2 ;
    //     else if(c == 2)
    //         return 1 ;
    //     else
    //         return 3 ;
    // }
    // void operator=(char val)
    // {
    //     if(val == 'T')
    //         c = 1 ;
    //     else if(val == 'F')
    //         c = 2 ;
    //     else if(val == 'U')
    //         c = 3 ;
    // }
    void scan()
    {
        short x = 0 ;
        scanf("%hd" , &x) ;
        c = x ;
    }
    void print()
    {
        printf("%hd" , c) ;
    }
} all[100005] ;
struct op
{
    char v ;
    int i , j ;
    void scan()
    {
        v = readch() ;
        // scanf("%d%d" , &i , &j) ;
        if(v == 'T' || v == 'F' || v == 'U')
            scanf("%d" , &i) ;
        else
            scanf("%d%d" , &i , &j) ;
    }
    void perf()
    {
        if(v == '+')
            all[i].c = all[j].c ;
        else if(v == '-')
        {
            if(all[j].c == 1)
                all[i].c = 2 ;
            else if(all[j].c == 2)
                all[i].c = 1 ;
            else if(all[j].c == 3)
                all[i].c = 3 ;
        }
        else
        {
            if(v == 'T')
                all[i].c = 1 ;
            else if(v == 'F')
                all[i].c = 2 ;
            else if(v == 'U')
                all[i].c = 3 ;
        }
    }
} ope[100005] ;
int c = 0 , t = 0 ;
int n = 0 , m = 0 ;
int cnt = 0 ;
bool flag = false ;
tri temp[100005] ;
void dfs(int now)
{
    if(flag)
        return ;
    if(now == n + 1)
    {
        for(int i = 1 ; i <= n ; ++i)
        {
            temp[i].c = all[i].c ;
        }
        for(int i = 1 ; i <= m ; ++i)
        {
            ope[i].perf() ;
        }
        for(int i = 1 ; i <= n ; ++i)
        {
            if(all[i].c != temp[i].c)
            {
                cnt = 0 ;
                return ;
            }
            if(all[i].c == 3)
                ++cnt ;
        }
        // printf("\n") ;
        // for(int i = 1 ; i <= n ; ++i)
        //     all[i].print() , printf(" ") ;
        // printf("\n") ;
        flag = true ;
        return ;
    }
    for(int i = 1 ; i <= 3 ;++i)
    {
        all[now].c = i ;
        dfs(now + 1) ;
        if(flag)
            return ;
    }
}
int main()
{
    freopen("tribool.in" , "r" , stdin) ;
    freopen("tribool.out" , "w" , stdout) ;
    scanf("%d%d" , &c , &t) ;
    while(t--)
    {
        flag = false ;
        cnt = 0 ;
        scanf("%d%d" , &n , &m) ;
        for(int i = 1 ; i <= m ; ++i)
            ope[i].scan() ;
        dfs(1) ;
        printf("%d\n" , cnt) ;
    }
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

正解思路：

大体思路是先按照题意模拟，给所有输入的操作的相关变量用并查集标记，然后我们可以发现在并查集查询操作前我们就可以确定哪些变量的值是确定的，哪些是不确定的，这时我们的任务就是最小化不确定的变量中 U 的个数那哪些情况的变量它的值一定是 U 呢？总的来说有两种：

x 的祖先是 −x。
x 的祖先是 U。

我们把这两种情况查询出来，再统计个数，就是最终答案了！由于 x 的值可能我们可能标记成负数了，所以并查集查询时遇到负数要取相反数，不然就会运行错误

由于我们要查询的 x 的祖先有可能是 -x，取相反数后又是 x，这样就会陷入死循环。于是我们需要用 vis 数组记录是否到过这个点的相反数（其实就是上面所写的情况1）。由于 vis 记录的值也有负数，所以我们要给记录的值统一加上一个 n 把其全变成正数。这时需要注意 vis 数组的大小要开到 2n。其余细节见代码

代码：

#include<iostream>
#define int long long
using namespace std;
const int T = 100001, F = -100001, U = 0;
int c = 0, t = 0, n = 0, m = 0, a = 0, b = 0, fa[100005] = {};
char ch[100005] = {};
bool vis[300005] = {};
int find(int x)
{
    int ret;
    if (x == T || x == F)
        ret = x;
    else if (vis[n - x] || x == U)
        ret = U;
    else if (vis[x + n])
        ret = T;
    else if (x < 0)
    {
        if (x == -fa[-x])ret = x;
        else
        {
            vis[x + n] = 1;
            ret = find(-fa[-x]);
            vis[x + n] = 0;
        }
    }
    else
    {
        if (x == fa[x])
            ret = x;
        else
        {
            vis[x + n] = 1;
            ret = fa[x] = find(fa[x]);
            vis[x + n] = 0;
        }
    }
    return ret;
}
signed main()
{
    freopen("tribool.in", "r", stdin) ;
    freopen("tribool.out", "w", stdout) ;
    scanf("%lld%lld", &c, &t) ;
    while (t--)
    {
        scanf("%lld%lld", &n, &m) ;
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        for (int i = 1; i <= m; i++)
        {
            cin>>ch[i] ;
            if (ch[i] == 'T')
            {
                scanf("%lld", &a) ;
                fa[a] = T;
            }
            else if (ch[i] == 'F')
            {
                scanf("%lld", &a) ;
                fa[a] = F;
            }
            else if (ch[i] == 'U')
            {
                scanf("%lld", &a) ;
                fa[a] = U;
            }
            else
            {
                scanf("%lld%lld", &a, &b) ;
                if (ch[i] == '+')
                    fa[a] = fa[b];
                else
                    fa[a] = -fa[b];
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (find(i) == U)
                ++ans;
        }
        printf("%lld\n", ans) ;
    }
    fclose(stdin) ;
    fclose(stdout) ;
    return 0;
}

22集训测试题(10.9)

种花

考场思路：

显然，我们可以根据题目要求直接暴力枚举所有可能的 x₁、x₂、x₃、y₀、y₁、y₂ 并进行判断，找出所有可行的 $C$ 与 $F$ 的方案，唯一好想的优化就是只有在找出一种可能的 $C$后再找 $F$。（注意输出时别忘了换行~~血的教训：40pts$\rightarrow$1pts~~）

考场代码(加了换行)：

#include<iostream>
#define MOD 998244353
using namespace std ;
int T = 0 , id = 0 , n = 0 , m = 0 , c = 0 , f = 0 ;
int vc = 0 , vf = 0 ;
char gar[1010][1010] = {} ;
bool checkc1(int x1 , int x2 , int y0)
{
    for(int i = x1 ; i <= x2 ; ++i)
        if(gar[i][y0] == '1')
            return false ;
    return true ;
}
bool checkc2(int x1 , int y0 , int y1)
{
    for(int i = y0 ; i <= y1 ; ++i)
        if(gar[x1][i] == '1')
            return false ;
    return true ;
}
bool checkc3(int x2 , int y0 , int y2)
{
    for(int i = y0 ; i <= y2 ; ++i)
        if(gar[x2][i] == '1')
            return false ;
    return true ;
}
bool checkf1(int x2 , int x3 , int y0)
{
    for(int i = x2 ; i <= x3 ; ++i)
        if(gar[i][y0] == '1')
            return false ;
    return true ;
}
int main()
{
    freopen("plant.in" , "r" , stdin) ;
    freopen("plant.out" , "w" , stdout) ;
    scanf("%d%d" , &T , &id) ;
    while(T--)
    {
        scanf("%d%d%d%d" , &n , &m , &c , &f) ;
        vc = vf = 0 ;
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ; j <= m ; ++j)
                cin>>gar[i][j] ;
        if(c == 0)
            goto CC ;
        for(int x1 = 1 ; x1 <= n ; ++x1)
        {
            for(int x2 = x1 + 2 ; x2 <= n ; ++x2)
            {
                for(int y0 = 1 ; y0 <= m ; ++y0)
                {
                    if(!checkc1(x1, x2 , y0))
                        continue ;
                    for(int y1 = y0 + 1 ; y1 <= m ; ++y1)
                    {
                        if(!checkc2(x1 , y0 , y1))
                            continue ;
                        for(int y2 = y0 + 1 ; y2 <= m ; ++y2)
                        {
                            if(!checkc3(x2 , y0 , y2))
                                continue ;
                            ++vc ;
                            vc %= MOD ;
                            if(f == 0)
                                continue ;
                            for(int x3 = x2 + 1 ; x3 <= n ; ++x3)
                            {
                                if(!checkf1(x2 , x3 , y0))
                                    continue ;
                                    ++vf ;
                                    vf %= MOD ;
                            }
                        }
                    }
                }
            }
        }
        CC : printf("%d %d\n" , vc * c % MOD , vf * f % MOD) ;
    }
    fclose(stdin) ;
    fclose(stdout) ;
}

优化思路：

我们考虑直接枚举x1、x2、x3、y0、y1、y2 十分浪费时间因此我们可以考虑使用DP（或记忆化搜索）。接下来问题就在于我们以什么方式搜索，考虑到将 C 推出后题目就简单了，我们就很容易想到可以从 C 的右上角开始进行搜索：

int dp[1010][1010][5] = {} ;
int dfs(int i , int j , int k)    //(k)0：刚开始，1：正在向左，2：刚向下，3：正向下，4：正向右
{
    if(gar[i][j] == '1' && k == 0)
        return 0 ;
    if(dp[i][j][k])
        return dp[i][j][k] ;
    int sum = 0 ;
    if(k == 0)
    {
        if(j != 1 && gar[i][j - 1] == '0')
            sum += dfs(i , j - 1 , 1) ;
    }
    else if(k == 1)
    {
        if(j != 1 && gar[i][j - 1] == '0')
            sum += dfs(i , j - 1 , 1) ;
        if(i != n && gar[i + 1][j] == '0')
            sum += dfs(i + 1 , j , 2) ;
    }
    else if(k == 2)
    {
        if(i != n && gar[i + 1][j] == '0')
            sum += dfs(i + 1 , j , 3) ;
    }
    else if(k == 3)
    {
        if(i != n && gar[i + 1][j] == '0')
            sum += dfs(i + 1 , j , 3) ;
        if(j != m && gar[i][j + 1] == '0')
            sum += dfs(i , j + 1 , 4) ;
    }
    else if(k == 4)
    {
        sum = 1 ;
        if(j != m && gar[i][j + 1] == '0')
            sum += dfs(i , j + 1 , 4) ;
    }
    sum %= mod ;
    return dp[i][j][k] = sum ;
}

但是如果向上面那样从右上角开始搜索，似乎不是很好确定 F 的数量，所以，我们应考虑从一个更方便推出 F 数量的位置开始搜索，考虑到 F 是由 C 的左下角向下找出的，所以我们从 C 的左下角开始搜索，用一个函数 $hmax0$ 求出从左下角向右的 0 的数量，将其与搜索结果相乘得到 C 的数量，再用一个函数 $lmax0$ 求出从左下角向下的 0 的数量，将其与 C 的答案相乘即可求出 F 的数量，复杂度为 O(nm) ~ O(n³m)。

记忆化搜索代码：

#include<iostream>
#include<cstring>
using namespace std ;
#define mod 998244353
int T = 0 , id = 0 , n = 0 , m = 0 , c = 0 , f = 0 ;
char gar[1010][1010] = {} ;
int dp[1010][1010][4] = {} ;
int ansc = 0 , ansf = 0 ;
int hmax0(int i , int j)
{
    int cnt = 0 ;
    ++j ;
    while(j <= m && gar[i][j] == '0')
        ++j , ++cnt ;
    return cnt ;
}
int lmax0(int i , int j)
{
    int cnt = 0 ;
    ++i ;
    while(i <= n && gar[i][j] == '0')
        ++cnt , ++i ;
    return cnt ;
}
int dfs(int i , int j , int k)
{
    if(gar[i][j] == '1' && k == 0)
        return 0 ;
    if(dp[i][j][k])
        return dp[i][j][k] ;
    int sum =  0 ;
    if(k == 0)
    {
        if(i != 1 && gar[i - 1][j] == '0')
            sum += dfs(i - 1 , j , 1) , sum *= hmax0(i , j) ;
    }
    else if(k == 1)
    {
        if(i != 1 && gar[i - 1][j] == '0')
            sum += dfs(i - 1 , j , 2) ;
    }
    else if(k == 2)
    {
        if(i != 1 && gar[i - 1][j] == '0')
            sum += dfs(i - 1 , j , 2) ;
        if(j != m && gar[i][j + 1] == '0')
            sum += dfs(i , j + 1 , 3) ;
    }
    else if(k == 3)
    {
        sum = 1 ;
        if(j != m && gar[i][j + 1] == '0')
            sum += dfs(i , j + 1 , 3) ;
    }
    sum %= mod ;
    return dp[i][j][k] = sum ;
}
int main()
{
    freopen("plant.in" , "r" , stdin) ;
    freopen("plant.out" , "w" , stdout) ;
    ios::sync_with_stdio(NULL) ;
    cin>>T>>id ;
    while(T--)
    {
        cin>>n>>m>>c>>f ;
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ; j <= m ; ++j)
                cin>>gar[i][j] ;
        memset(dp , 0 , sizeof dp) ;
        ansc = 0 , ansf = 0 ;
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ; j <= m ; ++j)
            {
                int ansnow = dfs(i , j , 0) ;
                ansc += ansnow ;
                ansc %= mod ;
                ansf += ansnow * lmax0(i , j) ;
                ansf %= mod ;
            }
        cout<<ansc * c % mod<<' '<<ansf * f % mod<<'\n' ;
    }
    return 0 ;
}

但是，直接记忆化搜索或DP的方法依赖于数据情况，复杂度不是非常稳定，（能过官方数据，但是无法通过洛谷的所有数据），我们考虑换一个方法或者优化一下

最终思路：

我们可以发现，上面的方法因为需要枚举 C 的坐下角的位置而使得其在图的分布十分稀疏时复杂度退化，所以我们现在应考虑更换思维角度。不难发现 C 实际上是由相隔至少一行的两个合法的横联通起来形成的，而如果上面有 a 个合法的横，那么下方每个可以与他们联通的横对数量的贡献就是 a ，那么，如果下面有 b 个合法的横，那么他们的总贡献就是 ab ，所以我们可以将每一行都像这样处理，再加上上面一行的合法的方案数，当遇到障碍（土坑）时再将计数数组清零。

因此，我们现在需要解决的问题就是如何快速求出每一行合法的横的数量，显然如果我们将每一行进行前缀和预处理就可以使用 O(1) 的复杂度查询每一行合法的横的数量了，将 C 求出后我们便可以很容易的把 F 推出了。（注意多测要清零，其他具体细节见代码）

最终代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1005 , mod = 998244353 ;
long long ansc = 0 , ansf = 0 , c = 0 , F = 0 ;
int n = 0 , m = 0 , id = 0 , T = 0 ;
int dp[N][N] = {} , jil = 0 , jilf = 0 , jis = 0 ;
char gar[N][N] = {} ;
int main()
{
    freopen("plant.in" , "r" , stdin) ;
    freopen("plant.out" , "w" , stdout) ;
    ios::sync_with_stdio(NULL) ;
    cin>>T>>id ;
    while (T--)
    {
        memset(dp , 0 , sizeof dp) ;
        cin>>n>>m>>c>>F ;
        for (int i = 1 ; i <= n ; ++i)
            for (int j = 1 ; j <= m ; ++j)
                cin >> gar[i][j] ;
        for (int i = 1 ; i <= n ; ++i)
            for (int j = m - 1 ; j >= 1 ; --j)
            {
                if (gar[i][j] == '1')
                    dp[i][j] = -1 ;
                else if (gar[i][j + 1] == '0')
                    dp[i][j] = dp[i][j + 1] + 1 ;
            }
        for (int j = 1 ; j < m ; ++j)
        {
            jis = jil = jilf = 0 ;
            for (int i = 1 ; i <= n ; ++i)
            {
                if (dp[i][j] == -1)
                {
                    jis = jilf = jil = 0 ;
                    continue ;
                }
                ansc = ansc % mod + (1ll * dp[i][j] * (jil % mod)) % mod ;
                ansf = (ansf % mod + jilf % mod) % mod ;
                jilf = (jilf + (1ll * dp[i][j] * (jil % mod)) % mod) % mod ;
                jil += max(0 , dp[i - 1][j]) ;
            }
        }
        cout << (c * ansc) % mod << ' ' << (F * ansf) % mod << '\n' ;
        ansc = ansf = 0 ;
    }
    return 0 ;
}

喵了个喵

考场思路：

先看一下具体如何消除吧：

好像没什么思路，随便做做看，试一下默认压入1号栈，能消则消的方法：

#include<iostream>
#include<vector>
#include<queue>
using namespace std ;
int T = 0 , n = 0 , m = 0 , k = 0 ;
deque<int> card ;
deque<int> S[301] ;
void clear()
{
    for(int i = 1; i <= n ; ++i)
        S[i].clear() ;
    card.clear() ;
}
bool emp()
{
    for(int i = 1 ; i <= n ; ++i)
        if(!S[i].empty())
            return false ;
    return true ;
}
struct op
{
    short op , s1 , s2 ;
} ;
vector<op> ope ;
void solve()
{
    while(!card.empty() || !emp())
    {
        bool flag = true ;
        vector<int> nemp ;
        for(int i = 1 ; i <= n ; ++i)
        {
            if(!S[i].empty())
            {
                if(card.empty())
                    goto A ;
                if(card.front() == S[i].front())
                {
                    flag = false ;
                    card.pop_front() , S[i].pop_front() ;
//                    printf("1 %d\n" , i) ;
                    ope.push_back((op){1 , i , 0}) ;
                }
            }
            A : if(!S[i].empty())
                nemp.push_back(i) ;
        }
        if(nemp.empty() && !card.empty())
        {
            flag = false ;
            S[1].push_front(card.front()) , card.pop_front() ;
//            printf("1 1\n") ;
            ope.push_back((op){1 , 1 , 0}) ;
        }
        int siz = nemp.size() ;
        for(int i = 0 ; i < siz ; ++i)
        {
            for(int j = 0 ; j < siz ; ++j)
            {
                if(i == j)
                    continue ;
                if(S[nemp[i]].back() == S[nemp[j]].back())
                {
                    flag = false ;
                    S[nemp[i]].pop_back() , S[nemp[j]].pop_back() ;
//                    printf("2 %d %d\n" , nemp[i] , nemp[j]) ;
                    ope.push_back((op){2 , nemp[i] , nemp[j]}) ;
                    goto B ;
                }
            }
        }
        if(flag && !card.empty())
        {
            for(int i = 1 ; i <= n ; ++i)
            {
                if(S[i].empty())
                {
                    flag = false ;
                    S[i].push_front(card.front()) , card.pop_front() ;
//                    printf("1 %d\n" , i) ;
                    ope.push_back((op){1 , i , 0}) ;
                    break ;
                }
            }
        }
        if(flag && !card.empty())
        {
            S[1].push_front(card.front()) , card.pop_front() ;
//            printf("1 1\n") ;
            ope.push_back((op){1 , 1 , 0}) ;
        }
        B : ;
    }
    int siz = ope.size() ;
    printf("%d\n" , siz) ;
    for(int i = 0 ; i < siz ; ++i)
    {
        if(ope[i].op == 1)
            printf("%hd %hd\n" , ope[i].op , ope[i].s1) ;
        else
            printf("%hd %hd %hd\n" , ope[i].op , ope[i].s1 , ope[i].s2) ;
    }
}
int main()
{
    freopen("meow.in" , "r" , stdin) ;
    freopen("meow.out" , "w" , stdout) ;
    scanf("%d" , &T) ;
    while(T--)
    {
        scanf("%d%d%d" , &n , &m , &k) ;
        for(int i = 1 ; i <= m ; ++i)
        {
            int a = 0 ;
            scanf("%d" , &a) ;
            card.push_back(a) ;
        }
        solve() ;
    }
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

OK，再一段时间的努力之后，终于过掉了所有样例，然而，构造方法错误，实际评测全TLE（构造失败）

正解：

仔细读题过后，我才注意到原来数据点分为两种类型：

$k = 2n - 2$
$k = 2n - 1$

考虑到这题应该是针对数据特点进行构造操作，我们可以从较好入手的点入手。我们可以发现当 $k = 2n - 2$ 时，如果一个栈里有不少于三张牌的话，那么位于中间的那一张是不容易被消掉的，而 k 的范围在 2n 左右，这启发我们尽可能使每个栈含有不超过两张牌。由此我们产生了构造策略 1 ：

存在一个编号为sp的空栈，且当前牌堆顶的牌在场上存在或其余栈中存在至少一个栈大小不超过1，如果当前牌堆顶的牌在场上出现过就执行上面的消除方法，若无，则将此牌放入一个大小不超过1

使用构造策略 1 可以轻松解决 $k = 2n - 2$ 的情况，应该能轻松拿下前15pts，然而在数据种类 2 中多了一种牌，所以策略 1 不一定会每次都奏效，要另外想办法

那么，我们现在就应考虑如何安置多出来的一种牌

我们再看牌堆顶的下一张牌，如果这张牌的同类牌出现在栈底（设对应栈编号为 p），那么不难得出可以将牌堆顶的牌放到栈 p 上，然后将下一张牌放到栈 sp 里，最后对栈 p 和 sp 执行一次操作2便可安置。如图：

但是如果下一张牌的同类牌在栈顶的话，我们可以直接将牌堆顶的牌放到栈 sp 上吗？显然不可以：

既然消除的关键还是栈底的牌，所以我们可不可往后看有没有位于底部的牌，然后将牌堆顶的牌放到对应栈顶呢？

好像是可行的，但是很容易找出反例：

在这个例子中，我们发现我们上面的策略仍然行不通，牌堆顶的牌阻挡了原栈顶的牌，使得它们不能互相消除

但这时如果我们改为将牌堆顶的牌放到 sp 里：

这样反而行得通了，唯一的区别就是 sp 换了一下

那么两者的区别是什么呢？仔细观察就可以发现：

前者第一张位于底部的牌所在栈的栈顶牌没有被消去，后者被消去了。

什么情况下栈顶元素会被消去？结合上述图思考一下便可得知：

在牌堆顶和其后第一张位于栈底的牌之间，与栈顶牌同类的牌出现了奇数次。

至于这两张牌之间的所有牌，由于它们都出现在栈顶出现，所以直接将其分别放在对应栈上即可。（当然一些牌会出现多次，在这种情况下为了方便，可以每次都将其放在同样的位置。）于是，我们得到了策略 2 ：

存在一个编号为 sp 的空栈，且不满足策略1条件。

此时我们首先记录现在每类牌所在的栈编号和是否位于栈顶，记 $P_{i}$ 此时牌 i 同类的牌所位于的栈编号，$t_{i} = 1$ 代表此时牌 i 同类的牌位于栈顶。

然后从牌堆顶的下一张开始，逐个向后判断。设当前判断的牌为 x。

若$t_{x} = 1$，则将$x$放到栈$P_{x}$的栈顶，然后判断下一张。
否则若 x 与牌堆顶的牌同类，将这两张牌放到 sp 里，然后更换使用策略 1 或重新使用策略 2 。
否则：

1.若与栈 $P_{x}$ 的栈顶牌同类的牌在牌堆顶至 x 这些牌之间出现了奇数次，则将此时牌堆顶的牌放置于栈 sp，将 x 放置于栈 $P_{x}$，然后将 sp 改为 $P_{x}$。

2.若与栈 $P_{x}$ 的栈顶牌同类的牌在牌堆顶至 x 这些牌之间出现了偶数次，则将此时牌堆顶的牌放置于栈 $P_{x}$，将 x 放置于栈 sp，然后在栈 sp 和 $P_{x}$ 上执行一次操作 2。

执行以上两种操作之一后更换使用策略 1 或重新使用策略 2 即可。

当然，由于将牌加入至栈的过程是有序的，所以在实现上会有些许不同。（例如，可以先找到 x 在哪里，然后根据信息判断牌堆顶的牌应放置在哪里，最后将牌堆顶之后的牌加入栈。）

重复执行策略 1 和策略 2 ，最终所有的牌均可以被消掉。这样我们也可以证明所有合法的初始配置均有解。

对于操作次数：我们会执行恰好 m 次操作 1 ，而每次操作 2 会消除两张牌，由于操作 1 执行过程中也会消去牌，因此 2m 张牌至多使用 m 次操作 2 即可全部消除，于是总操作次数不超过 2m，符合条件。

(注意，本题输入输出数据量较大，应使用较快的输入输出)

代码：

#include <iostream>
#include <queue>
using namespace std;
#define N 305
#define M 2000005
int card[M];
deque<int> z[N];
int d[N * 2];
typedef pair<int, int> pii;
vector<pii> ans;
inline void push(int s, int t = 0)
{
    ans.push_back(make_pair(s , t));
}
int t;
queue<int> q;
inline bool solve(int x)
{
    int s = d[x];
    if (s)
    {
        d[x] = 0;
        q.push(s);
        if (x ^ z[s].back())
        {
            push(t);
            push(t, s);
            z[s].pop_front();
        }
        else
        {
            push(s);
            z[s].pop_back();
        }
    }
    else
    {
        if (q.empty())
            return true;
        d[x] = s = q.front();
        q.pop();
        push(s);
        z[s].push_back(x);
    }
    return false;
}
int main()
{
    freopen("meow.in" , "r" , stdin) ;
    freopen("meow.out" , "w" , stdout) ;
    ios::sync_with_stdio(NULL) ;
    int T = 0;
    cin >> T ;
    while (T--)
    {
        int n, m, k;
        cin >> n >> m >> k ;
        for (int i = 1; i <= m; ++i)
            cin >> card[i] ;
        fill(d, d + n * 2, 0);
        ans.clear();
        t = n;
        while (q.size())
            q.pop();
        for (int i = 1; i < n; ++i)
        {
            q.push(i);
            q.push(i);
        }
        for (int i = 1; i <= m; ++i)
            if (solve(card[i]))
            {
                int p = card[i];
                int r = i + 1, x = card[r];
                for (; x ^ p && z[d[x]].back() == x; x = card[++r])
                    ;
                if (x ^ p)
                {
                    int s = d[x], y = z[s].back(), v = 1;
                    for (int j = i + 1; j < r; ++j)
                        if (card[j] == y)
                            v ^= 1;
                    if (v)
                    {
                        push(s);
                        z[s].push_back(p);
                        for (int j = i + 1; j < r; ++j)
                        {
                            if (card[j] ^ y)
                                solve(card[j]);
                            else
                                push(t);
                        }
                        push(t);
                        push(t, s);
                        z[s].pop_front();
                        d[x] = 0;
                        d[p] = s;
                    }
                    else
                    {
                        push(t);
                        z[t].push_back(p);
                        for (int j = i + 1; j < r; ++j)
                        {
                            if (card[j] ^ y)
                                solve(card[j]);
                            else
                                push(s);
                        }
                        push(s);
                        z[s].clear();
                        d[x] = d[y] = 0;
                        d[p] = t;
                        q.push(t);
                        t = s;
                    }
                }
                else
                {
                    push(t);
                    for (int j = i + 1; j < r; ++j)
                        solve(card[j]);
                    push(t);
                }
                i = r;
            }
        cout << ans.size() << "\n";
        for (pii ruozhi : ans)
        {
            int p = ruozhi.first, q = ruozhi.second ;

            if (q)
                cout << "2 " << p << ' ' << q << '\n' ;
            else
                cout << "1 " << p << '\n' ;
        }
    }
    return 0;
}

假期计划

考场思路：

考虑可以暴力枚举四个景点，而为了判断枚举的各个景点是否能由上一个景点到达，很显然需要根据题目要求跑一边无权图的最短路，求出各个景点之间的最少中转次数，而且需要求出每个之间的最少中转次数，考虑使用全源最短路，所以首先想到可以使用Floyed或者BFS

Floyed版

 #include<iostream>
 #include<cstring>
 using namespace std ;
 int n = 0 , m = 0 , k = 0 ;
 int edge[2505][2505] = {} ;
 bool vis[2505][2505] = {} ;
 long long val[2505] = {} ;
 void floyd()
 {
     for(int k = 1 ; k <= n ; ++k)
         for(int a = 1 ; a <= n ; ++a)
             for(int b = 1 ; b <= n ; ++b)
             {
                 if(vis[a][b] || vis[b][a])
                     continue ;
                 edge[a][b] = edge[b][a] = min(edge[a][b] , edge[a][k] + edge[b][k] + 1) ;
             }
 }
 long long maxv = 0 ;
 int main()
 {
     freopen("holiday.in" , "r" , stdin) ;
     freopen("holiday.out" , "w" , stdout) ;
     memset(edge , 0x3f , sizeof edge) ;
     scanf("%d%d%d" , &n , &m , &k) ;
     for(int i = 2 ; i <= n ; ++i)
         scanf("%d" , &val[i]) ;
     for(int i = 1 ; i <= m ; ++i)
     {
         int x = 0 , y = 0 ;
         scanf("%d%d" , &x , &y) ;
         edge[x][y] = edge[y][x] = 0 ;
     }
     floyd() ;
     for(int a = 2 ; a <= n ; ++a)
     {
         if(edge[1][a] > k)
             continue ;
         for(int b = 2 ; b <= n ; ++b)
         {
             if(b == a)
                 continue ;
             if(edge[a][b] > k)
                 continue ;
             for(int c = 2 ; c <= n ; ++c)
             {
                 if(c == a || c == b)
                     continue ;
                 if(edge[b][c] > k)
                     continue ;
                 for(int d = 2 ; d <= n ; ++d)
                 {
                     if(d == a || d == b || d == c)
                         continue ;
                     if(edge[c][d] > k)
                         continue ;
                     if(edge[1][d] > k)
                         continue ;
                     maxv = max(maxv , val[a] + val[b] + val[c] + val[d]) ;
                 }
             }
         }
     }
     printf("%lld\n" , maxv) ;
     fclose(stdin) ;
     fclose(stdout) ;
     return 0 ;
}

BFS 版

#include <iostream>
#include <queue>
#include<vector>
#include <cstring>
using namespace std;
int n = 0, m = 0, k = 0;
long long val[2505] = {};
#define maxn 2505
int dist[2505][2505] = {} ;
bool vis[2505] = {} ;
vector<int> edge[2505] ;
void dij(int a)
{
    memset(vis , 0 , sizeof vis) ;
    dist[a][a] = 0 ;
    queue<int> Q ;
    Q.push(a) ;
    while (Q.size())
    {
        int t = Q.front() ;
        Q.pop();
        int siz = edge[t].size() ;
        for (int i = 0 ; i < siz ; ++i)
        {
            int j = edge[t][i];
            if(vis[j])
                continue ;
            vis[j] = true ;
            if (dist[a][j] > dist[a][t] + 1)
            {
                dist[a][j] = dist[a][t] + 1 ;
            }
            Q.push(j);
        }
    }
}
long long maxv = 0;
int main()
{
    freopen("holiday.in", "r", stdin);
    freopen("holiday.out", "w", stdout);
    memset(dist, 0x3f, sizeof(dist));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 2; i <= n; ++i)
        scanf("%lld", &val[i]);
    for (int i = 1; i <= m; ++i)
    {
        int x = 0, y = 0;
        scanf("%d%d", &x, &y);
        edge[x].push_back(y) , edge[y].push_back(x) ;
        dist[x][y] = dist[y][x] = 0 ;
    }
    for(int i = 1 ; i <= n ; ++i)
        dij(i) ;
    for (int a = 2; a <= n; ++a)
    {
        if (dist[1][a] > k)
            continue;
        for (int b = 2; b <= n; ++b)
        {
            if (b == a)
                continue;
            if (dist[a][b] > k)
                continue;
            for (int c = 2; c <= n; ++c)
            {
                if (c == a || c == b)
                    continue;
                if (dist[b][c] > k)
                    continue;
                for (int d = 2; d <= n; ++d)
                {
                    if (d == a || d == b || d == c)
                        continue;
                    if (dist[c][d] > k)
                        continue;
                    if (dist[1][d] > k)
                        continue;
                    maxv = max(maxv, val[a] + val[b] + val[c] + val[d]);
                }
            }
        }
    }
    printf("%lld\n", maxv);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

优化思路：

以上两份代码中Floyed版效率差一些，只能拿60pts，而BFS版则能拿75pts，但是它们都不能拿到满分。我们不难发现根据题目要求，全源最短路是必须要求的，而使用BFS的效率已经是最高的了，无法继续优化了，所以上面代码的时间瓶颈就在于 O(n⁴) 的四重枚举，所以我们可以考虑减少枚举层数。

继续研究代码的运行过程，我们可以发现，景点 a 与景点 d 的枚举其实是没有必要的，因为当景点 b 与景点 c 确定后， a 与 d 的选择区间其实就已经固定了，所以，我们可以将可同时在 k 步以内到达 1(家) 与枚举到的景点提前预处理出来，并进行排序，然后在枚举时只用 O(n²) 的复杂度枚举 b、c 两景点，从而大大提升效率。

但是要注意一下，景点 b 中预处理出的权值最大的点点有可能与景点 c 中预处理出的权值最大的点重合，也有可能与 c 本身重合，而景点 c 也是一样的，需要注意，而在特判完a == c以及d == b要注意重新回到前面判一下a == d，具体实现见代码。

代码：

#include <iostream>
#include<algorithm>
#include <queue>
#include<vector>
#include <cstring>
#define int long long
using namespace std;
int read()
{
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
            f = -1 ;
        ch = getchar() ;
    }
    while(ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0' , ch = getchar() ;
    return x * f ;
}
int n = 0, m = 0, k = 0;
long long val[2505] = {};
#define maxn 2505
int dist[2505][2505] = {} ;
bool vis[2505] = {} ;
vector<int> edge[2505] ;
void dij(int a)
{
    memset(vis , 0 , sizeof vis) ;
    dist[a][a] = 0 ;
    queue<int> Q ;
    Q.push(a) ;
    while (Q.size())
    {
        int t = Q.front() ;
        Q.pop();
        int siz = edge[t].size() ;
        for (int i = 0 ; i < siz ; ++i)
        {
            int j = edge[t][i];
            if(vis[j])
                continue ;
            vis[j] = true ;
            if (dist[a][j] > dist[a][t] + 1)
            {
                dist[a][j] = dist[a][t] + 1 ;
            }
            Q.push(j);
        }
    }
}
long long maxv = 0 ;
struct node
{
    int id ;
    long long val ;
    bool operator<(const node& b) const
    {
        return val > b.val ;
    }
} ;
vector<node> ok[2505] ;
//int ma = 0 , mb = 0 , mc = 0 , md = 0 ;
signed main()
{
    freopen("holiday.in", "r", stdin);
    freopen("holiday.out", "w", stdout);
    memset(dist, 0x3f, sizeof(dist));
//    scanf("%d%d%d", &n, &m, &k);
    n = read() , m = read() , k = read() ;
    for (int i = 2; i <= n; ++i)
//        scanf("%lld", &val[i]);
        val[i] = read() ;
    for (int i = 1; i <= m; ++i)
    {
        int x = 0, y = 0;
//        scanf("%d%d", &x, &y);
        x = read() , y = read() ;
        edge[x].push_back(y) , edge[y].push_back(x) ;
        dist[x][y] = dist[y][x] = 0 ;
    }
    for(int i = 1 ; i <= n ; ++i)
        dij(i) ;
    for(int i = 2 ; i <= n ; ++i)
    {
        for(int j = 2 ; j <= n ; ++j)
        {
            if(i == j)
                continue ;
            if(dist[i][j] <= k && dist[1][j] <= k)
                ok[i].push_back((node){j , val[j]}) ;
        }
        sort(ok[i].begin() , ok[i].end()) ;
    }
    for (int b = 2; b <= n; ++b)
    {
        for (int c = 2; c <= n; ++c)
        {
            if(b == c)
                continue ;
            if (dist[b][c] > k)
                continue;
            if(ok[b].empty() || ok[c].empty())
                continue ;
            int a = ok[b][0].id , d = ok[c][0].id ;
            int flaga = 1 , flagd = 1 ;
            back : if(a == d)
            {
                if(ok[b].size() < flaga + 1)
                    if(ok[c].size() < flagd + 1)
                        continue ;
                    else
                        d = ok[c][flagd].id , ++flagd ;
                else
                    if(ok[c].size() < flagd + 1)
                        a = ok[b][flaga].id , ++flaga ;
                    else
                        if(val[ok[b][flaga - 1].id] + val[ok[c][flagd].id] > val[ok[b][flaga].id] + val[ok[c][flagd - 1].id])
                            d = ok[c][flagd].id , ++flagd ;
                        else
                            a = ok[b][flaga].id , ++flaga ;
            }
            if(a == c)
            {
                if(ok[b].size() < flaga + 1)
                    continue ;
                a = ok[b][flaga].id ;
                ++flaga ;
            }
            if(d == b)
            {
                if(ok[c].size() < flagd + 1)
                    continue ;
                d = ok[c][flagd].id ;
                ++flagd ;
            }
            if(a == d)
                goto back ;
            maxv = max(maxv , val[b] + val[c] + val[a] + val[d]) ;
//            if(val[a] + val[b] + val[c] + val[d] > maxv)
//                maxv = val[a] + val[b] + val[c] + val[d] , ma = a , mb = b , mc = c , md = d ;
        }
    }
    printf("%lld\n", maxv);
//    printf("%d %d %d %d\n" , ma , mb , mc , md) ;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

策略游戏

考场思路：

~~贪心？暴力枚举？~~涉及到区间，应该可以用线段树维护，但是时间不太够，还是写个暴力吧

~~结果：样例全过，但是测评WA+TLE~~

正确思路：

先将题目翻译一下：

A 在 a[l₁······r₁] 中选择一个 x，然后 B 在 b[l₂······r₂] 中选择一个 y，分数是 $x \times y$，A 想让分数尽可能大，B 想让分数尽可能小。求最终分数。

显然，我们需要先思考B再思考A，因为A会思考B的思考再进行选择

B 的行为就是对于 x，找到一个 b[l₂⋯r₂] 中的 y，使得 $x\times y$ 最小。

具体地：

$x \geq 0$时， B 会选择最小的 y
$x < 0$时， B 会选择最大的 y

那么 A 的行为会是怎样的？还是按照正负分类讨论：

如果 A 这次想让 $x \geq 0$，那么 B 会选择最小的 y。如果这个 $y \geq 0$，那么 A 一定会选最大的 x；如果这个$y < 0$，那么 A 一定会选最小的非负数 x（别忘了当前制约条件 $x \geq 0$）。
如果 A 这次想让 $x < 0$，那么 B 会选择最大的 y。如果这个 $y \geq 0$，那么 A 一定会选最大的负数 x；如果这个 $y < 0$，那么 A 一定会选最小的 x。

综上所述，A的选择只可能有四种：

$x_{max}$
$x_{min}$
最大的负数$x$
最小的负数$x$

然后我们只需要分别讨论 A 选择四种行为时 B 的选择，答案取最大值即可。

所以，此时我们只需要求静态区间最值，可以考虑使用线段树进行维护，具体见代码。

代码：

#include<iostream>
#define int long long
using namespace std;
int a[100010] = {}, b[100010] = {};
struct node1
{
    int l, r, mid;
    int maxx, minn;
    int zmin, fmax;
} d1[400010];
struct node2
{
    int l, r, mid;
    int minn, maxx;
} d2[400010];
node1 pushup1(node1 x, node1 y)
{
    x.minn = min(x.minn, y.minn);
    x.maxx = max(x.maxx, y.maxx);
    x.zmin = min(x.zmin, y.zmin);
    x.fmax = max(x.fmax, y.fmax);
    return x;
}
node2 pushup2(node2 x, node2 y)
{
    x.minn = min(x.minn, y.minn);
    x.maxx = max(x.maxx, y.maxx);
    return x;
}
void build1(int p, int l, int r)
{
    int mid = l + (r - l) / 2;
    d1[p].mid = mid;
    d1[p].l = l;
    d1[p].r = r;
    if (l == r)
    {
        d1[p].maxx = d1[p].minn = a[l];
        if (a[l] > 0)
        {
            d1[p].zmin = a[l];
            d1[p].fmax = LONG_LONG_MIN;
        }
        else if (a[l] < 0)
        {
            d1[p].zmin = LONG_LONG_MAX;
            d1[p].fmax = a[l];
        }
        else
            d1[p].zmin = d1[p].fmax = 0;
        return;
    }
    build1(p * 2, l, mid);
    build1(p * 2 + 1, mid + 1, r);
    d1[p].minn = min(d1[p * 2].minn, d1[p * 2 + 1].minn);
    d1[p].maxx = max(d1[p * 2].maxx, d1[p * 2 + 1].maxx);
    d1[p].fmax = max(d1[p * 2].fmax, d1[p * 2 + 1].fmax);
    d1[p].zmin = min(d1[p * 2].zmin, d1[p * 2 + 1].zmin);
}
void build2(int p, int l, int r)
{
    int mid = l + (r - l) / 2;
    d2[p].mid = mid;
    d2[p].l = l;
    d2[p].r = r;
    if (l == r)
    {
        d2[p].minn = b[l];
        d2[p].maxx = b[l];
        return;
    }
    build2(p * 2, l, mid);
    build2(p * 2 + 1, mid + 1, r);
    d2[p].minn = min(d2[p * 2].minn, d2[p * 2 + 1].minn);
    d2[p].maxx = max(d2[p * 2].maxx, d2[p * 2 + 1].maxx);
}
node1 getnum1(int p, int s, int t) //区间a最大值
{
    if (s <= d1[p].l && d1[p].r <= t)
        return d1[p];
    node1 t1, t2;
    t2.fmax = t1.fmax = LONG_LONG_MIN;
    t2.zmin = t1.zmin = LONG_LONG_MAX;
    t1.maxx = t2.maxx = LONG_LONG_MIN;
    t1.minn = t2.minn = LONG_LONG_MAX;
    if (s <= d1[p].mid) t1 = getnum1(p * 2, s, t);
    if (t > d1[p].mid) t2 = getnum1(p * 2 + 1, s, t);
    t1 = pushup1(t1, t2);
    return t1;
}
node2 getnum2(int p, int s, int t) //区间b所有值
{
    if (s <= d2[p].l && d2[p].r <= t)
        return d2[p];
    node2 t1, t2;
    t1.maxx = t2.maxx = LONG_LONG_MIN;
    t1.minn = t2.minn = LONG_LONG_MAX;
    if (s <= d2[p].mid) t1 = getnum2(p * 2, s, t);
    if (t > d2[p].mid) t2 = getnum2(p * 2 + 1, s, t);
    t1 = pushup2(t1, t2);
    return t1;
}
signed main()
{
    freopen("game.in" , "r" , stdin) ;
    freopen("game.out" , "w" , stdout) ;
    ios::sync_with_stdio(0);
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
        cin >> b[i];
    build1(1, 1, n); //a的区间
    build2(1, 1, m); //b的区间
    while (q--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        node1 L = getnum1(1, l1, r1);
        node2 Q = getnum2(1, l2, r2);
        //L想尽可能大 先选
        //Q想尽可能小 后选
        if (Q.minn >= 0)
            if (L.maxx >= 0)
                cout << L.maxx*Q.minn << '\n';
            else
                cout << L.maxx*Q.maxx << '\n';
        else //Q.minn小于0
            if (Q.maxx <= 0)
                if (L.minn >= 0)
                    cout << L.minn * Q.minn << '\n';
                else
                    cout << L.minn*Q.maxx << '\n';
            else //Q.minn<0&&Q.maxx>0
                if (L.minn >= 0)
                    cout << L.minn*Q.minn << '\n';
                else
                    if (L.maxx <= 0)
                        cout << L.maxx*Q.maxx << '\n';
                    else //L.minn<0&&L.max>0
                        cout << max(Q.maxx*L.fmax, Q.minn*L.zmin) << '\n';
    }
}

21集训测试题(10.10)

廊桥分配

考场思路：

可以暴力枚举所有可能的分配情况，并分别求出此时国内停靠飞机数与国外停靠飞机数，对它们的和取最大值，期望得分 = 实际得分 = 20pts

暴力代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;
int n = 0 , m1 = 0 , m2 = 0 ;
int maxn = 0 ;
inline int read()
{
    int w = 0 , f = 1 ;
    char ch = getchar() ;
    while(!isdigit(ch))
    {
        ch = getchar() ;
        if(ch == '-')
        {
            f = -1 ;
            ch = getchar() ;
            break ;
        }
    }
    while(isdigit(ch))
        w = w * 10 + ch - '0' , ch = getchar() ;
    return w * f ;
}
struct time
{
    int l , r ;
    bool operator<(const time& b) const
    {
        if(l != b.l)
            return l < b.l ;
        return r > b.r ;
    }
} listin[100005] , listout[100005] ;
bool statein[100005] = {} , stateout[100005] = {} ;
int main()
{
    freopen("airport.in" , "r" , stdin) ;
    freopen("airport.out" , "w" , stdout) ;
    // scanf("%d%d%d" , &n , &m1 , &m2) ;
    n = read() , m1 = read() , m2 = read() ;
    for(int i = 1 ; i <= m1 ; ++i)
        // scanf("%d%d" , &listin[i].l , &listin[i].r) ;
        listin[i].l = read() , listin[i].r = read() ;
    sort(listin + 1 , listin + m1 + 1) ;
    for(int i = 1 ; i <= m2 ; ++i)
        // scanf("%d%d" , &listout[i].l , &listout[i].r) ;
        listout[i].l = read() , listout[i].r = read() ;
    sort(listout + 1 , listout + m2 + 1) ;
    for(int in = 0 ; in <= n ; ++in)
    {
        memset(statein , 0 , sizeof statein) ;
        memset(stateout , 0 , sizeof stateout) ;
        int out = n - in ;
        int cntin = 0 , cntout = 0 ;
        for(int i = 1 ; i <= m1 ; ++i)
        {
            if(in < 1)
                continue ;
            if(i == 1)
            {
                ++cntin ;
                statein[i] = true ;
            }
            else
            {
                int use = 1 ;
                for(int j = 1 ; j <= i ; ++j)
                    if(statein[j] && listin[j].r > listin[i].l)
                        ++use ;
                if(use <= in)
                    ++cntin , statein[i] = true ;
            }
        }
        for(int i = 1 ; i <= m2 ; ++i)
        {
            if(out < 1)
                continue ;
            if(i == 1)
            {
                ++cntout ;
                stateout[i] = true ;
            }
            else
            {
                int use = 1 ;
                for(int j = 1 ; j <= i ; ++j)
                    if(stateout[j] && listout[j].r > listout[i].l)
                        ++use ;
                if(use <= out)
                    ++cntout , stateout[i] = true ;
            }
        }
        if(cntin + cntout > maxn)
            maxn = cntin + cntout ;
        // printf("%d %d\n" , cntin , cntout) ;
    }
    printf("%d\n" , maxn) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

优化思路：

首先考虑一一枚举各种分配情况并进行判断的复杂度实在太高，不是通过优化其中过程就能通过这题的，我们想到廊桥的限制相当于把一部分已经进入到廊桥的飞机移至远机位，所以可以考虑先忽略廊桥数量的限制来安排航班。我们可以维护一个空闲的廊桥队列，每到达一架航班，就给它安排编号最小的廊桥供其使用。

现在我们再将廊桥数量的限制加上，容易发现刚才的廊桥分配方法直接就帮我们解决了廊桥限制的问题：如果当前有 n 个廊桥可供使用，则分配到 n+1 号及以后的廊桥实质上就是分配到远机位了，无需再做任何额外的处理。

具体实现时，我们可以先按照到达时间对国内航班及国外航班分别进行排序，再在进行计算时，用两个优先队列分别维护等待离港的航班与空闲的廊桥，具体见代码。

代码：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std ;
#define pii pair<int , int>
inline int read()
{
    int w = 0 , f = 1 ;
    char ch = getchar() ;
    while(!isdigit(ch))
    {
        if(ch == '-')
        {
            f = -1 ;
            ch = getchar() ;
            break ;
        }
        ch = getchar() ;
    }
    while(isdigit(ch))
        w = w * 10 + ch - '0' , ch = getchar() ;
    return w * f ;
}
inline void write(int x)
{
    if(x < 0)
        putchar('-') , x = -x ;
    if(x > 0)
        write(x / 10) , putchar(x % 10 + '0') ;
}
struct tim
{
    int l , r ;
} a[100005] , b[100005] ;
int res1[100005] = {} , res2[100005] = {}  ;
int n = 0 , m1 = 0 , m2 = 0 ;
bool cmp(const tim& a , const tim& b)
{
    return a.l < b.l ;
}
void calc(tim* t , int m , int* res)
{
    priority_queue<pii , vector<pii> , greater<pii> > lq ;
    priority_queue<int , vector<int> , greater<int> > wq ;
    for(int i = 1 ; i <= n ; ++i)
        wq.push(i) ;
    for(int i = 1 ;i <= m ; ++i)
    {
        while(!lq.empty() && t[i].l >= lq.top().first)
            wq.push(lq.top().second) , lq.pop() ;
        if(wq.empty())
            continue ;
        int now = wq.top() ;
        wq.pop() ;
        ++res[now] ;
        lq.push(make_pair(t[i].r , now)) ;
    }
    for(int i = 1 ; i <= n ; ++i)
        res[i] += res[i - 1] ;
}
int main()
{
    freopen("airport.in" , "r" , stdin) ;
    freopen("airport.out" , "w" , stdout) ;
    n = read() , m1 = read() , m2 = read() ;
    for(int i = 1 ; i <= m1 ; ++i)
        a[i].l = read() , a[i].r = read() ;
    for(int i = 1 ; i <= m2 ; ++i)
        b[i].l = read() , b[i].r = read() ;
    sort(a + 1 , a + m1 + 1 , cmp) ;
    sort(b + 1 , b + m2 + 1 , cmp) ;
    calc(a , m1 , res1) ;
    calc(b , m2 , res2) ;
    int ans = 0 ;
    for(int i = 0 ; i <= n ; ++i)
        ans = max(ans , res1[i] + res2[n - i]) ;
    write(ans) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

括号序列

考场思路：

可以考虑使用深搜枚举所有可能的序列情况，并进行判断，但是时间复杂度太劣，而且判断不好写，挂掉了

正解思路：

考虑根据题目中的描述，我们共有以下几种可能的序列：

形态如***...*的括号序列（即全部是*）。
形态如(...)的括号序列（即左右直接被括号包裹且最左边括号与最右边的括号相互匹配）。
形态如(...)**(...)***的括号序列（即左边以括号序列开头，右边以*结尾）。
(...)***(...)*(...)的括号序列（即左边以括号序列开头，右边以括号序列结尾，注意：第2种形态也属于这种形态）。
形态如***(...)**(...)的括号序列（即左边以*开头，右边以括号序列结尾）。
形态如***(...)**(...)**的括号序列（即左边以*开头，右边以*结尾，注意：第1种形态也属于这种形态）。

我们可以考虑使用一个三维的 dp数组对每个区间内对应序列的数量

然后就是写一下状态转移方程：

bool check(int l , int r)
{
    return (str[l] == '(' || str[l] == '?') && (str[r] == ')' || str[r] == '?') ;
}

$dp_{l,r,0}$(对应第一种情况)(直接特判)
\[dp_{l,r,1}=(dp_{l+1,r−1,0}+dp_{l+1,r−1,2}+dp_{l+1,r−1,3}+dp_{l+1,r−1,4})∗check(l,r) \]
- 加括号时，里面可以是全*，可以是有一边是*，也可以是两边都不是*，唯独不能两边都是*且中间有括号序列。
\[dp_{l,r,2}=\sum_{i = l}^{r - 1} dp_{l,i,3}×dp_{i+1,r,0} \]
- 左边以括号序列开头且以括号序列结尾的是第3种，右边接一串*，是第0种。
\[dp_{l,r,3}=\sum_{i = l}^{r - 1}(dp_{l,i,2+}dp_{l,i,3})×dp_{i+1,r,1}+dp_{l,r,1} \]
- 左边以括号序列开头，结尾随便，符合的有第2和第3种，右边接一个括号序列，是第1种。
- 记得加上直接一个括号序列的。
\[dp_{l,r,4}=\sum_{i = 1}^{r - 1}(dp_{l,i,4}+dp_{l,i,5})×dp_{i+1,r,1} \]
- 左边以*开头，结尾随便，符合的有第4和第5种，右边接一个括号序列，是第1种。
\[dp_{l,r,5}=\sum_{i = l}^{r - 1}dp_{l,i,4}×dp_{i+1,r,0}+dp_{l,r,0} \]
- 左边以*开头，以括号序列结尾，符合的是第4种，右边接一串*，是第0种。
- 记得加上全是*的。

合法的答案是以以括号序列开头，以括号序列结尾，所以最后答案存储在$dp_{i,n,3}$中。

初始状态也不难设置，对于所有的 i 满足 $1 \leq i \leq n$，有 $dp_{i,i-1,0}=1$ 。

最终具体实现见代码。

代码：

#include<iostream>
const int MOD = 1e9 + 7 ;
long long n = 0 , k = 0 , dp[510][510][6] = {} ;
char str[510] = {} ;
bool check(int a , int b)
{
    return (str[a] == '(' || str[a]=='?') && (str[b]==')' || str[b]=='?');
}
int main()
{
    freopen("bracket.in" , "r" , stdin) ;
    freopen("bracket.out" , "w" , stdout) ;
    scanf("%lld%lld" , &n , &k) ;
    scanf("%s" , str + 1) ;
    for(int i = 1 ; i <= n ; ++i)
        dp[i][i-1][0] = 1 ;
    for(int len = 1 ; len <= n ; ++len)
    {
        for(int l = 1 ; l <= n - len + 1 ; ++l)
        {
            int r = l + len - 1 ;
            if(len <= k)
                dp[l][r][0] = dp[l][r-1][0] && (str[r] == '*' || str[r] == '?') ;
            if(len >= 2)
            {
                if(check(l , r))
                    dp[l][r][1] = (dp[l + 1][r - 1][0] + dp[l + 1][r - 1][2] + dp[l + 1][r - 1][3] + dp[l + 1][r - 1][4]) % MOD ;
                for(int i = l ; i <= r - 1 ; ++i)
                {
                    dp[l][r][2] = (dp[l][r][2] + dp[l][i][3] * dp[i+1][r][0]) % MOD ;
                    dp[l][r][3] = (dp[l][r][3] + (dp[l][i][2] + dp[l][i][3]) * dp[i + 1][r][1]) % MOD ;
                    dp[l][r][4] = (dp[l][r][4] + (dp[l][i][4] + dp[l][i][5]) * dp[i + 1][r][1]) % MOD ;
                    dp[l][r][5] = (dp[l][r][5] + dp[l][i][4] * dp[i+1][r][0]) % MOD ;
                }
            }
            dp[l][r][5] = (dp[l][r][5] + dp[l][r][0]) % MOD ;
            dp[l][r][3] = (dp[l][r][3] + dp[l][r][1]) % MOD ;
        }
    }
    printf("%lld" , dp[1][n][3]) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

报数

考场思路：

考虑到这题的数据量似乎不是很大，可以试试直接暴力从当前数向后枚举找到第一个符合要求的数（当然，要先判一下当前输入的数是不是不符合要求）

代码：

#include<iostream>
#include<cmath>
using namespace std ;
inline int read()
{
    int w = 0 , f = 1 ;
    char ch = getchar() ;
    while(!isdigit(ch))
    {
        ch = getchar() ;
        if(ch == '-')
        {
            f = -1 ;
            ch = getchar() ;
            break ;
        }
    }
    while(isdigit(ch))
        w = w * 10 + ch - '0' , ch = getchar() ;
    return w * f ;
}
inline void write(int x)
{
    if(x < 0)
        putchar('-') , x = -x ;
    if(x > 0)
        write(x / 10) , putchar(x % 10 + '0') ;
}
int T = 0 , x = 0 ;
bool p(int x)
{
    while(x > 0)
    {
        if(x % 10 == 7)
            return true ;
        x /= 10 ;
    }
    return false ;
}
bool check(int x)
{
    if(x <= 6)
        return true ;
    if(x == 7 || x == 14)
        return false ;
    int en = sqrt(x) ;
    for(int i = 1 ; i <= en ; ++i)
    {
        if(p(i))
        {
            if(x % i == 0)
                return false ;
        }
        else if(x % i == 0 && p(x / i))
            return false ;
    }
    return true ;
}
int main()
{
    freopen("number.in" , "r" , stdin) ;
    freopen("number.out" , "w" , stdout) ;
    T = read() ;
    while(T--)
    {
        x = read() ;
        if(!check(x))
            write(-1) , putchar('\n') ;
        else
        {
            ++x ;
            while(!check(x))
                ++x ;
            write(x) , putchar('\n') ;
        }
    }
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

结果是一个一个去筛数效率实在太低，只能拿70pts

优化思路：

上面的代码所费的时间主要是在筛数部分，而其中一个一个向后枚举的效率也太低了，这时候，我们可以再看一下题目给的数据范围，发现输入的数都小于$10^7$，因此我们可以考虑使用类似于埃氏筛的方法提前预处理筛出$1$~$10^7+100$之间不满足要求的数，并将它们打上标记，这个预处理的时间复杂度是可以接受的。

但是，在对程序进行测试的时候，我们会发现，这份代码的表现并不是很好，因为它在预处理出所有不符合要求的数后仍然是向后一个一个查找的，如此一来，效率就变低了，因此，我们可以考虑在预处理完后将标记数组逆向扫描一遍，建立一个指针数组，直接记录，每一个数后的第一个合法的数，这样便可将效率大大提高，做到O(1)回答每次问题，这题也就解决了。

优化后代码：

#include<iostream>
#include<cmath>
using namespace std ;
inline int read()
{
    int w = 0 , f = 1 ;
    char ch = getchar() ;
    while(!isdigit(ch))
    {
        ch = getchar() ;
        if(ch == '-')
        {
            f = -1 ;
            ch = getchar() ;
            break ;
        }
    }
    while(isdigit(ch))
        w = w * 10 + ch - '0' , ch = getchar() ;
    return w * f ;
}
inline void write(int x)
{
    if(x < 0)
        putchar('-') , x = -x ;
    if(x > 0)
        write(x / 10) , putchar(x % 10 + '0') ;
}
int T = 0 , x = 0 ;
bool p(int x)
{
    while(x > 0)
    {
        if(x % 10 == 7)
            return true ;
        x /= 10 ;
    }
    return false ;
}
bool flag[10000105] = {} ;
int nxt[10000105] = {} ;
int main()
{
    freopen("number.in" , "r" , stdin) ;
    freopen("number.out" , "w" , stdout) ;
    T = read() ;
    for(int i = 1 ; i <= 10000100 ; ++i)
    {
        if(flag[i])
            continue ;
        if(p(i))
        {
            int en = 10000100 / i ;
            for(int j = 1 ; j <= en ; ++j)
                flag[i * j] = true ;
        }
    }
    int now = 0 ;
    for(int i = 10000100 ;  i >= 1 ; --i)
    {
        if(!flag[i])
            now = i ;
        if(now)
            nxt[i] = now ;
    }
    while(T--)
    {
        x = read() ;
        if(flag[x])
            write(-1) , putchar('\n') ;
        else
            ++x , write(nxt[x]) , putchar('\n') ;
    }
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

数列

考场思路：

这题并没有什么其他思路，只能试一下暴力模拟，深搜枚举出所有可能的序列并求出它们对应的S，也就只能在S的范围上优化一下

考场暴力代码：

#include<iostream>
#define mod 998244353
using namespace std ;
int n = 0 , m = 0 , k = 0 ;
int val[105] = {} ;
int seq[35] = {} ;
long long sum = 0 ;
long long maxs = 0 , mins = 0 ;
bool check()
{
    long long S = 0 ;
    for(int i = 1 ; i <= n ; ++i)
        S += (1 << seq[i]) ;
    if(S < mins || S > maxs)
        return false ;
    int cnt1 = 0 ;
    while(S > 0)
    {
        if(S % 2)
        {
            ++cnt1 ;
            if(cnt1 > k)
                return false ;
        }
        S /= 2 ;
    }
    return cnt1 <= k ;
}
void show()
{
    for(int i = 1 ; i <= n ; ++i)
        printf("%d " , seq[i]) ;
    printf("\n") ;
}
void dfs(int now)
{
    if(now == n + 1)
    {
        if(check())
        {
            long long mul = 1 ;
            for(int i = 1 ; i <= n ; ++i)
                mul *= val[seq[i]] , mul %= mod ;
            sum += mul ;
            sum %= mod ;
            // show() ;
        }
        return ;
    }
    for(int i = 0 ; i <= m ; ++i)
    {
        seq[now] = i ;
        dfs(now + 1) ;
    }
}
int main()
{
    freopen("sequence.in" , "r" , stdin) ;
    freopen("sequence.out" , "w" , stdout) ;
    scanf("%d%d%d" , &n , &m , &k) ;
    for(int i = 0 ; i <= m ; ++i)
        scanf("%d" , &val[i]) ;
    maxs = (long long)n * (1 << m) ;
    mins = (long long)n ;
    dfs(1) ;
    printf("%lld\n" , sum) ;
    fclose(stdin) ;
    fclose(stdout) ;
    return 0 ;
}

优化方案：

我们先厘清一下题意，m是权值数组v的最大下标（下标从0开始），这里称v数组下标集合为A ，n 为下标数组a的长度，每个下标a_i都会在 S 的二进制表示方式的第$a_i + 1$位提供1的贡献，所以 S 的最高位最大只会是$m+\log n$，因为a_i最大也就只能是 m ，所以S的最大值应该是$n \times 2^m$
合法序列的长度为n，其每个元素 a 通过题意描述的相加构成的s在二进制表示中1的个数小于等于K

考虑我们在枚举每一个S ，枚举了每一种构成S的长度为 n 的 a 数组，那复杂度自然很高，于是考虑记录值递推，我们根据 a 值对 S 值的影响来看，发现应该是与二进制数位有关系

我们需要考虑一下合法序列是如何形成的，有 i 个 A 中的元素时已经形成了一个合法序列，其对应的值 S 当然是满足二进制中 1 的个数小于 K ，我们现在要形成一个有 i+t 个A中的元素的合法序列，对于 S 的某一位来看，假设这 t 个新增元素全部选同一位，那么他们对这一位产生了 t 个 1 的贡献，最后实际上 S 这一位有没有 1 取决于 t 加上本身这一位的值的和模除以2的值，也比较明显，对下一位进位的值是上一位对这一位进位的值加上 t 再加上这一位本身的值的和除以2的值。

我们不难发现，我们可以通过将 S 的位数从低到高循环来避免处理该位置原来就有值，虽然处理一种合法序列是由什么序列得到的不好处理，但处理由当前序列得到下一种序列并对其产生怎样的贡献是可求的。

事实上，我们应还需要一维，用来记录当前总共有多少个 A 中的元素已经产生了贡献（最多n个），以及当前 S 中已经有多少个 1 了，同时，我们要处理进位，所以我们考虑使用四维dp[i][j][k][p]：

i ：当前确定到s数组的第i位
j ：当前a序列已经有多少个元素了
k ：当前s二进制表示已经有多少个1了
p ：上一位向这一位进位了多少个1

对于下一个序列的转移，我们考虑假设在A中选了t个i元素（这个后面是通过枚举从1到n-j的，每个都要尝试并记录），i 肯定是变为i + 1 ，j 因为多了 t 个 i 元素，所以变成了 j + t ，k 这第 i 位获得了新的 t 个 1 以及上一位进位来的 p 个 1 ，所以k是否增加取决于 t + p 是否是奇数，而p 对下一位的进位就是$(t + p)/2$

现在考虑当前序列对下一个序列的贡献：多了t个元素i，所以先得乘上一个$pow(i , t)$
并且这t个元素i，是由剩余的 n - j 个空位里被任意安置的（这是一个序列）也就相当于n - j中选 t 个，我们考虑预处理得到任意 n 选 m 的方案数，这里直接乘上即可

最后我们提取答案：
考虑有$i = m - 1$，因为这是贡献递推过来的总和，同时$j = n$序列必须要 n 个元素，而k要加上对后面进位的 p 会增加的1的数量，记为$popcnt(p)$ ，求和即可得到答案。

优化后代码：

#include <iostream>
using namespace std;
#define int long long
const int mod = 998244353;
int ans = 0, v[105] = {}, dp[105][35][35][16] = {}, pv[105][35] = {};
int C[35][35] = {};
void init(int n)
{
    for (int i = 0; i <= n; ++i)
        C[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
int popcnt(int n)
{
    int res = 0;
    while (n) res += n & 1, n >>= 1;
    return res;
}
signed main()
{
    freopen("sequence.in" , "r" , stdin) ;
    freopen("sequence.out" , "w" , stdout) ;
    init(30);
    int n = 0, m = 0, K = 0;
    scanf("%lld %lld %lld", &n, &m, &K);
    for (int i = 0; i <= m; i++)
    {
        scanf("%lld", &v[i]);
        pv[i][0] = 1;
        for (int j = 1; j <= n; ++j)
            pv[i][j] = pv[i][j - 1] * v[i] % mod;
    }
    dp[0][0][0][0] = 1;
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= n; ++j)
            for (int k = 0; k <= K; ++k)
                for (int p = 0; p <= n >> 1; ++p)
                    for (int t = 0; t <= n - j; ++t)
                        dp[i + 1][j + t][k + (t + p & 1)][t + p >> 1] = (dp[i + 1][j + t][k + (t + p & 1)][t + p >> 1] + dp[i][j][k][p] * pv[i][t] % mod * C[n - j][t] % mod) % mod;
    for (int k = 0; k <= K; ++k)
        for (int p = 0; p <= n >> 1; ++p)
            if (k + popcnt(p) <= K) ans = (ans + dp[m + 1][n][k][p]) % mod;
    printf("%lld", ans);
    fclose(stdin) ;
    fclose(stdout) ;
    return 0;
}

写在最后：

暴力能力很重要，优化过的暴力可以拿到较高的分数，还是要多练暴力，当然，考试时碰到没有思路的题目时也不要慌，先冷静一下看它与自己学过的哪些知识有关，实在没办法还可以先写一个暴搜，然后再加上记忆化，这样也能拿大部分分（警示：现阶段题目如果30分钟还没有思路就应果断换下一题，让头脑清醒一下，等一下有时间再来看）~~（血的教训）~~

标签：ch,return,21,测试题,int,23,else,include,dp
From： https://www.cnblogs.com/Torrentolf/p/18561354

23集训测试题(10.8)

密码锁

暴力代码

但是这题其实也可以使用计数DP

代码

消消乐

考场35分思路：

考场代码：

稍微优化一些：

50分代码：

最终思路：

最终代码：

词典

考场思路：

考场代码：

更优的思路：

优化代码：

三值逻辑

考场思路：

考场代码：

正解思路：

代码：

22集训测试题(10.9)

种花

考场思路：

考场代码(加了换行)：

优化思路：

记忆化搜索代码：

最终思路：

最终代码：

喵了个喵

考场思路：

正解：

存在一个编号为sp的空栈，且当前牌堆顶的牌在场上存在或其余栈中存在至少一个栈大小不超过1，如果当前牌堆顶的牌在场上出现过就执行上面的消除方法，若无，则将此牌放入一个大小不超过1

存在一个编号为 sp 的空栈，且不满足策略1条件。

代码：

假期计划

考场思路：

Floyed版

BFS 版

优化思路：

代码：

策略游戏

考场思路：

正确思路：

A 在 a[l1······r1] 中选择一个 x，然后 B 在 b[l2······r2] 中选择一个 y，分数是 \(x \times y\)，A 想让分数尽可能大，B 想让分数尽可能小。求最终分数。

代码：

21集训测试题(10.10)

廊桥分配

考场思路：

暴力代码:

优化思路：

代码：

括号序列

考场思路：

正解思路：

代码：

报数

考场思路：

代码：

优化思路：

优化后代码：

数列

考场思路：

考场暴力代码：

优化方案：

优化后代码：

写在最后：

相关文章

赞助商

阅读排行

A 在 a[l₁······r₁] 中选择一个 x，然后 B 在 b[l₂······r₂] 中选择一个 y，分数是 \(x \times y\)，A 想让分数尽可能大，B 想让分数尽可能小。求最终分数。