首页 > 其他分享 >2023年暑假集训总结/6.30

2023年暑假集训总结/6.30

时间：2023-07-02 20:44:55浏览次数：33  
标签：std vis int 6.30 Era 2023 INF 集训 define

6-30

　　GCD

　　有 R − L + 1 个整数，分别为 L, L + 1, . . . , R − 1, R。你可以做如下操作最多 K 次：• 选择其中两个数 a, b，删掉它们，并往里面插入一个新的数 a × b。请判断是否可以让剩余所有数的 GCD 不为 1。该题存在 T 组数据。

　　显然，让所有数的最大公约数为2是最优的，那么判断区间奇数个数 ⌊ R+1/2 ⌋ − ⌊ L/2 ⌋ 是否 ≤ K 即可。

　　std:

#include <bits/stdc++.h>
typedef long long ll;
using std::min; using std::max;
#define INF 1e18
#define pE() puts("")
#define W(x) write(x)
#define rd() read<ll>()
#define lowbit(x) -x & x
#define pS() putchar(' ')
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
    T x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x / 10) write(x / 10);
    putchar((x % 10) ^ 48);
}
int T, l, r, k;
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    T = rd();
    while (T --) {
        l = rd();
        r = rd();
        k = rd();
        int len = r - l + 1;
        int sum;
        if (len == 1) {
            if (l == 1)
                printf("NO\n");
            else
                printf("YES\n");
            continue;
        }
        else if (len % 2 == 0)
            sum = len / 2;
        else if (l % 2 == 0)
            sum = (len - 1) / 2;
        else
            sum = (len + 1) / 2;
        if (sum <= k)
            printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

 

T2MEX

　　对于一个可重非负整数集 S，MEX(S) 表示这个集合中，没有出现的最小非负整数。例如 MEX({0, 0, 1, 3}) = 2, MEX({0}) = 1, MEX({}) = 0。黑板上有 N 个非负整数，第 i 个非负整数为 Ai。

　　你需要做下列操作恰好 K 次：

　　　　• 从黑板上选择零个或者若干个数，设它们组成的可重非负整数集 S，你将在黑板上写上 MEX(S) 这个数。请求出最后黑板上留下的数字有多少种情况，两种情况不同当且仅当存在某一个数字在两种情况中出现次数不同，答案对 998244353 取模

　　我们只要先都插入 m，然后都插入 < m 的数，这样一定能得到所有最终可能集合，还不会算重。枚举插入了 i 次 m，当前 MEX 为 mi，答案为 ∑K i=0 (mi+K−i−1mi−1 ) 。

　　std：

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int INF=1e6+5;
const int Mod=998244353;
int n,k,a[INF],num[INF],fav[INF],ifav[INF];
int ksm(int x,int y) {
    int ba=x%Mod,ans=1;
    while (y) {
        if (y&1) ans=(ans*ba)%Mod;
        ba=(ba*ba)%Mod;y>>=1;
    }
    return ans;
}
void init() {
    fav[0]=1;int N=1e6;
    for (int i=1;i<=N;i++) fav[i]=fav[i-1]*i%Mod;
    ifav[N]=ksm(fav[N],Mod-2);
    for (int i=N-1;~i;i--) ifav[i]=ifav[i+1]*(i+1)%Mod;
}
int C(int x,int y) {
    if (x<y) return 0;
    return fav[x]*ifav[y]%Mod*ifav[x-y]%Mod;
}
signed main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>k;int kk=k;init();
    for (int i=1;i<=n;i++) cin>>a[i],num[a[i]]++;
    int ans=0;
    for (int i=0;i<=5e5;i++) {
        int fl=0;
        if (!num[i]) {kk--;fl=1;}
        if (kk<0) break;
        if (fl) ans+=C(kk+i,i),ans%=Mod;
        else ans+=(C(kk+i,i)-C(kk+i-1,i-1))%Mod,ans%=Mod;
    }
    ans%=Mod;ans+=Mod;ans%=Mod;
    cout<<ans<<"\n";
    return 0;
}

T3XOR

　　

　　有一个长度为 N 的二元组序列 ((A1, B1),(A2, B2), . . . ,(AN , BN ))。 　　你需要进行 N/2 次删除操作将整个序列删空。对于每次删除操作，你需要选择一对相邻的二元组，将它们从序列中移除，再将前后的序列拼接成一个序列。 　　要求对于删除的每对二元组 (Ax, Bx),(Ay, By) (x < y) 中，都满足要求: 　　　　• Ax xor By = Bx xor Ay 　　　　• Ax + Bx ≤ K

　　不考虑第二个要求用队列模拟有80分，考虑正解，现在对于每个括号可以任意作为左括号或右括号，那么可以贪心地进行多种类括号匹配：

　　　　• 维护一个栈，按 i = 1, 2, . . . , N 的顺序每次往栈顶放入 Ai xor Bi。 　　　　• 每次放入元素后，如果栈顶两个元素相同，那么同时将它们弹出栈。 　　Cx = 0 的条件，可以看作是若 Ci = 1，那么这个元素被删除时只能在右边，也就是一定是右括号。现在一些括号可以自由定向，一些是右括号，从左往右扫似乎不好控制。此时我们从右往左扫，贪心地来说，对于一个右括号，扫到左边第一个可匹配的就匹配一定最优

　　std：

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int INF=1e6+5;
int n,a[INF],k,b[INF],c[INF],d[INF],q[INF];
void solve() {
    cin>>n>>k;int r=0;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) cin>>b[i];
    for (int i=n;i;i--) {
        c[i]=a[i]^b[i];
        d[i]=a[i]+b[i];
    }
    r=0;
    for (int i=n;i;i--) {
        // if (n==4)
        //     cerr<<c[q[r]]<<" "<<d[i]<<" ok?\n";
        if (c[q[r]]==c[i] && r && d[i]<=k) r--;
        else q[++r]=i;
    }
    // for (int i=1;i<=r;i++)
    //     cerr<<q[i]<<" ";
    // cerr<<" endl\n";
    if (r) cout<<"YES\n";
    else cout<<"NO\n";
}
signed main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=0;cin>>t;
    while (t--) solve();
    return 0;
}

T4RAY

　　Era 在一个大小为 H × W 的矩阵中，矩阵第 i 行第 j 列的格子坐标为 (i, j)。 　　有 Q 束射线穿过矩阵，第 i 束射线可由三个整数 Ti , Di , Xi 表示，意义如下： 　　　　• 这束射线在第 Ti 秒时出现，然后立即消失。 　　　　• 当 Di = 0 时，这束射线恰好竖直穿过第 Xi 列的所有格子。 　　　　• 当 Di = 1 时，这束射线恰好水平穿过第 Xi 行的所有格子。 　　被射线击中可不妙，Era 需要在矩阵中移动来躲避射线。Era 每一次可以向上下左右移动一格，具体地，一次移动规则如下： 　　　　• Era 当前所在坐标为 (x, y)。 　　　　• 若 (x − 1, y) 在矩阵内，Era 可以选择移动到 (x − 1, y)。 　　　　• 若 (x + 1, y) 在矩阵内，Era 可以选择移动到 (x + 1, y)。 　　　　• 若 (x, y − 1) 在矩阵内，Era 可以选择移动到 (x, y − 1)。 　　　　• 若 (x, y + 1) 在矩阵内，Era 可以选择移动到 (x, y + 1)。 　　　Era 可以在一秒钟移动任意次数（也可以不移动），被击中当且仅到 Era 在某束射线出现时，正好位于这束射线穿过的行或列中。Era 最初所在矩阵中的位置可以自由选择，请求出 Era 全避射线最少需要移动多少次。

　　　我们可以按照时间从后往前 DP，设第 i 秒在第 j 格在之后还需移动 fi,j 次，对于每个状态暴力枚举其它所有的格子转移，时间复杂度 O(|Ti |(N2 + M2 ))。实际上，对于每个格子，只需对左右两边最近的下一秒不会被射线击中的格子转移即可，可以简单用反证法证明，然而总的有用转移数是 O(Q) 的，所以我们不需要记录时间这一维状态，每次将当前秒每段连续射线所包含的格子转移即可

　　std：

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int INF=1e6+5;
struct P3 {
    int t,d,x;
}aa[INF];
int n,m,f[INF],vis[INF],q,sum;
signed main()
{
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1;i<=q;i++) 
        cin>>aa[i].t>>aa[i].d>>aa[i].x;
    sort(aa+1,aa+1+q,[](P3 xx,P3 yy){return xx.t<yy.t;});
    for (int i=1;i<=m;i++) f[i]=0;
    int la=0;
    for (int t=1;t<=1e5;t++) {
        int j=la;vis[0]=0;
        while (aa[j+1].t==t && j+1<=q) {
            j++;
            if (aa[j].d==1) vis[++vis[0]]=aa[j].x;
        }
        sort(vis+1,vis+1+vis[0],[](int x,int y){return x<y;});
        for (int k=1;k<=vis[0];k++) {
            int r=k;
            while (vis[r+1]==vis[r]+1 && r+1<=vis[0]) r++;
            int Min=1e18;
            for (int l=k;l<=r;l++) 
                Min=min(Min,f[vis[l]]-vis[l]);
            f[vis[r]+1]=min(f[vis[r]+1],vis[r]+1+Min);
            Min=1e18;
            for (int l=r;l>=k;l--)
                Min=min(Min,f[vis[l]]+vis[l]);
            f[vis[k]-1]=min(f[vis[k]-1],Min-(vis[k]-1));
            for (int l=k;l<=r;l++)
                f[vis[l]]=1e18;
            k=r;
        }
        la=j; 
    }

    int res=1e18;
    for (int i=1;i<=m;i++) res=min(res,f[i]);
    sum+=res;

    swap(n,m);
    for (int i=1;i<=q;i++) aa[i].d^=1;
    for (int i=1;i<=m;i++) f[i]=0;
    la=0;
    for (int t=1;t<=1e5;t++) {
        int j=la;vis[0]=0;
        while (aa[j+1].t==t && j+1<=q) {
            j++;
            if (aa[j].d==1) vis[++vis[0]]=aa[j].x;
        }
        sort(vis+1,vis+1+vis[0],[](int x,int y){return x<y;});
        for (int k=1;k<=vis[0];k++) {
            int r=k;
            while (vis[r+1]==vis[r]+1 && r+1<=vis[0]) r++;
            int Min=1e18;
            for (int l=k;l<=r;l++) 
                Min=min(Min,f[vis[l]]-vis[l]);
            f[vis[r]+1]=min(f[vis[r]+1],vis[r]+1+Min);
            Min=1e18;
            for (int l=r;l>=k;l--)
                Min=min(Min,f[vis[l]]+vis[l]);
            f[vis[k]-1]=min(f[vis[k]-1],Min-(vis[k]-1));
            for (int l=k;l<=r;l++)
                f[vis[l]]=1e18;
            k=r;
        }
        la=j; 
    }

    res=1e18;
    for (int i=1;i<=m;i++) res=min(res,f[i]);
    sum+=res;

    if (sum>1e17) cout<<"-1\n";
    else cout<<sum<<"\n";
    return 0;
}

 

标签：std,vis,int,6.30,Era,2023,INF,集训,define
From： https://www.cnblogs.com/determination/p/17521336.html

相关文章

  • 【总结】2023暑期集训 宋知渔的个人总结（2023-07-02更新）
    2023暑期集训宋知渔的个人总结博客食用效果更佳2023/07/02个人总结今日AC题目#148.高精度除法（高精/高精）#15.HelloWorld今日好题分享#148.高精度除法（高精/高精）今日学习了\(\operatorname{python}\)相关知识，能够完成此类题目。今日趣事竟然有人以为我是女的。......
  • 2022-2023 春学期 矩阵与数值分析 考试的范围
    2022-2023春学期矩阵与数值分析考试的范围原文考试的范围......
  • 2023/7/2
    21.7例3......
  • 2023年暑假集训总结/6.29
    6-27T1有毒爱排列有毒让你求长度为n且逆序对个数对p取余为k的排列的个数，答案对998244353取模。考试时我考虑到设fi,j表示放了数1∼i，此时逆序对个数modp=j的排列个数。转移显然，枚举i+1放到哪个位置即可，时间复杂度O(n^2p)。得了60分，而后通过观察性......
  • 2023年暑假集训总结/6.27
    6-27T1图一姬在一个n个点和m条边无向图中迷路了，她不知道她现在在哪里。每个点上有一个宝玉，一姬要收集k个宝玉才能缔结契约，走出这个无向图。图中被访问的点不能再访问第二次，经过每条边需要一定的时间，求所需的最大时间是多少？注:走到的点宝玉必须要取走。收集到k个宝......
  • P9381 [THUPC 2023 决赛] 那些脑海里最珍贵的
    小清新大模拟（？写起来挺顺的，就是浮点误差那块整破防了，最后问了神虎用了科学计数法存浮点数才过stO神虎Orz坑点：注意精度误差死亡后要清除Average的主动技能，防止重复触发死亡处理导致被动技能被弄乱Average的主动技能里的“\(3\)个回合”指的是南北两边各行动一次算一......
  • 2023年暑假集训总结/6.26
    6-26T1粉丝问我ctrl键在哪里励志阿伟现在正处在一个冰火迷宫中，迷宫由n个格子组成，每个格子要么是冰之格，要么是火之格，励志阿伟刚开始可以选择从迷宫中任意一个开始走，走到第i个位置时会得到值为ai的积分。如果励志阿伟当前在冰之格，那么他可以选择一个编号大于当前格子的......
  • 2023 冲刺国赛自测 9
    轻度的断食似乎对精神状态有好处。不过相比两年前还是吃的多些。两年前今天中午吃的一点东西是我当时一天的量。T3我会60的部分分，但是没写。问就是正解忘了板子怎么打。不如直接脖子右拧。晚上又没吃饭，感觉精神状态好了一些。明天早上得吃了，再不吃按照经验我妈得找我了。但......
  • C/C++职员薪资查询系统[2023-07-02]
    C/C++职员薪资查询系统[2023-07-02]数据结构与算法程序设计职员薪资查询系统1项目要求项目名称 职员薪资查询系统 项目类型 应用软件类项目难度 中等 素材资源 无（../res）使用工具 不限 编译系统 Windows、Linux硬件需求 无 程序语言 不限知识点 结构体/类、树、图、链表、......
  • 2023/7/2
    今天学习了两种类型转换，首先是向上转型，就是用父类的对象来引用子类，这种转型是安全的，注意父类的对象不能访问子类中的属性和方法。然后是向下转型，这种转型是不安全的，父类对象不能直接赋值给子类对象，要实现向下转型需要借助强制类型转换:子类类型子类对象=(子类类型)父类对象。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99