状态有所回升???
考试经过
开题,T1似乎是水题,两个枚举配一个二分,半小时过掉大样例提交带走
T2先写了个爆搜,看了看第二个样例给跑了两分钟,愤而投身正解。。。发现值域不是很大,想到枚举之后去重,于是开始乱搞,两个半小时的时候终于搞出来了,看了看复杂度是\(O(nm\sqrt m)\)的,估计过不去最后的点,给卡了卡常,检查了几遍走了
剩10分钟的时候看T3,发现20分冲不上去,直接return 0
骗一分等死
结束100+70+1=171,rank6
T1卡常成功了,顺利骗满;T2 果然没过最后两个点,后悔应该测试点分治
T1.a
枚举\(n^2m\),正解双指针,指针弱者无法实现,然而我阴差阳错加的几个剪枝配合卡常最终助我AC,\(979ms\)惊险通过
放上卡过去的代码
#include <bits/stdc++.h>
using namespace std;
#define R register
char a[35][50050];int b[35][50050];int l,r;
signed main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]-'0';
scanf("%d%d",&l,&r);
long long ans=0;
for(R int i=1;i<=n;i++)
for(R int j=i;j<=n;j++)
for(R int k=1;k<=m;k++)
{
if(b[j][k]-b[j][k-1]-b[i-1][k]+b[i-1][k-1]>r||b[j][m]-b[j][k-1]-b[i-1][m]+b[i-1][k-1]<l){continue;}
int ans1=0,ans2=0;
int ll=k,rr=m;
if(b[j][k]-b[j][k-1]-b[i-1][k]+b[i-1][k-1]>=l)ans1=k;
else
while(ll<=rr)
{
int mid=(ll+rr)>>1;
if(b[j][mid]-b[j][k-1]-b[i-1][mid]+b[i-1][k-1]>=l)rr=mid-1,ans1=mid;
else ll=mid+1;
}
ll=k;rr=m;
if(b[j][m]-b[j][k-1]-b[i-1][m]+b[i-1][k-1]<=r)ans2=m;
else
while(ll<=rr)
{
int mid=(ll+rr)>>1;
if(b[j][mid]-b[j][k-1]-b[i-1][mid]+b[i-1][k-1]<=r)ll=mid+1,ans2=mid;
else rr=mid-1;
}
ans+=ans2-ans1+1;
}
cout<<ans<<endl;
return 0;
}
T2.b
正解在于枚举因数做到\(log\),而我强行分解是根号级别,就差这里
先分别算出每个序列每个因子的贡献次数,将20个相乘,然后再做一次去重操作,将每个因数的贡献减去他所有倍数的贡献即可
这个方法应该积累一下,别上来就硬拆
#include <bits/stdc++.h>
using namespace std;
#define R register
const int mod=1e9+7;
const int N=100050;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int a[22][N];int n,m;
int yz[22][N],sum[N];
int s[22][N];
signed main()
{
cin>>n>>m;int ma=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read(),ma=max(ma,a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][a[i][j]]++;
for(int i=1;i<=n;i++)
for(int j=1;j<=ma;j++)
for(int k=j;k<=ma;k+=j)
yz[i][j]+=s[i][k];
for(R int i=1;i<=ma;i++)
{
long long an=1;
for(R int j=1;j<=n;j++)
an=1ll*an*((1ll*yz[j][i]+1)%mod)%mod;
sum[i]=(1ll*an-1+mod)%mod;
}
for(int i=ma/2+1;i>=1;i--)
{
if(!sum[i])continue;
for(int j=2*i;j<=ma;j+=i)
sum[i]=(1ll*sum[i]+mod-sum[j])%mod;
}
long long ans=0;
for(int i=1;i<=ma;i++)ans=(ans+1ll*sum[i]*i%mod)%mod;
cout<<ans<<endl;
return 0;
}
T3.c
点分治+dp,根本调不出来,鸽了
知识点全靠现学,根本学不会
所以这是我点分治入门题???
希望有空填坑吧
考试总结
1.把握时间,每分每秒都很珍贵,提高一分,干掉千人
2.思维灵活,从数据范围中寻找突破口,及时更换思路