今天题目质量逆天，题也不是那个他讲的。应该是生气了。所以我也不打算写赛时记录了。
T1 分讨负数个数，T2 二分答案；T3 我写了哈希，想半天想不到性质；T4 小范围暴力大范围输出区间最大值 + 暴力之类的。
本场的感觉很不好。模拟赛期间最绝望的是闲下来：指已经不能进一步思考、没有什么需要调了、没有暴力要打了、没什么事干，就很难受。真不知道正式考场上遇到这种情况该怎么办。
妈的，最后 15min 想出来一个 T3 的部分分，没调完，我急了。赛时摆烂导致的！
给一个有正负数的序列。可以无限次将相邻两数都乘 1。求能得到最大的序列和。
分类讨论一下序列中个数：奇数个负数，则一定可以都变成正数；否则最后序列中一定有一个负数，让绝对值最小的数做负数就好了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n;
int tot;
ll ans;
int a[N];
int main(){
// freopen("flip.in","r",stdin);
// freopen("flip","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]<0) tot++;
a[i]=abs(a[i]);
}
sort(a+1,a+n+1);
if(tot&1) ans=-a[1];
else ans=a[1];
for(int i=2;i<=n;i++) ans+=a[i];
printf("%lld",ans);
}
不介绍题目了。二分答案板子。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,ans=-1;
int l,r;
int a[N];
ll m;
bool check(int x){
ll tot=0;
for(int i=1;i<=n;i++){
if(a[i]>x) tot+=a[i]-x;
}
return tot>=m;
}
int main(){
// freopen("cut.in","r",stdin);
// freopen("cut.out","w",stdout);
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
r=max(r,a[i]);
}
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
l=mid+1;
ans=mid;
}
else r=mid-1;
}
printf("%d",ans);
}
正解是线段树维护字符串的哈希值。
赛时写了 \(O(n^2l)\) 的暴力。最后想出了一个 \(O(l^2 n\text{ }logn)\) 的对于第三部分分的暴力但没写完。这 30pts 也不该失啊。
这是 70pts 的码。没想到这么好写。
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=3e4+10;
int n,len;
string s;
ull f;
map<ull,int> cnt[210];
ll ans;
int main(){
scanf("%d%d",&n,&len);
for(int i=1;i<=n;i++){
cin>>s;
for(int j=0;j<len;j++){
f=0;
for(int k=0;k<len;k++){
if(j==k) continue;
f=f*131+(s[k]-'a'+1);
}
ans+=cnt[j][f];
cnt[j][f]++;
}
}
printf("%lld",ans);
}
然后发现那个 \(O(L)\) 计算删掉一位的哈希值的过程可以优化成 \(O(1)\)，即先处理出整个串的哈希值。
在这里的字符串哈希指转为一个 P 进制数，所以减去那一位的哈希值就能写成 f-(s[j]-'a'+1)*p[len-j-1]，其中 p 数组是我们预处理出用来进行算的 P 的幂。通常取 131 或 13331，此时冲突的可能性极低。同时，取模其实是个很慢的过程，所以这里用 unsigned long long 的类型的自然溢出代替。
\(O(Ln\text{ }log n)\) 理论上能过，但是容易卡。加了很多奇奇怪怪的卡常优化，在 oj 上成功卡到了 90pts。虽然最后交上了完美的 std。
这是我的去掉火车头的 Code：（其实用 vector 优化常数就能过了。但是我太懒了不想写。）
#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=3e4+10;
int n,len;
char s[N];
ull f,p[210];
map<ull,int> cnt[210];
ll ans;
int main(){
scanf("%d%d",&n,&len);
p[0]=1;
for(int i=1;i<=len;i++) p[i]=p[i-1]*131;
for(int i=1;i<=n;i++){
scanf("%s",s);
f=0;
for(int j=0;j<len;j++)
f=f*131+(s[j]-'a'+1);
for(int j=0;j<len;j++){
ull t=f-(s[j]-'a'+1)*p[len-j-1];
ans+=cnt[j][t];
cnt[j][t]++;
}
}
printf("%lld",ans);
return 0;
}
这是伟大的 std。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,l,s;
ll ha[30005],t[30005],Hina[205];
char c[300005][205];
const int p = 2333;
int main()
{
#ifndef ONLINE_JUDGE
freopen("match.in", "r", stdin);
freopen("match.out", "w", stdout);
#endif
scanf("%d%d%d",&n,&l,&s);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= l; j++)
{
cin >> c[i][j];
ha[i] = ha[i] * p + c[i][j];
}
}
Hina[0] = 1;
for (int i = 1; i <= l; i++)
{
Hina[i] = Hina[i - 1] * p;
}
int ans = 0;
for (int i = 1; i <= l; i++)
{
for (int j = 1; j <= n; j++)
{
t[j] = ha[j] - c[j][i] * Hina[l - i];
}
sort(t + 1,t + n + 1);
int tmp = 1;
for (int j = 1; j < n; j++)
{
if (t[j] != t[j + 1]) tmp = 1;
else
{
ans += tmp;
tmp++;
}
}
}
printf("%d\n",ans);
//system("pause");
return 0;
}
赛时纯纯的脑瘫了属于是。不太会哈希导致的。
这是赛时的码。
#include<bits/stdc++.h>
#define push_up(x) (ans[x]=max(ans[x<<1],ans[x<<1|1]))
using namespace std;
const int N=2e5+10;
const int M=6e5+10;
int n,m;
int a[N];
int flag=1;
int ans[M],tag[M];
void build(int p,int l,int r){
int mid=(l+r)>>1;
if(l==r){
ans[p]=a[l];
return;
}
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
}
int query(int p,int l,int r,int nl,int nr){
if(l>=nl&&r<=nr) return ans[p];
int mid=(l+r)>>1;
int ans=0;
if(nl<=mid) ans=query(p<<1,l,mid,nl,nr);
if(nr>mid) ans=max(ans,query(p<<1|1,mid+1,r,nl,nr));
return ans;
}
void solve(){
build(1,1,n);
while(m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
int ans=query(1,1,n,l,r);
if(ans<k){
printf("%d\n",ans);
continue;
}
ans=0;
for(int i=l;i<=r;i++){
ans=max(ans,a[i]%k);
if(ans==k-1) break;
}
printf("%d\n",ans);
}
}
int main(){
// freopen("flower.in","r",stdin);
// freopen("flower","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>300) flag=0;
}
if((n>10000&&flag)||n>50000){solve();return 0;}
while(m--){
int l,r,k;
int ans=0;
scanf("%d%d%d",&l,&r,&k);
for(int i=l;i<=r;i++){
ans=max(ans,a[i]%k);
if(ans==k-1) break;
}
printf("%d\n",ans);
}
}
（这里的线段树其实就是个求区间最值的幌子。我其实不会写线段树啊。
贺了一份代码 qwq。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m;
int a[N];
int len,cnt;
int mx[N],bel[N];
struct node{int l,r;int mx[N];}bl[2005];
int query(int l,int r,int mod){
int res=0;
if(bel[l]==bel[r]){
for(int i=l;i<=r;i++) res=max(res,a[i]%mod);
}
else{
for(int i=l;bel[i]==bel[l];i++) res=max(res,a[i]%mod);
for(int i=bel[l]+1;i<bel[r];i++) res=max(res,bl[i].mx[mod]);
for(int i=r;bel[i]==bel[r];i--) res=max(res,a[i]%mod);
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
len=sqrt(n*log2(n));
for(int i=1;i<=n;i++){
bel[i]=(i-1)/len+1;
scanf("%d",&a[i]);
if(bel[i]!=bel[i-1]){
bl[bel[i]].l=i;
cnt++;
}
bl[bel[i]].r=i;
}
for(int i=1;i<=cnt;i++){
memset(mx,0,sizeof mx);
for(int j=bl[i].l;j<=bl[i].r;j++) mx[a[j]]=a[j];
for(int j=1;j<=1e5;j++) mx[j]=max(mx[j-1],mx[j]);
for(int k=1;k<=1e5;k++)
for(int num=0;num<=1e5;num+=k)
bl[i].mx[k]=max(bl[i].mx[k],mx[min(100000,num+k-1)]-num);
}
for(int i=1;i<=m;i++){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",query(l,r,k));
}
return 0;
}