【学习笔记】NOIP暴零赛3

博弈(game)

观察到博弈过程中胜负态不会发生改变，那么求出从每个棋子出发能走的最长链，然后背包即可。

复杂度$O(nm)$。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int mod=998244353;
const int N=305;
int n,m,dp[N],in[N],g[N*N],g2[N*N],vis[N];
ll res;
string s;
queue<int>Q; 
vector<int>ve[N];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>s;for(int i=1;i<=m;i++){int u,v;cin>>u>>v,u--,v--;if(u>v)swap(u,v);ve[v].pb(u),in[u]++;}for(int i=0;i<n;i++)if(!in[i])Q.push(i);while(Q.size()){int u=Q.front();Q.pop();for(auto v:ve[u]){if(--in[v]==0)Q.push(v);if(s[u]==s[v])dp[v]=max(dp[v],dp[u]+1),vis[v]=1;else if(s[u]!=s[v]&&!vis[u]&&!dp[u])dp[v]=max(dp[v],1);}}g[0]=g2[0]=1;for(int i=0;i<n;i++){if(s[i]=='W'){for(int j=n*n;j>=dp[i];j--){g[j]=(g[j]+g[j-dp[i]])%mod;}}else{for(int j=n*n;j>=dp[i];j--){g2[j]=(g2[j]+g2[j-dp[i]])%mod;}}}for(int i=1;i<=n*n;i++){g2[i]=(g2[i-1]+g2[i])%mod;}for(int i=1;i<=n*n;i++){res=(res+(ll)g[i]*g2[i-1])%mod;}cout<<res;
} 

排列 (perm)

神仙题。

考虑怎么转化这个性质。等价于，不能存在一个区间，里面同时存在$(a,b),(b,c)$而不存在$(a,c)$。

由此可以想到传递闭包：每个区间，如果建一个图，就都必须具有传递性。

然后我们发现，只需要每个前缀都有传递性，每个后缀都有传递性就好了。

不要问我怎么想到的，以及证明，国内谜语人太多了，可以去骂写题解的人

也就是说，任取一个$i$，设$G_i$为考虑前$i$条边组成的图，那么$G_i$和$G_i$的补图都有传递性。

有一个很神奇的结论：满足这样条件的$G$恰好有$n!$个，这是因为，任取一个排列$p$，如果$a<b$并且$a$在$p$中的位置在$b$的后面，那么连边$(a,b)$，这样构造出来的图一定是满足传递性的，并且这是一个双射。

可能打表反而更实际一些

然后，最无脑的想法是，因为合法的前缀只有$n!$个，所以状态数只有$O(n!)$，也就是说可以直接把整张图的每条边存起来，然后暴力转移。不过既然我们都知道这样的$G$和一个排列$p$构成双射了，那么在$p$中转移则显得合情合理，一个合法的$G$加入一条边$(a,b)$后仍然合法，当且仅当$G$对应的排列$p$中$a$恰好在$b$前面的位置，加入边$(a,b)$相当于是交换$(a,b)$的位置。

复杂度$O(n!\times n)$。

对不起代码咕掉了，因为感受到了出题人的恶意

另外，这题的想法也太聪明了吧。。。

考场上只写了$20pts$的暴搜，大概是因为被搞心态了所以没想到$40pts$的无脑状压$dp$，不过这种失分还是挺无语的

出题人你还是要有同理心啊

子段和 (seg)

放在$t3$其实还是比较水的。

直接用数据结构暴力维护就能做到$O(n^2\log w)$，可以得到$70pts$。

然而没写对拍结果写炸了，警钟长鸣

接下来一步应该容易想到：对于$\max$相同的区间，我们每次要取出$\min$最小的那一个，对于这个过程，我们可以用一个$\text{set}$来维护。考虑堆套$\text{set}$，堆里面每个元素维护区间$\max$相同的区间的集合，用$\text{set}$维护这些区间的最小值的位置。这里有一个比较巧妙的想法，就是把堆中的元素存在一个数组里，这样每次从堆中取元素时就不用把它复制一遍了。

复杂度$O(n\log n)$。

后来发现题解的思路确实更加聪明。

考虑给定$k$，怎么求$g(k)$呢，二分答案$w$，令$a$为给出序列的前缀和，$a_0=0$，每次操作就是对一段后缀$-1$，最后要使得$\forall i<j,a_j-a_i\le w$。

直接从前往后贪心，维护一个$\text{lim}$表示后面的$a$经过操作后都不能超过$\text{lim}$。如果$a_i>\text{lim}$那么就在这里执行$a_i-\text{lim}$次操作，得到新的$a$。然后令$\text{lim}:=\min (\text{lim},a_i+w)$。

正解非常脑洞。考虑直接把所有$w$的$\text{lim}$一起维护，设这个函数为$L(w)$，另外维护$A(w)$表示目前的代价。剩下的就是用数据结构大力乱搞。

先贴一个$70pts$的代码吧。原谅我没有能力刚正解。

毕竟quack也说了这题到这里就差不多了。。。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=998244353;
int n,p[200005][20],p2[200005][20],Log[200005];
ll a[200005],s[200005],Min[200005][20],Max[200005][20],K,res,inv2=(mod+1)/2;
vector<pair<ll,ll>>v;
int qmin(int l,int r){int k=Log[r-l+1];return (Min[l][k]<Min[r-(1<<k)+1][k])?p[l][k]:p[r-(1<<k)+1][k];
}
int qmax(int l,int r){int k=Log[r-l+1];return (Max[l][k]>Max[r-(1<<k)+1][k])?p2[l][k]:p2[r-(1<<k)+1][k];
}
struct node{int l,r;ll S;bool operator <(const node &a)const{return s[qmax(l,r)]-S<s[qmax(a.l,a.r)]-a.S;} 
};
priority_queue<node>q;
vector<node>vec;
ll Sum(ll l,ll r){l%=mod,r%=mod;return (r-l+1)*(l+r)%mod*inv2%mod;
}
void calc(ll &K,ll Max,ll x,ll y){if(K/x>=y){res+=Sum(Max-y+1,Max)*(x%mod)-y;res%=mod,K-=x*y;}else{res+=Sum(Max-K/x+1,Max)*(x%mod)-(K/x),res%=mod;Max-=K/x,K%=x,res+=(K%mod)*(Max%mod),res%=mod,K=0;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=2;i<=n;i++)Log[i]=Log[i/2]+1;for(int i=1;i<=n;i++){cin>>a[i],s[i]=max(s[i-1]+a[i],0ll),Min[i][0]=Max[i][0]=s[i],p[i][0]=p2[i][0]=i;}for(int j=1;j<20;j++){for(int i=1;i<=n-(1<<j)+1;i++){Min[i][j]=min(Min[i][j-1],Min[i+(1<<j-1)][j-1]),Max[i][j]=max(Max[i][j-1],Max[i+(1<<j-1)][j-1]);p[i][j]=(Min[i][j]==Min[i][j-1])?p[i][j-1]:p[i+(1<<j-1)][j-1],p2[i][j]=(Max[i][j]==Max[i][j-1])?p2[i][j-1]:p2[i+(1<<j-1)][j-1]; }}q.push({1,n,0});cin>>K;while(q.size()){ll MAX=s[qmax(q.top().l,q.top().r)]-q.top().S,S2(inf);vec.clear();if(!MAX)break;while(q.size()&&s[qmax(q.top().l,q.top().r)]-q.top().S==MAX){int l=q.top().l,r=q.top().r;ll S=q.top().S;q.pop();S2=min(S2,s[qmin(l,r)]-S),vec.pb({l,r,S});}if(q.size())S2=min(S2,MAX-(s[qmax(q.top().l,q.top().r)]-q.top().S));for(int i=0;i<vec.size();i++){int l=vec[i].l,r=vec[i].r,p=qmin(l,r);ll S=vec[i].S;if(s[p]-S-S2==0){if(p>l)q.push({l,p-1,S+S2});if(p<r)q.push({p+1,r,S+S2});}else q.push({l,r,S+S2});}calc(K,MAX,vec.size(),S2);if(!K)break;}if(K){for(int i=1;i<=n;i++)a[i]=min(a[i],0ll);sort(a+1,a+1+n),reverse(a+1,a+1+n);for(int i=2;i<=n;i++){calc(K,a[i-1],i-1,a[i-1]-a[i]);if(!K)break;}if(K){calc(K,a[n],n,inf);}}cout<<(res+mod)%mod;
}