C - Between P and Q

题意简述

给定两个长度为N的排列P和Q，找到满足字典序大于P小于Q的长度为N的排列的个数

约束条件

  • 1≤N≤10
  • P和 Q 是 (1,2,…,N) 的排列。
  • 所有输入值均为整数。

思路

注意到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;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl "\n"
#define int long long
#define ld long double 
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const double PI = acos(-1.0),eps=1e-12L;
const long long  inf=1e18+10;
bool judge(vector<int> &a,vector<int> &b){
    int n=a.size();
    for (int i=0;i<n;i++){
        if (a[i]!=b[i]){
            return a[i]>b[i];
        }
    }
    return 0;
}
void solve(){    
    int n;
    cin>>n;
    vector<int> p(n),q(n);
    for (int i=0;i<n;i++) cin>>p[i];
    for (int i=0;i<n;i++) cin>>q[i];
    vector<int> t(n);    
    for (int i=0;i<n;i++) t[i]=i+1; 
    int ans=0;
    do{
        if (judge(t,p) && judge(q,t)) ans++;
    }while(next_permutation(t.begin(),t.end()));
    cout<<ans<<endl;
}
signed main(){
    IOS;
    int  T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}

D - Pre-Palindrome

题意简述

一个只包含小写英文字母的字符串，如果满足下面这个条件，就被称作好字符串：

  • 最多改写一个字符后，它能变成一个回文串。

给定一个问有多少个子串是好字符串。

约束条件

  • S 的长度在 11 到 104104 之间，且只包含小写英文字母。

思路

一般问回文串有很多情况可以按照长度分成偶数长度和技术长度；

我们也可以按照这个来分类 注意到：一个字符串向两边拓展，只有不符合的大于2，那么之后的肯定不复和；

奇数：长度为1的肯定符合，本身就是回文串，本身不符合的为0，然后向外拓展

偶数：长度为2也肯定符合，本身不符合的<=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
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl "\n"
#define int long long
#define ld long double 
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const double PI = acos(-1.0),eps=1e-12L;
const long long  inf=1e18+10;
void solve(){    
	string s;
	cin>>s;
	int n=s.size();
	int ans=0;
	//奇数
	for (int i=0;i<n;i++){
		ans++;
		int cnt=0;
		int l=i-1,r=i+1;
		while (l>=0 && r<n){
			if (s[l]!=s[r]) cnt++;
			if (cnt==2) break;
			ans++;
			l--;
			r++;
		}
	}
	//偶数
	for (int i=0;i<n-1;i++){
		ans++;
		int cnt=(int)(s[i]!=s[i+1]);
		int l=i-1,r=i+2;
		while (l>=0 && r<n){
			if (s[l]!=s[r]) cnt++;
			if (cnt==2) break;
			ans++;
			l--;
			r++;
		}
	}
	cout<<ans<<endl;
}
signed main(){
    IOS;
    int  T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}

E - Sum of Average

题目描述

给你一个正整数 N，还有一个长度为 N 的整数序列 A=(A1,A2,…,AN)。

定义 f(l,r) 为区间 Al,Al+1,…,Ar的算术平均值。

求 ∑1≤l≤r≤Nf(l,r)\sum_{1 \leq l \leq r \leq N} f(l, r)，结果对 998244353998244353 取模。

约束条件

  • 1≤N≤5×10^5^
  • 0≤Ai<998244353
  • 所有输入均为整数。

思路

对于这中的求和公式我们可以尝试拆分化简

对于单独的Ai 他对答案的贡献可以写成Ai 乘以几个分数之和；

那么这个分数之和我们可以通过打表得出规律

1/11/21/31/41/51/6
a1111111
a2122221
a3123321
a4123321
a5122221
a6111111

根据表格可得具有一定的对称性和规律，

可以通过预处理出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
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
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl "\n"
#define int long long
#define ld long double 
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const double PI = acos(-1.0),eps=1e-12L;
const long long  inf=1e18+10;
int mod=mod2;
int qpow(int base,int exp){
    int res=1;
    while (exp){
        if (exp&1) res=res*base%mod;
        base=base*base%mod;
        exp>>=1;
    }
    return res;
}
int inv(int n){
    return qpow(n,mod-2);
}
void solve(){    
    int n;
    cin>>n;
    vector<int> a(n+1);
    
   	//打表用
    // vector<vector<int> > t(n+1,vector<int> (n+1));
    // for (int i=1;i<=n;i++){
    //     for (int j=1;j<=n+1-i;j++){
    //         for (int k=1;k<=j;k++){
    //             t[i-1+k][j]++;
    //         }
    //     }
    // }
    // for (int i=1;i<=n;i++){
    //     for (int j=1;j<=n;j++){
    //         cout<<t[i][j]<<" \n"[j==n];
    //     }
    // }
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    vector<int> pre(n+1);
    for (int i=1;i<=n;i++){
        pre[i]=(pre[i-1]+inv(i))%mod;
    }
    int t=pre[n];
    for (int i=1;i<=(n+1)/2;i++){
        int j=n-i+1;
        if (i!=j){
            ans=(ans+(a[i]+a[j])%mod*t%mod)%mod;
        }else{
            ans=(ans+(a[i])*t%mod)%mod;
        }
        t=(t+((pre[j-1]-pre[i])%mod+mod)%mod)%mod;
    }
    cout<<ans<<endl;
}
signed main(){
    IOS;
    int  T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}

F - Chmax

题目描述

给你一个正整数 N，还有一个长度为 N的排列 P=(P1,P2,…,PN)，它是 (1,2,…,N) 的一个重排。

定义三个变量 x,y,c，初始时 x=y=c=0。

接下来，对于 k=1,2,…,N，你要依次执行以下两种操作中的一种：

  • 操作 1：如果 x<Pk ，则 c 加 11；然后将 x 更新为 max⁡(x,Pk)。
  • 操作 2：如果 y<Pk ，则 c 加 11；然后将 y 更新为 max⁡(y,Pk)。

你的任务是求出最终 c 能达到的最大值。

限制条件

  • 1≤N≤5×10^5^
  • P 是 (1,2,…,N) 的一个排列。
  • 所有输入均为整数。

思路

（感谢学长的思路喵^_^）

这道题表面上看是一个需要同时维护 xx 和 yy 状态的动态规划问题，但通过分析变量的性质，可以将其简化为非常经典且高效的 “前缀最大值 + 最长上升子序列 (LIS)” 问题。

核心观察

  1. max⁡(x,y)\max(x, y) 是恒定的

观察操作过程，每次将 PkP_k 放入 xx 或 yy 时，较大的那个变量必然会被更新为当前的前缀最大值。 也就是说，在处理完前 kk 个元素后：

max⁡(x,y)=max⁡(P1,P2,…,Pk)\max(x, y) = \max(P_1, P_2, \dots, P_k)

因为较大值是固定的，我们只需要关注较小值 min⁡(x,y)\min(x, y) 的变化。

  1. 按元素类型分类讨论

设处理到 PkP_k 时，前 k−1k-1 个元素的最大值为 M=max⁡(P1,…,Pk−1)M = \max(P_1, \dots, P_{k-1})：

情况一：Pk>MP_k > M（PkP_k 是新的前缀最大值）

  • 因为 PkP_k 严格大于之前的 xx 和 yy，所以无论将 PkP_k 赋给 xx 还是 yy，cc 都必定增加 11。
  • 为了给后续操作留出更大的空间，最明智的做法是将 PkP_k 放到原本较大的变量上，这样可以保持较小值 min⁡(x,y)\min(x, y) 不变。
  • 结论：每一个前缀最大值元素，都会无条件让答案 cc 加 11。

情况二：Pk<MP_k < M（PkP_k 不是前缀最大值）

  • 此时 PkP_k 只能尝试更新较小的值 p=min⁡(x,y)p = \min(x, y)。
  • 如果 p<Pkp < P_k，我们可以把 pp 更新为 PkP_k，此时 cc 增加 11。
  • 这与求解 最长上升子序列 (LIS) 的转移逻辑完全一致：只要新加入的数比前一个选择的数大，就能构成更长的递增链，从而让 cc 多加 11。

最终结论

  1. 统计序列 PP 中所有满足 Pk>max⁡(P1,…,Pk−1)P_k > \max(P_1, \dots, P_{k-1}) 的元素数量，记为 AA（即前缀最大值的个数）。
  2. 将其余不满足该条件的元素按原顺序提取出来，组成新序列 QQ。
  3. 计算序列 QQ 的 最长上升子序列长度 LIS(Q)\text{LIS}(Q)。

最终的最大 cc 值即为：

Ans=A+LIS(Q)\text{Ans} = A + \text{LIS}(Q)

整体时间复杂度为 O(Nlog⁡N)O(N \log N)，空间复杂度为 O(N)O(N)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl "\n"
#define int long long
#define ld long double 
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const double PI = acos(-1.0),eps=1e-12L;
const long long  inf=1e18+10;
int get(vector<int> a){
    if (a.empty()) return 0;
    vector<int> lis;
    for (int x:a){
        auto it = lower_bound(lis.begin(), lis.end(), x);
        if (it == lis.end()) {
            lis.push_back(x);
        } else {
            *it = x;
        }
    }
    return lis.size();
}
void solve(){    
    int n;
    cin>>n;
    vector<int> p(n);
    for (int i=0;i<n;i++){
        cin>>p[i];
    }
    int premax=0;
    int curmax=-1;
    vector<int> q;
    for (int x:p){
        if (x>curmax){
            curmax=x;
            premax++;
        }else{
            q.push_back(x);
        }
    }
    int ans=premax+get(q);
    cout<<ans<<endl;
}
signed main(){
    IOS;
    int  T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}