首页 > 其他分享 >20241002 模拟赛

20241002 模拟赛

时间：2024-10-07 18:23:06浏览次数：8  
标签：20241002 int ll mxn num ans 模拟 define

这场爆零了。（惨
先把题目发上来吧。









A. 躲避技能

难度：绿
机房大佬又给出解法：对于每个账号的位置，我们+1；而关键点，我们-1。（这里其实可以不必考虑正负，最后取abs就行了）
然后遍历一遍整棵树，将每个节点（除了根节点）作为根的子树点权和算出来，乘上该节点与其父亲连的边的边权，每个节点的加起来就行了。
仔细想发现这样做是很自然的。不必走的边自然会被省掉，手玩一下就能领会了。
当然这题还有很恶心的高精度。（连签到题都不给吗？？？）

#include<bits/stdc++.h>
#define ll long long
#define mxn 100010
using namespace std;
ll n,m,len[mxn],q[mxn];
ll val[mxn][110];
ll ans[110],l,sum,lstw;
struct edge{
    ll v,id;
};
vector<edge> t[mxn];
int dfs(int u,int f){
    int sum=0;
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i].v;
        if(v==f)continue;
        ll eid=t[u][i].id;
        int a=dfs(v,u);
        l=max(len[eid],l*1ll);
        for(int j=1;j<=len[eid];j++)
            ans[j]=ans[j]+fabs(val[eid][j]*a);
        sum+=a;
        for(int j=l;j;j--)
            ans[j+1]+=ans[j]/100000,ans[j]%=100000;
        if(ans[l+1])l++;
    }
    return sum+q[u];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//    freopen("skill.in","r",stdin);
//    freopen("skill.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){int s;cin>>s;q[s]++;}
    for(int i=1;i<=m;i++){int s;cin>>s;q[s]--;}
    for(int i=1;i<n;i++){
        int u,v;
        string w;
        cin>>u>>v>>w;
        int a=1,b=0;
        for(int j=0;j<w.length();j++){
            b=b+a*(w[j]-'0'),a*=10;
            if((j+1)%5==0)val[i][++len[i]]=b,a=1,b=0;
        }
        if(w.length()%5!=0)val[i][++len[i]]=b;
        t[u].push_back((edge){v,i});
        t[v].push_back((edge){u,i});
    }
    dfs(1,0);
    for(int i=l;i;i--){
        if(i!=l){
            int k=10000;
            for(int j=1;j<=5;j++){
                cout<<ans[i]/k;
                ans[i]-=ans[i]/k*k,k/=10;
            }
        }
        else cout<<ans[i];
    }
    return 0;
}

B. 奶茶兑换券

难度：绿-蓝
比较考验思维和乱猜结论能力的贪心。
首先，我们要尽可能让买两杯省的钱小于分别买两杯省的钱。因此，\(b_i+b_j\) 必须大于 \(m\)。
然后我们就把比 \(\frac{m}{2}\) 大的数和比 \(\frac{m}{2}\) 小的数分开。尽可能让这两组一一匹配。
发现在小的数这一组中，越大的数越匹配不到，所以让大的优先匹配。
最后让剩下的多的自行匹配就行了，这里怎么匹配答案都是一样的。

#include<bits/stdc++.h>
#define ll long long
#define mxn 100010
#define mp make_pair
#define pll pair<long long,long long>
using namespace std;
ll n,m,ans,sum,l,r,lcnt,rcnt,lsum;
set<pll> tea;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    // freopen("tea.in","r",stdin);
    // freopen("tea.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        ll a,b;
        cin>>a>>b;
        b%=m;
        if(b){
            b=m-b;
            sum+=b*a;
            tea.insert(mp(b,a));
        }
    }
    set<pll>::iterator r=tea.lower_bound(mp(m/2,0)),l=r;
    l--;
    if(r==tea.begin()){
        lsum=0;
        while(r!=tea.end()){
            lsum+=(*r).second;
            r++;
        }
        cout<<sum-lsum/2*m;
        return 0;
    }
    lcnt=(*l).second,rcnt=(*r).second;
    if((*r).first==m/2){
        r++,rcnt=0;
        if(r!=tea.end())rcnt=(*r).second;
    }
    while(1){
        if(!rcnt){if(r==tea.end())break;r++,rcnt=(*r).second;}
        if(!lcnt){if(l==tea.begin())break;l--,lcnt=(*l).second;}
        while((*l).first+(*r).first<m&&r!=tea.end()){r++;rcnt=(*r).second;}
        if(r==tea.end())break;
        ll cnt=min(lcnt,rcnt);
        lcnt-=cnt,rcnt-=cnt,ans+=cnt;
        
        sum-=cnt*m;
    }
    lsum=0;
    r=tea.lower_bound(mp(m/2,0));
    while(r!=tea.end()){
        lsum+=(*r).second;
        r++;
        rcnt=(*r).second;
    }
    cout<<sum-(lsum-ans)/2*m;
    return 0;
}

C. 帮助

难度：蓝
题目看起来好绕啊qwq
机房巨佬说这题扫描线秒了，可我连扫描线是什么也不知道啊（我好菜啊~~
设 \(g_{i,j}\) 为所有成绩为 \(j\) 且愿意帮助成绩为 \(i\) 的人做题数之和。
于是有递推式：
\(g_{i,j}=g_{i-1,j}+\sum\limits_{c_p=i,t_p=j}f_p-\sum\limits_{d_p=i-1,t_p=j}f_p\)
用树状数组维护，注意离散化。

#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define pll pair<ll,ll>
#define mxn 100010
using namespace std;
ll n,f[mxn],t[mxn];
ll a[mxn],b[mxn],c[mxn],d[mxn];
ll num[mxn],id1[mxn],id2[mxn];
ll tre[mxn],ans[mxn],l,noww;
ll sort_by_t[mxn],sort_by_c[mxn];
priority_queue<pll,vector<pll>,greater<pll> > q;
ll lowbit(ll x){
    return x&(-x);
}
ll ask(ll x){
    ll ret=0;
    while(x){
        ret+=tre[x];
        x-=lowbit(x);
    }
    return ret;
}
void treadd(ll x,ll val){
    while(x<=l){
        tre[x]+=val;
        x+=lowbit(x);
    }
    return;
}
bool cmpt(int a,int b){
    return num[a]<num[b];
}
bool cmpc(int a,int b){
    return c[a]<c[b];
}
void lisan(){
    sort(t+1,t+n+1);
    l=unique(t+1,t+n+1)-t-1;
    for(int i=1;i<=n;i++){
        ll aa,bb,cc,dd;
        cin>>aa>>bb>>cc>>dd;
        num[i]=lower_bound(t+1,t+l+1,num[i])-t;//离散化!
        a[i]=lower_bound(t+1,t+l+1,aa)-t;
        b[i]=upper_bound(t+1,t+l+1,bb)-t-1;
        c[i]=lower_bound(t+1,t+l+1,cc)-t;
        d[i]=upper_bound(t+1,t+l+1,dd)-t-1;
    }
    sort(sort_by_c+1,sort_by_c+n+1,cmpc);//按帮助别人的范围排序c
    sort(sort_by_t+1,sort_by_t+n+1,cmpt);//按成绩排序t
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    // freopen("help.in","r",stdin);
    // freopen("help.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>f[i];
    for(int i=1;i<=n;i++){
        sort_by_c[i]=sort_by_t[i]=i;
        cin>>t[i];
        num[i]=t[i];
    }
    lisan();
    for(int i=1;i<=n;i++){//按成绩排序遍历
        while(c[sort_by_c[noww]]<=num[sort_by_t[i]]&&noww<=n){//看i能被多少人帮助
            if(d[sort_by_c[noww]]>=num[sort_by_t[i]]){
                q.push(mp(d[sort_by_c[noww]],sort_by_c[noww]));
                treadd(num[sort_by_c[noww]],f[sort_by_c[noww]]);
            }
            noww++;
        }
        while(q.size()&&q.top().first<num[sort_by_t[i]]){
            treadd(num[q.top().second],-f[q.top().second]);
            q.pop();//再把不能的去掉
        }
        ans[sort_by_t[i]]+=ask(b[sort_by_t[i]])-ask(a[sort_by_t[i]]-1);//在受帮助的范围里减去
        if(num[i]<c[i]||num[i]>d[i]||num[i]<a[i]||num[i]>b[i])ans[i]+=f[i];//加上他自己做的
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}

D. 神奇的变换

难度：紫-黑
恶心数学题，出出来就是为了恶心别人的。
不想改了，就这样吧。

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define mxn 100001
#define mxm 350
using namespace std;
int pp[200][mxn],pre[80001][mxm],mipri[mxn*10],mapri[mxn];
int pri[mxn],wh[mxn*10],vis[mxn],fir[mxn];
int k[mxn+1],l[mxm],r[mxm];
int type,n,m,sq;
ll kk[mxm][mxm],inv[mxn],vv[mxn],ans;
bool is[mxn*10];
vector<int> a[mxn];
vector<ll> b[mxn],e[mxn];
inline ll qow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
inline void init_pri(){
    n=1000000;
    for(int i=2;i<=n;i++){
        if(!is[i]) pri[wh[i]=++pri[0]]=i,fir[wh[i]]=100001,mipri[i]=wh[i];
        for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++){
            is[i*pri[j]]=1;
            mipri[i*pri[j]]=j;
            if(i%pri[j]==0) break;
        }
    }
}
inline void read_all(){
    cin>>n>>m>>type;
    for(int i=1;i<=n;i++){
        int val;
        cin>>val;
        while(val!=1&&is[val])a[i].push_back(mipri[val]),val/=pri[mipri[val]];
        if(val!=1){
            a[i].push_back(wh[val]);
            if(val>1000) mapri[i]=wh[val];
        }
    }
}
inline void init_sq(){
    for(;(sq+1)*(sq+1)<=n;sq++);
    k[100001]=n;
    for(int i=1;i<=n;i++){
        k[i]=(i+sq-1)/sq;
        if(!l[k[i]]) l[k[i]]=i;
        r[k[i]]=i;
        for(int j:a[i]){
            pre[j][k[i]]++;
            if(pri[j]<=1000) pp[j][i]++;
            if(fir[j]>i) fir[j]=i;
        }
    }
    for(int i=1;i<=pri[0];i++) for(int j=k[fir[i]]+1;j<=k[n];j++)
        pre[i][j]+=pre[i][j-1];
    for(int i=1;pri[i]<=1000;i++) for(int j=fir[i]+1;j<=n;j++) pp[i][j]+=pp[i][j-1];
}
inline void init_pow(){
    for(int i=1;i<=n;i++) inv[i]=qow(i,mod-2),vv[i]=inv[i-1]*i%mod;
    if(type-3)return;
    for(int i=1;i<=pri[0];i++){
    	if(pri[i]<=1000){	
	        ll now=1;
	        b[i].resize(pre[i][k[n]]+1);
	        b[i][0]=1;
	        for(int j=1;j<=pre[i][k[n]];j++){
	            now=(now*pri[i]+1)%mod;
	            b[i][j]=now;
	        }
		}
		else{
	        ll now=1;
	        b[i].resize(pre[i][k[n]]+1);
	        e[i].resize(pre[i][k[n]]+1);
	        b[i][0]=e[i][0]=1;
	        for(int j=1;j<=pre[i][k[n]];j++){
	            e[i][j]=pri[i]+qow(now,mod-2);
	            now=(now*pri[i]+1)%mod;
	            b[i][j]=now;
	        }
		}
    }
}
inline void init_kans(){
    int sz=pri[0]*4+4;
    if(type==1){
        for(int i=1;i<=k[n];i++){
            ll ans1=1;
            for(int j=i;j<=k[n];j++){
                for(int p=l[j];p<=r[j];p++) 
                    if(mapri[p]){
                        int &cnt=++vis[mapri[p]];
                        ans1*=-1;if(cnt>=2) ans1=0;
                    }
                kk[i][j]=(ans1+mod)%mod;
            }
            memset(vis,0,sz);
        }
    }
    else if(type==2){
        for(int i=1;i<=k[n];i++){
            ll ans2=1;
            for(int j=i;j<=k[n];j++){
                for(int p=l[j];p<=r[j];p++) if(mapri[p]){
                    int &cnt=++vis[mapri[p]];
                    ans2=ans2*vv[cnt+1]%mod;
                }
                kk[i][j]=ans2;
            }
            memset(vis,0,sz);
        }
    }
    else{
        for(int i=1;i<=k[n];i++){
            ll ans3=1;
            for(int j=i;j<=k[n];j++){
                for(int p=l[j];p<=r[j];p++) 
                    if(mapri[p]){
                        int &cnt=++vis[mapri[p]],&num=mapri[p];
                        ans3=ans3*e[num][cnt]%mod;
                }
                kk[i][j]=ans3;
            }
            memset(vis,0,sz);
        }
    }
}
inline void query(int l,int r){
    if(k[l]==k[r]){
        if(type==1){
            ans=1;
            for(int i=1;pri[i]<=1000;i++){
                int cnt=pp[i][r]-pp[i][l-1];
                if(cnt==1) ans*=-1;
                else if(cnt>=2) ans=0;
            }
            for(int i=l;i<=r;i++) 
                if(mapri[i]){
                    int &num=mapri[i],&cnt=++vis[num];
                    if(cnt==1) ans*=-1;
                    else ans=0;
                }
            for(int i=l;i<=r;i++) 
                if(mapri[i]) 
                    vis[mapri[i]]--;
            ans=(ans+mod)%mod;
            cout<<ans<<'\n';
        }
        else if(type==2){
            ans=1;
            for(int i=1;pri[i]<=1000;i++){
                int cnt=pp[i][r]-pp[i][l-1];
                (ans*=(cnt+1))%=mod;
            }
            for(int i=l;i<=r;i++) if(mapri[i]){
                int &num=mapri[i],&cnt=++vis[num];
                (ans*=vv[cnt+1])%=mod;
            }
            for(int i=l;i<=r;i++) if(mapri[i]) vis[mapri[i]]--;
            cout<<ans<<'\n';
        }
        else{
            ans=1;
            for(int i=1;pri[i]<=1000;i++){
                int cnt=pp[i][r]-pp[i][l-1];
                (ans*=b[i][cnt])%=mod;
            }
            for(int i=l;i<=r;i++) 
                if(mapri[i]){
                    int &num=mapri[i],&cnt=++vis[num];
                    (ans*=e[num][cnt])%=mod;
                }
            for(int i=l;i<=r;i++) 
                if(mapri[i]) 
                    vis[mapri[i]]--;
            cout<<ans<<'\n';
        }
        return;
    }
    if(type==1){
        ans=1;
        if(k[l]+1<=k[r]-1) ans=kk[k[l]+1][k[r]-1];
        for(int i=1;pri[i]<=1000;i++){
            int cnt=pp[i][r]-pp[i][l-1];
            if(cnt==1) ans*=-1;
            else if(cnt>=2) ans=0;
        }
        for(int i=l;k[i]==k[l];i++) 
            if(mapri[i]){
                int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
                if(cnt==1) ans*=-1;
                else if(cnt>=2) ans=0;
            }
        for(int i=r;k[i]==k[r];i--) 
            if(mapri[i]){
                int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
                if(cnt==1) ans*=-1;
                else if(cnt>=2) ans=0;
            }
        for(int i=l;k[i]==k[l];i++)if(mapri[i])vis[mapri[i]]--;
        for(int i=r;k[i]==k[r];i--)if(mapri[i])vis[mapri[i]]--;
        (ans+=mod)%=mod;
        cout<<ans<<'\n';
    }
    else if(type==2){
        ans=1;
        if(k[l]+1<=k[r]-1) ans=kk[k[l]+1][k[r]-1];
        for(int i=1;pri[i]<=1000;i++){
            int cnt=pp[i][r]-pp[i][l-1];
            (ans*=(cnt+1))%=mod;
        }
        for(int i=l;k[i]==k[l];i++) 
            if(mapri[i]){
                int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
                (ans*=vv[cnt+1])%=mod;
            }
        for(int i=r;k[i]==k[r];i--) 
            if(mapri[i]){
                int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
                (ans*=vv[cnt+1])%=mod;
            }
        for(int i=l;k[i]==k[l];i++) if(mapri[i]) vis[mapri[i]]--;
        for(int i=r;k[i]==k[r];i--) if(mapri[i]) vis[mapri[i]]--;
        cout<<ans<<'\n';
    }
    else{
        ans=1;
        if(k[l]+1<=k[r]-1) ans=kk[k[l]+1][k[r]-1];
        for(int i=1;pri[i]<=1000;i++){
            int cnt=pp[i][r]-pp[i][l-1];
            (ans*=b[i][cnt])%=mod;
        }
        for(int i=l;k[i]==k[l];i++) 
            if(mapri[i]){
                int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
                (ans*=e[num][cnt])%=mod;
        }
        for(int i=r;k[i]==k[r];i--) 
            if(mapri[i]){
                int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
                (ans*=e[num][cnt])%=mod;
        }
        for(int i=l;k[i]==k[l];i++) if(mapri[i]) vis[mapri[i]]--;
        for(int i=r;k[i]==k[r];i--) if(mapri[i]) vis[mapri[i]]--;
        cout<<ans<<'\n';
    }
}
inline void query(){
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        l^=ans,r^=ans;
        query(l,r);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	// freopen("change.in","r",stdin);
  	// freopen("change.out","w",stdout); 
    init_pri();
    read_all();
    init_sq();
    init_pow();
    init_kans();
    query();
    return 0;
}

标签：20241002,int,ll,mxn,num,ans,模拟,define
From： https://www.cnblogs.com/nagato--yuki/p/18444560

相关文章

  • 10.7 模拟赛
    复盘T1看上去不难。一开始以为枚举\(a,b\)，然后考虑平方差。于是想出了这道题的解法。但是转化不过去。后来发现因为\(k\)很小直接暴力预处理就行。30min左右过大样例。T2一眼不会。想到了P1521求逆序对但还是不会做。T3,T4显然不可做。有了前几场的经验，先把所有......
  • 多校 A 层冲刺 NOIP2024 模拟赛 03
    多校A层冲刺NOIP2024模拟赛03T1五彩斑斓（colorful）签到题直接暴力枚举是\(O(n^4)\)，考虑使用\(bitset\)优化，对每个点开个\(bitset\)，预处理它所在一行它及它之前相同颜色的位置，这样就只用枚举另一个点所在列，时间复杂度为\(O(n^3+\frac{n^4}{w})\)。T2错峰旅行（travel）......
  • CSP-S 模拟赛 35
    CSP-S模拟赛35rnk14，\(45+45+15+18=123\)。T1送花愚蠢题。看到区间想到线段树，预处理出每个位置的颜色上一次出现的位置，记为\(\mathit{las}_i\)。从左到右扫右端点，给\([\max(1,\mathit{las}_{\mathit{las}_i}),\mathit{las}_i]\)减去\(d(c_i)\)，给\((\mathit{las}_i,i]\)......
  • CSP-S 模拟赛 34
    CSP-S模拟赛34rnk12，\(24+50+20+0=94\)。T1玩游戏有一个痿正解：从\(k\)到\(1\)扫左端点，对于每个左端点扫它最远能到达的右端点。如果在任何一时刻它的右端点位置\(<k\)，则断定输出No。否则检查当左端点到\(1\)时右端点能否到\(n\)。注意这里扫右端点的方式，不要每次都......
  • CSP-S 模拟赛 33
    CSP-S模拟赛33rnk19，\(30+20+40+15=105\)。T1构造字符串10pts：输出\(-1\)。30pts：对于所有\(z_i=0\)的情况，也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的，然后从\(1\)到\(n\)扫一遍，输出除去不同的字符之外的字典序最小的字符。70pts：暴搜。枚举每个......
  • 2024-10-6 模拟赛总结
    \(100+80+100+0=280\)，暴力又写挂了。比赛链接：http://172.45.35.5/d/HEIGETWO/homework/67025b796735d3863dc7f60d或者http://yl503.yali.edu.cn/d/HEIGETWO/homework/67025b796735d3863dc7f60dA-fountain题意：给定一条线段和一个圆，求线段上任意一点到圆上任意一点的最大距......
  • 多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9
    多校A层冲刺NOIP2024模拟赛02四道题因为暑假被拉去当模拟赛暑假集训CSP提高模拟22了，遂直接把赛后代码交了上去，然后就被通知换题了。原\(100+100+100+20\)被在accodersNOI上被卡成了\(100+100+90+10\)，更改longlong和int后达到了\(100+100+100+30\)。\(T1\)P318......
  • 『模拟赛』CSP-S模拟9
    Rank烂，知耻而后勇A.邻面合并签。注意到列数\(m\le8\)，我们可以直接先搜出每一行可能的“分块”情况，然后转移时枚举上一行的所有状态和这一行的所有状态，根据拼接情况来更新答案，最终答案即为\(n\)行所有情况的最小值。赛时开始打的错解，错解如果第一行总数计算错了就能过......
  • 傻逼模拟赛搬的时候能不能看看题面改之后还是不是让人能看懂还有不发 checker 是有什
    如题。傻逼模拟赛搬的时候能不能看看题面改之后还是不是让人能看懂还有不发checker是有什么心事吗还在最后一道题放集训队互测什么意思什么叫有\(b_{k}\)种\(k\)类型的货币，同一种流通的货币不会超过二十种什么叫接下来\(n\)个数表示\(a_{1}\sima_{n-1}\)......
  • 20241002每日一题洛谷P1563
    粗看题目我靠，什么方向还变来变去的（哭泣核心思想：圈内右数，圈外左数为整体逆时针数；圈外右数，圈内左数为整体顺时针数运用结构体就有了第一版源码：structpeople{ intface; charname[12];};intmain(){ intm,n; scanf("%d%d",&n,&m); peoplea[10010]; for(inti......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99