首页 > 其他分享 >NOIP2024加赛4

NOIP2024加赛4

时间:2024-11-11 18:08:28浏览次数:4  
标签:read second long int lst using 加赛 NOIP2024

简评:搬的梦熊的,一签一难两不可做。

王国边缘

倍增板子(但我不会打倍增所以场上调了半天)。

记\(f_{i,j}\)表示从\(i\)开始走\(2^j\)次时走的距离,\(g_{i,j}\)表示从\(i\)开始走\(2^j\)次时走到的点,这个用倍增。

处理\(f_{i,0}\)和\(g_{i,0}\)时分讨即可,卡不卡常无所谓。时空复杂度\(O(n\log K)\)。

也有基环树上跑倍增/\(O(1)\)求答案的,分别为\(O(n\log n)/O(n)\)。

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
    FILE *InFile = stdin,*OutFile = stdout;
    // FILE *InFile = freopen("kingdom.in","r",stdin),*OutFile = freopen("kingdom.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
    #define pc putchar_unlocked
    template<class T>
    inline void read(T &x){
        x = 0;char s = gc();
        for(;s < '0' || s > '9';s = gc());
        for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
    }
    inline void read(char &x){x = gc();}
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
    template<class T>
    inline void write(T x){
        static int sta[20],top = 0;
        do{sta[++top] = x%10,x /= 10;}while(x);
        do{pc(sta[top--]+'0');}while(top);
    }
    inline void write(char x){pc(x);}
    template<class T,class... Args>
    inline void write(T x,Args... argc){write(x);write(argc...);}
}using namespace IO;
#define int long long
const int N = 2e5 + 10,mod = 1e9 + 7;
int n,m,q,lst[N];
char s[N];
#define pii pair<int,int>
#define mk make_pair
pii f[N][65];
inline void solve(){
    read(n,m,q);
    rep(i,1,n,1) read(s[i]);
    drep(i,n,1,1) if(s[i] == '1'){lst[1] = i;break;}
    if(s[1] == '1') lst[1] = 1;
    rep(i,2,n,1){
        if(s[i] == '1') lst[i] = i;
        else lst[i] = lst[i-1];
    }
    rep(i,1,n,1){
        int to = i+m;
        to = to%n;
        if(!to) to = n;
        if(!lst[to]){
            f[i][0] = mk(1,i+1);f[i][0].second%=n;
            if(!f[i][0].second) f[i][0].second = n;
            continue;
        }
        if(lst[to] > to){
            int k = m/n;
            if(k < 0) f[i][0] = mk(1,i+1);
            else if((m-(to+n-lst[to])) > 0) f[i][0] = mk((m-(to+n-lst[to]))%mod,lst[to]);
            else f[i][0] = mk(1,i+1);
            f[i][0].second%=n;
            if(!f[i][0].second) f[i][0].second = n;
        }
        else{
            int k = m/n;
            if(k < 0) f[i][0] = mk(1,i+1);
            else if(m-(to-lst[to]) > 0) f[i][0] = mk((m-(to-lst[to]))%mod,lst[to]);
            else f[i][0] = mk(1,i+1);
            f[i][0].second%=n;
            if(!f[i][0].second) f[i][0].second = n;
        }
    }
    rep(i,1,59,1) rep(j,1,n,1){
        f[j][i] = mk((f[j][i-1].first+f[f[j][i-1].second][i-1].first)%mod,
                    f[f[j][i-1].second][i-1].second);
    }
    while(q--){
        int s,k;;read(s,k);
        int ans = s%mod;s %= n;if(!s) s = n;
        drep(i,59,0,1){
            if((k>>i)&1){
                ans = (ans + f[s][i].first)%mod;
                s = f[s][i].second;
            }
        }
        write(ans,'\n');
    }
}
signed main(){
    // cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

买东西题

反悔贪心板子。

考虑一个物品被购买时,有三种情况。

  1. 使用折扣价。
  2. 使用一个尚未使用的优惠券。
  3. 抢了前面一个已经使用过的优惠券,并让其以折扣价的价格购买。

发现第1种情况只有没有可以使用的优惠券或者折扣价比使用最大的可以使用的优惠券更优。

第2种情况直接用一个堆维护优惠券即可。

考虑第3中情况,假如当前要选择\(i\),抢的\(j\)的价值为\(v\)优惠券更优。那么有\(a_i-v-(a_j-v)+b_j=a_i-(a_j-b_j)\)。所以这就等价于如果\(j\)用了优惠券,那么就给后面的物品一个价值为\(a_i-a_j\)的优惠券。

时间复杂度\(O(n\log n)\)。

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
// using namespace __gnu_pbds;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
    FILE *InFile = freopen("buy.in","r",stdin),*OutFile = freopen("buy.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() ((p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<23,stdin),p1 == p2))?EOF:*p1++)
    template<class T>
    inline void read(T &x){
        x = 0;char s = gc();
        for(;s < '0' || '9' < s;s = gc());
        for(;'0' <= s && s <= '9';s = gc()) 
            x = (x<<1) + (x<<3) + (s^48);
    }
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
}using namespace IO;
#define pii pair<int,int>
#define mk make_pair
const int N = 1e6 + 10;
pii a[N],b[N];
int n,m;
inline void solve(){
    read(n,m);
    rep(i,1,n,1) read(a[i].first,a[i].second);
    rep(i,1,m,1) read(b[i].first,b[i].second);
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    priority_queue<int> q;int now = 0;ll ans = 0;
    rep(i,1,n,1){
        while(now < m && b[now + 1].first <= a[i].first) now++,q.push(b[now].second);
        if(q.empty() || a[i].first - a[i].second > q.top()) ans += a[i].second;
        else ans += a[i].first-q.top(),q.pop(),q.push(a[i].first - a[i].second);
    }
    cout<<ans;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

IMAWANOKIWA (Construction ver.)

超长分讨等你来写!!!

魔法少女们

不会格路计数,滚去看这玩意了。

p

image

image

标签:read,second,long,int,lst,using,加赛,NOIP2024
From: https://www.cnblogs.com/hzoi-Cu/p/18540286

相关文章

  • NOIP2024加赛4
    NOIP2024加赛4\(T1\)luoguP11267【MX-S5-T1】王国边缘\(85pts\)预处理前缀中最后一个\(1\)出现的位置然后就可以倍增跳了。点击查看代码constllp=1000000007;intnxt[200010][62],f[200010][62],last[200010];chart[200010];lldivide(lls,llk){llan......
  • 多校A层冲刺NOIP2024模拟赛20
    多校A层冲刺NOIP2024模拟赛20昨天晚上打ABC了,所以今天才发。T1星际联邦直接上菠萝(Borůvka)算法就行了,当然还可以用线段树优化prim算法,但是没打过只是口胡:就是维护当前的连通块,但一个点$i$加入连通块时,后面那些点就可以有$a_j-a_i$的贡献,前面的点可以有$a_i-......
  • NOIP2024(欢乐)加赛3
    NOIP2024(欢乐)加赛3\(T1\)CF2033BSakurakoandWater\(100pts\)枚举主对角线取\(\max\)即可。点击查看代码lla[510][510];intmain(){ llt,n,ans=0,maxx,i,j,k,h; cin>>t; for(h=1;h<=t;h++) { cin>>n; ans=0; for(i=1;i<=n;i++) { for(......
  • [赛记] 多校A层冲刺NOIP2024模拟赛20
    星际联邦80pts前连20条,后连20条80pts。。。考虑正解,发现向前连最大,向后连最小会出现重边,所以避免出现这种情况,我们只需要在做完向前连最大以后,在向后连最小的时候连不是同一个连通块的即可;时间复杂度:$\Theta(n\logn)$,瓶颈在排序;其实这个思想就是最小生成树的那个BUA算法......
  • 『模拟赛』NOIP2024(欢乐)加赛3
    Rank真欢乐吗,不过missionaccomplished.A.SakurakoandWaterCF2033B*900byd还懂难易搭配,不过这个b翻译甚至不着重以下主对角线差评,被硬控半个小时,直到手模样例才发觉不对。读懂题就很简单了,最优一定是找最长的对角线每次加,一共只有\(2n-1\)条线,枚举一下求出每条......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛20
    RankmissionfailedA.星际联邦由于急着想切题,上来没细看就打了个树状数组上去,果然寄了,然后又各种方式优化,最终还是寄了,只有50pts。正解是学最小生成树时直接跳过的prim和菠萝,但是偏不这么做,而是找性质得出严格\(\mathcal{O(n)}\)的做法。首先比较平凡发现一个点的最......
  • 多校A层冲刺NOIP2024模拟赛20
    多校A层冲刺NOIP2024模拟赛20\(T1\)A.星际联邦\(25pts\)部分分\(25pts\):暴力建边后跑\(Kruskal\)或\(Prim\)。点击查看代码structnode{ intfrom,to,w;};inta[300010];vector<node>e;structDSU{ intfa[300010]; voidinit(intn) { for(inti......
  • 多校A层冲刺NOIP2024模拟赛20
    简评:新拉的......
  • 【题解】「NOIP2024模拟赛24 T3」钙绿
    【题解】「NOIP2024模拟赛24T3」钙绿https://www.becoder.com.cn/contest/5715/problem/3\(\mathcal{Description}\)给定\(n,p,m\)。对于每个\(k=0,1,\dots,m\),统计满足下面条件的\(n\)位\(10\)进制数:(允许前导零各位数之和不超过\(k\)。\(p\)能整除这个数。数据......
  • 【题解】「NOIP2024模拟赛24 T2」子序列们
    【题解】「NOIP2024模拟赛24T2」子序列们https://www.becoder.com.cn/contest/5715/problem/2\(\mathcal{Description}\)给定一个0/1串\(a\),你需要生成一个长度为\(n\)的序列\(b\),其中\(b_i\)为\(a\)的一个子序列,且满足:\(|b_i|=n-i+1\);\(\foralli\in(1,n]\),\(b......