20191105模拟-pb

pb的场

xgc和高尔夫

题意:在一棵跳跳棋一样的无限二叉树上,给出起点和终点,统计有多少条长度恰为$K \le 100$的路径

请先思考后再展开

整场都投资在这题上了,结果赛后30min才过拍,主要是想错好多次。当然做法本身也不是很简洁,复杂度是$O(K^3+qK^2)$

总共需要处理5种函数,相同深度的节点是等价的,然后下面的计数其实思想都是一致的,就是要将最后的特殊段唯一贡献地取出,这算是计数的基本技能吧(那你为啥搞半天啊喂):
$$
\\down=ban掉父亲回到起点,down(dep,ln)=\sum_{i=0}^{ln-2} down(dep,ln-i-2)*2*down(dep+1,i)
\\up=ban掉一个孩子回到起点,up(dep,ln)=\sum_{i=0}^{ln-2} up(dep,ln-i-2)*(up(dep-1,i)+down(dep+1,i))
\\g=回到起点,g(dep,ln)=\sum_{i=0}^{ln-2} g(dep,ln-i-2)*(up(dep-1,i)+2*down(dep+1,i))
\\T2=从根节点(深度0)出发到这里且最后一步是向上,T2(dep,ln)=\sum_{i=2}^{ln-1} T1(dep-1,ln-i-1)*down(dep,i)
\\T1=从根节点(深度0)出发到这里,T1=\sum_{i=0}^{dep} T2(i,ln-(dep-i))
$$
主要是这个T1的求法,我的思路是将每种路径唯一计数地贡献到最后一次刚上升完的那个点上,接下来都是往下走,这样肯定是唯一的

搞定这些之后就没啥了,求一下lca,设长的链长为real1,另一条为real2,

起点终点相同就是g,有祖先关系就是$\sum_{ln1=1}^K T1(real-1,ln-1)*g(lcadep,K-ln1)$

否则就各自不经过lca地到两个儿子处,$\sum_{ln1=1}^K \sum_{ln2=1}^K T1(real1-1,ln1-1)*T1(real2-1,ln2-1)*g(lcadep,K-ln1-ln2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<bitset>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<assert.h>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define vc vector
#define PB push_back
#define bin(x) (1ll<<(x))
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define fo(i,a,b) for(register int i=(a);i<=(b);i++)
#define fd(i,a,b) for(register int i=(a);i>=(b);i--)
ll qread()
{
ll ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) putchar('-'),num=-num;
if(num>=10) write(num/10);putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);putchar('\n');}
template<typename T> void chmin(T &a,const T b){a=(a<b?a:b);}
template<typename T> void chmax(T &a,const T b){a=(a>b?a:b);}
const int N=1e3+10;
ll qpower(ll x,ll e,ll mod)
{
int ans=1;x%=mod;
while(e)
{
if(e&1) ans=ans*x%mod;
x=x*x%mod;e>>=1;
}return ans;
}
const int MOD=1e9+7;
template<typename T> void add(T &a,const int b){a=(a+b<MOD?a+b:a+b-MOD);}

map<ll,ll> G[200],U[200],D[200];
ll down(ll dep,int ln)
{
if(ln&1) return 0;if(!ln) return 1;if(D[ln].count(dep)) return D[ln][dep];
ll ans=0;fo(i,0,ln-2) add(ans, down(dep,ln-i-2)*2*down(dep+1,i)%MOD );
return D[ln][dep]=ans;
}
ll up(ll dep,int ln)
{
if(ln&1) return 0;if(!ln) return 1;if(U[ln].count(dep)) return U[ln][dep];
ll ans=0;fo(i,0,ln-2) add(ans, up(dep,ln-i-2)*((dep?up(dep-1,i):0)+down(dep+1,i))%MOD );
return U[ln][dep]=ans;
}
ll g(ll dep,int ln)
{
if(ln&1) return 0;if(!ln) return 1;if(G[ln].count(dep)) return G[ln][dep];
ll ans=0;fo(i,0,ln-2) add(ans, g(dep,ln-i-2)*((dep?up(dep-1,i):0)+2*down(dep+1,i))%MOD );
return G[ln][dep]=ans;
}
map<ll,ll> TT1[200],TT2[200];
ll T1(ll dep,int ln);
ll T2(ll dep,int ln)
{
if(!ln) return 0;if((ln-dep)&1) return 0;
if(!dep) return TT2[ln][dep]=down(dep,ln);
if(TT2[ln].count(dep)) return TT2[ln][dep];
ll ans=0;
fo(i,2,ln-1) add(ans, T1(dep-1,ln-i-1)*down(dep,i)%MOD );
return TT2[ln][dep]=ans;
}
ll T1(ll dep,int ln)
{
if(ln<dep) return 0;if((ln-dep)&1) return 0;
if(!ln) return dep==0;if(ln==dep) return 1;
if(TT1[ln].count(dep)) return TT1[ln][dep];
ll ans=T2(dep,ln);
fo(i,0,dep-1) if(ln-(dep-i)>i) add(ans, T2(i,ln-(dep-i)) );
return TT1[ln][dep]=ans;
}

ll getdep(ll d1,ll d2)
{
if(!d1 or !d2) return -1;if(d1==d2) return 0;
if(d1<d2) return (d2/d1)+getdep(d1,d2%d1);
return (d1/d2)+getdep(d1%d2,d2);
}
void tofa(ll &a,ll &b,ll &c)
{
if(b-a==c-b)
puts("error");
if(b-a<c-b) a=b+b-a,swap(a,b); else c=b+b-c,swap(b,c);
}
void main()
{
ll a,b,c,A,B,C,K;scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&A,&B,&C,&K);
if(a==A and b==B and c==C) {write(g(getdep(b-a,c-b),K));return;}
if(a-b==b-c)
{
ll dep=getdep(B-A,C-B);if(dep>K){write(0);return;}
write(T1(dep,K));return;
}
ll d1=getdep(b-a,c-b),d2=getdep(B-A,C-B),ans=0;
if(d1<d2) swap(A,a),swap(B,b),swap(C,c),swap(d1,d2);
ll x1=a,x2=A,y1=b,y2=B,z1=c,z2=C;
int real1=0,real2=0;
while(d1!=d2) d1--,tofa(x1,y1,z1),real1++;
while(x1!=x2 or y1!=y2 or z1!=z2) tofa(x1,y1,z1),tofa(x2,y2,z2),real2++;real1+=real2;
ll lcadep=getdep(y1-x1,z1-y1);

if(!real1 and !real2) ans=g(d1,K);
else if(!real2)
{
fo(ln1,1,K) add(ans, T1(real1-1,ln1-1)*g(lcadep,K-ln1)%MOD );
}
else fo(ln1,1,K) fo(ln2,1,K)
{
if(K-ln1-ln2>=0) add(ans,
T1(real1-1,ln1-1)*g(lcadep,K-ln1-ln2)%MOD*T1(real2-1,ln2-1)%MOD );
}
write(ans);
}
};//0 3 5 -2 1 5 7
int main()
{
srand(time(0));
mine::main();
}

DD头子张京华

题意:给出n个人,每个人有二进制标签$a_i \in [0,2^8)$,有m种代价为$val_i$的覆盖方案$s_i$,有两类:覆盖s为其前缀的人、覆盖s为其后缀的人,问覆盖所有人的最小代价,$m \le 500,w_i \le 1e3$

请先思考后再展开

考虑最小割

建出正串和反串的Trie,代表同个人的叶子节点间连边,Trie上边也连边,初始边权都是INF,每次加入方案的时候给对应节点与其父亲那条边,对$val_i$取min即可

AGC010D Decrementing

题意:给出一个长度为$n \le 1e5$且gcd=1的序列A,先后手轮流操作,每次选一个非1的数–,然后整个序列/gcd,不能操作者败北,问谁赢

请先思考后再展开

首先始终互质意味着始终存在奇数

如果没有/gcd的操作,我们只关心这个序列和的奇偶性,具体而言就是如果有奇数个偶数先手必胜

突破口:注意到一个数除它的奇因子不会改变奇偶性,所以只需要关心gcd=偶的情况

gcd=偶,只会发生在初始局面恰一个奇数的时候,先手将它搞成偶数,这只会连续发生log次,递归做即可,$O(nlog^2n)$

code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d870fa2f.html
转载请注明出处,谢谢!