AGC004

link

A

有一个$a\times b\times c$个正方体堆成的长方体,要求切成两个长方体,使得不存在一个正方体被切开,并使得两边正方体个数差最小。

如果$a,b,c$是偶数则答案为0.

否则为$\min(ab,bc,ac)$。

B

Snuke想得到$n$个颜色的史莱姆各一只。

为了得到这些史莱姆,Snuke可以进行两种操作:

  1. 抓一个$i$颜色的史莱姆,代价$a_i$。
  2. 用一个膜法,把所有$i$色史莱姆变成$i+1$色,$n$色史莱姆变成1色,代价$x$

求最少代价。

枚举用膜法的次数$m$,

令$a_{i+n}=a_i$,则最终获得$i$色史莱姆的最小代价是$\min(a_{i-m},\dots a_i)$

直接计算即可。

C

有一个$W\times H$的方格纸,Snuke在上面画了一个红色的联通块,Ciel在上面画了一个蓝色的联通块。红色和蓝色加在一起会变成紫色。

告诉你哪些块是紫色,求Snuke和Ciel的一种画的方案使得最后得到的紫色块恰好是这些。

保证最外面一圈不是紫色。

首先先构造一个基础方案,使得无紫色方案,并且所有可能紫色的格子都和红色蓝色分别联通。

那就第一行涂红色,最后一行涂蓝色,然后中间奇数列红色偶数列蓝色!

然后紫色的?直接涂上两个颜色啊

显然这个是对的。

D

一个国家有$n$个城市,其中1号是首都。

每个城市有一个传送门,第$i$个城市的传送门可以从i城市传送到$a_i$城市($a_i$可以$=i$),保证所有城市都能经过一次或多次传送到达首都。

国王Snuke喜欢一个数字$k$,他自私地希望修改一个传送门的$a_i$,使得每个城市传送$k$次的时候都在首都。

求最少修改的传送门数。

(首都也有传送门)

如果$1$ $k$次 可以到达1,则$a_1$ $k$次会到达$a_1$。所以显然$a_1=1$。

然后就得到了一棵以1为根的树,然后要求修改最少点的父亲使得每个点的深度$\le k$。

一个经典的贪心:每次选出最深的点把它的$k-1$级祖先的祖先改成1。

E

一个$W\times H$的网格,其中有一个出口,有一些位置是机器人。

每次你可以命令所有机器人全部向上/下/左/右移动一个单位,然后一个机器人到达出口的时候就被你救出来了,到网格外面就爆炸,你就不可能救出来了。

求最多救出的机器人个数。

DP,设$f_{a,b,c,d}$表示最多右移a个单位,左移b个,上移c个,下移d个最多救出来的机器人个数。

转移的时候从$f_{a-1,b,c,d},f_{a,b-1,c,d},f_{a,b,c-1,d},f_{a,b,c,d-1}$转移过来。

F

你有一个$n$点$m$边的简单联通图($n-1\le m\le n$)。起初每个点都是白色,你每次可以将两端同色的一条边两端同时反色,求使所有点变成黑色的最小操作数。

就是说可能是树或基环树。

树是一个二分图。

假设在树上深度为奇数的点上放一个硬币。

那么原来的两端同色的一条边反色,就相当于把一个硬币移到相邻没有硬币的点。

假设硬币是1,空点是-1,那么每个点对答案的贡献就是它子树和的绝对值。

为什么?

因为要想子树中每个点状态翻转,必须硬币数量和空点数量是一样的。

如果多了硬币,就可以在子树根处移出去。如果少了硬币,就可以从外面移到子树根,所以子树根对外的最少操作数就是子树和的绝对值,显然这个下限是可以取到的。

环是奇环

取出奇环上一条边,则剩下的还是一棵树。

显然在这条边上操作,相当于加上两个硬币或去掉两个硬币。

那么就可以算出这条边需要的操作次数,然后就和树一样了。

环是偶环

取出偶环上一条边$a\rightarrow b$,则剩下的还是一棵树。

假设树上$b​$是$a​$的祖先

设$a$给了$b$ $x$个硬币(x可以为负)

则$a$到$b$的路径(不包含b)外点子树和不变,路径上点子树和加$x$

然后就是要使$|x|+\sum |x-a_i|$最小。

显然$x$就是$a_i$和0取中位数。

Code

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int main(){
#ifdef QAQAutoMaton
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
ll a,b,c;
read(a,b,c);
if(a&1 && b&1 && c&1){
write(min(a*b,min(a*c,b*c)),'\n');
}
else write("0\n");

return 0;
}

B

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll a[2005],f[2005],x,c,ans;
int main(){
#ifdef QAQAutoMaton
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
ll n;
read(n,x);
for(ll i=1;i<=n;++i){read(a[i]);f[i]=a[i];}
ans=(ll)1e18;
for(ll i=0;i<n;++i){
c=i*x;
for(ll j=1;j<=n;++j)c+=f[j];
chkmin(ans,c);
for(ll j=1;j<=n;++j)chkmin(f[j],a[(i+j)%n+1]);
}
write(ans,'\n');
return 0;
}

C

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
while((x=gc())==' '||x=='\n'||x=='\r');
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int r[505][505],b[505][505];
int main(){
#ifdef QAQAutoMaton
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
int n,m;
read(n,m);
char c;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
r[i][j]=(i!=n) && ((i==1)||(j&1));
b[i][j]=(i!=1) && ((i==n)||(!(j&1)));
read(c);
if(c=='#')r[i][j]=b[i][j]=1;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)write(r[i][j]?'#':'.');
write('\n');
}
write('\n');
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)write(b[i][j]?'#':'.');
write('\n');
}
return 0;
}

D

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int n,k;
int to[100005],dis[100005],c,ans;
vector<int> son[100005];
int q[100005],del[100005];
int work(int x){
if(x==1)return 0;
if(dis[x])return dis[x];
dis[x]=work(to[x])+1;
return dis[x];
}
int u1(){
ans=to[1]!=1;
for(int i=2;i<=n;++i)work(i);
return ans;
}
void remove(int x){
if(del[x])return;
del[x]=1;
for(auto i:son[x])remove(i);
}
int main(){
#ifdef QAQAutoMaton
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
#endif
read(n,k);
--k;
for(int i=1;i<=n;++i)read(to[i]);
ans=to[1]!=1;
to[1]=1;
for(int i=2;i<=n;++i){son[to[i]].push_back(i);work(i);q[i]=i;}
sort(q+2,q+n+1,cmp_a<dis>);
for(int *l=q+2,*r=q+n,x;l<=r;--r){
if(dis[*r]<=k+1)break;
if(del[*r])continue;
x=*r;
for(int i=k;i;--i)x=to[x];
remove(x);
++ans;
}
write(ans,'\n');
return 0;
}

E

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: e.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
while((x=gc())=='\n' || x==' '||x=='\r');
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[105][105],f[2][105][105][105],b[105][105];
int main(){
#ifdef QAQAutoMaton
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
#endif
int n,m,x,y;
char c;
read(n,m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
read(c);
if(c=='E')x=i,y=j;
a[i][j]=c=='o';
b[i][j]=c=='o';
a[i][j]+=a[i][j-1];
b[i][j]+=b[i-1][j];
}
int ans=0;
for(int xl=0,t=0;xl<x;++xl,t^=1){
for(int xr=0;xr<=n-x;++xr){
for(int yl=0;yl<y;++yl){
for(int yr=0;yr<=m-y;++yr){
f[t][xr][yl][yr]=0;
if(xl)
chkmax(f[t][xr][yl][yr],
f[t^1][xr][yl][yr]+
(xr>=x-xl?0:max(0,a[x-xl][min(y+yr,m-yl)]-a[x-xl][max(y-yl-1,yr)]))
);
if(xr)
chkmax(f[t][xr][yl][yr],
f[t][xr-1][yl][yr]+
(xl+xr>n-x?0:max(0,a[x+xr][min(y+yr,m-yl)]-a[x+xr][max(y-yl-1,yr)]))
);
if(yl)
chkmax(f[t][xr][yl][yr],
f[t][xr][yl-1][yr]+
(yl+yr>=y?0:max(0,b[min(x+xr,n-xl)][y-yl]-b[max(x-xl-1,xr)][y-yl]))
);
if(yr)
chkmax(f[t][xr][yl][yr],
f[t][xr][yl][yr-1]+
(yl+yr>m-y?0:max(0,b[min(x+xr,n-xl)][y+yr]-b[max(x-xl-1,xr)][y+yr]))
);
chkmax(ans,f[t][xr][yl][yr]);
}
}
}
}
write(ans,'\n');
return 0;
}

F

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
/*
Author: QAQ-Automaton
LANG: C++
PROG: f.cpp
Mail: cnyalilk@vip.qq.com */
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll inf=1e12;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll f[100005][2],tag[100005],OddCircle;
ll cnt[100005];
vector<ll> son[100005],QAQ[100005];
void dfs(ll x,ll flg){
if(tag[x]){if(tag[x]!=flg)OddCircle=1;return;}
tag[x]=flg;
for(auto i:son[x])dfs(i,-flg);
}
ll vis[100005],fa[100005];
void dfs2(ll x,ll fa){
vis[x]=1;
cnt[x]=tag[x];
for(auto i:son[x])if(i!=fa && !vis[i]){
dfs2(i,x);
cnt[x]+=cnt[i];
}
}
namespace Tree{
void main(ll n){
dfs2(1,0);
if(cnt[1]){write("-1\n");return;}
ll ans=0;
for(ll i=1;i<=n;++i)ans+=abs(cnt[i]);
write(ans,'\n');
}
}
pii E;
void gete(ll x,ll f){
fa[x]=f;
vis[x]=1;
cnt[x]=tag[x];
for(auto i:son[x])if(i!=f){
if(!vis[i]){
gete(i,x);
cnt[x]+=cnt[i];
}
else{
E=make_pair(x,i);
}
}
}
namespace Odd{
void main(ll n){
gete(1,0);
if(cnt[1]%2){write("-1\n");return;}
tag[E.x]-=cnt[1]>>1;
tag[E.y]-=cnt[1]>>1;
ll ans=abs(cnt[1]>>1);
for(ll i=1;i<=n;++i)vis[i]=0;
dfs2(1,0);
for(ll i=1;i<=n;++i)ans+=abs(cnt[i]);
write(ans,'\n');
}
}
namespace Even{
ll a[100005];
void main(ll n){
gete(1,0);
if(cnt[1]){write("-1\n");return;}
for(ll i=1;i<=n;++i)vis[i]=0;
ll ans=0,t=0;
for(ll i=1;i<=n;++i)ans+=abs(cnt[i]);
ll u=E.x,v=E.y;
for(;u&&u!=v;u=fa[u]);
if(u==v)u=E.x;
else{
u=E.y;
v=E.x;
}
for(;u!=v;u=fa[u]){
ans-=abs(cnt[u]);
a[++t]=cnt[u];
}
a[++t]=0;
sort(a+1,a+t+1);
ll mid=(t+1)>>1;
for(ll i=1;i<=t;++i)ans+=abs(a[i]-a[mid]);
write(ans,'\n');
}
}
int main(){
#ifdef QAQAutoMaton
freopen("f.in","r",stdin);
freopen("f.out","w",stdout);
#endif
ll n,m,u,v;
read(n,m);
for(;m;--m){
read(u,v);
son[u].push_back(v);
son[v].push_back(u);
}
dfs(1,1);
if(n==m+1)Tree::main(n);
else if(OddCircle)Odd::main(n);
else Even::main(n);
return 0;

}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×