[#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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/180924.html
標籤：其他