概述
前言
咕了AGC去打Comet OJ
回过头来发现这场怎么这么zz啊
亏了亏了
题目链接
01 Matrix
这样构造(灵魂画师谢罪了)
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int h,w,a,b;
int main() {
scanf("%d%d%d%d",&h,&w,&a,&b);
fo(i,1,b) {
fo(j,1,w) putchar(j<=a?'1':'0');
puts("");
}
fo(i,b+1,h) {
fo(j,1,w) putchar(j<=a?'0':'1');
puts("");
}
return 0;
}
Sorting a Segment
不用动脑的想法叫做线段树维护哈希值
事实上会发现，两个区间[l1,r1],[l2,r2]是等价的只有两种情况：
1.[l1,r1]和[l2,r2]都单调不降
2.[l1,r1],[l1+1,r1+1],[l1+2,r1+2]…[l2,r2]全部等价
判断相邻两个区间是否等价是简单的，只需要求区间最值，单调队列即可做到线性
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int read() {
char ch;
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
int x=ch-'0';
for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x;
}
const int N=2e5+5;
int n,k,p[N],mx[N],mn[N],Mx[N],Mn[N],h1,t1,h2,t2;
void push(int x) {
while (h1<=t1&&p[mx[t1]]<p[x]) t1--;mx[++t1]=x;
while (h2<=t2&&p[mn[t2]]>p[x]) t2--;mn[++t2]=x;
}
void pop(int x) {
while (h1<=t1&&mx[h1]<x-k+1) h1++;
while (h2<=t2&&mn[h2]<x-k+1) h2++;
}
int main() {
n=read();k=read();
fo(i,1,n) p[i]=read();
h1=h2=1;t1=t2=0;
fo(i,1,k-1) push(i);
int ans=0;bool fir=1;
fo(i,k,n) {
push(i);pop(i);
Mx[i]=p[mx[h1]];
Mn[i]=p[mn[h2]];
if (i>k&&Mx[i]==p[i]&&Mn[i-1]==p[i-k]) continue;
if (t2-h2+1==k) {ans+=fir;fir=0;continue;}
ans++;
}
printf("%dn",ans);
return 0;
}
LCMs
这种数论题被做烂了好吧
令
C
[
i
]
=
∑
[
a
[
j
]
=
=
i
]
,
M
=
m
a
x
(
a
[
i
]
)
C[i]=sum [a[j]==i],M=max(a[i])
C[i]=∑[a[j]==i],M=max(a[i])，我们可以算
∑
i
=
1
M
∑
j
=
1
M
[
i
,
j
]
C
[
i
]
C
[
j
]
sum_{i=1}^{M}sum_{j=1}^{M}[i,j]C[i]C[j]
∑i=1M∑j=1M[i,j]C[i]C[j]然后减去
∑
a
[
i
]
sum a[i]
∑a[i]再除以2就是答案
里面那个东西直接反演即可
省略推导过程，答案是
∑
d
=
1
M
1
d
∑
i
=
1
⌊
M
d
⌋
μ
(
i
)
(
∑
j
=
1
⌊
M
i
d
⌋
(
i
j
d
C
[
i
j
d
]
)
)
2
sum_{d=1}^{M}{1over d}sum_{i=1}^{lfloor{Mover d}rfloor}mu(i)(sum_{j=1}^{lfloor{Mover id}rfloor}(ijdC[ijd]))^2
d=1∑Md1i=1∑⌊dM⌋μ(i)(j=1∑⌊idM⌋(ijdC[ijd]))2
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
int read() {
char ch;
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
int x=ch-'0';
for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x;
}
const int N=1e6+5,Mo=998244353,iv=Mo+1>>1;
int n,m,c[N],g[N],inv[N],p[N],mu[N];
bool vis[N];
void pre(int N) {
mu[1]=1;
fo(i,2,N) {
if (!vis[i]) p[++p[0]]=i,mu[i]=-1;
fo(j,1,p[0]) {
int k=i*p[j];if (k>N) break;
vis[k]=1;if (!(i%p[j])) break;
mu[k]=-mu[i];
}
}
}
int main() {
n=read();
fo(i,1,n) {
int x=read();
c[x]++;m=max(m,x);
}
pre(m);
fo(i,1,m) fo(j,1,m/i) (g[i]+=(ll)j*c[i*j]%Mo*i%Mo)%=Mo;
inv[0]=inv[1]=1;fo(i,2,m) inv[i]=(ll)(Mo-Mo/i)*inv[Mo%i]%Mo;
int ans=0;
fo(i,1,m) {
int ret=0;
fo(j,1,m/i) (ret+=(ll)mu[j]*g[i*j]*g[i*j]%Mo)%=Mo;
(ans+=(ll)ret*inv[i]%Mo)%=Mo;
}
fo(i,1,m) (ans-=(ll)c[i]*i%Mo)%=Mo;
ans=(ll)ans*iv%Mo;
printf("%dn",(ans+Mo)%Mo);
return 0;
}
Unique Path
考虑把所有0限制缩起来，每个连通块都是一棵树
如果有一个1限制连接了同一棵树是No
否则每棵树只能选一个点和外界相连(选两个点就形成环，环上的0不满足)
设连通块数为cnt，为了保证联通我们最少有cnt条边连成一个环，最多有
(
c
n
t
2
)
binom{cnt}{2}
(2cnt)条边连成一个完全图
注意特判cnt=1和cnt=2的情况
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
using namespace std;
typedef long long ll;
int read() {
char ch;
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
int x=ch-'0';
for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x;
}
const int N=1e5+5;
int n,m,cnt,q,k,a[N],b[N],c[N],fa[N];
int get(int x) {return fa[x]?fa[x]=get(fa[x]):x;}
void No() {puts("No");exit(0);}
int main() {
n=cnt=read();m=read();q=read();
fo(i,1,q) a[i]=read()+1,b[i]=read()+1,c[i]=read();
if (m==n-1) {
fo(i,1,q) if (c[i]) No();
puts("Yes");
return 0;
}
fo(i,1,q)
if (!c[i]) {
int x=get(a[i]),y=get(b[i]);
if (x==y) continue;
fa[y]=x;cnt--;k++;
}
fo(i,1,q)
if (c[i]) {
int x=get(a[i]),y=get(b[i]);
if (x==y) No();
}
if (cnt==2) {
fo(i,1,q) if (c[i]) No();
return 0;
}
if (m<k+cnt||m>k+(ll)cnt*(cnt-1)/2) No();
puts("Yes");
return 0;
}
Gachapon
大概和这题很像
考虑枚举最后选到的数i，考虑选择序列，最后一个是i，前面的其他数j都会出现至少b[j]次，i会出现b[i]-1次
考虑EGF，令
G
k
(
n
)
=
∑
i
=
0
n
(
a
[
k
]
s
x
)
i
i
!
G_k(n)=sum_{i=0}^{n}{({a[k]over s}x)^iover i!}
Gk(n)=∑i=0ni!(sa[k]x)i
那么答案序列的EGF就是
∏
k
!
=
i
(
e
a
[
k
]
s
x
−
G
k
(
b
[
k
]
−
1
)
)
∗
x
b
[
i
]
−
1
b
[
i
]
!
prod_{k!=i}(e^{{a[k]over s}x}-G_k(b[k]-1))*{x^{b[i]-1}over b[i]!}
∏k!=i(esa[k]x−Gk(b[k]−1))∗b[i]!xb[i]−1
把上式展开，考虑其中
e
p
x
x
t
e^{px}x^t
epxxt对答案的贡献，即
∑
i
≥
0
x
t
+
i
p
i
i
!
sum_{ige 0}{x^{t+i}p^iover i!}
∑i≥0i!xt+ipi
因为考虑的是最后一位前面的序列，步数其实是i+t+1，所以贡献为
∑
i
≥
0
p
i
(
t
+
i
+
1
)
!
i
!
sum_{ige 0}p^i{(t+i+1)!over i!}
∑i≥0pii!(t+i+1)!
通过一些化简可以发现上式=
(
1
1
−
p
)
t
+
2
(
t
+
1
)
!
({1over 1-p})^{t+2}(t+1)!
(1−p1)t+2(t+1)!
至于上式的展开可以先求出
∏
(
e
a
[
k
]
s
x
−
G
k
(
b
[
k
]
−
1
)
)
prod(e^{{a[k]over s}x}-G_k(b[k]-1))
∏(esa[k]x−Gk(b[k]−1))，每次除掉一个式子
复杂度
O
(
∑
a
(
∑
b
)
2
)
O(sum a(sum b)^2)
O(∑a(∑b)2)
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=405,Mo=998244353;
int pwr(int x,int y) {
int z=1;
for(;y;y>>=1,x=(ll)x*x%Mo)
if (y&1) z=(ll)z*x%Mo;
return z;
}
void inc(int &x,int y) {x=x+y>=Mo?x+y-Mo:x+y;}
int n,a[N],b[N],fac[N],pw[N][N],inv[N],iv,sa,sb;
int f[N][N],g[N][N],c[N][N];
int main() {
scanf("%d",&n);
fo(i,1,n) scanf("%d%d",&a[i],&b[i]),sa+=a[i],sb+=b[i];
fac[0]=1;fo(i,1,sb) fac[i]=(ll)fac[i-1]*i%Mo;
inv[sb]=pwr(fac[sb],Mo-2);fd(i,sb-1,0) inv[i]=(ll)inv[i+1]*(i+1)%Mo;
iv=pwr(sa,Mo-2);
fo(i,1,n) {
pw[i][0]=1;pw[i][1]=(ll)a[i]*iv%Mo;
fo(j,2,b[i]) pw[i][j]=(ll)pw[i][j-1]*pw[i][1]%Mo;
}
f[0][0]=1;sa=sb=0;
fo(i,1,n) {
sb+=b[i]-1;sa+=a[i];
fd(s,sa,0)
fd(t,sb,0) {
f[s][t]=Mo-f[s][t];
fo(k,1,b[i]-1) if (t>=k) inc(f[s][t],Mo-(ll)f[s][t-k]*pw[i][k]%Mo*inv[k]%Mo);
if (s>=a[i]) inc(f[s][t],f[s-a[i]][t]);
}
}
fo(s,0,sa) fo(t,0,sb) c[s][t]=pwr((ll)sa*pwr(sa-s,Mo-2)%Mo,t+2);
int ans=0;
fo(i,1,n) {
fo(s,0,sa-a[i]) fo(t,0,sb-b[i]+1) g[s][t]=f[s][t];
fo(s,0,sa-a[i])
fo(t,0,sb-b[i]+1) {
if (s>=a[i]) inc(g[s][t],Mo-g[s-a[i]][t]);
fo(k,1,b[i]-1) if (t>=k) inc(g[s][t],(ll)g[s][t-k]*pw[i][k]%Mo*inv[k]%Mo);
g[s][t]=Mo-g[s][t];
}
int ret=0;
fo(s,0,sa-a[i])
fo(t,0,sb-b[i]+1)
(ret+=(ll)g[s][t]*c[s][t+b[i]-1]%Mo*fac[t+b[i]]%Mo)%=Mo;
(ans+=(ll)ret*pw[i][b[i]]%Mo*inv[b[i]-1]%Mo)%=Mo;
}
printf("%dn",ans);
return 0;
}
Two Permutations
考虑i向p[i]连边，形成了许多环
由于a也是一个排列，每个环要么全部a[i]=i，要么全部a[i]=p[i]
b同理，也就是说每个环有两种取值，每个点根据两种取值的4种情况会有不同的贡献
直接二元关系建图跑最小割
把重边缩在一起效率会大大增加
Code
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
using namespace std;
int read() {
char ch;
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
int x=ch-'0';
for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x;
}
const int N=2e5+5,inf=0x7fffffff;
map<int,int> e[N];
typedef map<int,int> :: iterator it;
int t[N<<1],nxt[N<<1],f[N<<1],lst[N],l;
void add(int x,int y,int z) {
t[++l]=y;f[l]=z;nxt[l]=lst[x];lst[x]=l;
t[++l]=x;f[l]=0;nxt[l]=lst[y];lst[y]=l;
}
int n,p[N],q[N],a[N],b[N],id,S,T;
int d[N],dis[N];
bool bfs() {
fo(i,S,T) dis[i]=0;dis[S]=1;
int i=0,j=1;d[1]=S;
while (i<j) {
rep(k,d[++i])
if (f[k]&&!dis[t[k]]) {
dis[t[k]]=dis[d[i]]+1;
d[++j]=t[k];
}
}
return dis[T];
}
int dinic(int x,int y) {
if (x==T) return y;
int now=0;
rep(i,x)
if (f[i]&&dis[t[i]]==dis[x]+1) {
int k=dinic(t[i],min(y,f[i]));
f[i]-=k;f[i^1]+=k;
y-=k;now+=k;
if (!y) break;
}
if (!now) dis[x]=-1;
return now;
}
int main() {
n=read();l=1;
fo(i,1,n) p[i]=read()+1;
fo(i,1,n) q[i]=read()+1;
fo(i,1,n)
if (!a[i]) {
++id;int x=i;
do {a[x]=id;x=p[x];} while (x!=i);
}
fo(i,1,n)
if (!b[i]) {
++id;int x=i;
do {b[x]=id;x=q[x];} while (x!=i);
}
S=0;T=id+1;
int ans=0;
fo(i,1,n)
if (p[i]==q[i]) {
if (p[i]==i) continue;ans++;
e[a[i]][b[i]]++;e[b[i]][a[i]]++;
} else {
ans++;
if (i==p[i]) e[S][b[i]]++;
else if (i==q[i]) e[a[i]][T]++;
else e[a[i]][b[i]]++;
}
fo(x,S,T)
for(it i=e[x].begin();i!=e[x].end();i++) {
int y=i->first,z=i->second;
add(x,y,z);
}
while (bfs()) ans-=dinic(S,inf);
printf("%dn",ans);
return 0;
}
最后
以上就是要减肥飞鸟为你收集整理的[Atcoder Grand Contest 038]简要题解？的全部内容，希望文章能够帮你解决[Atcoder Grand Contest 038]简要题解？所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![ug05x10android,[Updated] Cash Shop Update for July 5](/uploads/reation/bcimg6.png)
![[Atcoder Grand Contest 038]简要题解？](/uploads/reation/bcimg9.png)
发表评论 取消回复