- 1消息中间件RabbitMQ需要知道的6个端口的作用_4369端口是什么服务
- 2从入门到入狱之kali Linux 命令指令_进入kali linux的代码
- 3Datawhale X 魔搭 AI 夏令营第四期的学习活动 Task1笔记
- 4vs2019 git拉取代码提示密码错误_the provided password or token is incorrect or you
- 5【Redis】网络模型_redis网络模型
- 6Vitis AI 综合实践（迁移学习+模型量化+DPU部署）_vitis ai dpu
- 7IDEA中Git及可视化工具TortoiseGit简单使用_git可视化工具
- 8【Flutter】编写第一个 Flutter 应用（官方示例完整代码版）_flutter编写
- 9解决git@gitee.com: Permission denied (publickey). Could not read from remote repository._gitee权限被拒绝
- 10手把手教你搭建QQ机器人_chatgptqq机器人
2020牛客暑期多校训练营（第六场）题解_2020牛客多校第六场 d data structure
赞
踩
A. African Sort
给出一个 1 1 1 ~ n n n 的排列，每次你可以选定一个子序列进行操作，代价为子序列的大小，操作内容为随机打乱这个子序列，问你在最优策略下使这个序列有序的最小代价。
如果让 i i i 向 p i p_i pi 连边，那么可以将这个排列看成若干个环，显然最优策略下肯定是对每个环单独求解，最后的结束状态是每个环的大小都为 1 1 1。
操作的花费之和可以转化为每一个点在操作过程中被几个环包含过，令
f
n
f_n
fn 表示一个一开始在大小为n的环内的点期望会被多少个环包含，要求这个东西，首先需要一个引理：
引理：随机打乱一个大小为 n n n 的环，环内每个点将等概率出现在大小为 1 1 1 ~ n n n 的环内。
证明： 设环内一个点在打乱后出现在一个大小为 i i i 的环内的概率为 c c c，那么 c = C n − 1 i − 1 × ( i − 1 ) ! × ( n − i ) ! c=C_{n-1}^{i-1}\times(i-1)!\times(n-i)! c=Cn−1i−1×(i−1)!×(n−i)!， C n − 1 i − 1 C_{n-1}^{i-1} Cn−1i−1 表示选出环内另外 i − 1 i-1 i−1 个点， ( i − 1 ) ! (i-1)! (i−1)! 表示这 i i i 个点圆排列方案数， ( n − i ) ! (n-i)! (n−i)! 表示剩下的点随便排列，将这个东西化简就得到 ( n − 1 ) ! (n-1)! (n−1)!，是与 i i i 无关的，所以是等概率出现在大小为 1 1 1 ~ n n n 的环内。
然后还有一个性质：每次操作整个环是最优的。相对的，另外一种想法是先操作环的一部分，再操作剩下的部分，这两种打乱方式代价同样为
n
n
n，但是前者一定更优，官方题解里是这么说的：
说实话，并不知道官方题解在说什么，也没有什么严谨的证明，自己手玩了很久也找不到证明，只能找到一些奇怪的结论，就不写了，如果有大佬会证的话还请救救蒟蒻qwq。
根据这两个性质，就可以推出
f
f
f 了：
f
n
=
1
+
1
n
f
n
+
∑
i
=
1
n
−
1
f
i
=
n
n
−
1
(
1
+
∑
i
=
1
n
−
1
f
i
)
=
n
n
−
1
+
n
n
−
1
∑
i
=
1
n
−
1
f
i
fn=1+1nfn+n−1∑i=1fi=nn−1(1+n−1∑i=1fi)=nn−1+nn−1n−1∑i=1fi
类似的，可以知道：
f
n
−
1
=
n
−
1
n
−
2
+
n
−
1
n
−
2
∑
i
=
1
n
−
2
f
i
f_{n-1}=\frac {n-1} {n-2}+\frac {n-1} {n-2}\sum_{i=1}^{n-2}f_i
fn−1=n−2n−1+n−2n−1i=1∑n−2fi
那么就有：
f
n
=
f
n
−
1
×
n
−
2
n
−
1
+
1
n
−
1
+
1
n
−
1
f
n
−
1
=
f
n
−
1
+
1
n
−
1
=
f
2
+
∑
i
=
3
n
1
i
−
1
=
1
+
∑
i
=
1
n
−
1
1
i
fn=fn−1×n−2n−1+1n−1+1n−1fn−1=fn−1+1n−1=f2+n∑i=31i−1=1+n−1∑i=11i
此时就可以递推求 f f f 了，边界为 f 1 = 0 , f 2 = 2 f_1=0,f_2=2 f1=0,f2=2
那么对于一个大小为 k k k 的环，代价就是 k × f k k\times f_k k×fk，这样就可以求解了，代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 100010 #define mod 998244353 int n,m,a[maxn]; int inv[maxn],f[maxn]; int main() { f[2]=2;inv[1]=1; for(int i=2;i<=maxn-10;i++){ inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; f[i+1]=(f[i]+inv[i])%mod; } scanf("%d %d",&n,&m); while(m--){ for(int i=1;i<=n;i++)scanf("%d",&a[i]); int ans=0; for(int i=1;i<=n;i++)if(a[i]){ int sz=1; for(int j=a[i],ne=a[j];j!=i;a[j]=0,j=ne,ne=a[j])sz++; ans=(ans+1ll*sz*f[sz]%mod)%mod; } printf("%d\n",ans); } }
- 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
B. Binary Vector
问你随机选出 n n n 个 n n n 维向量，他们线性无关的概率是多少，要求选出的向量每一维只能是 0 0 0 或 1 1 1。
假设现在已经选出 i i i 个线性无关的向量了，那么这 i i i 个向量一定张成了一个 i i i 维的空间，在这个 i i i 维空间内任意向量都可以被这 i i i 个向量表示出来。
也就是说，第 i + 1 i+1 i+1 个向量一定要扩张出新的一维，这样才能保证这个新向量与前面的向量线性无关。由于前面已经形成了一个 i i i 维的空间，这个空间内包含了 2 i 2^i 2i 个 01 01 01 向量，所以新向量只能选择剩下的 2 n − 2 i 2^n-2^i 2n−2i 个向量，选到的概率就是 2 n − 2 i 2 n \dfrac {2^n-2^i} {2^n} 2n2n−2i。
那么就有：
f
(
n
)
=
∏
i
=
0
n
−
1
2
n
−
2
i
2
n
=
∏
i
=
0
n
−
1
2
n
−
i
−
1
2
n
−
i
=
∏
i
=
1
n
2
i
−
1
2
i
=
f
(
n
−
1
)
×
2
n
−
1
2
n
f(n)=n−1∏i=02n−2i2n=n−1∏i=02n−i−12n−i=n∏i=12i−12i=f(n−1)×2n−12n
于是代码如下：
#include <cstdio>
#define maxn 20000010
#define mod 1000000007
int T,n,f[maxn],inv2=(mod+1)/2;
int main()
{
f[0]=1;
for(int i=1,p=inv2;i<=maxn-10;i++,p=1ll*p*inv2%mod)
f[i]=(f[i-1]-1ll*f[i-1]*p%mod+mod)%mod;
for(int i=2;i<=maxn-10;i++)f[i]^=f[i-1];
scanf("%d",&T);while(T--)scanf("%d",&n),printf("%d\n",f[n]);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
C. Combination of Physics and Maths
给出一个矩阵 a a a，找到一个 { 1 , 2 , . . . , n } \{1,2,...,n\} {1,2,...,n} 的子序列 A A A 和 { 1 , 2 , . . . , m } \{1,2,...,m\} {1,2,...,m} 的子序列 B B B，满足 ( ∑ i = 1 ∣ A ∣ ∑ j = 1 ∣ B ∣ a A i , B j ) / ( ∑ j = 1 ∣ B ∣ a A ∣ A ∣ B j ) (\sum_{i=1}^{|A|}\sum_{j=1}^{|B|}a_{A_i,B_j})/(\sum_{j=1}^{|B|}a_{A_{|A|}B_j}) (∑i=1∣A∣∑j=1∣B∣aAi,Bj)/(∑j=1∣B∣aA∣A∣Bj) 最大。
容易发现一个性质，当子矩阵的底为第 i i i 行时， A A A 一定为 { 1 , 2 , . . . , i } \{1,2,...,i\} {1,2,...,i}，因为上面那些不拿白不拿，拿了肯定能更大。
那么可以考虑枚举子矩阵的底，设为第 i i i 行，然后对于每一列，令 b j = ∑ x = 1 i a i , j b_j=\sum_{x=1}^i a_{i,j} bj=∑x=1iai,j，那么就是要选出若干个 j j j 使 ∑ x = 1 ∣ B ∣ b B x ∑ x = 1 ∣ B ∣ a i , B x \dfrac{\sum_{x=1}^{|B|} b_{B_x}} {\sum_{x=1}^{|B|}a_{i,B_x}} ∑x=1∣B∣ai,Bx∑x=1∣B∣bBx 最大。
当时想到这里，发现这不是个裸的 01 01 01 分数规划吗！冲冲冲
写到一半发现，这压根不用规划，直接贪心拿 b x a i , x \dfrac {b_x} {a_{i,x}} ai,xbx 最大的 x x x 就好了，再拿其他的显然不能使比值更大……
于是代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 210 int T,n,m,a[maxn][maxn],b[maxn]; double ans; int main() { scanf("%d",&T);while(T--) { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)scanf("%d",&a[i][j]); memset(b,0,sizeof(b));ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)b[j]+=a[i][j],ans=max(ans,1.0*b[j]/a[i][j]); } printf("%.8lf\n",ans); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
D.Data structure
给出一棵树，有 m m m 个询问，每次询问区间 [ l , r ] [l,r] [l,r] 内有多少对点的 l c a lca lca 是 x x x。
询问转化一下，就是 x x x 子树中 [ l , r ] [l,r] [l,r] 内的点两两配对减 x x x 的儿子的子树中 [ l , r ] [l,r] [l,r] 内点两两配对。
前者可以用主席树瞎搞，比较简单，重点是后者。
考虑轻重链剖分，对于一个对 x x x 点的询问，直接减去 x x x 重儿子子树内的配对数，这个也可以用主席树求，这部分复杂度为 O ( m log n ) O(m\log n) O(mlogn)。
对于轻儿子，考虑对询问跑莫队，每次新增或删除一个点时，将这个点沿着重链跳，由于此时只需要求轻儿子的答案，所以只会影响 log n \log n logn 个点，这部分复杂度是 O ( n n log n ) O(n\sqrt n\log n) O(nn logn) 的。
但是事实上第二个部分会 T T T 飞。
为了听懂下面的优化，你得先理解上面这个做法，这份代码是上面做法的正确实现，不太理解的话建议看一遍：
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <algorithm> using namespace std; #define maxn 200010 #define ll long long int n,m,rt; struct edge{int y,next;}e[maxn<<1]; int first[maxn],len=0; void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;} int fa[maxn],size[maxn],mson[maxn]; void dfs1(int x){//轻重链剖分 size[x]=1; for(int i=first[x],y;i;i=e[i].next)if((y=e[i].y)!=fa[x]){ fa[y]=x;dfs1(y); size[x]+=size[y]; if(size[y]>size[mson[x]])mson[x]=y; } } int id[maxn],con[maxn],old[maxn],idtot=0,top[maxn]; void dfs2(int x,int tp){ top[x]=tp;id[x]=++idtot;old[idtot]=x; if(mson[x])dfs2(mson[x],tp); for(int i=first[x];i;i=e[i].next) if(e[i].y!=fa[x]&&e[i].y!=mson[x])dfs2(e[i].y,e[i].y); con[x]=idtot; } ll ans[maxn]; struct que{int l,r,x,pos;}q[maxn]; vector<que>Q[maxn]; #define zuo ch[0] #define you ch[1] struct node *null=NULL; struct node{//主席树 int l,r,mid,z;node *ch[2]; node(int x,int y):l(x),r(y),mid(l+r>>1),z(0){ch[0]=ch[1]=null;} int ask(int x,int y){ if(this==null)return 0; if(l==x&&r==y)return z; if(y<=mid)return zuo->ask(x,y); else if(x>=mid+1)return you->ask(x,y); else return zuo->ask(x,mid)+you->ask(mid+1,y); } }*root[maxn]; void build(node *&from,node *&to,int l,int r,int x){ to=new node(l,r);if(l==r)return (void)(to->z++); int mid=l+r>>1,p=(x>=mid+1); to->ch[p^1]=from->ch[p^1];//¼Ì³Ð build(from->ch[p],to->ch[p],p?mid+1:l,p?r:mid,x);//н¨ to->z=to->zuo->z+to->you->z;//¸üР} void get_ans1(){ null=new node(0,0);null->zuo=null->you=null; root[0]=null; for(int i=1;i<=n;i++)build(root[i-1],root[i],1,n,old[i]); for(int i=1;i<=n;i++)if(mson[i]){ for(que j:Q[i]){ int x=root[con[i]]->ask(j.l,j.r)-root[id[i]-1]->ask(j.l,j.r),y=mson[i];//自己子树内配对数 int z=root[con[y]]->ask(j.l,j.r)-root[id[y]-1]->ask(j.l,j.r);//重儿子内配对数 ans[j.pos]+=1ll*x*(x-1)/2-1ll*z*(z-1)/2; } } } int be[maxn],block; #define belong(x) (x/block) bool cmp(que x,que y){return be[x.l]==be[y.l] ? (be[x.l]&1 ? x.r<y.r : x.r>y.r) : be[x.l]<be[y.l];} ll c[maxn],val[maxn];//c[i]表示当前i子树内有多少个[l,r]区间内的点，val[i]记录i的轻儿子的配对数之和 void add(int x){ for(int i;i=fa[top[x]];x=i) val[i]+=c[top[x]]++; } void del(int x){ for(int i;i=fa[top[x]];x=i) val[i]-=--c[top[x]]; } void get_ans2(){ block=n/(int)sqrt(n*2/3); for(int i=1;i<=n;i++)be[i]=(i-1)/block; sort(q+1,q+m+1,cmp); int l=1,r=0; for(int i=1;i<=m;i++){ while(r<q[i].r)add(++r); while(l>q[i].l)add(--l); while(r>q[i].r)del(r--); while(l<q[i].l)del(l++); ans[q[i].pos]-=val[q[i].x]; } } inline char cn() { static char buf[1000010],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } #define cn getchar template<class TY>void read(TY &x) { x=0;int f1=1;char ch=cn(); while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();} while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1; } char Output[1000100],Zk[100];int op_top=0,Zk_top; void fcheck(int Type=0){if(Type||op_top>=1000000)fwrite(Output,1,op_top,stdout),op_top=0;} template<class TY>inline void write(TY x) { if(x==0){Output[op_top++]='0';fcheck();return;} if(x<0)Output[op_top++]='-',x=-x; Zk_top=0;while(x)Zk[++Zk_top]=x%10+'0',x/=10; while(Zk_top)Output[op_top++]=Zk[Zk_top--];fcheck(); } #define K_G Output[op_top++]=' ' #define H_C Output[op_top++]='\n' int main() { read(n);read(m);read(rt); for(int i=1,x,y;i<n;i++){ read(x);read(y); buildroad(x,y),buildroad(y,x); } for(int i=1;i<=m;i++){ read(q[i].l);read(q[i].r);read(q[i].x);q[i].pos=i; Q[q[i].x].push_back(q[i]); } dfs1(rt);dfs2(rt,rt); get_ans1();//求解子树平方并减去重儿子的平方 get_ans2();//莫队求轻儿子 for(int i=1;i<=m;i++)write(ans[i]),H_C; fcheck(1);return 0; }
- 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
考虑优化，实测发现代码中 90 % 90\% 90% 的时间复杂度都来自第二个部分，考虑降低一下他的复杂度。
不妨稍微让轻重链剖分假一点，考虑根号分治，设置一个上限
S
Z
SZ
SZ，令
x
x
x 的子树大小超过SZ的儿子都成为
x
x
x 的重儿子，那么第二个部分跳重链时跳次数的就会少很多。
如果让 S Z SZ SZ 与根号相关，比如 s i z e [ x ] \sqrt{size[x]} size[x] ， s i z e [ x ] size[x] size[x] 是 x x x 的子树大小，那么 x x x 的重儿子个数不会超过 S Z SZ SZ 个，那么第一个部分的时间复杂度就变成了 O ( n c log n ) O(nc\log n) O(nclogn)，其中 c c c 是每个点重儿子个数，比 n \sqrt n n 要小不少但是仍然大于 log n \log n logn。
然后再考虑降低一下第一个部分的时间复杂度，发现主席树其实是可以用树状数组代替的，只需要将所有询问排个序即可。
时间用了 775 m s 775ms 775ms，算挺快的，具体细节看代码吧：
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <ctime> #include <algorithm> using namespace std; #define maxn 200010 #define ll long long #define pb push_back int n,m,rt; struct edge{int y,next;}e[maxn<<1]; int first[maxn],len=0; void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;} int fa[maxn],size[maxn]; int id[maxn],con[maxn],old[maxn],idtot=0; vector<int>mson[maxn],lson[maxn]; void dfs1(int x){ size[x]=1;id[x]=++idtot;old[idtot]=x; for(int i=first[x],y;i;i=e[i].next)if((y=e[i].y)!=fa[x]){ fa[y]=x;dfs1(y); size[x]+=size[y]; } int SZ=sqrt(size[x])/3;//代码里的块长都是选实测出来比较快的 for(int i=first[x],y;i;i=e[i].next)if((y=e[i].y)!=fa[x]) if(size[y]>SZ)mson[x].pb(y);else lson[x].pb(y);//分轻重儿子 con[x]=idtot; } int top[maxn]; void dfs2(int x,int tp){ top[x]=tp; for(int i:mson[x])dfs2(i,tp); for(int i:lson[x])dfs2(i,i); } ll ans[maxn]; struct que{int l,r,x,pos;}q[maxn]; struct que2{int x,pos,t1,t2,t3;};//t1:是原点还是重儿子 ; t2:询问的左端点还是右端点 ; t3:在tmp中的位置 vector<que2>Q[maxn]; struct tree{ int tr[maxn]; void add(int x){for(;x<=n;x+=(x&-x))tr[x]++;} int sum(int x){int re=0;for(;x;x-=(x&-x))re+=tr[x];return re;} }tr; vector<int>tmp;int t=-1; void get_ans1(){ for(int i=1;i<=n;i++){ tr.add(id[i]); for(que2 j:Q[i]){ tmp[j.t3]+=(tr.sum(con[j.x])-tr.sum(id[j.x]-1))*j.t2; if(j.t2==1)ans[j.pos]+=1ll*tmp[j.t3]*(tmp[j.t3]-1)/2*(j.t1?1:-1); } } } int be[maxn],block; #define belong(x) (x/block) bool cmp(que x,que y){return be[x.l]==be[y.l] ? (be[x.l]&1 ? x.r<y.r : x.r>y.r) : be[x.l]<be[y.l];} ll c[maxn],val[maxn],tot=0; void add(int x){ for(int i;i=fa[top[x]];x=i) val[i]+=c[top[x]]++,tot++; } void del(int x){ for(int i;i=fa[top[x]];x=i) val[i]-=--c[top[x]],tot++; } void get_ans2(){ block=n/sqrt(n*2/3); for(int i=1;i<=n;i++)be[i]=(i-1)/block; int last=clock(); sort(q+1,q+m+1,cmp); int l=1,r=0; for(int i=1;i<=m;i++){ while(r<q[i].r)add(++r); while(l>q[i].l)add(--l); while(r>q[i].r)del(r--); while(l<q[i].l)del(l++); ans[q[i].pos]-=val[q[i].x]; } } inline char cn() { static char buf[1000010],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } #define cn getchar template<class TY>void read(TY &x) { x=0;int f1=1;char ch=cn(); while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();} while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1; } char Output[1000100],Zk[100];int op_top=0,Zk_top; void fcheck(int Type=0){if(Type||op_top>=1000000)fwrite(Output,1,op_top,stdout),op_top=0;} template<class TY>inline void write(TY x) { if(x==0){Output[op_top++]='0';fcheck();return;} if(x<0)Output[op_top++]='-',x=-x; Zk_top=0;while(x)Zk[++Zk_top]=x%10+'0',x/=10; while(Zk_top)Output[op_top++]=Zk[Zk_top--];fcheck(); } #define K_G Output[op_top++]=' ' #define H_C Output[op_top++]='\n' int main() { read(n);read(m);read(rt); for(int i=1,x,y;i<n;i++){ read(x);read(y); buildroad(x,y),buildroad(y,x); } dfs1(rt);dfs2(rt,rt); for(int i=1;i<=m;i++){ read(q[i].l);read(q[i].r);read(q[i].x);q[i].pos=i; tmp.pb(0);t++; Q[q[i].l-1].push_back((que2){q[i].x,i,1,-1,t}); Q[q[i].r ].push_back((que2){q[i].x,i,1, 1,t}); for(int j:mson[q[i].x]){ tmp.pb(0);t++; Q[q[i].l-1].push_back((que2){j,i,0,-1,t}); Q[q[i].r ].push_back((que2){j,i,0, 1,t}); } } get_ans1(); get_ans2(); for(int i=1;i<=m;i++)write(ans[i]),H_C; fcheck(1);return 0; } /* 自制小数据: 9 5 3 3 7 7 4 7 2 2 5 2 6 6 9 3 1 1 8 3 8 7 1 9 1 2 5 2 3 8 3 4 6 2 5 1 1 9 1 */
- 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
- 146
- 147
- 148
- 149
- 150
- 151
E. Easy Construction
构造一个 1 1 1 ~ n n n 的排列，满足对于任意 i i i，都存在一个长为 i i i 的区间，这个区间的和在模 n n n 意义下等于 k k k。
比较简单就直接上代码了：
#include <cstdio> #define boom return printf("-1"),0 int n,k; int main() { scanf("%d %d",&n,&k); //当n为奇数时，总和模n一定是0，偶数时总和模n一定是n/2 //如果k不等于总和模n，那么就不存在长度为n的区间满足区间和模n为k if(n%2){//然后随便构造一下就行了 if(k!=0)boom; for(int i=1;i<=n/2;i++)printf("%d %d ",i,n-i); printf("%d",n); }else{ if(k!=n/2)boom; for(int i=1;i<n/2;i++)printf("%d %d ",i,n-i); printf("%d %d ",k,n); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
G. Grid Coloring
给出一张 n × n n\times n n×n 的网格图，有 k k k 种颜色，你要给每条边染色，满足：1、每种颜色出现次数相同；2、没有一个格子的四条边相同颜色；3、没有一行或一列的边都是相同颜色的。
有解的话一定满足 n > 1 , k > 1 , k ∣ 2 n ( n + 1 ) n>1,k>1,k|2n(n+1) n>1,k>1,k∣2n(n+1)。
分类讨论，当
k
k
k 是偶数且
k
≠
2
k\neq 2
k=2 时，可以将
k
k
k 种颜色均分两份分别给行和列，然后找到
n
+
1
n+1
n+1 和
n
n
n 的一组因子
x
,
y
x,y
x,y 满足
x
y
=
k
2
xy=\dfrac k 2
xy=2k，然后将行或列的
(
n
+
1
)
×
n
(n+1)\times n
(n+1)×n 条边分成
x
×
y
x\times y
x×y 份，然后每份内放相同的颜色，为了满足限制
2
2
2，将每行的颜色交错着放，再要满足限制
3
3
3，将奇数行右移一位即可，这是官方题解的图：
说句闲话，官方题解给的std A不了这题QAQ……
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 210 int T,n,k; int a[maxn][maxn],c; void go(int K){ int x,y; for(int i=1;i<=n+1;i++) if(K%i+(n+1)%i+n%(K/i)==0){x=i,y=K/i;break;} if(x<K){ x=(n+1)/x; for(int i=1;i<=n+1;i++){ int now=(i-1)/x*y; for(int j=1;j<=n;j++)a[i][j]=(j-1)%y+1+now; if(i&1){ now=a[i][1]; for(int j=1;j<n;j++)a[i][j]=a[i][j+1]; a[i][n]=now; } } }else{ y=n/y; for(int j=1;j<=n;j++){ int now=(j-1)/y*x; for(int i=1;i<=n+1;i++)a[i][j]=(i-1)%x+1+now; if(j&1){ now=a[1][j]; for(int i=1;i<n+1;i++)a[i][j]=a[i+1][j]; a[n+1][j]=now; } } } } int main() { scanf("%d",&T);while(T--) { scanf("%d %d",&n,&k); if(n==1||k==1||2*n*(n+1)%k){printf("-1\n");continue;} if(k%2||k==2)go(k),c=0; else go(k/2),c=k/2; for(int i=1;i<=n+1;i++){ for(int j=1;j<=n;j++) printf("%d ",a[i][j]); printf("\n"); } for(int i=1;i<=n+1;i++){ for(int j=1;j<=n;j++) printf("%d ",a[i][j]+c); printf("\n"); } } }
- 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
这是重写的更简短的代码：
#include <cstdio> int T,n,k; int main() { scanf("%d",&T);while(T--) { scanf("%d %d",&n,&k); if(n==1||k==1||2*n*(n+1)%k){printf("-1\n");continue;} int x,y,c; if(k%2||k==2)c=0;else k/=2,c=k; for(int i=1;i<=n+1;i++) if((n+1)%i + k%i + n%(k/i)==0){x=i,y=k/i;break;} for(int d=0,col;d<=1;d++){ for(int i=1;i<=n+1;i++){ for(int j=1;j<=n;j++){ col=(i-1)/((n+1)/x)*y+(i%2+j-1)%y+1; if(x==k)col=(j%2+i-1)%x+1; printf("%d ",col+c*d); } printf("\n"); } } } }
- 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
H. Harmony Pairs
设 S ( x ) S(x) S(x) 表示 x x x 每一位上的数字之和，求满足 0 ≤ A ≤ B ≤ n , S ( A ) > S ( B ) 0\leq A\leq B\leq n,S(A)>S(B) 0≤A≤B≤n,S(A)>S(B) 的 A , B A,B A,B 有多少对。
比较容易想到数位 dp \text{dp} dp，我一开始想的状态是前 i i i 位和为 j j j 的数字个数，然后写的时候越写越难写，很难判断和 n n n 位数一样的数是否大于 n n n，然后就自闭了。
膜了一发题解，题解的状态很妙，设 f [ i ] [ j ] [ t 1 ] [ t 2 ] f[i][j][t1][t2] f[i][j][t1][t2] 表示最高的 i i i 位已经确定，两数的 S S S 差为 j j j， t 1 , t 2 t1,t2 t1,t2 表示 A A A 与 B B B ， B B B 与 n n n 目前的大小关系， 1 1 1 表示小于， 0 0 0 表示等于，大于的状态是没有用的所以不记录。
然后每次枚举 A , B A,B A,B 下一位是什么就可以了，很容易写，代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 110 #define dlt 1000//偏移量 #define mod 1000000007 char s[maxn]; int n,a[maxn]; int f[maxn][2*dlt][2][2]; void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);} int main() { scanf("%s",s+1);n=strlen(s+1); for(int i=1;i<=n;i++)a[i]=s[i]-'0'; f[0][dlt][0][0]=1; for(int i=0;i<n;i++){ for(int j=0;j<=2*dlt;j++){ for(int t1=0;t1<2;t1++){ for(int t2=0;t2<2;t2++)if(f[i][j][t1][t2]){ for(int A=0;A<=9;A++){ for(int B=0;B<=9;B++){ if((A>B&&!t1) || (B>a[i+1]&&!t2) || j+A-B<0)continue; int T1=t1|(A<B),T2=t2|(B<a[i+1]); add(f[i+1][j+A-B][T1][T2],f[i][j][t1][t2]); } } } } } } int ans=0; for(int i=dlt+1;i<=dlt*2;i++){ for(int j=0;j<2;j++){ add(ans,f[n][i][1][j]); } } printf("%d",ans); }
- 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
J. Josephus Transform
给出一个序列，有 m m m 次操作，每次给出 k , x k,x k,x，表示对这个序列进行 x x x 次距离为 k k k 的约瑟夫游戏，进行一次游戏后生成的序列是每个数按死亡时间排序后的序列，求最后的序列。
注意到数据范围 n × m ≤ 1 0 6 n\times m\leq 10^6 n×m≤106，就是在暗示我们每次操作是 O ( n ) O(n) O(n) 或 O ( n log n ) O(n\log n) O(nlogn) 的qwq。
所以每次可以用权值线段树求出 1 1 1 ~ n n n 的排列进行一次距离为 k k k 的约瑟夫游戏后的序列，这个序列可以看成一个置换，将其中的每个循环旋转 x − 1 x-1 x−1 次，就得到了 1 1 1 ~ n n n 进行 x x x 次 k k k 距离的约瑟夫游戏后的序列，再将原序列映射一下就好了。
代码如下：
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define maxn 100010 #define pb push_back int n,m,a[maxn],b[maxn],c[maxn]; struct node{ int l,r,mid,z;node *zuo,*you; node(int x,int y):l(x),r(y),mid(l+r>>1),z(0){ if(x<y){ zuo=new node(l,mid); you=new node(mid+1,r); }else zuo=you=NULL; } void init(){z=r-l+1;if(l<r)zuo->init(),you->init();} int find(int x){ z--;if(l==r)return l; if(x<=zuo->z)return zuo->find(x); else return you->find(x-zuo->z); } }; bool v[maxn]; vector<int>s; void work(int k,int x){ static node *root=new node(1,n); root->init();int pos=1; for(int i=1;i<=n;i++){ pos=(pos+k-2)%(n-i+1)+1; b[i]=root->find(pos); v[i]=false; } for(int i=1;i<=n;i++)if(!v[i]){ s.clear();s.pb(i);v[i]=true; for(int j=b[i];j!=i;j=b[j])s.pb(j),v[j]=true; int p=x%(int)s.size(); for(int j=0;j<s.size();j++)b[s[j]]=s[(j+p)%(int)s.size()]; } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)a[i]=i; for(int i=1,k,x;i<=m;i++){ scanf("%d %d",&k,&x); work(k,x); for(int j=1;j<=n;j++)c[j]=a[b[j]]; for(int j=1;j<=n;j++)a[j]=c[j]; } for(int i=1;i<=n;i++)printf("%d ",a[i]); }
- 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
K. K-Bag
定义一个序列是 k-Bag \text{k-Bag} k-Bag 的，当且仅当这个序列由若干个 1 1 1 ~ k k k 的排列拼接而成，现在问一个序列是不是一个 k-Bag \text{k-Bag} k-Bag 序列的片段。
如果是，那么一定形如： ∗ ∗ ∗ + 1 ***+1 ∗∗∗+1 ~ k + 1 k+1 k+1 ~ k + . . . + 1 k+...+1 k+...+1 ~ k + ∗ ∗ ∗ k+*** k+∗∗∗， 1 1 1 ~ k k k 表示 1 1 1 到 k k k 的一个排列， ∗ ∗ ∗ *** ∗∗∗ 表示一段没有重复数字的序列，并且长度小于 k k k。
然后就随便判一下就做完了，代码如下：
#include <cstdio> #include <set> #include <algorithm> using namespace std; #define maxn 500010 int T,n,k,a[maxn],b[maxn],tot=0,f[maxn]; set<int>s; void add(int x){if(!b[x]++)tot++;}; void del(int x){if(!--b[x])tot--;} int main() { scanf("%d",&T);while(T--) { scanf("%d %d",&n,&k);bool tf=false; for(int i=1;i<=n;i++)scanf("%d",&a[i]),tf|=a[i]>k; if(tf){printf("NO\n");continue;}//有数字大于k int st=0;s.clear();while(!s.count(a[st+1]))st++,s.insert(a[st]);//求出头尾的***长度 int ed=n+1;s.clear();while(!s.count(a[ed-1]))ed--,s.insert(a[ed]); if(st>=ed-1){printf("YES\n");continue;} //假如k>n，那么序列中不可能存在1~k的排列，所以一定是两段***组成，假如存在两段以上***就无解 else if(k>n){printf("NO\n");continue;} for(int i=0;i<=st;i++)f[i]=1;//f[i]表示前i位是否有可能是k-Bag序列的片段 for(int l=1,r=1;l<=n;l++){//two-pointers找1~k的排列 while(tot<k&&r<=n)add(a[r++]); if(tot==k&&r-l==k)f[r-1]|=f[l-1]; del(a[l]); } tf=false;for(int i=ed-1;i<=n;i++)tf|=f[i]; if(tf)printf("YES\n");else printf("NO\n"); for(int i=1;i<=n;i++)b[a[i]]=0,f[i]=0; } }
- 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
