1. 小A的文化节

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
    cin>>n>>m;
    vector<int> q(n+1,0);
    for(int i=1;i<=n;i++)    cin>>q[i];
    int res=0;
    while(m--){
        int tmp;cin>>tmp;
        res+=q[tmp];
    }
    cout<<res;
}

2. 小A的游戏

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;cin>>T;
    while(T--){
        int a,b;cin>>a>>b;
        cout<<(abs(a-b)%3==0?"Yes":"No")<<endl;
    }
}

3. 小A的数字

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;cin>>T;
    while(T--){
        int s;cin>>s;
        string str=to_string(s);
        string ans="";
        for(auto c:str){
            ans.push_back(c=='0'?'1':'0');
        }
        int tmp=atoi(ans.c_str());
        cout<<(tmp==0?(str.back()-'0'==1?2:1):tmp)<<endl;
    }
}

4. 小A的任务

维护定长b任务大根堆，总和值为ans，遍历到i，维护前缀和sum，答案即为​min(sum+ans)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,q;
    cin>>n>>q;
    vector<int> a(n),b(n);
    for(auto &i:a)    cin>>i;
    for(auto &i:b)    cin>>i;
    while(q--){
        int k;
        cin>>k;
        long long sum=accumulate(a.begin(),a.begin()+k,0LL);
        long long ans=0;
        priority_queue<int> pq;
        for(int i=0;i<k;i++){
            pq.push(b[i]);
            ans+=b[i];
        }
        long long res=sum+ans;
        for(int i=k;i<n;i++){
            ans-=pq.top();
            pq.pop();
            pq.push(b[i]);
            ans+=b[i];
            sum+=a[i];
            res=min(res,sum+ans);
        }
        cout<<res<<endl;
    }
}

5. 小A的线段

输入：

5 4
4 5
1 5
3 5
1 4

输出：

3

将每个区间排序，变为1 4 , 1 5 , 3 5 , 4 5

答案有三种情况

①1 4 , 1 5 , 3 5 , 4 5

②1 4 , 1 5 , 3 5

③1 4 , 1 5 , 4 5

设当前遍历的区间为[x,y]，每个区间的累计状态记为[s,t]

对于第一种我们可以通过这种状态转换得到[0,0]->[0,4]->[5,5]->[5,5]，我们理想的状态是[n,n]，此时刚好[1,n]被覆盖过两次

设dp[s,t]表示s左侧区间被统计过两次，区间[s,t]被统计过一次，得到的方案数，答案即为dp[n,n]

① ​y<s ，说明[s,t]区间左侧被计算过两次，添加这个区间，相当于得到状态[s,t]的方法都可以带上[x,y]这个区间，即dp[s,t]+=dp[s,t]

② ​y<t ， 说明区间[y,s]被计算了两次，只需要在计算dp[y,t]的值即可，dp[y,t]+=dp[s,t];

③ ​y>=t ， 同②，只需计算dp[t,y]

④ ​s < x-1 ，说明区间[s,x)未被计算两次，但[x,t]被计算两次，排序后，根据dp定义这种情况不符合条件，直接跳过即可

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
 
int main() {
  
    int n,m;cin>>n>>m;
    vector<pair<int, int>> p(m);
    for (auto &[x,y]:p)  cin>>x>>y;
    sort(p.begin(),p.end());
  
    map<pair<int,int>,int> dp;
    dp[{0,0}]=1;
    for (auto &[x,y]:p) {
        map<pair<int, int>,int> dp2(dp);
        for (auto &[u,val]:dp) {
            auto &[s,t]=u;
            if (s<x-1)  continue;
            if (y < s) {
                dp2[u] = (dp2[u] + val) % mod;
            } else if (y < t) {
                dp2[{y, t}] = (dp2[{y, t}] + val) % mod;
            } else if (y >= t){
                dp2[{t, y}] = (dp2[{t, y}] + val) % mod;
            }
        }
        dp=move(dp2);
    }
 
    int ans = 0;
    for (auto &[u,val]:dp) {
        if (u.first == n) {
            ans = (ans + val) % mod;
        }
    }
 
    cout << ans << "\n";
    return 0;
}

==== 1 ====
当前遍历区间1 4
0 0 1
0 4 1
==== 2 ====
当前遍历区间1 5
0 0 1
0 4 1
0 5 1
4 5 1
==== 3 ====
当前遍历区间3 5
0 0 1
0 4 1
0 5 1
4 5 1
5 5 1
==== 4 ====
当前遍历区间4 5
0 0 1
0 4 1
0 5 1
4 5 1
5 5 3