20182019ACMICPC,AsiaNakhonPathomRegionalContest部分题解

1 #include
2 using namespace std ;
3 int main()
4 {
5 std::ios::sync_with_stdio(false) , cin.tie(0) ;
6 int T ;
7 cin >> T ;
8 while(T --)
9 {
10 int n ;
11 cin >> n ;
12 vector a(n + 1) ;
13 for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
14 int lst = -100000 ;
15 int ans = 0 ;
16 for(int i = 1 ; i <= n ; i ++)
17 {
18 if(abs(a[i] - lst) <= 10) continue ;
19 else lst = a[i] + 10 , ans ++ ;
20 }
21 cout <22 }
23 return 0 ;
24 }
View Code

Problem E How many groups

本来写了$200$多行的分类讨论，虽然过了，不过很不爽。

看了别人代码发现是个简单$dp$，感觉失去了一个亿。

分类讨论。

1 #include
2 using namespace std ;
3 int n ;
4 int a[105] ;
5 int l[105] ;
6 int r[105] ;
7 int c[2] = {-1 , 1} ;
8 int d[4] = {-1 , 1 , 0 , 0} ;
9 int e[4] = {0 , 0 , -1 , 1} ;
10 int cal1(int i)
11 {
12 int res = 1 ;
13 if(i - 1 >= 1 && abs(a[i - 1] - a[i]) <= 2) res += ((i - 1) - l[i - 1] + 1) ;
14 if(i + 1 <= n && abs(a[i + 1] - a[i]) <= 2) res += (r[i + 1] - (i + 1) + 1) ;
15 return res ;
16 }
17 int cal2(int i , int j)
18 {
19 if(abs(a[i] - a[j]) > 2) return 0 ;
20 int res = 2 ;
21 if(i - 1 >= 1 && abs(a[i - 1] - a[i]) <= 2) res += ((i - 1) - l[i - 1] + 1) ;
22 if(j + 1 <= n && abs(a[j + 1] - a[j]) <= 2) res += (r[j + 1] - (j + 1) + 1) ;
23 return res ;
24 }
25 int main()
26 {
27 std::ios::sync_with_stdio(false) , cin.tie(0) ;
28 int T ;
29 cin >> T ;
30 for(int cas = 1 ; cas <= T ; cas ++)
31 {
32 cout <<"Case " < 33 cin >> n ;
34 for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
35 sort(a + 1 , a + n + 1) ;
36 int ans = 0 ;
37 for(int i = 1 ; i <= n ; i ++)
38 {
39 int j = i ;
40 while(j + 1 <= n && a[j + 1] - a[j] <= 2) j ++ ;
41 for(int k = i ; k <= j ; k ++) l[k] = i , r[k] = j ;
42 ans = max(ans , j - i + 1) ;
43 i = j ;
44 }
45 for(int i = 1 ; i <= n ; i ++)
46 {
47 int tmp = a[i] ;
48 for(int j = 0 ; j <2 ; j ++)
49 {
50 a[i] = tmp + c[j] ;
51 ans = max(ans , cal1(i)) ;
52 }
53 a[i] = tmp ;
54 }
55 for(int i = 1 ; i <= n - 1 ; i ++)
56 {
57 int tmp1 = a[i] ;
58 int tmp2 = a[i + 1] ;
59 for(int j = 0 ; j <2 ; j ++)
60 for(int k = 0 ; k <2 ; k ++)
61 {
62 a[i] = tmp1 + c[j] ;
63 a[i + 1] = tmp2 + c[k] ;
64 ans = max(ans , cal2(i , i + 1)) ;
65 }
66 a[i] = tmp1 ;
67 a[i + 1] = tmp2 ;
68 }
69 //cout < 70 for(int i = 1 ; i <= n ; i ++)
71 {
72 int res = 1 ;
73 a[i] ++ ;
74 if(i + 1 <= n)
75 {
76 if(i - 1 >= 1 && abs(a[i] - a[i - 1]) <= 2) res += (i - 1) - l[i - 1] + 1 ;
77 ans = max(ans , res) ;
78 if(abs(a[i] - a[i + 1]) <= 2)
79 {
80 res += r[i + 1] - (i + 1) + 1 ;
81 ans = max(ans , res) ;
82 int nxt = r[i + 1] ;
83 //cout < 84 if(nxt + 1 <= n)
85 {
86 int tmp1 = a[nxt] ;
87 int tmp2 = a[nxt + 1] ;
88 for(int j = 0 ; j <4 ; j ++)
89 {
90 a[nxt] = tmp1 + d[j] ;
91 a[nxt + 1] = tmp2 + e[j] ;
92 int tt = res ;
93 if(abs(a[nxt] - a[nxt + 1]) <= 2)
94 {
95 if(abs(a[nxt] - a[nxt - 1]) <= 2)
96 {
97 tt ++ ;
98 //cout < 99 if(nxt + 2 <= n && abs(a[nxt + 1] - a[nxt + 2]) <= 2)
100 {
101 tt += r[nxt + 2] - (nxt + 2) + 1 ;
102 }
103 ans = max(ans , tt) ;
104 }
105 }
106 }
107 a[nxt] = tmp1 ;
108 a[nxt + 1] = tmp2 ;
109 }
110 }
111 }
112 a[i] -- ;
113
114 res = 1 ;
115 a[i] -- ;
116 if(i + 1 <= n)
117 {
118 if(i - 1 >= 1 && abs(a[i] - a[i - 1]) <= 2) res += (i - 1) - l[i - 1] + 1 ;
119 ans = max(ans , res) ;
120 if(abs(a[i] - a[i + 1]) <= 2)
121 {
122 res += r[i + 1] - (i + 1) + 1 ;
123 ans = max(ans , res) ;
124 int nxt = r[i + 1] ;
125 //cout <126 if(nxt + 1 <= n)
127 {
128 int tmp1 = a[nxt] ;
129 int tmp2 = a[nxt + 1] ;
130 for(int j = 0 ; j <4 ; j ++)
131 {
132 a[nxt] = tmp1 + d[j] ;
133 a[nxt + 1] = tmp2 + e[j] ;
134 int tt = res ;
135 if(abs(a[nxt] - a[nxt + 1]) <= 2)
136 {
137 if(abs(a[nxt] - a[nxt - 1]) <= 2)
138 {
139 tt ++ ;
140 //cout <141 if(nxt + 2 <= n && abs(a[nxt + 1] - a[nxt + 2]) <= 2)
142 {
143 tt += r[nxt + 2] - (nxt + 2) + 1 ;
144 }
145 ans = max(ans , tt) ;
146 }
147 }
148 }
149 a[nxt] = tmp1 ;
150 a[nxt + 1] = tmp2 ;
151 }
152 }
153 }
154 a[i] ++ ;
155 }
156 //cout <157 for(int i = 1 ; i <= n ; i ++)
158 {
159 a[i] -- ;
160 int res = 1 ;
161 if(i - 1 >= 1)
162 {
163 if(i + 1 <= n && abs(a[i] - a[i + 1]) <= 2) res += r[i + 1] - (i + 1) + 1 ;
164 ans = max(ans , res) ;
165 if(abs(a[i] - a[i - 1]) <= 2)
166 {
167 res += (i - 1) - l[i - 1] + 1 ;
168 ans = max(ans , res) ;
169 int nxt = l[i - 1] ;
170 if(nxt - 1 >= 1)
171 {
172 int tmp1 = a[nxt] ;
173 int tmp2 = a[nxt - 1] ;
174 for(int j = 0 ; j <4 ; j ++)
175 {
176 int tt = res ;
177 a[nxt] = tmp1 + d[j] ;
178 a[nxt - 1] = tmp2 + e[j] ;
179 if(abs(a[nxt] - a[nxt - 1]) <= 2)
180 {
181 if(abs(a[nxt] - a[nxt + 1]) <= 2)
182 {
183 tt ++ ;
184 if(nxt - 2 >= 1 && abs(a[nxt - 1] - a[nxt - 2]) <= 2)
185 {
186 tt += (nxt - 2) - l[nxt - 2] + 1 ;
187 }
188 ans = max(ans , tt) ;
189 }
190 }
191 }
192 a[nxt] = tmp1 ;
193 a[nxt - 1] = tmp2 ;
194 }
195 }
196 }
197 a[i] ++ ;
198
199 a[i] ++ ;
200 res = 1 ;
201 if(i - 1 >= 1)
202 {
203 if(i + 1 <= n && abs(a[i] - a[i + 1]) <= 2) res += r[i + 1] - (i + 1) + 1 ;
204 ans = max(ans , res) ;
205 if(abs(a[i] - a[i - 1]) <= 2)
206 {
207 res += (i - 1) - l[i - 1] + 1 ;
208 ans = max(ans , res) ;
209 int nxt = l[i - 1] ;
210 if(nxt - 1 >= 1)
211 {
212 int tmp1 = a[nxt] ;
213 int tmp2 = a[nxt - 1] ;
214 for(int j = 0 ; j <4 ; j ++)
215 {
216 int tt = res ;
217 a[nxt] = tmp1 + d[j] ;
218 a[nxt - 1] = tmp2 + e[j] ;
219 if(abs(a[nxt] - a[nxt - 1]) <= 2)
220 {
221 if(abs(a[nxt] - a[nxt + 1]) <= 2)
222 {
223 tt ++ ;
224 if(nxt - 2 >= 1 && abs(a[nxt - 1] - a[nxt - 2]) <= 2)
225 {
226 tt += (nxt - 2) - l[nxt - 2] + 1 ;
227 }
228 ans = max(ans , tt) ;
229 }
230 }
231 }
232 a[nxt] = tmp1 ;
233 a[nxt - 1] = tmp2 ;
234 }
235 }
236 }
237 a[i] -- ;
238 }
239 cout <240 }
241 return 0 ;
242 }
View Code

$dp[i][j][k]$表示前$i$个数修改了$j$次且第$i$个数是$a[i]+k-1$的以$i$为右端点的最大连续段长度。

1 #include
2 using namespace std ;
3 int n , a[105] ;
4 int dp[105][3][3] ;
5 int main()
6 {
7 std::ios::sync_with_stdio(false) , cin.tie(0) ;
8 int T ;
9 cin >> T ;
10 for(int cas = 1 ; cas <= T ; cas ++)
11 {
12 cout <<"Case " <13 cin >> n ;
14 for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
15 sort(a + 1 , a + n + 1) ;
16 for(int i = 0 ; i <= n ; i ++)
17 for(int j = 0 ; j <= 2 ; j ++)
18 for(int k = 0 ; k <= 2 ; k ++)
19 dp[i][j][k] = -1e9 ;
20 int fix = 1 ;
21 for(int i = 1 ; i <= n ; i ++)
22 {
23 dp[i][0][fix + 0] = 1 ;
24 dp[i][1][fix - 1] = 1 ;
25 dp[i][1][fix + 1] = 1 ;
26 }
27 for(int i = 1 ; i 28 for(int j = 0 ; j <= 2 ; j ++)
29 for(int k = 0 ; k <= 2 ; k ++)
30 for(int p = j ; p <= 2 ; p ++)
31 for(int t = 0 ; t <= 2 ; t ++)
32 {
33 if(dp[i][j][k] <0) continue ;
34 int now = a[i] + k - fix ;
35 int nxt = a[i + 1] + t - fix ;
36 if(abs(now - nxt) <= 2 && (j + abs(t - fix)) == p)
37 {
38 dp[i + 1][p][t] = max(dp[i + 1][p][t] , dp[i][j][k] + 1) ;
39 }
40 }
41 int ans = 0 ;
42 for(int i = 1 ; i <= n ; i ++)
43 for(int j = 0 ; j <= 2 ; j ++)
44 for(int k = 0 ; k <= 2 ; k ++)
45 ans = max(ans , dp[i][j][k]) ;
46 cout <47 }
48 return 0 ;
49 }
View Code

Problem F Lucky Pascal Triangle

留坑。

Problem G Communication

题面的英语写的过于上等。没说$message$是可传递的，然后写了个并查集果然$WA$了。

反应过来如果可以传递就是一个$SCC$，贴个板子就过了。

1 #include
2 using namespace std ;
3 const int maxn = 200 + 10 ;
4 const int maxm = 10000 + 10 ;
5 int n ;
6 struct Link
7 {
8 int num , head[maxn] ;
9 struct Edge
10 {
11 int v , next ;
12 } edge[maxm <<1] ;
13 void init()
14 {
15 num = 0 ;
16 memset(head , -1 , sizeof(head)) ;
17 }
18 void add_edge(int u , int v)
19 {
20 edge[num].v = v ;
21 edge[num].next = head[u] ;
22 head[u] = num ++ ;
23 }
24 } link ;
25 struct Tarjan
26 {
27 int cnt , scc_num , lay ;
28 int low[maxn] , dfn[maxn] , belong[maxn] ;
29 int st[maxn] , s[maxn] ;
30 bool vis[maxn] ;
31 void init()
32 {
33 cnt = scc_num = lay = 0 ;
34 memset(vis , 0 , sizeof(vis)) ;
35 memset(low , 0 , sizeof(low)) ;
36 memset(dfn , 0 , sizeof(dfn)) ;
37 }
38 void dfs(int k)
39 {
40 vis[k] = 1 ;
41 low[k] = dfn[k] = ++ lay ;
42 st[++ cnt] = k ;
43 for(int i = link.head[k] ; i != -1 ; i = link.edge[i].next)
44 {
45 int v = link.edge[i].v ;
46 if(dfn[v] == 0)
47 {
48 dfs(v) ;
49 low[k] = min(low[k] , low[v]) ;
50 }
51 else if(vis[v])
52 low[k] = min(low[k] , dfn[v]) ;
53 }
54 if(dfn[k] == low[k])
55 {
56 ++ scc_num ;
57 do
58 {
59 belong[st[cnt]] = scc_num ;
60 vis[st[cnt]] = 0 ;
61 cnt -- ;
62 } while(st[cnt + 1] != k) ;
63 }
64 }
65 void cal()
66 {
67 for(int i = 1 ; i <= n ; i ++)
68 if(dfn[i] == 0) dfs(i) ;
69 }
70 } tarjan ;
71 int main()
72 {
73 std::ios::sync_with_stdio(false) , cin.tie(0) ;
74 int T ;
75 cin >> T ;
76 while(T --)
77 {
78 cin >> n ;
79 link.init() ;
80 tarjan.init() ;
81 int e ;
82 cin >> e ;
83 for(int i = 1 ; i <= e ; i ++)
84 {
85 int u , v ;
86 cin >> u >> v ;
87 u ++ ;
88 v ++ ;
89 link.add_edge(u , v) ;
90 }
91 tarjan.cal() ;
92 cout <93 }
94 return 0 ;
95 }
View Code

Problem H As rich as Crassus

留坑。

Problem I Bowabowaukulipukuli

留坑。

Problem J Floating-Point Hazard

需要看出来这是求导定义式的分子。

$f(x)=x^{\frac{1}{3}}$，求导后得到$f^{'}(x)$。

答案是$\sum f^{'}(i)*(10^{-15})$。

1 #include
2 using namespace std ;
3 #define ld long double
4 int main()
5 {
6 std::ios::sync_with_stdio(false) , cin.tie(0) ;
7 while(1)
8 {
9 int l , r ;
10 scanf("%d%d" , &l , &r) ;
11 if(l == 0 && r == 0) break ;
12 ld ans = 0 ;
13 for(int i = l ; i <= r ; i ++) ans += pow(i , -2.0 / 3.0) ;
14 ans /= 3.0 ;
15 int res = 15 ;
16 while(ans >= 10.0) ans /= 10 , res -- ;
17 while(ans <1.0) ans *= 10 , res ++ ;
18 printf("%.5LfE-" , ans) ;
19 printf("%03d\n" , res) ;
20 }
21 return 0 ;
22 }
View Code

Problem K The Stream of Corning 2

裸的第$k$大。

1 #include
2 #define all(x) begin(x), end(x)
3 using namespace std;
4 const int N = 1e5 + 5;
5 const int MAXSIZE = 1 <<20;
6 char buf[MAXSIZE], *p1, *p2;
7 inline char gc() { return (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2) ? EOF : *p1++); }
8 inline void read(int& t)
9 {
10 t = 0; char c = gc();
11 while(c>'9'||c<'0') c = gc();
12 while(c>='0'&&c<='9') t = t*10 + c - 48, c = gc();
13 }
14 bool qry[N];
15 int kas;
16 int n, ans[N];
17 struct Event
18 {
19 int t, v, op;
20 bool operator <(const Event& oth) { return t==oth.t ? op 21 }e[N<<1];
22 struct seg
23 {
24 int l, r, cnt;
25 }t[N<<2];
26 void up(int p) { t[p].cnt = t[p<<1].cnt + t[p<<1|1].cnt; }
27 void build(int p, int l, int r)
28 {
29 t[p].l = l, t[p].r = r, t[p].cnt = 0;
30 if(l==r) return;
31 int mid = (l+r)>>1;
32 build(p<<1, l, mid); build(p<<1|1, mid+1, r);
33 }
34 void upd(int p, int x, int v)
35 {
36 int l = t[p].l, r = t[p].r;
37 if(l==r)
38 {
39 t[p].cnt += v;
40 return;
41 }
42 int mid = (l+r) >> 1;
43 if(x<=mid) upd(p<<1, x, v);
44 else upd(p<<1|1, x, v);
45 up(p);
46 }
47 int ask(int p, int k)
48 {
49 int l = t[p].l, r = t[p].r;
50 if(l==r) return t[p].cnt>=k ? l : -1;
51 if(t[p<<1].cnt>=k) return ask(p<<1, k);
52 else return ask(p<<1|1, k-t[p<<1].cnt);
53 }
54 void solve()
55 {
56 read(n);
57 int m = 0;
58 vector lsh;
59 auto getid = [&](int x) { return lower_bound(all(lsh), x) - begin(lsh) + 1; };
60 for(int i=1; i<=n; i++)
61 {
62 qry[i] = 0;
63 int op; read(op);
64 if(op==1)
65 {
66 int l, v, r; read(l), read(v), read(r);
67 e[++m] = {l, v, 1};
68 e[++m] = {r+1, v, -1};
69 lsh.push_back(v);
70 }
71 else
72 {
73 qry[i] = 1;
74 int t, k; read(t), read(k);
75 e[++m] = {t, k, i+1};
76 }
77 }
78 sort(all(lsh));
79 lsh.resize(unique(all(lsh)) - begin(lsh));
80 build(1, 1, (int)lsh.size());
81 sort(e+1, e+m+1);
82 for(int i=1; i<=m; i++)
83 {
84 if(e[i].op<=1) upd(1, getid(e[i].v), e[i].op);
85 else ans[e[i].op-1] = ask(1, e[i].v);
86 }
87 printf("Case %d:\n", ++kas);
88 for(int i=1; i<=n; i++)
89 if(qry[i])
90 {
91 if(ans[i]==-1) puts("-1");
92 else printf("%d\n", lsh[ans[i]-1]);
93 }
94 }
95 int main()
96 {
97 int _; read(_);
98 while(_--) solve();
99 return 0;
100 }
View Code

Problem L Largest Allowed Area

看作二维平面上的点，在斜率是$-1$的直线上进行双指针扫描，以$L$作为左上角的点，$R$作为右下角的点。前缀和预处理后可以$O(1)$判断正方形内$1$的个数。

不过这题卡常，需要快读。

1 #include
2 using namespace std;
3 const int N = 1e3 + 5, inf = 1e9;
4 int n, m;
5 int a[N][N], r[N][N], s[N][N];
6 int qry(int x1, int y1, int x2, int y2) { return s[x2][y2]+s[x1-1][y1-1]-s[x2][y1-1]-s[x1-1][y2]; }
7 inline void read(int& t)
8 {
9 t = 0;
10 char c = getchar();
11 while(c>'9'||c<'0') c = getchar();
12 while(c>='0'&&c<='9') t = t*10 + c - 48, c = getchar();
13 }
14 void solve()
15 {
16 read(n), read(m);
17 for(int i=1; i<=n; i++)
18 for(int j=1; j<=m; j++) read(a[i][j]), s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
19 for(int i=0; i<=n; i++)
20 for(int j=0; j<=m; j++) r[i][j] = i;
21 int ans = 0;
22 for(int i=1; i<=n; i++)
23 {
24 for(int j=1; j<=m; j++)
25 {
26 int rgt = r[i-1][j-1];
27 while(rgt+1<=i && qry(rgt+1, rgt+1+j-i, i, j)>1) rgt++;
28 ans = max(ans, i-rgt);
29 r[i][j] = rgt;
30 }
31 }
32 printf("%d\n", ans);
33 }
34 int main()
35 {
36 int _; read(_);
37 while(_--) solve();
38 return 0;
39 }
View Code