目录
随便找了场听说风评不错的洛谷月赛，因为我的实力是 Div2 选手，所以从 Div2 做起！！
因为洛谷不公开代码，所以代码得贴，所以省略了码头。
花如幻想一般
Solution
翻转一定只会做一次，加上整数等价于改为整数。
扫一下就行。
Code
const int N=5e5;
int n,a[N+10],b[N+10];
int calc() {
int ret=0;
FOR(i,1,n) if(a[i]!=b[i]) ret++;
return ret;
}
int main() {
n=read();
FOR(i,1,n) a[i]=read();
FOR(i,1,n) b[i]=read();
int ans1=calc();
reverse(a+1,a+n+1);
printf("%d\n",min(ans1,calc()+1));
}
灵山之上神风起
Solution
四种情况：
- 全选 \(1\)。
- 选最左的 \(2\)，与这个 \(2\) 往右的所有 \(1\)。
- 选最右的 \(3\)，与这个 \(3\) 往左的所有 \(1\)。
- 选最左的 \(2\)，最右的 \(3\)，与 \(2,3\) 中间的所有 \(1\)。
扫一遍即可。
Code
const int N=1e5;
int n,a[N+10];
int main() {
n=read();
FOR(i,1,n) a[i]=read();
int ans=0,sum=0,i1,i2;
FOR(i,1,n) ans+=(a[i]==1);
FOR(i,1,n) if(a[i]==2) {i1=i;break;}
ROF(i,n,1) if(a[i]==3) {i2=i;break;}
if(i1) {
sum=1;
FOR(i,i1,n) sum+=(a[i]==1);
ans=max(ans,sum);
}
if(i2) {
sum=1;
FOR(i,1,i2) sum+=(a[i]==1);
ans=max(ans,sum);
}
if(i1&&i2&&i1<=i2) {
sum=2;
FOR(i,i1,i2) sum+=(a[i]==1);
ans=max(ans,sum);
}
printf("%d\n",ans);
}
来自地上的支援
Solution
考虑 \(x\) 的前后，\([1,x-1]\) 的数一定要使得现在这个值能被选到不然就再也选不到了，可以在一开始的时候模拟出来。
而 \([x+1,n]\) 的数，观察发现要想取到 \(x\) 需要 \(a_x+(i-x)v>a_i\)。移项得 \(a_x>a_i-iv+xv\)，\(a_i-iv\) 可以预处理，所以简单维护一下即可。
Code
const int N=2e6;
int n;
int ma[N*4+10],a[N+10],b[N+10];
priority_queue<int> pq;
void build(int p,int l,int r) {
if(l==r) return ma[p]=a[l],void();
int mid=(l+r)>>1;
build(p*2,l,mid),build(p*2+1,mid+1,r);
ma[p]=max(ma[p*2],ma[p*2+1]);
}
int query(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return ma[p];
int mid=(l+r)>>1,m=-1e9;
if(x<=mid) m=max(m,query(p*2,l,mid,x,y));
if(y>mid) m=max(m,query(p*2+1,mid+1,r,x,y));
return m;
}
signed main() {
n=read();int q=read(),v=read();
FOR(i,1,n) {
a[i]=read(),pq.push(a[i]);
b[i]=pq.top()+v,pq.pop(),pq.push(b[i]);
}
FOR(i,1,n) a[i]-=i*v;
build(1,1,n);
ll a1=0,a2=0;
FOR(i,1,q) {
int x=read(),k=read();
if(x+k-1<=n) {
int s=max(b[x-1],query(1,1,n,x+1,x+k-1)+x*v+1);
a1^=s,a2+=s;
}
}
printf("%lld %lld\n",a1,a2);
}
夜空中的 UFO 恋曲
Solution
假如 \(x\) 为奇数，\(c\) 为偶数，那么最终的答案一定会是 \(1\)。
假如 \(x\) 和 \(c\) 均为偶数，\(x\) 的二进制末尾至少有一个 \(0\)，\(x^{2c}\) 末尾就至少有 \(2c\) 个 \(0\)，\(c\) 于是可以直接填在后面，所以答案就是 \(\text{lowbit}(c)\)。
假如 \(c\) 是奇数：
- 如果 \(a\) 是偶数，和之前一样，\(a^{2c}\) 末尾至少 \(2c\) 个 \(0\)，所以可以把 \(a\) 看成 \(c\)。
- 如果 \(a\) 是奇数，因为 \(c\) 也是奇数，异或完了就会变成偶数，回到上一种情况。
- 如果最后是奇数，那么答案是 \(1\)。
- 否则，答案为 \(\text{lowbit}(c^{2c}\oplus c)\)。
直接做就做完了，但是打表可以得到 \(\text{lowbit}(c^{2c}\oplus c)=\text{lowbit}(c-1)\)，做到 \(O(1)\)。
Code
ll a,b,c;
ll lowbit(ll a) {return a&-a;}
int main() {
a=read(),b=read(),c=read();
if(!(c&1)) {
if(a&1) printf("1\n");
else printf("%lld\n",lowbit(c));
}
else {
if((a&1)^(b&1)) printf("1\n");
else printf("%lld\n",lowbit(c-1));
}
}
死亡之后愈发愉悦
Solution
打个表先。
打表找规律得到，对于某一个完全平方数 \(x^2\)，从这个数开始往后 \(x+1\) 个是可爱的数，然后 \(x\) 个是不可爱的数。
倍增出 \(x\) 后面的连续段，设长为 \(p\)，从 \(p\) 往后继续找到后面的这个段，设长为 \(q\)，用 \(p,q\) 就可以计算出来所有答案。
求 \(p\) 是需要两次倍增的，一次正着一次倒着，容易理解是为什么。
求 \(q\) 同样需要倍增，但倍增两次次数就超标了，但是可以优化，我们从 \(2^k\le p\) 的 \(k\) 开始倍增，可以省下一个 \(\log\)。
Code
int T;
map<ll,int> p;
int query(ll x) {
if(p.find(x)!=p.end()) return p[x];
printf("? %lld\n",x),fflush(stdout);
return p[x]=read();
}
ll get(ll x,ll k) {
ll st=query(x);
if(query(x+1)!=st) return x;
ll beg=0;
while(1ll<<(beg+1)<=k) beg++;
while(1) {
if(query(x+k+(1ll<<beg))!=st) break;
k+=1ll<<beg,beg++;
}
ROF(i,beg-1,0) if(query(x+k+(1ll<<i))==st) k+=(1ll<<i);
return x+k;
}
signed main() {
T=read();
while(T--) {
p.clear();
ll i1=get(0,1);
ll i2=get(i1+1,max(i1-1,1ll));
ll L=i2-i1;
if(query(0)==0) printf("! %lld\n",(L-1)*(L-1)-1-i1);
else printf("! %lld\n",L*L+L-i1);
}
}
魔力的磁云
磁铁。
Solution
设 \(b_i=4^{a_i}\)，\(c_i=d_0-d_i\)。
第一步定向。
如果 \(c_i=1\)，则我们声称 \(i-1,i,i+1\) 为一个方向，必要性不证了，证一下充分性，首先如果去掉这个磁铁后长度只减少一，那么实际上只有两种可能，一种是两个放一起且两个磁铁磁力相同，这是不可能的，单独一个也不可能，所以只有长度 \(\ge 3\) 的连续段是可能的。
接下来，我们来分析一下两个连续方向相同的和左右方向都与其不同的差异，设连续的磁铁磁力分别为 \(a,b,c\)，如果 \(b,c\) 方向相同，那么初始 \(a,c\) 的距离为 \(a+b+1\)，移除 \(b\) 后是 \(a+c\)，差值为 \(b-c+1\)，这个值对三取模的答案为 \(1\)。
而如果 \(a,b,c\) 的方向均不相同，则初始 \(a,c\) 的距离为 \(a+2b+c+1\)，移除 \(b\) 后变为 \(0\)，差值就是 \(a+2b+c+1\)，对三取模得到 \(2\)。
根据上面的说明，如果 \(c_i\not=1\) 且 \(c_i\equiv 1\pmod 3\) 时我们声称这个磁铁属于一个长度为 \(2\) 的连续段，但是我们并不知道这个磁铁是和 \(i-1\) 一段还是和 \(i+1\) 一段，但是我们可以先取出 \(\ge 3\) 的连续段和长度为 \(1\) 的连续段，剩下的就是长度为二的连续段组成的长段，从开头开始划分即可。
这一部分可以精细实现到 \(O(n)\)，代码中使用了并查集。
第二步规定磁力。
首先我们先考察一个长度 \(\ge 2\) 的连续段，考虑相邻的磁铁 \(i,j,k\)，其中 \(j,k\) 方向相同，则有 \(c_j-1=b_j-b_k\)，知晓两数之差，可以进行还原，注意到 \(b_i=4^{a_i}\)，两个这样的数相减，二进制下就是 \(10000\ldots00-1000\ldots00\)，其答案的 \(\text{lowbit}\) 必然是 \(b_k\)，则 \(b_j=(c_j-1)+b_k\)，注意到这样可以确定 \(b_l,b_{l+1},b_{r-1},b_{r}\) 的磁力，而 \([l+2,r-2]\) 的磁力可以随意赋值。
接下来考察长度为 \(1\) 的单个磁铁，同样考虑相邻的磁铁 \(i,j,k\)，\(c_j-1=b_i+2b_j+b_k\)，这个时候可以分两种情况讨论：
- \(\text{popcount}(c_j-1)=3\)，注意到我们只要确定 \(b_j\)，同样的 \(b_i=4^{a_i}\) 又可以帮上大忙，\(b_i\) 的二进制表示下 \(1\) 的位置必然是偶数位，而乘上一个 \(2\) 就到了奇数位，于是取出奇数位，这个就是 \(2b_j\)。
- \(\text{popcount}(c_j-1)=2\)，此时 \(b_i=b_k\)，你无法确定奇数位上的是 \(b_i+b_k\) 还是 \(2b_j\) 但是如果你知道 \(b_i\) 或是 \(b_k\) 就可以确定 \(b_j\)。
如果存在长度 \(\ge 2\) 的连续段，我们就可以确定全部磁力，如果不存在，则利用上述方法无法确定的情况只有一种，就是所有的 \(\text{popcount}(c_j-1)=2\) 且相邻磁铁颜色不同，此时奇数位磁铁磁力相同，偶数位磁铁磁力相同，直接分配即可。
这一部分可以精细实现到 \(O(n)\)，总时间复杂度 \(O(n)\)。
Code
const int N=1e6,V=1e7;
int n;
ll d0,d[N+10],c[N+10];
int f[N+10],a[N+10];
int rid(int x) {
if(x>n) return x-n;
if(x<1) return x+n;
return x;
}
int popcount(ll x) {return __builtin_popcountll(x);}
int lg(int x) {return __lg(x);}
int lowbit(int x) {return x&-x;}
int fa[N+10],siz[N+10];
int find(int x) {return fa[x]=(fa[x]==x?x:find(fa[x]));}
void merge(int x,int y) {
int fx=find(x),fy=find(y);
if(fx==fy) return;
fa[fy]=fx,siz[fx]+=siz[fy];
}
int get(int x) {
if(x==-1) return 0;
else return x^1;
}
void get_f() {
FOR(i,1,n) fa[i]=i,siz[i]=1;
if(c[1]==1) merge(1,n),merge(1,2);
if(c[n]==1) merge(1,n),merge(n-1,n);
FOR(i,2,n-1) if(c[i]==1) merge(i-1,i),merge(i,i+1);
vi p;
FOR(i,1,n) if(c[i]>=0&&c[i]%3==2) p.pb(i);
FOR(i,1,n) if(siz[find(i)]!=1) p.pb(i);
sort(p.begin(),p.end());
FOR(i,0,sz(p)-2) for(int j=p[i]+1;j<=p[i+1]-1;j+=2) merge(j,j+1);
if(p[sz(p)-1]!=n||p[0]!=1)
for(int i=rid(p[sz(p)-1]+1);rid(i-1)!=rid(p[0]-1);i=rid(i+2))
merge(i,rid(i+1));
int las=1;
FOR(i,1,n) if(find(i)==i) f[i]=las^1,las^=1;
FOR(i,1,n) f[i]=f[find(i)];
}
void solvebt() {
int x=lowbit(c[1]-1),y=lowbit(c[1]-1-x);
x=(lg(x)-1)/2,y=(lg(y)-1)/2;
for(int i=1;i<=n;i+=2) a[i]=x;
for(int i=2;i<=n;i+=2) a[i]=y;
}
void solvenof(int l,int r) {
FOR(i,l,r) if(a[i]==-1) a[i]=1919810+i;
}
void gtdel(int x,int y,ll v) {
if(v<0) v=-v,swap(x,y);
ll ay=lowbit(v),ax=ay+v;
a[x]=lg(ax)/2,a[y]=lg(ay)/2;
}
void solve3(int i,int j,int k,ll v) {
if(popcount(v)==3) {
ll x=lowbit(v),y=lowbit(v-x),z=lowbit(v-x-y);
x=lg(x),y=lg(y),z=lg(z);
if(x%2==1) a[j]=(x-1)/2;
if(y%2==1) a[j]=(y-1)/2;
if(z%2==1) a[j]=(z-1)/2;
}
else {
int z=-1;
if(a[i]!=-1) z=a[i];
if(a[k]!=-1) z=a[k];
ll x=lowbit(v),y=lowbit(v-x);
x=(lg(x)-1)/2,y=(lg(y)-1)/2;
if(z==x) a[j]=y;
else a[j]=x;
}
}
void get_a() {
bool FL=1;
FOR(i,1,n) FL&=(c[i]-1>=0&&popcount(c[i]-1)==2);
FOR(i,1,n) FL&=(f[i]!=f[rid(i+1)]);
if(FL) return solvebt();
int i1=0,i2=0,fl=0,fr=0;
FOR(i,1,n) if(f[i]!=f[1]) {i1=i-1;break;}
ROF(i,n,1) if(f[i]!=f[1]) {i2=rid(i+1);break;}
if(i1==0&&i2==0) return solvenof(1,n);
vi p;p.clear();
if(i1!=i2) {
fl=i2,fr=i1;
gtdel(i2,rid(i2+1),c[i2]-1),gtdel(i1,rid(i1-1),c[i1]-1);
if(fl>fr) solvenof(fl,n),solvenof(1,fr);
else solvenof(fl,fr);
}
int las=i1;
i1=rid(i1+1),i2=rid(i2-1);
FOR(i,i1,i2) {
if(f[i]!=f[i-1]) {
if(las!=i-1) {
if(!fl) fl=las,fr=i-1;int r=i-1;
gtdel(las,las+1,c[las]-1),gtdel(r,r-1,c[r]-1);
solvenof(las,r);
}
las=i;
}
}
if(las!=i2) {
if(!fl) fl=las,fr=i2;
gtdel(las,las+1,c[las]-1),gtdel(i2,i2-1,c[i2]-1);
solvenof(las,i2);
}
if(fl>fr) {
FOR(i,fr+1,fl-1) if(c[i]-1>=0&&a[i]==-1) solve3(rid(i-1),i,rid(i+1),c[i]-1);
}
else {
ROF(i,fl-1,1) if(c[i]-1>=0&&a[i]==-1) solve3(rid(i-1),i,rid(i+1),c[i]-1);
FOR(i,fr+1,n) if(c[i]-1>=0&&a[i]==-1) solve3(rid(i-1),i,rid(i+1),c[i]-1);
}
}
signed main() {
n=read(),d0=read();
for(int i = 1; i <= n; i++) d[i] = read();
FOR(i,1,n) c[i]=d0-d[i],f[i]=-1,a[i]=-1;
get_f(),get_a();
FOR(i,1,n) printf("%lld %lld\n",f[i],a[i]);
}
纯粹的复仇女神
Solution
离线扫描线。
首先先使用单调栈求出每一个数的影响区间。
接下来对于每一个 \(r\)，我们采用如下操作：
- 插入所有影响区间 \([L_r,R_r](a_r)\)。
- 处理掉所有以 \(r\) 为右端点的询问。
- 撤销掉以 \(r\) 为右端点的操作。
使用一个标记永久化的线段树，用 multiset 维护标记即可。
Code
const int N=2e5;
int n,q,c[N+10],a[N+10],L[N+10],R[N+10];
priority_queue<int> add[N*4+10],del[N*4+10];
void update(int p,int l,int r,int x,int y,int w) {
if(x<=l&&r<=y) {
if(w>0) add[p].push(w);
else del[p].push(-w);
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(p*2,l,mid,x,y,w);
if(y>mid) update(p*2+1,mid+1,r,x,y,w);
}
int query(int p,int l,int r,int x) {
int ret=0;
while(sz(add[p])&&sz(del[p])&&add[p].top()==del[p].top()) add[p].pop(),del[p].pop();
if(sz(add[p])) ret=add[p].top();
if(l==r) return ret;
int mid=(l+r)>>1;
if(x<=mid) chkmax(ret,query(p*2,l,mid,x));
else chkmax(ret,query(p*2+1,mid+1,r,x));
return ret;
}
list<int> st[N+10];
struct Interval {int l,r,w;};
struct Query {int l,id;};
vector<Interval> I[N+10];
vector<Query> Q[N+10];
int ans[N*5+10];
int main() {
n=read(),q=read();
FOR(i,1,n) st[i].pb(0);
FOR(i,1,n) c[i]=read();
FOR(i,1,n) a[i]=read();
FOR(i,1,n) {
while(a[st[c[i]].back()]>=a[i]) st[c[i]].pop_back();
L[i]=st[c[i]].back()+1,st[c[i]].pb(i);
}
FOR(i,1,n) st[i].clear(),st[i].pb(n+1);
ROF(i,n,1) {
while(a[st[c[i]].back()]>=a[i]) st[c[i]].pop_back();
R[i]=st[c[i]].back()-1,st[c[i]].pb(i);
}
FOR(i,1,n) I[i].pb({L[i],i,a[i]}),I[R[i]+1].pb({L[i],i,-a[i]});
FOR(i,1,q) {
int l=read(),r=read();
Q[r].pb({l,i});
}
FOR(i,1,n) {
for(auto j:I[i]) update(1,1,n,j.l,j.r,j.w);
for(auto j:Q[i]) ans[j.id]=query(1,1,n,j.l);
}
FOR(i,1,q) write(ans[i]),pc('\n');
return fl;
}
禁断之门对面，是此世还是彼世
Solution
史诗级的题目。
先来考虑化简贡献式（\(s_i\) 表示 \(b_i\) 的前缀和）：
\[\begin{aligned} f(B)&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{t}\sum\limits_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})}A_{i,k}\\ &=\sum^n_{i=1}\sum^t_{j=1}\sum_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})} a_ib_k\\ &=\sum^n_{i=1}a_i\sum^t_{j=1}\sum_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})} b_k\\ &=\sum^n_{i=1}a_i\sum^t_{j=1}s_{\max(B_{i,j},B_{i+1,j})}-s_{\min(B_{i,j},B_{i+1,j})-1} \end{aligned} \]考虑 \(B\) 的每一行，设第 \(i\) 行为 \(b_i\)，定义行与行之间的贡献函数为：
\[F(A,B)=\sum_{i=1}^ts_{\max(A_i,B_i)}-s_{\min(A_i,B_i)-1} \]可见性质：\(F(A,B)=F(B,A)\)。
很好证的性质：\(B\) 的行上的组成一定形如 \(X,Y,X,Y,X,Y,\ldots\)，可以调整证明。
则，问题变为求 \(\sum^n_{i=1}a_iF(X,Y)\) 的最大值。\(a_i\) 的和是一个定值，所以我们希望 \(F(X,Y)\) 尽可能小。
这是一个匹配问题，等价于一个二分图，然后左右两边选出 \(k\) 组匹配，左侧的 \(i\) 不能选定右侧的 \(i\)，可以建出费用流模型，时间复杂度过大，无法通过。
考虑换一种思路，针对一组上面的匹配，设 \(a_i\) 匹配 \(b_i\)，我们将 \(a_i\) 向 \(b_i\) 连边，连出来的图形应当是只有环和链，挖掘这里的性质：
- 环不相交，考虑环 \(a,c\) 和 \(b,d\)，若 \(a<b<c<d\)，则交换 \(a,b\) 更优。这同时意味着环所占的位置是一个区间。
- 环的大小为 \(2\) 或 \(3\)，如环的大小为 \(4\)，假设是 \(i,i+1,i+2,i+3\)，则 \(b_{i+1}\)，\(b_{i+2}\) 都会被算三次，而拆成 \(i,i+1\) 和 \(i+2,i+3\) 明显更优。
设 dp 状态为 \(f_{i,j,0/1}\) 表示现在在 \(i\) 用了 \(j\) 条 \(i-1\) 有没有链接过来，枚举环长 \(2,3\) 和链继续接还是断开还是不接可以做到 \(O(m^2)\)。
费用流模型启示我们这个题其实有凸性，使用 wqs 二分优化即可，注意物品是边而非选的权值。
Code
const int N=5e5,mod=1e9+7;
const ll inf=0x3f3f3f3f;
int n,m,t,s,b[N+10];
struct node {
ll val;int num;
node operator + (const node &x) const {return {val+x.val,num+x.num};}
bool operator < (const node &x) const {
if(val==x.val) return num<x.num;
return val<x.val;
}
} f[N+10][2];
int calc(ll mid) {
f[0][0]=f[1][0]={0,0},f[0][1]=f[1][1]={inf,0};
FOR(i,2,m) {
f[i][0]=f[i-1][0];
node tmp={b[i-1]+b[i]-mid,1};
f[i][1]=min(f[i-1][1],f[i-2][0])+tmp;
tmp={2*(b[i-1]+b[i])-2*mid,2};
f[i][0]=min(f[i][0],f[i-2][0]+tmp);
if(i>2) {
tmp={2*(b[i-2]+b[i])+3*b[i-1]-3*mid,3};
f[i][0]=min(f[i][0],f[i-3][0]+tmp);
}
f[i][0]=min(f[i][0],f[i][1]);
}
return f[m][0].num;
}
int main() {
n=read(),m=read(),t=read();
FOR(i,1,n) s=(s+read())%mod;
FOR(i,1,m) b[i]=read();
ll l=1,r=3e9,ans;
while(l<=r) {
ll mid=(l+r)>>1;
if(calc(mid)<=t) l=mid+1,ans=mid;
else r=mid-1;
}
calc(ans);
printf("%lld\n",(f[m][0].val+ans*t)%mod*s%mod);
}