Changchun 2015

作为观摩队伍参加了比赛……最后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;
}