总结 | #寒假营第一场#
A. A+B Problem(WA了3发）
考点：模拟，枚举
题意：给一个正整数n，找出最小的正整数x让n=n*x，把n的个位数变成0
为什么错？以为只需要把2和5抽出来单独讨论即可，漏了偶数与5的乘积也可以是得到0
AC代码：
void whale_solve() {
int n;cin>>n;
int a=n%10;
int x=-1;
if(a==0) x=1;
else if(a==2||a==4||a==6||a==8) x=5;
else if(a==5) x=2;
else x=10;
cout<<x;
}
C. Array Covering (WA了2发）
考点：排序，贪心
题意：给个数组和下标l,r,把(l,r)里所有数变成区间端点的较大值，求数组和的最大值
为什么错？把开区间看成了闭区间
AC代码：
void whale_solve() {
int n;cin>>n;
vector<int>a(n),b(n);
for(int i=0;i<n;i++){
cin>>a[i];b[i]=a[i];
}
sort(a.begin(),a.end());
int ans=a[n-1]*(n-2)+b[0]+b[n-1];
cout<<ans;
}
B. Card Game (WA了6发）
考点：贪心，组合数
题意：把2*n张牌分给小红，小苯，小苯可以任意排列自己的牌，然后比较两人当前手牌中的最前一张，数字大的一方把牌移除并加一分，另一方不变，直到有一个人没有牌了。求让小苯获得最多分数的排列方式
为什么错？以为只要小苯的把大于n的牌都排在最前面就能最大，实际上只需大于小红的最小牌就行
AC代码：
#define int long long
const int P=998244353;
vector<int>pailie(200005,1);
void pl(){for(int i=1;i<=200005;i++) pailie[i]=(pailie[i-1]*i)%P;}
void whale_solve() {
int n;cin>>n;
vector<int>a(n),b(n);
int cnt=0;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
sort(b.begin(),b.end());
for(int num:a){
if(num>b[0]) cnt++;
}
int ans=(pailie[cnt]*pailie[n-cnt])%P;
cout<<ans;
}
A. A+B Problem (unfinished)
考点：模拟，快速幂，取模运算，枚举
题意：太长了自己去看吧。。。。。。
为什么错？太麻烦了不想写（buhsi)，取模运算取得不够彻底，快速幂不够熟练，以及取一个数的个十百千位时错用了string（如果灯表示的是0034，那么数字就是34，转换成字符不好补前导0）
AC代码：
#define int long long
const int P=998244353;
//灯的开关状态压缩成01字符串
vector<string>ga={
"1110111","0010010","1011101","1011011","0111010",
"1101011","1101111","1010010","1111111","1111011"
};
//快速幂
int km(int a,int b){
int ans=1;
a%=P;
while(b){
if(b&1) ans=ans*a%P;
a=a*a%P;
b>>=1;
}
return ans;
}
//单独算100的-1次方取模
const int MOD=km(100,P-2);
void whale_solve() {
int sum=0;
int C;cin>>C;
vector<int>p(8);
vector<int>q(10,1);
//计算出现每个数字的概率
for(int i=1;i<=7;i++){
cin>>p[i];
for(int j=0;j<10;j++){
if(ga[j][i-1]=='1') q[j]=((q[j]%P)*(p[i]%P))%P*MOD%P;
else q[j]=((q[j]%P)*((100-p[i])%P))%P*MOD%P;
}
//cout<<q[0]<<" ";
}
//cout<<q[0]<<endl;
vector<int>a(4),b(4);
//枚举A和B的大小并计算概率
for(int A=0;A<=C;A++){
int B=C-A;
a[0]=A/1000;a[1]=A/100%10;a[2]=A/10%10;a[3]=A%10;
b[0]=B/1000;b[1]=B/100%10;b[2]=B/10%10;b[3]=B%10;
int pa=1,pb=1;
for(int i=0;i<4;i++){
pa=(q[a[i]]%P)*(pa%P)%P;
pb=(q[b[i]]%P)*(pb%P)%P;
}
int ans=((pa%P)*(pb%P))%P;sum=(sum%P+ans%P)%P;
}
cout<<sum;
}
拓展：取模运算模版
template<const int M = 1e9 + 7>
struct MInt {
using LL = long long;
int x;
MInt(int x = 0) : x(norm(x)) {}
MInt(LL x) : x(norm(x % M)) {}
inline int norm(LL x) const {if (x < 0) x += M; if (x >= M) x -= M; return x;}
inline MInt ksm(MInt x, LL y) const {return x ^= y;}
inline int val() const {return x;}
inline MInt operator - () const {return MInt(norm(M - x));}
inline MInt inv() const {assert(x != 0 ); return *this ^ (M - 2);}
inline MInt& operator *= (const MInt& rhs) {x = LL(x) * rhs.x % M; return *this;}
inline MInt& operator += (const MInt& rhs) {x = norm(x + rhs.x); return *this;}
inline MInt& operator -= (const MInt& rhs) {x = norm(x - rhs.x); return *this;}
inline MInt& operator /= (const MInt& rhs) {return *this *= rhs.inv();}
inline MInt& operator ^= (LL y){
LL ans = 1;
while(y){
if(y & 1) ans = ans * x % M;
x = LL(x) * x % M;
y >>= 1;
}
x = ans;
return *this;
}
inline friend MInt operator * (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res *= rhs; return res;}
inline friend MInt operator + (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res += rhs; return res;}
inline friend MInt operator - (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res -= rhs; return res;}
inline friend MInt operator / (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res /= rhs; return res;}
inline friend MInt operator ^ (const MInt& lhs, LL y) {MInt res = lhs; res ^= y; return res;}
inline friend istream& operator >> (istream& is, MInt& a) {LL v; is >> v; a = MInt(v);return is;}
inline friend ostream& operator << (ostream& os, const MInt& a) {return os << a.val();}
};
using Z = MInt<998244353>;
vector<Z> a(8),p(10,1);
G. Digital Folding (WA了INF发)
考点：构造，按位贪心
题意：给定区间[l,r]，求里面翻转后最大的数
为什么错? 1.忘了去前导0。2.忘了有l的约束。3.以为末位是9就一定最大。4.longlong类型得用stoll。。。。。。(反正还有很多)
AC代码：
//翻转函数，可去前导0
void fz(int x){
string sx=to_string(x);
int cnt=0;
for(int i=sx.size()-1;i>=0;i--){
if(sx[i]=='0') cnt++;
else break;
}
for(int i=sx.size()-cnt-1;i>=0;i--) cout<<sx[i];
}
void whale_solve() {
int l,r;cin>>l>>r;
string sl=to_string(l),sr=to_string(r);
int n1=sr.size(),n2=sl.size();
string t="1",s="";
for(int i=0;i<n1-1;i++) t+='0';//构造100...00
if(sr==t){
if(l==r) fz(r);
else fz(r-1);
return;
}else{
if(n1==n2){
int index=-1;
for(int i=0;i<n1;i++){
if(sl[i]!=sr[i]){
index=i;break;
}
}
//cout<<index<<endl;
if(index==-1) s+=sr;
else{
string ni=sr.substr(0,index+1);
ni+=string(n1-index-1,'9');//构造...99
//cout<<ni<<endl;
if(ni==sr) s+=sr;
else if(sr[0]=='1'){
if(index==n1-1) s+=sr;
else{
s+=sr.substr(0,index);
s+=sr[index]-1;
s+=string(n1-1-index,'9');
}
}else{
if(index==n1-1) s+=sr;
else{
s+=sr.substr(0,index);
s+=sr[index]-1;
s+=string(n1-1-index,'9');
}
}
}
}else{
sl=t.substr(0,n1-1);sl+='1';//构造100...001
int index=-1;
for(int i=0;i<n1;i++){
if(sl[i]!=sr[i]){
index=i;break;
}
}
if(index==-1) s+=sr;
else{
string ni=sr.substr(0,index+1);
ni+=string(n1-index-1,'9');
if(ni==sr) s+=sr;
else if(sr[0]=='1'){
if(index==n1-1) s+=sr;
else if(index==n1-2&&r%10==9) s+=sr;//10...65 10...89
else{
s+=sr.substr(0,index);
s+=sr[index]-1;
s+=string(n1-1-index,'9');
}
}else{
s+=sr.substr(0,index);
s+=sr[index]-1;
s+=string(n1-1-index,'9');
}
}
}
//cout<<sl<<endl;
int is=stoll(s);
fz(is);
}
}
H. Blackboard (unfinished)
考点：前缀和，位运算，dp
题意：有n个整数相加，现在将若干个'+'换成'|'，求有多少种换法可以让换前换后结果相等。
最初想法：找到几段最长的可随意变换符号的数段，其余固定为'+'。
正确思路：要想结果相等则需要连续数段在二进制的每一个位置上最多只能有一个1,那现在设dp[i]表示1~i的换法，在其中找到满足条件的最小的j，就有dp[i]=dp[i]+dp[i-1]+...+dp[j]
AC代码：
using ll=long long;
const ll P=998244353;
void whale_solve() {
int n;cin>>n;
vector<ll>a(n+1),pre(n+1);
int last=0;
//记录i前面离得最近的非零数字的位置
//0对算式没有任何影响，跳过0可以节省时间
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=last;
if(a[i]>0) last=i;
}
vector<ll>dp(n+2),s(n+2);
//初始化
dp[1]=1;s[1]=1;
for(int i=1;i<=n;i++){
int j=i;ll cal=0;
while(j>0&&(cal&a[j])==0){
cal|=a[j];j=pre[j];
}//判断是否符合条件
dp[i+1]=(s[i]-s[j]+P)%P;//状态转移
s[i+1]=(s[i]+dp[i+1])%P;//计算前缀和
}
cout<<dp[n+1];
}
