第一题 简单模拟 ? 稍作思考
题目意思：奥林匹克赛制 每个选手 需要b个毛巾 n个选手 每局每个选手需要a 瓶水 一个裁判一瓶
解题思路：我们只需要模拟这个操作即可，重点在于是奇数如何处理我们发现，如果又奇数存在就会直接
轮空晋级，所以每次/2判断奇偶之后加入轮空即可，最后一人就是胜利
时间复杂度：0(logn)
void solve()
{
cin>>n>>x>>y;
int ans=0,res=n*y;
while(n!=1){
ans+=n/2;
int res=n%2;// 轮空人数
n/=2;
n+=res;
}
ans*=(2*x+1);
cout<<ans<<" "<<res<<endl;
return ;
}
但是真的需要这么麻烦吗？有人觉得这个问题解决了却不去思考了，实际上这是不好的，我们面对复杂问题
的时候不仅考虑时间复杂度，空间复杂度，也要考虑时间复杂度！那么这个题是否可以再优化呢?
其实我们要是思考到本质的n个选手要剩下一个选手那必然是淘汰了n-1个选手每淘汰一个选手需要依次比赛
所以最简单的代码就是
int n,b,p;
scanf("%d %d %d",&n,&b,&p);
printf("%d %d\n",(2*b+1)*(n-1),n*p);
第二题 数的性质 ? 类dp思考
题目意思：给定一个可能带有前导0的超级大数求其中子串是4倍数的数量(可以带前导0)
解题思路：我们首先要发现对于4的倍数所具有的特点，如果一个数是一个两位数是4的倍数或者一位数是4的倍数
那么这个数的基础上加上100，1000也就是直接给他的第三位数附值照样是4的倍数(100%4==0)，否则都不是
所以启发我们可以考虑一个数的第一位和前一位是否是4的倍数是的话直接累加上前面的多的位数即可
时间复杂度o(n)
void solve()
{
string s; cin>>s;
n=s.size(); s=' '+s;
int ans=0;
for(int i=n;i>=1;i--){
int x=s[i]-'0';// 以当前这一位结尾的是4倍数的数量
if(x%4==0) ans++;
if(i>1 and (x+10*(s[i-1]-'0'))%4==0){
ans++;
ans+=(i-2);
}
}
cout<<ans<<endl;
return ;
}
第三题 简单模拟
题目意思：规定d等于字母字典序的差值 给定一个string 求一个string满足两个的对应字母d之和为m
解题思路：我们首先思考一下什么情况下会无解，也就是我每一个数都取到最大差值的时候依旧小于m
那就是明显无解，否则就是有解,那么我们如何构造呢?我们可以在前面的时候在范围内满足最大即可，
后面可以直接填充一样的，注意每一个位置的左右都是可以的
时间复杂度o(n)
int t,n,m;
string s;
void solve()
{
cin>>n>>m;
cin>>s;
int res=0;
for(int i=0;s[i];i++){
int x=max(s[i]-'a',25-(s[i]-'a'));
res+=x;
}
if(res<m){
cout<<-1<<endl;
return ;
}
for(int i=0;i<n;i++){
int l=s[i]-'a',r=25-l;
if(m){
int x=min(m,max(l,r));// 实际可最大变化
if(x<=l)
cout<<(char)((l-x)+'a');
else cout<<(char)((l+x)+'a');
m-=x;
}
else cout<<s[i];
}
cout<<endl;
return ;
}
第四题 位数dp
题目意思：给定两个位数相同的超级大数，求中间满足偶数位置都为d，奇数位置不是d,并且是m倍数数的数量
解题思路：首先可以联想到数位dp(比较明显的特征区间求数量),接着考虑到数很大就要用string来
存储，然后不能直接同dp(r)-dp(l-1) 一样毕竟是串，所以我们可以变成dp(r)-dp(l)+ok(特判左边界即可)
考虑到位数相同所以不需要写前导0，接着考虑我们这个数是不满足某些性质还是需要满足，
1.数很大所以需要开long long
2.对于逐位取mod是当前状态是会对下一个状态产生影响的必须开一个数组存下来
3.对于当前是否满足最后所有偶数位置都是对于d的是否需要开数组记录?可以不用我们可以在中间直接剪
枝这个分支不满足要求的直接不递归就好
时间复杂度o(能过)
using i64 = long long;
const int N = 2010,mod=1e9+7;
i64 f[N][N];
int num[N];
string a,b;
vector<int> A,B;
int m,x;
i64 dfs(int pos,int now,int limit,int _mod){
i64&v=f[pos][_mod];
if(!pos) return (!_mod ) ;
if(~v && !limit) return v;
int upper=limit?num[pos]:9;
i64 res=0;
for(int i=0;i<=upper;i++){
if(now&1 && i==x) continue;// 剪枝
if((now%2==0 and i!=x)==0)res=(res+dfs(pos-1,now^1,limit & i == upper,(_mod*10+i)%m))%mod;
}
return limit?res:v=res;
}
i64 dp(vector<int> &A){
int pos=0;
for(int i=A.size()-1;i>=0;i--) num[++pos]=A[i];
return dfs(pos,1,1,0);
}
int main(){
memset(f,-1,sizeof f);
cin>>m>>x;
cin>>a>>b;
for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');
for(int i=0;i<b.size();i++) B.push_back(b[i]-'0');
bool ok=true;// 特判左边界
int res=0;
for(int i=0;i<A.size();i++){
res=((i64)res*10+A[i])%m;
}
if(res) ok=false;
for(int i=0,cnt=1;i<A.size();i++,cnt^=1){
if(cnt&1 and A[i]==x) ok=false;
if(cnt%2==0 and A[i]!=x) ok=false;
}
i64 ans=(dp(B)-dp(A)+ok)%mod;
ans=(ans+mod)%mod;// 注意取模可能为负数
cout<<ans<<endl;
return 0;
}
第五题：树状数组辅助模拟
题目意思：在给定矩阵中找到所有的z(几个一起拼起来是z也是z)
解题思路：我们发现对于每一个z都有一个右上左下为类似轴心，比如那么就容易想到预处理出来每一个数左边
和右边有多少个连续的z,以及副对角线有多少个连续udj[i]j接着我们枚举右上角的点，以他为
右上角轴的最大z长度为min(l[i][j],udj[i][j]),然后我们可以对满足要求的每一个在轴上的点判断一下他们的
长度是否满足变成一个z(时间复杂度为n^3)这是我们难以接受的，我们有没有办法可以使得处理每一个对角线的
时候复杂度降低呢？答案是可以的，需要我们发现一些性质,对于每一个可构造的z都是变成一个类似正方形的造型
也就是在对角线上的点是如果要有答案就必须其右边可以延申到我们固定的右上角的位置或者更加右边
zzzz
aaz| <----比如这个图假设我们以(1,3)为右上角那么起码都要到达|这个位置才可以
zzz|
那么对于每一个轴上的点的(i,j)也就是其最远的距离为(j+r[i][j]-1);
对于每一个副对角线都是在i+j上的也就是每一点只会对其所在对角线产生影响
那么我们就可以直接从下到上预处理出来每一个点对于其所在对角线上点的贡献使用树状数组维护
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=3010,mod=1e9+7;
int t,n,m;
char s[M][M];
int l[M][M];
int r[M][M];
int udj[M][M];
struct BIT{// 对于每一个对角线的树状数组
int tr[M];
void add (int x){
for(int i=x;i<=m;i+=lowbit(i)) tr[i]++;
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i];
return res;
}
}my_bit[2*M];
vector<pair<int,int>> seg[2*M];
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++){// 预处理出来每一个数的一直往左边和右边延申// 以及左下开始延申
for(int j=1;j<=m;j++) cin>>s[i][j];
for(int j=1;j<=m;j++) l[i][j]= s[i][j]=='z' ? l[i][j-1]+1 : 0;
for(int j=m;j>=1;j--) r[i][j]= s[i][j]=='z' ? r[i][j+1]+1 : 0;
}
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
udj[i][j]= s[i][j]=='z' ? udj[i+1][j-1]+1 : 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int len=j+r[i][j]-1;
if(j<=len) seg[len].push_back({i,j});// 表示在这个对应长度下满足的下标是多少
}
LL sum=0;
for(int j=m;j>=1;j--){// 从长的开始覆盖
for(auto&[l,r]:seg[j]){// 当前的最大长度
my_bit[l+r].add(r);//表示越早出现被加入的下标一定是可以满足的他的延展性已经到了j
}
for(int i=1;i<=n;i++){
if(s[i][j]!='z') continue;
int ql=j-min(l[i][j],udj[i][j])+1,qr=j;
sum+=my_bit[i+j].query(qr)-my_bit[i+j].query(ql-1);
}
}
cout<<sum<<endl;
return ;
}
signed main ()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
solve();
}
