建设部监理师网站,论论坛坛网网站站建建设设,网络推广怎么收费,凡客模板wordpress比赛经历
有点忘了#xff0c;稍微写一些 本来早上有 n f l s nfls nfls 的#xff0c;但因为今天大联盟 T 1 T1 T1 是我们学校的题#xff0c;于是写大联盟 第一题因为下午要我们讲#xff0c;所以讨论了一下做法#xff0c;个人感觉第一步把 a b a aba aba 拆成 …比赛经历
有点忘了稍微写一些 本来早上有 n f l s nfls nfls 的但因为今天大联盟 T 1 T1 T1 是我们学校的题于是写大联盟 第一题因为下午要我们讲所以讨论了一下做法个人感觉第一步把 a b a aba aba 拆成 a b ab ab 和 a a a 两个不关联的部分很妙其他随便贪或者我比较蠢写了决策单调性优化 d p dp dp 大概过了 40 m i n 40min 40min T 2 T2 T2 是串串题看了一遍没什么思路于是跳 接下来就是恶心的部分了 我 C C C 题一眼想到一个 n m 2 nm^2 nm2 的 d p dp dp遂写发现过了样例考虑优化时一眼卷积于是便直接开始打 n t t ntt ntt打完之后发现坏了模数是 1 e 9 7 1e97 1e97改成 f f t fft fft 之后精度掉没了这时大概 2 h 2h 2h 其他人 T 3 T3 T3 也没思路分享了一下解法我觉得还是我的 n 3 n^3 n3 比较简单但始终优化不到 O ( n 2 ) O(n^2) O(n2)没办法拼了个 m 1145141919 m1145141919 m1145141919 的部分分上去 其实一开始我就大概知道 T 4 T4 T4 题意了因为有人开 T 4 T4 T4 把题意报出来了我感觉很不可做于是就没细想 预估分数 100 0 40 0 140 1000400140 1000400140 实际分数 100 0 25 0 125 1000250125 1000250125 T 3 T3 T3 特殊性质拼错了还是要二项式反演
反思
今天题感觉做着很难绷没有一道题我是有十足的把握能够在赛场上场切的感觉遗憾就是 T 3 T3 T3 没看到模数 1 e 9 7 1e97 1e97 然后浪费了 $4 0 m i n 0min 0min
题解
T1
把 a , b , a a,b,a a,b,a 拆成 a b ab ab 和 a a a然后直接贪即可 我是写的决策单调性优化 d p dp dp因为 a b ab ab 选的个数一定不降 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
#include bits/stdc.h
#define int long long
using namespace std;
const int N100100,M1000100;
int n,m,ans[M],a[N],b[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void solve(int l,int r,int ql,int qr){if(lr) return;int mid(lr)1;int posql;for(int iql;iqr;i){if(mid-2*i0) break;int valb[i]a[mid-2*i];if(valb[pos]a[mid-2*pos]) posi;}ans[mid]b[pos]a[mid-2*pos];solve(l,mid-1,ql,pos),solve(mid1,r,pos,qr);
}
signed main(){freopen(coin.in,r,stdin);freopen(coin.out,w,stdout);nread(),mread();for(int i1;in;i) a[i]read();for(int i1;in;i) b[i]read()a[i];sort(a1,an1,greaterint()),sort(b1,bn1,greaterint());for(int i1;in;i) a[i]a[i-1],b[i]b[i-1];solve(1,min(m,3*n),0,n);int ANS0;for(int i1;imin(m,3*n);i) ANS^ans[i];for(int i3*n1;im;i) ANS^ans[3*n];printf(%lld\n,ANS);return 0;
}
T2
感觉很有意思的一道题 首先一个结论是每个串的开头都是 T 0 T_0 T0 考虑贡献只有可能是在两串交接处和末串与 D D D 的交接处和 D D D 内部 我们记 m x s u f i mxsuf_i mxsufi 表示 T i T_i Ti 末尾与 S S S 的开头最多匹配的长度每次只要跳 b o r d e r border border 就可以找到所有合法串因为 T 0 T_0 T0 是已知的一串开头所以我们可以预处理出 t o t i tot_i toti 表示 m x s u f i mxsufi mxsufi 的匹配的个数 然后我们只要用类似 k m p kmp kmp 的方式暴力一个一个跳 D D D 即可 至于预处理我用的是字符串哈希进行匹配 细节有些多时间复杂度 O ( ∑ ∣ D ∣ ) O(\sum |D|) O(∑∣D∣)
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int N2000100;
typedef unsigned long long ull;
ull v[2][2],base[2]{1331,131},hS[2][N],hT[2][N],bs[2][N];
int n,mxsuf[N],tot[N];
ull ans[N];
int neS[N],fail[N][2];
int lens,lent0;
char t0[N],s[N],D[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
ull gethash(int l,int r,int t,ull *h){ return h[r]-h[l-1]*bs[t][r-l1];}
void init(){lensstrlen(s1);for(int i2,j0;ilens;i){while(js[j1]!s[i]) jneS[j];if(s[j1]s[i]) j;neS[i]j;}for(int i1;ilens;i){int cs[neS[i]1]-48;fail[i][c]neS[i],fail[i][c^1]fail[neS[i]][c^1];}v[0][0]mrand(),v[0][1]mrand(),v[1][0]mrand(),v[1][1]mrand();lent0strlen(t01);for(int i1;ilent0;i) for(int t:{0,1}) hT[t][i]hT[t][i-1]*base[t]v[t][t0[i]-48];for(int i1;ilens;i) for(int t:{0,1}) hS[t][i]hS[t][i-1]*base[t]v[t][s[i]-48];bs[0][0]bs[1][0]1;for(int i1;ilens;i) for(int t:{0,1}) bs[t][i]bs[t][i-1]*base[t];for(int i1;ilens;i){if(hT[0][lens-i]gethash(i1,lens,0,hS[0])hT[1][lens-i]gethash(i1,lens,1,hS[1])) tot[i]1;tot[i]tot[neS[i]];}for(int ilens-1;i;i--) if(hS[0][i]gethash(lent0-i1,lent0,0,hT[0])hS[1][i]gethash(lent0-i1,lent0,1,hT[1])){ mxsuf[0]i;break;}for(int i1;ilent0-lens1;i) if(gethash(i,ilens-1,0,hT[0])hS[0][lens]gethash(i,ilens-1,1,hT[1])hS[1][lens]) ans[0];
}
int main(){freopen(string.in,r,stdin);freopen(string.out,w,stdout);nread();scanf(%s,s1),scanf(%s,t01);init();for(int i1;in;i){int kread(),pre-1;while(k--){int idread();ans[i]ans[id];if(pre!-1) ans[i]tot[mxsuf[pre]];preid;}scanf(%s,D1);int lenDstrlen(D1);mxsuf[i]mxsuf[pre];for(int j1;jlenD;j){if(D[j]s[mxsuf[i]1]) mxsuf[i];else{mxsuf[i]fail[mxsuf[i]][D[j]-48];if(D[j]s[mxsuf[i]1]) mxsuf[i];}if(mxsuf[i]lens) ans[i],mxsuf[i]neS[mxsuf[i]];}}for(int i1;in;i) printf(%llu\n,ans[i]);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
C w x q n b ! ! ! wxq\;nb!!! wxqnb!!! 我也不知道 w x q wxq wxq 怎么想到的用 E G F EGF EGF 求解 我忘了式子怎么推的了。。。 反正最后的式子是 ∑ S 0 2 n − 1 ( − 1 ) p o p c n t ( S ) S . . . \sum\limits_{S0}^{2^n-1}(-1)^{popcnt(S)}S... S0∑2n−1(−1)popcnt(S)S... 然后好像是二项式定理展开再分治 d p dp dp 解决 我不记得了改天再问一下他怎么做 时间复杂度 O ( n 2 l o g n ) O(n^2logn) O(n2logn)
#include bits/stdc.h
using namespace std;
const int N2100,P1e97;
int n,m,f[N][N],g[N],h[(120)5];
int pw2[N*N],C[N][N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void solve(int n){if(!n||n1) return;solve(n/2);for(int i0;im;i)for(int j0;ji;j) f[n][i](f[n][i]1ll*f[n/2][j]*f[n/2][i-j]%P*C[i][j]%P*pw2[j*(n/2)])%P;if(n1){for(int i0;im;i){g[i]0;for(int j0;ji;j) g[i](g[i]1ll*f[n][j]*f[1][i-j]%P*C[i][j]%P*pw2[j])%P;}for(int i0;im;i) f[n][i]g[i];}
}
int qmi(int a,int b){int res1;for(;b;b1){if(b1) res1ll*res*a%P;a1ll*a*a%P;}return res;
}
void fwt(){for(int mid1;mid1n;mid1)for(int i0;i1n;imid1) for(int j0;jmid;j) h[ijmid](h[ijmid]h[ij])%P;
}
void work_sb(){pw2[0]1;for(int i1;in;i) pw2[i]pw2[i-1]*2%P;for(int S0;S1n;S){int res0;for(int i0;in;i) if(Si1) respw2[i];h[S]qmi(res,m);}for(int S0;S1n;S) if(__builtin_popcount(S)1) h[S](P-h[S])%P;fwt();if(n1) printf(%d\n,(P-h[(1n)-1])%P);else printf(%d\n,h[(1n)-1]);
}
int main(){freopen(glass.in,r,stdin);freopen(glass.out,w,stdout);nread(),mread();if(m1145141919){ work_sb();exit(0);}C[0][0]1;for(int i1;im;i) for(int j0;ji;j) C[i][j](!j||ij)?1:(C[i-1][j-1]C[i-1][j])%P;pw2[0]1;for(int i1;im*n;i) pw2[i]pw2[i-1]*2%P;f[0][0]1;for(int i1;im;i) f[1][i]P-1;solve(n);if(n1) printf(%d\n,(P-f[n][m])%P);else printf(%d\n,f[n][m]);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
D
大分块题狗都不补
