| Solved | A | B | C | D | E |
|---|---|---|---|---|---|
| 5/5 | O | Ø | Ø | O | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A HDU 5943 - Kingdom of Obsession
题目描述
一个数可以对应他的所有因数，问$[1,n]$能不能被$[s+1,s+n]$一一对应。
解题思路
显然，一个区间内若有两个质数则必然不可行，猜测差别$400$以上不可行，剩余的跑匈牙利。
AC代码
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
struct Edge{
int e,n;
}e[N<<1];
int hd[N],cnt,vis[N],mt[N];
void add(int a,int b){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
}
int n,s;
int dfs(int p,int t){
int i;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(vis[q]!=t){
vis[q]=t;
if(!mt[q]||dfs(mt[q],t))return mt[q]=p;
}
}
return 0;
}
int maxmt(){
int i;
for(i=1;i<=n;i++)if(!dfs(i,i))return 0;
return 1;
}
int main(){
int i,j,k,t;
scanf("%d",&t);
for(k=1;k<=t;k++){
scanf("%d%d",&n,&s);
printf("Case #%d: ",k);
if(s<n)std::swap(s,n);
if(n>400){
printf("No\n");
continue;
}
memset(hd,0,sizeof(hd));cnt=0;
memset(vis,0,sizeof(vis));
memset(mt,0,sizeof(mt));
for(i=s+1;i<=s+n;i++)
for(j=1;j<=n;j++)
if(i%j==0)add(i-s,j);
printf("%s\n",maxmt()?"Yes":"No");
}
return 0;
}
B HDU 6305 - RMQ Similar Sequence
题目描述
定义两个序列相似，当且仅当对于任意一个区间$[l,r]$，其最大数的最左位置相同。
给定一个序列$A$，随机产生一个序列$B$，其中$B$的所有元素都是等概率从$(0,1)$中选取的。如果$AB$相似，则$B$的满意度为$B$中所有数之和，否则$B$的满意度为$0$。求$B$的满意度期望。
解题思路
笛卡尔树的同构，$[0,1]$之中$n$个数总和期望为$\frac n2$，各个数两两不同的概率为$1$（即不需考虑两个数相同的情况）。树同构的概率为$\prod\frac1{siz[i]}$（证明：用拓扑序表示树，则某一个点$i$作为根的时候位置必然在其所有子树点的后面，则对于该点而言，满足这个条件只需考虑这$siz[i]$个节点的顺序，故满足条件的概率为$\frac 1{siz[i]}$），于是答案为$\frac n2\prod\frac1{siz[i]}$。
AC代码
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
long long inv[N]={0,1},w=1000000007,ans;
int a[N],sta[N],top,siz[N],l[N],r[N];
void dfs(int p){
if(!p)return;
siz[p]=1;
dfs(l[p]);siz[p]+=siz[l[p]];
dfs(r[p]);siz[p]+=siz[r[p]];
ans=ans*inv[siz[p]]%w;
}
int main(){
int i,n,t;
for(i=2;i<N;i++)inv[i]=inv[w%i]*(w-w/i)%w;
scanf("%d",&t);
while(t--){
top=0;
scanf("%d",&n);
ans=n*inv[2]%w;
for(i=1;i<=n;i++)scanf("%d",&a[i]),l[i]=r[i]=0;
for(i=1;i<=n;i++){
while(top&&a[i]>a[sta[top]])l[i]=sta[top--];
if(top)r[sta[top]]=i;
sta[++top]=i;
}
dfs(sta[1]);
printf("%lld\n",ans);
}
return 0;
}
C ZOJ 3656 - Bit Magic
题目描述
给定一个由$a[n]$经过或、与、异或运算得到的矩阵$b[n][n]$，问能不能够找到$a[n]$的解。
解题思路
用并查集模拟或和与的填数以及异或的两元素关系。每个数拆成$32$个$bit$，并分成两半，一半是该数需要与某个数相同，另一半是该数不可与某个数相同。
听说能用$2-sat$做，看来还是要学习一个。
AC代码
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
int b[N][N],n,f[M];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void merge(int x,int p){
int a=find(x),b=find(p);
f[a]=f[b]=f[x]=f[p]=std::min(a,b);
}
int solve(){
int i,j,k;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++)if(b[i][j]!=b[j][i])return 0;
if(b[i][i])return 0;
}
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
for(k=0;k<32;k++){
if(i%2&&j%2){
if(!(b[i][j]&(1<<k))){
int p=(i+1)*32+k,q=(j+1)*32+k;
if(find(p)==find(1)||find(q)==find(1)||find(p)==find(q+32*n))return 0;
merge(p,0);merge(q,0);
merge(p+32*n,1);merge(q+32*n,1);
}
}else if(!(i%2)&&!(j%2)){
if(b[i][j]&(1<<k)){
int p=(i+1)*32+k,q=(j+1)*32+k;
if(find(p)==find(0)||find(q)==find(0)||find(p)==find(q+32*n))return 0;
merge(p,1);merge(q,1);
merge(p+32*n,0);merge(q+32*n,0);
}
}else{
if(b[i][j]&(1<<k)){
int p=(i+1)*32+k,q=(j+1)*32+k;
if(find(p)==find(q))return 0;
merge(p,q+32*n);merge(q,p+32*n);
}else{
int p=(i+1)*32+k,q=(j+1)*32+k;
if(find(p)==find(q+32*n))return 0;
merge(p,q);merge(q+32*n,p+32*n);
}
}
}
}
}
return 1;
}
int main(){
int i,j;
while(~scanf("%d",&n)){
for(i=0;i<=32*(n+2)*2;i++)f[i]=i;
for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&b[i][j]);
printf("%s\n",solve()?"YES":"NO");
}
return 0;
}
D ZJOI2008 - 骑士
题目描述
每个人都对应有一个不能同时上台的人，并有一个实力值，问选择出的人的实力值之和最大是多少。
解题思路
基环树，也可找到环之后切开分两段$DP$。
AC代码-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
using namespace std;
typedef long long ll;
struct Edge{
int end,near;
}e[N<<1];
int head[N],cnt,vis[N],fa[N];
void add(int a,int b){
e[++cnt].end=b;e[cnt].near=head[a];head[a]=cnt;
}
ll str[N],ans,f[2][N];
int rt;
void dp(int x){
int i,q;
if(!vis[x])vis[x]=1;
f[0][x]=0;
f[1][x]=str[x];
for(i=head[x];i;i=e[i].near){
q=e[i].end;
if(q!=rt){
dp(q);
f[1][x]+=f[0][q];
f[0][x]+=max(f[1][q],f[0][q]);
}
}
if(x==rt)f[1][x]=0;
}
void cir(int x){
ll t;
vis[x]=1;
rt=x;
while(!vis[fa[rt]]){
rt=fa[rt];
vis[rt]=1;
}
dp(rt);t=f[0][rt];
rt=fa[rt];
dp(rt);ans+=max(t,f[0][rt]);
}
int main(){
int i,n,y;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld%d",&str[i],&y);
add(y,i);fa[i]=y;
}
for(i=1;i<=n;i++)if(!vis[i])cir(i);
printf("%lld",ans);
return 0;
}
AC代码-2
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
typedef long long ll;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a>b?b:a;}
struct Edge{
int end,near;
}e[N<<1];
int head[N],cnt;
void add(int a,int b){
e[++cnt].end=b;e[cnt].near=head[a];head[a]=cnt;
}
ll str[N],f[2][N];
int rt;
void dp(int x,int fa){
int i,q;
f[0][x]=0;
f[1][x]=str[x];
for(i=head[x];i;i=e[i].near){
q=e[i].end;
if(q!=fa){
dp(q,x);
f[1][x]+=f[0][q];
f[0][x]+=max(f[1][q],f[0][q]);
}
}
if(x==rt)f[1][x]=0;
}
int fla[N],A[N],B[N],tot;
int main(){
int i,n,y;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld%d",&str[i],&y);
if(fla[i]&&fla[y]){
A[++tot]=i;B[tot]=y;continue;
}
fla[i]=fla[y]=1;
add(y,i);add(i,y);
}
ll ans=0;
for(i=1;i<=tot;i++){
dp(A[i],A[i]);ll t=f[0][A[i]];
dp(B[i],B[i]);
ans+=max(t,f[0][B[i]]);
}
printf("%lld",ans);
return 0;
}
E HYSBZ 4774 - 修路
题目描述
给一个图，要求选择某些边，使得前$d$个点和后$d$个点必须分别相连通，问最小权值和。
解题思路
设$f[i][j]$表示当前斯坦纳树的根为$i$，指定集合中，包含点的集合表示为$j$的生成树最小权值。
则转移方程为：$f[i][j]=min(f[i][S]+f[i][S \oplus j])$（分成两个以$i$为根的斯坦纳树，点集状态分别为$S$和$j\oplus S$），$f[i][j]=min(f[k][j]+len[i][k])$（换根，根再向$i$连边），这一步看起来很像最短路，可以用最短路算法算出。
AC代码
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
using namespace std;
struct Edge{
int e,n,l;
}e[N<<1];
int hd[N],cnt,n,m,d;
void add(int a,int b,int l){
e[++cnt].e=b;e[cnt].n=hd[a];e[cnt].l=l;hd[a]=cnt;
}
int f[N][M],g[M],vis[N];
queue<int>Q;
void spfa(int s){
while(!Q.empty()){
int p=Q.front(),i;Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(f[q][s]>f[p][s]+e[i].l){
f[q][s]=f[p][s]+e[i].l;
if(!vis[q])Q.push(q),vis[q]=1;
}
}
vis[p]=0;
}
}
int main(){
int i,j,k,s,u,v,w;
scanf("%d%d%d",&n,&m,&d);s=(1<<(d<<1));
for(i=0;i<m;i++)
scanf("%d%d%d",&u,&v,&w),
add(u,v,w),add(v,u,w);
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
for(i=1;i<=d;i++)
f[i][1<<i-1]=0,f[n-i+1][1<<d+i-1]=0;
for(j=0;j<s;j++){
for(i=1;i<=n;i++){
for(k=j&(j-1);k;k=(k-1)&j)
f[i][j]=min(f[i][j],f[i][k]+f[i][j^k]);
if(f[i][j]<1e9)Q.push(i),vis[i]=1;
}
spfa(j);
for(i=1;i<=n;i++)g[j]=min(g[j],f[i][j]);
}
for(j=0;j<s;j++)
for(k=j&(j-1);k;k=(k-1)&j)
if((k&((1<<d)-1))==(k>>d)&&((j^k)&((1<<d)-1))==((j^k)>>d))
g[j]=min(g[j],g[k]+g[j^k]);
printf("%d\n",g[s-1]<1e9?g[s-1]:-1);
return 0;
}