碎碎念
时限3h打了五题铜，感觉还没有把可做题全部写完，待补
J. Local Minimum
记录行最小值和列最小值，遍历一遍矩阵判断当前值是否同时是行最小值与列最小值，记录答案即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define inf 0x3f3f3f3f
const int N=1000+100;
int t,n,m,q,a[N][N],minr[N],minc[N];
vector<int> g[N];
string s;
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cin>>a[i][j];
}
for(int i=1;i<=n;i++)
{
int mii=1e9;
for(int j=1;j<=m;j++) mii=min(mii,a[i][j]);
minr[i]=mii;
}
for(int j=1;j<=m;j++)
{
int mii=1e9;
for(int i=1;i<=n;i++) mii=min(mii,a[i][j]);
minc[j]=mii;
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(min(minr[i],minc[j])==a[i][j]) ans++;
}
}
cout<<ans;
}
main()
{
IOS;
solve();
}
B. Magical Subsequence
小dp，记录 \(dp[i][j]\) 表示当前匹配到 \(i\) 位，选择和为 \(j\) 的最大长度。
\[dp[i][j]=max(dp[i-1][j],dp[LastOccrrenceIndexof(j-a[i])-1][j]+2)
\]
其中 $ LastOccrrenceIndexof(j-a[i])$ 表示最近的值为 \(j-a[i]\) 的元素出现的位置，可以 \(O(n)\) 地预处理出来。
注意一丢丢不要匹配到负数下标的小细节
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define inf 0x3f3f3f3f
const int N=1e5+100;
int t,n,m,q,a[N],f[N][201],g[N][201];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=100;j++)
{
g[i][j]=g[i-1][j];
}
g[i][a[i]]=i;
}
for(int i=1;i<=n;i++)
{
for(int x=2;x<=200;x++)
{
f[i][x]=max(f[i][x],f[i-1][x]);
int now=x-a[i];
//if(x==2) cout<<f[i][x]<<' '<<g[i-1][now]<<' '<<f[g[i-1]][now]<<'\n';
if(now>=1&&now<=100)
{
if(g[i-1][now]>0) f[i][x]=max(f[i][x],f[g[i-1][now]-1][x]+2);
}
}
}
int ans=0;
for(int i=2;i<=200;i++) ans=max(ans,f[n][i]);
cout<<ans;
}
main()
{
solve();
}
E. Power and Modulo
找到第一个 \(a[i]!=a[i-1]\time 2\) 的位置，即可知道 \(mod=2\time a[i-1] - a[i]\) ，遍历数组判断是否满足 \(a[i]=2^{i-1}%mod\) 即可。 需要考虑 \(a[1]!=1,mod<=0\) 这两种特殊情况。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define inf 0x3f3f3f3f
const int N=2e5+100;
int t,n,m,q,a[N];
vector<int> g[N];
string s;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int mod=-1;
if(a[1]!=1)
{
for(int i=1;i<=n;i++)
{
if(a[i]!=0)
{
cout<<"-1\n";
return;
}
}
cout<<"1\n";
return;
}
for(int i=2;i<=n;i++)
{
if(a[i]!=a[i-1]*2)
{
if(a[i]>a[i-1]*2)
{
cout<<"-1\n";return;
}
mod=2*a[i-1]-a[i];
break;
}
}
if(mod==-1) cout<<-1<<'\n';
else
{
int b=1;
for(int i=1;i<=n;i++)
{
if(a[i]!=b)
{
cout<<"-1\n";
return;
}
b=b*2%mod;
}
cout<<mod<<'\n';
}
}
main()
{
cin>>t;
while(t--) solve();
}
I. Power and Zero
按位拆分这个数组二进制第0位第31位每一位有多少个1，答案等同于删第0位的次数，而因为每次只能删去0i的一个前缀，需要满足序列单调不增，可以通过高位-1=低位+2来变换，大概想法是二分答案判断最多需要多少次，乱糊了一下发现就过了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define inf 0x3f3f3f3f
const int N=2e5+100;
int t,n,m,q,a[N],b[40],c[40];
bool check(int mid)
{
memcpy(c,b,sizeof c);
int nowmin=mid;
for(int i=1;i<=32;i++)
{
//cout<<c[i];
if(c[i]>nowmin) return false;
int time=(nowmin-c[i])/2;
c[i+1]-=time,c[i]+=time*2;
nowmin=min(nowmin,c[i]);
}
return true;
}
void solve()
{
memset(b,0,sizeof b);
memset(c,0,sizeof c);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=32;j++)
{
if((a[i]>>(j-1))&1) b[j]++;
}
}
int l=0,r=1e9,mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
// for(int i=1;i<=32;i++)
// {
// c[i]=b[i]-b[i-1];
// }
// for(int i=32;i>=2;i--)
// {
// if(c[i]<=0) continue;
// int time=(c[i]+2)/3;
// c[i]-=time*3,c[i-1]+=time*2;
// }
cout<<l<<'\n';
}
main()
{
cin>>t;
while(t--) solve();
}
D. Math master
2<<19枚举删除分子的哪些位，删完后确定新的分母，判断能否删除得到，有一些细节比如前导0需要注意。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define inf 0x3f3f3f3f
const int N=2e5+100;
int T,n,m,q;
int lens,lent;
vector<int> g[N];
string s,t;
int ansn,ansm;
int stringtoint(string s)
{
int ans=0;
for(int i=0;i<(int)s.size();i++) ans=ans*10+s[i]-'0';
return ans;
}
string inttostring(int x)
{
int y=x;
string ss;
while(y) ss+='0'+y%10,y/=10;
reverse(ss.begin(),ss.end());
return ss;
}
void check(int num)
{
int a[10]={0};
string ss,tt;
for(int i=0;i<lens;i++)
{
if((num>>i)&1)
{
// if(ss.size()==0&&s[i]=='0') return;
ss+=s[i];
}
else a[s[i]-'0']++;
}
int ssi=stringtoint(ss);
if(ssi==0) return;
int d=((__int128)ssi*(__int128)m)%(__int128)n;
if(d!=0) return;
int ssj=((__int128)ssi*(__int128)m)/(__int128)n;
tt=inttostring(ssj);
int p=tt.size()-1;
int cnt=0;
for(int i=(int)t.size()-1;i>=0;i--)
{
if(p>=0&&t[i]==tt[p]) p--;
else {
if(!(p==-1&&t[i]=='0')) a[t[i]-'0']--;
else cnt++;
}
}
bool flag=1;
for(int i=0;i<10;i++) if(a[i]!=0)
{
if(i==0&&a[0]>0&&cnt>=a[0]) continue;
flag=0;
}
if(p==-1&&flag)
{
if(ssi<ansn)
{
ansn=ssi,ansm=ssj;
}
return;
}
}
void solve()
{
cin>>n>>m;
s=inttostring(n),t=inttostring(m);
lens=s.size(),lent=t.size();
ansn=n,ansm=m;
for(int i=1;i<=(1<<lens)-1;i++)
{
check(i);
}
cout<<ansn<<' '<<ansm<<'\n';
}
main()
{
cin>>T;
while(T--) solve();
}