时间戳

首页 > 技术文章 > 10.18号题解报告

10.18号题解报告

william4s 2020-10-19 20:05 原文

[#818. Johann Numbers ]

题目链接#

思路：一条签到题，暴力得把枚举得到的放到vis里就可以了。(也可以用map)

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int N=1e9+5;
bool vis[N];
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	ll x;
	cin>>x;
	vis[x]=1;
	ll ans=1;
	while(1)
	{
		if (x%5!=0)
		{
			x+=2;
		}
		else
			x/=5;
		if (!vis[x])
		{
			vis[x]=1;
			ans++;
		}
		else
			break;
	}
	cout<<ans;
	return 0;
}

[#819. Fishing ]

题目链接[#](

思路：二维前缀和区域块的和方便表示，二分法枚举k。

二维前缀和推导公式是：

\(b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]\);

点\((x_1,y_1)\)到\((x_2,y_2)\)区域的和表达方式是：

\(b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1];\)

画一张图能更好得理解

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
ll a[1010][1010],b[1010][1010];
ll M;
struct Fish
{
	ll k,S;
};
Fish fun(ll k)
{
	ll maxn=-1;
	for (ll i=1; i+k-1<=M; i++)
		for (ll j=1; j+k-1<=M; j++)
		{
			ll x1=i,y1=j,x2=i+k-1,y2=j+k-1;
			ll tem=b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1];
			maxn=max(maxn,tem);
		}
	return {k,maxn};
}
Fish ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin>>n>>m;
	M=max(m,n);
	for (ll i=1; i<=M; i++)
	{
		for (ll j=1; j<=M; j++)
		{
			if (i<=n&&j<=m)
				cin>>a[i][j];
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
		}
	}
	ll s;
	cin>>s;
	ll l=1,r=M,mid;
	Fish f;
	while(l<=r)
	{
		mid=(l+r)/2;
		f=fun(mid);
		if (f.S>=s)
		{
			ans=f;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<ans.k<<' '<<ans.S;
	return 0;
}

[#820. Round Johann]

题目链接[#](

思路:用数组\(tim\)存储轮流的一个用时，当一个Johann的程序以及编写完成，当前数组会为0。这样可以方便我们直接用\(i\) \(mod\) \(n\)来表示当前时间是第几个。最后再把时间片段前缀和一下，这样就可以直接表示询问时间

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int N=1e4+5;
const int TT=1e8+5;
ll t[N],sum;
ll tim[TT]; 
int main()
{
	ios::sync_with_stdio(false); //关闭同步，加速cin,cout,此时不可用scanf 
	cin.tie(0);
	cout.tie(0);
	ll n,T,dis,q;
	cin>>n>>dis;
	for (ll i=0; i<n; i++)
	{
		cin>>t[i];
	}
	bool pd=1;
	ll cnt=1;
	while(pd)
	{
		for (ll i=0;i<n;i++)
		{
			tim[cnt++]=dis;
			t[i]-=dis;
			if (t[i]<0) //并不用担心tim[i]为0或者负数 
			{
				tim[cnt-1]+=t[i];
				t[i]=0;
			}
		}
		pd=0;
		for (ll i=0;i<n;i++)
			if (t[i]>0)
				pd=1;
	}
	for (ll i=1;i<=cnt;i++)
		tim[i]+=tim[i-1];

	cin>>q; 
	while(q--)
	{
		ll Q;
		cin>>Q;
		ll ans=upper_bound(tim+1,tim+cnt+1,Q)-tim-1;   //upper_bound是内置的二分模板函数，返回值为一个地址 
		ans=ans%n;
		cout<<ans<<'\n';
	}

return 0;
}

[#821. Work-Life Balance]

题目链接[#](

思路:

使用$dp[i][j][0/1] $表示已经选了i块砖头，左右重量差为j，因此设置k用“坐标零点”，0表示左边更重，1表示右边更重的方案数，转移只需要枚举接下来使用哪种砖头即可，放在哪一侧可以根据i的奇偶性来决定。

\(dp[i][j+w[k]*sign[i\)%\(2]]\)\(=(dp[i][j + w[k]*sign\)\([i\) % \(2]]+dp[i-1][j]);\)

(听队友说了两遍，还是没懂hhhh，最后自己回去复盘时候弄懂了)

#include<bits/stdc++.h>//补题QAQ 
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int N=105;
const int MOD=1e9+7;
ll a[N],dp[N][2*N];
int pd[2]={-1,1};
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	ll n,k,m;
	cin>>n>>k>>m;
	for (ll i=1;i<=n;i++)
		cin>>a[i];
	dp[0][k]=1;//initialization
	//dp[第几个][平衡力]
	for (ll i=1;i<=m;i++)
		for (ll j=0;j<=2*k;j++)
		{
			for (ll l=1;l<=n;l++)
			{
				ll tem=j+pd[i%2]*a[l];
				if (tem>=0&&tem<=2*k)
					dp[i][tem]=(dp[i-1][j]+dp[i][tem])%MOD;//选第i个时，平衡力为j（k为零点），选之前的状态是dp[i-1][j] 
				

			}
		}
	ll sum=0;
	for(ll i=0;i<=2*k;i++)
		sum=(sum+dp[m][i])%MOD;
	cout<<sum;
	return 0;

}

推荐阅读