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

NOIP2024加赛6

时间：2024-11-18 20:57:09浏览次数：1  
标签：rs int ls freopen ans 加赛 NOIP2024 define

NOIP2024加赛6

\(T1\) P323. 草莓 \(60pts\)

  • 部分分

    • \(60pts\)
      • 先将 \(\{ x \},\{ y \}\) 降序排序，状态转移方程为 \(f_{i,j}=\min(f_{i-1,j}+x_{i}(j+1),f_{i,j-1}+y_{j}(i+1))\) ，边界为 \(f_{0,0}=0\) ，最终有 \(f_{n-1,m-1}\) 即为所求。
      • 若费用提前计算则需要将 \(\{ x \},\{ y \}\) 升序排序并做前缀和，状态转移方程为 \(f_{i,j}=\min(f_{i-1,j}+sumx_{i},f_{i,j-1}+sumy_{j})\) ，边界为 \(f_{0,0=0}\) ，最终有 \(f_{n-1,m-1}+sumx_{n-1}+sumy_{m-1}\) 即为所求。
    点击查看代码 
    ll x[200010],y[200010],f[2][200010];
int main()
{
#define Isaac
#ifdef Isaac
	freopen("guiltiness.in","r",stdin);
	freopen("guiltiness.out","w",stdout);
#endif
	ll n,m,i,j;
	cin>>n>>m;
	n--;
	m--;
	for(i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	for(i=1;i<=m;i++)
	{
		cin>>y[i];
	}
	sort(x+1,x+n+1);
	sort(y+1,y+m+1);
	for(i=1;i<=n;i++)
	{
		x[i]+=x[i-1];
	}
	for(i=1;i<=m;i++)
	{
		y[i]+=y[i-1];
	}
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=m;j++)
		{
			f[(i+1)&1][j]=0x3f3f3f3f3f3f3f3f;
		}
		for(j=0;j<=m;j++)
		{
			f[(i+1)&1][j]=min(f[(i+1)&1][j],f[i&1][j]+y[j]);
			f[i&1][j+1]=min(f[i&1][j+1],f[i&1][j]+x[i]);
		}
	}
	cout<<f[n&1][m]+x[n]+y[m]<<endl;
	return 0;
}

  • 正解

    • 上述做法因为需要求解在网格图上的最短路，只能另寻他法。
    • 考虑临项交换，观察到最终操作序列上相邻的 \(x_{i},y_{j}\) 交换成 \(y_{j},x_{i}\) 更优当且仅当 \(y_{j}>x_{i}\) ，将 \(\{ x \},\{ y \}\) 放到一起降序排序即可。
    点击查看代码 
    ll cnt[2];
vector<pair<ll,ll> >a;
int main()
{
#define Isaac
#ifdef Isaac
	freopen("guiltiness.in","r",stdin);
	freopen("guiltiness.out","w",stdout);
#endif
	ll n,m,x,ans=0,i;
	cin>>n>>m;
	n--;
	m--;
	for(i=1;i<=n+m;i++)
	{
		cin>>x;
		a.push_back(make_pair(x,i>n));
	}
	sort(a.begin(),a.end());
	reverse(a.begin(),a.end());
	for(i=0;i<a.size();i++)
	{
		ans+=a[i].first*(cnt[a[i].second^1]+1);
		cnt[a[i].second]++;
	}
	cout<<ans<<endl;
	return 0;
}

\(T2\) P324. 三色 \(0pts\)

  • 原题：QOJ 1286. Ternary String Counting

  • 部分分

    • 子任务 \(1,2\)
      • 类似 luogu P11233 [CSP-S 2024] 染色 ，设 \(f_{i,j,k}\) 表示 \([1,i]\) 中第一个与 \(a_{i}\) 颜色不同的是 \(a_{j}\) ，第一个与 \(a_{i},a_{j}\) 颜色互不相同的数是 \(a_{k}\) 的方案数。转移时分讨 \(a_{i+1}=a_{i}/a_{j}/a_{k}\) 刷表法转移即可。边界为 \(f_{1,0,0}=3\) 。
      • 当访问到一个限制时及时去除不合法状态。
      • 最终有 \(\sum\limits_{j=0}^{n-1}\sum\limits_{k=0}^{\max(0,j-1)}f_{n,j,k}\) 即为所求。
      • 时间复杂度为 \(O(n^{3}+m)\) ，空间复杂度为 \(O(n^{2}+m)\) 。
    点击查看代码 
    const int p=1000000007;
int f[2][5010][5010];
vector<pair<int,int> >q[5010];
int main()
{
#define Isaac
#ifdef Isaac
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
#endif
	int t,n,m,l,r,x,ans,i,j,k,h,v;
	scanf("%d",&t);
	for(v=1;v<=t;v++)
	{
		ans=0;
		cin>>n>>m;
		for(i=1;i<=n;i++)
		{
			q[i].clear();
		}
		for(i=1;i<=m;i++)
		{	
			cin>>l>>r>>x;
			q[r].push_back(make_pair(l,x));
		}
		memset(f,0,sizeof(f));
		f[1][0][0]=3;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<=i;j++)
			{
				for(k=0;k<=max(0,j-1);k++)				
				{
					for(h=0;h<q[i].size();h++)
					{
						if(q[i][h].second==1&&q[i][h].first<=j)
						{
							f[i&1][j][k]=0;
						}
						if(q[i][h].second==2&&(q[i][h].first<=k||j<q[i][h].first))
						{
							f[i&1][j][k]=0;
						}
						if(q[i][h].second==3&&k<q[i][h].first)
						{
							f[i&1][j][k]=0;
						}
					}
					f[(i+1)&1][j][k]=0;
				}
			}
			for(j=0;j<=i-1;j++)
			{
				for(k=0;k<=max(0,j-1);k++)
				{
					f[(i+1)&1][j][k]=(f[(i+1)&1][j][k]+f[i&1][j][k])%p;
					f[(i+1)&1][i][k]=(f[(i+1)&1][i][k]+f[i&1][j][k])%p;
					f[(i+1)&1][i][j]=(f[(i+1)&1][i][j]+f[i&1][j][k])%p;
				}
			}
		}
		for(j=0;j<=n-1;j++)
		{
			for(k=0;k<=max(0,j-1);k++)
			{
				ans=(ans+f[n&1][j][k])%p;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

  • 正解

    • 仍考虑 luogu P11233 [CSP-S 2024] 染色 的优化方式，将 \(j,k\) 看做矩阵。当 \(i\) 转移到 \(i+1\) 时，分讨 \(a_{i+1}=a_{i}/a_{j}/a_{k}\) 分别对应复制到 \(i+1\) 处/将每列累加到 \(i+1\) 行的对应位置/将每行累加到 \(i+1\) 列的对应位置，后两者可以看做新加入一行。考虑维护 \(s_{k}=\sum\limits_{j=1}^{n}f_{i,j,k}+f_{i,k,j}\) 。
    • 遇到限制时等价于保留合法矩阵，不合法状态置零。
    • 使用 vector 快速处理出合法状态的集合使得每个数仅被加入、删除 \(O(1)\) 次。时空复杂度为 \(O(n^{2}+m)\) 。
    点击查看代码

\(T3\) P325. 博弈 \(0pts\)

  • 原题： QOJ 8077. Madeline and Badeline

  • 选出的三个数为 \(a,b,c(a<b<c)\) 时，有 Madeline 必胜。

    • 若 \(a,c\) 关于 \(b\) 对称，那么 Madeline 直接操作 \(a,c\) 使其等于 \(b\) 即可获胜。
    • 否则，以 \(a'=a-(c-b)>0,b,b\) 为例（ \(b,b,c'=c-(b-a)>0\) 同理）。若在进入该状态后 Badeline 必胜，则 Madeline 直接仿照原 Badeline 的操作方式操作（多操作几步使其到达 Badeline 必胜的第一步情况）即可获胜；否则因为 Badeline 必败，故 Madeline 必胜。

  • 选出的三个数中有两个数相同时，以 \(a,a,b(a<b)\) 为例。此时 Madeline 只能将 \(a,b\) 操作成 \(\frac{a+b}{2}\) （如果无法操作必败）， Badeline 继续这种操作方式。若 \(|a-b|\) 最低位的 \(1\) 是第偶数位 Madeline 必胜，即 __builtin_ffs(abs(a-b))%2==0 。

  • 选出的三个数都相同时 Madeline 必败。

  • 将 \(\{ a \}\) 倒着插入 \(01Trie\) 树上统计叶子个数即可。

    点击查看代码 
    unordered_map<ll,ll>vis;
unordered_map<ll,ll>::iterator it;
struct Trie
{
	int son[30000010][4],siz[30000010],rt_sum=1;
	void clear()
	{
		for(int i=1;i<=rt_sum;i++)
		{
			son[i][0]=son[i][1]=son[i][2]=son[i][3]=siz[i]=0;
		}
		rt_sum=1;
	}
	int build_rt()
	{
		rt_sum++;
		return rt_sum;
	}
	void insert(ll s)
	{
		int x=1;
		for(int i=0;i<=60;i+=2)
		{
			if(son[x][(s>>i)&3]==0)
			{
				son[x][(s>>i)&3]=build_rt();
			}
			siz[x]++;
			x=son[x][(s>>i)&3];
		}
		siz[x]++;
	}
	ll query(ll s)
	{
		int x=1;
		ll ans=0;
		for(int i=0;i<=60;i+=2)
		{
			ans+=(siz[son[x][((s>>i)&3)^1]]+siz[son[x][((s>>i)&3)^3]]);
			x=son[x][(s>>i)&3];
		}
		return ans;
	}
}T;
int main()
{
#define Isaac
#ifdef Isaac
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
#endif
	ll t,n,x,ans,i,j;
	scanf("%lld",&t);
	for(j=1;j<=t;j++)
	{
		T.clear();
		vis.clear();
		scanf("%lld",&n);
		ans=n*(n-1)*(n-2)/6;
		for(i=1;i<=n;i++)
		{
			scanf("%lld",&x);
			T.insert(x);
			vis[x]++;
		}
		for(it=vis.begin();it!=vis.end();it++)
		{
			ans-=it->second*(it->second-1)/2*T.query(it->first);
			ans-=it->second*(it->second-1)*(it->second-2)/6;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

\(T4\) P326. 后缀数组 \(0pts\)

  • 原题： CodeChef TASUFFIX-Very Long Suffix Array

    点击查看 std 代码 
    #include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<random>
#include<map>
#include<math.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&-(x))
#define popcount(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define umap unordered_map
#define all(x) x.begin(),x.end()
#define mk make_pair
#define pb push_back
#define ckmax(x,y) x=max(x,y)
#define ckmin(x,y) x=min(x,y)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define N 100005
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int mo=998244353;
inline void red(int &x){x>=mo?x-=mo:0;}
inline int qpow(int x,int b){
	int res=1;
	for(;b;x=1LL*x*x%mo,b>>=1) if(b&1) res=1LL*res*x%mo;
	return res;
}
struct FHQ{
	int ls,rs,sze,cnt,sum,lazy;
	pii v;
}T[N*2];
int rt,pool;
mt19937 rnd(114514);
inline int newNode(int l,int r){
	T[++pool].sze=1,T[pool].cnt=T[pool].sum=max(r-l+1,l-r+1),T[pool].v={l,r};
	return pool;
}
inline void pushup(int k){
	T[k].sze=T[T[k].ls].sze+T[T[k].rs].sze+1;
	T[k].sum=T[T[k].ls].sum+T[T[k].rs].sum+T[k].cnt;
}
inline void pushdown(int k){
	if(!T[k].lazy) return;
	T[k].lazy=0;
	swap(T[T[k].ls].v.fi,T[T[k].ls].v.se);
	swap(T[T[k].rs].v.fi,T[T[k].rs].v.se);
	swap(T[T[k].ls].ls,T[T[k].ls].rs);
	swap(T[T[k].rs].ls,T[T[k].rs].rs);
	T[T[k].ls].lazy^=1;
	T[T[k].rs].lazy^=1;
}
int U;
void split(int k,int &x,int &y,int s){
	if(!k) return (void)(x=y=0);
	pushdown(k);
	if(T[T[k].ls].sum+T[k].cnt<=s){
		x=k;
		split(T[k].rs,T[k].rs,y,s-T[T[k].ls].sum-T[k].cnt);
		U+=T[T[k].ls].sum+T[k].cnt;
	}
	else{
		y=k;
		split(T[k].ls,x,T[k].ls,s);
	}
	pushup(k);
}
int merge(int x,int y){
	if(!x || !y) return x+y;
	pushdown(x),pushdown(y);
	if(rnd()%(T[x].sze+T[y].sze)<T[x].sze){
		T[x].rs=merge(T[x].rs,y);
		pushup(x);return x;
	}
	else{
		T[y].ls=merge(x,T[y].ls);
		pushup(y);return y;
	}
}
int n,m;
pii b[2*N];
void get(int k){
	pushdown(k);
	if(T[k].ls) get(T[k].ls);
	b[++m]=T[k].v;
	if(T[k].rs) get(T[k].rs);
}
map<int,int> rk;
signed main(){
	freopen("sa.in","r",stdin);
	freopen("sa.out","w",stdout);
	n=read(),m=read();
	rt=newNode(1,n);
	for(int i=1;i<=m;++i){
		int op=read(),l=read(),r=read();
		int x,y,z;
		U=0;
		split(rt,x,y,l-1);
		U=l-1-U;
		if(U){
			int now=y;
			while(T[now].ls){
				pushdown(now);
				T[now].sum-=U;
				now=T[now].ls;
			}
			T[now].sum-=U,T[now].cnt-=U;
			if(T[now].v.fi<=T[now].v.se){
				int mid=T[now].v.fi+U-1;
				x=merge(x,newNode(T[now].v.fi,mid));
				T[now].v.fi=mid+1;
			}
			else{
				int mid=T[now].v.fi-U+1;
				x=merge(x,newNode(T[now].v.fi,mid));
				T[now].v.fi=mid-1;
			}
		}
		U=0;
		split(y,y,z,r-l+1);
		U=(r-l+1)-U;
		if(U){
			int now=z;
			while(T[now].ls){
				pushdown(now);
				T[now].sum-=U;
				now=T[now].ls;
			}
			T[now].sum-=U,T[now].cnt-=U;
			if(T[now].v.fi<=T[now].v.se){
				int mid=T[now].v.fi+U-1;
				y=merge(y,newNode(T[now].v.fi,mid));
				T[now].v.fi=mid+1;
			}
			else{
				int mid=T[now].v.fi-U+1;
				y=merge(y,newNode(T[now].v.fi,mid));
				T[now].v.fi=mid-1;
			}
		}
		if(op==0){
			rt=merge(y,merge(x,z));	
		}
		else{
			swap(T[y].v.fi,T[y].v.se);
			swap(T[y].ls,T[y].rs);
			T[y].lazy^=1;
			rt=merge(x,merge(y,z));
		}
	}
	m=0;
	get(rt);
	// for(int i=1;i<=m;++i) fprintf(stderr,"%d %d\n",b[i].fi,b[i].se);
	int pre=0;
	for(int i=1;i<=m;++i){
		rk[b[i].fi]=pre+1;
		pre+=abs(b[i].fi-b[i].se)+1;
		rk[b[i].se]=pre;
	}
	int ans=-1,lst=-1;
	pre=0;
	for(int i=1;i<=m;++i){
		if(b[i].fi<=b[i].se){
			if(b[i].fi!=b[i].se){
				if(pre+2>lst) ans++;
			}
			else if(rk[b[i].fi+1]>lst) ans++;
			pre+=b[i].se-b[i].fi+1;
			if(b[i].fi!=b[i].se){
				if(rk[b[i].se+1]>pre) ans++;
			}
			lst=rk[b[i].se+1];
		}
		else{
			if(rk[b[i].fi+1]>lst) ans++;
			if(pre+1>rk[b[i].fi+1]) ans++;
			pre+=b[i].fi-b[i].se+1;
			lst=pre-1;
		}
		ans+=max(0,abs(b[i].fi-b[i].se)-1);
	}
	cout<<qpow(2,ans);
	return 0;
}

总结

  • \(T1\) 口胡的费用提前计算一开始想假了，将横竖的边权搞反了。

后记

  • \(T3\) 题面过于狗屎，没有说明行动过程中改变之后的数值仍为整数。

标签：rs,int,ls,freopen,ans,加赛,NOIP2024,define
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18553208

相关文章

  • [2024.11.18]NOIP2024模拟赛#23
    赛时T1题面实在太奇怪，结合样例看了好久才看懂。看懂以后发现应该就是简单神秘结论题。简单写了一会就过了样例，发现没给大样例，就扔了。T2第一眼感觉还是结论题，但是如果发现每个点能保证只覆盖一次的话就能做到\(\mathcal{O}(nm)\)。然后开始写，写完不过样例，发现题目让先输入......
  • [赛记] 多校A层冲刺NOIP2024模拟赛23
    字符串构造机100pts原题，见[赛记]多校A层冲刺NOIP2024模拟赛01【衡中】T1；忍者小队60pts赛时最后想出来个$\Theta(n^2\logn)$的DP，所以60pts；对于这个DP，直接用map维护一下所有lcm的状态转移即可；点击查看代码#include<iostream>#include<cstdio>#include<vect......
  • NOIP2024加赛5
    暴力操作（opt）拜谢丁真首先题目有一个很明显的性质：我们肯定只会对前\(\cfrac{n+1}{2}\)个数进行操作使它变小。最后的答案很明显没看出来具有二分答案的性质，考虑怎么check。实则就是要判断前\(\cfrac{n+1}{2}\)个数是否都能\(\lemid\)。我们可以方便的找出\(a_i\)变......
  • NOIP2024 前集训：NOIP2024加赛 5
    前言music《浮光》看指尖拨响蝴蝶扇动一场离别我推开无声岁月续梦一页你我只是打个照面可曾有过誓约走进熟悉却陌生的思念啊……啊……你的眼眸装满了时间你的身后拥故事成篇此生如梦愿细数流年与你同写沧海桑田浮光掠影重山彩云间你的伏线......
  • 『模拟赛』NOIP2024加赛5
    Rank反向挂分大王A.暴力操作（opt）签，但是没有人签。都想到了二分和更新c值，但是c多多少少没更到最优。首先还是调和级数预处理，倒序取min。然后考虑到超过\(m\)的也有可能产生更小的代价，因此\(\mathcal{O(n)}\)枚举一遍找到最小的\(j\)使\(i\timesj\gtm\)，全部赋......
  • NOIP2024加赛5
    喜欢每个包绑一个hack是吧。暴力操作（opt）容易发现答案具有单调性，考虑二分答案。还发现只需要处理\(1\sim\left\lceil\frac{n}{2}\right\rceil\)即可。发现如果\(c_{i}>c_{j}且i<j\)，那么选\(j\)肯定更优。有\(\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\l......
  • NOIP2024加赛5
    NOIP2024加赛5题目来源：2023NOIPA层联测31\(T1\)HZTG5777.暴力操作（opt）\(40pts\)先将\(\{a\}\)升序排序。因为\(\left\lfloor\dfrac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor=\left\lfloor\dfrac{a}{bc}\right\rfloor\)，先钦定\(......
  • NOIP2024模拟赛#21 总结
    坐牢3h+。赛时开T1，发现好唐啊，10min切了。过了全部大样例。开T2，现在是8:10。？现在是8:27，我怎么把T2大样例全过了。是不是太水了。我只是胡了一个贪心啊。开T3，现在是8:30。草，T1加样例了，做法假了。先不管T1了，先去看T3。感觉保证每次操作后都会满足对于\(i......
  • NOIP2024 前集训：MX 炼石计划 NOIP 模拟赛 20
    前言今天不知道为啥去打MX了，bug不少啊，包括但不限于赛时能通过自己主页看自己题过没过，赛时可以进入“补题”的比赛交从而直接成IOI赛制，文件还有点问题？0+100+12+0，T1读假题：\(\ge×，>√\)，喜提爆零，但是本来就不会正解，我去我表都打出来了不知道二分？？！？！！？不打T4是错误的，乱搞能得的分......
  • 【考试题解】NOIP2024（欢乐）加赛3
    目录A.SakurakoandWater题目内容思路代码B.BinomialCoefficients,KindOf题目内容思路代码C.QED'sFavoritePermutation题目内容思路代码D.CardGame题目内容思路代码E.LongWaytobeNon-decreasing题目内容思路代码F.ManyGames题目内容思路代码A.SakurakoandW......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99