比赛记录

比赛传送门

D

可以注意到,由于飞机中两个三个相同的数必须是相邻的,所以只用枚举一个数便可知道另一个三个相同的数是什么
接下来就该考虑如何分配后面两个对子:
对于一个点数,如果该点数有 $2$ 或 $3$ 张,那么该点数可以拿去凑到其中一对
(记这种情况的点数有 c2 个)
如果 $≥4$ 张,那么该点数可以自成两对或者是拿去凑到其中一对
(记这种情况的点数有 c4 个)
于是可以这样组合:
c2中自取不同的两对: c2*(c2-1)/2
c4中自取不同的两对: c4*(c4-1)/2
c2和c4中各取一对: c2*c4
c4中自取相同的两对: c4
在每次枚举三个相同的数时更新 c2 和 c4 即可快速计算

Code

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
void solve(){
    int n;
    cin >> n;
    vector<int> cnt(N);
    for(int i=0;i<n;i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    int cnt2=0,cnt4=0;
    for (int i=1;i<N;i++) {
        if (cnt[i]>=4) {
            cnt4++;
            continue;
        }
        if (cnt[i]>=2) cnt2++;
    }
    int ans=0;
    for (int i=1;i<N-1;i++) {
        if (cnt[i]>=3 && cnt[i+1]>=3) {
            int t1=cnt[i];
            int t2=cnt[i+1];
            t1-=3; t2-=3;
            int c2=cnt2; int c4=cnt4;
            if (cnt[i]>=4 && t1<4) {
                c4--;
                if (t1>=2) c2++;
            }
            else if(cnt[i]<4) c2--;
            if (cnt[i+1]>=4 && t2<4) {
                c4--;
                if (t2>=2) c2++;
            }
            else if(cnt[i+1]<4) c2--;
            ans=(ans+(c2*(c2-1)/2)%MOD+c4+(c2*c4)%MOD+(c4*(c4-1)/2)%MOD)%MOD;
        }
    }
    cout<<ans<<el;
}

G

仔细观察可以注意到,对于一个顺子区间[l,r] 修改次数为$n$-该区间内数字的种类数(这里指在原数组内的)
点数最多1e9,用map存点数信息,由于我们最后只要计算区间内元素种类数,点数个数并不重要,我们将点数的最后一次出现的索引记录,便于后续给出操作方案
可以将map存储的信息转到 vector 容器中,便于我们查询

可以发现,区间端点为原先就有的数字为最优
利用双指针计算长度为 $n$ 的区间包含的最多元素种类数,同时记录最优区间的左端点,便于后续给出操作方案
目前已经可以给出最优操作次数了,就差给出操作方案:
用set记录最优区间中已经包含的数字,用vis数组记录这些数字最后一次出现的索引(因为只要保留一个,所以有最后一个索引也就够了)
遍历原数组,跳过vis数组中已经记录过的索引,这些位置不要动
记一个变量 $now$ 为当前要改成的数字,在遍历原数组的过程中,要跳过原数组中已经有的最优区间内的数字

Code

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
void solve(){
    int n;
    cin >> n;
    map<int,int> mp;
    vector<int> v(n+1);
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        mp[x]=i;
        v[i]=x;
    }
    vector<pair<int,int>> a(all(mp));
    int ans=0,l=-1;
    for (int i=0,j=0;i<a.size();i++) {
        int right=a[i].first+n-1;
        while(j<a.size() && a[j].first<=right) j++;
        if (j-i>ans) {
            ans=j-i;
            l=i;
        }
    }
    set<int> used;
    vector<int> vis(n+1);
    for (int i=l;i<l+ans;i++) {
        used.insert(a[i].first);
        vis[a[i].second]=true;
    }
    int now=a[l].first;
    vector<pair<int,int>> res;
    for (int i=1;i<=n;i++) {
        while (used.find(now)!=used.end())  now++;
        if (vis[i]) continue;
        res.pb({i,now});
        now++;
    }
    cout << n-ans << el;
    for (auto &[x,y]:res) cout<<x<<" "<<y<<el;
}

说些什么吧！

waline