526互联

第十三届山东省大学生程序设计竞赛

发布时间 2023-09-14 01:07:40作者: value0

第十三届山东省大学生程序设计竞赛

A. Orders

解题思路:

对订单进行升序排序。

遍历每一天，我们每天生成\(k\)件货物，到第\(i\)天就减去需要的，不够就是\(No\)。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll,ll> pii;
#define fi first
#define se second
int n,m,k;
void solve()
{
	scanf("%d %d",&n,&k);
	vector<pii> v(n + 1);
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld %lld",&v[i].fi,&v[i].se);
	}
	sort(v.begin()+1,v.end());
	ll sum = 0;
	ll last = 0;
	for(int i = 1;i<=n;i++)
	{
		sum += (v[i].fi - last) * k;
		last = v[i].fi;
		if(sum >= v[i].se)
		{
			sum -= v[i].se;
		}
		else
		{
			printf("No\n");
			return;
		}
	}
	printf("Yes\n");
	
}

int main()
{
	int t = 1;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
	
}

I. Three Dice

解题思路:

直接暴力分类讨论即可。

代码1:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll,ll> pii;
#define fi first
#define se second
int n,m,k;
void solve()
{
	ll a,b;
	scanf("%lld %lld",&a,&b);
	vector<int> black;
	black.push_back(2);
	black.push_back(3);
	black.push_back(5);
	black.push_back(6);
	map<int,bool> q;
	n = black.size();
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			for(int k = 0;k<n;k++)
			{
				int res = black[i] + black[j] + black[k];
				q[res] = true;
			
			}
		}
	}
	map<int,int> s;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			int res = black[i] + black[j];
			s[res] = 1;
		}
	}
	if(a == 0)
	{
		for(auto c : q)
		{
			if(c.fi == b)
			{
				puts("Yes");
				return;
			}
		}
		puts("No");
		return;
	}
	else if(a == 1)
	{
		for(auto c : s)
		{
			if(c.fi == b)
			{
				puts("Yes");
				return;
			}
		}
		puts("No");
		return;
	}
	else if(a == 4)
	{
		for(auto c : s)
		{
			if(c.fi == b)
			{
				puts("Yes");
				return;
			}
		}
		puts("No");
		return;
	}
	else if(a == 2)
	{
		if(b == 2 || b == 3 || b == 5 || b == 6)
		{
			puts("Yes");
			return;
		}
		else
		{
			puts("No");
			return;
		}
	}
	else if(a == 5)
	{
		if(b == 2 || b == 3 || b == 5 || b == 6)
		{
			puts("Yes");
			return;
		}
		else
		{
			puts("No");
			return;
		}
	}
	else if(a == 8)
	{
		if(b == 2 || b == 3 || b == 5 || b == 6)
		{
			puts("Yes");
			return;
		}
		else
		{
			puts("No");
			return;
		}
	}
	else if(a == 3)
	{
		if(b != 0)
		{
			puts("No");
			return;
		}
		else
		{
			puts("Yes");
			return;
		}
	}
	else if(a == 12)
	{
		if(b != 0)
		{
			puts("No");
			return;
		}
		else
		{
			puts("Yes");
			return;
		}
	}
	puts("No");
	
}

int main()
{
	int t = 1;
//	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
	
}

优雅的题解思路代码(推荐):

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll,ll> pii;
#define fi first
#define se second
int n,m,k;
int a[] = {0,1,0,0,4,0,0};
int b[] = {0,0,2,3,0,5,6};
void solve()
{
	scanf("%d %d",&n,&m);
	for(int i = 1;i<=6;i++)
	{
		for(int j = 1;j<=6;j++)
		{
			for(int k = 1;k<=6;k++)
			{
				if(a[i] + a[j] + a[k] == n && b[i] + b[j] + b[k] == m)
				{
					puts("Yes");
					return;
				}
			}
		}
	}
	puts("No");
	
}

int main()
{
	int t = 1;
//	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
	
}

G. Matching

解题思路:

公式变换：

\[\begin{align} i - j &= a_i - a_j\\ a_i - i &= a_j - j \end{align} \]

不难发现，\(a_i - i\)相同的可以分到同一集合中。且任一集合中的边都不会指向另一个集合。

所以，我们每次选取一个集合中\(a_i\)最大的两个点即可。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll,ll> pii;
#define fi first
#define se second
int n,m,k;
void solve()
{
	scanf("%d",&n);
	vector<ll> a(n + 1);
	map<ll,vector<ll>> q;
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		ll res = a[i] - i;
		q[res].push_back(a[i]);
	}
	ll ans = 0;
	for(auto &t : q)
	{
		vector<ll> &v = t.se;
		sort(v.begin(),v.end());
		for(int i = v.size()-1;i > 0;i--)
		{
			ll a = v[i];
			ll b = v[i-1];
			if(a + b > 0)
			{
				ans += a + b;
				i --;
			}
		}
	}
	printf("%lld\n",ans);
	
}

int main()
{
	int t = 1;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
	
}

D. Fast and Fat

解题思路:

  1. 二分队伍速度\(x\).

  2. 对于速度大于等于\(x\)的队员，他们的极限承重能力为\(w_j\),我们可进行公式推导：

    \[\begin{align} &v_i - (w_j - w_i) = x \\ &v_i - w_j + w_i = x\\ &v_i+w_i-x=w_j \\ &w_j = v_i+ w_i-x \end{align} \]

    所以，我们可以记录可背人队员的承重极限，然后和速度小于\(x\)的队员进比较，分配任务。

    贪心地想，从最轻的落后队员开始看，尽量让承重极限小的队员背他，以此类推。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll,ll> pii;
#define fi first
#define se second
int n,m,k;
void solve()
{
	scanf("%d",&n);
	vector<ll> v(n + 1),w(n + 1);
	vector<pair<ll,int>> a(n + 1);
	vector<pair<pair<ll,ll>,int>> q(n + 1);
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld %lld",&v[i],&w[i]);
		a[i] = {v[i] + w[i],i};
		q[i] = {{w[i],v[i]},i};
	}
	sort(q.begin() + 1,q.end());
	sort(a.begin() + 1,a.end());
	int l = 0;
	int r = 1e9 + 1;
	auto check = [&](int x)
	{
		
		vector<int> t,ans;
		vector<bool> st(n + 1);
		for(int i = 1;i<=n;i++)
		{
			if(q[i].fi.se < x)
			{
				st[q[i].se] = true;
				t.push_back(q[i].fi.fi);
			}
		}
		for(int i = n;i>=1;i--)	
		{
			if(!st[a[i].se])
			{
				ans.push_back(a[i].fi - x);
			}
		}
		reverse(ans.begin(),ans.end());
		if(ans.size() < t.size())
		{
			return false;
		}
		int idx = ans.size()-1;
		for(int i = t.size()-1;i>=0 && idx >= 0;i--)
		{
			while(idx >= 0 && ans[idx] < t[i])
			{
				idx --;
			}
			if(idx >= 0)
			{
				idx --;
				t[i] = 0;
			}
			else
			{
				break;
			}
		}
		if(t.empty() || t[0] == 0)
		{
			return true;
		}
		return false;
	};
	while(l + 1 < r)
	{
		int mid = l + r >> 1;
//		cout<<mid<<endl;
		if(check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	printf("%d\n",l);
	
	
}

int main()
{
	int t = 1;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
	
}

L. Puzzle: Sashigane

解题思路:

不难发现，我们围着块周围铺全覆盖的\(L\)型块即可。

一共n层，开头有了一层，我们还需要铺\(n-1\)层。

自己画图试一下就好。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;
typedef pair<ll,ll> pii;
#define fi first
#define se second
 

void solve()
{
	int n,a,b;
	scanf("%d %d %d",&n,&a,&b);
	int u = a;
	int d = a;
	int l = b;
	int r = b;
	printf("Yes\n%d\n",n-1);
	for(int i = 1;i <= n - 1;i++)
	{
//		cout<<i<<endl;
		//Èç¹ûÑ¡(u-1,l-1) 
		if(u > 1 && l > 1)
		{
			u --;
			l --;
			printf("%d %d %d %d\n",u,l,d - u, r - l);
		}
		else if(u > 1 && r < n)
		{
			u --;
			r ++;
			printf("%d %d %d %d\n",u,r,d - u,l - r);
		}
		else if(d < n && l > 1)
		{
//			cout<<1<<endl;
			d ++;
			l --;
			printf("%d %d %d %d\n",d,l,u - d,r - l);
		}
		else if(d < n && r < n)
		{
			d ++;
			r ++;
			printf("%d %d %d %d\n",d,r,u - d,l - r);
		}
//		printf("udlr : %d %d %d %d\n",u,d,l,r);
	}
}

int main()
{
	int t = 1;
//	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
	
}

E. Math Problem

解题思路:

首先，我们能够发现如果我们执行一次\(a\)操作，然后再执行一次\(b\)操作，那么除了花费增加了\(a + b\)，值没有任何变化。所以，如果我们能得到一个答案，那么一定是先将需要操作的\(b\)操作完，再进行\(a\)操作。

不难发现，如果我们一直进行\(b\)操作，那么\(n\)会在\(log_kn\)级的操作次数内变为\(0\)。也就是说，我们可以枚举分别执行了\(0,1,2...log_2n\)次\(b\)操作，然后在执行完了\(i\)次\(b\)操作后开始不断执行\(a\)操作直到求得答案。

如果我们在执行完了\(i\)次\(b\)操作后有执行了\(j\)次\(a\)操作，那么此次求得答案的花费就是\(i * a + j * b\)。

那么执行\(a\)操作的次数会不会超时呢？

公式推导:

\[\begin{align} f_0 &= n\\ f_i&=k*f_{i-1} +x,(0\leq x <k,i>0) \end{align} \]

暴力带入\(x = k + 1\)看上界规律:

\[\begin{align} f_0 &= n\\ f_1 &= k*n+x\\ & =k*n + k - 1\\ & =k*(n + 1) - 1 \\ f_2 &= k(k*n+x)+x\\ &= k^2*n + k*x+x\\ &= k^2*n + k*(k-1)+ (k - 1)\\ &=k^2*n +(k+1)*(k-1)\\ &=k^2*n +k^2-1\\ &=k^2*(n + 1) - 1\\ &......\\ f_p &= k^p*(n + 1)-1 \end{align} \]

假设进行完除法得到的当前数为\(cur\).那么如果进行了\(p\)次乘法操作，我们的可取值区间为:

\[[k^p,k^p*(n+1)-1] \]

即使\(k^p\)并不是\(m\)的倍数，只要\(k^p*(n+1)-1 - (k^p)\)即往后\(k^p*n-1\)个数中有\(m\)的倍数即可。

也就是说\(k^p*n-1 \geq m-1\)即可。

由上可知：乘法的最大执行次数大概也是\(log_km\)级别的。所以直接暴力即可。

所以，总时间复杂度为\(O(log_k{n} \times log_k{m})\)。

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;
typedef pair<ll,ll> pii;
#define fi first
#define se second

ll qmi(ll a,ll b)
{
	ll res = 0;
	while(b)
	{
		if(b & 1)
		{
			res = (res * a);
		}
		
	}
}

void solve()
{
	ll n,k,m,a,b;
	scanf("%lld %lld %lld %lld %lld",&n,&k,&m,&a,&b);
	if(n % m == 0)
	{
		printf("0\n");
		return ;
	}
	if(k == 1)
	{
		printf("-1\n");
		return;
	}
	ll ans = 1e18;
	i128 cur = n;
	for(int i = 0;;i++,n /= k)
	{
		if(n == 0)
		{
			ans = min(ans,i * b);
			break;
		}
		i128 l = n;
		i128 r = n;
		ll res = i * b;
		while(r / m == l / m && l % m)
		{
			l *= k;
			r = r * k + k - 1;
			res += a;
		}
		ans = min(ans,res); 
	}
	cout<<ans<<endl;
}

int main()
{
	int t = 1;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
	
}