WZHS2023 特长生招生 Day2 题解
huangrenheluogu
·
·
个人记录
去年：rk4 的分数至少为 200。
Sol
A 矩阵游戏
处理 (n-1)i+j 的贡献，对于行，我们处理出行标记 lin_i，答案应该是 (A(n-1)i+B)lin_i，这个证明是容易的，而 A,B 只和列标记有关，处理一下是容易的。
### [B 旋转子段](https://www.luogu.com.cn/problem/U419988)
枚举 $i$ 子段，观察旋转到 $a_i=i$ 的地方需要旋转哪一个子段。然后枚举旋转中心，把以这个中心旋转的子段按照旋转半径排序，预处理出前/后多少个已经满足 $a_i=i$ 的就好了。
$O(n\log n)$。
### [C 操作](https://www.luogu.com.cn/problem/U420001)
写了一个 $O(n^2\log n)$，但是过了。
**我的做法：**
钦定一个最小的数 $x$，然后从这个数到大删除，容易证明这样是最优的。能删除的条件就是左边第一个小于 $x$ 的和右边第一个大于 $x$ 个数之间有大于等于 $k$ 个数。这个可以用树状数组维护。
$O(n^2\log n)$。
**官解：**
考虑双指针，判断值域 $[l,r]$ 是否可行。
查找出一段 $a_i\ge l$ 的 $a_i\in[l,r]$ 的数量，容易算出这一段区间的贡献，这个东西可以双指针。
于是做好了，$O(n^2)$。
### [D 平均](https://www.luogu.com.cn/problem/U420004)
这一看就是每一个数都减掉 $x$，然后总和为 $0$。
$f_{i,j}$ 表示前 $i$ 个物品选了 $j$ 个的答案。转移方程简单，不知道为什么当时写了很抽象的代码，凑合这看吧。
转移的时候就是枚举大于 $0$ 和小于 $0$ 选择的数量，然后直接调用就好了。
复杂度 $O(nV)$，$V$ 是最多可以选择的价值。
## My Codes
### A
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, m, k, x, y, col[N], lin[N], ans, sum1, sum2;
char c;
signed main(){
scanf("%lld%lld%lld", &n, &m, &k);
for(int i = 1; i <= n; i++){
lin[i] = 1;
}
for(int i = 1; i <= m; i++){
col[i] = 1;
}
for(int i = 1; i <= k; i++){
c = getchar();
while(c != 'R' && c != 'S') c = getchar();
scanf("%lld%lld", &x, &y);
if(c == 'R'){
lin[x] = lin[x] * y % mod;
}
else{
col[x] = col[x] * y % mod;
}
}
for(int i = 1; i <= m; i++){
(sum1 += col[i]) %= mod;
(sum2 += i * col[i]) %= mod;
}
for(int i = 1; i <= n; i++){
(ans += (sum1 * (i - 1) % mod * m % mod + sum2) % mod * lin[i] % mod) %= mod;
}
printf("%lld\n", ans);
return 0;
}
```
### B
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, a[N], ans, f[N], g[N], L, R;
struct node{
int midl, midr, l, r;
inline void calc(){
if(l > r) swap(l, r);
midl = l + r >> 1, midr = l + r + 1 >> 1;
}
}b[N];
inline bool cmp(node x, node y){
if(x.midl != y.midl) return x.midl < y.midl;
if(x.midr != y.midr) return x.midr < y.midr;
return x.l > y.l;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
ans += (a[i] == i);
}
for(int i = 1; i <= n; i++){
b[i].l = i, b[i].r = a[i];
b[i].calc();
}
for(int i = 1; i <= n; i++){
f[i] = f[i - 1] + (a[i] == i);
}
for(int i = n; i; i--){
g[i] = g[i + 1] + (a[i] == i);
}
sort(b + 1, b + n + 1, cmp);
for(int i = 1, j, k; i <= n; i = j){
j = i;
while(b[j].midl == b[i].midl && b[j].midr == b[i].midr){
k = j;
while(k <= n && b[k].l == b[j].l && b[k].r == b[j].r) k++;
j = k;
ans = max(ans, f[b[j - 1].l - 1] + g[b[j - 1].r + 1] + j - i);
}
}
printf("%d\n", ans);
return 0;
}
```
### C
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, k, q, a[N], b[N], m, pos[N], sum[N], t, las, L[N], c[N], p, cnt, res, R[N], ans = 2e9;
inline bool cmp(int x, int y){
return a[x] < a[y];
}
inline void add(int x){
while(x <= n){
c[x]++;
x += x & -x;
}
}
inline int get(int x){
int res = 0;
while(x){
res += c[x];
x -= x & -x;
}
return res;
}
inline int query(int l, int r){
return get(r) - get(l - 1);
}
inline void calc(int x){
las = 1;
cnt = 0;
for(int i = 1; i <= n; i++) c[i] = 0;
for(int i = 1; i <= n; i++){
if(a[i] < x){
las = i + 1;
}
else L[i] = las;
}
las = n;
for(int i = n; i; i--){
if(a[i] < x){
las = i - 1;
}
else R[i] = las;
}
res = -1;
for(int i = 1; i <= n; i++){
p = pos[i];
if(a[p] < x) continue ;
if(R[p] - L[p] + 1 - query(L[p], R[p]) >= k){
cnt++;
if(cnt == q){
res = a[p] - x;
ans = min(ans, res);
return ;
}
add(p);
}
if(n - i + cnt < q) return ;
}
}
int main(){
scanf("%d%d%d", &n, &k, &q);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
assert(a[i]);
}
for(int i = 1; i <= n; i++){
pos[i] = i;
}
sort(pos + 1, pos + n + 1, cmp);
sort(b + 1, b + n + 1);
m = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= m; i++){
calc(b[i]);
if(!(~res)) break ;
}
// assert(ans < 2000000000);
printf("%d\n", ans);
return 0;
}
```
### D
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353, N = 151, M = 3e5 + 1;
int k, q, up, n, x, f[N][M], sum[N][M], preup, now, tmp, ans, a1, a2;
inline void upd(int &x, int y){
x += y;
if(x >= mod) x -= mod;
}
signed main(){
// freopen("505.in", "r", stdin);
// freopen("505.out", "w", stdout);
scanf("%d%d", &k, &q);
up = 75 * 76 / 2;
up = up * k;
// cerr << up << endl;
f[0][0] = 1;
n = 150;
for(int i = 1; i <= n; i++){
now = 0, tmp = 0;
preup += i * k;
preup = min(preup, up);
for(int j = 0; j <= preup; j++){
sum[now][tmp] = f[i - 1][j];
if(tmp) upd(sum[now][tmp], sum[now][tmp - 1]);
now++;
if(now >= i) now -= i, tmp++;
}
now = 0, tmp = 0;
for(int j = 0; j <= preup; j++){
if(tmp <= k) f[i][j] = sum[now][tmp];
else f[i][j] = sum[now][tmp] - sum[now][tmp - k - 1];
now++;
if(f[i][j] < 0) f[i][j] += mod;
if(now >= i) now -= i, tmp++;
}
now = 0, tmp = 0;
for(int j = 0; j <= preup; j++){
sum[now][tmp] = 0;
now++;
if(now >= i) now -= i, tmp++;
}
}
while(q--){
scanf("%d%d", &n, &x);
a1 = x - 1, a2 = n - x;
if(a1 > a2) swap(a1, a2);
ans = 0;
now = a1 * (a1 + 1) / 2;
now = min(1ll * now * k, 1ll * up);
for(int i = 0; i <= now; i++){
upd(ans, 1ll * f[a1][i] * f[a2][i] % mod);
// printf("%d %d %d\n", i, f[a1][i], f[a2][i]);
}
ans = 1ll * ans * (k + 1) % mod;
upd(ans, mod - 1);
printf("%d\n", ans);
}
return 0;
}
```
## 官方代码
### A
```cpp
#include <bits/stdc++.h>
using namespace std;
int N,M,K;
const int MOD = (1e9) + 7;
int R[1000005];
int sumR;
int C[1000005];
int S;
int rez;
int element(int i,int j){
return (1LL * (i - 1) * M + j) % MOD;
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
for(int i = 1;i <= 1000000;i++){
R[i] = C[i] = 1;
}
cin >> N >> M >> K;
for(int i = 1;i <= K;i++){
char c;
int x,y;
cin >> c >> x >> y;
if(c == 'R'){
R[x] = 1LL * R[x] * y % MOD;
}
else {
C[x] = 1LL * C[x] * y % MOD;
}
}
for(int i = 1;i <= N;i++){
S = (1LL * S + 1LL * element(i,1) * R[i]) % MOD;
sumR += R[i];
if(sumR >= MOD){
sumR -= MOD;
}
}
for(int i = 1;i <= M;i++){
rez = (1LL * rez + 1LL * S * C[i]) % MOD;
if(rez >= MOD){
rez -= MOD;
}
S += sumR;
if(S >= MOD){
S -= MOD;
}
}
cout << rez<<endl;
return 0;
}
```
### B
```cpp
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 5e5+5;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch <= '9' && ch >= '0')
x = x*10+ch-'0',ch = getchar();
return x*f;
}
vector<int>G[Maxn<<1];
int N,ctr,L,R,ans;
int A[Maxn],Sum[Maxn],Suf[Maxn];
bool cmp(int x,int y){
return abs(2*x - ctr) < abs(2*y - ctr);
}
int main(){
freopen("rotate.in","r",stdin);
freopen("rotate.out","w",stdout);
N = read();
for(int i = 1 ; i <= N ; ++i){
A[i] = read();
G[A[i] + i].push_back(i);
if(A[i] == i) Sum[i] = 1;
Sum[i] += Sum[i - 1];
}
for(int i = N ; i ; --i){
if(A[i] == i) Suf[i] = 1;
Suf[i] += Suf[i + 1];
}
for(int i = 2 ; i <= 2*N ; ++i)
if(!G[i].empty()){
ctr = i;
int l , r , ret , n;
sort(G[i].begin(),G[i].end(),cmp);
n = G[i].size();
for(int j = 0 ; j < n ; ++j){
l = G[i][j];
r = i - G[i][j];
if(l > r) swap(l , r);
ret = Sum[l-1] + Suf[r + 1] + j + 1;
if(ret > ans) ans = ret,L = l,R = r;
}
}
printf("%d\n",ans);
return 0;
}
```
### C
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
inline ll read() {
register ll x=0,f=1;
register char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int n,k,q;
int a[N],b[N];
bool ok(int l,int r) {
register int pos=1,sum=0,t;
for(register int i=1; i<=n+1; i++) {
if(a[i]<b[l]) {
t=0;
for(register int j=pos; j<i; j++) {
if(a[j]<=b[r])t++;
}
sum+=max(0,min(t,i-pos+1-k)),pos=i+1;
}
}
return sum>=q;
}
int main() {
n=read(),k=read(),q=read();
for(register int i=1; i<=n; i++)a[i]=b[i]=read();
sort(b+1,b+1+n);
register int i,j,ans=1e9;
for(i=j=1; i<=n; i++) {
while(j<=n&&!ok(i,j))j++;
if(j<=n)ans=ans<b[j]-b[i]?ans:b[j]-b[i];
}
printf("%d",ans);
return 0;
}
```
### D
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
inline void mo(int& x){x>=MOD?x-=MOD:0;}
inline int mo1(int x){ return x>=MOD?x-MOD:x; }
int f[155][310005],s[155];
int n,k;
int main(){
freopen("average.in","r",stdin);
freopen("average.out","w",stdout);
scanf("%d",&k);
int n=150,q; scanf("%d",&q);
f[0][0]=1,s[0]=0;
for(int x=1;x<=n;++x){
if(x>n/2) s[x]=s[x-1];
else s[x]=s[x-1]+x*k;
for(int j=0;j<=s[x];++j){
f[x][j]=f[x-1][j];
if(j>=x){
mo(f[x][j]+=f[x][j-x]);
if(j>=(k+1)*x)
mo(f[x][j]+=MOD-f[x-1][j-(k+1)*x]);
}
// printf("[%d %d %d]",x,j,f[x][j]);
}
}
while(q--){
int n,x; scanf("%d%d",&n,&x);
int ans=0;
for(int j=0;j<=min(s[x-1],s[n-x]);++j)
ans=(ans+1ll*f[x-1][j]*f[n-x][j]%MOD*(k+1))%MOD;
mo(ans+=MOD-1);
printf("%d\n",ans);
}
return 0;
}
```