开点坑……没事研究一点Deep learning的论文,希望自己能对DL有点更深刻的认识……

这篇是DL在ImageNet上的很早的成果了,这篇文章之后DL开始在各个领域爆发。本文把之前ImageNet上的结果用DL方法提高了非常多,也是CV领域图像分类的开辟新方法之作。

网络结构

五层Conv层,三层FC。由于GPU的memory不是太够,层与层之间不是全都有连接(分在两个GPU里了),不过这个应该不是本质的影响。

作者提出了四个网络结构上的特点。

ReLU激活函数

ReLU是一个非饱和的激活函数,相比其他饱和的激活函数比如$\tanh$,能加快训练速度。

初步理解感觉是饱和的激活函数在输入过大的时候会梯度消失,不利于训练。

多GPU训练

不是特别懂这方面的东西……暂时先挖个坑。

Local Response Normalization

感觉作者也没太讲清楚这个为什么会help。假设$a_{x,y}^i$是网络某层输出的第$i$个channel的$(x,y)$位置的输出,则这个层会把$a$变成下面公式描述的$b$:

$$b_{x,y}^{i} = a_{x,y}^{i} / \left( k + \alpha \sum_{j=\max(0,i-n/2)}^{\min(N-1,i+n/2)} (a_{x,y}^{j})^2 \right)^\beta$$

其中$k,\alpha,\beta,n$都是超参数,$N$是总的channel个数。

作者说这个是从真实的神经元得到的启发……

Overlapping Pooling

作者说这个会轻微减小overfitting,不过这个在以后的网络结构中貌似也不是特别关注了。意思就是用stride小于window size的pooling操作。作者也把它放在最不重要的位置说了,应该也不是很本质的影响。

减少Overfitting

Data Augmentation

就是用一些保label的图像变换达到扩充数据集的作用。

第一种方法是在训练的时候,将数据从$256\times 256$随机抠出一块$224\times 224$的区域,然后再随机决定是否水平翻转图片。在预测的时候从四角和中心各抠出$224\times 224$的区域,和它们的水平翻转共十个图片,将预测结果做一个平均再输出最终结果。

第二种方法是对颜色进行微扰的方法。先对整个训练集的RGB像素值算出一个$3\times 3$的协方差矩阵,然后做一次PCA,对单张图片的每个像素的RGB值向量加上下面这个向量:

$$\begin{bmatrix}\mathbf{p}_1&\mathbf{p}_2&\mathbf{p}_3\end{bmatrix} \begin{bmatrix}\alpha_1\lambda_1&\alpha_2\lambda_2&\alpha_3\lambda_3\end{bmatrix}^\mathrm{T}$$

其中$\mathbf{p}_i$是第$i$个PCA分解出的特征向量,$\lambda_i$为其对应的特征值,$\alpha_i$是一个服从高斯分布$N(0,0.1)$的随机变量(对于每张图片重新采样,单张图片内$\alpha_i$的值是一样的)。

Dropout

实验结果表明Dropout会降低收敛速度,但可以显著减少Overfitting。将多个模型的预测结果组合起来是一种通用的提高performance的方法,Dropout可以视为指数个网络取平均的一种方法,并且不会增加很多的计算负担。Dropout会学到更鲁棒的表示。具体的可能以后会在读Dropout paper的时候再写一篇博文描述。

总结

作者还进行了卷积核的可视化,GPU1上的卷积核更多不关心颜色,GPU2的卷积核则更多关心颜色。这个现象后来应该也没人提过了……应该也不本质。

最后作者提到了深度是非常重要的,网络去掉任何一层都会导致performance下降,因此作者说在当时性能提高的瓶颈主要在于GPU的memory去训练更大的模型。后面的CNN的工作也证实了这一点。

文章中还提到最后一层的$4096$维的向量特征可以反映出图片的内容信息,两个图片的这个向量欧式距离较近就说明两张图片的内容也比较相似。

我们都知道递归函数,我们也知道编程语言的计算能力不超出图灵机,而图灵机和lambda calculus又等价,那么编程语言能完成的计算应该可以用lambda calculus表示。可是我们来看一下lambda calculus:

1
2
3
<expr> ::= <id>
<expr> ::= (lambda (<id>) <expr>)
<expr> ::= (<expr> <expr>)

考虑计算一个list的长度,我们可以写出这样的函数:

1
2
3
4
5
(define length
(lambda (lst)
(if (null? lst)
0
(+ 1 (length (cdr lst))))))

这就出问题了,在lambda calculus中,没有任何一个规则可以把这个函数命名,所以我们必须把length再整体传到调用的位置。可是这个新length的整体又产生了递归,这样我们必须写出无限长的程序,怎么办呢?

Y组合子就是一个帮助我们从lambda calculus推出递归函数的方法,它可以说明我们这样定义的递归函数是合理的,并且不超过lambda calculus的计算能力。从感官上来说,就是如果我们有一个递归函数,就像上文中的length,把开头的define换成lambda,就像这样:

1
2
3
4
5
(lambda (length)
(lambda (lst)
(if (null? lst)
0
(+ 1 (length (cdr lst))))))

Y组合子可以将这个函数,转化为真正的递归函数。

虽然我们不能通过define这么直接的方式命名函数了,但是实际上<expr> ::= (lambda (<id>) <expr>)也是一种命名的方式,当我们调用((lambda (x) lambda_body) x_body)的时候,x_body实际上就被我们命名成了x。受到这个启发,我们把length当作一个参数传给自身,以下这个函数实际上表示的就是函数length

1
2
3
4
5
6
7
8
9
10
((lambda (length)
(lambda (lst)
(if (null? lst)
0
(+ 1 ((length length) (cdr lst))))))
(lambda (length)
(lambda (lst)
(if (null? lst)
0
(+ 1 ((length length) (cdr lst)))))))

注意上面两处(length length),这是因为我们多传了一个参数,需要把length传到递归调用的位置。由于两块代码看起来完全一样,我们再抽象一下:

1
2
3
4
5
6
7
((lambda (length)
(length length))
(lambda (length)
(lambda (lst)
(if (null? lst)
0
(+ 1 ((length length) (cdr lst)))))))

我们的目标是什么呢?我们要把原来经过改造的length函数找回来,所以要再把(length length)命名掉,也就是:

1
2
3
4
5
6
7
8
9
((lambda (length)
(length length))
(lambda (length)
((lambda (func)
(lambda (lst)
(if (null? lst)
0
(+ 1 (func (cdr lst))))))
(length length))))

现在我们发现其中有一个部分就是原来经过改造的length,于是可以把这个原来经过改造的整体当成一个函数,在上面的函数中最外层加一个参数,把这个原来经过改造的函数传进去:

1
2
3
4
(define Y
(lambda (F)
((lambda (length) (length length))
(lambda (length) (F (length length))))))

其中有一些部分可以改名字,为了更美观可以改成下面的形式:

1
2
3
4
(define Y1
(lambda (F)
((lambda (x) (x x))
(lambda (y) (F (y y))))))

我们大概就完成了!还有一个小问题,在应用序求值的解释器中,为了求值(y y),解释器会自己递归下去,一直循环,所以可以将它改成(lambda (t) ((y y) t)),这跟原来显然是一个函数,只是在求值的时候不会让解释器陷入无限递归。

所以最终Y组合子的形式是:

1
2
3
4
(define Y
(lambda (F)
((lambda (x) (x x))
(lambda (y) (F (lambda (t) ((y y) t)))))))

可以验证一下,如果我们把length函数按照开头说的方法改造一下:

1
2
3
4
5
6
(define length_Y
(lambda (length)
(lambda (lst)
(if (null? lst)
0
(+ 1 (length (cdr lst)))))))

那么(Y length_Y)就是一开始的length函数。我们也就完全使用lambda calculus推出了递归函数在这个模型中是存在的。

(由于作者刚刚接触这一方面的内容,文中可能有错误、叙述不详和表述不清的地方,欢迎指正!)

作为观摩队伍参加了比赛……最后Rank 17。

怎么说呢……感觉这个成绩比较一般吧。大概过程是前90分钟搞了五道水题,然后不知道什么原因E一直不过,后三个半小时一直在搞E。当时觉得其他题都非常难应该搞不出来,现在看起来的话题目难度不算特别大,如果后三个小时及时转攻其他题目可能会比较好吧。

于是这就成为了我人生中第一次ACM……感谢一下两位队友lisihang & ZidaneAndMessi。

所以现在也是打算补起来了。

随时更新……

A. Too Rich

有面值为$1,5,10,20,50,100,200,500,1000,2000$的硬币,要求用最多的硬币凑出$p (p \leq 10^9)$,无解输出$-1$。一共有$T (T \leq 100000)$组询问。

首先把所有钱币都用上,设钱币面值总和为$S$,那么就是用最少的硬币凑出$S-p$。
如果没有面值$500$和$50$,那么这就是一个普通的贪心题。
普通的贪心是有反例的,比如$p = 60$,四个钱币分别是$20,20,20,50$。
这种情况算法发生错误的原因是多选了一个$50$或者$500$。
注意$100 = 2 \times 50, 1000 = 2 \times 500$,可以把两个$50$和$500$凑起来,转化为普通的贪心。
所以强制$50$和$500$选择是奇数个还是偶数个,分别贪心取最小值即可。

注意细节,比如$p$是否够强制取一个$500$之类的……

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=1000000000;
const int MAXN=100;
int T,n,c[MAXN],p[MAXN]={1,5,10,20,50,100,200,500,1000,2000};
int solve(int n)
{
int res=0;
for(int i=9;i>=0;i--)
{
if(p[i]==50)
{
int x=n/100;
x=min(x,c[i]/2);
res+=2*x;
n-=100*x;
continue;
}
else if(p[i]==500)
{
int x=n/1000;
x=min(x,c[i]/2);
res+=2*x;
n-=1000*x;
continue;
}
int x=n/p[i];
x=min(x,c[i]);
res+=x;
n-=p[i]*x;
}
if(n) return INF;
else return res;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int total=0,sum=0;
for(int i=0;i<10;i++) scanf("%d",&c[i]),sum+=c[i]*p[i],total+=c[i];
n=sum-n;
if(n<0) {puts("-1");continue;}
int ans=INF;
ans=min(ans,solve(n));
if(c[7])
{
n-=500,c[7]--;
if(n>=0) ans=min(ans,solve(n)+1);
n+=500,c[7]++;
}
if(c[4])
{
n-=50,c[4]--;
if(n>=0) ans=min(ans,solve(n)+1);
n+=50,c[4]++;
}
if(c[4]&&c[7])
{
n-=550,c[4]--,c[7]--;
if(n>=0) ans=min(ans,solve(n)+2);
n+=550,c[4]++,c[7]++;
}
if(ans==INF) puts("-1");
else printf("%d\n",total-ans);
}
return 0;
}

B. Count $a \times b$

定义$f(m)$为$a \times b \bmod m \neq 0$的$(a,b)$对数,其中$0 \leq a < m, 0 \leq b < m$。$T(T \leq 20000)$次询问$\sum_{d \mid n}{f(d)}\bmod 2^{64}, 1\leq n \leq 10^9$。

普通的做法:
设$h(m) = m^2 - f(m)$,暴力打表猜出$h$是积性函数和$h(p^k) = p^{k-1}(k(p-1)+p)$,就可以AC辣!

文艺的做法:
设$h(m) = m^2 - f(m)$,即$a \times b \bmod m = 0$的对数,枚举$a$,那么$b$应该是$\frac{m}{\gcd(a,m)}$的倍数,共有$\gcd(a,m)$个。
那么$h(m) = \sum_{a=1}^{m}{\gcd(a,m)}$,枚举每个最大公约数的取值,有$h(m) = \sum_{d \mid m}{d \times \phi\left( \frac{m}{d} \right)}$。
这个东西是恒等函数和欧拉函数的狄里克雷卷积,所以是积性函数。于是目标就是求出$h(p^k)$了。
$$h(p^k) = \sum_{d \mid p^k}{d \times \phi\left( \frac{p^k}{d} \right)} = \sum_{i=0}^{k}{p^i \times \phi(p^{k-i})} = p^k+ \sum_{i=0}^{k-1}p^i p^{k-i-1} (p-1) = p^{k-1}(k(p-1)+p)$$
于是对询问的$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
58
59
60
61
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;
ULL qpow(ULL x,ULL n)
{
ULL con=1,p=x;
while(n)
{
if(n&1) con*=p;
p*=p;
n>>=1;
}
return con;
}
const int MAXN=100010;
int prime[MAXN],tot;
bool p[MAXN];
int T,n;
ULL sqr(ULL x,ULL k)
{
return qpow(x,k+k);
}
ULL h(ULL x,ULL k)
{
if(k==0) return 1;
return qpow(x,k-1)*(k*(x-1)+x);
}
int main()
{
for(int i=2;i<=100000;i++)
if(!p[i])
{
prime[++tot]=i;
for(int j=i+i;j<=100000;j+=i)
p[j]=true;
}
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int nn=n;
ULL SQR=1,H=1;
for(int i=1;i<=tot&&prime[i]*prime[i]<=nn;i++)
if(n%prime[i]==0)
{
int k=0;
n/=prime[i],k++;
while(n%prime[i]==0) n/=prime[i],k++;
ULL c1=0,c2=0;
for(int x=0;x<=k;x++)
c1+=sqr(prime[i],x),c2+=h(prime[i],x);
SQR*=c1,H*=c2;
}
if(n>1) SQR*=sqr(n,0)+sqr(n,1),H*=h(n,0)+h(n,1);
printf("%llu\n",SQR-H);
}
return 0;
}

E. Rebuild

给一个$n(n \leq 10000)$个点多边形,满足所有边长都是整数。
现在要在每个顶点处画个圆,使得多边形任意两个相邻顶点处的圆都相切。
$T(T \leq 100)$组数据。

根据每条边可以列出一个式子,如果$n$是奇数那么这个解唯一,只需要解出来然后判断有没有半径是负数即可。
如果$n$是偶数要么无解,要么可以把所有的圆半径写成跟第一个圆有关的一次函数,然后求出使所有圆半径非负的第一个圆半径的区间。这些圆半径的平方和为一个二次函数,求其在一个区间内的最值。

没错这题就是这么简单……然而为什么考场上就是不过呢?这次重写大概改动了以下几个地方……

  1. $n$是奇数的时候,先求出所有圆半径平方之和再乘上$\pi$
  2. $n$是偶数的时候,直接把求得的取得最值的点带入二次函数算总面积
  3. 二次函数的系数不是在末尾清空,而是在每组数据开头清空

然而1和2真的可以影响这么大的精度吗……而且考场上3这个问题已经检查挺多遍了应该没错的吧……

于是为什么这么一个题我们交了10+次成了一个未解之谜。

(话说当时重写一遍也能过吧!为什么就等死啊!)

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const int MAXN=100010;
const LL INF=100000000000000000LL;
const double PI=acos(-1);
const double eps=1e-10;
int T,n;
LL x[MAXN],y[MAXN],d[MAXN],b[MAXN],Min,Max,B;
double r[MAXN],C;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
for(int i=1;i<=n;i++)
{
int j=i%n+1;
d[i]=(LL)(sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]))+0.5);
}
for(int i=1;i<=n;i++) b[i+1]=d[i]-b[i];
if(n&1)
{
double x=b[n+1]/2.0;
bool ok=true;
for(int i=1;i<=n;i++)
{
if(!(i&1)) r[i]=b[i]-x;
else r[i]=b[i]+x;
if(r[i]<-eps) ok=false;
}
if(!ok) {puts("IMPOSSIBLE");continue;}
else
{
double S=0;
for(int i=1;i<=n;i++)
S+=r[i]*r[i];
S*=PI;
printf("%.02lf\n",S);
for(int i=1;i<=n;i++)
printf("%.02lf\n",r[i]);
}
}
else
{
B=0,C=0;
if(b[1]!=b[n+1]) {puts("IMPOSSIBLE");continue;}
Min=0,Max=INF;
for(int i=1;i<=n;i++)
{
if(!(i&1)) Max=min(Max,b[i]),B-=2LL*b[i],C+=b[i]*b[i];
else Min=max(Min,-b[i]),B+=2LL*b[i],C+=b[i]*b[i];
}
if(Min>Max) {puts("IMPOSSIBLE");continue;}
double sym=-(B*1.0/(2*n)),x,S;
if(sym>=Min&&sym<=Max) x=sym,S=n*x*x+B*x+C;
else if(sym<Min) x=Min,S=n*x*x+B*x+C;
else x=Max,S=n*x*x+B*x+C;
S*=PI;
bool ok=true;
for(int i=1;i<=n;i++)
{
if(!(i&1)) r[i]=b[i]-x;
else r[i]=b[i]+x;
if(r[i]<-eps) ok=false;
}
if(!ok) {puts("IMPOSSIBLE");continue;}
printf("%.02lf\n",S);
for(int i=1;i<=n;i++)
printf("%.02lf\n",r[i]);
}
}
return 0;
}

F. Almost Sorted Array

定义Almost Sorted Array是一个序列满足可以去掉一个数满足单调不降或者单调不增,给出一个序列问它是否是Almost Sorted Array。

签到题……我的做法有点麻烦了。求出前缀最长连续不降和后缀连续最长不降,判断一下,再把序列取相反数判断一下。

然而就是这种题还WA了一次。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=100010;
int T,n,a[MAXN],f[MAXN],g[MAXN];
int main()
{
scanf("%d",&T);
while(T--)
{
bool ok=false;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[1]=1;
for(int i=2;i<=n;i++)
{
if(a[i]>=a[i-1]) f[i]=f[i-1]+1;
else f[i]=1;
}
g[n]=1;
for(int i=n-1;i>=1;i--)
{
if(a[i]<=a[i+1]) g[i]=g[i+1]+1;
else g[i]=1;
}
for(int i=2;i<n;i++)
if(a[i-1]<=a[i+1]&&f[i-1]+g[i+1]>=n-1) ok=true;
if(f[n-1]==n-1) ok=true;
if(g[2]==n-1) ok=true;
if(f[n]==n) ok=true;
for(int i=1;i<=n;i++) a[i]=100001-a[i];
f[1]=1;
for(int i=2;i<=n;i++)
{
if(a[i]>=a[i-1]) f[i]=f[i-1]+1;
else f[i]=1;
}
g[n]=1;
for(int i=n-1;i>=1;i--)
{
if(a[i]<=a[i+1]) g[i]=g[i+1]+1;
else g[i]=1;
}
for(int i=2;i<n;i++)
if(a[i-1]<=a[i+1]&&f[i-1]+g[i+1]>=n-1) ok=true;
if(f[n-1]==n-1) ok=true;
if(g[2]==n-1) ok=true;
if(f[n]==n) ok=true;
if(ok) puts("YES");
else puts("NO");
}
return 0;
}

G. Dancing Stars on Me

给$n$个点问是否是正$n$边形。

注意$n = 4$才有可能是正$n$边形,然后随便判一下就好了。

考场上敲了一个凸包,敲完才意识到$n = 4$的问题。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=110;
struct Point
{
int x,y;
Point(){}
Point(int _x,int _y):x(_x),y(_y){}
}P[MAXN];
Point operator-(const Point &p,const Point &q){return Point(p.x-q.x,p.y-q.y);}
int Dot(const Point &p,const Point &q){return p.x*q.x+p.y*q.y;}
int T,n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&P[i].x,&P[i].y);
if(n!=4) {puts("NO");continue;}
vector<int> D;
D.clear();
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
D.push_back(Dot(P[i]-P[j],P[i]-P[j]));
sort(D.begin(),D.end());
int x=D[0];
if(D[1]!=x||D[2]!=x||D[3]!=x||D[4]!=2*x||D[5]!=2*x) puts("NO");
else puts("YES");
}
return 0;
}

H. Partial Tree

一棵$n(n \leq 2015)$个点树的权值定义为$\sum_{i=1}^{n}{f(d_i)}$,$d_i$为第$i$个点的度数,给出函数$f$,求$n$个点的树最大可能权值。

其实这题是lisihang做的……以下都是他的想法。

由Prufer序列可以知道任何一个长度为$n-2$的序列,其中每个数都不大于$n$,都可以代表一个合法的树。
考虑一个Prufer序列,可以把它排序,每次在后面添加一个数。
考虑正在添加第$i$个数,添加的数可以跟前一个数相同,这种情况下假如前面已经有$k$个数与这个新加的数相同,权值增加$f(k+2) - f(k+1)$。
否则可以自己新开一段,这种情况权值最大值就是前$i-1$个形成的权值最大值再加上$f(2)-f(1)$。
那么就可以DP了,$dp_{i,j}$表示$i$个数,序列最后有$j$个数是相同的,初值$dp_{0,0} = n \times f(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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=1000000000;
int T,n,c[3000],f[2050][2050];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n-1;i++) scanf("%d",&c[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
f[i][j]=-INF;
f[0][0]=n*c[0];
for(int i=1;i<=n-2;i++)
{
for(int j=1;j<=n;j++)
f[i][j]=max(f[i][j],f[i-1][j-1]+c[j]-c[j-1]);
int res=-INF;
for(int j=0;j<=n;j++)
res=max(res,f[i-1][j]);
f[i][1]=res+c[1]-c[0];
}
int res=-INF;
for(int i=0;i<=n;i++)
res=max(res,f[n-2][i]);
printf("%d\n",res);
}
return 0;
}

J. Chip Factory

有一个长度为$n(n \leq 1000)$的序列$s$,对于不同的$i,j,k$,求
$$\max_{i,j,k}{(s_i+s_j) \oplus s_k}$$
其中$\oplus$代表异或运算。

现场赛$O(n^3)$居然可以过……

对$s$构一个Trie树,然后枚举$i,j$,每次删除$s_i,s_j$再查询,再插入回来。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=100010;
int T_T,n,a[MAXN];
struct Trie
{
int ch[2],size;
}T[MAXN];
int root=1,tot=1;
void Insert(int x)
{
int o=root;
T[o].size++;
for(int k=30;k>=0;k--)
{
int c;
if(x&(1<<k)) c=1;
else c=0;
if(!T[o].ch[c]) T[o].ch[c]=++tot;
o=T[o].ch[c];
T[o].size++;
}
}
void Delete(int x)
{
int o=root;
T[o].size--;
for(int k=30;k>=0;k--)
{
int c;
if(x&(1<<k)) c=1;
else c=0;
o=T[o].ch[c];
T[o].size--;
}
}
int Query(int x)
{
int o=root;
for(int k=30;k>=0;k--)
{
int c;
if(x&(1<<k)) c=1;
else c=0;
if(c==1)
{
if(T[o].ch[0]&&T[T[o].ch[0]].size) o=T[o].ch[0];
else o=T[o].ch[1],x^=(1<<k);
}
else
{
if(T[o].ch[1]&&T[T[o].ch[1]].size) o=T[o].ch[1],x^=(1<<k);
else o=T[o].ch[0];
}
}
return x;
}
int main()
{
scanf("%d",&T_T);
while(T_T--)
{
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) Insert(a[i]);
for(int i=1;i<=n;i++)
{
Delete(a[i]);
for(int j=i+1;j<=n;j++)
{
Delete(a[j]);
ans=max(ans,Query(a[i]+a[j]));
Insert(a[j]);
}
Insert(a[i]);
}
printf("%d\n",ans);
for(int i=1;i<=tot;i++) T[i].ch[0]=0,T[i].ch[1]=0,T[i].size=0;
tot=1;
}
return 0;
}

K. Maximum Spanning Forest

给一个网格图,每次给出参数$x_1,y_1,x_2,y_2,c$,在满足条件$x_1 \leq a_1,a_2 \leq x_2$,$y_1 \leq b_1,b_2 \leq y_2$,$|a_1−a_2|+|b_1−b_2|=1$的点对$(a1,b1),(a2,b2)$中间连一条权值为$c$的边,每次操作之后输出图的最大生成森林。

$T(T \leq 500)$组数据,$n \leq 100$,坐标范围$2 \times 10^9$,只有$20$组数据$n>50$。

将所有询问离散化,这样问题转化到了$200 \times 200$的网格图上,新图上每一个$1 \times 1$的方格都对应原图一个矩形,设对应的原来的矩形为$x \times y$的,那么这个网格内的最大生成树是可以直接算的,就是$x \times y \times c$,$c$是最大的权值。这一部分直接计入答案。

然后需要求这个网格图的最大生成树,假设网格图中某条边对应原来的连续$x$个格点,相邻两个格点最大权值为$c$,那么如果连$x-1$条边就连通了,首先应该连上$x-2$条边,这部分直接计入答案。
然后把每条边的边权设为$c$,跑最大生成树,答案再加上最大生成树的总边权,这样就是最终答案了。

但是如果每次Kruskal算法的边都重新排序的话,复杂度$O(n^3 \log n)$不太能过。于是……一个神奇的地方
大概意思就是把每次求出的最大生成森林保留下来,只有这部分边下次才有可能选,然后下次操作时在for循环到一个合适的位置的时候把下次插入的所有边处理一下(因为插入的所有边边权都相同),就优化到$O(n^3)$了。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int MOD=1000000007;
int T,n,N,M;
int X1[210],X2[210],Y1[210],Y2[210];
LL C[210],u[210][210],r[210][210],p[210][210],Hash[210][210];
struct Edge
{
int x,y;
LL z;
Edge(){}
Edge(int _x,int _y,LL _z):x(_x),y(_y),z(_z){}
friend bool operator<(const Edge &p,const Edge &q)
{
return p.z>q.z;
}
}E[100010],nextE[100010];
int tot,nextTot,fa[100010];
int find(int x)
{
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
inline void uni(int i,int j)
{
fa[find(i)]=find(j);
}
LL ans;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ans=0;
vector<int> X,Y;
X.clear(),Y.clear();
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d%lld",&X1[i],&Y1[i],&X2[i],&Y2[i],&C[i]);
X.push_back(X1[i]),Y.push_back(Y1[i]);
X.push_back(X2[i]),Y.push_back(Y2[i]);
}
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
sort(Y.begin(),Y.end());
Y.erase(unique(Y.begin(),Y.end()),Y.end());
for(int i=1;i<=n;i++)
{
X1[i]=lower_bound(X.begin(),X.end(),X1[i])-X.begin();
X2[i]=lower_bound(X.begin(),X.end(),X2[i])-X.begin();
Y1[i]=lower_bound(Y.begin(),Y.end(),Y1[i])-Y.begin();
Y2[i]=lower_bound(Y.begin(),Y.end(),Y2[i])-Y.begin();
}
N=X.size(),M=Y.size();
for(int i=0;i<=N;i++)
for(int j=0;j<=M;j++)
p[i][j]=0,u[i][j]=0,r[i][j]=0,Hash[i][j]=i*M+j+1;
tot=0;
for(int o=1;o<=n;o++)
{
bool updated=false;
for(int i=X1[o];i<=X2[o];i++)
for(int j=Y1[o];j<Y2[o];j++)
if(r[i][j]<C[o]) r[i][j]=C[o],updated=true;
for(int i=X1[o];i<X2[o];i++)
for(int j=Y1[o];j<=Y2[o];j++)
if(u[i][j]<C[o]) u[i][j]=C[o],updated=true;
for(int i=X1[o];i<X2[o];i++)
for(int j=Y1[o];j<Y2[o];j++)
if(p[i][j]<C[o])
{
ans=(ans-(p[i][j]*(X[i+1]-X[i]-1)%MOD*(Y[j+1]-Y[j]-1))%MOD+MOD)%MOD;
p[i][j]=C[o];
ans=(ans+(p[i][j]*(X[i+1]-X[i]-1))%MOD*(Y[j+1]-Y[j]-1))%MOD;
}
if(!updated) {printf("%lld\n",ans);continue;}
ans=0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
ans=(ans+(p[i][j]*(X[i+1]-X[i]-1))%MOD*(Y[j+1]-Y[j]-1))%MOD;
for(int i=1;i<=N*M;i++) fa[i]=i;
for(int i=0;i<N;i++)
for(int j=0;j<M-1;j++)
if(r[i][j]) ans=(ans+r[i][j]*(Y[j+1]-Y[j]-1))%MOD;
for(int i=0;i<N-1;i++)
for(int j=0;j<M;j++)
if(u[i][j]) ans=(ans+u[i][j]*(X[i+1]-X[i]-1))%MOD;
for(int i=1;i<=tot;i++)
{
if(E[i-1].z>C[o]&&E[i].z<=C[o])
{
for(int x=X1[o];x<=X2[o];x++)
for(int y=Y1[o];y<Y2[o];y++)
{
int p=Hash[x][y],q=Hash[x][y+1];
if(find(p)==find(q)) continue;
uni(p,q);
ans=(ans+C[o])%MOD;
nextE[++nextTot]=Edge(p,q,C[o]);
}
for(int x=X1[o];x<X2[o];x++)
for(int y=Y1[o];y<=Y2[o];y++)
{
int p=Hash[x][y],q=Hash[x+1][y];
if(find(p)==find(q)) continue;
uni(p,q);
ans=(ans+C[o])%MOD;
nextE[++nextTot]=Edge(p,q,C[o]);
}
}
if(find(E[i].x)==find(E[i].y)) continue;
uni(E[i].x,E[i].y);
ans=(ans+E[i].z)%MOD;
nextE[++nextTot]=E[i];
}
if(tot==0||E[tot].z>C[o])
{
for(int x=X1[o];x<=X2[o];x++)
for(int y=Y1[o];y<Y2[o];y++)
{
int p=Hash[x][y],q=Hash[x][y+1];
if(find(p)==find(q)) continue;
uni(p,q);
ans=(ans+C[o])%MOD;
nextE[++nextTot]=Edge(p,q,C[o]);
}
for(int x=X1[o];x<X2[o];x++)
for(int y=Y1[o];y<=Y2[o];y++)
{
int p=Hash[x][y],q=Hash[x+1][y];
if(find(p)==find(q)) continue;
uni(p,q);
ans=(ans+C[o])%MOD;
nextE[++nextTot]=Edge(p,q,C[o]);
}
}
printf("%lld\n",ans);
tot=nextTot;
E[0]=Edge(0,0,1000000001);
for(int i=1;i<=tot;i++) E[i]=nextE[i];
nextTot=0;
}
}
return 0;
}

L. House Building

给一块积木图,$(i,j)$位置放了一个高度为$a_{i,j}$的积木,求表面积(不算下表面)。

横向扫一扫纵向扫一扫就可以了……没啥好说的……又是一个签到题……

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int T,n,m,a[100][100];
int main()
{
scanf("%d",&T);
while(T--)
{
int ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m+1;j++)
ans+=abs(a[i][j-1]-a[i][j]);
for(int i=1;i<=n+1;i++)
for(int j=1;j<=m;j++)
ans+=abs(a[i-1][j]-a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]) ans++;
printf("%d\n",ans);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=0;
}
return 0;
}

3/100 Challenge:0/10

2015-09-19

心情是崩溃的,居然留的是CC……

上场CC打的不是很好的样子,做出六道题,最后三道题有两道都不太难但没做出来……

哎,仿佛日了狗。再加上之前运动会给我重大打击,感觉要死。

没办法还是写吧……

先看了一下自己的题……我的妈……第一题一个类似下落的圆盘的计算几何,然而我计算几何都不会写线段求交……第二题好像挺厉害的行列式之类的……总之两道都不会。

而且最BT的是要求完成10道challenge,天辣!

XRQRS之前做过,直接复制下来。可持久化Trie的裸题。

TWOCOMP熬夜写……因为忘处理倍增数组WA了好几发……处理一下树链相交之后就是弱智网络流了。

现在是凌晨2:40,我的心情是崩溃的。

2015-09-20

做完了CUCUMBER。

2015-09-21

做完了FNCS。

这两天网断了没及时更……

2015-10-20

都一个月没更了……

然而作业有点想弃疗了……就这么放着好了……

最后可能会在这里把一些有用的东西发上来,写多少算多少吧。

事情是这样的……CF完全不敢打因为Rating比我实际水平高太多……

所以就想打打TC,做点题练习一下。

然而Hard太难了根本不会做啊……看题解也不容易。

所以就只好写点Medium……顺手把Easy也做了,不过Easy就不写题解了。

SRM 634. SegmentDrawing

给$n(n \leq 20)$个点,可以涂成红蓝两种颜色。相同颜色的点之间可以连线段,线段的颜色为其顶点的颜色,不同颜色的线段不能相交。每一条线段有一个权值(相同顶点的线段颜色不同权值也不同),求连出线段的最大权值为多少。

把红蓝线段建成点,可以把不相交和顶点颜色的限制表述为:如果选了红线段$a$,那么在集合$S_a$中的蓝线段不能选择。这样就是一个最小割模型了。

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
#include<bits/stdc++.h>
#define next next2
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
if(b==0) return a;
return gcd(b,a%b);
}
LL qpow(LL x,LL n,LL MOD)
{
LL con=1,p=x;
while(n)
{
if(n&1) con=(con*p)%MOD;
p=(p*p)%MOD;
n>>=1;
}
return con;
}
const int MAXN=100010;
const int MAXM=1000010;
const int INF=1000000000;
int S,T,d[MAXN];
int q[MAXN],l,r;
int head[MAXN],to[MAXN],next[MAXN],w[MAXN],cnt=1;
inline void adde(int f,int t,int ww)
{
cnt++,to[cnt]=t,next[cnt]=head[f],head[f]=cnt,w[cnt]=ww;
cnt++,to[cnt]=f,next[cnt]=head[t],head[t]=cnt,w[cnt]=0;
}
inline void add2(int f,int t,int ww)
{
cnt++,to[cnt]=t,next[cnt]=head[f],head[f]=cnt,w[cnt]=ww;
cnt++,to[cnt]=f,next[cnt]=head[t],head[t]=cnt,w[cnt]=ww;
}
bool BFS()
{
for(int i=1;i<=T;i++) d[i]=-1;
q[l=r=1]=S,d[S]=1;
while(l<=r)
{
int x=q[l++];
for(int i=head[x];i;i=next[i])
if(w[i]>0&&d[to[i]]==-1) d[to[i]]=d[x]+1,q[++r]=to[i];
}
return d[T]!=-1;
}
int DFS(int x,int a)
{
if(x==T) return a;
int flow=a,f;
for(int i=head[x];i;i=next[i])
if(d[to[i]]==d[x]+1&&w[i]>0)
{
f=DFS(to[i],min(w[i],a));
w[i]-=f,w[i^1]+=f,a-=f;
if(a<=0) return flow;
}
if(a!=0) d[x]=-1;
return flow-a;
}
int Dinic()
{
int flow=0,f;
while(BFS())
while((f=DFS(S,INF))!=0)
flow+=f;
return flow;
}
int sgn(int x)
{
if(x==0) return 0;
return x>0?1:-1;
}
struct Point
{
int x,y;
Point(){}
Point(int _x,int _y):x(_x),y(_y){}
};
Point operator+(const Point &p,const Point &q){return Point(p.x+q.x,p.y+q.y);}
Point operator-(const Point &p,const Point &q){return Point(p.x-q.x,p.y-q.y);}
int Cross(const Point &p,const Point &q){return p.x*q.y-p.y*q.x;}
bool Intersect(const Point &p1,const Point &p2,const Point &q1,const Point &q2)
{
int c1=Cross(p2-p1,q1-p1),c2=Cross(p2-p1,q2-p1),c3=Cross(q2-q1,p1-q1),c4=Cross(q2-q1,p2-q1);
return sgn(c1)*sgn(c2)<0&&sgn(c3)*sgn(c4)<0;
}
int n,Hash[50][50][2],tot,ans;
class SegmentDrawing {
public:
int maxScore(vector <int> x, vector <int> y, vector <int> redScore, vector <int> blueScore) {
n=x.size();
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
Hash[i][j][0]=++tot,ans+=redScore[i*n+j];
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
Hash[i][j][1]=++tot,ans+=blueScore[i*n+j];
S=++tot,T=++tot;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
adde(S,Hash[i][j][0],redScore[i*n+j]);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
adde(Hash[i][j][1],T,blueScore[i*n+j]);
for(int xi=0;xi<n;xi++)
for(int xj=xi+1;xj<n;xj++)
for(int yi=0;yi<n;yi++)
for(int yj=yi+1;yj<n;yj++)
if(Intersect(Point(x[xi],y[xi]),Point(x[xj],y[xj]),Point(x[yi],y[yi]),Point(x[yj],y[yj]))) adde(Hash[xi][xj][0],Hash[yi][yj][1],INF);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
for(int k=0;k<n;k++)
if(k!=i) adde(Hash[i][j][0],Hash[min(i,k)][max(i,k)][1],INF);
for(int k=0;k<n;k++)
if(k!=j) adde(Hash[i][j][0],Hash[min(j,k)][max(j,k)][1],INF);
}
ans-=Dinic();
return ans;
}
};
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

SRM 635. StoryFromTCO

一个人要打$n(n \leq 1000)$场比赛,他在第$i$场比赛获得名次是$place_i$,第$i$场比赛的晋级人数为$cutoff_i$,他要在所有$n$场比赛都晋级。他可以选择一个集合$S$,可以任意排列场次在$S$中比赛的排名。问使他达到目标的最小的$|S|$是多少,或者指出不存在这样的$S$。

首先如果给出了一个可以轮换的集合$S$,可以用贪心判断是不是合法。把在集合$S$中的所有$place_i$排序,$cutoff_i$排序,如果存在$i$,使得$place_i > cutoff_i$说明是当前$S$不合法。

如果初始状态下$place_i > cutoff_i$,那么必有$i \in S$,我们拿来这个集合判断是否合法,如果合法了这个就是最小的集合$S$了,否则得添加一些元素进去,考虑一个一个添加元素。

不合法的判定中,一定存在一个最小的$i$有$place_i > cutoff_i$,这是最早不满足条件的比赛,我们需要添加一个当前满足条件的比赛进入轮换,让这个不满足的条件满足。只要选择一个$place_j \leq cutoff_i, j \notin S$的比赛$j$,加入进去就可以让原来不满足的满足,如果不存在这个$j$,那么就无解。满足这个条件的$j$有很多个,应该选$cutoff_j$最大的$j$,这样更有可能使集合$S$合法。

添加元素之后再次检测集合$S$是否合法,如果不合法重复上述步骤。

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
#include<bits/stdc++.h>
#define next next2
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
if(b==0) return a;
return gcd(b,a%b);
}
LL qpow(LL x,LL n,LL MOD)
{
LL con=1,p=x;
while(n)
{
if(n&1) con=(con*p)%MOD;
p=(p*p)%MOD;
n>>=1;
}
return con;
}
const int MAXN=2010;
int n,fail;
bool used[MAXN];
vector<int> p,c;
bool check()
{
sort(p.begin(),p.end());
sort(c.begin(),c.end());
for(int i=0;i<c.size();i++)
if(p[i]>c[i]) {fail=c[i];return false;}
return true;
}
class StoryFromTCO {
public:
int minimumChanges(vector <int> places, vector <int> cutoff) {
n=places.size();
for(int i=0;i<n;i++)
if(places[i]>cutoff[i])
p.push_back(places[i]),c.push_back(cutoff[i]),used[i]=true;
while(!check())
{
int sub=-1;
for(int i=0;i<n;i++)
if(!used[i]&&places[i]<=fail)
if(sub==-1||cutoff[i]>cutoff[sub]) sub=i;
if(sub==-1) return -1;
used[sub]=true;
p.push_back(places[sub]),c.push_back(cutoff[sub]);
}
return p.size();
}
};
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

SRM 636. ClosestRabbit

给一个$n \times m$的棋盘$(n,m \leq 20)$,棋盘上有些格子是障碍物。有$r$只兔子要随机跳进棋盘,每只兔子必须选择一个不是障碍的格子,不能有两只兔子选同一个格子。定义$f(i)$为距离第$i$个兔子最近的兔子的编号,距离定义为欧氏距离,如果有多个最近的就选行数最小的,如果还有多个就选列数最小的。假设有一张图,对所有的$i$让$i$向$f(i)$连边,求图的期望连通块数。

首先这个图$n$个点$n$条边,是个环套树森林,连通块数就是环数。

可以证明不存在三元或以上的环。如果存在$n$元环的话,这$n$个兔子必须形成一个正$n$边形,但是在$n \neq 4$的时候不存在格点正$n$边形。$n = 4$的时候,因为要连到行数最小的格子,所以右上和左下的点必然同连左上的点,也不可能。

所以可以枚举两个点,算一下多大概率这两个点是环,加一下就可以了。

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
#include<bits/stdc++.h>
#define next next2
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
if(b==0) return a;
return gcd(b,a%b);
}
LL qpow(LL x,LL n,LL MOD)
{
LL con=1,p=x;
while(n)
{
if(n&1) con=(con*p)%MOD;
p=(p*p)%MOD;
n>>=1;
}
return con;
}
const int MAXN=410;
int n,m,tot;
pair<int,int> P[MAXN];
double ans=0,C[MAXN][MAXN];
int Dis(const pair<int,int> &p,const pair<int,int> &q)
{
return (p.first-q.first)*(p.first-q.first)+(p.second-q.second)*(p.second-q.second);
}
class ClosestRabbit {
public:
double getExpected(vector <string> board, int r) {
n=board.size(),m=board[0].size();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(board[i][j]=='.') P[++tot]=make_pair(i,j);
C[0][0]=1;
for(int i=1;i<=tot;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
for(int i=1;i<=tot;i++)
for(int j=i+1;j<=tot;j++)
{
int good=0,D=Dis(P[i],P[j]);
for(int k=1;k<=tot;k++)
{
if(k==i||k==j) continue;
int d=Dis(P[i],P[k]);
if(d<D||(d==D&&(P[k].first<P[j].first||(P[k].first==P[j].first&&P[k].second<P[j].second)))) continue;
d=Dis(P[j],P[k]);
if(d<D||(d==D&&(P[k].first<P[i].first||(P[k].first==P[i].first&&P[k].second<P[i].second)))) continue;
good++;
}
ans+=C[good][r-2]/C[tot][r];
}
return ans;
}
};
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

SRM 637. PathGame

有一个$2 \times n$的棋盘$(n \leq 1000)$,棋盘上有障碍物,一开始可以从最左面的一个格子走到最右面的一个格子,两个人玩游戏,轮流放障碍物,谁放完之后不能从左面走到右面谁就输了。问谁是人生赢家。

加入一个障碍物之后,可以注意到游戏被分成了三块。

637 1

只不过左右两块有限制,每一块左边或右边的边界处有的格子不能进入或走出。

这样就可以用$f_{l,r,l0,r0,l1,r1}$表示$\left[ l,r \right]$这一段,左边的状态是$(l0,l1)$,右边的状态是$(r0,r1)$所对应的SG函数。

但是这样转移也是$O(n)$的,时间达到了$O(n^3)$,不能接受。

但是一开始所有的障碍物已经把棋盘分割好了!可以认为一开始的障碍物把棋盘分割成了很多部分,这样中间的部分就没有障碍物了,可以用每段长度来DP。

637 2

这样时间就是$O(n^2)$了……

(图片转自官方题解)

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
#include<bits/stdc++.h>
#define next next2
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
if(b==0) return a;
return gcd(b,a%b);
}
LL qpow(LL x,LL n,LL MOD)
{
LL con=1,p=x;
while(n)
{
if(n&1) con=(con*p)%MOD;
p=(p*p)%MOD;
n>>=1;
}
return con;
}
int n,SG;
int f[1010][2][2][2][2];
int getf(int n,int l0,int l1,int r0,int r1)
{
if(n==0) return 0;
int &x=f[n][l0][l1][r0][r1];
if(x!=-1) return x;
if(n==1)
{
if(l0==0&&r1==0) return x=0;
if(l1==0&&r0==0) return x=0;
return x=1;
}
vector<int> v;
v.clear();
int l,r;
if(l0) l=getf(n-1,1,0,r0,r1),v.push_back(l);
if(l1) l=getf(n-1,0,1,r0,r1),v.push_back(l);
if(r0) r=getf(n-1,l0,l1,1,0),v.push_back(r);
if(r1) r=getf(n-1,l0,l1,0,1),v.push_back(r);
for(int i=2;i<n;i++)
{
l=getf(i-1,l0,l1,1,0);
r=getf(n-i,1,0,r0,r1);
v.push_back(l^r);
l=getf(i-1,l0,l1,0,1);
r=getf(n-i,0,1,r0,r1);
v.push_back(l^r);
}
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=0;i<v.size();i++) if(v[i]!=i) return x=i;
return x=v.size();
}
class PathGame {
public:
string judge(vector <string> board) {
memset(f,-1,sizeof(f));
n=board[0].size();
vector<tuple<int,int,int> > v;
v.clear();
for(int i=0;i<n;i++)
if(board[0][i]=='#') v.push_back(make_tuple(i,0,1));
else if(board[1][i]=='#') v.push_back(make_tuple(i,1,0));
if(v.empty()) SG=getf(n,1,1,1,1);
else
{
SG^=getf(get<0>(v[0]),1,1,get<1>(v[0]),get<2>(v[0]));
for(int i=0;i<v.size()-1;i++)
SG^=getf(get<0>(v[i+1])-get<0>(v[i])-1,get<1>(v[i]),get<2>(v[i]),get<1>(v[i+1]),get<2>(v[i+1]));
SG^=getf(n-1-get<0>(v[v.size()-1]),get<1>(v[v.size()-1]),get<2>(v[v.size()-1]),1,1);
}
if(SG==0) return "Sothe";
else return "Snuke";
}
};
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

TheLargestString

给两个字符串$S,T$,$\left| S \right| = \left| T \right|$,可以一次消去$S,T$中同一个位置的字符,要求最后得到$S+T$的字符串最大,$+$表示字符串的拼接。字符串长度$\leq 47$。

看起来真像贪心题啊……

然而貌似贪心是不行的……官方题解给的方法是DP。

我的DP方法是$f_{i,j}$表示前$i$个位置中选$j$个的最大字符串。

$f_{i,j}$可以通过$f_{i-1,j}$和$f_{i-1,j-1}$转移过来。

正确性可以保证,因为很容易证明任何其他的从前$i-1$个中选择$j-1$个位置选出的字符串都不如$f_{i-1,j-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
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class TheLargestString {
public:
string find(string, string);
};
int n;
string f[50][50],ans;
string TheLargestString::find(string s, string t) {
n=s.size();
f[0][1]=s.substr(0,1)+t.substr(0,1);
for(int i=1;i<n;i++)
for(int j=1;j<=i+1;j++)
{
if(j!=i+1) f[i][j]=max(f[i][j],f[i-1][j]);
f[i][j]=max(f[i][j],f[i-1][j-1].substr(0,j-1)+s[i]+f[i-1][j-1].substr(j-1,j-1)+t[i]);
}
for(int i=1;i<=n;i++) ans=max(ans,f[n-1][i]);
return ans;
}
//Powered by [KawigiEdit] 2.0!

TheMagicMatrix

有一个$n \times n$的棋盘,每一个位置用一个$0$到$9$的数字填充,要求填充完毕后每一行每一列的和的个位数字相同。已经有$k$个格子填完了。$n \leq 1000,k \leq 10$。

题目好厉害……

答案相当于在$\bmod 10$意义下,使每行每列和相等的方案数。

假如有一行一列都没有障碍的话,我们可以空出这一行这一列,枚举一个和,把其它格子任意填上数字,这样就可以对应一种填法。所以这种情况下答案是$10^{(n-1)*(n-1)+1-m}$。

这样剩下的$n \leq 10$,不到$100$个变量了,可以暴力列方程组高斯消元。

但是注意到$\bmod 10$意义下求解解的个数比较难,因为可能出现$8x = 0$这样的方程,它有$2$个解。

如果模数是质数就好做了,因为要么一个变量是自由元,要么它只有一个解。而如果把$10$拆成$2$和$5$,对于每个数来说方案数乘起来之后还是等价的,所以答案就是先$\bmod 2$消元的答案乘上$\bmod 5$消元的答案。

但是因为这道题的消元矩阵比较特殊,里面的数只可能是$0,1$,所以可以直接$\bmod 10$高斯消元,依然可以保证一个变量有$1$或$10$种解。模$10$意义的高斯消元在消元过程中用辗转相除即可。

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
152
153
154
155
156
157
158
159
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
typedef long long LL;
const LL MOD=1234567891;
const LL mod1=2;
const LL mod2=5;
LL qpow(LL x,LL n,LL MOD)
{
LL con=1,p=x;
while(n)
{
if(n&1) con=(con*p)%MOD;
p=(p*p)%MOD;
n>>=1;
}
return con;
}
class TheMagicMatrix {
public:
int find(int, vector <int>, vector <int>, vector <int>);
};
int n,m,tot,Len[1010],R;
LL A[1010][110],ans;
inline int Hash(int i,int j)
{
return i*n+j+1;
}
void Gauss(LL mod)
{
int now=1;
for(int i=1;i<=n*n;i++)
{
int sub=0;
for(int j=now;j<=tot;j++) if(A[j][i]>0) sub=j;
if(sub==0) continue;
for(int k=1;k<=n*n+1;k++) swap(A[now][k],A[sub][k]);
now++;
for(int k=now;k<=tot;k++)
{
while(A[k][i]!=0)
{
for(int j=1;j<=n*n+1;j++) swap(A[now-1][j],A[k][j]);
LL o=A[k][i]/A[now-1][i];
for(int j=1;j<=n*n+1;j++)
A[k][j]=(A[k][j]-(o*A[now-1][j])%mod+mod)%mod;
}
}
}
}
int TheMagicMatrix::find(int n, vector <int> rows, vector <int> columns, vector <int> values) {
::n=n;
m=rows.size();
if(n>10) return qpow(10LL,(n-1)*(n-1)-m+1,MOD);
for(int D=0;D<10;D++)
{
LL ans1=0,ans2=0;
memset(A,0,sizeof(A));
tot=0;
for(int i=0;i<n;i++)
{
++tot;
for(int j=0;j<n;j++)
A[tot][Hash(i,j)]++;
A[tot][n*n+1]=D%mod1;
}
for(int j=0;j<n;j++)
{
++tot;
for(int i=0;i<n;i++)
A[tot][Hash(i,j)]++;
A[tot][n*n+1]=D%mod1;
}
for(int i=0;i<m;i++)
{
++tot;
A[tot][Hash(rows[i],columns[i])]++;
A[tot][n*n+1]=values[i]%mod1;
}
Gauss(mod1);
memset(Len,0,sizeof(Len));
for(int i=1;i<=tot;i++)
while(Len[i]<=n*n&&A[i][Len[i]]==0) Len[i]++;
bool ok1=true;
for(int i=1;i<=tot;i++)
if(Len[i]==n*n+1&&A[i][n*n+1]!=0) ok1=false;
R=0;
Len[tot+1]=n*n+1;
for(int i=1;i<=tot;i++)
if(Len[i+1]>Len[i]) R++;
ans1=qpow(mod1,n*n-R,MOD)%MOD;
if(!ok1) ans1=0;
memset(A,0,sizeof(A));
tot=0;
for(int i=0;i<n;i++)
{
++tot;
for(int j=0;j<n;j++)
A[tot][Hash(i,j)]++;
A[tot][n*n+1]=D%mod2;
}
for(int j=0;j<n;j++)
{
++tot;
for(int i=0;i<n;i++)
A[tot][Hash(i,j)]++;
A[tot][n*n+1]=D%mod2;
}
for(int i=0;i<m;i++)
{
++tot;
A[tot][Hash(rows[i],columns[i])]++;
A[tot][n*n+1]=values[i]%mod2;
}
Gauss(mod2);
memset(Len,0,sizeof(Len));
for(int i=1;i<=tot;i++)
while(Len[i]<=n*n&&A[i][Len[i]]==0) Len[i]++;
bool ok2=true;
for(int i=1;i<=tot;i++)
if(Len[i]==n*n+1&&A[i][n*n+1]!=0) ok2=false;
R=0;
Len[tot+1]=n*n+1;
for(int i=1;i<=tot;i++)
if(Len[i+1]>Len[i]) R++;
ans2=qpow(mod2,n*n-R,MOD)%MOD;
if(!ok2) ans2=0;
ans=(ans+(ans1*ans2)%MOD)%MOD;
}
return ans;
}
//Powered by [KawigiEdit] 2.0!

ThePowers

已知$X \in \left[ 1,A \right],Y \in \left[ 1,B \right]$,求$X^Y$有多少种不同的取值。$A \leq 10^9,B \leq 10^9$。

下面的分析不考虑底数为$1$,最后考虑$1$时只要在最后把答案增加$1$就可以了。

首先如果$x_{1}^{y_1} = x_{2}^{y_2}$,那么存在$r$,使得$x,y$均为$r$的幂。

定义集合$S_x = \left\{ x^k \right\}$。考虑所有的$S_i$,这里$i$是一个不能被表为$a^b \left( b \geq 2 \right)$的数,在不同集合中的数作为底数所产生的幂一定不相同,所以可以分别对所有集合求解。

虽然集合个数非常多,但分析之后可以发现只要集合大小相同,这个集合产生的幂个数就是相同的。大小超过$1$的集合之多只有$\sqrt{n}$个,所以可以暴力统计出大小为$x$的集合的个数$c_x$。

这样子问题变成了给一个数列$a^1,a^2,a^3,\cdots,a^A$和一个数$B$,求数列中的数的$1$到$B$次幂共有多少种。先对数列所有项取对数,可以把问题变成$x \in \left[ 1,A \right],y \in \left[ 1,B \right],S = \left\{ xy \right\}$,求$\left| S \right|$。这里$A \leq 30$。

接下来$S$内的数都在$\left[ 1,AB \right]$内了,按照$B$把这个区间分成$A$份,每一份形如$\left[ (i-1)B+1,iB \right]$。第$i$份内某个数合法等价于这个数是$\left[ i,A \right]$中某一个数的倍数。这样分段的好处是不用考虑$B$的限制了,只要这个数$a$在段内,而且它是某个数$x \in \left[ i,A \right]$的倍数,那么一定有$\frac{a}{x} \leq B$。

现在的问题是给一个集合$D = \left[ i,A \right]$,求$\left[ L,R \right]$中是$D$中某元素倍数的数的个数。利用前缀和可以把$\left[ L,R \right]$转化为$\left[ 1,N \right]$。如果$\left| D \right|$很小可以用容斥原理暴力做,但是现在$\left| D \right|$最大可以达到$30$。注意如果$D$中两个元素$d_1,d_2$有整除关系$d_1 \mid d_2$,那么$d_2$可以直接删掉。这样子暴力一下发现对于任何$i$,$\left[ i,A \right]$都能缩减到$15$以下的规模,就可以暴力容斥了。

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
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
typedef long long LL;
class ThePowers {
public:
long long find(int, int);
};
LL MAX,c[50],ans;
bool used[100010],inS[50];
LL gcd(LL a,LL b)
{
if(b==0) return a;
return gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
return a/gcd(a,b)*b;
}
LL solve(const vector<int> &d,LL N)
{
static int popcnt[100010];
int n=d.size();
LL res=0;
for(int S=1;S<(1<<n);S++)
{
popcnt[S]=popcnt[S>>1]+(S&1);
LL con=1;
for(int j=0;j<n;j++)
if(S&(1<<j)) con=lcm(con,d[j]);
if(popcnt[S]&1) res+=N/con;
else res-=N/con;
}
return res;
}
LL calc(LL A,LL B)
{
LL res=0;
for(LL i=1;i<=A;i++)
{
memset(inS,false,sizeof(inS));
for(int j=i;j<=A;j++) inS[j]=true;
for(int j=i;j<=A;j++)
for(int p=j+j;p<=A;p+=j)
inS[p]=false;
vector<int> d;
d.clear();
for(int j=i;j<=A;j++)
if(inS[j]) d.push_back(j);
res+=solve(d,i*B)-solve(d,(i-1)*B);
}
return res;
}
long long ThePowers::find(int A, int B) {
while((MAX+1)*(MAX+1)<=A) MAX++;
for(LL i=2;i<=MAX;i++)
{
if(used[i]) continue;
LL p=i,t=1;
used[i]=true;
while(p*i<=A)
{
p*=i,t++;
if(p<=MAX) used[p]=true;
}
c[t]++;
}
c[1]=A-1;
for(int i=2;i<50;i++) c[1]-=i*c[i];
for(int i=1;i<50;i++)
if(c[i]) ans+=c[i]*calc(i,B);
return ans+1;
}
//Powered by [KawigiEdit] 2.0!

A.Secrets

找到一个集合,要求这个集合中的元素都能表示为$ 3^k $,且集合的元素和大于$ n $,且去掉任何一个元素后集合的元素和小于$ n $,问这个集合元素个数的最大值。

考虑把集合中元素排序,显然要求去掉第一个元素后集合的元素和小于$ n $。记第一个元素为$ x $,如果$ x \mid n $,那么去掉$ x $之后这个元素集合一定不小于$ n $。反之则去掉$ x $后集合元素和一定小于$ n $。

找到最大的$ k $使得$ 3^k \mid n $,令集合中所有元素都等于$ 3^{k+1} $,这个集合满足题意,且元素个数已经达到了上界。答案即为$ \lceil \frac{n}{3^{k+1}} \rceil $。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL n,k=1;
int main()
{
scanf("%I64d",&n);
while(n%k==0) k*=3;
printf("%I64d\n",n/k+1);
return 0;
}

B.Chips

$ n \times n $的棋盘上有$ m $个障碍,可以在棋盘的边界(但不是角)的位置放置一个棋子。有$ n-1 $轮行动,每次行动都将每个棋子向它初始位置对面的方向移动一个格子。要求中途移动的时候棋子不能触碰障碍、不能棋子与棋子处于一个格子内、不能在一轮行动后两个棋子仅互相交换位置,求最多可以放多少个棋子。

显然每行每列只能放一个棋子。

考虑第$ i $行、第$ i $列、第$ n-i+1 $行、第$ n-i+1 $列,这两行两列可以放四个棋子。

Div.1 B

这样我们将整个棋盘两行两列为一组分开,每一组之间相互独立,在每一组内判断哪四个位置因为障碍不能放棋子就可以了。

注意特判$ 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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN=1010;
int n,k,x,y,usedx[MAXN],usedy[MAXN],ans;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
usedx[x]=true;
usedy[y]=true;
}
for(int i=2;i<=(n>>1);i++)
{
if(!usedx[i]) ans++;
if(!usedx[n+1-i]) ans++;
if(!usedy[i]) ans++;
if(!usedy[n+1-i]) ans++;
}
if((n&1)&&(!usedx[(n+1)>>1]||!usedy[(n+1)>>1])) ans++;
printf("%d\n",ans);
return 0;
}

C.Lucky Tickets

一个八位数,如果可以在其中添加加号、减号、乘号、小括号使得运算结果为$k$,就称为Lucky Ticket。请找到$m$个Lucky Ticket。

这算什么破题……完全就是乱搞啊……

只考虑前四位,爆搜一下能产生什么结果,后面再用一个四位数加一加减一减凑出$k$……

代码是抄的。不过我写的这个应该不能保证所有的都跑出来?因为前四位考虑的情况也不全……只是这样写就过掉了测试数据……

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int k,m,last[100010],now;
void DFS(int n,int res,int num)
{
if(n>4) return;
if(n==4)
{
int o=abs(res-k);
if(o<10000&&last[o]!=now)
{
last[o]=now;
printf("%04d%04d\n",now,o);
m--;
if(m==0) exit(0);
}
return;
}
DFS(n+1,res+(num%10),num/10);
DFS(n+1,res-(num%10),num/10);
DFS(n+1,res*(num%10),num/10);
DFS(n+2,res+(num%100),num/100);
DFS(n+2,res-(num%100),num/100);
DFS(n+2,res*(num%100),num/100);
}
int main()
{
scanf("%d%d",&k,&m);
memset(last,-1,sizeof(last));
for(int i=0;i<10000;i++)
{
now=i;
DFS(1,i%10,i/10);
DFS(2,i%100,i/100);
DFS(3,i%1000,i/1000);
}
return 0;
}

D.Characteristics of Rectangles

输入一个$ n \times m $的数表,第$ i $行第$ j $列的数为$ a_{i,j} $,求$ \max_{i_1,i_2,j_1,j_2} \min \left( {a_{i_1,j_1},a_{i_2,j_1},a_{i_1,j_2},a_{i_2,j_2}} \right) $。

先二分一个答案$ ans $,设$ c_{i,j} = 1 $当且仅当$ a_{i,j} \geq ans $。问题转化为是否存在$ i_1,i_2,j_1,j_2 $,使得$ c_{i_1,j_1}=c_{i_2,j_1}=c_{i_1,j_2}=c_{i_2,j_2}=1 $。

考虑这样的做法:将所有满足存在$ j $,使得$ c_{i_1,j} = c_{i_2,j} = 1 $的$ i_1,i_2 $二元组记录下来,如果某个$ i_1,i_2 $出现了两次,那就说明问题有解。扫描每一列,确定$j$,标记这样的二元组,这个时间复杂度可以做到$ O \left( n+这样的二元组数 \right) $。这样扫$m$次是可能超时的,因为二元组总数(重复的算多个)可以非常多,但我们只需要确定是否存在重复的,所以遇到重复的就直接跳出,复杂度就变成了不重复二元组总数,只有$ O \left( \frac{n(n-1)}{2} \right) $。

不过吧……这题暴力好像可以过……

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n,m,L,R,mid,a[2010][2010],c[2010][2010];
bool used[2010][2010];
vector<int> v;
bool check()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]>=mid) c[i][j]=1;
else c[i][j]=0;
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++)
used[i][j]=false;
for(int i=1;i<=n;i++)
{
v.clear();
for(int j=1;j<=m;j++)
if(c[i][j]==1)
{
for(int k=0;k<v.size();k++)
{
if(used[v[k]][j]) return true;
used[v[k]][j]=true;
}
v.push_back(j);
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
L=0,R=1000000000;
while(L<R)
{
mid=(L+R+1)>>1;
if(check()) L=mid;
else R=mid-1;
}
printf("%d\n",L);
return 0;
}

E.Summer Earnings

平面上给定$n$个点,两点间距离是它们的欧几里得距离,求一个三角形内最小边的最大值除以$2$。

官方题解给的好像利用了几何性质,我没太看懂……

不过这个题还可以用bitset水过去!

考虑从大到小加边,每次判定图内是否有三元环,如果有那么答案就是这条边的权值。我们要做的是加速判断三元环是否存在。

新形成的三元环一定有一条边是刚加的这条边,然后存在一个点与这这条边两个端点都相邻。

bitset存一下每一个点与谁相邻就好了。

时间复杂度是$ O \left( \frac{n^3}{32} \right) $。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<bitset>
#include<cmath>
#define fi first
#define se second
using namespace std;
const int MAXN=3010;
int n,x[MAXN],y[MAXN],tot;
pair<double,pair<int,int> > P[MAXN*MAXN/2];
bitset<MAXN> B[MAXN],X;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
++tot;
P[tot].fi=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
P[tot].se.fi=i,P[tot].se.se=j;
}
sort(P+1,P+tot+1);
reverse(P+1,P+tot+1);
for(int i=1;i<=tot;i++)
{
X=B[P[i].se.fi]&B[P[i].se.se];
if(X.count()) {printf("%.010lf\n",P[i].fi/2);return 0;}
B[P[i].se.fi][P[i].se.se]=1;
B[P[i].se.se][P[i].se.fi]=1;
}
return 0;
}

很久以前就想自己搭个博客奈何自己太弱只好用用CSDN之类的……

现在终于扒教程什么的转到GitHub上啦!

数学公式:

$ E = m c^2 $