首页 > 其他分享 >暑假集训csp提高模拟3

暑假集训csp提高模拟3

时间:2024-07-20 21:30:00浏览次数:5  
标签:FILE int ll long 集训 暑假 using csp define

赛时 rank 20,T1 0,T2 45,T3 20,T4 95

T1粘了两遍(因为OJ卡第一次没有显示出来)CE了,挂了100,T4没卡常挂了5

汤碗了!!!!!!!!!!!!!!!

T1 abc猜想

对于任意整数\(c\)都有

\[\left\lfloor\frac{a}{b}\right\rfloor+c = \left\lfloor\frac{a}{b}+c\right\rfloor = \left\lfloor\frac{a+bc}{b}\right\rfloor \]

所以

\[\left\lfloor\frac{a^b}{c}\right\rfloor = kc+ans \]

\[ans = \left\lfloor\frac{a^b-kc^2}{c}\right\rfloor = \left\lfloor\frac{a^b\,mod\,c^2 }{c}\right\rfloor \]

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
ll a,b,c;
inline ll power(ll a,ll b,ll mod){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a*a%mod;
    }
    return res;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>a>>b>>c;
    cout<<power(a,b,c*c)/c<<'\n';
}

死亡回放

image

image

T2 简单的排列最优化题

\(O(n)\)做法

将排列中的数分为两类,\(\pi_i>i\),\(\pi_i\le i\)

记第一类的总数为\(zcnt\),贡献为\(ztot\);

记第二类的总数为\(fcnt\),贡献为\(ftot\)。

除了放到队首的数,第一类数做出的贡献和减掉\(zcnt\),第二类数做出的贡献和加上\(fcnt\)

当一个数从第一类数变为第二类数时,那么有\(\pi_i-i=0\),预处理每个数变化的时间即可。

第二类数变成第一类数时,只能是是队尾变队首,特判。

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
const int N = 1e7 + 10;
int n,zcnt,fcnt,a[N],Z[N];
ll ztot,ftot;
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    for(int i = 1;i <= n; ++i){
        if(a[i] <= i) fcnt++,ftot += i-a[i];
        else zcnt++,ztot+=a[i]-i,Z[a[i]-i]++;
    }
    ll ans = ztot+ftot,id = 0;
    for(int i = 1;i < n; ++i){
        ztot -= zcnt;
        zcnt -= Z[i];
        ftot += fcnt;
        fcnt += Z[i];
        int x = a[n - i + 1];
        ftot -= n+1-x,--fcnt;
        if(x > 1) Z[x-1+i]++,ztot+= x-1,++zcnt;
        else ++fcnt;
        if(ans > ftot + ztot) ans = ftot+ztot,id = i;
    }
    cout<<ans<<' '<<id<<'\n';
}

T3 简单的线性做法题

小清新的分治做法

区间\([l\sim r]\)的绝对众数\(x\)(即出现次数大于\(\frac{len}{2}\)的众数)满足对于任意的\(l\le k\le r\),\(x\)一定为区间\([l\sim k]\)\((k\sim r]\)的绝对众数。利用这一性质分治,\(O(n)\)从mid出发扫描能够成为众数的数。

枚举众数\(x\),求当前区间中的满足绝对众数为\(x\)的子区间个数。

先从mid开始向左扫描左端点\(b\),记录\(mid-b+1-cnt_x\)不同取值的个数。
再向右扫描右端点\(e\),求满足\(e-b+1-cnt_x > \left\lfloor\frac{e-b+1}{2}\right\rfloor\)的\([b\sim e]\)个数。

时间复杂度\(O(n\log^2n)\)

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
const int N = 5e5 + 10;
int n,a[N],pos[N],num[N],cnt[N*2];
ll ans;
void solve(int l,int r){
    if(l == r) {ans++;return;}
    int mid = (l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    for(int i = mid;i >= l;--i){
        if(++cnt[a[i]] > (mid - i + 1)/2){
            if(!pos[a[i]]) num[pos[a[i]] = ++num[0]] = a[i];
        }
    }
    for(int i = mid+1;i <= r;++i){
        if(++cnt[a[i]] > (i - mid)/2){
            if(!pos[a[i]]) num[pos[a[i]] = ++num[0]] = a[i];
        }
    }
    for(int i = l;i <= r; ++i) pos[a[i]] = cnt[a[i]] = 0;
    for(int i = 1;i <= num[0]; ++i){
        int sum = r-l+1,mx = sum,mn = sum;
        cnt[sum] = 1;
        for(int j = l;j < mid; ++j){
            if(a[j] == num[i]) sum++;
            else sum--;
            mx = max(mx,sum);
            mn = min(mn,sum);
            cnt[sum]++;
        }
        if(a[mid] == num[i]) sum++;
        else sum--;
        for(int j = mn;j <= mx; ++j) cnt[j] += cnt[j - 1];
        for(int j = mid+1;j <= r; ++j){
            if(a[j] == num[i]) sum++;
            else sum--;
            ans += cnt[min(mx,sum-1)];
        }
        for(int i = mn;i <= mx; ++i) cnt[i] = 0;
    }
    num[0] = 0;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n;int x;cin>>x;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    solve(1,n);
    cout<<ans;
}

T4 简单的线段树题

n很大,分块无法过,线段树维护就可以了,其他的和分块一样,卡卡常数。

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
const int N = 1e6 + 10;
inline void read(ll &x){
    x = 0;
    char s = getchar();
    for(;s<'0'||s >'9';s=getchar());
    for(;'0' <= s && s<='9';s=getchar()) x = (x<<1)+(x<<3)+(s^48);
}
ll n,m;ll a[N];
void write(ll x){
    if(x > 9) write(x/10);
    putchar(x%10+48);
}
struct Segment_Tree{
    struct segment_tree{
        int l,r,lazy,tot;ll sum;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define sum(x) tree[x].sum
        #define lazy(x) tree[x].lazy
        #define tot(x) tree[x].tot
    }tree[N<<2];
    inline void pushup(int k){
        sum(k) = sum(k<<1) + sum(k<<1|1);
        tot(k) = min(tot(k<<1),tot(k<<1|1));
    }
    inline void pushdown(int k){
        if(lazy(k)){
            int ls = k<<1,rs = k<<1|1;
            lazy(ls) += lazy(k);
            lazy(rs) += lazy(k);
            if(tot(ls) >= 6) tot(ls) = 6;
            else{
                tot(ls) += lazy(k);
                sum(ls) = 0;
                for(int i = l(ls);i <= r(ls); ++i) sum(ls) += a[i];
            }
            if(tot(rs) >= 6) tot(rs) = 6;
            else{
                tot(rs) += lazy(k);
                sum(rs) = 0;
                for(int i = l(rs);i <= r(rs); ++i) sum(rs) += a[i];
            }
            lazy(k) = 0;
        }
    }
    void build(int k,int l,int r){
        l(k) = l,r(k) = r;
        if(l == r)return sum(k) = a[l],void();
        int mid = (l+r)>>1;
        build(k<<1,l,mid);build(k<<1|1,mid+1,r);
        pushup(k);
    }
    void update(int k,int l,int r){
        if(tot(k) == 6) return;
        if(l <= l(k) && r(k) <= r){
            if(tot(k) == 6) return;
            tot(k)++;lazy(k)++;
            sum(k) = 0;
            for(int i = l(k);i <= r(k); ++i) sum(k) += (a[i] = sqrt(a[i]));
            return;
        }
        pushdown(k);
        int mid = (l(k) + r(k))>>1;
        if(l <= mid) update(k<<1,l,r);
        if(r > mid) update(k<<1|1,l,r);
        pushup(k);
    }
    ll query(int k,int l,int r){
        if(l <= l(k) && r(k) <= r) return sum(k);
        pushdown(k);
        int mid = (l(k) + r(k))>>1;
        ll res = 0;
        if(l <= mid) res += query(k<<1,l,r);
        if(r > mid) res += query(k<<1|1,l,r);
        return res;
    }
}T;
signed main(){
    read(n);
    for(int i = 1;i <= n; ++i) read(a[i]);
    T.build(1,1,n);
    read(m);
    int ttt = 0;
    while(m--){
        ll op,l,r;
        read(op),read(l),read(r);
        if(op == 0) T.update(1,l,r);
        else write(T.query(1,l,r)),puts("");
        // if(op) ttt++;
        // if(ttt == 141 && op) cerr<<l<<' '<<r<<'\n';
    }
}

标签:FILE,int,ll,long,集训,暑假,using,csp,define
From: https://www.cnblogs.com/hzoi-Cu/p/18313827

相关文章

  • 暑假集训记录
    这里记一些从7.15开始做的NOI篇或者让人眼前一亮的题目/trick。(哦,前面的题可能忘了某些细节了。)P3452求补图连通块个数。P4555首先看到回文串,先上马拉车。然后发现马拉车双回文不好做,考虑拆成两部分。大概就是维护一个以\(i\)为左端点/右端点的最长回文串。然后......
  • 暑假学习Java第三周
    通过本周的学习我认识到了自己有很多的不足与优点,优点是我能够把问题细化逐步分析,缺点是我的意志力不够坚定。我还了解了Java的三大特性包括:面向对象:Java是一种面向对象的编程语言,它允许程序员定义一系列关于对象和类的概念,并将这些概念作为编程的基本单位。在实际内容中,面向对象......
  • 2024 暑假友谊赛 2
    A题目链接思路:枚举每个十字中心点,合法就标记,最后若还剩下点没被标记就NO#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definePIIpair<int,int>constintN=1e6+5,mod=998244353,Mod=1e9+7;intdx[4]={-1,0,1,0};intdy[4......
  • 暑假第三周总结(7.15-7.20)
    这周做了什么继续学习JAVA,做出了城堡游戏点击查看代码//RoompackagecastleV3;importjava.util.HashMap;publicclassRoom{ privateStringdescription;privateHashMap<String,Room>exits=newHashMap<String,Room>();publicRoom(String......
  • 暑假集训CSP提高模拟3
    暑假集训CSP提高模拟3\(T1\)P117.abc猜想\(100pts\)原题:[ARC111A]SimpleMath2由题,有\(\dfrac{(a^{b}-a^{b}\bmodc)\bmodc^{2}}{c}\)即为所求。证明设\(\left\lfloor\dfrac{a^{b}}{c}\right\rfloor=\dfrac{a^{b}-a^{b}\bmodc}{c}=kc+r\),其中\(r......
  • 集训第二天
    ABCD HI题A-闰年展示Description输入x,y,输出[x,y] 区间中闰年个数,并在下一行输出所有闰年年份数字,使用空格隔开。Input输入两个正整数 ......
  • 2024 暑假友谊赛 2
    B.TilingChallenge1.我的方法是按顺序遍历,遇到'.'时就检查一下它的上下左右是不是都是点,如果都是点的话,标记这个点,把这个点和他上下左右都标记为‘?’,但是要加一个条件,如果‘.’的个数不是5的倍数就不符合题意,不加这个会wa37,我也不知道为什么#include<bits/stdc++.h>#defin......
  • P1407 [国家集训队] 稳定婚姻
    原题链接题解二分图,分为两类,一类是指向,一类是被指向在这里,只需要建立情人之间的边就行,因为找情人能否成功code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;vector<int>G[10000];intmatch[10000]={0};boolvis[10000]={0};booldfs(intnow)//......
  • 暑假集训CSP提高模拟2
    T1看到这时限和内存,连一个数组都开不下,更别说离散化了,考试的时候我用了一个栈来模拟,相同留、进,不同退,可以说是很接近正解了,但还是没继续往下想,也是爆零了。正解的思路很简单,这里引出一个概念,摩尔投票法,适用于超过半数(不能等于)的众数,可以在常数的空间下、\(O(n)\)的时间复杂度下......
  • 2024暑假集训测试6
    前言比赛链接。挂分挂的最多的一集。T1不知道摩尔投票,被2M内存限制卡死。T2赛时打了个很像正解的莫队,赛时出题人发现了之后现往里加hack,还一个捆绑里加一个,直接爆零了,我真的谢了,求求以后不要一个捆绑放一个hack了,给条活路吧。T3一眼看出线段树优化建图,但是不会打......