首页 > 其他分享 >noip模拟3

noip模拟3

时间:2024-11-03 14:08:21浏览次数:1  
标签:const noip int res ll long 模拟 mod

这场好难。

A 网格

队列里的结构体数组开大了导致 RE。。。

正解很简洁,对于现在有的字符串,添加一个数字或符号的转移是相对固定的:

添加一个数字,如果前一位是运算符,那么久新加一个数字,否则,让现在的数字乘以 10 加上它;

添加运算符同理。

点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+1,mod=998244353;
int n,m;
char s[N][N];
int dp1[N][N],dp2[N][N],dp3[N][N],dp4[N][N];
signed main()
{
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    dp2[1][0]=1,dp4[1][0]=1;
    for(int i=1;i<=n;i++)
	{
        for(int j=1;j<=m;j++)
		{
            dp4[i][j]=(dp4[i-1][j]+dp4[i][j-1])%mod,dp1[i][j]=(dp1[i-1][j]+dp1[i][j-1])%mod;
            dp2[i][j]=(dp2[i-1][j]+dp2[i][j-1])%mod,dp3[i][j]=(dp3[i-1][j]+dp3[i][j-1])%mod;
            if(s[i][j]=='+')dp1[i][j]=(dp1[i][j]+dp3[i][j])%mod,dp2[i][j]=dp4[i][j],dp3[i][j]=0;
			else if(s[i][j]=='*') dp2[i][j]=dp3[i][j],dp3[i][j]=0;
			else dp3[i][j]=(dp3[i][j]*10+(s[i][j]-'0')*dp2[i][j])%mod;
        }
    }
    printf("%lld",(dp1[n][m]+dp3[n][m])%mod);
    return 0;
}

B 矩形

太可惜了,考场上写出来 \(O(n^2 \log n)\) 做法但是 RE,敲的不对。

写对了有 \(64\) 分。

正解和我的思路很相似,但是存的东西不同。要存点的相对位置,看有多少组点可以上下匹配,然后再乘上系数。

需要离散化。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int M=500;
#define ll long long
#define ull unsigned long long
int n;
ll ans;
struct nd{
	int x,y,id;
	bool operator<(const nd &t){
		if(x!=t.x)return x<t.x;
		return y<t.y;
	}
}a[N];
vector<int> ve[N];
int siz[N];
int mxx,mnx=1e9,mxy,mny=1e9;
int id[N],cnt,B;
ull sta[N],tp;
ull t=998244353;
ull hashp(int x,int y){
	return t*x+y;
}
const ll SZ=1.8e6+3;
ll gx(int x,int y){
	int l=0,r=0;
	ll res=0;
	for(;r<siz[y];r++){
		while(ve[x][l]<ve[y][r]&&l<siz[x]-1)l++;
		if(ve[x][l]==ve[y][r])res++;
	}
	return res*(res-1)/2;
}
struct hash_map{
    struct data {
        ull u;
    	int v,nex;
    }e[SZ<<1];
	int h[SZ],cnt;
	int hash(ull u){return u%SZ;}
	int &operator[](ull u) {
		ll hu = hash(u);
    	for (int i=h[hu];i;i=e[i].nex){
    		if(e[i].u==u)return e[i].v;
		}
   	 	return e[++cnt]=data{u,0,h[hu]},h[hu]=cnt,e[cnt].v;
  	}
	void clear(){
		cnt=0;
    	memset(h,0,sizeof(h));
	}
}mp;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	#ifndef LOCAL
	freopen("rect.in","r",stdin);
	freopen("rect.out","w",stdout);
	#endif
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		a[i].id=i;
	}
	sort(a+1,a+n+1);
	int tmp=500;
	B=max(1,tmp);
	for(int i=1;i<=n;i++){
		if(a[i].x!=a[i-1].x){
			cnt++;
		}
		id[i]=cnt;
		ve[cnt].push_back(a[i].y);
	}
	for(int i=1;i<=cnt;i++){
		siz[i]=ve[i].size();
	}
	for(int i=1;i<=cnt;i++){
		if(siz[i]<=B){
			for(int j=0;j<siz[i];j++){
				for(int k=j+1;k<siz[i];k++){
					ull nowh=hashp(ve[i][j],ve[i][k]);
					ll val=mp[nowh];
					ans+=val;
					sta[++tp]=nowh;
				}
			}
			while(tp)mp[sta[tp--]]++;
		}
		else{
			for(int j=1;j<=cnt;j++){
				if((siz[j]>B&&j<i)||j==i)continue;
				ans+=gx(i,j);
			}
		}
	}
	cout<<ans;
	return 0;
}

C 集合

不可做。

D 倒水

\(52\) 分的 dp+性质:

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N=1e5+4;
int a[N],p[N];
int calc[N];
int cnt=0;
const int mod=998244353;
int ppow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=(res*a)%mod;
		a=(a*a)%mod,b>>=1;
	}return res;
}
void dfs(int x)
{
	if(x==n+1)
	{
		++cnt;cnt%=mod;
		for(int i=1;i<=n;i++) calc[i]+=p[i];
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(i==x) continue;
		int tmp=min(a[i]-p[i],p[x]);
		p[i]+=tmp,p[x]-=tmp;
		dfs(x+1);
		p[i]-=tmp,p[x]+=tmp;
	}
}
int q[N];
int ans[N],dp[401][401];
signed main()
{
	freopen("bottle.in","r",stdin);
	freopen("bottle.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	bool _=1;
	for(int i=1;i<=n;i++) cin>>a[i],_&=(a[i]==1);
	if(_)
	{
		int inv=ppow(n-1,mod-2);
		int pos=1;
		p[1]=1;
		for(int i=2;i<=n;i++)
		{
			p[i]=pos*inv%mod,pos=(pos+p[i])%mod;
		}
		pos=p[n],q[n]=0;
		for(int i=n-1;i>=1;i--)
		{
			q[i]=pos*inv%mod,pos=(pos+p[i])%mod;
		}
		for(int i=1;i<=n;i++) cout<<q[i]<<"\n";
		return 0;
	}
	if(n<=8)
	{
		p[1]=a[1];
		dfs(1);
		const int inv=ppow(cnt,mod-2);
		for(int i=1;i<=n;i++) calc[i]=(calc[i]*inv)%mod,cout<<calc[i]<<"\n";
		return 0;
	}
	int inv=ppow(n-1,mod-2);
	dp[1][a[1]]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=a[i];j++)
		{
			int p=inv*dp[i][j]%mod;
			for(int k=1;k<i;k++)
			{
				int v=min(j,a[k]);
				ans[i]+=p*(j-v),ans[i]%=mod;
				ans[k]+=p*v,ans[k]%=mod;
			}
			for(int k=i+1;k<=n;k++)
			{
				int v=min(j,a[k]);
				ans[i]+=p*(j-v),ans[i]%=mod;
				dp[k][v]+=inv*dp[i][j],dp[k][v]%=mod;
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
	return 0;
}

标签:const,noip,int,res,ll,long,模拟,mod
From: https://www.cnblogs.com/ccjjxx/p/18523237

相关文章

  • 【STL_list 模拟】——打造属于自己的高效链表容器
    一、list节点​list是一个双向循环带头的链表,所以链表节点结构如下: template<classT> structListNode { Tval; ListNode*next; ListNode*prve; ListNode(intx) { val=x; next=prve=this; } };二、list迭代器2.1、list迭代器与vector......
  • 2024.11.2 模拟赛
    2024.11.2模拟赛T1P11242碧树把\(n\)个点往外连即可。最终答案为\(n-\max_{i=1}^na_i+1\)T2P11243繁花感觉我的做法麻烦了,而且随机复杂度()显然的,从左往右看可以分层,遇到一次大于号分一次。对于每段,遍历一遍,每遇到一次小于号计算一次答案。如果不考虑等于号,这段的......
  • strlen函数的模拟实现
    首先我们先新建项目,并新建源文件然后先调用sring.h里的strlen函数看看该函数的效果可以看到strlen的结果为字符串"abc"的长度我们又知道对于字符串"abc"实际上在字符串尾部会存在\0,即字符串arr实际上是"abc\0"那么先定义自定义函数my_strlen使它的返回类型为int,接受的数组......
  • 易语言模拟真人动态生成鼠标滑动路径
    一.简介鼠标轨迹算法是一种模拟人类鼠标操作的程序,它能够模拟出自然而真实的鼠标移动路径。鼠标轨迹算法的底层实现采用C/C++语言,原因在于C/C++提供了高性能的执行能力和直接访问操作系统底层资源的能力。鼠标轨迹算法具有以下优势:模拟人工轨迹:算法能够模拟出非贝塞尔曲线的......
  • Python模拟真人动态生成鼠标滑动路径
    一.简介鼠标轨迹算法是一种模拟人类鼠标操作的程序,它能够模拟出自然而真实的鼠标移动路径。鼠标轨迹算法的底层实现采用C/C++语言,原因在于C/C++提供了高性能的执行能力和直接访问操作系统底层资源的能力。鼠标轨迹算法具有以下优势:模拟人工轨迹:算法能够模拟出非贝塞尔曲线的......
  • C++模拟真人动态生成鼠标滑动路径
    一.简介鼠标轨迹算法是一种模拟人类鼠标操作的程序,它能够模拟出自然而真实的鼠标移动路径。鼠标轨迹算法的底层实现采用C/C++语言,原因在于C/C++提供了高性能的执行能力和直接访问操作系统底层资源的能力。鼠标轨迹算法具有以下优势:模拟人工轨迹:算法能够模拟出非贝塞尔曲线的......
  • 《冰汽时代2》为何叫刁民模拟器?《冰汽时代2》详细玩法介绍
    《冰汽时代2》(Frostpunk2)是11bitstudios开发的一款城市建造和生存策略游戏,是2018年大受好评的《冰汽时代》的续作。这款游戏在发布前就受到了广泛关注,部分玩家戏称其为“刁民模拟器”,这主要是因为原作中的一些特点:为什么叫“刁民模拟器”?1.道德抉择:在《冰汽时代》中,玩家......
  • json-server详细模拟GET、POST、DELETE等接口数据教程
    引言在前端开发过程中,我们经常需要在后端API尚未就绪的情况下模拟接口数据。json-server是一个强大而灵活的工具,可以帮助我们快速创建一个模拟的RESTfulAPI。本文将详细介绍如何使用json-server来模拟GET、POST、PUT、PATCH、DELETE等常用的HTTP方法,以及如何处理复杂的数......
  • 单双链表(数组模拟)笔记
    单双链表(数组模拟)笔记如题,我们要使用数组来模拟链表这个数据结构区别于传统的结构体链表(动态链表):structnode{ intvalue; structnode*next;//指向下一个节点的指针}user_define_name;//调用链表的别称数组模拟链表(静态链表)的速度更快,但是对于空间的优化不如动态链表......
  • 第16章:MATLAB中的模拟方法(16/29)
    目录第16章:MATLAB中的模拟方法16.1模拟的基本概念16.2蒙特卡洛模拟16.2.1蒙特卡洛模拟的步骤16.2.2MATLAB实现蒙特卡洛模拟16.2.3代码解释16.3马尔科夫链模拟16.3.1马尔科夫链的基本概念16.3.2MATLAB实现马尔科夫链16.3.3代码解释16.4系统动态仿真16.4......