做网站别人点击能得钱吗,百度爱采购推广怎么入驻,网站设计用什么做,如何开发高端客户文章目录前言题目解析随机减法#xff08;calculate#xff09;大图书馆#xff08;bibliotheca#xff09;子串选取 #xff08;substr#xff09;代码T1T2T3总结前言
200pts 4010060 rnk3 拿到牌勒嘿嘿嘿#xff08;脑补流口水黄豆#xff09;
T3两个log想在ybt的机…
文章目录前言题目解析随机减法calculate大图书馆bibliotheca子串选取 substr代码T1T2T3总结前言
200pts 4010060 rnk3 拿到牌勒嘿嘿嘿脑补流口水黄豆
T3两个log想在ybt的机子上过5e5确实是奢望了。 把串反过来改一改dp定义看出题解的那个性质就可以拿掉那个log有些可惜。 但毕竟没有挂分还是不错的v
题目解析
随机减法calculate
乍一看这个题就感觉在 OI-wiki 上见过。 但是就记得在OIwiki上有了属于那个章节怎么做统统不记得… 于是就只配打暴力了… 其实也看出了卷积但那个东西需要再变成封闭形式化一下必然还是脱离不了 O(k)O(k)O(k) 的复杂度。 而且看到 1e971e971e97 这种模数本能的觉得不是多项式… 而且为啥我的dp转移和题解又不一样难看的很难化了…
题目的贡献其实也就是 ∏ai\prod a_i∏ai 的变化量。 即 ∏ai−∏ai′\prod a_i-\prod a_i∏ai−∏ai′ 前面已知考虑如何算后面的贡献。
设每个数的删除次数为 d1...nd_{1...n}d1...n则有 ans∑∑dikk!∏(ai−di)∏di!ans\sum_{\sum d_ik}\frac{k!\prod(a_i-d_i)}{\prod d_i!}ans∑dik∑∏di!k!∏(ai−di) k!∑∑dik∏(ai−di)∏di!k!\sum_{\sum d_ik}\frac{\prod(a_i-d_i)}{\prod d_i!}k!∑dik∑∏di!∏(ai−di) 设后面这个东西的生成函数为 GGG那么它其实就是 nnn 个形如 Fp∑i0∞(ap−i)xii!F_p\sum_{i0}^{\infty}\dfrac{(a_p-i)x^i}{i!}Fp∑i0∞i!(ap−i)xi 的EGF卷起来。 然后把这个 FFF 化一下 Fp∑i0∞(ap−i)xii!F_p\sum_{i0}^{\infty}\dfrac{(a_p-i)x^i}{i!}Fpi0∑∞i!(ap−i)xi ap⋅∑i0∞xii!−∑i1∞xi(i−1)!a_p\cdot\sum_{i0}^{\infty}\dfrac{x^i}{i!}-\sum_{i1}^{\infty}\dfrac{x^i}{(i-1)!}ap⋅i0∑∞i!xi−i1∑∞(i−1)!xi ap⋅∑i0∞xii!−∑i0∞xi1i!a_p\cdot\sum_{i0}^{\infty}\dfrac{x^i}{i!}-\sum_{i0}^{\infty}\dfrac{x^{i1}}{i!}ap⋅i0∑∞i!xi−i0∑∞i!xi1 (ap−x)⋅∑i0∞xii!(a_p-x)\cdot\sum_{i0}^{\infty}\dfrac{x^i}{i!}(ap−x)⋅i0∑∞i!xi (ap−x)⋅ex(a_p-x)\cdot e^x(ap−x)⋅ex 那么就有 G∏p1nFpG\prod_{p1}^nF_pGp1∏nFp G∏p1n((ap−x)ex)G\prod_{p1}^n((a_p-x)e^x)Gp1∏n((ap−x)ex) G(∏p1n(ap−x))enxG(\prod_{p1}^n(a_p-x))e^{nx}G(p1∏n(ap−x))enx 前面的 ∏p1n(ap−x)\prod_{p1}^n(a_p-x)∏p1n(ap−x) 可以暴力背包求解设得到的函数为 fff 那么就有 G(∑i0∞fixi)×(∑i0∞(nx)ii!)G(\sum_{i0}^{\infty}f_ix^i)\times (\sum_{i0}^{\infty}\frac{(nx)^i}{i!})G(i0∑∞fixi)×(i0∑∞i!(nx)i) 那么最终得到的期望就是 GGG 的第 kkk 项乘上 k!k!k! 再除以 nkn^knk即 E∑i0fi⋅ki‾niE\sum_{i0}\frac{f_i\cdot k^{\underline i}}{n^i}Ei0∑nifi⋅ki 答案就是 ∏ai−E\prod a_i-E∏ai−E 总复杂度 O(n2)O(n^2)O(n2)。
大图书馆bibliotheca
被A穿了的一道题… 15提交14AC一个96就离谱… 说实话我感觉这道题没有那么简单啊… 网络流显而易见建图方法五花八门。 我的做法是转化为k重线段覆盖集问题然后直接做。 题解的做法把“不买书” 转化为一次买书和一次“卖书”然后回溯连边也是挺不错的。
子串选取 substr
挺可惜的一道题差一点点。 感觉很经典的一道字符串题。 似乎必然是要SAM的所以直接往那边想了。 然后又无脑的上了线段树合并 endpos 集合的套路。 然后找找性质二分搞吧搞吧就两个log了。 但是5e5两只log是过不去的…
先把串反过来设计 dpidp_idpi 表示以 iii 结尾的最大答案。 然后就有一个非常优秀的性质fi≤fi−11f_i\le f_{i-1}1fi≤fi−11。 较为显然把 fif_ifi 的一种方案每个串删去结尾就能得到答案为 fi−1f_{i}-1fi−1 且以 i−1i-1i−1 结尾的方案。 有了这个之后每次就不用二分 dp 值了直接从上一个继承来然后不断暴力check不合法就减减即可有点类似于后缀数组求 heightheightheight。 这样就把第二只 log 拿掉了复杂度变为单 log可以通过。
代码
T1
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N5e3100;
const int B150;
const int inf2e9;
const int mod1e97;int n,m;int a[N];
ll f[2][N],c[5];
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}signed main(){freopen(calculate.in,r,stdin);freopen(calculate.out,w,stdout);//printf(%d\n,sizeof(t)/1024/1024);nread();mread();ll ans1;for(int i1;in;i) a[i]read(),ansans*a[i]%mod;int now1,pre0;f[now][0]1;for(int k1;kn;k){c[0]a[k];c[1]mod-1;swap(pre,now);memset(f[now],0,sizeof(f[now]));for(int i0;i(k-1);i){for(int j0;j1;j){f[now][ij](f[now][ij]f[pre][i]*c[j])%mod;}}}ll E(0),bas1,mi1,niksm(n,mod-2);for(int i0;in;i){if(i) basbas*(m-i1)%mod,mimi*ni%mod;E(Ef[now][i]*bas%mod*mi)%mod;}printf(%lld\n,(ansmod-E)%mod);return 0;
}
/*
12
abcdbabcabba
*/
T2
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N4e3100;
const int B150;
const int inf2e9;
const int mod998244353;int n,m;
int ww1e61;int s,t,tot;
struct node{int to,nxt,cap,w;
}p[N*N];
int fi[N],cur[N],cnt;
inline void addline(int x,int y,int c,int w){p[cnt](node){y,fi[x],c,w};fi[x]cnt;return;
}
inline void add(int x,int y,int c,int w){addline(x,y,c,w);addline(y,x,0,-w);//printf( %d-%d cap%d w%d\n,x,y,c,w);return;
}
int dis[N];
bool vis[N];
queueintq;
bool spfa(){fill(dis,dis1tot,inf);dis[s]0;q.push(s);vis[s]1;while(!q.empty()){int nowq.front();q.pop();vis[now]0;for(int icur[now]fi[now];~i;ip[i].nxt){int top[i].to;if(!p[i].cap||dis[to]dis[now]p[i].w) continue;dis[to]dis[now]p[i].w;if(!vis[to]){vis[to]1;q.push(to);}}}return dis[t]inf;
}
int flow,cost;
int dfs(int x,int lim){if(!lim||xt){costlim*dis[t];return lim;}if(vis[x]) return 0;vis[x]1;int res(0);for(int icur[x];~i;ip[i].nxt){int top[i].to;if(dis[to]!dis[x]p[i].w) continue;int adddfs(to,min(lim,p[i].cap));resadd;lim-add;p[i].cap-add;p[i^1].capadd;if(!lim) break;}if(!res) dis[x]-1;vis[x]0;return res;
}
void dinic(){flowcost0;int tmp(0);while(spfa()){while((tmpdfs(s,inf))) flowtmp;}return;
}struct line{int l,r,val;
}l[N];
int pre[N],lst[N];
int a[N],c[N],ans;signed main(){freopen(bibliotheca.in,r,stdin);freopen(bibliotheca.out,w,stdout);//printf(%d\n,sizeof(p)/1024/1024);memset(fi,-1,sizeof(fi));cnt-1;nread();mread();for(int i1;in;i) a[i]read();for(int i1;in;i) c[i]read();for(int i1;in;i){pre[i]lst[a[i]];ansc[a[i]];lst[a[i]]i;}for(int i1;in;i){int xlst[i];while(pre[x]){l[tot](line){pre[x],x,c[i]};xpre[x];}}for(int i1;in;i) l[tot](line){i,i,ww};ansn*ww;int numtot;tot1;stot;ttot;int otot;add(s,o,m,0);for(int i1;inum;i){//printf(i%d (%d %d)\n,i,l[i].l,l[i].r);add(o,i,1,0);add(i,inum,1,-l[i].val);add(inum,t,1,0);for(int j1;jnum;j){if(ij) continue;if(l[j].ll[i].r) add(inum,j,1,0);}}dinic();printf(%d\n,anscost);return 0;
}
/*
9 2
2 1 2 1 2 3 1 2 3
1 2 3 0 0 0 0 0 0
*/
T3
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N1e6100;
const int B150;
const int inf2e9;
const int mod998244353;int n,m;struct tree{int ls,rs,sum,suf;
};
struct Segment_Tree{#define mid ((lr)1)tree tr[N*30];int tot;inline int copy(int x){tr[tot]tr[x];return tot;}inline void pushup(int k){tr[k].sumtr[tr[k].ls].sumtr[tr[k].rs].sum;tr[k].sufmax(tr[tr[k].ls].suf,tr[tr[k].rs].suf);return;}void upd(int k,int l,int r,int p,int w){if(!k) kcopy(0);if(lr){tr[k].sumw;tr[k].sufl;return;}if(pmid) upd(tr[k].ls,l,mid,p,w);else upd(tr[k].rs,mid1,r,p,w);pushup(k);}int merge(int x,int y,int l,int r){if(!x||!y) return x|y;int nowcopy(x);tr[now].lsmerge(tr[now].ls,tr[y].ls,l,mid);tr[now].rsmerge(tr[now].rs,tr[y].rs,mid1,r);pushup(now);return now;}int findsuf(int k,int l,int r,int x,int y){if(xy) return 0;if(!k) return 0;if(xlry) return tr[k].suf;int res0;if(ymid) resmax(res,findsuf(tr[k].rs,mid1,r,x,y));if(res) return res;if(xmid) resmax(res,findsuf(tr[k].ls,l,mid,x,y));return res;}#undef mid
}t;
int rt[N];int fa[N],len[N],tr[N][26],tot1,lst1,state[N];
inline void ins(int c,int pos){c-a;int curtot,plst;lsttot;state[pos]cur;t.upd(rt[cur],1,n,pos,1);len[cur]len[p]1;for(;p!tr[p][c];pfa[p]) tr[p][c]cur;if(!tr[p][c]) fa[cur]1;else{int qtr[p][c];if(len[q]len[p]1) fa[cur]q;else{int nqtot;len[nq]len[p]1;fa[nq]fa[q];for(int i0;i26;i) tr[nq][i]tr[q][i];fa[cur]fa[q]nq;for(;ptr[p][c]q;pfa[p]) tr[p][c]nq;}}return;
}
vectorintv[N];
int pl[N][20];
void dfs(int x){pl[x][0]fa[x];//printf(i%d k0 pl%d\n,i,pl[i][0]);for(int k1;pl[x][k-1];k){pl[x][k]pl[pl[x][k-1]][k-1];//printf(i%d k%d mid%d pl%d\n,i,k,pl[i][k-1],pl[i][k]);}for(int to:v[x]){dfs(to);rt[x]t.merge(rt[x],rt[to],1,n);}return;
}
void build(){for(int i2;itot;i) v[fa[i]].push_back(i);dfs(1);return;
}
inline int jump(int x,int l){//printf( jump: x%d L%d\n,x,l);for(int k19;k0;k--){//if(pl[x][k]) printf( k%d pl%d len%d\n,k,pl[x][k],len[pl[x][k]]);if(len[pl[x][k]]l) xpl[x][k];}return x;
}char s[N],ss[N];
int dp[N],mx,ans;
bool check(int x,int L){//printf(check: x%d L%d\n,x,L);int sjump(state[x],L-1);int plt.findsuf(rt[s],1,n,1,x-L);//printf( cutpre: s%d (%d %d) pl%d state%d\n,s,1,x-L,pl,state[x]);if(dp[pl]L-1) return true; if(x1){sjump(state[x-1],L-1);plt.findsuf(rt[s],1,n,1,x-L);//printf( cutsuf: s%d (%d %d) pl%d state%d\n,s,1,x-L,pl,state[x-1]);if(dp[pl]L-1) return true; }return false;
}
void DP(){for(int i1;in;i){dp[i]dp[i-1]1;while(dp[i]1!check(i,dp[i])) --dp[i];ansmax(ans,dp[i]);//printf(i%d dp%d\n\n,i,dp[i]);}return;
}
signed main(){freopen(substr.in,r,stdin);freopen(substr.out,w,stdout);//printf(%d\n,sizeof(t)/1024/1024);nread();scanf( %s,ss1);for(int i1;in;i) s[i]ss[n-i1];//printf(%s\n,s1);for(int i1;in;i) ins(s[i],i);//for(int i1;itot;i) printf(i%d fa%d len%d\n,i,fa[i],len[i]);build();DP();printf(%d\n,ans);return 0;
}
/*
12
abcdbabcabba
*/
总结
感觉最近不再像一开始那样疯狂挂分了。 明天就要上学校了加油awa
