东莞市网站建设系统企业,自动生成网站,易联网站制作,众筹网站搭建博弈(game)
观察到博弈过程中胜负态不会发生改变#xff0c;那么求出从每个棋子出发能走的最长链#xff0c;然后背包即可。
复杂度O(nm)O(nm)O(nm)。
#includebits/stdc.h
#define ll long long
#define pb push_back
using namespace std;
const int mod9982443…博弈(game)
观察到博弈过程中胜负态不会发生改变那么求出从每个棋子出发能走的最长链然后背包即可。
复杂度O(nm)O(nm)O(nm)。
#includebits/stdc.h
#define ll long long
#define pb push_back
using namespace std;
const int mod998244353;
const int N305;
int n,m,dp[N],in[N],g[N*N],g2[N*N],vis[N];
ll res;
string s;
queueintQ;
vectorintve[N];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnms;for(int i1;im;i){int u,v;cinuv,u--,v--;if(uv)swap(u,v);ve[v].pb(u),in[u];}for(int i0;in;i)if(!in[i])Q.push(i);while(Q.size()){int uQ.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 i0;in;i){if(s[i]W){for(int jn*n;jdp[i];j--){g[j](g[j]g[j-dp[i]])%mod;}}else{for(int jn*n;jdp[i];j--){g2[j](g2[j]g2[j-dp[i]])%mod;}}}for(int i1;in*n;i){g2[i](g2[i-1]g2[i])%mod;}for(int i1;in*n;i){res(res(ll)g[i]*g2[i-1])%mod;}coutres;
} 排列 (perm)
神仙题。
考虑怎么转化这个性质。等价于不能存在一个区间里面同时存在(a,b),(b,c)(a,b),(b,c)(a,b),(b,c)而不存在(a,c)(a,c)(a,c)。
由此可以想到传递闭包每个区间如果建一个图就都必须具有传递性。
然后我们发现只需要每个前缀都有传递性每个后缀都有传递性就好了。
不要问我怎么想到的以及证明国内谜语人太多了可以去骂写题解的人
也就是说任取一个iii设GiG_iGi为考虑前iii条边组成的图那么GiG_iGi和GiG_iGi的补图都有传递性。
有一个很神奇的结论满足这样条件的GGG恰好有n!n!n!个这是因为任取一个排列ppp如果ababab并且aaa在ppp中的位置在bbb的后面那么连边(a,b)(a,b)(a,b)这样构造出来的图一定是满足传递性的并且这是一个双射。
可能打表反而更实际一些
然后最无脑的想法是因为合法的前缀只有n!n!n!个所以状态数只有O(n!)O(n!)O(n!)也就是说可以直接把整张图的每条边存起来然后暴力转移。不过既然我们都知道这样的GGG和一个排列ppp构成双射了那么在ppp中转移则显得合情合理一个合法的GGG加入一条边(a,b)(a,b)(a,b)后仍然合法当且仅当GGG对应的排列ppp中aaa恰好在bbb前面的位置加入边(a,b)(a,b)(a,b)相当于是交换(a,b)(a,b)(a,b)的位置。
复杂度O(n!×n)O(n!\times n)O(n!×n)。
对不起代码咕掉了因为感受到了出题人的恶意
另外这题的想法也太聪明了吧。。。
考场上只写了20pts20pts20pts的暴搜大概是因为被搞心态了所以没想到40pts40pts40pts的无脑状压dpdpdp不过这种失分还是挺无语的
出题人你还是要有同理心啊
子段和 (seg)
放在t3t3t3其实还是比较水的。
直接用数据结构暴力维护就能做到O(n2logw)O(n^2\log w)O(n2logw)可以得到70pts70pts70pts。
然而没写对拍结果写炸了警钟长鸣
接下来一步应该容易想到对于max\maxmax相同的区间我们每次要取出min\minmin最小的那一个对于这个过程我们可以用一个set\text{set}set来维护。考虑堆套set\text{set}set堆里面每个元素维护区间max\maxmax相同的区间的集合用set\text{set}set维护这些区间的最小值的位置。这里有一个比较巧妙的想法就是把堆中的元素存在一个数组里这样每次从堆中取元素时就不用把它复制一遍了。
复杂度O(nlogn)O(n\log n)O(nlogn)。
后来发现题解的思路确实更加聪明。
考虑给定kkk怎么求g(k)g(k)g(k)呢二分答案www令aaa为给出序列的前缀和a00a_00a00每次操作就是对一段后缀−1-1−1最后要使得∀ij,aj−ai≤w\forall ij,a_j-a_i\le w∀ij,aj−ai≤w。
直接从前往后贪心维护一个lim\text{lim}lim表示后面的aaa经过操作后都不能超过lim\text{lim}lim。如果ailima_i\text{lim}ailim那么就在这里执行ai−lima_i-\text{lim}ai−lim次操作得到新的aaa。然后令lim:min(lim,aiw)\text{lim}:\min(\text{lim},a_iw)lim:min(lim,aiw)。
正解非常脑洞。考虑直接把所有www的lim\text{lim}lim一起维护设这个函数为L(w)L(w)L(w)另外维护A(w)A(w)A(w)表示目前的代价。剩下的就是用数据结构大力乱搞。
先贴一个70pts70pts70pts的代码吧。原谅我没有能力刚正解。
毕竟quack也说了这题到这里就差不多了。。。
#includebits/stdc.h
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod998244353;
int n,p[200005][20],p2[200005][20],Log[200005];
ll a[200005],s[200005],Min[200005][20],Max[200005][20],K,res,inv2(mod1)/2;
vectorpairll,llv;
int qmin(int l,int r){int kLog[r-l1];return (Min[l][k]Min[r-(1k)1][k])?p[l][k]:p[r-(1k)1][k];
}
int qmax(int l,int r){int kLog[r-l1];return (Max[l][k]Max[r-(1k)1][k])?p2[l][k]:p2[r-(1k)1][k];
}
struct node{int l,r;ll S;bool operator (const node a)const{return s[qmax(l,r)]-Ss[qmax(a.l,a.r)]-a.S;}
};
priority_queuenodeq;
vectornodevec;
ll Sum(ll l,ll r){l%mod,r%mod;return (r-l1)*(lr)%mod*inv2%mod;
}
void calc(ll K,ll Max,ll x,ll y){if(K/xy){resSum(Max-y1,Max)*(x%mod)-y;res%mod,K-x*y;}else{resSum(Max-K/x1,Max)*(x%mod)-(K/x),res%mod;Max-K/x,K%x,res(K%mod)*(Max%mod),res%mod,K0;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinn;for(int i2;in;i)Log[i]Log[i/2]1;for(int i1;in;i){cina[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 j1;j20;j){for(int i1;in-(1j)1;i){Min[i][j]min(Min[i][j-1],Min[i(1j-1)][j-1]),Max[i][j]max(Max[i][j-1],Max[i(1j-1)][j-1]);p[i][j](Min[i][j]Min[i][j-1])?p[i][j-1]:p[i(1j-1)][j-1],p2[i][j](Max[i][j]Max[i][j-1])?p2[i][j-1]:p2[i(1j-1)][j-1]; }}q.push({1,n,0});cinK;while(q.size()){ll MAXs[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().SMAX){int lq.top().l,rq.top().r;ll Sq.top().S;q.pop();S2min(S2,s[qmin(l,r)]-S),vec.pb({l,r,S});}if(q.size())S2min(S2,MAX-(s[qmax(q.top().l,q.top().r)]-q.top().S));for(int i0;ivec.size();i){int lvec[i].l,rvec[i].r,pqmin(l,r);ll Svec[i].S;if(s[p]-S-S20){if(pl)q.push({l,p-1,SS2});if(pr)q.push({p1,r,SS2});}else q.push({l,r,SS2});}calc(K,MAX,vec.size(),S2);if(!K)break;}if(K){for(int i1;in;i)a[i]min(a[i],0ll);sort(a1,a1n),reverse(a1,a1n);for(int i2;in;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(resmod)%mod;
}
