2024 暑假友谊赛-热身2
知识点
1.分数a/b对998244353取模写成
//a/b取模mod写成 a%mod*ksm(b,mod-2)%mod;
题解
E. Beautiful Mirrors
1.令dpi-1为第1天走到第i-1天开心的期望天数，pi为第i天照镜子开心的概率，如果第i天询问成功，那么对期望天数的贡献为pi*（dpi-1+1），如果没有询问成功，这时候贡献的天数为dpi-1+1，根据题意要回到第一天，然后又要花dpi天，所以此时的贡献为（1-pi） * （dpi-1+1+dpi）
2.所以公式化简以后就是dpi=100（dpi-1+1）/pi
3.注意这里的pi指的是概率，实际概率为pi/100
4.最后就是线性递推
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
#define mod 998244353
int ksm(int a,int n)//a为底数，n为次方
{
int res=1;
while(n>0)
{
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}//快速幂模版
void solve()
{
int n;cin>>n;
vector<int>dp(n+1),p(n+1);
for(int i=1;i<=n;i++)
{
cin>>p[i];
dp[i]=(dp[i-1]+1)*100%mod*ksm(p[i],mod-2)%mod;//推导出来的公式但是把分数写成了取模的形式
}
//a/b取模mod写成 a%mod*ksm(b,mod-2)%mod;
cout<<dp[n];
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
B - RGB Boxes
1.很明显其实我们会想到暴力枚举来验证加起来是否相等，但是数据范围3000，O（n3）的复杂度肯定是过不去的
2.那么我们就思考如何用n2的方法来解决呢？枚举前两个数，再验证一下n-sum是不是剩下的这个数的倍数即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int r,g,b,n; cin>>r>>g>>b>>n;
int ans=0;
for(int i=0;i<=3000;i++)
{
for(int j=0;j<=3000;j++)
{
if(i*r+j*g==n) ans++;
else{
int k=n-i*r-j*g;
if(k%b==0&&k>0) ans++;//别忘了要大于0
}
}
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
C - 4/N
1.这两道题的思想其实是一样的，不过这里需要把公式变形一个可以验证第三个数的等式，那么化完就可以写成w=(1.0*N * n * h )/ (4 * n * h-N * n-N * h )
2.然后就是两层循环验证一下即可，验证当double型的w强转为int是不是值不变，因为题目说了答案都是整数
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n;cin>>n;
for(int h=1;h<=3500;h++)
{
for(int k=1;k<=3500;k++)
{
double w1=1.0*n*k*h/(4*k*h-n*k-n*h);
int w2=(int)w1;
if(w1==w2&&w1>0&&w1<=3500)
{
cout<<h<<" "<<k<<" "<<w2;
return;
}
}
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
C - AB Substrings
1.这题首先我们要知道，一串字符中中间部分在遍历一次找AB完以后，中间部分就是没有用的，然后我们只需要关注头和尾
2.把头尾分成三种，xa，bx，和ba，x可以为任意字符
3.然后我们要特殊处理一下ba这种，假如说有4个ba,那么连起来就是babababa，总共有3个AB，即当ba有n种，答案就是n-1种
4.xa要优先用到与ba这种类型结合，再与bx这种结合，为什么呢？假设我们有1个ba，一个xa，一个bx，如果xabxba，答案为1，如果xababx则答案为2，因为与ba结合以后，尾部会有一个a，可能可以让bx再来拼接再产生一个ab
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n; cin>>n;
int ans=0,ba=0,xa=0,bx=0;
while(n--)
{
int fla=0;
string s; cin>>s;
int len=s.size();
for(int i=0;i<s.size()-1;i++){
if(s[i]=='A'&&s[i+1]=='B')
{ ans++;
fla=1;
}
}
if(s[0]=='B'&&s[len-1]=='A') ba++;
if(s[0]!='B'&&s[len-1]=='A') xa++;
if(s[0]=='B'&&s[len-1]!='A') bx++;
}
if(ba>0) ans+=ba-1;//先拼ba把头尾贡献出b和a来
if(xa>0&&ba>0) ans++,xa--;//xa可以花一个接到上面接完的ba来，当然对应消耗一个
ans+=min(xa,bx);//xa与bx拼接，数量取决于少的那一个
if(bx>xa&&ba>0) ans++;//如果bx还有剩余，因为ba的尾还没接，所以可以再接一个bx
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
DivRem Number
1.首先要用小学知识知道，被除数=除数 * 商+余数
2.题设给定的n/m==n%m 所以我们可以把余数设为x，则根据点1有n=m*x +x
3.所以m=n/x-1，但是还要注意范围，因为m>x,所以n=m*（x+1）>(x+1 ) * x,所以我们枚举x的时候范围就是x * （x+1）<n
4.所以整体思路就是枚举可能合适余数，然后总和加上m即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int a[20][20];
void solve()
{
int n; cin>>n;
int ans=0;
//被除数=除数*商+余数，因为题目中的商和余数相等
//我们假设商和余数为x，n=m*x+x;
//所以m=n/x-1
//所以我们枚举余数 又因为除数大于余数 所以m>x;所以n=m*（x+1）>x*(x+1)
//所以枚举的范围（x+1）*x<n
for(int x=1;x*(x+1)<n;x++)
{
if(n%x==0) ans+=(n/x-1);//这里取余的原因是 因为一定要满足n=m*(x+1)这个等式，
//这个点很细 因为并不是枚举的每个x都满足这个等式
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}