比赛链接:https://vjudge.csgrandeur.cn/contest/536129#problem

难度评测:

codeforces div3前四题。难度最高D题  1400分构造题。洛谷两红两橙。

有两个构造题。难度还可以,需要认真分析一下。不能想的太复杂,这两个题一开始我思路都错了一次,C题是读题错了。这两个构造题应该是codeforces绿蓝名的题。

剩下的题个人感觉F和G题还不错,H作为橙题有点水。校赛更倾向CDFG这种开拓性的题。板子题较少。如果这些题全部没问题,校赛应该能很好地解决百分之七十左右的题。保二争一应该有。ABE有校赛签到水平。

题解:

A:大意是模拟a+b输出a+b的值。

比较简单。scanf格式输入,然后输出即可。

code:

void solve()
{
	int a,b;
	scanf("%d+%d",&a,&b);
	cout<<a+b<<endl;
}


B:大意是给出一个四格矩阵,可以90度旋转,对于[a,b][c,d]判断是否可以满足a<b ,c<d,a<c,b<d。

四重循环遍历状态。每次交换一下相邻元素。4*90=360。满足一圈

code:

void solve()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	for(int i=1;i<=4;i++){
		if(a<b&&c<d&&a<c&&b<d){
			cyes;
			return;
		}
		int t = c;
		c=d;d=b;b=a;a=t;
	}
	cno;
}

C:构造题。大意是给出k和n。找到从1-n中k个数组成的序列满足最大的条件。条件为a[i]-a[i-1]的和。


对于长度符合的构造1,2,3...的差。不符合长度的直接+1输出即可。一开始读题读错了。忘记了应该有序。

code:

void solve()
{
	int k,n;
	cin>>k>>n;
	int a= 1;
	int c= 1;
	cout<<1<<' ';
	for(int i=2;i<=k;i++){
		if(a+c<=n&&(k-i+(a+c))<=n){
			cout<<a+c<<' ';
			a = a+c;
			c++;
		}else{
			cout<<a+1<<' ';
			a++;
		}
	}
	cout<<endl;
}


D:构造题。大意是给出一个数组。求是否存在一个x,对于所有(不是任意)是所有。满足a[i] = abs(a[i]-x)。使其数组递增。

这个题最开始分析错了。以为存在单调关系。这个题可以对于所有的逆序a[i],求一个最大的两个数平均值。然后看这个值是否可以满足。

为什么要找两个数的平均的值。因为这个值恰恰使得这两个数可以改变次序。

code:

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll maxt = 0;
	for(int i=2;i<=n;i++){
		if(a[i]<a[i-1]){
			maxt = max(maxt,upchu((a[i]+a[i-1]),2));
//			cout<<maxt<<endl;
//			cout<<a[i]<<' '<<a[i-1]<<endl;
		}
	}
	for(int i=1;i<=n;i++){
		a[i] = abs(a[i]-maxt);
		if(a[i]<a[i-1]){
			cout<<-1<<endl;
			return; 
		}
	}
	cout<<maxt<<endl;
}	


E题:大意是给出一个数组。去重排序后输出。

我第一个反应是可以拿unique这个函数去重,先排序,然后直接删掉后面的重复。当然这个题应该也可以用哈希表来做。不删的话也可以判断第一个逆序和相等。做法很多

code:


int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		ve.push_back(x);
	}
	sort(ve.begin(),ve.end());
	ve.erase(unique(ve.begin(),ve.end()),ve.end());
	cout<<ve.size()<<endl;
	for(int i=0;i<ve.size();i++){
		
		cout<<ve[i]<<' ';
	} 
	cout<<endl;
}


F题:大意是给出一个数n,求n!的质因子。对数量进行排序后输出cnt+质因子。

比较简单。第一个思路来的很快,因为map可以直接排序。保险起见,线性筛一遍质数ans边记录边除质因子,map进行存储,直接迭代器输出。这样做法应该是比较保守的。复杂度差不多nlogn。又是保险起见,因为这个算法跑的比较快。n我筛了一个大范围n*10.即使这样跑出来也就是几十ms。

code:


const int nn = 100010;
bool sign[nn]; 
vector<int> ve; 
map<int,int> mp;
void shai(){
	for(int i=2;i<nn;i++){
		if(!sign[i]) ve.push_back(i);
		for(int j=2;i*j<nn;j++){
			sign[i*j] = true;
		}
	}
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	shai();
	ll n;
	cin>>n;
	ll ans = 1;
	for(int i=1;i<=n;i++){
		ans *=i;
		for(int j=0;j<ve.size();j++){
			if(ve[j]>ans) break;
			else{
				while(ans%ve[j]==0) ans/=ve[j],mp[ve[j]]++;
			}
		}
	}
	map<int,int>::iterator it = mp.begin();
	while(it!=mp.end()){
		cout<<it->fi<<' '<<it->se<<endl;
		it++;
	}
}


G题:大意是给出一个x和y,求p,q满足gcd是x最小公倍数是y的数量。

分情况讨论。如果x<y是0,x=y是1.其他的就找满足的数量,然后翻个倍数。中间具体怎么操作?

如果pq满足是x的倍数。那么p一定可以由x乘以一个倍数。q一定可以由y除以一个倍数。前提是y%x=0。如果不等于也不要紧,因为if我们可以再判断一下。if里面我们直接判断题目中的条件即可。

code:


int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int x,y;
	cin>>x>>y;
	int a,b;
	int ans = 0;
	for(int i=1;i<=y/x;i++){
		a = x*i;
		b = y/i;
		if(a>b) break;
		if(__gcd(a,b)==x&&a*b/__gcd(a,b)==y) ans++; 
	} 
	if(x==y) cout<<1<<endl;
	else if(x>y) cout<<0<<endl;
	else cout<<ans*2<<endl;
}

H题:01背包板子题。大意是给出总钱数和m个商品。求购买的总价值。每个商品的价值等于  价格*价值系数。


正常跑一遍01背包。状态表示将+value[i]替换为+money[i]*value[i],难度较低。

code:


int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>money[i]>>value[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
			if(j<money[i]) f[i][j] = f[i-1][j];
			else f[i][j] = max(f[i-1][j],f[i-1][j-money[i]]+money[i]*value[i]);
		}
	}
	cout<<f[m][n];
}