HL DAY5
Kendrick_Z · · 个人记录
今天还是有点SB 换根式子没推出来
然后明明做过换根的题 但是不知道自己在干什么乱搞T1
真是个SB
T1:
最裸的暴力就是O（n^4)
直接枚举每个子串情况
然后暴力判断求解
考虑一下优化
其实有个问题就是
这个题真的跟字符串有关吗????
不就是昨天考了字符串 然后老师迷惑下我们
考虑下五千的数据应该是O（n^2）的做法
题目要求是记录子串中位置相同 然后相同位置的个数
那么我们考虑直接两个串一个一个位置匹配
然后计算一下对答案的贡献
我们可以用数学的方法，在找到两个相同的字符后直接算出答案。将两个字符所在的位置对齐。讲两个字符串分别分出两个部分。一个左边一个右边。先算出两个字符串的左边的最小值，再算出两个字符串的右边的最小值。右边的界限是一定在右边的最小值中的。左边的界限是一定在左边的最小值中。所以方法为左边的数*右边的数。（包含当前数）
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char a[N],b[N];
int n;
long long num,ans;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
freopen("strfun.in","r",stdin);
freopen("strfun.out","w",stdout);
n=read();
cin>>a+1>>b+1;
for(int i=1;i<=n;i++){
num+=(i*i);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i]==b[j]){
ans+=min(i,j)*min(n-i+1,n-j+1);
}
}
}
// printf("%d",ans);
printf("%.6lf",(double )ans/(double )num);
return 0;
}对 100%的数据, 可以发现若 a < b，上面那个式子的值是可以确定的，所以我们转而考 虑枚举 s 串的一个位置 a，看 t 串有多少个 b 的位置使得 s[a] = t[b]，且 b > a，这样我 们可以用一个前缀和数组优化，即可通过此题。 复杂度 O(n)
#include <bits/stdc++.h>
using namespace std;
const int N=1E6+10;
long long ans,num;
int n,sa[N],sb[N];
char a[N],b[N];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
freopen("strfun.in","r",stdin);
freopen("strfun.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
num+=i*i;
}
cin>>a+1>>b+1;
for(int i=1;i<=n;i++){
sa[a[i]-'A']+=i;
ans+=sb[a[i]-'A']*(n-i+1);
sb[b[i]-'A']+=i;
ans+=sa[b[i]-'A']*(n-i+1);
}
printf("%.6lf",(double )ans/(double )num);
return 0;
}T2：
考场上手玩了一下数据
然后搞出来一个玄学的做法
具体实现？
就是我们从1号节点开始DFS树
然后我们统计一下从一号节点的树上前缀和
这样的话我们只要再考虑下再次DFS时 通过已知的从1开始的
推一下式子
结果发现 只要记录下开始的根 然后用LCA推出来了个式子
ans+=(dis[root]+dis[v]-2*dis[Lca(root,v)]+a[Lca(root,v)]);然后一开始测试的时候发现小数据过了
大样例没过
输出是负的
然后发现没lld
改过之后就A了
真的没想到
过于神奇
然后最后推了推换根式子 发现失败了
就50分吧..
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1E6+10;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
struct edge{
int next,to,w;
}e[N];
int head[N],cnt,dis[N],a[N],n,ans,f[N][21],dep[N],t;
inline void add(int x,int y,int w){
e[++cnt].next=head[x];
e[cnt].to=y;
e[cnt].w=w;
head[x]=cnt;
}
//inline void dfs1(int x,int fa){
// for(int i=head[x];i;i=e[i].next){
// int v=e[i].to;
// if(v==fa) continue;
// if(dis[v]) continue;
// dis[v]=dis[x]+a[v];
// dfs1(v,x);
// }
//}
queue<int >q;
int last=0;
inline void bfs(){
queue<int>q;
q.push(1);
dep[1]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dep[v]) continue;
dep[v]=dep[u]+1;
dis[v]=dis[u]+a[v];
f[v][0]=u;
for(int j=1;j<=t;j++){
f[v][j]=f[f[v][j-1]][j-1];
}
q.push(v);
}
}
}
inline int Lca(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
for(int i=t;i>=0;i--){
if(dep[f[y][i]]>=dep[x]) y=f[y][i];
}
if(x==y) return x;
for(int i=t;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
inline void dfs2(int root,int x,int fa,int la){
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
if(e[i].w!=la){
q.push(v);
dfs2(root,v,x,e[i].w);
ans+=(dis[root]+dis[v]-2*dis[Lca(root,v)]+a[Lca(root,v)]);
}
}
}
signed main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
n=read();
t=log2(n);
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<n;i++){
int u,v,w;
u=read();
v=read();
w=read();
add(u,v,w);
add(v,u,w);
}
bfs();//O(n)
// dfs1(1,0);
// for(int i=1;i<=n;i++){
// cout<<a[i]<<endl;
// }
for(int i=1;i<=n;i++){//Nlogn
// queue<int >q;
// last=0;
dfs2(i,i,0,0);
// while(!q.empty()){
// int u=q.front();
//// cout<<u<<" ";
// q.pop();
// ans+=(dis[i]+dis[u]-2*dis[Lca(i,u)]+a[Lca(i,u)]);
// }
// cout<<endl;
}
printf("%lld",ans/2);
return 0;
}正解好像是树形DP ？？
考虑学一学点分治
T3:
什么鬼畜的生成树计数？？
图计数我还不会
直接放弃先
还需要prufer序...
我佛了
放下STD:
#include <cstdio>
typedef long long ll;
const int Mod = 1004535809;
const int MaxN = 110;
int n, dp[MaxN][MaxN][MaxN], A[MaxN], fac[MaxN], Ie[MaxN];
int pow(int x, int k) {
ll res = 1, r = x;
for (; k; k >>= 1, r = r * r % Mod)
if (k & 1) res = res * r % Mod;
return res;
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
if (A[i] >= n) A[i] = n - 1;
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % Mod;
Ie[n] = pow(fac[n], Mod - 2);
for (int i = n; i; --i) Ie[i - 1] = (ll)Ie[i] * i % Mod;
dp[0][0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
for (int k = 0; k <= n; ++k)
if (dp[i - 1][j][k]) {
if ((dp[i][j][k] += dp[i - 1][j][k]) >= Mod) dp[i][j][k] -= Mod;
for (int c = 0; c < A[i]; ++c) {
if (k + c > n) break;
if ((dp[i][j + 1][k + c] += (ll)dp[i - 1][j][k] * Ie[c] % Mod) >= Mod) dp[i][j + 1][k + c] -= Mod;
}
}
}
}
printf("%d ", n);
for (int i = 2; i <= n; ++i) printf("%d ", (ll)dp[n][i][i - 2] * fac[i - 2] % Mod);
fclose(stdin);
fclose(stdout);
}