首页 > 其他分享 >高一高考集训欢乐赛

高一高考集训欢乐赛

时间：2024-06-12 20:10:36浏览次数：12  
标签：int 高考 高一 long num define 集训 dp mod

image
注意细节

点击查看代码 
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair 
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 200000+5;
int n,m,a[N],b[N],c1,c2;char s[N];
int main()
{
	speed();
	freopen("grade.in","r",stdin);
	freopen("grade.out","w",stdout);
	cin>>n>>m;
	cin>>s+1;
	bool flag=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='.')
		{
			flag=1;
			continue;
		}
		if(flag)b[++c2]=s[i]-'0';
		else a[++c1]=s[i]-'0';
	}
	int wei=c2;
	for(int i=1;i<=c2;i++)
	{
		if(b[i]>=5)
		{
			for(int j=i;j>=1;j--)
			{
				if(b[j]>=5)
				{
					wei=j-1;
					b[wei]++;
					m--;		
					if(!m)break;
				}
			}
			break;	//	一定不能忘	
		}

	}
	if(b[0])//进位
	{
		flag=0;
		int tmp=c1;
		a[tmp]++;
		while(a[tmp]>=10)
		{
			a[tmp]-=10;
			a[tmp-1]++;
			tmp--;
		}
	}
	if(a[0])cout<<a[0];//进位
	for(int i=1;i<=c1;i++)cout<<a[i];
	if(flag)
	{
		cout<<".";
		for(int i=1;i<=wei;i++)cout<<b[i];
	}
	return 0; 
}

image
codeforces
从一道紫题变为了黄题
我们其实只需要确定IP地址前两部分，因为回文，IP地址后两部分可以确定,注意IP地址长度大于4小于12，然后就是搜索了,还要注意每个数都至少出现过一次
遍历前三部分比较方便，而且复杂度可以接受，所以就是\(O(255^3)\)

点击查看代码 
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair 
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 15;
int n,acc[N],used[N],tot;
vector <int> num,Ans[10005];
bool check(int x)
{
	if(!x)return 1;
	used[x%10]++;
	return check(x/10)&&acc[x%10];
}
bool huiwen(int a,int b,int c,int d)
{
	int len=num.size()-1;
//	if(len>11)return 0;
	for(int i=0;i<=len;i++)
	{
		if(num[i]!=num[len-i])return 0;
	}++tot;
	Ans[tot].pb(a);Ans[tot].pb(256);Ans[tot].pb(b);Ans[tot].pb(256);
	Ans[tot].pb(c);Ans[tot].pb(256);Ans[tot].pb(d);
//	for(int i=0;i<=len;i++)cout<<num[i]<<" ";
//	cout<<endl;
	return 1;
}
void del(int x)
{
	if(!x)return;
	used[x%10]--;
	del(x/10);
}
void pushup(int x)
{
	if(!x)return;
	pushup(x/10);
	num.pb(x%10);
}
bool hf()
{
	for(int i=0;i<=9;i++)
	{
//		cout<<i<<" "<<used[i]<<" "<<acc[i]<<endl;
		if(!used[i]&&acc[i])
		{
			return 0;
		}
	}
	return 1;
}
int start(int a,int b,int c)
{
	num.clear();
	int tmp=0;
	pushup(a/10);num.pb(a%10);
	pushup(b/10);num.pb(b%10);
	pushup(c/10);num.pb(c%10);
//	cout<<a<<" "<<b<<" "<<c<<endl;

//	for(auto v:num)cout<<v<<" ";
//	cout<<endl;
	int flag=0;
	flag=1;
	num.pb(num[0]);//最后一部分是一位数
	tmp+=huiwen(a,b,c,num[0]);
	if(num[1])//最后一部分是两位数
	{
		if(flag==1)num.pop_back();
		num.pb(num[1]);
		num.pb(num[0]);
		tmp+=huiwen(a,b,c,10*num[1]+num[0]);
		flag=2;
	}
	if(num[1]*10+num[2]*100+num[0]<=255&&num[2])//最后一部分是三位数
	{
		if(flag==2)
		{
			num.pop_back();
			num.pop_back();			
		}else if(flag==1)
		{
			num.pop_back();
		}
		num.pb(num[2]);
		num.pb(num[1]);
		num.pb(num[0]);
		tmp+=huiwen(a,b,c,num[1]*10+num[2]*100+num[0]);
	}
//	int sb;
//	{
//		cout<<"%%"<<a<<" "<<b<<" "<<c<<endl;
//		cout<<tmp<<" "<<"AC"<<endl;
//		cin>>sb;
//	}
	return tmp;
}

int main()
{
	speed();
//	freopen("ipadd.in","r",stdin);
//	freopen("ipadd.out","w",stdout);
	cin>>n;
	int a;
	for(int i=1;i<=n;i++)//IP length>=4 <=12
	{
		cin>>a;
		acc[a]=1;
	}
	ll ans=0;
	for(int i=0;i<=255;i++)
	{
		used[i%10]++;//一定要考虑0的情况
		if(check(i/10)&&acc[i%10])
		{
			for(int j=0;j<=255;j++)
			{
				used[j%10]++;
				if(check(j/10)&&acc[j%10])
				{
					for(int k=0;k<=255;k++)
					{
						used[k%10]++;
						if(check(k/10)&&acc[k%10]&&hf())
						{
							ans+=start(i,j,k);
						}
						used[k%10]--;
						del(k/10);
					}
				}
				used[j%10]--;
				del(j/10);
			}			
		}
		used[i%10]--;//回溯
		del(i/10);
	}
	cout<<ans<<endl;
	for(int i=1;i<=tot;i++)//输出方案
	{
		for(auto v:Ans[i])
		{
			if(v==256) cout<<".";
			else cout<<v;
		}
		cout<<endl;
	}
	return 0; 
}

C. 装饰

image
水题，找规律即可

点击查看代码 
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair 
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 200000+5;
int T;
int main()
{
	speed();
	freopen("decorate.in","r",stdin);
	freopen("decorate.out","w",stdout);
	cin>>T;
	ll a,b,c;
	while(T--)
	{
		cin>>a>>b>>c;
		
		if((a+b+c)==max({a,b,c}))
		{
			cout<<0<<endl;
		}else
		{
			priority_queue <ll> q;
			q.push(a);q.push(b);q.push(c);
			a=q.top();q.pop();b=q.top();q.pop();c=q.top();
			ll ans=0;
			ans=min((b+c),(a+b+c)/3);
			cout<<ans<<endl;
		}
	}
	return 0; 
}
/*
5
1 2 3
5 0 0
9 1 1
5 5 4
0 6 6
*/

D. 最大子矩阵Largest Submatrix

image

炸裂的暴力

点击查看代码 
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair 
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod=1e9+7;
ll n,m,ans,dp[1005][1005],a[1005][1005];char g[1005][1005],tmp[1005][1005];

int get(int i,int j)
{
	if(g[i][j]=='a')return 1;//0001
	if(g[i][j]=='b')return 2;//0010
	if(g[i][j]=='c')return 4;//0100
	if(g[i][j]=='w')return 3;//0011
	if(g[i][j]=='y')return 5;//0101
	if(g[i][j]=='z')return 7;//0111
	if(g[i][j]=='x')return 6;//0110
}
int main()
{					//w a,b
					//x b,c
					//y a,c
					//z a,b,c
	speed();
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	while(cin>>m>>n)
	{
		ans=0;
		for(int i=1;i<=m;i++)//w y z //w x z//x y z
		{
			cin>>g[i]+1;
		}
		for(int i=1;i<=m;i++)//w y z //w x z//x y z
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]=get(i,j);
			}
		}ans=0;
		for(int i=1;i<=m;i++)		
		{
			for(int j=1;j<=n;j++)
			{
				int now=1;
				for(int ii=i;ii<=m;ii++)		
				{
					for(int jj=j;jj<=n;jj++)
					{
						now=a[ii][jj];
						for(int iii=i;iii<=ii;iii++)		
						{
							for(int jjj=j;jjj<=jj;jjj++)
							{
								now&=a[iii][jjj];
								if(!now)break;
							}
							if(!now)break;
						}
						if(now)ans=max<ll>(ans,abs(ii-i+1)*(jj-j+1));
					}
					
				}
				
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

现在想正解，我们可以贪心一下，遍历三次，每一次，把能变为a/b/c的都变为相同的a/b/c,这样再找最大的
如何找呢，可以用类似玉蟾宫的思想，先处理出每一列列相同元素的长，然后用栈维护
image

点击查看代码 
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair 
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod=1e9+7;
ll n,m,ans,dp[1005][1005];char g[1005][1005],tmp[1005][1005];
void find(char tg)
{
//	cout<<"&&&&"<<endl;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
//			cout<<tmp[i][j];	
			dp[i][j]=0;
			if(tmp[i][j]==tg)dp[i][j]=dp[i-1][j]+1;
		}
//		cout<<endl;
	}
	stack <int> stk;
	for(int i=1;i<=m;i++)
	{
 		for(int j=0;j<=n+1;j++)
 		{
 			while(!stk.empty()&&dp[i][j]<dp[i][stk.top()])
 			{
 				int tmp=dp[i][stk.top()];//一定是最小的
 				stk.pop();
 				if(stk.empty())break;
// 				cout<<stk.top()<<endl;
 				ans=max<ll>(ans,tmp*(j-stk.top()-1));
// 				cout<<ans<<endl;
// 				stk.pop();
			}
			stk.push(j);
		}
	}
}
int main()
{					//w a,b
					//x b,c
					//y a,c
					//z a,b,c
	speed();
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	while(cin>>m>>n)
	{
		ans=0;
		memset(g,0,sizeof g);
		for(int i=1;i<=m;i++)//w y z //w x z//x y z
		{
			cin>>g[i]+1;
		}
		for(int p=1;p<=3;p++)
		{
			for(int x=1;x<=m;x++)
			{
				for(int y=1;y<=n;y++)
				{
					if(p==1&&(g[x][y]=='w'||g[x][y]=='y'||g[x][y]=='z'))
					{
						tmp[x][y]='a'-1+p;
					}
					else if(p==2&&(g[x][y]=='w'||g[x][y]=='x'||g[x][y]=='z'))
					{
						tmp[x][y]='a'-1+p;
					}
					else if(p==3&&(g[x][y]=='x'||g[x][y]=='y'||g[x][y]=='z'))
					{
						tmp[x][y]='a'-1+p;
					}else
					{
						tmp[x][y]=g[x][y];
					}
				}
			}	
			find('a'-1+p);		
		}
		cout<<ans<<endl;
//		cout<<"%%%%%%%%%"<<endl;
	}
	return 0;
}

E. 中国象棋

image

设计\(dp[i][j][k]\)有j列有1个炮,有k列有2个炮

点击查看代码 
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair 
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 105,mod=9999973;
ll n,m;ll dp[N][N][N];
ll calc(ll x)
{
	return 1ll*x*(x-1)%mod/2%mod;
}
int main()
{
	speed();
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
	cin>>n>>m;
//	for(int i=0;i<=m;i++)dp[0][i][m-i]=1;
	dp[0][0][0]=1;
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			for(int k=0;k<=m-j;k++)
			{
				dp[i][j][k]=dp[i-1][j][k]%mod;
				if(k>=1)dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1)%mod;
				if(k>=2)dp[i][j][k]+=dp[i-1][j+2][k-2]%mod*((j+2)*(j+1)/2)%mod;
				if(j>=1)dp[i][j][k]+=dp[i-1][j-1][k]*(m-k-j+1)%mod;
				if(j>=2)dp[i][j][k]+=dp[i-1][j-2][k]*calc(m-k-j+2)%mod;
				if(k>=1)dp[i][j][k]+=dp[i-1][j][k-1]%mod*(m-j-k+1)%mod*j%mod;
				dp[i][j][k]%=mod;
//				cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
//				ans+=dp[i][j][k];
			}
		}
	}
//	ll ans=0;
	for(int j=0;j<=m;j++)
		for(int k=0;k<=m;k++)//这里注意一下不是m-j
			ans=(ans+dp[n][j][k])%mod;
	cout<<ans<<endl;
	return 0; 
}

F. 奇妙的 Fibonacci

image

这题还是比较有思想的
首先证明\(F_i|F_j,则i|j\)
证明:\(F_i=f_{i-1}*f_2+f_{i-2}*f_1\)
\(F_i=f_{i-3}*f_2+f_{i-2}*f_3\)
同理:\(F_i=f_{i-k}*f_{k-1}+f_{i-k+1}*f_k\)
不停带入\(k\),可推广出\(f_{n+m}-f_{n-1}\times f_m+f_n \times f_{m+1}\)
显然\(f_i与f_{i-1}\)互质
类比\(gcd(n+m,m)=gcd(n,m)\)
\(gcd(f_{n+m},f_m)=gcd(f_n,f_m)\)
也就是说，对于相同的\(n,m\),上述两个同时成立\(f_i|f_j,i|j\)

设\(A_i\)为\(i\)的约数个数,\(B_i\)为\(i\)的约数平方和,\(C_i\)为\(i\)的最小质因数的幂是多少,\(D_i\)为\(i\)除去所有最小质因子后剩下的数
\(A_i\),\(B_i\)满足互质积性
\(设q为质因子\)
\(A_q=2,B_q=1+q^2,C_q=1,D_q=1\)
当\(gcd(i,q)=1,A_{iq}=A_i*A_q,B_{iq}=B_i*B_q,C_{iq}=1,D_{iq}=i\)
当\(i|q,A_{iq}=A_i/(C_i+1)*(C_i+2),B_{iq}=B_i*q^2+B_{D_i},C_{iq}=C_i+1,D_{iq}=D_i\)

注意\(f_2\)是所有\(f_i\)的约数,要特判

点击查看代码 
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair 
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e7+5,MAX = 1e7,mod=1e9+7;
ll A[N],B[N],C[N],D[N],pr[N],tot,n,q[N],c;bool vis[N];
void get()
{
	A[1]=1;B[1]=1;
	for(int i=2;i<=MAX;i++)
	{
//		cout<<i<<endl;
		if(!vis[i])
		{
			pr[++tot]=i;
			A[i]=2;
			B[i]=(1ll*i*i%mod+1)%mod;//(i*i是int必须加longlong)
			C[i]=1;
			D[i]=1;
		}
		for(int j=1;j<=tot;j++)
		{
//			cout<<j<<endl;
			ll num=pr[j]*i;
			if(num>MAX)break;
			vis[num]=1;
			if(i%pr[j]==0)//pr[j]是i的最小质因子 
			{	
				A[num]=A[i]/(C[i]+1)*(C[i]+2);
				C[num]=C[i]+1;D[num]=D[i];
				B[num]=(B[i]*1ll*(pr[j]%mod*pr[j])%mod+B[D[i]]%mod)%mod;
				
				
				break;
			}
			else//pr[j]变成了i*pr[j]的最小质因子 ,因为i的最小质因子还没有遍历到 
			{
				C[num]=1;
				B[num]=(B[i]*(pr[j]%mod*pr[j])%mod+B[i]%mod)%mod;
				//B[num]=B[i]*B[pr[j]]%mod;
				A[num]=A[i]*A[pr[j]]%mod;
				D[num]=i;				
				
			}

		}
	}
}
int main()
{
	speed();
	freopen("fibo.in","r",stdin);
	freopen("fibo.out","w",stdout);
	cin>>n;
	get();
	
	ll Q1,a,b;
	cin>>Q1>>a>>b>>c;
	
	q[1]=Q1;
	for(int i=2;i<=n;i++)
	{
		q[i]=(q[i-1]*a%c+b%c)%c+1;
//		cout<<q[i]<<endl;
	}
	ll A1=0,A2=0;
	for(int i=1;i<=n;i++)
	{
		A1+=A[q[i]]+(q[i]&1);
		A2=(A2+B[q[i]]+4*(q[i]&1))%mod;
		A1%=mod;A2%=mod;	
	}
	cout<<A1<<endl<<A2<<endl;
	return 0;
}

标签：int,高考,高一,long,num,define,集训,dp,mod
From： https://www.cnblogs.com/wlesq/p/18244164

相关文章

  • 2024/6/12高一高考集训欢乐赛题解
    目录赛时榜T1.Efim与奇怪的成绩T2.美丽的IP地址赛时榜你说得对，但是安禄山进长安——\(\huge{唐完了}\)。T1.Efim与奇怪的成绩贪心题+小模拟。先说结论：从小数点往后找到第一个可以四舍五入的位置，然后开始四舍五入。证明：首先，小数位数靠后的如果四舍五入，收益肯定是没前面的......
  • 高一高考集训欢乐赛
    大石碎胸口——万能青年旅店久违的头图渔王还想继续做渔王而海港已经不知去向此刻他醉倒在洗浴中心没有潮汐的梦胸口已暮色苍茫肥胖的城市递给他一个传统的方法来克制恐慌卖掉武器风暴喉咙换取饮食背叛能让你获得自由停电之后暂时摆脱了坚硬的时刻倒转......
  • M1 高考回忆
    高考回忆​ 已经过去了\(4\)天了，终于才想起要写这个。不得不说，翻过了这座山，还是思绪万千的，尽管心中总是在想“这也没什么大不了”，但是旁观者清，只有投入进去，在那种有天启即将到来的感觉的压迫下依旧能保有如此心态，才是比较难得的。可是我做不到，至少曾经吧。​ 我在高考前百日......
  • 2024 广东省队集训
    5.21试机赛B.朴素计数，写个dp算贡献系数就好了。C.网路流。建边\((s,i_0,C),(i_1,t,C),(i_0,j_1,dis_{i,j})\)，跑最大流即可。5.22A.首先分析一下贡献的形式。因为这玩意是凸的，所以我们可以钦定一个选点顺序，优先让第一个最大，其次让第二个最大，以此类推。很容易猜测选的点......
  • 2024年高考作文考人工智能，人工智能写作文能否得高分
    前言众所周知，今年全国一卷考的是人工智能，那么，我们来测试一下，国内几家厉害的人工智能他们的作答情况，以及能取得多少高分呢。由于篇幅有限，我这里只测试一个高考真题，我们这里用百度的文心一言和科大讯飞的讯飞大模型，本测试结果仅供参考，无评价好坏之分。2024高考作文1.1全国甲......
  • 2024年全国高考作文题目汇总
    2024全国高考作文题目汇总新课标I卷阅读下面的材料，根据要求写作。（60分）随着互联网的普及、人工智能的应用，越来越多的问题能很快得到答案。那么，我们的问题是否会越来越少？以上材料引发了你怎样的联想和思考？请写一篇文章。要求：选准角度，确定立意，明确文体，自拟标题；不要套作，不得抄......
  • 2024年高考生的抉择：计算机相关专业是否依然值得选择？
    2024年，计算机相关专业还值得选择吗？随着2024年高考的钟声渐行渐远，数百万高三学生们正忙着擦拭自己那满是压力汗水的额头，并面对人生中的重要抉择：选择大学专业。这可比选择今天中午吃什么难多了！这个决定就像一场巨大的甜品派对，你得在满桌子的蛋糕、布丁和冰淇淋中选一个最不容易......
  • 大一下集训队选拔赛
    rank2还需努力7paoxiaomo不爱DP很简单的一道DP赛时看错数据范围导致陷入思考误区其实只用求每个前缀和对应的答案然后往后合并区间一但有区间和等于pre[i]那么将该区间加入并且计算贡献如果区间和大于pre[i]那么该答案不符合点击查看代码#include<bits/stdc++.h>#de......
  • 2024年新高考2卷精选试题解答
    **(2024年新高考2卷19题)**已知双曲线$C:x^2-y^2=m\(m>0)$,点$P_1(5,4)$在$C$上,$k$为常数,$0<k<1$.按照如下方式依次构造点$P_n\\left(n=2,3,\cdots\right)$:过$P_{n-1}$作斜率为$k$的直线与$C$的左支交于点$Q_{n-1}$,令$P_n$为$Q_{n-1}$关于$y$轴的对称点,记$P_{n}$的坐标......
  • 2024年高考作文题目人工智能，热门AI
    当今社会的发展越来越迅速，人工智能也逐步走进我们的生活，连今年的高考作文题目也是人工智能高考作文：新课标I卷阅读下面的材料，根据要求写作。（60分）随着互联网的普及、人工智能的应用，越来越多的问题能很快得到答案。那么，我们的问题是否会越来越少？以上材料引发了你......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99