test28
我用什么才能留住你liuzhuni
我当然知道正解符合人类直觉，但是任意错解难道不符合很多人的直觉吗，没有大样例好难啊好难啊。注意到最优解一定可以是某种田忌赛马，不妨枚举赢的断点，来做一个暴力的对拍。
首先套路又直觉的，我们想办法说明先最大化 \(+1\) 的贡献不劣，用 \(man_i\) 表示一个等级为 \(i\) 的类入，用 \(bike_i\) 表示一个等级为 \(i\) 的车车。考虑最优情况下存在一个 \(bike_i\) 匹配 \(man_i\)，而后面有一个 \(man_{j(>i)}\) 被拥挤到不能 \(+1\)，那么让 \(man_j\) 抢走 \(man_i\) 的车车贡献是 \((1/2)-(0/1)\geq 0\)。
现在要想办法在最大化 \(+1\) 的前提下最大化 \(+0\) 的数量，显然确定了前者之后尽量 \(man_i\) 匹配 \(bike_i\) 即可，所以我们要思考什么样的情况下这个东西最大呢。考虑 \(bike_i\) 可以给 \(man_{l},man_r\) 匹配即 \(i<l<r\)，那么匹配给 \(l\) 更优，因为剩下来的 \(bike\) 更容易给 \(man_r\) 匹配 \(1/0\) 的贡献。而对于 \(bike_l,bike_r\) 可以匹配到 \(man_i\) 即 \(l<r<i\)，显然匹配 \(r\) 更好。那么不妨按照 \(man\downarrow\) 的顺序贪心 \(+1\) 的贡献，每一次查找一个编号最大的车车，最后再补算 \(0/-1\) 的贡献喵 qwq
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=300005;int n, x[N], y[N], Ans, stk[N], top;signed main() {freopen("liuzhuni.in","r",stdin); freopen("liuzhuni.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n;up(i,1,n) cin >> x[i];up(i,1,n) cin >> y[i];up(i,1,n) {while(top&&y[i]) {int j=stk[top];int k=min(y[i],x[j]);x[j]-=k, y[i]-=k, Ans+=k;if(!x[j]) --top;}stk[++top]=i;}up(i,1,n) {int k=min(x[i],y[i]);x[i]-=k, y[i]-=k, Ans-=y[i];}cout << Ans << '\n';return 0;
}
我给你瘦落的街道、绝望的落日、荒郊的月亮wogeini
设计一个函数 \(f(a)=\sum_{i\neq j} [情侣i,j相交但不包含]\)，显然这个必须下降到 \(0\)，同时依次操作最多让这个下降 \(2\)（如果你认为 \(i,j\) 是有序对，那么就是下降 \(1\)），又注意到任意时刻肯定有这样的位置（符合直觉且容易反证），所以最优操作次数就很好求了。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=1000005;int n, a[N], lst[N], Ans, tr[N];void add(int x,int v) {for( ; x<=n; x+=x&-x) tr[x]+=v;
}int ask(int x) {int ret=0;for( ; x; x-=x&-x) ret+=tr[x];return ret;
}signed main() {freopen("wogeini.in","r",stdin); freopen("wogeini.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n, Ans=n=(n<<1);up(i,1,n) cin >> a[i];up(i,1,n) {if(!lst[a[i]]) {lst[a[i]]=i;add(i,1);}else {int j=lst[a[i]];add(j,-2), add(i,1);Ans+=ask(i-1)-ask(j);}}cout << Ans/2 << '\n';return 0;
}
我给你一个one
我做过原题，且因为年代久远，我完全只记得怎么做，所以我毫不知情怎么写题解比较自然。在虚构推理的过程中，其实感觉有点像要直接 yy 出一组充要的东西，但是这个题目好想到的东西就那么点、凑起来又恰好是正解弥补了这一点。
DAG 图上的问题我们我们一般希望分层处理，其实也就是按照拓扑序考虑了，经验告诉我们用拓扑序当新标号很赞。那么对于一个 \(i\)，我们能用的边分为 \(u/v<i,u/v>i,u<i<v\)，三种前两种的贡献可以直接处理成正/反图上的最短路，单边贡献就是前后缀最大值惹，第三种刚好可以用来合并贡献，即动态维护 \(\max_{u<i<v} \{f_u+g_v+1\}\)，这个显然可以扫，来个 multiset 即可。
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_backusing namespace std;const int N=500005, inf=1e9;int n, m, tot, in[N], f[N], g[N], pre[N], suf[N], p[N], pos, Ans=inf;
vector<int> F[N], G[N];
queue<int> q;
multiset<int> counter;void eadd(int u,int v) {F[u].pb(v), G[v].pb(u), ++in[v];
}signed main() {freopen("one.in","r",stdin); freopen("one.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;while(m--) {int u, v;cin >> u >> v;eadd(u,v);}up(i,1,n) if(!in[i]) q.push(i);while(q.size()) {int x=q.front(); q.pop();p[++tot]=x;for(int y:F[x]) if(!--in[y]) q.push(y);}up(u,1,n) {int i=p[u];for(int j:F[i]) f[j]=max(f[j],f[i]+1);pre[u]=max(pre[u-1],f[i]);}dn(u,n,1) {int i=p[u];for(int j:G[i]) g[j]=max(g[j],g[i]+1);suf[u]=max(suf[u+1],g[i]);}up(u,1,n) {int i=p[u], Pluto=max(pre[u-1],suf[u+1]);for(int j:G[i]) {int val=f[j]+g[i]+1;counter.erase(counter.find(val));}if(counter.size()) Pluto=max(Pluto,*--counter.end());if(Pluto<Ans||Pluto==Ans&&i<pos) pos=i, Ans=Pluto; for(int j:F[i]) {int val=f[i]+g[j]+1;counter.insert(val);}}cout << pos << ' ' << Ans << '\n';return 0;
}
久久地望着孤月的人的悲哀beiai
本质不同的子序列的求法，设 \(f_i\) 表示考虑到 \(i\) 且强制 \(a_i\) 选的方案数，枚举不同的值 \(j\) 转移其最后一个位置的 \(f\)，放到这个题目里面就是 \(f_i=\sum_{j=1}^i f_{i-j}\)，发现好改成前缀和减少转移点数，\(s_i-s_{i-1}=s_{i-1}-s_{i-m-1}\) 也就是 \(s_i=2s_{i-1}-s_{i-m-1}\)。
想要来一点组合意义，就是可以 \(i\to i+1\) 乘上系数 \(2\)，或者可以 \(i\to i+(m+1)\) 乘上系数 \(-1\)，枚举多少次第二种走，可以得到 \(Ans=\sum_{i=0}^{\lfloor\frac{n}{m+1}\rfloor}(-1)^i2^{n-(m+1)i\binom{n-mi}{i}}\)，上标求和是调和级数，暴力求解即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=1000005, P=1e9+7;int n, q, m, f[N], tag[N], Ans;
int pw[N], mul[N], inv[N];inline int C(int n,int m) {if(m<0||n<m) return 0;return mul[n]*inv[m]%P*inv[n-m]%P;
}int solve(int m) {if(tag[m]) return f[m];tag[m]=1, Ans=0;up(i,0,n/(m+1)) {int val=pw[n-(m+1)*i]*C(n-m*i,i)%P;if(i&1) Ans=(Ans-val)%P; else Ans=(Ans+val)%P;}return f[m]=(Ans%P+P)%P;
}signed main() {freopen("beiai.in","r",stdin); freopen("beiai.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> q;pw[0]=mul[0]=inv[0]=inv[1]=1;up(i,1,n) pw[i]=pw[i-1]*2%P;up(i,1,n) mul[i]=mul[i-1]*i%P;up(i,2,n) inv[i]=inv[P%i]*(P-P/i)%P;up(i,2,n) inv[i]=inv[i-1]*inv[i]%P;while(q--) {cin >> m;cout << solve(m) << '\n';}return 0;
}