首页 > 其他分享 >2024暑假集训测试1

2024暑假集训测试1

时间：2024-07-09 11:20:33浏览次数：27  
标签：10 ok gcd int 2024 ge 暑假 集训 define

前言

image

排名历程：\(3→5→3\)，因为 \(T1\) 的 special judge 是后来加上的，导致部分人挂了分，赛后安排了重测，就变成了 \(rank5\)，赛后发现 \(T1\) 数据过水，重新更新了数据，卡掉了很多人的假做法，又成了 \(rank3\)。

T1

已知合法的分组有 \(\begin{cases} 0~0~0\\ 1~1~1\\ 2~2~2\\ 0~1~2\\ \end{cases}\)

  • 唐氏做法：

    统计 \(cnt_0,cnt_1,cnt_2\) ，找规律发现除了其中两个 \(\bmod 3=2\) ，剩下一个 \(\bmod 3<2\) 时，将 \(<2\) 的一组中拆出来两个补给其余两个形成 \(0~1~2\) ，这样 \(ans-1+2\)，更优。

    其余情况均为将其各自分组，最后余下的形成 \(0~1~2\) 即可。

    由此 \(if~else\) 大模拟即可。

  • 正解：

    考虑枚举 \(0~1~2\) 的组数即可。

T2

  • 部分分 \(30pts\)： \(n\le 1e7\) 的情况，暴力即可。

  • 正解：

    大模拟不想打了，总而言之就是找到一个周期，周期之外的再特殊处理即可。

    考虑到存在没有周期的情况，仅存在于二者完全势均力敌或单方面碾压的数据中，如 ABABABAB…… 就是完全势均力敌，最后比分一定为 \(0:0\)；另一种当一方已经赢过两次而另一方一次没有赢过时（且此时已经循环超过 \(2\times k\)），结果一定为 \(x:0\) 或 \(0:x\)。此两种情况特判即可。

    模拟懒得写了，挂个官方题解吧：

    官方题解

    我们把 \(k\) 颗球看做是一轮。

    对于每一轮来说，如果在这一轮开始前，比分是 \(a:b\)，那么这一轮结束后，比分是多少就是确定的。

    很明显可以看出来的一点是，开始时候两个人的当前局得分如果都 \(>11\) 的话，同时把两个人的分数减去同样的分数，使得两个人的分数都 \(≤11\)，是不会影响这一轮结果的。

    那么，我们开三个数组 \(t,sa,sb\)，分别记录。\(t_{a,b}\)：最早什么时候，遇到这一轮开始前，比分是 \(a:b\)。\(sa_{a,b},sb_{a,b}\)：这个时候，zwh/小红一共赢了多少局。

    那么，当我下一次在tim时候（此时总比分是 \(A:B\) ）模拟遇到同样的 \(a,b\) 时，就可以视作，模拟的过程是每 \(tim−t_{a,b}\) 一个周期，每个周期内，大局的得分都是 \(A−sa_{a,b}:B−sb_{a,b}\)。

    直接跳过这个超级大周期，然后模拟完剩余的时间即可。

    由于开始的比分最多只有 \(12×12+1=145\) 种，因此模拟的总次数不会超过 \(145×k\)。

T3

  • 部分分 \(30pts\)：爆搜即可。

  • 部分分 \(40pts\)：再处理一下 \(k=1\) 的情况即可。

  • 正解 \(100pts\)：

    • 结论：

      忽略字典序，将所有 & 放在前面，所有 | 放在后面一定是最优情况。

      • 证明：

        有 \(\begin{cases} x|y\ge \max(x,y)\\ x\&y\le \min(x,y)\\ x\&y\le x|y\\ \end{cases}\)

        因此有 \(x\&y|z\ge \max(x\&y,z)\ge \min(x|y,z)\ge x|y\&z\)。

        解释一下，若 \(x\&y\ge z\) ，\(\because x|y\ge x\&y\)，\(∴ \max(x\&y,z)=x\&y\ge z=\min(x|y,z)\)；

        反之若 \(x\&y<z\)，\(\because x|y\ge x\&y\)，\(∴ \min(x|y,z)\ge z=\max(x\&y,z)\)。

        由此继续推广，得上述结论，证毕。

    因此根据上述结论我们可以先求出最大答案，接下来处理字典序的问题。

    从前往后推，若该位填 |，后面的依然按照结论进行，若答案不变，则本位可以填 |，否则填 &。

    由此 \(O(n^2)\) 算法已经可以得到 \(60pts\) 了。

    考虑 \(a_i<2^{60}\) ，可以按位计算，当计算到第 \(i\) 位时，对于区间 \([l,r]\)，若填 &，只有 \(a_l\sim a_r\) 本位均为 \(1\) 时答案本位才能为 \(1\)，否则为 \(0\)；若填 |，只要 \(a_l\sim a_r\) 中有一个本位为 \(1\) 答案本位就可以为 \(1\)，否则为 \(0\)。

    由此算法优化到 \(O(n\log(n))\)，可以通过此题。

    点击查看代码 
    #include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,M=61;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,k,a[N],maxx,m,ans,now,b[M],sum[N][M];
int check(int l,int now,int k)
{
    if(l<=n-k)
    {
        for(int i=0;i<=m;i++) b[i]=sum[n-k][i]-sum[l-1][i];
        for(int i=0;i<=m;i++) 
            if(b[i]!=n-k-l+1&&(now>>i)&1)
                now^=(1ll<<i); 
    }
    if(n-k+1<=n)
    {
        for(int i=0;i<=m;i++) b[i]=sum[n][i]-sum[n-k][i];
        for(int i=0;i<=m;i++)
            if(b[i]!=0) 
                now|=(1ll<<i);
    }
    return now;
}
signed main()
{
    read(n),read(k);
    for(int i=1;i<=n;i++) read(a[i]),maxx=max(maxx,a[i]);
    m=log2(maxx);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++) sum[i][j]=sum[i-1][j];
        for(int j=0;j<=m;j++) if((a[i]>>j)&1) sum[i][j]++;
    }
    ans=check(2,a[1],k);
    write(ans),puts("");
    now=a[1];
    for(int i=2;i<=n;i++)
        if(k>=1&&check(i+1,now|a[i],k-1)==ans)
            putchar('|'),now|=a[i],k--;
        else 
            putchar('&'),now&=a[i];
}

T4

  • 赛时部分分都没打出来，直接看正解吧。

  • 正解：

    预处理一个布尔数组 \(ok_{l,r}\)，表示区间 \([l,r]\) 能否全部删掉。

    区间 \(DP\) 处理，有：

    \[ok_{l,r}|=(ok_{l,k-1}\&ok_{k+1,r})\&([\gcd(a_{l-1},a_k)>1]|[\gcd(a_k,a_{r+1})>1]),k∈[l,r] \]

    初始值： \(\begin{cases} ok_{l,r}=1&l>r\\ ok_{i,i}=1&\gcd(a_{i-1},a_i)>1 || \gcd(a_i,a_{i+1})>1\\ \end{cases}\)

    此时需要假设 \(a_{l-1},a_{r+1}\) 没有被删掉，貌似假了，但是看到下面的 \(DP\) 式子就知道其是正确的了。

    \(f_i\) 表示若 \(a_i\) 不删，前 \(i\) 个元素中最多能删多少个，有：

    \[f_i=\max_{j=0}^{i-1}\{f_j+ok_{j+1,i-1}\times (i-j-1)\} \]

    答案为 \(f_{n+1}\)。

    预处理 \(\gcd\)，复杂度为 \(O(n^3)\)。

    点击查看代码 
    #include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=510;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,a[N],gcd[N][N],f[N];
bool ok[N][N];
int Gcd(int a,int b) {return b==0?a:Gcd(b,a%b);}
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            gcd[j][i]=gcd[i][j]=Gcd(a[i],a[j]);
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<i;j++)
            ok[i][j]=1;
    for(int i=1;i<=n;i++)
        if(gcd[i][i+1]>1||gcd[i-1][i]>1) ok[i][i]=1;
    for(int i=1;i<=n;i++)
        for(int l=1;l+i-1<=n;l++)
        {
            int r=l+i-1;
            for(int k=l;k<=r;k++)
            {
                ok[l][r]|=(ok[l][k-1]&ok[k+1][r])&(gcd[k][l-1]>1|gcd[k][r+1]>1);
                if(ok[l][r]==1) break;
            }
        }
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<=i-1;j++)
                f[i]=max(f[i],f[j]+(i-j-1)*ok[j+1][i-1]);
    write(f[n+1]);
}

T5

  • 部分分 \(15pts\)：对于 \(n\le 8\) 的数据，直接爆搜。

  • 部分分 \(60pts\):对于所有 \(n\le 20\) 的数据，状压优化概率 \(DP\)。

  • 部分分 \(85pts\)：

    利用数学模型，对于 \(5\) 个数的排列，另其前三个数的顺序确定，则其概率为 \(\dfrac{3!}{A_{5}^{3}}\) ，此时不管另其前三个顺序为 a,b,c 还是 b,a,c 等概率都是一样的。

    枚举最后一个听的歌为 \(x\)，考虑其他的歌，定义 \(f_{i,j,k}\) 表示对于前 \(i\) 首歌，选择了 \(j\) 首，使其愉悦值为 \(k\) 的方案数，第一维可以滚掉，即典型的 \(01\) 背包。

    最后统计答案为 \(ans_x=\sum\limits_{j=0}^{n-1}\sum\limits_{k<S\&k+a_x\ge S}f_{j,k}\times\dfrac{(j+1)!}{n}\)。

    复杂度为 \(O(n^3S)\)。

  • 正解：

    在 \(85pts\) 部分分基础上进行优化。

    考虑先将所有 \(i\) 对于 \(f_{j,k}\) 处理出来，当枚举到最后一个听的歌为 \(i\) 时将 \(i\) 的贡献去除掉，处理完再加回来，从而使复杂度优化到 \(O(n^2S)\)。

    基于 \(01\) 背包倒叙循环 \(j\) 使 \(f_{j-1,k}\) 的只能对 \(f_{j,k+a_i}\) 进行一次贡献，得到 \(ins\) 操作：

    for(int j=n;j>=1;j--)
    for(int k=0;k<s-a[i];k++)
        f[j][k+a[i]]+=f[j-1][k];

    考虑如何将其撤销，若依旧将 \(j\) 倒叙循环，我们知道现在的 \(f_{j-1,k}\) 已经今非昔比了，再这么做会减去比应有的更多的贡献，由此将 \(j\) 正序循环，现将 \(f_{j-1,k}\) 变回原来的模样，再另 \(f_{j,k+a_i}\) 减去 \(f_{j-1,k}\) 的贡献；感性理解就是之前怎么搞的，现在就反着搞回去。由此得到 \(del\) 操作：

    for(int j=1;j<=n;j--)
    for(int k=0;k<s-a[i];k++)
        f[j][k+a[i]]-=f[j-1][k];

    其余同 \(85pts\) 做法。

    点击查看代码 
    #include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=110,M=1e4+10,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,a[N],jc[N],f[N][M];
int qpow(int a,int b)
{
    int ans=1;
    for(;b;b>>=1)
    {
        if(b&1) (ans*=a)%=P;
        (a*=a)%=P;
    }
    return ans;
}
int A(int n,int m)
{
    if(n<m) return 0;
    return jc[n]*qpow(jc[n-m],P-2)%P;
}
void add(int &x,int y) {x=((x+y)%P+P)%P;}
void ins(int i)
{
    for(int j=n;j>=1;j--)
        for(int k=0;k<m-a[i];k++)
            add(f[j][k+a[i]],f[j-1][k]);
}
void del(int i)
{
    for(int j=1;j<=n;j++)
        for(int k=0;k<m-a[i];k++)
            add(f[j][k+a[i]],-f[j-1][k]);
}
signed main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    jc[0]=1;
    for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%P;
    f[0][0]=1;
    for(int i=1;i<=n;i++) ins(i);
    for(int i=1;i<=n;i++)
    {
        del(i);
        int ans=0;
        for(int j=0;j<=n-1;j++)
            for(int k=m-a[i];k<m;k++)
                add(ans,f[j][k]*jc[j]%P*qpow(A(n,j+1),P-2)%P);
        ins(i);
        write(ans),putchar(' ');
    }
}

    因为我懒得预处理所以多了个 \(\log\)。

总结

要具备一些 \(OIer\) 的基本素养，不要没事就想着 \(if~else\)。

合理分配耗时间，不要因思维失误浪费过多时间，本次模拟赛大多数人都是打不完题从而挂分。

分数还是太平凡了，得来的分都没什么营养价值，能力依旧不足，需要提升思维能力。

标签：10,ok,gcd,int,2024,ge,暑假,集训,define
From： https://www.cnblogs.com/Charlieljk/p/18291024

相关文章

  • 2024.07.09【读书笔记】|医疗科技创新流程（第二章 创新创造 概念探索与测试案例分析1）
    案例一：Oculeve-神经刺激治疗干眼症背景与挑战干眼症（DryEyeDisease,DED）是一种常见的眼部疾病，影响着数百万美国人的生活质量。该病症由泪液不足或蒸发过快引起，导致眼表炎症、疼痛、灼热感、异物感和视力受损。Oculeve团队认识到，尽管市场上有人工泪液等治疗方法，但这些方......
  • SMU Summer 2024 Contest Round 1
    SequenceDecomposing1.题意其实就是要我们找共有多少个最长的上升的子序列，也就是理解成可以找到几个尽量长的队伍（最少LIS不相交覆盖）2.我们开一个multiset，然后先放进去第一个数，由于multiset会对元素自动从小到大排序，那么我们放进的队尾，也是排序好的，然后从第二个数开始遍历，检查一......
  • 2024码蹄杯职高省赛第三场初赛全题解
    其实吧对于码蹄杯省赛的话，第三场是一千五百多人，百分之25的获奖率，然后前四百名左右就可以获奖，根据排行来看大概是六题左右，其中大概就四题要点脑子，其余的基本上属于语法题，也就是13题中如果语法没问题的话，九题是很轻松的，因为都是青铜白银题，语法没问题的话就OK的，然后就是一个P序列，......
  • 题解(2024.7.8贪心)
    1.Teleporters（HardVersion）题意：有n+2个位置：0～n+1，给定n个数\(a_1\)～\(a_n\),有以下操作：向左/右移动一格，代价为1。传送回0位置或者n+1位置，记你当前的位置为i，则代价为\(a_i\)。每个位置只能发动一次传送。求最大传送次数思路：因为每次传送都会回到0/n+1号点，所以，到......
  • 2024已过半，还没试过在vue3中使用ioc容器吗？
    Vue3已经非常强大和灵活了，为什么还要引入IOC容器呢？IOC容器离不开Class，那么我们就从Class谈起Class的应用场景一提起Class，大家一定会想到这是Vue官方不再推荐的代码范式。其实，更确切的说，Vue官方是不推荐基于Class来定义Vue组件。如图所示：社区确实有几款基于Clas......
  • 2024年7个最佳WooCommerce商城案例
    WooCommerce毫无疑问是最受欢迎的电子商务平台。截至2021年，它的下载量已超过8230万次，运行的网站超过380万个。 就市场份额而言，WooCommerce高达40.9%—比紧随其后的竞争对手Shopify高出近15%。 这些数字说明了WooCommerce的规模有多大，以及无数电子商务品......
  • 南京外国语学校暑期集训7/8号排序2
    显然，这道题使用快排第k大做，快排第k大思想：（下标从1开始）每次找一个key值，一轮后可以得到key在原数组中的位置（暂且称之为a），把a和n-k+1值比较，一样就返回，小就往左边找，大就往右边找。然后原数组在main里按题目要求初始化一下就行了点击查看代码#include<bits/stdc++.h>usingnamespac......
  • 9个用于测试自动化的最佳AI测试工具（2024）
    选择一款优质的基于生成式AI人工智能的测试工具能够确保测试过程的准确性和效率，从而加速整个软件测试周期。相反，设计不佳的测试工具可能无法发现错误，并可能存在安全问题。它们可能产生误报或漏报，误导开发与测试团队，导致潜在的软件故障。  1、testRigortestRigor是一个基......
  • 2024/7/8 笔记
    CF1656Hhttps://www.luogu.com.cn/problem/CF1656H参考DaiRuiChen007的题解:code:usingnamespacestd;#definell__int128_tconstintmaxn=1e3+10;llgcd(lla,llb){ returnb?gcd(b,a%b):a;}constintN=1024,N2=N<<2;structstree{ lltree[N2];......
  • 国开大学2024《电子商务法律与法规（统设课）》
    一、单选题1.2017年8月18日（）挂牌成立,这是全国第一家集中审理涉网案件的试点法院。A.北京互联网法院B.广州互联网法院C.杭州互联网法院D.上海互联网法院答案：C2.电子合同是平等主体之间以（）的形式达成的,设立、变更、终止民事权利义务关系的协议。A.电子签名B.数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99