首页 > 其他分享 >NOIP2024 前集训：NOIP2024加赛 6

NOIP2024 前集训：NOIP2024加赛 6

时间：2024-11-20 17:19:58浏览次数：1  
标签：unlocked int void Tp read inline 加赛 集训 NOIP2024

前言

music 
《身骑白马》

我爱谁 跨不过 从来也不觉得错

自以为 抓着痛 就能往回忆里躲

偏执相信着 受诅咒的水晶球

阻挡可能心动的理由

而你却 靠近了 逼我们视线交错

原地不动 或向前走

突然在意这分钟

眼前荒沙弥漫了等候

耳边传来孱弱的呼救

追赶要我 爱的不保留

我身骑白马 走三关

我改换素衣 回中原

放下西凉 无人管

我一心只想 王宝钏

而你却 靠近了 逼我们视线交错

原地不动 或向前走

突然在意这分钟

眼前荒沙弥漫了等候

耳边传来孱弱的呼救

追赶要我 爱的不保留

我身骑白马 走三关

我改换素衣 回中原

放下西凉 无人管

我一心只想 王宝钏

满身伤痕累累 也来不及痛

那是指引我走向你的清楚感受

不管危不危险

都要放下一切跟你走

只要一起承担

只要你不放手

我身骑白马 走三关

我改换素衣 回中原

放下西凉 无人管

我一心只想 王宝钏

我改换素衣 回中原

放下西凉 无人管

我一心只想 王宝钏

前天的模拟赛今天才改，无语了，前天好像困得快死了，我假期也没熬太晚啊，现在前天发生了点啥都忘了。

T1 离谱签到，不知道一个贪心为啥要开 \(2s\) 时限，后面三道计数和博弈论，直接罚坐，本来马上要睡着了，结果 huge 去 D 了睡着的菜，我就吓醒了，然后继续罚坐，应该就是这样的。

改题的时候先改了 T2 的部分分，然后看不懂正解去改 T3 还没打完，然后帮 @ _君の名は 卡 T3 的常，然后也不知道怎么的一天就过去了，貌似睡着了？

然后食堂确实不给餐具了。

T1 草莓

直接贪心，显然先选权值大的。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,a[N],b[N],cnt[N]; ll ans;
signed main()
{
	freopen("guiltiness.in","r",stdin);
	freopen("guiltiness.out","w",stdout);
	read(n,m);
	for(int i=1;i<n;i++) read(a[i]),cnt[a[i]]++; n=0;
	for(int i=2e5;i;i--) while(cnt[i]) cnt[a[++n]=i]--;
	for(int i=1;i<m;i++) read(b[i]),cnt[b[i]]++; m=0;
	for(int i=2e5;i;i--) while(cnt[i]) cnt[b[++m]=i]--;
	for(int i=1,j=1;i<=n||j<=m;) ans+=a[i]>b[j]?1ll*a[i++]*j:1ll*b[j++]*i;
	write(ans);
}

T2 三色

首先考虑 \(O(n^3)\) 的 DP，设 \(f_{i,j,k}\) 表示处理到 \(i\)，三种不同的颜色最后一次出现的位置分别是 \(i,j,k\)，满足 \(i<j<k\)，直接转移即可，这么设计状态的目的就是判断是否合法。

考虑将 \(j,k\) 视为二维平面，那么之前的三种转移就分别对应三种移动方式，直接前缀和就能做到 \(O(n^2)\)，对于不合法的矩阵直接删除即可，因为每个点最多删除一次，所以复杂度正确。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5010,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int T,n,m,ans,lj[N],rj[N],lk[N],rk[N],vl[N],vr[N],sx[N],sy[N],f[N][N];
inline bool check(int i,int j) {return j>=lj[i]&&j<=rj[i];}
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
inline void del(int i,int l,int r)
{
	for(;vl[i]<l&&vl[i]<=vr[i];vl[i]++)
	{
		sx[i]=mod(sx[i],P-f[i][vl[i]]);
		sy[vl[i]]=mod(sy[vl[i]],P-f[i][vl[i]]);
	}
	for(;vr[i]>r&&vl[i]<=vr[i];vr[i]--)
	{
		sx[i]=mod(sx[i],P-f[i][vr[i]]);
		sy[vr[i]]=mod(sy[vr[i]],P-f[i][vr[i]]);
	}
}
signed main()
{
	freopen("color.in","r",stdin),freopen("color.out","w",stdout);
	for(read(T);T;T--,write(ans),puts(""))
	{
		read(n,m),ans=vl[0]=0,f[0][0]=sx[0]=sy[0]=3;
		for(int i=1;i<=n;memset(f[i++],0,4*(n+1)))
			lj[i]=lk[i]=vl[i]=sx[i]=sy[i]=0,rj[i]=rk[i]=vr[i]=i-1;
		for(int i=1,l,r,x;i<=m;i++)
		{
			read(l,r,x);
			if(x==1) rj[r]=min(rj[r],l-1);
			else if(x==2) lj[r]=max(lj[r],l),rk[r]=min(rk[r],l-1);
			else lk[r]=max(lk[r],l);
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<i;j++) check(i,j)?del(j,lk[i],rk[i]):del(j,j+1,0);
			if(i<n) for(int j=0;j<i;sx[i]=mod(sx[i],f[i][j++]))
				f[i][j]=mod(sx[j],sy[j]),sy[j]=mod(sy[j],f[i][j]);
		}
		for(int i=0;i<=n;i++) ans=mod(ans,sx[i]);
	}
}

T3 博弈

  • 结论 \(1\)：若 \(a,b,c\) 满足 \(a=b=c\)，则 Alice 必败，这是显然的，因为根本动不了。

  • 结论 \(2\)：若 \(a,b,c\) 互不相等，则 Alice 必胜。

    证明：假设 \(a<b<c\)，Alice 可一先靠拢 \(a,c\) 直到 \(b=c\)，轮到 Bob 靠拢 \(a,b\)，若此时为必败状态则 Alice 必胜，反之 Alice 可以在第一步时直接挪到当前的必胜状态，故 Alice 必胜。

  • 结论 \(3\)：若 \(a,b,c\) 满足 \(a=b<c\)，则 Alice 第一步一定是将 \(a,c\) 变成 \(\dfrac{a+c}{2}\)，若无法进行则到 Bob 手里就变成了三个互不相等的数，Bob 就赢了，Bob 的操作也是同理，所以二人轮流进行上述操作直到一个人无法进行时为必败状态。

    简单模拟一下发现 \(\exists k\in\N,\text{lowbit}(c-a)=2^{2k}\) 时先手必胜。

根据上面三个结论，前两个结论可以直接处理，第三个结论可以在 trie 树上处理，若当前为奇数则减去该点贡献，否则加上该点贡献。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5e5+10,M=3e7+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int T,n,m,tot,c[N],sz[M],t[M][2]; ll a[N],b[N],ans;
inline void insert(ll x,int d)
{
	sz[1]+=d; for(int i=0,p=1,c;i<60;i++,sz[p=t[p][c]]+=d)
		(!t[p][c=(x>>i)&1])&&(t[tot][0]=t[tot][1]=sz[t[p][c]=++tot]=0);
}
inline ll ask(ll x)
{
	int res=0; for(int i=0,j=1,p=1,c;p&&i<60;i++,j*=-1)
		res+=j*sz[p=t[p][c=(x>>i)&1]]; return res;
}
signed main()
{
	freopen("game.in","r",stdin),freopen("game.out","w",stdout);
	for(read(T);T;T--,write(ans),puts(""))
	{
		read(n),t[tot=1][0]=t[1][1]=0;
		for(int i=1;i<=n;i++) read(a[i]); sort(a+1,a+1+n);
		b[m=1]=a[1],c[1]=1,ans=1ll*n*(n-1)*(n-2)/6;
		for(int i=2;i<=n;i++) a[i]==a[i-1]?c[m]++:(c[++m]=1)&&(b[m]=a[i]);
		for(int i=1;i<=m;insert(b[i],c[i]),i++)
		{
			if(c[i]>2) ans-=1ll*c[i]*(c[i]-1)*(c[i]-2)/6;
			if(c[i]>1) ans-=1ll*c[i]*(c[i]-1)*(n-c[i])>>1;
		}
		for(int i=1;i<=m;i++) if(c[i]>1) ans+=c[i]*(c[i]-1)*ask(b[i])>>1;
	}
}

T4 后缀数组

题目和题目名称并没有什么关系，只是出题人想出计数了随便找个理由而已，那个“字符串”的定义也和什么似的，不会。

标签：unlocked,int,void,Tp,read,inline,加赛,集训,NOIP2024
From： https://www.cnblogs.com/Charlieljk/p/18556782

相关文章

  • [68] (NOIP集训) NOIP2024 加赛 5
    恐将成为我改题时间最长的一场（也是分最低的一场）码长断崖式领先了flowchartTB A(暴力操作) styleAcolor:#ffffff,fill:#00c0c0,stroke:#ffffff首先你肯定要让小于（等于）中位数的数变小，将较大的值变小是毫无意义的，因为即使你完全不管他们，也不会对答案造成任何影响，白白浪费费......
  • Noip 集训 （后半）
    已经快两周没写闲话了，一想万一十几天就退役了不得留点念想啊，于是还是拾起来吧11.19上午打了困困模拟赛，不过我倒没那么困，不至于像CTH一样啃着水杯呼呼大睡开场就听大家说全不可做，于是果断【数据删除】结果再看题目，看T1的前半小时脑子里全是【数据删除】，看了十几分钟才看懂......
  • [赛记] NOIP2024加赛5
    暴力操作（opt）30pts这个错解可反悔贪心30pts；考虑正解，我们只需考虑前$\fracn2+1$小的数即可；考虑二分出一个中位数$mid$，那么我们要让大于它的都用最小的代价变小；考虑如何求这个最小的代价，因为$\lfloor\frac{\lfloor\fracab\rfloor}{c}\rfloor=\lfloor\frac{ab......
  • [赛记] 多校A层冲刺NOIP2024模拟赛24
    选取字符串60pts直接暴力60pts；这题难点在于读懂题把。。。考虑建出$KMP$树，然后在其中选出$k$个数，他们的$LCA$的深度的平方和就是这个答案，然后简单统计一下即可；具体地，把$KMP$树建出来，然后求每$k$个点的$LCA$的深度的平方和即可，最后乘上方案数（总的减去......
  • 多校A层冲刺NOIP2024模拟赛24
    选取字符串建出失配树以后直接dp就好了。但场上现推的kmp……点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i<=t;i+=p)#definedrep(i,s,t,p)for(inti=s;i>=t;i-=p)#ifdefLOCALFILE*InFile=freope......
  • NOIP2024加赛6
    一签三计数，罚坐了。草莓简单贪心，随便贪就过了。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i<=t;i+=p)#definedrep(i,s,t,p)for(inti=s;i>=t;i-=p)#ifdefLOCAL FILE*InFile=freopen("in.in","r......
  • 多校A层冲刺NOIP2024模拟赛24
    多校A层冲刺NOIP2024模拟赛24\(T1\)A.选取字符串\(100pts\)考虑建出失配树，然后等价于询问\(\sum\limits_{S\sube\{0,1,2,\dots,n\},|S|=k}dep_{\operatorname{LCA}\{S\}}^{2}\)。不妨从\(\operatorname{LCA}\)的角度考虑，统计\(x\)能作为多少个\(|S|\)......
  • [71] (多校联训) A层冲刺NOIP2024模拟赛24
    bydT3放道这种题有什么深意吗flowchartTB A(选取字符串) styleAcolor:#ffffff,fill:#00c0c0,stroke:#ffffff确实是签，但是一直在想组合意义，最后因为没提前处理逆元遗憾离场了，赛后看题解发现的确是往树上转化更简单点赛时的组合意义代码没过#include<bits/stdc++.h>us......
  • 暑假集训随笔3 dp进阶2
    状压dp本身没啥可说的,这玩意主打一个技巧多。技巧1下面是一个用于枚举某个二进制数所表示集合的子集的二进制形式的代码。//S为二进制数for(intx=S;x;x=S&(x-1))cout<<x<<"";技巧2用一切方式避免直接进行严格\(O(n^2)\)的枚举，可以尝试用一些方式避开，如维护各个状态所......
  • 『模拟赛』NOIP2024加赛6
    Rank大奋场，T3没切有点菜A.草莓和前天多校T3很像，所以一眼鉴定为贪心，从大到小选比从小到大选一眼优，代价一样时横竖无所谓先后，然后sort一遍就做完了，复杂度\((n+m)\log(n+m)\)。10min切的。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for(registerint......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99