零、写在前面
本人比较菜，在这场接近提高组的模拟赛中获得了 /(30 + 100 + 30 + 50 = 210/) 的 烂 分
事实上只要把暴力打足成绩一般就不会差
但后来本人在 ZYF 神犇的指导下侥幸 AK 了
言归正传，接下来就是本场比赛的解题思路了 坐稳扶好
壹、碑文
这是本场比赛最难的题目，没有之一！
一、骗分思路
初看题目我们可能会很看不懂题，但是 /(30/%/) 的数据范围非常小，完全可以直接按照题目的意思模拟
只需要注意数组别越界就行了
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,ans;
int a[100009],b[100009];
int p[100009];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
while(q--)
{
memset(p,0,sizeof(p));//多测不清空，RE两行泪
int x,k;
cin>>x>>k;
p[1]=x,ans=0;
for(int i=2;i<=n&&p[i-1]<=n&&p[i-1]>=1;i++)//别让数组越界
p[i]=p[i-1]+k+a[p[i-1]];//直接按照题意莽上去
for(int i=1;i<=n;i++)
if(p[i]<=n&&p[i]>=1) ans+=b[p[i]];//同理
else break;
cout<<ans<<endl;
}
return 0;
}
二、满分思路
骗分代码交上去理所当然地 /(/text{TLE}/) 了
我们静下心来，再仔细想一想这道题中数列 /(P/) 有什么性质
我们发现，对于第 /(i/) 个询问，不考虑数列 /(S/) 的影响，/(|P|/) 是与 /(/cfrac{n}{K_i}/) 同阶的
因此，我们可以对 /(K_i/) 的值用分块的思想做出分类：
-
/(K_i /ge /sqrt{n}/)：
我们发现，在这种情况下，/(|P|/) 是不会超过 /(/sqrt{n}/) 的
所以我们只需要按照上面暴力的思路来就可以了
（直接把暴力代码粘贴过来）时间复杂度 /(O(/sqrt{n})/)
-
/(K_i < /sqrt{n}/)：
这种情况下，/(|P|/) 有可能远远超过 /(/sqrt{n}/)，造成上面的暴力跑不过去
但我们发现，当 /(K_i</sqrt{n}/) 时，/(K_i/) 的可能数也会较少
同时我们发现，对于任意一个 /(K_i/)，在数列 /(S/) 相同的情况下，一定对应一个唯一的数列 /(P/)
因此我们处理出所有 /(K_i < /sqrt{n}/) 时所有的 /(P/) 的情况
具体的，对于每一个 /(K_i < /sqrt{n}/)，我们都建一棵高度为 /(n/) 的树，从根节点开始，依次计算这棵树的前缀和，询问时直接输出第 /(K_i/) 棵树中根节点到 /(X_i/) 的前缀和即可（代表题目中询问的 /(/sum/limits_{j=1}^{|P|} T_{P_j}/)
预处理时间复杂度 /(O(n/sqrt{n})/)，询问时间复杂度 /(O(1)/)
按照上面两种情况考虑，这道题标准时间复杂度应该是 /(O((n+q)/sqrt{n})/)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,ans,sqn;
int a[100009],b[100009];
int p[100009],nex[319][100009];
signed main()
{
scanf("%lld%lld",&n,&q),sqn=sqrt(n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
for(int i=1;i<=sqn;i++)
for(int j=n;j>=1;j--)
{
nex[i][j]=b[j];
if(i+j+a[j]<=n) nex[i][j]+=nex[i][i+j+a[j]];//重点部分，根据公式推出来的
}//n*sqrt(n) 预处理
while(q--)
{
int x,k;
scanf("%lld%lld",&x,&k);
if(k>=sqn)//大于 sqrt(n) 就暴力
{
p[1]=x,ans=0;
for(int i=2;i<=n&&p[i-1]<=n&&p[i-1]>=1;i++)
p[i]=p[i-1]+k+a[p[i-1]];
for(int i=1;i<=n;i++)
if(p[i]<=n&&p[i]>=1) ans+=b[p[i]];
else break;
printf("%lld/n",ans);
continue;
}
printf("%lld/n",nex[k][x]);//不然直接输出
}
return 0;
}
贰、虚空
这道题是比赛上最简单的一题
尽管还是可以打暴力
一、骗分思路
还是和 /(/text{T1}/) 一样，按照题意模拟
每次从 /(i= n /sim 1,j=m /sim 1/) 的顺序查找，找到第一个为 /(1/) 的数，把这个数左上角的数全部取反，同时答案 /(+1/)
可以 水 60分
//代码转载自 topscoding10125
//此代码网址：https://www.topscoding.com/records/6301ff482e0ba731ef9d3530
#include<bits/stdc++.h>
using namespace std;
int cnt=0,n,m;
string s;
bool b[5001][5001];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s;
for(int j=1;j<=m;j++)
b[i][j]=s[j-1]-'0';
}
while(1){
int x=-1,y=-1;
bool flag=1;
for(int i=n;i>=1&&flag;i--)
for(int j=m;j>=1&&flag;j--)
if(b[i][j])
x=i,y=j,flag=0;//按题意找到第一个不为 0 的数并记录坐标
if(flag)//如果都为 0 就结束循环
break;
for(int i=1;i<=x;i++)
for(int j=1;j<=y;j++)
b[i][j]=!b[i][j];//左上角全部取反
cnt++;//计数器 +1
}
cout<<cnt<<endl;
return 0;
}
二、满分思路
这道题要用到差分的二维前缀（异或）和
我们发现，对于每一个位于 /((x,y)/) 的修改操作，影响的一定是 /((1/sim x,1 /sim y)/) 坐标里的值
也就是说，若某个位置 /((x,y)/) 为 /(1/)，且它的右下角的矩阵除了它全是 /(0/)，那肯定要在 /((x,y)/) 进行一次操作（也就是上面暴力的思想）
而取反这个东西如果是暴力 /(O(nm)/) 的话，总时间复杂度会是 /(O(n^2m^2)/) 会 /(/text{TLE}/)
因为操作的是整个子矩阵，所以我们考虑用差分的思想
差分过程就不在讲了，具体想了解可以百度
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
bool a[5009][5009],s[5009][5009];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char c;
cin>>c,a[i][j]=c-48;
}
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
s[i][j]=s[i+1][j]^s[i][j+1]^s[i+1][j+1],//差分
ans+=s[i][j]^a[i][j],//计算这一位要不要操作（取反）
s[i][j]^=(1*(s[i][j]^a[i][j]));//如果这一位要取反，就把它取反
//这里笔者太懒了（ε=ε=ε=┏(゜ロ゜;)┛）简写了
//原本这里应该有 if 判断的，笔者把它省略了（doge
cout<<ans;
return 0;
}
叁、星河
这道题有四种解法，接下来一一讲解
一、骗分思路——暴力
还是按照题意模拟，枚举区间 /(l /sim r/) 中无序实数对 /((i,j)/)，判断是否符合题目要求
时间复杂度 /(O(q(r-l)^2)/)，可以骗 /(30/) 分
#include<bits/stdc++.h>
#define int long long//十年 OI 一场空，不开 long long 见祖宗（悲）
using namespace std;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--)
{
int l,r,ans=0;
cin>>l>>r;
for(int i=l;i<=r;i++)
for(int j=i+1;j<=r;j++)
if(i/__gcd(i,j)*j>i+j) ans++;//暴力枚举
cout<<ans<<endl;
}
return 0;
}
二、骗分思路——找规律
我们发现，若 /([i,j]/le i+j/)（/([i,j]/) 表示 /(i/) 和 /(j/) 的最小公倍数），则 当且仅当 /(i |j/) 或 /(j|i/)
于是我们可以对于 /(l /sim r/) 中每一个数算出这个区间里有多少个数是它的倍数
具体的，对于一个数 /(x(l /le x /le r)/)，这个区间里一共有 /(/lfloor /cfrac{r-l+1}{x} /rfloor/) 个数是它的倍数
时间复杂度降到了 /(O(q(r-l))/)，可以骗 /(50/) 分
代码就不放了，因为第三种解法就是它的改进版
三、满分思路——数论分块
上面第二种解法的时间复杂度瓶颈在于对于每个询问，都要把整个区间全部扫一遍
但我们再想想就可以发现，/(/lfloor /cfrac{r-l+1}{x} /rfloor/) 只会有约等于 /(/sqrt{r-l+1}/) 种结果
可以用数论分块来优化，时间复杂度为 /(O(q/sqrt{r-l})/)，可以 /(/text{AC}/)
#include<bits/stdc++.h>
using namespace std;
signed main()
{
int T;
scanf("%d",&T);
while(T--)
{
int l,r;
unsigned long long ans=0;
scanf("%d%d",&l,&r);
for(int lef=l,rig;lef<=r;lef=rig+1)
rig=r/(r/lef),ans+=(rig-lef+1)*1ll*(r/lef);//数论分块
printf("%lld/n",(ans=((r-l+2)*1ll*(r-l+1)>>1)-ans));//注意，答案是整个组合的数量减去前面统计的值
}
return 0;
}
四、满分思路——树状数组
我们考虑枚举 /(l /le i< r/)，对于每个 /(i/)，累和统计它在 /([i+1,r]/) 区间中的倍数数量
/([l,r]/) 区间中数对的数量是 /(/cfrac{(r-l+1)(r-l)}{2}/)的，所以我们拿所有的数量减去不满足的数量即可（刚才讲过了）
由于询问较多 /((q /le 10^5)/)，考虑离线
注意到，对于一对不满足孪生星数对的 /((i,j)/)，会被所有在 /(l=[1,i],r=[j,MAXR]/) 范围内被统计
我们稍加思索得出结论，如果 /(l/) 比较大，被影响的就会比较少，甚至会不被统计
因此，我们先开一个计数数组 /(d/)，将询问以 /(l/) 降序排序，从 /(MAXR /sim 1/) 枚举 /(i/)，再枚举 /(i/) 的倍数 /(j/)，同时将 /(d_j/) 加 /(1/)
然后对于每个询问，当 /(i=l/) 时，答案就是
/[/cfrac{(r-l+1)(r-l)}{2} – /sum/limits_{x=1}^r d_x
/]
我们发现，这里是单点修改，区间查询，因此我们考虑用树状数组
时间复杂度 /(O(q /log q+r /log r)/)
当然用分块也可以
//代码转载自 heshuyu1527
//此代码网址：https://www.topscoding.com/records/630365b62e0ba731ef9d4fd9
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x//树状数组模板
int q;
long long ans[100005],t[500005];//t:树状数组模板
struct seg{
int l,r,seq;
}a[100005];//离线处理
bool cmp(const seg& x,const seg& y){
return x.r<y.r;
}
void add(int x,long long k){//树状数组模板
for(;x<=500000;x+=lowbit(x))t[x]+=k;
}
long long ask(int x){//树状数组模板
long long res=0;
for(;x;x-=lowbit(x))res+=t[x];
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>q;
for(int i=1;i<=q;i++){
cin>>a[i].l>>a[i].r;
a[i].seq=i;
}
sort(a+1,a+q+1,cmp);
int p=1;
for(int i=1;i<=500000;i++){
for(int j=1;j*j<=i;j++){
if(i%j==0){
add(j,1);
if(j*j!=i)add(i/j,1);//上面思路中的“增加”操作
}
}
while(a[p].r==i&&p<=q){
long long len=a[p].r-a[p].l+1;
ans[a[p].seq]=len*(len+1)/2-ask(a[p].r)+ask(a[p].l-1);//套入上面推理的公式
p++;
}
if(p>q)break;//左边界比右边界还大就中断
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'/n';
return 0;
}
肆、天启
一、骗分思路
直接暴力，按题意模拟，可得 /(30/) 分
二、满分思路
稍加推理，便可以得出答案是
/[/min /{ /max /{ /min /{ a_i,a_{i+1}/}/} (1 /le i < n) , 2 /times/min /{ a_i/}(1 /le i /le n) /}
/]
即要么一直走一条链，要么跑到最小值那里转一圈
所以我们有如下策略：
- 用 /(k/) 次操作将第 /(1/) 小到第 /(k/) 小值全部改为 /(10^9/)
- 用 /(k-1(k>1)/) 次操作将第 /(1/) 小到第 /(k-1/) 小值全部改为 /(10^9/)，并在其中一个值的旁边修改一个 /(10^9/)
- 在最大值的旁边把一个值修改为 /(10^9/)
然后就排序、套策略就行了
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n,times,a[300009];
pair<int,int>maxed,ring;
pair<int,int>node[300009];
inline bool cmp_node(pair<int,int>u,pair<int,int>v)
{
return u.first<v.first?1:(u.first>v.first?
0:u.second<v.second);
}
inline int find_max(int l,int r)
{
int res=0;
for(int i=l;i<=r;i++) res=max(res,a[i]);
return res;
}
inline void copy_max(int l,int r)
{
for(int i=l;i<=r;i++) a[node[i].second]=inf;
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>times;
maxed=ring=make_pair(0,0);
for(int i=1;i<=n;i++) cin>>a[i],node[i]=make_pair(a[i],i);
sort(node+1,node+n+1,cmp_node);
if(!(times^1))
maxed.first=find_max(1,n),ring.first=node[1].first<<1,
a[node[1].second]=inf;
else
copy_max(1,times-1),
maxed.first=inf,ring.first=node[times].first<<1,
a[node[times].second]=inf;
for(int i=2;i<=n;i++)
maxed.second=max(maxed.second,min(a[i],a[i-1]));
if(times^n) ring.second=node[times+1].first<<1;
else ring.second=(inf<<1);
cout<<max(min(maxed.first,ring.first),min(maxed.second,ring.second))<<"/n";
}
return 0;
}
/(/huge/texttt{THE END}/)
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/282073.html