题目列表

CF1914

A. Problemsolving Log

B. Preparing for the Contest

C. Quests

D. Three Activities

E. Game with Marbles

F. Programming Competition

G. Light Bulbs

AB 一句话题解

A.用一个桶记录数字出现次数然后从小到大枚举即可

代码

B.题目给你 n,k 你要保证生成一个序列 {a} 满足 ai>ai−1a_i>a_i-1 不得超过 k 次（从第二位开始计数）

代码

C

C.n个关卡，首通奖励 a_i 重复通关奖励 b_i ，你最多能打x关并且通关按照顺序，询问你最多能够得到多少奖励

我们可以枚举通到哪一关，重复通关就直接一直通之前 b_i 最大的即可

代码

D

给你三个数组 a,b,c 选择最大的 ai+bj+ck,i≠j≠ka_i+b_j+c_k , i\neq j\neq k

直接a,b,c排序取前3个最大的，可以证明取前三个最大的一定包含最优情况。

代码

E

两个数组 a,ba,b 每次 a,ba,b 轮流进行操作 ai−1,bi=0a_i-1,b_i=0 (B的ab要交换)，选手A 想要最大化 ∑ai−bi\sum{a_i-b_i} 同时选手B要最小化，询问两人都执行最优操作最后两个数组的差值

显然，如果A 操作 ii 位置能获得的差值是 ai+bj−1a_i+b_j-1 ,B同理也是 ai+bj−1a_i+b_j-1，排序然后轮流操作即可。

代码

F

给你一颗树，树的节点不能与自己祖先节点配对，询问最多能够配对多少节点。1是根节点。

我们考虑一个节点 tt 的所有子树，如果他们的 sizev<(sizet−1)/2size_v<(size_t-1)/2 说明可以让子树的来交叉两两匹配。

否则记录 g[u]g[u] 表示 uu 的子树最多能自行配对的节点个数。对于节点 tt ，它的唯一重儿子 vv ，有如下转移：

g[t]=min(sz[t]−1,g[u]+(sz[t]−1−sz[u])∗2)g[t]=min(sz[t]-1,g[u]+(sz[t]-1-sz[u])*2) 因为后面这里 sz[u] 是一定比 sz[t]-1-sz[u] 大的，所以不会出锅 我突然发现自己写了这么烂的代码还没有bug

代码

G

给你一个长度为 2n2n 的串，每个元素都是 1≤ai≤n1 \leq a_i \leq n 并且都出现两次，你可以进行以下操作：

一个 axa_x 被访问，另一个 axa_x 也可以被访问

记 ai=aja_i=a_j 对于 k∈[i,j],akk \in [i,j],a_k 都可以被访问，现在记我们访问的集合为S ，询问S最小值以及可能的方案数。

最简单的想法是，对于 ai=aja_i=a_j 他们都向 [i,j][i,j] 的其他点连一条有向边，其他点同理，如果答案为 1 的话，有一些点一定可以访问到所有点

否则，他们一定被分成很多个区间，并且这些区间仅有完全包含关系或者不相交关系，同时这些区间一定是连续的

例如 1 1 2 4 3 5 5 4 2 3 可以视为 [1,1][2,4,3,5,5,4,2,3] 其中右边区间包含区间 [5,5]

对于上述做法，方案数就是每个区间中能访问其他所有点的点的个数乘积，S的大小为这种区间的个数

进一步思考，我们能够证明方案数是没有被包含区间中没有子区间覆盖的数量的乘积。

证明：

对于被包含的区间，区间内的所有点都最多只能访问到这个小区间，但是区间外的大区间有的点能够访问里面的点，所以里面的区间点没有用。

对于被这种小区间覆盖的点，一定是被大区间覆盖掉了，这种区间有一个性质，就是出现的元素都出现了偶数次，假设我们选的是 a 号点，和他一样的点是 b ，我们可以如下操作：

a,b 一定在大区间内，如果 a,b 不是这个大区间的端点,那么a-b一定有其他点的 b’ 节点在区间外，否则就矛盾了。以此类推，直到到了端点。

那怎么处理呢，直接每个数字随机一个权值然后哈希，在把 [l,r] 的所有哈希值放入一个 vector 中排序，接着做一个差分即可。

时间复杂度 O(nlog⁡n)O(n\log 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=400200;
const int modp=998244353;

int n,m,a[maxn],s[maxn],b[maxn];
int ans,unqualify;
int c[maxn];
map <int,int> mp;

void solve()
{
    ans=0;
    cin>>n;
    srand(n);
    mp.clear();
    n*=2;
    for(int i=1;i<=n;i++) 
    {
        c[i]=0;
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(!mp[a[i]])
        {
            mp[a[i]]=abs(1ll*(rand()+1)*(rand()+1)*(rand()+1)*(rand()+1));
            b[i]=mp[a[i]];
        }
        else b[i]=mp[a[i]];
    }
    for(int i=1;i<=n;i++) 
    {
        s[i]=(s[i-1]^b[i]);
    }
    int las=0;
    int tmpcost=1;
    for(int i=1;i<=n;i++)
    {
        if((s[i]^s[las])==0ll) 
        {
            vector <pair<int,int> > tmp;
            for(int j=las+1;j<i;j++) tmp.push_back(make_pair(s[j],j));
            sort(tmp.begin(),tmp.end());
            for(int j=1;j<tmp.size();j++)
            {
                if(tmp[j].first==tmp[j-1].first)
                {
                    c[tmp[j-1].second+1]++;
                    c[tmp[j].second+1]--;
                }
            }
            int tot=0;
            for(int j=las+2;j<i;j++)
            {
                c[j]+=c[j-1];
                if(c[j]>=1) tot++;
            }
            tmpcost=tmpcost*(i-las-tot)%modp;
            ans++;
            las=i;
        }
        else
        {
            // if(i==las+1) continue;
            // if(nxt[a[i]]==i) continue;
            // else if((s[i-1]^s[nxt[a[i]]])==0) unqualify++;
        }
    }
    cout<<ans<<" "<<tmpcost<<"\n";

}

signed main()
{
    ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}