快捷搜索:

codeforces 711 div2 ( A-C )

A. GCD Sum

思路:暴力就完事

#include<bits/stdc++.h>
using namespace std;
//#define long long ll
long long all(long long x)
{
          
   
	long long total=0;
	while(x)
	{
          
   
		total+=x%10;
		x/=10;
	}
	return total;
}
int main()
{
          
   
	int t;
	cin>>t;
	while(t--)
	{
          
   
		long long  n;
		cin>>n;
		while(__gcd(n,all(n))==1)	
		{
          
   
			n++;
		}
		cout<<n<<endl;
	}
}

B. Box Fitting

思路:优先队列存放最大值,分为不够放和够放两种情况

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll a[N];
int n,w;
int main()
{
          
   
	int t;
	cin>>t;
	while(t--)
	{
          
   
		cin>>n>>w;
		for(int i=0;i<n;i++)
		{
          
   
			cin>>a[i];
			//尽量把数量多的放第一排 
		}
		sort(a,a+n);
		priority_queue<int> q;
		int ans=0;
		for(int i=n-1;i>=0;i--)
		{
          
   
			if(q.empty())//如果用完了 
			{
          
   
				q.push(w);
				ans++;
			}
			if(q.top()<a[i])//不够减 
			{
          
   
				q.push(w-a[i]);
				ans++;
			}
			else//够减 
			{
          
   
				if(q.top()!=a[i])//两者不相等 
				{
          
   
					int r=q.top();
					q.pop();
					q.push(r-a[i]);
				}
				else
				{
          
   
					q.pop();
				}
			}
		}
		cout<<ans<<endl;
	}
}

C. Planar Reflections

思路:简单递推 d p dp dp

设置 d p [ i ] [ j ] dp[i][j] dp[i][j]为当前还有 i i i架飞机,且当前衰变周期为 j j j

递推公式 d p [ i ] [ j ] = d p [ m − i ] [ j − 1 ] + d p [ i − 1 ] [ j ] dp[i][j] = dp[m-i][j-1]+dp[i-1][j] dp[i][j]=dp[m−i][j−1]+dp[i−1][j] 注意先对 j j j循环

#include<bits/stdc++.h>
using namespace std;
//递推公式挺好找的,前面有i个飞机,当前的衰变周期为j 
//dp[i][j]=dp[m-i][j-1]+dp[i-1][j]
const int N = 1005;
long long dp[N][N];
const int MOD = 1e9+7;
int main()
{
          
   
	int t;
	cin>>t;
	while(t--)
	{
          
   
		int m,n;
		cin>>m>>n;
		//不剩下墙的时候为1 
		for(int j=1;j<=n;j++)
		{
          
   
			dp[0][j]=1;
		}
		//i个粒子衰变为1的时候不管怎么跑都只有i个
		for(int i=1;i<=m;i++)
		{
          
   
			dp[i][1]=1;
		}	
		for(int j=1;j<=n;j++)
		{
          
   
			for(int i=1;i<=m;i++)
			{
          
   
				dp[i][j]=(dp[m-i][j-1]+dp[i-1][j])%MOD;
			}
		}
		cout<<dp[m][n]<<endl;
	} 
}
经验分享 程序员 微信小程序 职场和发展