[ARC145C] Split and Maximize
Little Fresh Conclusion Question.
First gazes can be made to know the construction scheme that maximizes the result.
Then consider how making the result constant produces a different number of scenarios.
The principles of addition and multiplication are discussed separately, and then it pushes on to Cattelan numbers, which turn out not to even require a combinatorial number; just take the remainder as you multiply.
Click to view code
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int mod=998244353;
const int maxn=4e5+10;
const int inf=1e9+7;
int n;
int qw(int x,int y)
{
int ans=1;
while(y)
{
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
// #else
// freopen("","r",stdin);
// freopen("","w",stdout);
#endif
cin>>n;
int ans=qw(2,n);
for(int i=n+2;i<=2*n;i++)ans=ans*i%mod;
cout<<ans;
return 0;
}
[ABC026D] Takahashi-kun ball No.1
At first glance, it seems that the function is not mono-increasing as if it can only simulate annealing (which I can't do), and at second glance, I realize that according to the requirements of the question, we only need to find a set of feasible solutions, so the dichotomy, even if it can't find all the solutions, must eventually stay at one of the correct ones, and therefore feasible.
After writing the sample found that the error is very large, how to adjust can not be adjusted, in a fit of anger directly to the handover, and then passed?
Click to view code
#include <bits/stdc++.h>
#define int long long
#define pi 3.141592653589793
using namespace std;
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int mod=998244353;
const int maxn=4e5+10;
const int inf=1e10+7;
double a,b,c;
bool ch(double x)
{
return a*x+b*sin(c*x*pi)>100;
}
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
// #else
// freopen("","r",stdin);
// freopen("","w",stdout);
#endif
cin>>a>>b>>c;
double l=1,r=1e9+7;
for(int i=1;i<=6e6;i++)
{
double mid=(l+r)/2.00;
if(ch(mid))r=mid;
else l=mid;
}
printf("%.10lf",l);
return 0;
}
[ABC204D]Cooking
A more familiar routine.
After transforming the question twice you can get a 01 backpack and then we just do it.
Click to view code
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int mod=998244353;
const int maxn=4e5+10;
const int inf=1e9+7;
int n,a[maxn],sum;
int dp[120][200000];
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
// #else
// freopen("","r",stdin);
// freopen("","w",stdout);
#endif
cin>>n;
for(int i=1;i<=n;i++)a[i]=read(),sum+=a[i];
for(int i=1;i<=n;i++)
{
for(int j=sum/2;j>=a[i];j--)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
}
}
cout<<sum-dp[n][sum/2];
return 0;
}
[ABC322C] Festival
I had come to see D, but couldn't, so went to see C. I found out that I can use water.
An unadulterated deuce.
Click to view code
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int mod=998244353;
const int maxn=4e5+10;
const int inf=1e9+7;
int n,m,a[maxn];
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
// #else
// freopen("","r",stdin);
// freopen("","w",stdout);
#endif
cin>>n>>m;
for(int i=1;i<=m;i++)a[i]=read();
for(int i=1;i<=n;i++)
{
int pos=a[lower_bound(a+1,a+m+1,i)-a];
cout<<pos-i<<endl;
}
return 0;
}