[toc]

本页面记录了本人在赛时和赛后的思路和相关问题以及对应解法,总结和反思

cf

2025cccc选拔赛

后记:一定要用成熟的版本,不要临时求变,一定要巩固好最稳定的做法.前几题考不到什么大的知识点的,主要都是侧重思维,因此一定要注意自己解法在思维上的投入(太少太暴力模拟肯定不对),肯定不能过于直观,一般一定是错的,要不在此基础上优化,要不就全部推翻用新思路.确定了绝对不可能的思路那就一定要及时完全跳出来,不要再被拖累了,每次都是先想到了巨麻烦的做法但是又总不即时抛弃掉,脑子跳不出来想.

B 放烟花

Bob喜欢放烟花，他购买了两个烟花发射装置和大量的发射炮弹。

两个装置同时开启。第一个装置每隔 $a$ 分钟（即开启后 $a, 2 \cdot a, 3 \cdot a, \dots$ 分钟）发射一次烟花。第二个装置每隔 $b$ 分钟（即开启后 $b, 2 \cdot b, 3 \cdot b, \dots$ 分钟）发射一次烟花。

每个烟花在发射后的 $m + 1$ 分钟内都可以在天空中看到，也就是说，如果一个烟花是在装置开启后的 $x$ 分钟后发射的，那么从 $x$ 到 $x + m$ （包括首尾两分钟）的每一分钟都可以看到该烟花。如果一个烟花在另一个烟花 $m$ 分钟后发射，则两个烟花都将在一分钟内可见。

天空中最多可以同时看到多少枚烟花？

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ 代表测试用例数。

每个测试用例的第一行也是唯一一行包含整数 $a$, $b$, $m$ $(1 \le a, b, m \le 10^{18})$ 代表第一个装置、第二个装置的发射频率和烟花在天空中可见的时间。

赛时思路:画图直观枚举叠加,发现数据量过大暴力不行,又想到差分(?),根据样例分析直接盲猜*2做差的结论(?),后面才发现只需求出各个区间内最多后再相加即可

正确思路:由于时间无限,直接求出各个区间内最多后再相加即可,总有重叠的时候.

反思:不要直观画图了真就完全只按直观的来,肯定要在图上思考优化的,甚至是推翻图重做,思路一定要打开,别把前面的题就想得那么难直接硬套太多大知识点.可以根据样例分析而思考相应做法,但样例分析肯定不会完全透出正解甚至可能完全跟正解做法不相关(纯暴力模拟),绝对不能完全依靠据此猜得的各种结论和做法.

C 自然语言处理

Alice 觉得无聊，于是决定用五个字母 $\texttt{a}$ , $\texttt{b}$ , $\texttt{c}$ , $\texttt{d}$ , $\texttt{e}$ 创造一种简单的语言。字母分为两类：

  • 元音 — 字母 $\texttt{a}$ 和 $\texttt{e}$ 。用 $\textsf{V}$ 表示。
  • 辅音 — 字母 $\texttt{b}$ , $\texttt{c}$ 和 $\texttt{d}$ 。用 $\textsf{C}$ 表示。

这种语言中有两种类型的音节： $\textsf{CV}$ （辅音后接元音）或 $\textsf{CVC}$ （元音前后均有辅音）。例如， $\texttt{ba}$ , $\texttt{ced}$ , $\texttt{bab}$ 是音节，但 $\texttt{aa}$ , $\texttt{eda}$ , $\texttt{baba}$ 不是。

语言的单词由音节序列构成。Alice 写了一个单词，但她不知道如何将其分割为音节。请帮助她分割单词。

例如，给定单词 $\texttt{bacedbab}$ ，应分割为 $\texttt{ba.ced.bab}$ （点 $\texttt{.}$ 表示音节边界）。

Input

输入包含多个测试用例。

第一行包含一个整数 $t$ $(1 \leq t \leq 100)$ 代表测试用例数量。接下来描述每个测试用例。

每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^5)$ 代表单词长度。

每个测试用例的第二行包含一个由 $n$ 个小写拉丁字母组成的字符串，代表要分割的单词。

所有给定的单词均为合法单词，即仅使用字母 $\texttt{a}$, $\texttt{b}$, $\texttt{c}$, $\texttt{d}$, $\texttt{e}$，且每个单词由若干音节构成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

Output

对每个测试用例，输出一个字符串，通过在相邻音节间插入点 .. 来表示分割后的结果。

若存在多种可能的分割方式，输出任意一种即可。输入保证至少存在一种有效分割。

赛时思路:一个个找出来再分割,不同的分割情况相应深搜再剪枝叶(?),后面发现数据量太大不可能,随后观察题意,才发现有元音处一定有分割,于是想先找出所有元音位置后再进行分割然后再深搜剪枝(?),发现肯定也太麻烦,后面对比两种形式后才发现元音前一定是辅音,只要在辅音前加.则一定会满足题意(题目保证了一定有一种解法,这样一定最优,无论哪种分割都不会漏点)

正解思路:对比两种形式后才发现元音前一定是辅音,只要在辅音前加.则一定会满足题意(题目保证了一定有一种解法,这样一定最优,无论哪种分割都不会漏点)

反思:要学会观察题意对比,找出共通点从而形成简单而符合题意的思路.

代码问题:

1
2
3
4
5
6
7
8
9
repp(i,0,s.length()-1)//循环中用了s.length,由于字符串被修改且长度变化,这里循环次数也是会变化的
        {
            if(s[i]=='a'||s[i]=='e')
            {
            s.insert(i-1,".");//就在该位置插入,然后把后面字符串往后推
            i++;//关键一步,如果插入了,则肯定要再向后推(s长度变化了),不然这里指向的位置就不再是原来的a/e
        }
        }
        s.erase(s.begin());//前面肯定会有一个多的点,要删除掉

D 数学平均数

Bob 有一个由 $n$ 个整数组成的数组 $a$。让我们用 $k$ 表示这些元素的数学平均数（注意 $k$ 有可能不是整数）。

由 $n$ 个元素组成的数组的数学平均数是所有元素之和除以这些元素的个数（即和除以 $n$）。

Bob 希望从 $a$ 中恰好删除两个元素，这样剩下的 $(n - 2)$ 个元素的数学平均数仍然等于 $k$。

你的任务是计算有多少对位置 $[i, j]$ (i < j)$，使得删除这些位置上的两个元素后，剩下的 $(n - 2)$ 个元素的数学平均数仍然等于 $k$（即等于原数组 $a中 n个元素的数学平均数）。

赛时思路:求出所有i-n的数的出现次数,一开始想用二分,但发现并非有序,但发现空间太大,无法完成,又尝试用map映射,但发现也是空间太大,实现不了(本质都没变),

正解思路:先处理好1-n的数的出现次数,再倒序遍历,对于遍历到每个数时减去一次该数相应求平均数对象的出现次数,再加和即为1-i-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
int a[(int)2e5+3];
int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        unordered_map<int,int>s;//记得每次都要重新开,得hu
        lld sum=0;lld ans=0;
        repp(i,1,n){
            cin>>a[i];
            sum+=a[i];
            s[a[i]]++;
        }
        lf k0=(sum*2.0/n);lld k=(sum*2.0/n);
        if(k0!=k)
        {
            cout<<0<<endl;ct;
        }
        else
        {
            repm(i,n,1)
            {
                int a0=k-a[i];s[a[i]]--;
                ans+=(s[a0]);
            }
        }
        cout<<ans<<endl;
    }
}

牛客

2025 牛客寒假训练1

G 调整出1-n序列(贪心+排序)

题意：给一个数组，每次操作可以使一个元素加1，另一个元素减1，问变成排列的最小操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
lld a[100003],sum,ans;bool biao[100003];vi dai,que;
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    //int t;cin>>t;
    //while(t--){ }
    lld n;cin>>n;
    repp(i,1,n)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(sum!=(n*(n+1))/2)//加减操作不应影响整个的和
    {cout<<-1;ret 0;}
    sort(a+1,a+1+n);
    repp(i,1,n)
    {
        ans+=abs(a[i]-i);//对应操作
    }
    cout<<ans/2;//取一半即可,加减操作次数相同
    ret 0;
}

E 双生双宿之错

题意：给定一个数组，每次操作可以使得一个元素加1或者减1，问最小操作几次可以变成双生数组，即元素种类数为2、且出现次数相同。

中位数定理：给定一个数组，每次操作加1或者减1，将所有元素变成相同的最小操作次数则是将所有元素变成中位数即可。(出现浮点数时整左右哪个整数都行,因为左右两半的数个数是相同的)

2a4d15a25658e929758cd4a0a0afd4d2

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
lld a[100003],x,y,t,n;
lld check(lld xx,lld yy)
{
    lld sum=0;
    if(xx!=yy)
    {
        repp(i,1,t)
        sum+=abs(a[i]-xx);
        repp(i,t+1,n)
        sum+=abs(a[i]-yy);
    }
    else//如果相等分类讨论取最小
    {
        lld sum1=0;lld sum2=0;
        repp(i,1,t)
        sum1+=abs(a[i]-(xx-1));
        repp(i,t+1,n)
        sum1+=abs(a[i]-yy);
        repp(i,1,t)
        sum2+=abs(a[i]-xx);
        repp(i,t+1,n)
        sum2+=abs(a[i]-(yy+1));
        sum=min(sum1,sum2);
    }
    ret sum;
}
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    int k;cin>>k;//记得把t换了
    while(k--){ 
    cin>>n;
    repp(i,1,n)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);//排好序
    t=n>>1;//拆一半
    if(t&1)//如何取中位数
    {
        x=a[(t+1)/2];
        y=a[(n+t+1)/2];
    }
    else
    {
        x=a[t/2];//不统一方向取,尽量防止相等
        y=a[(n+t+1)/2];
    }
    cout<<check(x, y)<<endl;//输出处理结果
    }
    ret 0;
}

M 数值膨胀之美

STL、排序，枚举

要使得数组极差变小，显然需要先让最小值乘以 2 ，然后是次小值，……，以此类推。

新的区间一定会包含这个区间.我们需要在每次乘以 2 操作后计算数组的极差。

我们需要一个容器：每次操作可以在容器中删除一个数，并插入一个数。符合条件的容器有许多，我们选择的是 multiset

时间复杂度 O(nlogn)。

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
int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1);//用于读取
    vector<pair<int, int>> b;//用于形成映射并排序
    multiset<int> st;//用于读取两个最值
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b.push_back({a[i], i});//用{}也能造pair
        st.insert(a[i]);
    }
    sort(b.begin(),b.end());//排序,从而读取原序列第k小值位置
    multiset<int>::iterator it;//先定义迭代器及其类型(auto 在 if里面不给用)
    auto [l, r] = b[0];//读取pair的一种方法
    if(( it=st.find(l))!=st.end())st.erase(it);//只能删除一个数一次,不然还得数多少个,麻烦
    st.insert(l * 2);
    int ans = *st.rbegin() - *st.begin();//逆向即末尾数
    l = r;
    for(auto &[_, i] : b){//当用不上一个元素时,可用_代替(记得打上&)
        if(i >= l && i <= r) continue;
        for(int j = l - 1; j >= i; j--){
            if((it=st.find(a[j]))!=st.end())st.erase(it);
            st.insert(a[j] * 2);
            ans = min(ans, *st.rbegin() - *st.begin());
        }
        l = min(l, i);
        for(int j = r + 1; j <= i; j++){
            if((it=st.find(a[j]))!=st.end())st.erase(it);
            st.insert(a[j] * 2);
            ans = min(ans, *st.rbegin() - *st.begin());
        }
        r = max(r, i);
    }
    cout << ans << endl;
}

H 井然有序之窗

构造、贪心

从小到大考虑(后面选择合理的前提条件)1-n的数.在符合要求(l<i,此时选择l更大的或者更小的都不会影响最终结果,因为都是符合这个要求的了)的所有区间中选择 r 最小的区间给使用掉(限制最严的)一定不会使得答案变劣。

可以使用优先队列维护右端点最小的区间，对区间先按左端点排序后，可以从前往后将左端点小于i的区间加入优先队列(所以这个优先队列里的一直都能用,因为i是从小到大考虑的,i增大后放进来的数也肯定还满足l<i)，然后取出右端点最小的区间。

若右端点小于i ，理论上应该将这个区间丢弃，找到第一个满足右端点大于等于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
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
st qujian{
    int l;int r;int hao;
};
bool cmp(qujian a,qujian b)//用于sort比较的
{
    if(a.l!=b.l)
    ret(a.l<b.l);
    else
    ret(a.r<b.r);
}
bool operator <(qujian a,qujian b)//用于pq特殊比较的
{
    if(a.l!=b.l)
    ret(a.l>b.l);//记得反过来
    else
    ret(a.r>b.r);
}
lld n,a[M];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;int nowhao=0;//标记第几个区间
    pq<qujian>q;
    deque<qujian>s(n);//提前预定好空间,从而下面可借助引用&读取输入
    for(auto &[l, r, i] : s){
        cin >> l >> r;
        i = ++nowhao;
    }
    sort(s.begin(),s.end(),cmp);
    repp(i,1,n)
    {
        while(s.size()&&s.front().l<=i)
        {
            auto [l,r,hao]=s.front();s.pop_front();//因为不可以浪费,所以这里直接弹出就好
            q.push({r,l,hao});//注意只在这边反着存入,读取时仍然按原定义的l,r顺序读取
        }
        if(q.empty()){//特判空的1情况
            cout<<-1;ret 0;
        }
        auto tt=q.top();
        if(i>tt.l)//肯定不符合要求了
        {
            cout<<-1;
            ret 0;
        }
        else
        {
            a[tt.hao]=i;q.pop();//在a的指定位置填入i
        }
    }
    repp(i,1,n)cout<<a[i]<<' ';
    ret 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
int main(){
    int n;
    cin >> n;
    deque<array<int, 3>> a(n);
    int pt = 0;
    for(auto &[l, r, i] : a){
        cin >> l >> r;
        i = ++pt;
    }
    ranges::sort(a);
    vector<int> ans(n + 1);
    set<array<int, 3>> st;
    for(int i = 1; i <= n; i++){
        while(a.size() && a[0][0] <= i){
            auto [l, r, i] = a[0];
            st.insert({r, l, i});
            a.pop_front();
        }
        if(!st.size()){
            cout << -1 << endl;
            return 0;
        }
        auto [r, l, j] = *st.begin();
        st.erase(st.begin());
        if(r < i){
            cout << -1 << endl;
            return 0;
        }
        ans[j] = i;
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}


J 硝基甲苯之袭

因数分解、打表、质数筛

先x 的因子 t,再枚举 x ，那么 y=x⊕t，再检查 gcd(x,y)=t 是否合法(逆向思维)**，若合法统计答案。

时间复杂度 O(nsqrt(n)) ，使用质数筛大概可以优化到 O(nlogn)) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ci M = (int)2e5+10;
lld n,a[M],maxn,ans;
signed main()
{
        cin>>n;unordered_map<lld,lld>s;//标记出现次数
        repp(i,1,n){
			cin>>a[i];s[a[i]]++;maxn=max(maxn,a[i]);}
		repp(i,1,maxn)//先枚举x的因子
		{
			for(lld j=i;j<=maxn;j+=i)//再枚举数x
			{
				lld k=i^j;
				if(j<k&&__gcd(j,k)==i&&k<=maxn)//需满足的条件
				ans+=s[j]*s[k];//如果两个数都存在才会叠加
			}
		}
		cout<<ans;
}

2025牛客寒假训练营

D 字符串里串

思维、贪心

有一个比较容易想到的结论，如果从前往后第i>1个字符在i之后的第j个位置还出现过，那么选择这[1,i]]前缀作为子串，子序列就把[1,i-1]和[j,j]拼在一起，就得到了两个不一样的子串。

然后把字符串翻转一下，再跑一次即可（从前往后和从后往前都是可以的不要只有一个方向）。

注意 “aba” 的答案是 0 ，而不是 1 ，之前 std 也错了，不过数据里没有这个，所以不考虑这一个也能过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    set<int> st;
    int ans = 0;
    for(int i = n; i >= 2; i--){
        if(st.count(s[i])){ ans = max(ans, i);break;}//看后面有没有这个字母,仅在此可break
        st.insert(s[i]);
    }
    st = set<int>();//可以清空
    for(int i = 1; i <= n - 1; i++){//另一个方向
        if(st.count(s[i])) ans = max(ans, n - i + 1);
        st.insert(s[i]);
    }
    cout << ans << endl;
}

C 字符串外串

构造

首先要知道D题的结论，那我们需要构造一个字符串使得从前往后看和从后往前看可爱度都是m的字符串。

那就思考一下类似回文串的构造方法。

如果 n超过了m的两倍，意味着前m个和后m个字母对称（”abcdefcba”），中间n-2m个字母在整个字符串中全都只能出现一次，总共需要的字母种类是m+n-2m=n-m，很显然字母种类不能超过26个。

如果 n不超过m的两倍，意味着前 n-m个和后n-m个字母对称（”abczzzcba”），中间字母任意，总共需要的字母种类是n-m，很显然字母种类不能超过26个。

按上述情况分类讨论构造一下即可。

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
int m,n;
string s;
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;string ans="";
        if(n-m>26||n<=m){
            cout<<"NO"<<endl;ct;
        }
        else
        {
            cout<<"YES"<<endl;
            if(n>=2*m)
            {
                repp(i,0,m-1)
                {
                    ans+=('a'+i);
                }
                repp(i,m,n-m-1)
                {
                    ans+=('a'+i);
                }
                repm(i,m-1,0)
                {
                    ans+=('a'+i);
                }
            }
            else
            {
                repp(i,0,n-m-1)
                {
                    ans+=('a'+i);
                }
                repp(i,1,2*m-n)
                {
                    ans+=('a'+n-m-1);
                }
                repm(i,n-m-1,0)
                {
                    ans+=('a'+i);
                }
            }
            cout<<ans<<endl;
        }
    }
    ret 0;
}

H 一起画很大的圆！

构造、计算几何，贪心

三个不共线的点确定一个圆。

如果这三个点越接近一条直线，这个圆最大(三点共线的时候这个最大)。

那么我们需要在边界上找三个点使得最接近一条直线，猜一下有一个点会在边角，那剩下的点就不难确定了。

横着可以找到一个答案是9d846c00bf84543b285250dadf59bd12，但如果c32aae6022cbfb5e60918fcde1845b07 的话，就应该竖着找。

显然在长边取两个点越接近直线斜边也越长

我们应当使得斜边尽可能的大，同时斜边所对的角尽可能的接近0 或 180 ^{\circ}。前者很好实现，令长边上的一点位于角落（如图中点A，短边上点尽可能靠近角落（如图中点C)，此时可使得AB所对的锐角角度最小(相切那个是角度最大)。

alt

再移动一位取B

alt

那么关键就在于找出长边了.