首页 > 其他分享 >暑假集训CSP提高模拟12

暑假集训CSP提高模拟12

时间：2024-07-31 19:50:09浏览次数：15  
标签：12 cout int ll find long 集训 CSP define

T1
image
这题千万不要认为是莫反题
枚举质因子\(x,y\)，\(x,y<=998\),对答案的贡献为\(min(\lfloor{\frac{B}{x}}\rfloor,\lfloor{\frac{D}{y}}\rfloor)\)，再容斥一下即可
MD最后答案要取模啊

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
using namespace std;
const int mod=1e9+7;
ll A,B,C,D;
inline ll solve(ll B,ll D)
{
	ll ans=0;
	for(ll x=1;x<=998;x++)
	{
		for(ll y=1;y<=998;y++)
		{
			if(x+y>999||x>B||y>D)break;
			if(__gcd(x,y)!=1)continue;
//			cout<<x<<" "<<y<<endl;
//			cout<<B/x+D/y<<endl;
			ans=((min(B/x,D/y))*(x+y)%mod+ans)%mod;
//			ans%=mod;
		}
	}
	return ans;
}
int main()
{
	speed();
	cin>>A>>B>>C>>D;
	ll ans=0;
//	cout<<solve(B,D)<<endl;
	cout<<((solve(B,D)+solve(A-1,C-1)-solve(A-1,D)-solve(B,C-1))%mod+mod)%mod<<endl;
	
	return 0;
}
/*
5 8 3 6

999999999999 1000000000000 999999999999 1000000000000
*/

T2
image
读假题了，以为是一个一个换（MD我考试在干什么啊）
其实就是找行之间那些匹配，同理找列之间，我们发现是有传递性的，如\(1行可以与2行和3行匹配\)，那无论\(2,3行\)可不可以直接交换，都有一种可以通过\(1\)让他们交换位置

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
using namespace std;
const int mod=998244353,N=55;
ll n,k,a[N][N];
ll jie[N],fa[N],cnt[N],cnt2[N];
int find(int x)
{
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	}
	jie[0]=1;
	for(ll i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			bool chk=1;
			for(int x=1;x<=n;x++)
				if(a[i][x]+a[j][x]>k){chk=0;break;}
			if(chk)
			{
				if(find(i)!=find(j))
				{
					fa[find(i)]=find(j);
				}
				// hang[i]++;
			}
		}
		// hang[i]++;
		// cout<<i<<" "<<hang[i]<<endl;
	}
	ll ans=1;
	for(int i=1;i<=n;i++)
	{
		cnt[find(i)]++;
	}
	for(int i=1;i<=n;i++)if(cnt[i])ans=ans*jie[cnt[i]]%mod;
	// 	cout<<endl;
	// cout<<han<<endl;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			bool chk=1;
			for(int x=1;x<=n;x++)
				if(a[x][i]+a[x][j]>k){chk=0;break;}
			if(chk)
			{
				if(find(i)!=find(j))
				{
					fa[find(i)]=find(j);
				}
			}
		}
		// cout<<i<<" "<<lie[i]<<endl;
	}
	for(int i=1;i<=n;i++)
	{
		cnt2[find(i)]++;
	}
	for(int i=1;i<=n;i++)if(cnt2[i])ans=ans*jie[cnt2[i]]%mod;
	// for(int i=1;i<=n;i++)cout<<cnt2[i]<<" ";
	// 	cout<<endl;
	// if(!ans)
	// {
		// ans=jie[max(*max_element(cnt+1,cnt+1+n),*max_element(cnt2+1,cnt2+1+n))];
	// }
	cout<<ans<<endl;
	return 0;
}

T3
原题
image

记忆化搜索 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#pragma GCC optimize(10086)
#define ull unsigned long long
using namespace std;
const int N = 255;
const ull B=233;
int T,n,r;
struct ac
{
	double p;ll val;
}a[N];
bool vis[N];
unordered_map <ull,map<int,double>> dp[2];
//ll dp[15][15][1<<10];
ull calc()
{
	ull ans=0;
	for(int i=1;i<=n;i++)
	{
		ll cnt=vis[i];
		ans=ans*B+cnt;
	}
	return ans;
}
double dfs(int cnt,ull tmp,bool f)
{
	if(!cnt)return 0.0;
	if(dp[f][tmp][cnt])return dp[f][tmp][cnt]; 
	double p=1,res=0.0;
	for(int i=1;i<=n;i++)
	{
		if(vis[i])continue;
		vis[i]=1;
		res+=p*a[i].p*(a[i].val+dfs(cnt-1,calc(),1));
		p*=(1.0-a[i].p);
		vis[i]=0;
	}
	res+=p*dfs(cnt-1,tmp,0);
//	cout<<tmp<<" "<<setprecision(6)<<fixed<<res<<endl;
	return dp[f][tmp][cnt]=res;
}
int main()
{
	speed();
//	freopen("T3.in","r",stdin);
	cin>>T;
	while(T--)
	{
		cin>>n>>r;	
		memset(vis,0,sizeof vis);
		memset(a,0,sizeof a);
//		memset(dp,0,sizeof dp);
		dp[1].clear();dp[0].clear();
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].p>>a[i].val;
		}
		if(!r)
		{
			double p=1,res=0.0;
			for(int i=1;i<=n;i++)
			{
				if(vis[i])continue;
				vis[i]=1;
				res+=p*a[i].p;
				p*=(1.0-a[i].p);
				vis[i]=0;
			}
			res+=p;			
			cout<<0<<endl;
			continue;
		}

		cout<<setprecision(10)<<fixed<<dfs(r,0,1)<<endl;
//		break;
	}
	return 0;
}
/*
2 
10 5
0.5000 2 
0.3000 3 
0.9000 1
0.5000 2 
0.3000 3 
0.9000 1
0.5000 2 
0.3000 3 
0.9000 1
0.5000 2 
3 2 
0.5000 2 
0.3000 3 
0.9000 1
*/

正解，考虑设\(g_i\)表示修第\(i\)段水管的概率,则答案为\(ans=\sum g_ival_i\)
如何求\(g_i\)呢?,设\(f_{i,j}\)表示前\(i\)段内修复了\(j\)次的概率，显然转移就有当前位置修或不修(既不漏)

\[f_{i,j}=(i!=j)f_{i-1,j}\times (1-p_i)^{r-j}+(j\ne 0) f_{i-1,j-1}\times (1-(1-p_i)^{r-j+1}) \]

显然有\(g_i=\sum_{j=0}^{min{(i-1,r)}}f_{i-1,j}\times [1-(1-p_i)^{r-j}]\)注意啊边界，因为当前必须修
注意特判\(r=0\)的时候

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
using namespace std;
const int N=355;
struct ac
{
	double p;ll val;
}a[N];
int T,n,r;
double f[N][N],g[N],qpow[N][N];
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>T;
	while(T--)
	{
		cin>>n>>r;
		if(!r)
		{
			cout<<0.00000000<<endl;
			continue;
		}
		memset(f,0,sizeof f);	
		memset(a,0,sizeof a);memset(g,0,sizeof g);
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].p>>a[i].val;
			qpow[i][0]=1;
			for(int j=1;j<=r;j++)qpow[i][j]=qpow[i][j-1]*(1-a[i].p);
		}
		// f[1][0]=pow(1-a[1].p,r);
		// for(int i=2;i<=n;i++)f[i][0]=f[i-1][0]*pow(1-a[i].p,r);
		f[1][0]=qpow[1][r];f[1][1]=g[1]=1.0-qpow[1][r];
		for(int i=2;i<=n;i++)
		{
			for(int j=0;j<=min(i,r);j++)
			{		
				f[i][j]=(i!=j)*f[i-1][j]*qpow[i][r-j]+(j!=0)*f[i-1][j-1]*(1.0-qpow[i][r-j+1]);
			}
		}
		for(int i=2;i<=n;i++)
			for(int j=0;j<=min(i-1,r);j++)
				g[i]+=f[i-1][j]*(1.0-qpow[i][r-j]);
		double ans=0;
		for(int i=1;i<=n;i++)ans+=g[i]*a[i].val;
		cout<<setprecision(10)<<fixed<<ans<<endl;
	}
	return 0;
}

T4
分块，deque可以直接访问，服了
注意越界问题

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
// #pragma GCC optimize(3)
int n,a[N],q,sq,bl[N],cnt[340][N];
int be[N],ed[N];
deque <int> dq[340];
void T()
{
	cout<<"*************"<<sq<<" "<<n/sq<<" "<<endl;
	for(int i=1;i<=sq;i++)
	{
		cout<<dq[i].size()<<endl;
		for(auto s:dq[i])cout<<s<<" ";
		cout<<endl;
	}
	cout<<endl;
}
void init()
{
	for(int i=1;i<=n;i++)
	{
		bl[i]=(i-1)/sq+1;
		be[i]=(bl[i]-1)*sq+1;
		ed[i]=min(n,bl[i]*sq);
	}
	// for(int i=1;i<=n;i++)
	// {
	// 	cout<<be[i]<<" "<<ed[i]<<endl;
	// }
	for(int x=1;x<=n;x+=sq)
	{
		for(int i=be[x];i<=ed[x];i++)
			dq[bl[x]].pb(a[i]),++cnt[bl[x]][a[i]];
	}
	// T();
}
int tmp[N];
void update(int l,int r)
{
	if(bl[l]==bl[r])
	{
		int b=bl[l];
		int x=dq[b][r-be[l]];
		dq[b].erase(dq[b].begin()+(r-be[l]));
		dq[b].insert(dq[b].begin()+(l-be[l]),x);
		return;
	}
	// cout<<"*****&"<<endl;
	dq[bl[l]].insert(dq[bl[l]].begin()+ (l-be[l]),dq[bl[r]][r-be[r]]);
	// cout<<"*****"<<endl;
	++cnt[bl[l]][dq[bl[r]][r-be[r]]];
	--cnt[bl[r]][dq[bl[r]][r-be[r]]];
	dq[bl[r]].erase(dq[bl[r]].begin()+(r-be[r]));
	// cout<<"*****"<<endl;
	for(int b=bl[l]+1;b<=bl[r];b++)
	{
		int t=dq[b-1].back();
		dq[b].push_front(t);
		++cnt[b][t];
		dq[b-1].pop_back();
		--cnt[b-1][t];
	}
}
int query(int l,int r,int k)
{
	int res=0;
	if(bl[l]==bl[r])
	{
		int  b=bl[l];
		for(int i=l;i<=r;i++)
			if(dq[b][i-be[l]]==k)res++;
		return res;
	}
	res+=query(l,ed[l],k);
	
	for(int b=bl[l]+1;b<=bl[r]-1;b++)
	{
		res+=cnt[b][k];
	}
	res+=query(be[r],r,k);
	return res;
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("fk.out","w",stdout);
	cin>>n;
	sq=max(3,(int)sqrt(n));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	init();
	// cout<<"********"<<endl;
	cin>>q;
	int op,l=0,r=0,last=0,k;
	while(q--)
	{
		cin>>op>>l>>r;
		
		l=(l+last-1)%n+1;
		r=(r+last-1)%n+1;
		if(l>r)swap(l,r);
		if(op==1)
		{
			// cout<<"*****"<<endl;
			update(l,r);
			// cout<<"*****"<<endl;
		}
		else
		{
			cin>>k;
			k=(k+last-1)%n+1;
			last=query(l,r,k);
			cout<<last<<endl;
		}
	}
	return 0;
}

标签：12,cout,int,ll,find,long,集训,CSP,define
From： https://www.cnblogs.com/wlesq/p/18335160

相关文章

  • 『模拟赛』暑假集训CSP提高模拟12
    Rank正常偏下发挥吧。A.黑客签到题。题目中的关键点是只有\(x\)和\(y\)的和在区间\(\left[0,999\right]\)内才合法，因此我们只枚举和在这个范围内的两个值，寻找约分前的值即可，复杂度为\(\mathcal{O(999^2)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,......
  • 【C++BFS算法 二分查找】2812. 找出最安全路径
    本文涉及知识点C++BFS算法C++二分查找LeetCode2812.找出最安全路径给你一个下标从0开始、大小为nxn的二维矩阵grid，其中(r,c)表示：如果grid[r][c]=1，则表示一个存在小偷的单元格如果grid[r][c]=0，则表示一个空单元格你最开始位于单元格(0,0)。在......
  • 暑假集训CSP提高模拟12
    暑假集训CSP提高模拟12\(T1\)P171.黑客\(40pts\)将式子进行二维差分。考虑枚举\(\frac{i+j}{\gcd(i,j)}=t\)，并统计它能对答案产生的贡献。令\(\gcd(i,j)=1\)，这样的话才会不重不漏。推式子，有\(\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\fr......
  • 暑假集训CSP提高模拟 ∫[0,6] (x^2)/6 dx
    \[\text{暑假集训CSP提高模拟}\int^{6}_{0}\frac{x^{2}}{6}dx\]A.黑客显然这个题里只有\(999\)放在复杂度里是有可能对的，要么是\(999^{2}\)要么是\(999^{2}\log999\)，显然应该是前者.考虑枚举全部的最简分数，然后乘上去，算的时候直接算当前分母/分子是最简分式的几倍（注意上......
  • 暑假集训csp提高模拟12
    赛时rank47，T1100,T20,T30,T420做题策略不好，没做T2，死在T4上了。感觉赛时就是唐。T1黑客考虑枚举结果，如果存在贡献，那么一定有\(i+j=k\&gcd(i,j)=1\)，统计一下有多少组即可点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//usingnamespace__gnu_pbds;......
  • 洛谷题单指南-前缀和差分与离散化-P1083 [NOIP2012 提高组] 借教室
    原题链接：https://www.luogu.com.cn/problem/P1083题意解读：已知第i天有r[i]个教室可以供租借，有m个租借教室的订单，第i订单需要在第s[i]~t[i]天区间内租借d[i]个教室，计算是否全部订单都能满足，如果不满足要输出从第几个订单开始不满足。解题思路：1、朴素做法枚举1~m个订单，通过差分......
  • 基于ads1292的心电信号采集之芯片关键点备忘
    一前记团队在作基于ads1292的心电数据采集时候，遇到了一些问题。这里做一个记录和备忘。也希望能帮的到同样遇到困难的朋友。 二关注点1reset引脚不能悬空，这个悬空的时候，笔者发现ads1292无法正常工作。  2.start信号在单独使用的时候，不要接GND......
  • 嵌入式学习第12天——C语言循环结构
    循环结构什么是循环代码的重复执行，就叫做循环。循环的分类无限循环：程序设计中尽量避免无限循环（程序中的无限循环必须可控）。有限循环：循环限定循环次数或者循环的条件。循环的构成循环体循环条件当型循环的实现while语法： while(循环条件) { 循环语句；......
  • 21LTR.com_Scene1_2.120靶机
    getshell主机发现，端口目录扫描只有一个logs目录，接着往下扫访问首页，检查源代码，发现一组账号密码，可能是ssh，也可能是ftp的访问logs接口，没有权限尝试利用发现的账号密码，ssh没有成功，尝试ftp注意在windows上什么没有，用kali连接下载到本地查看一下拼接访问logs目录......
  • 瑞士ABB苏黎世张力控制器PFEA112-20
    其特点是控制电路结构简单、成本较低，机械特性硬度也较好，能够满足一般传动的平滑调速要求，已在产业的各个领域得到广泛应用。但是，这种控制方式在低频时，由于输出电压较低，转矩受定子电阻压降的影响比较显著，使输出大转矩减小。另外，其机械特性终究没有直流电动机硬，动态转矩能力和静态......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99