T1.Adore
描述:
原题：
小 w 偶然间⻅到了一个 DAG。
这个 DAG 有 m 层, 第一层只有一个源点, 最后一层只有一个汇点, 剩下的每一层都有 k 个
节点。
现在小 w 每次可以取反第 i(1 < i < n − 1) 层和第 i + 1 层之间的连边。也就是把原本从
(i, k 1 ) 连到 (i + 1, k 2 ) 的边, 变成从 (i, k 2 ) 连到 (i + 1, k 1 )。
请问他有多少种取反的方案, 把从源点到汇点的路径数变成偶数条?
答案对 998244353 取模。
输入格式：
一行两个整数 m, k。
接下来 m − 1 行, 第一行和最后一行有 k 个整数 0 或 1, 剩下每行有 k 2 个整数 0 或 1, 第
(j − 1) × k + t 个整数表示 (i, j) 到 (i + 1, t) 有没有边。
输出格式：
一行一个整数表示答案。
数据规模与约定：
20% 的数据满足 $m ≤ 10, k ≤ 2$
40% 的数据满足 $m ≤ 10^3 , k ≤ 2$
60% 的数据满足 $m ≤ 10^3 , k ≤ 5$
100% 的数据满足 $4 ≤ m ≤ 10^4 , k ≤ 10$
一行一个整数表示答案。
思路：
由于每层只有 k(k<=10) 个节点，而且只需要求满足某种奇偶性的解的个数。我们可以用二进制保存每一层的状态。接下来进行状态压缩 DP。
注意以下的问题：
1. 边的表示？
为了达到更高的速度，边可以用邻接矩阵表示，而这个邻接矩阵又是由二进制构成的，因此可以用位运算加速连通性的计算。
比如：
$$
\begin{bmatrix}
1 & 1 & 0\\
0 & 1 & 0\\
1 & 0 & 1
\end{bmatrix}
$$
这个矩阵表示，每一列对应的左侧节点与每一行对应的右侧节点联通，当且仅当这一列这一行的元素为 1。
而每一层的状态我们又可以用一个 k 维向量表示，
比如：
$$
\begin{bmatrix}
1 \\
0 \\
1
\end{bmatrix}
$$
这个向量表示，从起点到这一层的 1,3 个节点有奇数中走法，第 2 个节点有偶数种走法。这样，如果我们将这连个矩阵相乘：
$$
\begin{bmatrix}
1 & 1 & 0\\
0 & 1 & 0\\
1 & 0 & 1
\end{bmatrix} \times
\begin{bmatrix}
1 \\
0 \\
1
\end{bmatrix} =
\begin{bmatrix}
1 \\
0 \\
2
\end{bmatrix} =
\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix}(mod2)
$$
然而，由于我们用一个 int 型数就可以表示矩阵的一行，我们就可以在 O(k) 的时间复杂度内完成这个矩阵乘法。具体的实现是：将矩阵的每个行向量与当前层的 k 维向量按位与，取答案中 1 的个数。很快，对不对？不够快。
注意到上面的式子中出现了取 1 的个数操作。如果这个操作仅仅使用 x=x&(x-1) 这样的操作来读取的话，恭喜你，时间复杂度不幸地变成了 $O(k^2)$。如何才能更快求 1 的个数呢？我们以空间换时间，结合本博客中另一篇有关位运算的“ 位运算那些令人咋舌的操作” 文章，大家一定可以找到更快速的方法。我最终采用的算法时间复杂度约为 $O(mk2^k)$
2. 思考的复杂度
由于这道题的内容及我所选择的做法，我的程序频繁地涉及位运算相关的代码。而位运算代码的编写由略为困难。如何在代码执行高效的基础上减少位运算的思考复杂度，已知是一个值得权衡的问题。
3. 时间的复杂度
使用的第一个问题所提到的架构，时间复杂度已经得到了保证。谁知当我采用 x=x&(x-1) 取得答案中 1 的个数时，却发生了 60 分 TLE 惨案…。在考场上我最初的邻接矩阵甚至没有用到位运算，速度更慢，计算时间复杂度为 $O(mk^22^k)$，有对于后 40 分有危险，为了确保万无一失我才改成了位运算，谁知…. 还是 TLE，而且 T 了 60 分。数据实在是没有梯度，这种出题人该裱该表。
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 50005
#define mod 998244353
#define mov(x) ((ui)1<<(x))
#define lowbit(x) ((x)&(-(x)))
#define reg register
using namespace std;
typedef unsigned int ui;
ui f[MX][1<<11];
ui edg[MX][12];
ui rev[MX][12];
ui noo[1<<16];
ui m,k;
void outb(ui x)
{
for(int i=0;i<=5;i++)cout<<!!(x&mov(i));cout<<endl;
}
ui count1(ui x)
{
ui cnt=0;
while(x)x-=lowbit(x),cnt++;
return cnt;
}
ui count2(int x)
{
return (noo[65535&x]+noo[65535&(x>>16)]);
}
void input()
{
ui t;
scanf("%d%d",&m,&k);
for(ui i=1;i<=k;i++)
{
scanf("%d",&t);
if(t==1)edg[1][0]|=(mov(i-1));
}
for(ui i=2;i<=m-2;i++)
{
for(ui j=1;j<=k;j++)
{
for(ui l=1;l<=k;l++)
{
scanf("%d",&t);
if(t==1)edg[i][l]|=(mov(j-1)),rev[i][j]|=(mov(l-1));
}
}
}
for(ui i=1;i<=k;i++)
{
scanf("%d",&t);
if(t==1)edg[m-1][0]|=(mov(i-1));
}
}
void work()
{
ui nt1,nt2;
f[2][(mov(k)-1)&(edg[1][0])]=1;
for(reg ui i=2;i<=m-2;i++)
{
for(reg ui w=0;w<mov(k);w++)
{
if(f[i][w])
{
nt1=nt2=0;
for(reg ui j=1;j<=k;j++)
{
if(count2(edg[i][j]&w)&1)nt1|=(mov(j-1));
if(count2(rev[i][j]&w)&1)nt2|=(mov(j-1));
}
f[i+1][nt1]+=f[i][w];
f[i+1][nt1]%=mod;
f[i+1][nt2]+=f[i][w];
f[i+1][nt2]%=mod;
}
}
}
ui cnt=0;
for(ui w=0;w<mov(k);w++)
if((count2(w&edg[m-1][0])&1)==0)
cnt+=f[m-1][w],cnt%=mod;
cout<<cnt<<endl;
}
void init()
{
for(int i=0;i<mov(16);i++)noo[i]=count1(i);
}
int main()
{
freopen("adore.in","r",stdin);
freopen("adore.out","w",stdout);
init();
input();
work();
return 0;
}
T2.Confess
描述:
原题：
小 w 隐藏的心绪已经难以再隐藏下去了。
小 w 有 n + 1(保证 n 为偶数) 个心绪, 每个都包含了 [1, 2n] 的一个大小为 n 的子集。
现在他要找到隐藏的任意两个心绪, 使得他们的交大于等于 n/2。
输入格式：
一行一个整数 n。
接下来每行一个⻓度为 k 的字符串, 该字符串是一个 64 进制表示,ASCII 码为 x 的字符代
表着 x − 33, 所有字符在 33 到 33 + 63 之间。
转为二进制表示有 6k 位, 它的前 2n 个字符就是读入的集合, 第 i 位为 1 表示这个集合包
含 i, 为 0 表示不包含。
输出格式：
一行两个不同的整数表示两个集合的编号。
如果无解输出”NO Solution”。
数据规模与约定：
对于 20% 的数据满足 $n ≤ 100$
对于 50% 的数据满足 $n ≤ 1 \times 10^3$
对于 100% 的数据满足 $n ≤ 6 \times 10^3 $
思路:
我首先想到的是随机化算法。因为我只想着去骗分了。后来发现其实这就是正解。为什么随机化算法骗分是可行的呢？我们来考虑任意两个集合的交集大于等于 n/2 的概率：
设这两个集合为 [1,2n] 中的 n 个整数组成的集合，设 P(i) 为它们交集大小为 i 的概率，那么：
$$
P(i)=\frac{C_{2n}^{i}C_{2n-i}^{n-i}C_{n}^{n-i}}{C_{2n}^{n}C_{2n}^{n}}
$$
其中分数线上方第一个 C 表示从 2n 个元素里选出 i 个作为它们的交，后两个表示从剩下的里面选出不重复的 n-i 和 n-i 个分别作为两个集合的元素。而我们要求的是：
$$
P=\sum\limits_{i=n/2}^{n}{P(i)}
$$
随手用计算机一算，这个结果还是蛮大的。
假设，P=0.01(是不是非常小)，那么我们只需要随机选 1000 组集合，它们都没有大于等于 n/2 的交集的概率为 0.00004，显然是符合要求的。因此，我们可以大胆地骗分了。
优化：
对于暴力求交集，我们是可以优化的。我们不需要一个一个元素地比较，而可以保存在二进制数里用位运算求交集 (即按位与)。同时又可以结合“ 位运算那些令人咋舌的操作” 中介绍的方法，快速求交集大小。这种方法在图像处理等现实应用中十分有效，即” 汉明距离” 的快速求法。结合这种优化，我们可以在 1s 内求大约 10 倍于普通做法的交集次数，对大数据范围内的求解帮助还是很大的。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define LEN 62001
#define MX 30001
#define SZ 32
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;
int set[MX][LEN/SZ];
int cno[(1<<8)+1];
int n,num;
inline int count1(int x)
{
int cnt=0;
while(x)x-=lowbit(x),cnt++;
return cnt;
}
inline int count2(int x)
{
return cno[x&(255)]+cno[(x>>8)&255]+cno[(x>>16)&255]+cno[(x>>24)&255];
}
void input()
{
int len=0,t,len2;
char str[MX],str2[MX];
scanf("%d",&n);
for(int i=1;i<=n+1;i++)
{
memset(str2,0,sizeof(str2));
scanf("%s",str);
len=strlen(str),len2=0;
for(int j=0;j<len;j++)
{
t=str[j]-33;
for(int k=0;k<6;k++)str2[len2++]='0'+!!(t&(1<<k));
}
for(int j=0;j<len2;j++)
if(str2[j]>'0')
set[i][j/SZ]|=(1<<(j%SZ));
}
num=len2/SZ;
}
inline int comb(int a,int b)
{
int cnt=0;
for(int i=0;i<=num;i++)
{
cnt+=count2(set[a][i]&set[b][i]);
}
return cnt;
}
inline void test()
{
int T,k1,k2;
while(1)
{
k1=rand()%(n+1)+1;
k2=rand()%(n+1)+1;
while(k1==k2)k2=rand()%(n+1)+1;
if(comb(k1,k2)>=n/2)
{
printf("%d %d\n",k1,k2);
return;
}
}
printf("NO Solution\n");
}
void init()
{
for(int i=0;i<(1<<8);i++)cno[i]=count1(i);
}
int main()
{
freopen("confess.in","r",stdin);
freopen("confess.out","w",stdout);
init();
input();
test();
return 0;
}
T3.Repulsed
描述：
原题
小 w 心里的火焰就要被熄灭了。
简便起⻅, 假设小 w 的内心是一棵 n − 1 条边,n 个节点的树。
现在你要在每个节点里放一些个灭火器, 每个节点可以放任意多个。
接下来每个节点都要被分配给一个至多 k 条边远的灭火器, 每个灭火器最多能分配给 s 个节
点。
至少要多少个灭火器才能让小 w 彻底死心呢?
输入格式
第一行三个整数 n, s, k。
接下来 n − 1 行每行两个整数表示一条边。
输出格式
一行一个整数表示答案
数据规模与约定
对于 20% 的数据满足 $n ≤ 100, k ≤ 2$
对于另外 20% 的数据满足 $k = 1$
对于另外 20% 的数据满足 $s = 1$
对于 100% 的数据满足 $ n ≤ 10^5 , k ≤ 20, s ≤ 10^9 $
思路：
当初没有想出来，也没有时间想了，于是看数据范围骗了 40 分。
实际上的思路是这样的：
设 G(x,i) 表示 x 节点及其子树中还没有被灭的火的个数。
设 F(x,i) 表示 x 节点及其子树中多余的灭火器能灭的火的个数。
策略 1：对于每一个火，我们尽量在靠近树根的地方灭掉。
策略 2：对于每一个 x 及其子树中多余的灭火器和火，我们在两者距离为 k 或 k-1 时让它们相互泯灭。
按照这两个策略，我们就可以快捷地写出代码。。。原来比骗分还简单。
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 100001
#define MK 22
using namespace std;
typedef long long ll;
ll f[MX][MK],g[MX][MK],ans;
int fst[MX],nxt[MX<<1],v[MX<<1],lnum;
int n,s,k;
ll ceil(ll x)
{
return x/s+((x%s)>0);
}
void addeg(int nu,int nv)
{
nxt[++lnum]=fst[nu];
fst[nu]=lnum;
v[lnum]=nv;
}
void input()
{
int a,b;
scanf("%d%d%d",&n,&s,&k);
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
addeg(a,b);
addeg(b,a);
}
}
void dfs(int x,int fa)
{
ll t,num;
for(int i=fst[x];i!=-1;i=nxt[i])
{
if(v[i]==fa)continue;
dfs(v[i],x);
for(int j=0;j<=k-1;j++)
{
f[x][j+1]=min(f[x][j+1]+f[v[i]][j],(ll)n);
g[x][j+1]+=g[v[i]][j];
}
}
g[x][0]=1;
if(g[x][k])
{
t=ceil(g[x][k]);
ans+=t;
f[x][0]=min((ll)n,t*s);
}
for(int i=0;i<=k;i++)
{
t=k-i;
num=min(f[x][i],g[x][t]);
f[x][i]-=num;
g[x][t]-=num;
}
for(int i=0;i<k;i++)
{
t=k-i-1;
num=min(f[x][i],g[x][t]);
f[x][i]-=num;
g[x][t]-=num;
}
}
int main()
{
freopen("repulsed.in","r",stdin);
freopen("repulsed.out","w",stdout);
int num=0;
memset(fst,0xff,sizeof(fst)),lnum=-1;
input();
dfs(1,0);
for(int i=k;i;i--)
{
for(int j=0;j<=k-i;j++)
{
num=min(f[1][i],g[1][j]);
f[1][i]-=num;
g[1][j]-=num;
}
}
num=0;
for(int i=0;i<=k;i++)num+=g[1][i];
ans+=ceil(num);
printf("%lld",ans);
return 0;
}
0 条评论