题解9.29-10.3

1.MakeitAlternating
如果它已经是交替的序列我们就不用管了，最终的目的是把序列变成交替的序列，那么我们可以把连续相同的数
全部取出来只留下一个，可以分成几段相同的数，最后的结果就是把这些相同的数全部只保留一个，用排列组合C(m,1);
第一个结果很简单，把重复的数加一下即可，后面的答案我们用C(m,1)算出来每个的数量，最后把拿出来的数全排列一下就行。

#include <bits/stdc++.h>using namespace std;
#define int long long intint MOD =998244353;int res[2000001];
//预处理把所有的阶乘算出来
void init()
{res[0] = 1;for (int i = 1; i <= 200000; i++){res[i] = res[i - 1] * i % MOD;// cout << res[i] << ' ';}
}int32_t main(){ios::sync_with_stdio(false);cin.tie(nullptr);init();int t;cin>>t;while(t--){string s;cin>>s;int cs=0;int ans=1;int q=1;char cnt=s[0];for (int i =1; i < s.length(); ++i) {if(s[i]==cnt)cs++,q++;else{cnt=s[i];if(q!=1)ans*=q;ans%=MOD;q=1;}}if(q!=1){ans*=q;ans%=MOD;q=1;}if(ans==1) cout<<cs<<' '<<1<<'\n';elsecout<<cs<<" "<<(res[cs]*ans)%MOD<<'\n';}return 0 ;
}

2. 2.C. Black Circles
两点之间直线最短，如果刚好相切，可以画图证明一下也是可以的，这里注意不要用sqrt精度不行，所以直接用乘积比较

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{int x;int y;
}v[100001];
int32_t main(){ios::sync_with_stdio(false);cin.tie(NULL);int t;cin>>t;while(t--){int n;cin>>n;for (int i = 1; i <=n ; ++i) {cin>>v[i].x>>v[i].y;}int tx,ty;int ex,ey;cin>>tx>>ty;cin>>ex>>ey;int pd=0;int dis=((tx - ex) * (tx - ex) + (ty - ey) * (ty - ey));for (int i = 1; i <=n; ++i) {int dis1=((v[i].x - ex) * (v[i].x - ex) + (v[i].y - ey) * (v[i].y - ey));if(dis1<=dis){pd=1;break;}}if(pd)cout<<"NO\n";else cout<<"YES\n";}}

3.The Strict Teacher (Hard Version))
二分，给出的数是有顺序的，目的是找最接近的左边和右边的数，两边二分即可

#include <bits/stdc++.h>
using  namespace  std;#define  int long longint32_t main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--){int n,m,q;cin>>n>>m>>q;set<int>st;set<int,greater<>>st2;st.insert(0);st2.insert(0);for (int i = 1; i <=m ; ++i) {int b;cin>>b;st.insert(b);st2.insert(b);}while(q--){int d;cin>>d;int f=*st.upper_bound(d);int h=*st2.upper_bound(d);if(f<=d){cout<<n-h<<'\n';}else if(h==0){cout<<f-1<<'\n';}else{cout<<(f-h)/2<<'\n';}// cout<<"f: "<<f<<" h: "<<h<<'\n';}}
}

4.F.Sakurako'sBo
考察题目逆元的性质，计算除法的时候会改变值，这个时候我们用快速幂逆元写即可

#include <bits/stdc++.h>
using  namespace  std;#define  int long longint MOD=1000000007;
int f[1008611];
int pre[1008611];
int qpow(int a,int n)
{int res=1;while(n){if(n&1) res=res*a%MOD;n>>=1;a=a*a%MOD;}return res;
}int32_t main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--){int n;cin>>n;pre[0]=0;for (int i = 1; i <=n ; ++i) {cin>>f[i];pre[i]=pre[i-1]+f[i];}int sum=0;for (int i = 1; i <n ; ++i) {sum+=((f[i]%MOD*((pre[n]-pre[i])%MOD)%MOD))%MOD;sum%=MOD;}int fm=(n*(n-1)/2)%MOD;//这也要记得modcout<<(sum%MOD* qpow(fm,MOD-2))%MOD<<'\n';}
}

5.C. Absolute Zero
找规律发现，以最大的数依次除二与数组进行取绝对值，最后会变成1或者是0，我一开始直接拿最大的数操作，但是wa了二，很明显
最大的数有可能进行40次操作不一定够，于是想到数据的范围不超过2的30次方，那么我们把最大的数设置为2的29次方，拿最终经过30或者31次操作必有解

#include <bits/stdc++.h>
using  namespace  std;#define  int long longint MOD=1000000007;
int f[1008611];
int qpow(int a,int n)
{int res=1;while(n){if(n&1) res=res*a;n>>=1;a=a*a;}return res;
}int32_t main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--){int n;cin>>n;int maxx=0;int maxd=0;int ji=0;int ou=0;for (int i = 1; i <=n ; ++i) {cin>>f[i];if(f[i]%2==0)ou=1;else ji=1;maxd=max(maxd,f[i]);}int pd=0;if(maxd==0){cout<<0<<'\n';cout<<'\n';continue;}if(ji&&ou)pd=1;maxx= qpow(2,29);if(pd){cout<<-1<<'\n';}else{int ans=0;int res=maxx;int d=abs(f[n]-1);while(maxx>0){//  cout<<maxx<<' ';d=abs(d-maxx);maxx/=2;ans++;if(ans>40){pd=1;break;}}if(pd){cout<<-1<<'\n';continue;}if(ans!=0&&d==0)cout<<ans+1<<'\n';else if(ans!=0&&d==1){cout<<ans+2<<'\n';}elsecout<<ans<<'\n';while(res>0){cout<<res<<' ';res/=2;ans++;}if(ans!=0)cout<<1<<' ';if(ans!=0&&d==1)cout<<1<<' ';cout<<'\n';}}
}

6.B. Battle Cows
题单上写的二分，我一直往二分方向考虑，想不出来，后面看题解发现根本不是二分的思路，我们如果要比赛赢的
最多，我们必须比前面的都大，这个时候我们跟第一个数交换，如果前面出现比自己的数大，那么我们就跟从第一个
开始比自己大的数交换，然后比较这两个数谁大就行

#include <bits/stdc++.h>
using namespace std;int a[1008611];
void solve()
{int n,k,i; cin>>n>>k;for(i=1;i<=n;i++) cin>>a[i];swap(a[k],a[1]);int ans1=0;  //与第一个人交换的方案的胜场数for(i=2;i<=n;i++){if(a[i]>a[1]) break;else ans1++;}swap(a[k],a[1]); //swap回来进行下一个方案的求解int flag=n+1,ans2=0; //flag为第一个比k大的人的下标for(i=1;i<=n;i++)if(a[i]>a[k]){flag=i;break;}if(flag<k){swap(a[k],a[flag]);if(flag>1) ans2++;//特判当前k是不是在开头，否则会赢前面的人一场for(i=flag+1;i<=n;i++){if(a[i]>a[flag]) break;else ans2++;}}cout<<max(ans1,ans2)<<"\n";
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while (t--){solve();}
}

7.1.E. Secret Box
不难，但是思路错了，我的想法是它要凑出x，y，z的数量，并且x,y,z的点必须是相联的，
然后我去计算点数的时候也出错了，就一直想不通，其实大体思路没错，但是没有想清楚，每个点
从1开始向后移动就是连续的了，我们只需要枚举x，y，用k/x*y，去找c即可，最主要的原因还是没有分析
清楚，找不出计算的规律

#include <iostream>
using namespace std;
using ll = long long;int main(){int t; cin >> t;while(t--){ll x, y, z, k; cin >> x >> y >> z >> k;ll ans = 0;for(int a = 1; a <= x; a++){for(int b = 1; b <= y; b++){if(k % (a * b)) continue;ll c = k / (a * b);if(c > z) continue;ll ways = (ll)(x - a + 1) * (y - b + 1) * (z - c + 1);ans = max(ans, ways);}}cout << ans << "\n";}
}