Butteruni Blog
0%

2023牛客暑期多校4（A D F H J L）

发表于 分类于

题目连接

由易到难为：LFA，J，HD

L. We are the Lights

从后往前遍历，对于行和列只计算最后一次操作对答案的贡献即可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
struct Node
{
    string t;
    int idx;
    string op;
}ls[N];
ll n,m;
ll q;
bool r[N],c[N];
ll cntr,cntc;
ll ans;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>ls[i].t>>ls[i].idx>>ls[i].op;
    }
    for(int i=q;i>=1;i--)
    {
        if(ls[i].t=="row")
        {
            if(r[ls[i].idx])continue;
            r[ls[i].idx]=true;
            cntr++;
            if(ls[i].op=="on")
            {
                ans+=m-cntc;
            }
        }
        else if(ls[i].t=="column")
        {
            if(c[ls[i].idx])continue;
            c[ls[i].idx]=true;
            cntc++;
            if(ls[i].op=="on")
            {
                ans+=n-cntr;
            }
        }
    }
    cout<<ans;
    return 0;
}

F. Election of the King

先对所有人进行排序，显然每次出局的人是会是最左或最右的人。依题意每次投票时对于 投最右的人，有 都投最右，投最左同理，于是每次被投出去的是最左还是最右只取决于最中间的人投最左还是最右。以此投到最后一个即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll n;
map<ll,ll> a2i;
ll ls[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>ls[i];
        a2i[ls[i]]=i;
    }
    sort(ls+1,ls+n+1);
    ll l=1,r=n;
    while(l<r)
    {
        ll mid=(ls[l]+ls[r])/2;
        // cout<<l<<" "<<r<<"---"<<mid<<"\n";
        ll L=l,R=r;
        while(L<R)
        {
            ll MID=L+R+1>>1;
            if(ls[MID]<=mid)L=MID;
            else R=MID-1;
        }
        if(L-l+1>=r-L)r--;
        else l++;
    }
    cout<<a2i[ls[l]];
    return 0;
}

A. Bobo String Construction

显然 全为1或全为0中至少有一个满足条件，于是分别计算 全为1和 全为0下的 是否只能识别出两个 即可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int T;
int n;
string t;
int ne[N];
void getNext(string p)
{
    int m=p.length()-1;
    for(int i=2,j=0;i<=m;i++)
    {
        while(j&&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }
}
// 匹配
bool KMP(string s,string p)
{
    int n=s.length()-1,m=p.length()-1;
    int cnt = 0;
    for(int i=1,j=0;i<=n;i++)
    {
        while(j&&s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==m)
        {
            j=ne[j];
            cnt++;
        }
    }
    return cnt == 2;
}
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>T;
    while(T--)
    {
        memset(ne,0,sizeof(ne));
        cin>>n;
        cin>>t;
        getNext(" "+t);
        string s0,s1;
        for(int i=1;i<=n;i++)
        {
            s0+='0';
            s1+='1';
        }
        if(KMP(" "+t.substr(0,t.length())+s0+t.substr(0,t.length())," "+t))
        {
            cout<<s0<<"\n";
        }
        else
        {
            cout<<s1<<"\n";
        }
    }
    return 0;
}

J. Qu'est-ce Que C'est?

记 表示对于长度为 的序列，最小后缀为 的方案数。读者可自行枚举 的情况可知此时 合法且可进行状态转移。考虑下一个数放 ，要使得放进去后序列不回非法，存在 因此 可以转移到 ，其中 ， 从 的角度考虑，即为 ，其中 满足 ，使用滚动数组加前缀和优化，分别将空间复杂度优化到 和 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 5010;
ll dp[2][3 * N];
ll pre[2 * N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    if(n == 1)
    {
        cout << (2 * m + 1) << '\n';
    }else 
    {
        for(int i = 1;i <= n;++i)
        {
            int t = (i & 1);
            if(i == 1)
            {
                for(int j = 0;j <= 2 * m;++j)
                    dp[t][j] = 1;
                pre[0] = dp[t][0];
                for(int j = 1;j <= 2 * m;++j)
                {
                    pre[j] = (pre[j - 1] + dp[t][j] + mod) % mod;
                }
            }else 
            {
                for(int j = 0;j <= 2 * m;++j)
                {
                    if(j < m)
                        dp[t][j] = (pre[2 * m] - pre[2 * m - 1 - j] + mod) % mod;
                    else if(j > m)
                        dp[t][j] = (pre[2 * m] - pre[j - m - 1] + mod) % mod;
                    else 
                        dp[t][j] = pre[2 * m];
//                     cout << dp[t][j] << " | ";
                }
//                 cout << endl;
                pre[0] = dp[t][0];
                for(int j = 1;j <= 2 * m;++j)
                {
                    pre[j] = (pre[j - 1] + dp[t][j] + mod) % mod;
//                     cout << pre[j] << ' ';
                }
            }
        }
        ll ans = 0;
        int t = n & 1;
        for(int i = 0;i <= 2 * m;++i)
        {
            ans = (ans + dp[t][i] + mod) % mod;
        }
        cout << ans << endl;
    }

}

H. Merge the squares!

本题解法来自 jiangly。

看完题目首先考虑到这是一道分治题，将 的大正方形拆分成数量小于等于 个小正方形，将这些小正方形向下拆成数量小于 的的小小正方形直至所有小正方形均为 即可。接下来考虑如何拆分。

对于一开始的 正方形 ，现在左上角做一个大小为 的小正方形，在右下角做一个 小正方形，对于这两个小正方形不妨令 此时在原 正方形的左下角和右上角均出现了一个 的矩形，已知要将 的正方形拆成数量不超过50的小正方形，如果此时 矩形能拆封成不超过 个小正方形则此次拆分合法。

接下来考虑如何拆分 矩形，先考虑一种贪心的做法，每次使用 ， 中较小的那个作为小正方形的边长进行填充，直到填完或形成一个新的矩形，接下来对新矩形如法炮制即可，整个过程相当于对 进行辗转相除并对每次的系数求和。

显然，我们无法保证对于每个 都能找到合法拆法（ 显然不符合要求），因此对于每个 （这里假定 为矩形长边）需要找到一个 使得 矩形存在合法拆法。对于 经打表得知一定存在一个 使得 合法

考虑递归拆解图形是否一定可行，若当前要拆分 正方形， 令拆出的矩形为 ，（其中 为预处理出的使 合法的 ）此时两个小正方形边长分别为 和 ， ；若当前要拆分 矩形，显然对于一个合法矩形，拆除一个最大正方形（边长为 ）后的剩下的小矩形一定合法。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
struct op
{
    int x,y,size;
};
void init() //预处理 i * j 矩形
{
    for(int i = 2;i <= 1000;++i)
    {
        for(int j = 1;j < i;++j)
        {
            int cnt = 1;
            int a = j,b = i - j;
            while(b)
            {
                cnt += a / b;
                a %= b;
                swap(a,b);
            }
            if(cnt <= 24)
            {
                f[i] = j;
                break;
            }
        }
    }
}
vector<op>ans;
void solve(int x1,int y1,int x2,int y2)
{
    if(x2 - x1 == y2 - y1) //此时框出一个正方形
    {
        if(x2 - x1 == 1) //刚好框出 1 * 1
            return;
        int k = f[x2 - x1]; 
        solve(x1,y1,x1 + k,y1 + k);
        solve(x1 + k,y1 + k,x2,y2);
        solve(x1,y1 + k,x1 + k,y2);
        solve(x1 + k,y1,x2,y1 + k);
        ans.push_back(op{x1,y1,x2 - x1});
        return;
    }
    if(x2 - x1 > y2 - y1) //此时框出一个矩形，则分类讨论小正方形边长是哪一边
    {
        int d = y2 - y1;
        solve(x1,y1,x1 + d,y2);
        solve(x1 + d,y1,x2,y2);
    }else 
    {
        int d =  x2 - x1;
        solve(x1,y1,x2,y1 + d);
        solve(x1,y1 + d,x2,y2);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    init();
    solve(0,0,n,n);    
    cout << ans.size() << '\n';
    for(auto temp : ans)
    {
        cout << temp.x + 1 << " " << temp.y + 1 << " " << temp.size << '\n'; 
    }
}

D. Classical Problem?

同上，本题解法来自 jiangly 。

记 为 在 进制下 最终答案 ，若 ，显然当 时 取到最小值 ，若 较小，也可直接暴力枚举所有可能（每次计算 复杂度为 ，关键在 较大且小于 时如何处理。

由于 ，假设最优进制 ，显然存在 （d为最高位)，且对 有

考虑 可能的范围，有 ，由于存在 ，有 先枚举 再枚举 得到 的一个上界，然后枚举所有满足以下条件的 即可 其中第一项式子可转化成

进而转化成 即

因此

枚举 的所有可能解复杂度 ，枚举 需要 枚举 需要 ，二分求出 需要 ，枚举所有可行 需要 ，整体复杂度 

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
#define i128 __int128
const i128 N = 1e4;
int T;
i128 n, K, ans;
 
inline i128 read() 
{
   char c = getchar() ;
   i128 num = 0 , f = 1 ;
   for (; c < '0' || c > '9' ; c = getchar()) if (c == '-') f = -f ;
   for (; c >= '0' && c <= '9' ; c = getchar()) num = num * 10 - '0' + c ;
 
   return num * f ;
}
 
inline void print(i128 num)
{
   if (!num) 
   {
       puts("0"); 
       return;
   }
   vector<int> ch;
   for (; num ; ch.push_back(num % 10) , num /= 10);
   reverse(ch.begin() , ch.end());
   for (auto x : ch) 
       putchar((char)(x + '0'));
   putchar('\n');
}
inline i128 qpow(i128 a,i128 b)
{
    i128 res = 1;
    while(b > 0)
    {
        if(b / 2 == 1)
            res = res * a;
        a = a * a;
        b = b / 2;
    }
    return res;
}
inline void check(i128 k) 
{
   if (k < 2 || K < k) 
       return;
   i128 sum = 0 ;
   for (i128 t = n ; t ; t /= k) 
       sum += t % k;
   if (ans == -1) 
       ans = sum;
   else 
       ans = min(ans , sum);
}
 
bool num_check(i128 k , int L , int a) {
   i128 kL = 1;
   for (int i = 0 ; i < L - 1 ; ++i)
   {
      if (n / kL < k) 
          return 0;
      kL *= k;
   }
    
   if (n / kL < a) 
       return 0;
   return 1 ;
}
 
int main() {
   scanf("%d" , &T) ;
   while(T--)
   {
      n = read(); K = read();
      if(K >= n)
      {
          cout << 1 << "\n";
          continue;
      }
      ans = -1;
      int lim = min(N , K);
      for (int i = 2; i <= lim; ++i) 
          check(i);
      for (i128 d = 2; d <= 12; ++d)
         for (i128 a = 1; a <= ans; ++a) 
         {
            i128 l = lim + 1, r = K + 1;
            while (l < r) 
            {
               i128 mid = (l + r + 1) >> 1;
               if (num_check(mid,d,a)) 
                   l = mid;
               else 
                   r = mid - 1;
            }
            i128 k = l + 1;
            for (int i = 1; i <= ans - a; ++i) 
                check(k - i);
         }
      print(ans) ;
   }
   return 0;
}