首页 > 其他分享 >[42] (多校联训) A层冲刺NOIP2024模拟赛03

[42] (多校联训) A层冲刺NOIP2024模拟赛03

时间：2024-10-07 20:21:47浏览次数：8  
标签：03 freopen int 42 pos long 联训 401 区间

今天的乐子

今天的乐子2

昨天晚上做梦

梦见自己被关进戒网瘾学校

里面的老师全和疯子一样

然后我和这帮疯子老师比疯

疯子老师发现他们没我疯

所以就把我放了

今天的乐子3

lhx 罗曼蒂克的辟谷

A.五彩斑斓

赛时的想法

\(n^4\) 的做法，设 \(f_{i,j,k,l}\) 表示以 \((i,j)\) 为左上角，右下角不超过 \((k,l)\) 的矩阵的个数和

\[f_{i,j,k,l}=f_{i,j,k-1,l}+f_{i,j,k,l-1}-f_{i,j,k-1,l-1}+judge_{i,j,k,l} \]

观察到可以直接开桶，把第四维压掉

然后就变成 \(n^3\) 的了

但是我正确性出问题了，不知道哪有问题，有大佬可以指一下思路上的问题

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n,m;
int a[401][401];
long long f[401][401];
long long  samecnt[401][401];
map<int,int>mp;
int cnt=0;
bool check(int xa,int ya,int xb,int yb){
    int tmp1=a[xa][ya],tmp2=a[xa][yb],
        tmp3=a[xb][ya],tmp4=a[xb][yb];
    return !(tmp1==tmp2 and tmp2==tmp3 and tmp3==tmp4);
}
signed main(){
    freopen("colorful.in","r",stdin);
    freopen("colorful.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&a[i][j]);
            if(!mp.count(a[i][j])){
                mp[a[i][j]]=++cnt;
            }
            a[i][j]=mp[a[i][j]];
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=1;k<=cnt;++k){
                samecnt[j][k]&=0;
            }
        }
        for(int j=1;j<=m;++j){
            f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1];
            for(int sti=1;sti<=i;++sti){
                if(a[sti][j]==a[i][j]){
                    samecnt[sti][a[i][j]]++;
                    f[i][j]+=j-samecnt[sti][a[i][j]];
                }
                else f[i][j]+=j;
            }
        }
    }
    cout<<f[n][m]<<endl;
}

题解的思路是类似的，正难则反，考虑求顶点全相同的矩形个数，\(n^4\) 的做法就更简单了，直接枚举顶点就行了

所以有人直接用 bitset 草过去了

实际上可以对值域开桶

假设我们已经知道了矩形的右边两个点（可以通过分别枚举上边界，右边界和下边界来 \(n^3\) 得到），那么我们有如下两个结论

  • 已知的两个点不一致时不存在解
  • 考虑下边界这一行，设 \(cnt_{a_{rd}}\) 表示在该行下标小于等于矩形右下角的节点中，值和右下角顶点相同，且与对应上边界节点值相同的节点数量，则该点答案即为 \(cnt_{a_{rd}}\)

如果难理解可以画图理解

图

瓶颈在清空，出题人你没有心

#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt[1000001],a[401][401];
long long ans;
int main(){
    freopen("colorful.in","r",stdin);
    freopen("colorful.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){
            for(int k=1;k<=m;++k){
                if(a[i][k]==a[j][k]){
                    cnt[a[i][k]]++;
                    ans+=cnt[a[i][k]];
                }
            }
            for(int k=1;k<=m;++k){
                if(a[i][k]==a[j][k]){
                    cnt[a[i][k]]=0;
                }
            }
        }
    }
    cout<<n*(n+1ll)*m*(m+1)/4-ans;
}

B.错峰旅行

结论题

结论

  • 如果有一段连续的长度为 \(l\) 的时间段，满足该时间段内不存在状态改变的城市，且状态为不拥挤的城市有 \(x\) 个，则对方案数的贡献（乘）为 \(x^l\)

所以这是一个离散化板子题

  • 把所有坐标离线下来做离散化（注意开始结尾也要插进去离散化），然后因为对于区间 \([l,r]\)，是 \(r+1\) 才更新状态，所以应该插入 \(l,r+1\)
  • 开双指针对坐标扫一遍，另一个扫操作，记一下这个是状态加还是状态减，直接统计答案就行了

不明白 STD 开牛魔的差分，题目里不是保证了区间不重叠了吗

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int power(int a,int t){
    int base=a,ans=1;
    while(t){
        if(t&1){
            ans=ans*base%p;
        }
        base=base*base%p;
        t>>=1;
    }
    return ans;
}
int n,m,s,t;
struct ope{
    int id,pos;
    bool isadd;
    bool operator <(const ope &A)const{
        if(A.pos==pos) return isadd<A.isadd;
        return pos<A.pos;
    }
};
int sum[1000001];
vector<ope>op={{}};
map<int,int>mp;
int pos[4000001];
int cnt=0,cnt2=0;
signed main(){
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
    for(int i=1;i<=m;++i){
        int x,l,r;
        scanf("%lld %lld %lld",&x,&l,&r);
        op.push_back({x,l,true});
        op.push_back({x,r+1,false});
        pos[++cnt2]=l;
        pos[++cnt2]=r+1;
    }
    pos[++cnt2]=s;
    pos[++cnt2]=t+1;
    sort(op.begin(),op.end());
    sort(pos+1,pos+cnt2+1);
    cnt2=unique(pos+1,pos+cnt2+1)-pos-1;
    long long lsum=1,nsum=0;
    long long lnum=n,nnum=0;
    for(int i=1,j=0;i<cnt2;++i){
        nsum=0;
        nnum=lnum;
        while(j<2*m and op[j+1].pos<=pos[i]){
            j++;
            int x=op[j].id;
            int d=(op[j].isadd?1:-1);
            if(sum[x]>0 and sum[x]+d<=0) ++nnum;
            else if(sum[x]<=0 and sum[x]+d>0) --nnum;
            sum[x]+=d;
        }
        assert(pos[i+1]-pos[i]>=0);
        nsum=lsum*power(nnum,pos[i+1]-pos[i])%p;
        lsum=nsum;
        lnum=nnum;
    }
    cout<<nsum;
}

C.线段树

考虑一个询问区间 \([l,r]\) 的贡献，发现至少有 \(1\) 的贡献

抛开这个 \(1\) 不谈，剩下的贡献都是通过如下方式增加的

  • 线段树存在一个子区间，使得两个区间有交集且不包含

因此区间 DP，设 \(f_{i,j}\) 表示区间 \([i,j]\) 划分后的最小新增贡献

\[f_{i,j}=\min_{k}f_{i,k}+f_{k+1,j}+cost \]

所以计算本层贡献即可

关于本层贡献的计算，可以分别统计有多少区间与当前区间有交，有多少区间被当前区间包含，直接减掉就行了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define r l+len-1
int n,qq;
int w[501];
int num[501][501];
int f[501][501];
signed main(){
    freopen("segment.in","r",stdin);
    freopen("segment.out","w",stdout);
    cin>>n>>qq;
    for(int i=1;i<=qq;i++){
        int _l,_r;
        scanf("%lld %lld",&_l,&_r);
        num[_l][_r]++;
        w[_l]++;w[_r]--;
    }
    for(int i=1;i<=n;i++){
        w[i]+=w[i-1];
    }
    for(int len=n-1;len>=1;len--){
        for(int l=1;r<=n;l++){
            num[l][r]=num[l][r]+num[l-1][r]+num[l][r+1]-num[l-1][r+1];
        }
    }
    for(int len=2;len<=n;len++){
        for(int l=1;r<=n;l++){
            f[l][r]=LLONG_MAX;
            for(int k=l;k<r;k++){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+(w[k]-num[l][r]));
            }
        }
    }
    cout<<f[1][n]+qq<<'\n';
}

标签：03,freopen,int,42,pos,long,联训,401,区间
From： https://www.cnblogs.com/HaneDaCafe/p/18450497

相关文章

  • P8531 [Ynoi2003] 戌亥彗星
    特殊性质实际上就是保证了所有环外点度数都\(\le2\)，这样就只需要考虑前两个条件。注意到对于一个\(i\)，假设\(i\)为区间左端点，那么所有满足条件\(2\)的右端点构成一个区间，记为\(l_i,r_i\)，且满足\(l_i\lel_{i+1},r_i\ler_{i+1}\)。而且这些区间有更强的性质：如果\(l_i<l_......
  • 多校A层冲刺NOIP2024模拟赛03 -- T4 量子隧穿问题
    多校A层冲刺NOIP2024模拟赛03--T4量子隧穿问题$$HZOI$$感觉是这两天最有意义的题吧。\(n\)句话题意我是巴甫洛夫的狗，我又重生了，重生在薛定谔的家里。薛定谔是抖S，于是给我铃声。我开始狂跑不止。为什么没流口水没删除我给定\(n\)个点，对于\(i\)存在一条外向连的单向......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛03
    Rank炸了，触底反弹A.五彩斑斓（colorful）签，又没签上。考虑如何一步步优化暴力。最暴力的思想\(\mathcal{O(n^4)}\)枚举每个矩形，判断四个顶点颜色。稍微优化些，两次\(\mathcal{O(n^2)}\)跑出对于行/列每个点下一个与之颜色相同的坐标，利用容斥全部减去不合法的方案数，然后再枚......
  • CSP 联训 3
    好吧，又倒数了，就签了个T2，100pts。T1我把相同颜色的存起来，每种颜色找出枚举选哪两个座位不合法的矩阵的左上和右下，如果找到的矩阵左下和右上也相同，则这个矩阵确实不合法，减去，但判断左下和右上的时候写的太急（最后十五分钟才开始打这个暴力）少判了和当前颜色是否相同，挂了80pts，！总......
  • CSP2024 前集训：多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反，脑瘫了没敢用bitset（复杂度擦边但卡常能过），T2空间开大了挂了\(100pts\)，\(T3\)是原。T1五彩斑斓部分分\(20pts\)：\(O(n^4)\)暴力。部分分\(20+?pts\)：进行一些优化，极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\)：bitset优化一下，\(O(\f......
  • 多校A层冲刺NOIP2024模拟赛03
    多校A层冲刺NOIP2024模拟赛03还有一个半小时结束才来，题基本没打，全口胡。T1五彩斑斓（colorful）直接统计答案难做，考虑统计四个顶点都一样的。知道\(n\)行\(m\)列的矩阵有\(\frac{n\times(n+1)\timesm\times(m+1)}{4}\)个子矩阵，这个想成选择矩阵的边界就可以证明。如何统计四......
  • ETC2420 / ETC5242 Statistical Thinking
    StatisticalThinking(ETC2420/ETC5242)Assignment1Semester2,2024InstructionsThisassignmentisagroupassignment.Onlyonesubmissionforeachgroupisrequired.Allgroupsaretodoalltasksinthisassignment,regardlessofyourunitcode.Eff......
  • 多校 A 层冲刺 NOIP2024 模拟赛 03
    多校A层冲刺NOIP2024模拟赛03T1五彩斑斓（colorful）签到题直接暴力枚举是\(O(n^4)\)，考虑使用\(bitset\)优化，对每个点开个\(bitset\)，预处理它所在一行它及它之前相同颜色的位置，这样就只用枚举另一个点所在列，时间复杂度为\(O(n^3+\frac{n^4}{w})\)。T2错峰旅行（travel）......
  • 网站403forbidden怎么解决
    遇到“403Forbidden”错误通常表示服务器拒绝了请求访问某个资源。解决这个问题可以从以下几个方面入手：1.检查权限设置服务器文件权限：确认服务器上的文件和目录权限是否正确。通常文件权限应为 644，目录权限应为 755。使用命令 chmod 和 chown 调整权限：sudochm......
  • 信息学奥赛复赛复习14-CSP-J2021-03网络连接-字符串处理、数据类型溢出、数据结构Map
    PDF文档公众号回复关键字:202410071P7911[CSP-J2021]网络连接[题目描述]TCP/IP协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99