A 怪盗-1412
problem
用个,个,个进行排列,求最多有多少个子序列。
solution
显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份,分别放在4两边。如果前面的有个,那么答案就是,这是一个二次函数,当时取得最大值。
code
/* * @Author: wxyww * @Date: 2020-05-22 18:59:57 * @Last Modified time: 2020-05-22 19:03:29 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int main() { int T = read(); while(T--) { ll n = read(),m = read(),K = read(); ll t = n / 2; cout<<t * (n - t) * m * K<<endl; } return 0; }
B Dis2
problem
给出一个个点树,对于每个点求与它距离为2的点的数目。
solution
对于第i个点统计出他的度数,当我们要求这个点的答案时,就枚举一个与有连边的将答案加上。减一是因为要减去u这个点。
code
/* * @Author: wxyww * @Date: 2020-05-22 19:04:43 * @Last Modified time: 2020-05-22 19:06:04 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N =200010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } vector<int>e[N]; int du[N]; int main() { int n = read(); for(int i = 1;i < n;++i) { int u = read(),v = read(); du[u]++;du[v]++; e[u].push_back(v);e[v].push_back(u); } for(int i = 1;i <= n;++i) { ll ans = 0; for(vector<int>::iterator it = e[i].begin();it != e[i].end();++it) { ans += du[*it] - 1; } printf("%lld\n",ans); } return 0; }
C 序列卷积之和
problem
给出一个长度为n的序列,求的值。
solution
将和的枚举提到前面来,
这就非常了,统计一个的前缀和,然后枚举,答案就是
code
/* * @Author: wxyww * @Date: 2020-05-22 19:09:59 * @Last Modified time: 2020-05-22 19:21:52 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 200010,mod = 1e9+7; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } ll a[N]; int main() { int n = read(); ll sum = 0,ans = 0; ll inv = (mod + 1) / 2; for(int i = 1;i <= n;++i) { a[i] = read(); ll t1 = 1ll * i * a[i] % mod; ll t2 = 1ll * (n - i + 1) * a[i] % mod; sum += t1; sum %= mod; ans += sum * t2 % mod; ans %= mod; } cout<<(ans + mod) % mod; return 0; }
D 宝石装箱
problem
将颗宝石装入个箱子中,每个箱子中都必须有宝石,第个宝石不能装入第个箱子中,问有多少种方案。
solution
长得类似于错排问题。所以我们可以先在外面套一个容斥。设表示至少有个箱子不合法其他的箱子先不放的方案数。
那么答案就是。乘是因为剩下的个箱子可以随便排列。
然后我们只要求出来就行了。
发现数据范围允许我们的求。考虑。先预处理出一个表示有个宝石不能放到第个箱子中。用表示前个箱子有j个不合法,其他的先不放的方案数。转移就是
code
/* * @Author: wxyww * @Date: 2020-05-22 19:23:49 * @Last Modified time: 2020-05-22 19:29:28 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 8010,mod = 998244353; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } ll qm(ll x,ll y) { ll ret = 1; for(;y;y >>= 1,x = x * x % mod) if(y & 1) ret = ret * x % mod; return ret; } ll f[2][N],jc[N],ans; int b[N]; int main() { int n = read(); jc[0] = 1; for(int i = 1;i <= n;++i) { b[read()]++; jc[i] = jc[i - 1] * i % mod; } f[0][0] = 1; for(int i = 1;i <= n;++i) { int t = i & 1; for(int j = 0;j <= n;++j) { f[t][j] = f[t ^ 1][j]; if(j) f[t][j] += 1ll * f[t ^ 1][j - 1] * b[i] % mod,f[t][j] >= mod ? f[t][j] -= mod : 0; } } for(int i = 0;i <= n;++i) { ll k = 1; if(i & 1) k = -1; ans += k * jc[n - i] * f[n & 1][i] % mod; ans %= mod; } cout<<(ans + mod) % mod<<endl; return 0; }
E 如果我让你查回文你还爱我吗
problem
给出一个长度为的字符串。然后有次查询,每次询问区间内回文串的个数。
solution
学到许多~
如果我们现在在查询这个区间,对于一个所造成的贡献就是。其中表示以i这个点中心的回文串长度。
这就比较难处理了。我们把一次询问拆成两半()进行查询。以查询为例,我们就是要求所有满足的点。因为每个回文串只有一个中心点,所以并不会被重复查询。
然后我们考虑求。其实对于一个满足条件的回文串,我们只要将这个区间+1,然后查询的时候查询的区间和就行了。因为要控制中心点的位置,所以离线下来,将询问按照右端点从小到大排序。然后一边进行区间加,一边查询就行了。
PS:细节超多~
code
/* * @Author: wxyww * @Date: 2020-04-21 20:46:23 * @Last Modified time: 2020-05-22 21:24:27 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 500010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int now,fail[N],ans[N],len[N],lst,lstans; char s[N]; int get(int p) { while(s[now - len[p] - 1] != s[now]) p = fail[p]; return p; } int trie[N][26],tot = 1,dy2[N]; void ins() { int p = get(lst); if(!trie[p][s[now] - 'a']) { len[++tot] = len[p] + 2; dy2[tot] = now; int tmp = get(fail[p]); fail[tot] = trie[tmp][s[now] - 'a']; add(dy2[fail[tot]],tot); trie[p][s[now] - 'a'] = tot; } else { dy2[++tot] = now; fail[now] = trie[p][s[now] - 'a']; add(dy2[fail[tot]],tot); } lst = trie[p][s[now] - 'a']; } int dfn[N],cnt; struct node { int v,nxt; }e[N << 1]; int siz[N],head[N],ejs; void add(int u,int v) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } void dfs(int u,int fa) { dfn[u] = ++cnt; siz[u] = 1; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v;if(v == fa) continue; dfs(v,u); siz[u] += siz[v]; } } int main() { int n = read(),m = read(); scanf("%s",s + 1); len[1] = -1; fail[0] = 1;fail[1] = 0; for(int i = 1;i <= n;++i) { now = i; ins(); } add(0,1); dfs(0,0); return 0; }