15.10.18【并查集、dp】

  1. 1 黑魔法师之门(magician)
  2. 2 守卫者的挑战(guard)
  3. 3 终极武器(laser)

100+0+40

1 黑魔法师之门(magician)

【题目描述】
applepi 被囚禁的地点只有一扇门,当地人称它为“黑魔法师之门”。这扇门上画着一张无向无权图,而打开这扇门的密码就是图中每个点的度数大于零且都是偶数的子图的个数对1000000009 取模的值。此处子图(V, E) 定义为:点集V 和边集E 都是原图的任意子集,其中E 中的边的端点都在V 中。
但是Vani 认为这样的密码过于简单,因此门上的图是动态的。起初图中只有N 个顶点而没有边。Vani 建造的门控系统共操作M 次,每次往图中添加一条边。你必须在每次操作后都填写正确的密码,才能够打开黑魔法师的牢狱,去拯救伟大的领袖applepi。
【输入格式】
第一行包含两个整数N 和M。
接下来M 行,每行两个整数A 和B,代表门控系统添加了一条无向边(A,B)。
【输出格式】
输出一共M 行,表示每次操作后的密码。
【样例输入】
4 8
3 1
3 2
2 1
2 1
1 3
1 4
2 4
2 3
【样例输出】
0
0
1
3
7
7
15
31

表示我是找规律的,其实我并不知道这题是干嘛的。。。

solution: 实际上每次操作后的答案就是 2^( 图中 “元”环的个数 )。
元环的意思:如右图所示,(1 -2-3-4-1) 和 (3 -4-5-3) 是元环, 1-2-3-5-4-1不是,因为它可以看做由上述的两个环合成。
因为一个环里每点的度数都是大于零偶,我们可以这样来构造答案:每个环有选和不选两种选择,如果选了该环,那么环上所有边的“选择次数”+1。最后取所有“选择次数”为奇的边构成一个边集,就是一个答案。可以证明这样构造出来的解不重复且涵盖了所有情况因此答案就是2^(图中“元”环的个数 )。实现方法非常简单,只需要一个并查集即可。
具体实现方法:
并查集维护连通性,初始化 ans=1。
加入一条边 (x,y)时,如果 x和 y在同一集合内,ans*=2。
每次询问输出 ans-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
#include<cstdio>
using namespace std;
int n,m,x,y,f1,f2,mod=1000000009,fa[200001];
long long ans;
int father(int x)
{
if(fa[x]==x) return x;
else return fa[x]=father(fa[x]);
}
int main()
{
freopen("magician.in","r",stdin);
freopen("magician.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
f1=father(x);f2=father(y);
if(f1==f2) ans=(ans*2+1)%mod;
else fa[f1]=f2;
printf("%lld\n",ans);
}
}

2 守卫者的挑战(guard)

【题目描述】 打开了黑魔法师 Vani 的大门,队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的监狱的所在地。突然,眼前一道亮光闪过。“我,Nizem,是黑魔法圣殿的守卫者。如果你 能通过我的挑战,那么你可以带走黑魔法圣殿的地图……”瞬间,队员们被传送到了一个擂台上,最初身边有一个容量为 K 的包包。
擂台赛一共有 N 项挑战,各项挑战依次进行。第i 项挑战有一个属性ai ,如果ai≥0,表示这次挑战成功后可以再获得一个容量为ai 的包包;如果ai=-1,则表示这次挑战成功后可以得到一个大小为 1 的地图残片。地图残片必须装在包包里才能带出擂台,包包没有 必要全部装满,但是队员们必须把获得的所有的地图残片都带走(没有得到的不用考虑,只需要完成所有 N 项挑战后背包容量足够容纳地图残片即可),才能拼出完整的地图。并且他 们至少要挑战成功 L 次才能离开擂台。
队员们一筹莫展之时,善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率,其中第i 项挑战成功的概率为 pi。现在,请你帮忙预测一下,队员们能够带上他们获得的地图残片离开擂台的概率。
【输入格式】
第一行三个整数 N , L , K 。
第二行 N 个实数,第i 个实数 pi 表示第i 项挑战成功的百分比。
第三行 N 个整数,第i 个整数ai 表示第i 项挑战的属性值.
【输出格式】
一个整数,表示所求概率,四舍五入保留 6 位小数。

dp
f[i][j][k]表示挑战到了第i次,赢了j次,背包容量为k的概率
因为结果与顺序无关,也就是只要最后能装下就行,所以k可以是负的
当k>n的范围时无意义,所以-200≤k≤200。
最后把能成功的概率加起来就好了
注意一个问题:我开了f[201][201][410],结果爆了128M,linux下运行时错误,改成401就行了QAQ,下次一定要算一下内存

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
#include<cstdio>
using namespace std;
int n,L,K,a[201],b[201];
double ans,f[201][201][401];
int main()
{
freopen("guard.in","r",stdin);
freopen("guard.out","w",stdout);
scanf("%d%d%d",&n,&L,&K);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
f[0][0][200+K]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<=400;k++)
{
f[i][j][k]=f[i-1][j][k]*(100-a[i])/100;
if(k>=b[i]&&j>0) f[i][j][k]+=f[i-1][j-1][k-b[i]]*a[i]/100;
}
for(int i=L;i<=n;i++)
for(int k=200;k<=400;k++)
ans+=f[n][i][k];
printf("%.6lf",ans);
}

3 终极武器(laser)

【题目描述】 经过一番周折,精英队伍的队员们终于来到了关押applepi的牢狱面前。心中神一般的领袖applepi就在眼前,队员们都不由自主地跪烂膝盖……不过令他们沮丧的是,牢狱的大锁没有钥匙孔,黑魔法师Vani根本就没有指望它再被打开。幸好队员们携带了新研制的终极武器——k型氙激光器(Xenon Laser - k,代号XLk),可以用来破拆这把锁。不过作为一道终极武器,它的启用规则异常严格。
Xenon Laser - k上共有N个波段能够发射激光,每个波段可以用一个闭区间[ai,bi]来表示,其中ai,bi为正整数,bi-1<ai≤bi。对于两个数字p和q,如果对于这N个波段内的任意一个整数num,把它在十进制表示下的后k位中某一位上的p换成q(或者q换成p),都满足得到的整数仍然在这N个波段内,那么称在该激光器中,数字p和q是k等价的。我们称两两之间k等价的数字组成一个k等价类。
激光器附带了9个发射匣,代表1~9这9个数字。只有把同一个等价类的数字对应的发射匣安置在一排上,Xenon Laser - k才能够启动。给定个波段,现在就请你求出1~9这9个数字分成了哪些等价类,并且每行输出一个等价类。
本题描述比较抽象,请参考样例解释。
【输入描述】
第一行两个整数N,k。
接下来N行每行两个整数ai,bi。ai,bi为正整数,满足bi-1<ai≤bi。
【输出描述】
每行一个k等价类,各行之内都按照数字从小到大排序,数字中间没有空格,行与行之间按照等价类中最小的数字从小到大排序。

题解:(我真的没有看懂)
  读入所有区间之后,转化为前闭后开形式即 [L,R),存入数组……然后我们拿出其中的一个区间来考虑。。。
  单独对于这个区间,我们考虑第k位上的数字变化。如果我们知道比第k位低的位上都是都是什么数字的话,显然可以很容易地判断出这一位上的数字1-9可以分成哪两组等价类……
  比如区间[2012,6278),考虑十位。如果规定各位数字是0,那么[2020,6280)中的数在区间内,剩下的在区间外,即十位上[2,8)是一个等价类,其余数字是另一个。如果规定个位数字是2,那么十位上是[1,8),如果个位数字是8,那么十位上是[1,7)。
  可以发现最初第k位上的数字的其中一组是[L/10^k %10 +1, R/10^k %10 +1),当后面的位经过L%10k这个数的时候区间左端减一,经过R%10k这个数的时候区间右端减一。
  因此我们可以依次处理每一位,对于每一位上,把读入的n个区间中,所有这样引起该位数字区间变化的数值记录下来,排序离散化之后再依次处理。可以发现引起变化的位置只可能是这n个区间的左右端点,并且变化规律就是上面一段所说的。
  大概梳理一下整个算法过程:
    初始化:建一个9*9的完全图的邻接矩阵。
    特殊处理个位情况。
    主要环节:
      1.枚举每一位,设当前枚举到第k位。
      2.按照上面所述的方法计算引起变化的位置,排序,离散化,离散后的每个位置开一个1*9的数组记录哪些数字在数字区间内,哪些在外面。
      3.首先令后k-1位都是0,计算各个数字区间(1*9的数组)的初始值。
      4.依次循环每个变化位置,对应的1*9的数组里进行加减。
      5.每次变化后把对应的1*9数组的信息反映到9*9的矩阵里,不同集合内的边断掉。
    输出答案。
  该算法综合运用到了邻接矩阵、排序离散化、Hash等多项NOIP中进行数据统计处理的知识,可以处理100%的数据,得到满分。
详见

标程:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
struct rec{
__int64 low; int dat,side;
rec(void){}
rec(__int64 a,int b,int c):low(a),dat(b),side(c){}
}c[20010];
pair<__int64,__int64> a[10010],b[10010];
#define x first
#define y second
map<__int64,int> hash;
int f[30010][10],n,k,m,tot,link,i,j;
bool g[10][10],v[10];

inline bool operator <(rec a,rec b) {return a.low<b.low;}
inline void change(rec a) {a.side==1?b[a.dat].x--:b[a.dat].y--;}
inline void crash(int v[10])
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(v[i]&&!v[j]&&g[i][j]) g[i][j]=g[j][i]=0,link-=2;
}

void calc()
{
int i,j,l,r;
__int64 now,L,R;
for(now=-1,i=1;i<=n;i++,now=R)
{
l=a[i].x%10,r=a[i].y%10;
L=a[i].x/10,R=a[i].y/10;
if(L!=now&&now>0) crash(f[0]),memset(f[0],0,sizeof(f[0]));
if(L!=R)
{
for(j=l;j<=9;j++) f[0][j]++;
crash(f[0]);
memset(f[0],0,sizeof(f[0]));
for(j=1;j<r;j++) f[0][j]++;
}
else for(j=l;j<r;j++) f[0][j]++;
}
crash(f[0]);
}

bool solve(int k)
{
__int64 l,r,L,R,pow=1,now;
int i,j,p,q,num=1;
memset(f,0,sizeof(f));
for(m=tot=i=0;i<k;i++) pow*=10;
for(i=1;i<=n;i++)
{
L=a[i].x/pow,R=a[i].y/pow;
if(!L&&!R) continue;
l=a[i].x%pow,r=a[i].y%pow;
b[++m]=make_pair(L+1,R+1);
c[++tot]=rec(l,m,1),c[++tot]=rec(r,m,2);
}
if(!m) return 0;
hash.clear();
sort(c+1,c+tot+1);
for(p=1;p<=tot&&!c[p].low;p++) change(c[p]);
for(i=1,now=-1;i<=m;i++,now=R)
{
l=b[i].x%10,r=b[i].y%10;
L=b[i].x/10,R=b[i].y/10;
if(L!=now&&now>0) hash[now]=num++;
if(L!=R)
{
for(j=l;j<=9;j++) f[num][j]++;
hash[L]=num++;
for(j=1;j<r;j++) f[num][j]++;
}
else for(j=l;j<r;j++) f[num][j]++;
}
hash[now]=num++;
for(i=1;i<num;i++) crash(f[i]);
for(;p<=tot;p=q)
{
for(q=p;q<=tot&&c[q].low==c[p].low;q++)
{
change(c[q]);
now=c[q].side==1?b[c[q].dat].x:b[c[q].dat].y;
k=now%10,now/=10;
if(!hash[now]) hash[now]=num++;
now=hash[now];
if(c[q].side==1) f[now][k]++; else f[now][k]--;
}
for(i=1;i<num;i++) crash(f[i]);
}
return 1;
}

int main()
{
freopen("laser.in","r",stdin);
freopen("laser.out","w",stdout);
cin>>n>>k;
for(i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].y++;
memset(g,1,sizeof(g));
link=72;
calc();
for(i=1;i<k&&solve(i)&&link;i++);
for(i=1;i<=9;i++)
if(!v[i])
{
cout<<i,v[i]=1;
for(j=1;j<=9;j++)
if(!v[j]&&g[i][j]) cout<<j,v[j]=1;
cout<<endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}