西安交大多校联训NOIP1模拟赛题解

T1 秘境

形式化题意

求 $\sum _{i=1}^n\lfloor i\rfloor$ ，$1\le n\le 10^{18}$

思路

看到根号直接想到根号分块。直接将原式转换为 $[\sum _{i=1}^{\lfloor \sqrt{n}\rfloor -1}(2i+1)]+P$，这个式子直接用公式就可以了, $P$ 的散块 $O(1)$ 算。

代码（丑陋）

//Syt forever!
#include<bits/stdc++.h>
#define int __int128 
#define ll long long 
using namespace std;const int mod=998244353;
ll c;
int n;
signed main(){scanf("%lld",&c);n=c;int a=1,b=2,c=-n;int delta=b*b-4*a*c;delta=sqrtl(delta);ll r=delta;int p=delta-b;p/=2*a;int ans=p*(p+1)*(2*p+1)/3+(1+p)*p/2;int num=(3+2*p+1)*p/2;num=n-num;++p;ans+=num*p;ans%=mod;ll tot=ans;printf("%lld\n",tot);return 0;
}

T2 礼物

形式化题意

有 $n$ 件物品，第 $i$ 个礼物价格为 $w_i$ 元，价值为 $v_i$ 。
$T$ 次询问，每次有 $m$ 元，用这些钱购买奇数 $q_i$ 件物品，对于每个询问计算出购买 $q_i$ 件物品的中位数的最大值。若无法购买输出 $-1$。

思路

首先不难想到若购买物品越多中位数最大值越小，假如我们先钦定一个中位数，去检查其是否可行，无非检测 $\ge$ 中位数和 $<$ 中位数两部分是否合法。这个其实直接可以权值线段树维护，将查询离线，两棵权值线段树就可以了。

代码（实现）

//Syt forever!
#include<bits/stdc++.h>
#define int long long 
using namespace std;const int maxn=5e5+10;
const int maxm=1e6+10;
int n,m,T,cnt;
int c[maxn],ans[maxn];
struct node{int v,w;
}a[maxn];
struct vertex{int x,op;
}e[maxn];
struct Segment{int l,r;int num,sum;
}t[5][maxm<<2];
inline void ipt(){scanf("%lld%lld%lld",&n,&m,&T);for(int i=1;i<=n;i++){scanf("%lld%lld",&a[i].v,&a[i].w);c[i]=a[i].v;}for(int i=1;i<=T;i++){scanf("%lld",&e[i].x);e[i].op=i;} 
}
inline bool cmp1(node nx,node ny){return nx.v<ny.v;}
inline bool cmp2(vertex nx,vertex ny){return nx.x<ny.x;}
inline bool cmp3(vertex nx,vertex ny){return nx.op<ny.op;}
inline void init(){sort(c+1,c+n+1);cnt=unique(c+1,c+n+1)-c-1;sort(a+1,a+n+1,cmp1);sort(e+1,e+T+1,cmp2);
}
inline void build(int op,int i,int l,int r){t[op][i].l=l,t[op][i].r=r;if(l==r)return ;int mid=l+r>>1;build(op,i<<1,l,mid);build(op,i<<1|1,mid+1,r);
}
inline void upd(int op,int i){t[op][i].num=t[op][i<<1].num+t[op][i<<1|1].num;t[op][i].sum=t[op][i<<1].sum+t[op][i<<1|1].sum;
}
inline void change(int op,int i,int l,int r,int x){if(t[op][i].l>r||t[op][i].r<l)return ;if(l<=t[op][i].l&&t[op][i].r<=r){t[op][i].num+=x;t[op][i].sum+=x*l;return ;}change(op,i<<1,l,r,x);change(op,i<<1|1,l,r,x);upd(op,i);
}
inline int query(int op,int i,int k){if(k==0)return 0;if(t[op][i].l==t[op][i].r){int u=min(k,t[op][i].num);return u*t[op][i].l;}if(t[op][i<<1].num<=k)return t[op][i<<1].sum+query(op,i<<1|1,k-t[op][i<<1].num);return query(op,i<<1,k);
}
inline void solve(){int pos=cnt,s;for(int i=1;i<=n;i++){if(a[i].v==c[cnt])change(1,1,a[i].w,a[i].w,1);else {change(0,1,a[i].w,a[i].w,1);s=i;}}for(int i=1;i<=T;i++){if(e[i].x==e[i-1].x)continue;if(ans[e[i-1].x]==-1){ans[e[i].x]=-1;continue;}int l=(e[i].x-1)/2;if(t[0][1].num<l){ans[e[i].x]=-1;continue;}while(1){int p=query(0,1,l)+query(1,1,l+1);if(t[0][1].num<l){ans[e[i].x]=-1;break;}if(t[1][1].num>=l+1){if(p<=m){ans[e[i].x]=c[pos];break;}}--pos;int ns=0;for(int j=s;j>=1;j--){if(a[j].v==c[pos]){change(1,1,a[j].w,a[j].w,1);change(0,1,a[j].w,a[j].w,-1);	}else{ns=j;break;}}s=ns;}}
}
inline void opt(){sort(e+1,e+T+1,cmp3);for(int i=1;i<=T;i++)printf("%lld\n",ans[e[i].x]);
}
signed main(){ipt();init();build(0,1,1,1000000);build(1,1,1,1000000);solve();opt();return 0;
}

T3 小盒子的数论

形式化题意

当给定 $T$ 组数据，每组数据包括一个进制数 $m$ 和一个字符串 $s$ 。其中 $s$ 表示的是一个 $m$ 进制数，其中数据相同字母表示相同的数字，不同字母表示不同的数字，且 $s$ 表示的数字不包含前导零。求 $s$ 表示的所有可能的数字的最大公约数，用十进制表示。

思路

设出现字符的种类数为 $cnt$。
若 $m=2$ 需要特判，此处略。
若 $m\ne 2,cnt<m$，可以通过构造证明答案为每个字母出现数位的最大公约数。
若 $m\ne 2,cnt=m$，若 $m$ 为奇数，答案为 $\frac{n-1}{2}$；若 $m$ 为偶数，答案为 $n-1$。

代码（分讨）

//Syt forever!
#include<bits/stdc++.h>
#define int long long 
using namespace std;const int maxn=260;
int t,n,cnt;
char s[maxn];
int op[maxn],a[maxn];
inline void solve(){cnt=0;memset(op,0,sizeof(op));memset(a,0,sizeof(a));scanf("%lld",&n);scanf("%s",s);int len=strlen(s);for(int i=len;i>=1;i--)s[i]=s[i-1];int c=1;for(int i=len;i>=1;i--){if(i!=len)c*=n;int u=(int)(s[i]);if(!op[u])op[u]=++cnt;a[op[u]]+=c;}if(n==2){if(len==1)printf("1\n");else {if(s[1]==s[2])printf("3\n");else printf("2\n");}return ;}if(cnt!=n){int ans=a[1];for(int i=2;i<=cnt;i++)ans=__gcd(ans,a[i]);	printf("%lld\n",ans);} else {if(n%2==1)printf("%lld\n",(n-1)/2);else printf("%lld\n",n-1);}
}
signed main(){ scanf("%lld",&t);while(t--)solve();return 0;
}

T4 猫猫贴贴(CF997E)

形式化题意

长度为 $n$ 的排列 $a_1,a_2,\cdots ,a_n$。$q$ 次询问，每次询问 $[l,r]$ 子区间（不能为空）内部元素重新排序后连续的子区间数量。

思路

首先考虑被计算在答案的区间 $[l,r]$ 的特征。
其充要条件为 $\underset{i=l}{\overset{r}{\max }}{a}_i-\underset{i=l}{\overset{r}{\min }}{a}_i+1=r-l+1$，化简一下可以得到 $\underset{i=l}{\overset{r}{\max }}{a}_i-\underset{i=l}{\overset{r}{\min }}{a}_i-r+l=0$。发现 $\underset{i=l}{\overset{r}{\max }}{a}_i-\underset{i=l}{\overset{r}{\min }}{a}_i-r+l\ge 0$，想到可以记录这一坨式子的最小值和出现次数，进行计算答案。
对于区间问题有一个传统套路，按照区间右端点 $r$ 从小到大排序，在处理到右端点为 $r$ 时。我们只维护 $[i,r]$ 的答案，历史答案记录。
对于 $\max$ 和 $\min$ 的更新，可以通过 $2$ 个单调栈维护区间，每次通过单调栈去寻找出哪些 $i$构成的区间的 $\max$ 和 $\min$ 需要变化。
这个东西显然可以用线段树去维护，线段树维护 个量：

• $mn$，上面一坨式子的最小值。
• $cnt$，最小值次数。
• $lazy$，区间加tag。
• $ans$，历史答案。
• $ans$_$lazy$，历史答案tag。

初始时对于线段树每个节点 $t[l,l].mn=l$，每次右端点向右扩张 $1$ ，最大值单调栈处理，最小值单调栈处理，将对应 $3$ 个线段树区间加，其中第二个第三个只会让区间最小值变大，之后往 $t[1,n].ans$_$lazy$ 加一，查询的时候求 $ans$ 的和。

这样线段树正确性证明：若某个区间最小值变化，那么肯定在上一步pushdown，若无则说明这个区间是 $[1,n]$。pushdown时顺便将上一次的 $ans$_$lazy$ 以及 $cnt$ 转换为 $ans$。这样将开启新一轮的计算，所以这样的线段树不会出现错误。

代码（深奥）

//Syt forever!
#include<bits/stdc++.h>
#define int long long
using namespace std;const int maxn=2e5+10;
int n,q;
int a[maxn];
struct Segment{int l,r;int lazy;int mn,cnt;int ans,ans_lazy;
}t[maxn<<2];
//查询离线
struct node{int l,r,ans,op;
}c[maxn];
struct vertex{int l,r,x;
};
//单调栈
stack<vertex>st_mx,st_mi;
inline bool cmp1(node nx,node ny){return nx.r<ny.r;}
inline bool cmp2(node nx,node ny){return nx.op<ny.op;}
inline void ipt(){scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);scanf("%lld",&q);for(int i=1;i<=q;i++){scanf("%lld%lld",&c[i].l,&c[i].r);c[i].op=i;}sort(c+1,c+q+1,cmp1);
} 
inline void upd(int i){t[i].ans=t[i<<1].ans+t[i<<1|1].ans;if(t[i<<1].mn<t[i<<1|1].mn){t[i].mn=t[i<<1].mn;t[i].cnt=t[i<<1].cnt;}else if(t[i<<1].mn>t[i<<1|1].mn){t[i].mn=t[i<<1|1].mn;t[i].cnt=t[i<<1|1].cnt;}else {t[i].mn=t[i<<1].mn;t[i].cnt=t[i<<1].cnt+t[i<<1|1].cnt;}return ;
}
inline void build(int i,int l,int r){t[i].l=l,t[i].r=r;if(l==r){t[i].mn=l;t[i].cnt=1;return ;}int mid=l+r>>1;build(i<<1,l,mid);build(i<<1|1,mid+1,r);upd(i);
}
inline void modify1(int i,int x){t[i].mn+=x;t[i].lazy+=x;
}
inline void modify2(int i,int x){t[i].ans_lazy+=x;t[i].ans+=x*t[i].cnt;
}
inline void pushdown(int i){if(t[i].lazy!=0){modify1(i<<1,t[i].lazy);modify1(i<<1|1,t[i].lazy);t[i].lazy=0;}if(t[i].ans_lazy!=0){if(t[i<<1].mn==t[i].mn)modify2(i<<1,t[i].ans_lazy);if(t[i<<1|1].mn==t[i].mn)modify2(i<<1|1,t[i].ans_lazy);t[i].ans_lazy=0;}return ;  
}
//区间加 
inline void change(int i,int l,int r,int x){if(t[i].l>r||t[i].r<l)return ;if(l<=t[i].l&&t[i].r<=r){modify1(i,x);return ;}pushdown(i);change(i<<1,l,r,x);change(i<<1|1,l,r,x);upd(i);
}
inline int query(int i,int l,int r){if(t[i].l>r||t[i].r<l)return 0;if(l<=t[i].l&&t[i].r<=r)return t[i].ans;pushdown(i);return query(i<<1,l,r)+query(i<<1|1,l,r); 
}
inline void solve(){int o=1;for(int i=1;i<=n;i++){change(1,1,n,-1);int l=i,r=i;while(!st_mx.empty()){vertex u=st_mx.top();if(u.x<a[i]){l=min(l,u.l);change(1,u.l,u.r,a[i]-u.x);st_mx.pop();}else break;}st_mx.push((vertex){l,r,a[i]});l=i,r=i;while(!st_mi.empty()){vertex u=st_mi.top();if(u.x>a[i]){l=min(l,u.l);change(1,u.l,u.r,u.x-a[i]);st_mi.pop();}else break;}st_mi.push((vertex){l,r,a[i]});modify2(1,1);while(c[o].r==i&&o<=q){c[o].ans=query(1,c[o].l,c[o].r);++o;}}
}
inline void opt(){sort(c+1,c+q+1,cmp2);for(int i=1;i<=q;i++)printf("%lld\n",c[i].ans);
}
signed main(){ipt();build(1,1,n);solve();opt();return 0;
}