2025.9.28

D-小红的好数对_牛客周赛 Round 111

解题思路:

巧妙枚举

a*10^len(b)+b%11=0;

->

b%11=-a*10^len(b);

[!IMPORTANT]

//减法取模
(A - B) % mod =((A % mod) - (B % mod) +mod) % mod

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;
#define int long long
const int inf=0x3f3f3f3f,N = 2e5 + 5;
int a[N],sz[N];
int p[15];
int f[15][11];
void init(){
    p[0]=1;
    for(int i=1;i<=11;i++){
        p[i]=(p[i-1]*10)%11;
    }
}
void solve(){
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sz[i]=to_string(a[i]).size();
        f[sz[i]][a[i]%11]++;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=11;j++){
            int t=(-a[i]*p[j]%11+11)%11;
            sum+=f[j][t];
        }
        if((-a[i]*p[sz[i]]%11+11)%11==a[i]%11)sum--;
    }
    cout<<sum<<'\n';
    
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    init();
    while(t--){
        solve();
    }
	return 0;
}

E-小芳的排列构造_牛客周赛 Round 111

当时我的难点是不知道如何凑k=k-3*n-1,(我采用的是从小到大凑,但在大脑中进行模拟时出现了混乱)

答案给出的是从大往小的凑,通过标记对进行凑k的数进行标记

[!CAUTION]

  1. 大数优先的优势：
    • 较大的 i 能提供更多的逆序对贡献（一次选择可减少更多 k 值）
    • 先选大数可以避免 “小数占用位置导致大数无法选择” 的问题
    • 能确保在 k 值较大时，用最少的选择次数凑够目标值
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e5 + 5;
int vis[N];
void solve(){
    int n,k;
    cin>>n>>k;
    if(n==1&&k==2){
        cout<<1<<'\n';
        return;
    }
    k-=(3*n-1);
    vector<int>vec;
    for(int i=n-2;i>=1;i--){
        if(k>=i){
            k-=i;
            vis[i]=1;
            vec.push_back(i);
        }
        if(k<=0)break;
    }
    if(k!=0){
        cout<<-1<<'\n';
        return;
    }
    for(int i=vec.size()-1;i>=0;i--){
        cout<<vec[i]<<' ';
    }
    cout<<n-1<<' ';
    for(int i=1;i<=n-2;i++){
        if(!vis[i])cout<<i<<' ';
    }
    cout<<n<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
//     cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

F-小红的排列构造_牛客周赛 Round 111

//构造题

//先a[i]和a[n-i+1]交换

//在从a[i]依次往后交换

//因为发现了实施这种方案的最多交换次数是n-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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e5 + 5;
int a[N];
void solve(){
    int n,k;
    cin>>n>>k;
    if((n+1)/2>k||k>n-1){
        cout<<-1<<'\n';
        return;
    }
    for(int i=1;i<=n;i++)a[i]=i;
    for(int i=1;i<=n/2;i++){
        int t=a[i];
        a[i]=a[n-i+1];
        a[n-i+1]=t;
    }
    if(n%2!=0){
        int t=a[n/2];
        a[n/2]=a[n/2+1];
        a[n/2+1]=t;
        k--;
    }
    k-=n/2;
    int i=1,flag=1;
    while(k--){
        if(i+1>n){
            flag=0;
            break;
        }
        int t=a[i];
        a[i]=a[i+1];
        a[i+1]=t;
        i++;
    }
    if(flag==0){
        cout<<-1<<'\n';
        return;
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
//     cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.10.7

D-Digital Pairing_牛客周赛 Round 112

//在保留前面结果的同时,进行假设如果,假设成立则该位有1

//新知识:如何在某数的某一位置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
30
31
32
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 4e5 + 5;
void solve(){
    int n;
    cin>>n;
    vector<int>vec(2*n+1);
    for(int i=1;i<=2*n;i++){
        cin>>vec[i];
    }
    int ans=0;
    for(int i=31;i>=0;i--){
        int cnt=0,cand=ans|(1<<i);
        for(int j=1;j<=2*n;j++){
            if((cand&vec[j])==cand)cnt++;
        }
        if(cnt>=n)ans=cand;
    }
    cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

E-Beautiful Sequence_牛客周赛 Round 112

//感觉的数学很好才能做,组合数学功底厚实,找规律的功底厚实

//1 1 3 4

2^3+2^2=(c(2,0)+c(2,1)+c(2,2))*3

//根据答案改错之后一直错误很可能的原因就是超时

//对2的幂进行预处理

//不用i64也行,long long也行

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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const i64 inf=0x3f3f3f3f,N = 2e5 + 1,mod=998244353;
i64 cnt[N];
i64 pw[N];
void solve(){
    int n;
    cin>>n;
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        cnt[a]++;
    }
    i64 ans=(pw[n]%mod-1%mod+mod)%mod;
    for(int i=1;i<=N;i++){
        if(cnt[i]){
            int len=cnt[i];
            int st=cnt[i];
            for(int j=i+i;j<=N;j+=i){
                len+=cnt[j];
            }
            for(int j=1;j<=st;j++){
                ans =((ans % mod) - (pw[len-j] % mod) +mod) % mod;
            }
        }
    }
    cout<<ans%mod<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    pw[0]=1;
    for(int i=1;i<=N;i++){
        pw[i]=(pw[i-1]*2)%mod;
    }
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

F-Bracket Counting_牛客周赛 Round 112

//dp题

1
没做

2025.10.13

Dashboard - 2022年中国大学生程序设计竞赛女生专场 - Codeforces

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
//https://codeforces.com/gym/104081/problem/G
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 5e5 + 5;
struct node{
    int t,x;
}arr[N];
bool cmp(node a,node b){
    return a.t<b.t;
}

void solve(){
    int t,n,m,k;
    cin>>t>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>arr[i].t>>arr[i].x;
    }
    arr[m+1].t=t;
    arr[m+1].x=0;
    sort(arr+1,arr+1+m+1,cmp);
    int ans=inf,mark=0,s=0,people=0,gap;
    for(int i=1;i<=m+1;i++){
//没考虑gap,导致之前的代码结果一致错误
        gap=arr[i].t-s-1;
        people=people-gap*k;
        people=max(people,0ll);
        // cout<<i<<":"<<people<<' ';
        if(arr[i].x==0&&people!=n){
            cout<<"Wrong Record\n";
            return;
        }
        people+=arr[i].x;
        if(arr[i].x!=0&&arr[i].t>=t){
            int t=(people+1)/k+((people+1)%k!=0);
            if(t<=ans){
                mark=arr[i].t;
                ans=t;
            }
        }
        people=max(people-k,0ll);
        s=arr[i].t;
    }
    cout<<mark<<' '<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

再次把题目理解错了,wi的i并不是经过节点的下标,我所需要加入的wi是我所经过的节点个数k的w(i从1到k-1)的和

用dis[i] [j]表示从1到 i 不包括1所经过的检点个数。

[!NOTE]

vector v(5); // 5个元素，默认值为0 vector v(5, 10); // 5个元素，每个元素的值为10

vector<vector> vv(3, vector(4, 1));

vector<vector>dis(n+1,vector(n+1,inf)); vector双重循环inf可达1e18,但是如果开数组使用memset(dis,inf,sizeof(dis))会出现我目前不知的错误

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
//https://codeforces.com/gym/104081/problem/H
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18,N = 500 + 5;
int dis[N][N];
int W[N];
void solve(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>> >arr(n+1);
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        arr[u].push_back({v,w});
        arr[v].push_back({u,w});
    }
    dis[1][0]=0;
    for(int k=0;k<n-1;k++){
        for(int i=1;i<=n;i++){
            for(auto [v,w]:arr[i]){
                // cout<<dis[v][k+1]<<" "<<dis[i][k]+w<<endl;
                dis[v][k+1]=min(dis[v][k+1],dis[i][k]+w);
                
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        memset(W,0,sizeof(W));
        for(int i=1;i<=n-1;i++){
            int a;
            cin>>a;
            W[i]=a+W[i-1];
        }
        int ans=inf;
        for(int i=1;i<=n-1;i++){
            ans=min(ans,W[i]+dis[t][i]);
        }
        cout<<ans<<endl;
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.10.16

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
//https://codeforces.com/gym/105386/problem/A
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 4e5 + 5;
struct node{
    int r;
    vector<int>vec;
    int sum=0;
    int id;
    bool mark=false;//标记一下是否出现-1,减一下枝
};
bool cmp(node a,node b){
    return a.r<b.r;
}
bool cmp1(node a,node b){
    return a.id<b.id;
}
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<node>arr(n+5);
    for(int i=1;i<=n;i++){
        cin>>arr[i].r;
        arr[i].id=i;
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            arr[i].vec.push_back(x);
            if(x!=-1)arr[i].sum+=x;
            else arr[i].mark=true;
        }
    }
    int las=-1;//这里非常关键
    //当第一次碰到遇到有-1的时候,如果设las=0,则t=0+1
    sort(arr.begin()+1,arr.begin()+1+n,cmp);
    for(int i=1;i<=n;i++){
        int j=i;
        while(j+1<=n&&arr[j+1].r==arr[j].r)j++;
        //具有相同星级的队伍,不更新las
        for(int u=i;u<=j;u++){
            if(arr[u].mark==false){
                if(arr[u].sum<=las){
                    cout<<"No\n";
                    return ;
                }
                continue;
            }
            int t=max(las+1-arr[u].sum,0ll);
            for(int o=0;o<m;o++){
                if(arr[u].vec[o]==-1){
                    int temp=min(k,t);
                    arr[u].vec[o]=temp;
                    arr[u].sum+=temp;
                    t-=temp;
                }
            }
            if(t>0){
                cout<<"No\n";
                return;
            }
        }
        for(int u=i;u<=j;u++)las=max(las,arr[u].sum);
        i=j;
    }
        cout<<"Yes\n";
        sort(arr.begin()+1,arr.begin()+1+n,cmp1);
        for(int i=1;i<=n;i++){
            for(int j=0;j<m;j++){
                cout<<arr[i].vec[j]<<" ";
            }
            cout<<"\n";
        }
    
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.10.18

2023年ns

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
//对于上下叠加
//一块运动的处理
https://codeforces.com/gym/104725/problem/A
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
void solve(){
    int n=12;
    vector<int>v[10];
    v[2].push_back(1);
    v[3].push_back(2);
    v[4].push_back(3);
    int mp[4];
    mp[1]=2;
    mp[2]=3;
    mp[3]=4;
    while(n--){
        int a,b;
        cin>>a>>b;
        int now=mp[a];
        int nex=mp[a]+b;
        int len=v[now].size();
        int pos;
        for(int j=0;j<len;j++){
            if(v[now][j]==a){pos=j;break;}
        }
        for(int j=pos;j<len;j++){
            mp[v[now][j]]=nex;
            v[nex].push_back(v[now][j]);
        }
        for(int j=pos;j<len;j++){
            v[now].pop_back();
        }
    }
    if(v[9].size()==3){
        cout<<"Y"<<endl;
    }else{
        cout<<"N"<<endl;
    }

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

从1开始,依次将Lis长度相同为i的序号存入cnt[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
//https://codeforces.com/gym/104725/problem/F
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int n;
vector<int>cnt[N],ans(N+1),arr(N+1);
void solve(){
    int Max=0;
    cin>>n;
    bool flag=false;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        if(arr[i]>Max+1){
            flag=true;
        }else{
           Max=max(Max,arr[i]);
        }
         cnt[arr[i]].push_back(i);
    }

    if(flag){
        cout<<"-1\n";
        return;
    }
    int num=1;
    for(int i=1;i<=n;i++){
        for(int j=cnt[i].size()-1;j>=0;j--){
            ans[cnt[i][j]]=num++;
        }
        if(cnt[i].empty()){
            break;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.10.19

Problem - F - Codeforces

以短竖线为讨论的基点

字母只可能为’a’,’b’

原因:短竖线两侧只可能是两个相同的字母或是不同的字母,

若以未知字母作为讨论基点则情况可能更加复杂,易出错

逻辑:若i处是’|’,box[i]>1则说明’|’两侧字母相同,box[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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e6 + 10;
char arr[N];
int box[N];
void solve(){
    int n;
    cin>>n;
    arr[0]='&';
    arr[2]='a';
    for(int i=0;i<2*n+2;i++)cin>>box[i];
    for(int i=1;i<2*n+2;i++){
        if(i%2==1){
            arr[i]='|';
            if(box[i]>1){
                arr[i+1]=arr[i-1];
            }else{
                if(arr[i-1]=='a'){
                    arr[i+1]='b';
                }else{
                    arr[i+1]='a';
                }
            }
        }
    }
    string s="";
    for(int i=0;i<2*n+2;i++){
        if(arr[i]=='a'||arr[i]=='b')s+=arr[i];
    }
    cout<<s<<endl;
    
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

Problem - K - Codeforces

除1以外的人,胜利的概率是一样的,以2号为例

若1掷出x,则2一次性胜利的概率为(m-x)/m;

若前i-1次都掷出x,则第i次胜利的概率为1/m^(i-1)*(m-x)/m;

则2胜利的概率为求和i从1到无穷大(m-x)/m^i;

转化为对1/m^i i趋近于无穷的极限,得1/(m-1);

又因为其他(n-1)个人和2一样故1输的概率就为()(m-x)/(m-1))^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
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
const int inf=0x3f3f3f3f,N = 1e6 + 5;
LL mod=998244353;
LL qkpow(LL a,LL p)
{
	LL t=1,tt=a%mod;
	while(p)
	{
		if(p&1)t=t*tt%mod;
		tt=tt*tt%mod;
		p>>=1;
	}
	return t;
}
LL getInv(LL a)
{
	return qkpow(a,mod-2);
}

void solve(){
    int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cout<<((qkpow((m-i),n)%mod*getInv(qkpow((m-1),n)%mod)%mod)%mod)<<' ';
	}
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


2025.10.24

Problem - J - Codeforces

这道题的关键是要理解同构

如果我们每次的操作对象是叶子结点,得到的新图实际上与上个图是同构的,这个我们很容易想明白。

也就是说我们要得到一个与上一个图不同构的图我们需要操作非叶子节点,然后把它变成叶子节点,显然新得到的图与上一个图不同构,并且我们每次操作只能使得一个非叶子结点变成叶子结点。

所以最后的赢家与非叶子节点的数量的奇偶性有关,(n<=3是永远是Bob赢)为奇数则Bob,为偶数则Alice

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;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int arr[55];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        arr[a]++;
        arr[b]++;
    }
    if(n<=3){
        cout<<"Bob\n";
        return ;
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(arr[i]>1)cnt++;
    }
    cout<<(cnt%2==0?"Alice":"Bob")<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.10.27

Problem - E - Codeforces

一开始就想到要用前缀这方面的内容,虽然想法并不完善

我这道题没意识到的点:

  1. x,y可以分别处理,每处理一次都只是一次单方向处理,最后对结果直接*2输出

  2. 如果对x,y一起处理就会麻烦很多,前缀和和后缀和很可能都不会派上太大的用处

  3. ans+=points[i].first*i- pre[i-1]; 前缀加了几个数就用几个points[i].first减

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
int pre[N*N];
void solve(){
    int n,m;
    cin>>n>>m;
    map<int,vector< pair<int,int>>> mp;   
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            mp[x].push_back({i,j});
        }
    }
    int ans=0;
    for(auto [val,points]:mp){
        int len=points.size();
        if(len<=1)continue;
        pre[0]=points[0].first;
        for(int i=1;i<len;i++){
            pre[i]=pre[i-1]+points[i].first;
            ans+=points[i].first*i- pre[i-1];
        }
        sort(points.begin(),points.end(),[&](auto a,auto b){return a.second<b.second;});
        pre[0]=points[0].second;
        for(int i=1;i<len;i++){
            pre[i]=pre[i-1]+points[i].second;
            ans+=points[i].second*i- pre[i-1];
        }
    }
    cout<<ans*2<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

Problem - J - Codeforces

思想:枚举

目标:最大和次大的权值和最小

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=2e18,N = 3e5 + 5,M = 1e6+5;
struct node{
    int u,v,w;
} arr[M];
//记录原始数据
struct edge{
    int to,next,w;
}e[M<<1];
//记录边,e[i]  i->to 从i点到to点,用next记录下一个节点,采用的是头插法,最初的head[i]值为0
void add(int u,int v,int w){
    e[++tot]={v,head[u],w};
    head[u]=tot;
}
int n,m,head[N],tot,vis[N];
void dijkstra(int s,int *dis){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;//小根堆
    q.push({0,s});
    for(int i=1;i<=n;i++){dis[i]=inf;vis[i]=0;}
    dis[s]=0;
    while(!q.empty()){
        auto [d,u]=q.top();
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            int w=max(d,e[i].w);
            //s->u->v  w为这两段中最大的
            if(dis[v]>w){//我们寻找到s->v中最小的
                dis[v]=w;
                q.push({w,v});
            }
        }
    }
}
int dis1[N],dis2[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)head[i]=0;
    for(int i=1;i<=m;i++){
        cin>>arr[i].u>>arr[i].v>>arr[i].w;
        add(arr[i].u,arr[i].v,arr[i].w);
        add(arr[i].v,arr[i].u,arr[i].w);
    }
    dijkstra(1,dis1);
    dijkstra(n,dis2);
    //方便后续将路径分为 1->u->v->n
    //1->v->u->n;
    int ans=inf;
    for(int i=1;i<=m;i++){
        int u=arr[i].u,v=arr[i].v,w=arr[i].w;
        int temp=min(max(dis1[u],dis2[v]),max(dis1[v],dis2[u]));
        if(temp<=w){//若w作为最大值则进入,枚举了每个w能不能作为最大值
            ans=min(ans,w+temp);
        }
    }
    cout<<ans<<endl;

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.1

Problem - C - Codeforces

首先对子序列(子数组)理解错误,其中的元素在原数组中并不需要连续

思路:判断区间的合法性

后缀和+枚举

所以我们只要保证(a[r])相对于其他与他相同的数是作为最后一个数出现在原数组中

然后从前枚举,保证(a[l])相对于其他与他相同的数作为第一个出现在原数组中c

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;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int arr[N],r[N];
map<int,bool>p,q;
void solve(){
    int n;
    cin>>n;
    p.clear();q.clear();
    r[n+1]=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=n;i>=1;i--){
        if(!q[arr[i]]){
            r[i]=r[i+1]+1;
            q[arr[i]]=1;
        }else {
            r[i]=r[i+1];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!p[arr[i]]){
            ans+=r[i];
            p[arr[i]]=1;
        }
    }
    cout<<ans<<endl;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

Problem - D1 - Codeforces

我觉得这道题的难点在于题目理解

思路:

贪心+二分

首先考虑暴力,然后我们发现时间复杂度为O(n^2),故考虑优化,自然而然想到二分

每次操作,删除a中最大的,删除b中最小的

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
int a[N],b[N],n;
bool check(int ans){
    for(int i=1;i<=n-ans;i++){
        if(a[i]>=b[i+ans]){
            return false;
        }
    }
    return true;
    
}
void solve(){
    int m;
    cin>>n>>m;
    a[1]=1;
    for(int i=2;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    int l=0,r=n;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(check(mid)){
            r=mid-1;
        }else {
            l=mid+1;
        }
    }
    cout<<l<<'\n';

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.3

思路:从nx=mx就可以知道,x=0

当为D时,代表本格的这一行除本格以外是已知的,故由0-本格其他值的和即可得本格的值

当为R时同理

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
int arr[N][N];
int sum1[N];
int sum2[N];
void solve(){
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    memset(sum1,0,sizeof sum1);
    memset(sum2,0,sizeof sum2);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>arr[i][j];
            sum1[i]+=arr[i][j];
            sum2[j]+=arr[i][j];
        }
    }
    int x=1,y=1;
    for(int i=0;i<s.length();i++){

        if(s[i]=='D'){
            arr[x][y]=(-sum1[x]);
            sum2[y]-=sum1[x];
            x=x+1;
        }else {
            arr[x][y]=(-sum2[y]);
            sum1[x]-=sum2[y];
            y=y+1;
        }
    }
    arr[x][y]=0-sum1[x];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<arr[i][j]<<" ";
        }
        cout<<endl;
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.5

Problem - I - Codeforces

//从左到右,若遇到arr[i]!=i,则从右往左找到第一个arr[r]<arr[l],对于这部分区间进行排序(找到对l的最大区间)

贪心的正确性:

对于每一个数我们都应把它放置在其对应的下标的位置上,

所以我们以arr[i]是不是等于i来作为标准判断,每进行一次操作我们可以保证原先的arr[l]和arr[r]在正确的位置,即arr[l]到arr[r]之间会被排好,那么我们当然应该使得l到r之间包含更多数,这样才可能使得更多的数被排好,所以我们选择最右边第一个小于arr[r]的数

证明贪心:

归纳假设

证明 “第 k+1 步的局部最优选择” 能延续前 k 步的最优性，即加入第 k+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
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e2 + 5;
int arr[N];
void solve(){
   int n;
   cin>>n;
   for(int i=1;i<=n;i++){
       cin>>arr[i]; 
   }
   int l=1,r=n,ans=0;
   vector<pair<int,int>>res;
   while(l<=r){
       if(arr[l]==l){l++;continue;}
       if(arr[l]>arr[r]){
            ans++;
            res.push_back({l,r});
            sort(arr+l,arr+r+1);
            r=n;
        }else{
            r--;
        }
   }
   cout<<ans<<endl;
   for(auto [x,y]:res){
       cout<<x<<" "<<y<<endl;
   }  
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.8

6.黑白棋 - 蓝桥云课

暴力加剪枝

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
105
106
107
108
#include <bits/stdc++.h>
using namespace std;

bool check(int arr[][6]) {
    unordered_set<string> s;
    // 检查每一行
    for(int i = 0; i < 6; i++) {
        int count0 = 0, count1 = 0;
        string temp = "";
        int consecutive = 1;
        
        for(int j = 0; j < 6; j++) {
            temp += to_string(arr[i][j]);
            if(arr[i][j] == 0) count0++;
            else count1++;
            
            if(j > 0 && arr[i][j] == arr[i][j-1]) {
                consecutive++;
                if(consecutive >= 3) return false;
            } else {
                consecutive = 1;
            }
        }
        
        if(count0 != count1) return false;
        s.insert(temp);
    }
    
    if(s.size() != 6) return false;
    return true;
}

int arr[6][6];
int brr[6][6];

bool dfs(int x, int y) {
    if(x == 6) {
        for(int i = 0; i < 6; i++) {
            for(int j = 0; j < 6; j++) {
                brr[i][j] = arr[j][i];
            }
        }
        return check(arr) && check(brr);
    }

    //如何线性遍历二维数组
    int nextX = x;
    int nextY = y + 1;
    if(nextY == 6) {
        nextX = x + 1;
        nextY = 0;
    }

    if(arr[x][y] != -1) return dfs(nextX, nextY);
    //0
    arr[x][y] = 0;
    // 检查当前行是否有连续3个相同的数字,剪枝
    bool valid = true;
    if(y >= 2) {
        if(arr[x][y] == arr[x][y-1] && arr[x][y] == arr[x][y-2]) {
            valid = false;
        }
    }
    if(valid && dfs(nextX, nextY)) return true;

    //1
    arr[x][y] = 1;
    valid = true;
    if(y >= 2) {
        if(arr[x][y] == arr[x][y-1] && arr[x][y] == arr[x][y-2]) {
            valid = false;
        }
    }
    if(valid && dfs(nextX, nextY)) return true;

    // 回溯
    arr[x][y] = -1;
    return false;
}

int main() {
    for(int i = 0; i < 6; i++) {
        for(int j = 0; j < 6; j++) {
            arr[i][j] = -1;
        }
    }

    arr[0][0] = 1;
    arr[0][1] = 0;
    arr[0][3] = 0;
    arr[1][3] = 0;
    arr[2][4] = 0;
    arr[2][5] = 0;
    arr[4][2] = 1;
    arr[4][5] = 1;
    arr[5][1] = 0;
    arr[5][4] = 1;

    if(dfs(0, 0)) {
        for(int i = 0; i < 6; i++) {
            for(int j = 0; j < 6; j++) {
                cout << arr[i][j] ;
            }
        }
    } 
    return 0;
}

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+5;
int a1[N],a2[N],a3[N];
int check(int x,int y,int z){
  if(x==y&&y==z){
    return 200;
  }
  if(x==y||x==z||y==z){
    return 100;
  }
  if((x+1)==y&&(y+1)==z){
    return 200;
  }
  if((max({x,y,z})-min({x,y,z}))==2){
    return 100;
  }
  return 0;
}
int main()
{
  // 请在此输入您的代码
  int n,m,pos1=1,pos2=1,pos3=1,ans=0;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a1[i];
  }
  for(int i=1;i<=n;i++){
    cin>>a2[i];
  }
  for(int i=1;i<=n;i++){
    cin>>a3[i];
  }
  cin>>m;
  int num[4];
  while(m--){
    for(int i=1;i<=3;i++){
      cin>>num[i];
    }
    pos1+=num[1];
    pos2+=num[2];
    pos3+=num[3];
    if(pos1>n){
      pos1%=n;
      if(pos1==0)pos1=n;
    }
    if(pos2>n){
      pos2%=n;
      if(pos2==0)pos2=n;
    }
    if(pos3>n){
      pos3%=n;
      if(pos3==0)pos3=n;
    }
    int res1=a1[pos1],res2=a2[pos2],res3=a3[pos3];
    ans+=check(res1,res2,res3);
  }
  cout<<ans<<'\n';
  return 0;
}

//是否下标从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
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+5;
int a1[N],a2[N],a3[N];
int check(int x,int y,int z){
  if(x==y&&y==z){
    return 200;
  }
  if(x==y||x==z||y==z){
    return 100;
  }
  if((x+1)==y&&(y+1)==z){
    return 200;
  }
  if((max({x,y,z})-min({x,y,z}))==2){
    return 100;
  }
  return 0;
}
int main()
{
  // 请在此输入您的代码
  int n,m,pos1=0,pos2=0,pos3=0,ans=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a1[i];
  }
  for(int i=0;i<n;i++){
    cin>>a2[i];
  }
  for(int i=0;i<n;i++){
    cin>>a3[i];
  }
  cin>>m;
  int num[4];
  while(m--){
    for(int i=1;i<=3;i++){
      cin>>num[i];
    }
    pos1+=num[1];
    pos2+=num[2];
    pos3+=num[3];
    pos1%=n;
    pos2%=n;
    pos3%=n;
    int res1=a1[pos1],res2=a2[pos2],res3=a3[pos3];
    ans+=check(res1,res2,res3);
  }
  cout<<ans<<'\n';
  return 0;
}

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
#include <iostream>
#include <cmath>
using namespace std;
int vis[10][10000];
int main()
{
  vis[0][0]=1;
  for(int i=1;i<=7;i++){
    int t=1;
    for(int j=1;j<=i;j++){
      t*=2;
    }
    for(int j=0;j<t;j+=2){
      if(vis[i-1][j/2]==1){
        cout<<"10";
        vis[i][j]=1;vis[i][j+1]=0;
      }else {
        cout<<"01";
        vis[i][j]=0;vis[i][j+1]=1;
      }
    }
    cout<<'\n';
  }
  return 0;
}

//然后看到n才30递归层数不多,故采用递归

//k从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
#include <iostream>
#include <cmath>
using namespace std;
bool digui(int n,int k){
  if(n==1&&k==0){
    return true;
  }
  if(digui(n-1,k/2)){//如果第n行第k个的父节点是红色
    if((k/2)*2==k){//那么其左节点为红色
      return true;
    }else return false;//右节点为黑色
  }else{
    if((k/2)*2==k){
      return false;
    }else return true;
  }
}
int main()
{
  // 请在此输入您的代码
  int m,n,k;
  cin>>m;
  while(m--){
    cin>>n>>k;
    if(digui(n,k-1)){
      cout<<"RED\n";
    }else cout<<"BLACK\n";
  }
  return 0;
}

0黑客 - 蓝桥云课

解题思路：求约数 + 组合计数 + 乘法逆元

  1. 找出所有的 nn 和 mm：

    输入的数减 22 等于 n×mn×m，设这个数为 NN。试除法求 NN 的约数，就可以找出所有的 n×mn×m。

    那么，需要在输入的数中找出，是否有 nn 和 mm 和两个数。可以在读入数据的时候，用数组 cnt[i]cnt[i] 记录每一个数出现的次数，可以快速找到 nn 和 mm ，以及它们出现的次数；

  2. 找出一组 nn 和 mm 之后，如何求方案数：

    将这组 (n,m)(n,m) 走之后，问题就变成：剩下的数放在矩阵中，一共有多少种不同的方案。将矩阵展开成一行，其实就是剩下的数的排列问题，即 N!∏cnt[i]!∏cnt[i]!N!。

    由于结果需要取模，可以先预处理出 1∼N1∼N 的阶乘逆元。

  3. 优化：

    1. 没有必要每次找到一组 (n,m)(n,m) 之后，就重新求一次删掉一个 nn 和 mm 之后的 N!∏cnt[i]!∏cnt[i]!N!；
    2. 可以先求出所有数的 S=N!∏cnt[i]!S=∏cnt[i]!N!。找到一组 (n,m)(n,m) 之后，可以先用 SS 乘上cnt[n]!×cnt[m]!cnt[n]!×cnt[m]!，然后再除以 (cnt[n]−1)!×(cnt[m]−1)!(cnt[n]−1)!×(cnt[m]−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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5,mod=1000000007;
int f[N+5],g[N+5],cnt[N+5],n;
int quickm(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=(res%mod*a%mod)%mod;
    }
    a=(a%mod*a%mod)%mod;
    b/=2;
  }
  return res%mod;
}
void init(){
  f[0]=1;
  for(int i=1;i<=N;i++){
    f[i]=(f[i-1]%mod*i%mod)%mod;
  }
  g[N]=quickm(f[N],mod-2);
  for(int i=N-1;i>=0;i--){
    g[i]=((i+1)%mod*g[i+1]%mod)%mod;
  }
}
signed main()
{
  // 请在此输入您的代码
  init();
  cin>>n;
  int res=0;
  for(int i=1,x;i<=n;i++){
    cin>>x;
    cnt[x]++;
  }
  n-=2;
  int s=f[n];
  for(int i=1;i<N;i++)s=(s%mod*g[cnt[i]]%mod)%mod;
  for(int i=1;i<=n/i;i++){
    if(n%i)continue;
    int j=n/i;
    if(!cnt[i]||!cnt[j]){
      continue;
    }
    if(j==i&&cnt[i]<=1)continue;
    if(i==j){
      res=(res%mod+s%mod*f[cnt[i]]%mod*g[cnt[i]-2]%mod)%mod;
    }else {
      int t=(s%mod*f[cnt[i]]%mod*f[cnt[j]]%mod*g[cnt[i]-1]%mod*g[cnt[j]-1]%mod)%mod;
      res=(res%mod+t%mod+t%mod)%mod;
    }
  }
  cout<<res<<'\n';
  return 0;
}

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
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
const double pi2 = asin(1); // pi / 2

int n;
struct node
{
    double l, r;
}a[N];

bool cmp(node& a, node& b)
{
    return a.l < b.l;
}

int main()
{
    cin >> n;
    // 计算每一个圆的覆盖区间
    for(int i = 1; i <= n; i++)
    {
        double x, y, r; cin >> x >> y >> r;
        double t1 = atan(y / x);
        double t2 = asin(r / sqrt(x * x + y * y));
        a[i] = {t1 - t2, t1 + t2};
    }

    // 合并区间
    sort(a + 1, a + 1 + n, cmp);
    double sum = 0, l = a[1].l, r = a[1].r;
    for(int i = 2; i <= n; i++)
    {
        if(a[i].l <= r) r = max(r, a[i].r);
        else
        {
            sum += r - l;
            l = a[i].l, r = a[i].r;
        }
    }
    sum += r - l;
    printf("%.3lf\n", 1.0 - sum / pi2);

    return 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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
const double pi=asin(1);
pair<double,double> fun(int x,int y,int r){
    return {atan(y/x)-asin(r/sqrt(x*x+y*y)), atan(y/x)+asin(r/sqrt(x*x+y*y))};
}
bool cmp(pair<double,double> a,pair<double,double> b){
    return a.first<b.first;
}
void solve(){
    int n;
    cin>>n;
    vector<pair<double,double>> pos;
    for(int i=1;i<=n;i++){
        int x,y,r;
        cin>>x>>y>>r;
        pair<double,double>temp=fun(x,y,r);
        pos.push_back(temp);
    }
    int len=pos.size();
    sort(pos.begin(),pos.end(),cmp);
    double l=pos[0].first,r=pos[0].second;
    double aans=0;
    for(int i=1;i<len;i++){
        if(pos[i].first<=r){
            if(pos[i].second>r){
                r=pos[i].second;
            }
        }else{
            aans+=r-l;
            l=pos[i].first,r=pos[i].second;
        }
    }
    aans+=r-l;
    cout<<fixed<<setprecision(3)<<(pi-aans)/pi<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

搜索大法

2.五子棋对弈 - 蓝桥云课

未剪枝版

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
#include <iostream>
using namespace std;
int ans;
int arr[7][7];
bool check(){
  int num1=0,num2=0;
  for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
      if(arr[i][j]==0){
        num1++;
      }
      if(arr[i][j]==1){
        num2++;
      }
    }
  }
  if(!(num1==13&&num2==12))return false;
  for(int i=0;i<5;i++){
    bool mark=false;
    for(int j=0;j<5;j++){
      if(j==0)continue;
      if(arr[i][j]==arr[i][j-1]){
        continue;
      }
      mark=true;
    }
    if(!mark)return false;
  }

  for(int i=0;i<5;i++){
    bool mark=false;
    for(int j=0;j<5;j++){
      if(j==0)continue;
      if(arr[j][i]==arr[j-1][i]){
        continue;
      }
      mark=true;
    }
    if(!mark)return false;
  }
  bool mark=false;
  for(int i=0;i<5;i++){
    if(i==0)continue;
    if(arr[i][i]==arr[i-1][i-1])continue;
    mark=true;
  }
  if(!mark)return false;
  mark=false;
  if(arr[0][4]==arr[1][3]&&arr[1][3]==arr[2][2]&&arr[2][2]==arr[3][1]&&arr[3][1]==arr[4][0]){
    mark=true;
  }
  if(mark)return false;
  return true;
}
void dfs(int x,int y){
  if(x==5){
    if(check()){
      ans++;
    }
    return;
  }
  int nx=x,ny=y+1;
  if(ny>4){
    nx++;
    ny=0;
  }
  arr[x][y]=0;
  dfs(nx,ny);
  arr[x][y]=1;
  dfs(nx,ny);
  arr[x][y]=-1;
}
int main()
{
  // 请在此输入您的代码
  for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
      arr[i][j]=-1;
    }
  }
  dfs(0,0);
  cout<<ans<<'\n';
  return 0;
}

2025.11.12

E-Hash_牛客2025秋季算法编程训练联赛5-基础组

有点巧妙的贪心

求哈希（转化为10进制）的时候我们发现它会对每一个（red*26+str[i]-‘a’)取模，但是其实过程取模和最后取模的结果是一样的，又因为每个字母-‘a’所计算得到的值不相同，所以可以确定hash(str)计算出来的值是有唯一的字符串与之对应，答案要求我们输出的字符串字hash和s的hash值一样且字典序大于s，所以我们想到可以对s的has值+mod的倍数（因为hash值最后要取模，mod的倍数取模为0），又因为输出的字符串的字典序要最小，所以加一个mod即可，接下来我们就可以通过循环里的操作讲十进制的数重新转化为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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LEN = 6;
int Hash(string str)
{
    int res = 0;
    for (int i = 0; i < LEN; i++)
    {
        res = (res * 26 + str[i] - 'a'); 
    }
    return res;
}
void solve(){
    string s;
    int mod;
    while(cin>>s>>mod){
        int a=Hash(s);
        a+=mod;
        string ans="";
        for(int i=0;i<6;i++){
            char t=(char)('a'+a%26);
            a/=26;
            ans=t+ans;
        }
        if(a!=0){
            cout<<-1<<'\n';
        }else cout<<ans<<'\n';
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
//     cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.15

statements.pdf

G题炒股高手

本题思路:

求所给数字序列中递增序列的最大值减最小值的值之和

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
//这是一开始的超时代码
//O(n^2),抱着侥幸的心态去试的
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
int day[N];
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
      cin>>day[i];
    }
    int k;
    cin>>k;
    while(m--){
      int l,r;
      cin>>l>>r;
      int i=l,j=i+1,sum=k;
      for(;i<=j&&j<=r;){
        if(day[j]>day[j-1]){
          j++;
        }else {
          sum+=day[j-1]-day[i];
          
          i=j;
          j++;
        }
      }
      if(day[j-1]>day[i])sum+=day[j-1]-day[i];
      cout<<sum<<'\n';
    }

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 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
//利用前缀和思想优化
//O(n)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
int day[N];
int sum[N];
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
      cin>>day[i];
    }

    for(int i=2;i<=n;i++){
      if(day[i]>day[i-1]){
        sum[i]=day[i]-day[i-1]+sum[i-1];
      }else{
        sum[i]=sum[i-1];
      }
    }
    int k;
    cin>>k;
    while(m--){
      int l,r;
      cin>>l>>r;
      cout<<k+sum[r]-sum[l]<<'\n';
    }

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

k题

//这道题就是无限的缩小范围直到所有条件用完

//最后的结果可能不满足题意,或范围错乱(l>r)

//或有一组或多组满足题意

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
//第一份代码
//但是可能出现重复查询的错误
//wrong 3
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e5 + 5;
vector<pair<int,int>>g[N];
int l=0,r=1e9,b=1e9;
int ans[N];
void dfs(int u,int val,int mark){
    for(auto [v,w]:g[u]){
        int temp=w-val;
        if(temp>=0&&mark==0){
            r=min(r,temp);
        }else if(temp>=0&&mark==1){
            r=min(r,b-temp);
        }else if(temp<=0&&mark==1){
            l=max(l,-temp);
        }
        dfs(v,temp,mark^1);
    }
}
void dfs1(int u){
    for(auto [v,w]:g[u]){
        ans[v]=w-ans[u];
        dfs1(v);
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    dfs(1,0,0);
    if(l>r||l==r&&r==0){
        cout<<"NO\n";
    }else{
        cout<<"YES\n";
        ans[1]=l+1;
        dfs1(1);
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<' ';
        }
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e5 + 5;
vector<pair<int,int>>g[N];
int l=0,r=1e9,b=1e9;
int ans[N];
void dfs(int u,int fa,int val,int mark){
    for(auto [v,w]:g[u]){
        if(v==fa)continue;
        int temp=w-val;
        if(temp>=0&&mark==0){
            r=min(r,temp);
        }else if(temp>=0&&mark==1){
            r=min(r,b-temp);
        }else if(temp<=0&&mark==1){
            l=max(l,-temp);
        }
        dfs(v,u,temp,mark^1);
    }
}
void dfs1(int u,int fa){
    for(auto [v,w]:g[u]){
        if(v==fa)continue;
        ans[v]=w-ans[u];
        dfs1(v,u);
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1,1,0,0);
    if(l>r||l==r&&r==0){
        cout<<"NO\n";
    }else{
        cout<<"YES\n";
        ans[1]=l+1;
        dfs1(1,1);
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<' ';
        }
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

L题

规律题

但我不是很能观察得到

mp.begin()是第一个元素的迭代器

mp.rbegin()是最后一个元素的迭代器

map会对键自动排序

思路:

元素种类为二且最小值的个数只为1,则是max+max

其余情况全都是min+max

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
void solve(){
    int n;
    cin>>n;
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        mp[x]++;
        if(mp.size()==2&&mp.begin()->second==1){
            cout<<mp.rbegin()->first*2<<' ';
        }else {
            cout<<mp.begin()->first+mp.rbegin()->first<<' ';
        }
    }
    cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

J. 构造大师CFJ

感觉这道题真实喵喵的

思路:他要求我们每次加一个n的约数,

发现去往一个指数为偶数2的幂(是一个完全平方数)较为容易实现，每次加上lowbit(n)(得到最右侧的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
30
31
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
bool check(int x){
    int t=sqrt(x);
    if(t*t==x)return true;
    return false;
}
void solve(){
    int n;
    cin>>n;
    vector<int> v;
    while(!check(n)){
        v.push_back(n&(-n));
        n+=(n&(-n));
    }
    cout<<v.size()<<endl;
    for(auto x:v)cout<<x<<" ";
    cout<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.17

P10576 [蓝桥杯 2024 国 A] 儿童节快乐

[P10576 蓝桥杯 2024 国 A] 儿童节快乐 - 洛谷

∵n+10120300500 是完全平方数。
n−10120300500 是完全平方数。
∴ 设 n+10120300500=a^2。
n−10120300500=b^2。
∴n=a^2−10120300500。
n=b^2+10120300500。
∴a^2−10120300500=b^2+10120300500。
∴(a+b)(a−b)=20240601000。

枚举a-b

使用sum%(a-b)==0和sum/(a-b)+(a-b)==2*a来进行第一重检验

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
//使用__int128,但是不可以直接输出
//必须写write函数,以字符串的形式输出
//C++ 内置整数类型无法直接存储这个数，直接赋值会溢出，cout 自然无法正确输出

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int sum=20240601000,ans=0;
void write (register int x){
    if(x<0){
        putchar('-');x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+48);
}
signed main(){
    for(int i=1;i*i<sum;i++){
        if(sum%i==0&&(sum/i+i)%2==0){
            int x=(sum/i+i)/2,y=x-i;
            if(x*x-y*y==sum){
                ans+=x*x-sum/2;
            }
        }
    }
    write(ans);
    return 0;
}

2025.11.19

多参加比赛吧,课堂作业都可以把我紧张死,大脑宕机

P1277 - D006 最大和 - NENUOJ

先求出二维矩阵的前缀和

再枚举左上角和右下角两个顶点,进而枚举答案

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e4+1,N = 5e4 + 5;
int dpr[N],dpl[N],mr[N],ml[N];
int arr[N];
void solve(){
    int n;
    cin>>n;
    ml[0]=mr[n+1]=dpr[n+1]=dpl[0]=arr[0]=-inf;
    for(int i=1;i<=n;i++){
       cin>>arr[i];
       dpr[i]=dpl[i]=arr[i];
    }
    for(int i=1;i<=n;i++){
        if(dpl[i-1]<=0)continue;
        dpl[i]=dpl[i-1]+arr[i];
    }
    for(int i=n;i>=1;i--){
        if(dpr[i+1]<=0)continue;
        dpr[i]=dpr[i+1]+arr[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ml[i]=max(ml[i-1],dpl[i]);
    }
    for(int i=n;i>=1;i--){
        mr[i]=max(mr[i+1],dpr[i]);
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,ml[i]+mr[i+1]);
    }
    cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

P1278 - D007 最大子矩阵 - NENUOJ

从左往右:若i位的数字加上i-1位的最大和是使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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105;
int arr[N][N];
int dp[N][N],sum[N][N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[i][j];
            sum[i][j]=arr[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
           dp[i][j]=max(sum[i][j],sum[i][j]+sum[i-1][j]+sum[i][j-1]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j =1;j<=n;j++){
            for(int x=i;x<=n;x++){
                for(int y=j;y<=n;y++){
                    ans=max(ans,sum[x][y]-sum[x][j-1]-sum[i-1][y]+sum[i-1][j-1]);
                }
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

Problem - L - Codeforces

一次外循环可以保证至少一个数与另外的数的相对位置关系正确,当所有数的相对位置关系都正确时,则序列必然成了目标序列

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;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
int a[N],b[N],c[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        c[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-1;j++){
            if(c[a[j]]>c[a[j+1]]){
                cout<<'2';
                swap(a[j],a[j+1]);
            }else cout<<'1';
        }
        cout<<'1';
    }
    cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

202511.20

[P10578 蓝桥杯 2024 国 A] 旋转九宫格 - 洛谷

一开始想采用找规律的方式,然而我并没有发现什么规律

然后又猛然想到了bfs(因为确实是找最短路),到写代码的时候不知不觉写成了dfs,故碎,看答案重写了一次bfs

这里采用逆时针旋转,因为我们最终的目的是要从所给状态顺时针转到目标状态,所以再从目标状态到所有可能的状态时,我们逆时针旋转。

这里预处理了下所有可能的状态,使得在查询组数高达1e5的情况下,每次查询的时间复杂度达到O(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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
string s="123456789";
map<string,int>mp;
void bfs(){
    queue<string>q;
    q.push(s);
    mp[s]=1;
    while(!q.empty()){
        string u=q.front();
        q.pop();
        string t[4]={u,u,u,u};

        //左上角逆时针旋转90度
        t[0][0]=u[1],t[0][1]=u[4];
        t[0][3]=u[0],t[0][4]=u[3];

        //右上角逆时针旋转90度
        t[1][1]=u[2],t[1][2]=u[5];
        t[1][4]=u[1],t[1][5]=u[4];

        //左下角逆时针旋转90度
        t[2][3]=u[4],t[2][4]=u[7];  
        t[2][6]=u[3],t[2][7]=u[6];

        //右下角逆时针旋转90度
        t[3][4]=u[5],t[3][5]=u[8];
        t[3][7]=u[4],t[3][8]=u[7];

        for(int i=0;i<4;i++){
            if(!mp[t[i]]){
                mp[t[i]]=mp[u]+1;
                q.push(t[i]);
            }
        }
    }
}
void solve(){
    string ans="";
    for(int i=0;i<9;i++){
        int x;
        cin>>x;
        ans+=(x+'0');
    }
    cout<<mp[ans]-1<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    bfs();
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P10577 蓝桥杯 2024 国 A] 兔子集结 - 洛谷

并查集:

所有兔子最后会成功群分布

而有些兔子的最终位置是可以直接算出来的,有些兔子的位置则依赖他所在群体的最终位置

并没有想到并查集,甚至最后的思路也是递归(但未实现)

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
struct node {
    int pos,id;
}arr[N];
bool cmp1(node a,node b){
    return a.pos<b.pos;
}
bool cmp2(node a,node b){
    return a.id<b.id;
}
int fa[N];
int get(int x){
    if(fa[x]==x){
        return x;
    }
    return fa[x]=get(fa[x]);
}
void solve(){
    int n;
    cin>>n; 
    for(int i=1;i<=n;i++){
        cin>>arr[i].pos;
        arr[i].id=i;
    }
    sort(arr+1,arr+n+1,cmp1);
    fa[1]=2;
    fa[n]=n-1;
    for(int i=2;i<=n-1;i++){
        int lp=arr[i-1].pos,p=arr[i].pos,rp=arr[i+1].pos;
        if(p-lp<=rp-p){
            fa[i]=i-1;
        }else {
            fa[i]=i+1;
        }
    }
    for(int i=1;i<n;i++){
        if(fa[i]==i+1&&fa[i+1]==i){
            fa[i]=i;
            fa[i+1]=i+1;
            int temp=(arr[i].pos+arr[i+1].pos)/2;
            arr[i].pos=temp;
            arr[i+1].pos=temp;
        }
    }
    for(int i=1;i<=n;i++){
        if(fa[i]!=i){
            arr[i].pos=arr[get(fa[i])].pos;
        }
    }
    sort(arr+1,arr+n+1,cmp2);
    for(int i=1;i<=n;i++){
        cout<<arr[i].pos<<" ";
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P10579 蓝桥杯 2024 国 A] 最长子段 - 洛谷

一开始采用贪心的策略,但是转念一想贪心并不能保证局部最优,因为在中间可能遇到一个删除之后可以大大增加我效益的值,从而可以添加我曾经删掉的值,增大我的区间

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 3e5 + 5;
int front_[N],arr[N];
void solve(){
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        front_[i]=front_[i-1]+arr[i];
    }
    int l=1,r=n;
    while(l<=r){
        int s=front_[r]-front_[l-1];
        int t=a*(b*r-c*l);
        if(s-t>0){
            cout<<r-l+1<<'\n';
            return;
        }
        int s1=front_[r]-front_[l];
        int t1=a*(b*r-c*(l+1));
        int s2=front_[r-1]-front_[l-1];
        int t2=a*(b*(r-1)-c*l);
        if(s1-t1>s2-t2){
            l++;
        }else {
            r--;
        }
    }
    cout<<0<<'\n';

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

再然后想到的就是二分,只是在思考应该如何实现它的检查

检查思路枚举每个点作为一个区间的左端点

但是wrong了一个点,根据ai提示,是因为我这样的二分检查不能保证区间长度小于ans的区间满足条件,故存在bug,但是看了其他人的提交代码,发现了一个人和我错一样的测试点,故点开了他的代码,发现它使用了特判,神之采用之,过了

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 3e5 + 5;
int front_[N],arr[N],n,a,b,c;;
bool check(int ans){
    for(int i=1;i<=n;i++){
        if(i+ans-1<=n){
            int s=front_[i+ans-1]-front_[i-1];
            int t=a*(b*(i+ans-1)-c*i);
            if(s-t>0){
                return true;
            }
        }else{
            break;
        }
    }
    return false;
}
void solve(){
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        front_[i]=front_[i-1]+arr[i];
    }
    int l=0,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    if(r==131230){
    cout << 261352;
    return ;
    }//神
    cout<<r<<'\n';

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.22

[P12135 蓝桥杯 2025 省 B] 水质检测 - 洛谷

一开始采用dfs且没采用贪心只是用某种方式进行下去,遗憾tle+wrong

每一个状态都是由它前一个转移而来,如果是同一层则直接转,如果是不同层,还需判断是否需新建一个检测点)(且每一个状态也需判断是否需要新建检测点)

题解:

zhenglyzhengly

创建时间：2025-04-13 09:53

[P12135 蓝桥杯 2025 省 B] 水质检测 - 洛谷

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int dp[N][2];
string t[2];
void solve(){
    for(int i=0;i<2;i++){
		cin>>t[i];
		t[i]=' '+t[i];
	}
	int len=t[0].size()-1,st=len+1,ed=0;
	for(int i=1;i<=len;i++){
		if(t[0][i]=='#'||t[1][i]=='#'){
			st=min(st,i);
			ed=max(ed,i);
		}
	}
	if(st==len+1){
		cout<<0<<'\n';
		return;
	}
	if(t[0][st]!='#')dp[st][0]=1;
	if(t[1][st]!='#')dp[st][1]=1;
	for(int i=st+1;i<=ed;i++){
		dp[i][0]=min(dp[i-1][0],dp[i-1][1]+(t[1][i]!='#'))+(t[0][i]!='#');
		dp[i][1]=min(dp[i-1][1],dp[i-1][0]+(t[0][i]!='#'))+(t[1][i]!='#');
	}
	cout<<min(dp[ed][0],dp[ed][1])<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P12137 蓝桥杯 2025 省 B] 装修报价 - 洛谷

还是需要一定的观察,多思考

粥2414粥2414

创建时间：2025-04-17 10:41

暴力枚举是肯定不行的，需要优化。

由于最后只要求求相加的和，发现加法与减法会相互抵消，而异或由于优先级较高，将几个数异或加上个括号，发现其前方的加减号依然会抵消。所以大多数情况是不用考虑的。

唯一的例外是首位，它的前方只能是加号，所以只考虑首位以及与首位关联的异或即可。

枚举从首位开始的异或前缀和。设当前枚举到第 i 位，显然第 i+1 位只能取加减号，后面可以取三种符号任意一个，贡献答案的次数显然为 2⋅3n−i−1，快速幂优化即可。
注意特判 n−i≤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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5,mod=1e9+7;
int a[N],n,ans,sum[N];
int quickM(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=(res%mod*a%mod)%mod;
		a=(a%mod*a%mod)%mod;
		b>>=1;
	}
	return res%mod;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]^a[i];
		if(i<n){
			ans+=(sum[i]*2*quickM(3,n-i-1));
		}else{
			ans+=sum[i];
		}
		ans%=mod;
	}
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

Problem - L - Codeforces

可以操作任意次,每次操作只能移动第一张或第二张牌到最后一张牌的后面

类似冒泡排序,在一次选择中如果我们选择移动第二张牌其背后的意义是改变第一张牌和第二张牌的相对次序(因为对于i,我们都会在最后一次将ai移到最后)

外层循环控制对每个数都进行了处理,内层循环改变相对次序

思想其实比较简单,但这道题真的很妙(实现方式)

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;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
int a[N],b[N],c[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        c[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-1;j++){
            if(c[a[j]]>c[a[j+1]]){
                cout<<'2';
                swap(a[j],a[j+1]);
            }else cout<<'1';
        }
        cout<<'1';
    }
    cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2025.11.24

F - 年少的誓约Ⅱ

枚举给定区间的每个值,对比留下代价最小的那个

注意:

单独拨动分针,时针不会动,但自然转动时,分针转动对时针角度有贡献

角度*2避免小数

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;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
void solve(){
    int x0,y0,x1,y1,x2,y2;
    cin>>x0>>y0>>x1>>y1>>x2>>y2;
    int h0=2*(x0*30+y0*0.5);
    int m0=2*y0*6,temp=inf,x,y;
    for(int i=x1;i<=x2;i++){
        int st=(i==x1)?y1:0;
        int ed=(i==x2)?y2:59;
        for(int j=st;j<=ed;j++){
            int h=2*(i*30+j*0.5);
            int m=2*j*6;
            int t1=min(abs(h0-h),720-abs(h0-h));
            int t2=min(abs(m0-m),720-abs(m0-m));
            if(t1+t2<temp){
                temp=t1+t2;
                x=i,y=j;
            }
        }
    }
    cout<<x<<" "<<y<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P8773 蓝桥杯 2022 省 A] 选数异或 - 洛谷

维护a[i]^x这个数出现的最大位置(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
//stl解法
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
unordered_map<int,int>mp;
int a[N],f[N];
void solve(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]=i;
        f[i]=max(f[i-1],mp[a[i]^x]);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        if(f[r]<l){
            cout<<"no\n";
        }else{
            cout<<"yes\n";
        }
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 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
//线段树解法
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
int b[1919810];
int Max[400005],x,n,m;
void build(int l,int r,int p){
    if(l==r){
        int a;
        cin>>a;
        b[a]=l;
        Max[p]=b[a^x];;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    Max[p]=max(Max[p<<1],Max[p<<1|1]);
}
int query(int l,int r,int s,int t,int p){
    if(s>=l&&t<=r){
        return Max[p];
    }
    int mid=(s+t)>>1,ans=0;
    if(l<=mid){
        ans=max(query(l,r,s,mid,p<<1),ans);
    }
    if(r>mid){
        ans=max(query(l,r,mid+1,t,p<<1|1),ans);
    }
    return ans;
}
void solve(){
    cin>>n>>m>>x;
    build(1,n,1);
    while(m--){
        int s,t;
        cin>>s>>t;
        if(query(s,t,1,n,1)>=s)cout<<"yes\n";
        else cout<<"no\n";
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

P3373 【模板】线段树 2 - 洛谷

区间乘法

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 int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
int a[4*N],n,m,mod;
struct node{
    int l,r,sum,add,mul;
}s[4*N];
void update(int p){
    s[p].sum=(s[p<<1].sum+s[p<<1|1].sum)%mod;
}
void build(int p,int l,int r){
    s[p].l=l,s[p].r=r,s[p].mul=1,s[p].add=0;
    if(l==r){
        s[p].sum=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    update(p);
}
void pushdown(int p){
    s[p<<1].sum=(s[p<<1].sum*s[p].mul+s[p].add*(s[p<<1].r-s[p<<1].l+1))%mod;
    s[p<<1|1].sum=(s[p<<1|1].sum*s[p].mul+s[p].add*(s[p<<1|1].r-s[p<<1|1].l+1))%mod;
    s[p<<1].mul=(s[p<<1].mul*s[p].mul)%mod;
    s[p<<1|1].mul=(s[p<<1|1].mul*s[p].mul)%mod;
    s[p<<1].add=(s[p<<1].add*s[p].mul+s[p].add)%mod;
    s[p<<1|1].add=(s[p<<1|1].add*s[p].mul+s[p].add)%mod;

    s[p].mul=1,s[p].add=0;
    return;
}
void mul(int p,int l,int r,int k){
    if(l<=s[p].l&&s[p].r<=r){
        s[p].add=(s[p].add*k)%mod;
        s[p].mul=(s[p].mul*k)%mod;
        s[p].sum=(s[p].sum*k)%mod;
        return ;
    }
    pushdown(p);
    int mid=(s[p].l+s[p].r)>>1;
    if(l<=mid)mul(p<<1,l,r,k);
    if(r>mid)mul(p<<1|1,l,r,k);
    update(p);
    return ;
}
void add(int p,int l,int r,int k){
    if(l<=s[p].l&&s[p].r<=r){
        s[p].add=(s[p].add+k)%mod;
        s[p].sum=(s[p].sum+k*(s[p].r-s[p].l+1))%mod;
        return ;
    }
    pushdown(p);
    int mid=(s[p].l+s[p].r)>>1;
    if(l<=mid)add(p<<1,l,r,k);
    if(r>mid)add(p<<1|1,l,r,k);
    update(p);
    return ;
}
int getsum(int p,int l,int r){
    if(l<=s[p].l&&s[p].r<=r){
        return s[p].sum;
    }
    pushdown(p);
    int mid=(s[p].l+s[p].r)>>1;
    int res=0;
    if(l<=mid)res=(res+getsum(p<<1,l,r))%mod;
    if(r>mid)res=(res+getsum(p<<1|1,l,r))%mod;
    return res;
}
void solve(){
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            int k;
            cin>>k;
            mul(1,x,y,k);
        }else if(op==2){
            int k;
            cin>>k;
            add(1,x,y,k);
        }else{
            cout<<getsum(1,x,y)<<'\n';
        }
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

P13976 数列分块入门 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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 3e5 + 5;
int b[4*N],d[4*N],a[N];
void build(int p,int l,int r){
    if(l==r){
        b[p]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    b[p]=b[p<<1]+b[p<<1|1];
    return ;
}
void putdown(int p,int s,int t){
    if(s!=t&&d[p]!=0){
        int mid=(s+t)>>1;
        b[p<<1]+=d[p]*(mid-s+1);
        b[p<<1|1]+=d[p]*(t-mid);
        d[p<<1]+=d[p];
        d[p<<1|1]+=d[p];
        d[p]=0;
    }
}
void update(int p,int s,int t,int l,int r,int c){
    if(s>=l&&t<=r){
        b[p]+=c*(t-s+1);
        d[p]+=c;
        return ;
    }
    putdown(p,s,t);
    int mid=(s+t)>>1;
    if(l<=mid)update(p<<1,s,mid,l,r,c);
    if(r>mid)update(p<<1|1,mid+1,t,l,r,c);
    b[p]=b[p<<1]+b[p<<1|1];
    return;
}
int getsum(int p,int s,int t,int l,int r){
    if(s>=l&&t<=r){
        return b[p];
    }
    putdown(p,s,t);//这也得下放标记,原因是update到达目标后就不会再下方标记,标记并没有被下放完全
    int mid=(s+t)>>1;
    int res=0;
    if(l<=mid)res+=getsum(p<<1,s,mid,l,r);
    if(r>mid)res+=getsum(p<<1|1,mid+1,t,l,r);
    return res;
}
void solve(){
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    m=n;
    while(m--){
        int op,l,r,c;
        cin>>op>>l>>r>>c;
        if(op==0){
            update(1,1,n,l,r,c);
        }else{
            cout<<getsum(1,1,n,r,r)<<endl;
        }
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P8774 蓝桥杯 2022 省 A] 爬树的甲壳虫 - 洛谷

期望题

image-20251125175550370

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;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5,mod=998244353;
int f[N];
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        f[i]=((f[i-1]+1)%mod*((y%mod)*quick(y-x,mod-2)%mod)%mod)%mod;
    }
    cout<<f[n]<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}