Water The Garden
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; typedef queue<int> QI; void makedata() { freopen("input.txt", "w", stdout); fclose(stdout); } int x[300]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n, k, t; cin >> t; while (t--) { cin >> n >> k; int ans = 0; for (int i = 0; i < k; i++) cin >> x[i]; ans = max(ans, x[0]); ans = max(ans, n - x[k - 1] + 1); for (int i = 1; i < k; i++) ans = max(ans, (x[i] - x[i - 1] + 2) / 2); cout << ans << endl; } return 0; }
Tea Queue
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; typedef queue<int> QI; void makedata() { freopen("input.txt", "w", stdout); fclose(stdout); } int l[2000], r[2000]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n, t; cin >> t; while (t--) { cin >> n; for (int i = 0; i < n; i++) cin >> l[i] >> r[i]; int time = 0; for (int i = 0; i < n; i++) { if (time < l[i]) time = l[i]; if (time > r[i]) { cout << 0 << ' '; continue; } cout << time << ' '; time++; } cout << endl; } return 0; }
Swap Adjacent Elements
显然一段1+0子段是可以变换为任意顺序的，而各个1+0中间单独存在的0必须满足a[i]=i时才能完成排序。对于某一段1+0子段，假设对应区间为a[i]~a[j]由于它无法与其他子段发生交换，所以a[i]~a[j]中的数字必须由i~j组成。
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; typedef queue<int> QI; void makedata() { freopen("input.txt", "w", stdout); fclose(stdout); } int a[220000], p[220000], b[220000]; bool f[220000]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; p[a[i]] = i; } char ch; for (int i = 1; i < n; i++) { cin >> ch; b[i] = ch - '0'; } b[n] = 0; bool ok = true; int ptr = 1; while (ptr <= n) { if (b[ptr] == 0) { if (a[ptr] != ptr) ok = false; ptr++; } else { int l = ptr; while (b[ptr] == 1) ptr++; int r = ptr; for (int i = l; i <= r; i++) f[i] = false; for (int i = l; i <= r; i++) f[a[i]] = true; for (int i = l; i <= r; i++) if (!f[i]) ok = false; ptr++; } } if (ok) cout << "YES" << endl; else cout << "NO" << endl; return 0; }
Tanks
如果所有的水箱中水量加起来不到v，则方案不存在。
首先选出若干个水箱，他们当前的水量加起来与v对k取余相同，若选不出来，则方案不存在。
对于选出的水箱，首先把这部分水箱中的水集中在一起，然后把其余的水箱中的水集中在一起，然后再舀回若干次k即可。
代码鸽了。
Connected Components
观察一下这个数据，其实挺搞笑的。对于小数据，怎么搞都可以。对于n和m都是20w的大数据，其答案肯定是199990+和几个一位数组成。
对于大小是S1和S2的两个强联通分量，其中的不直连关系至少要有S1*S2个。对于给定条件，每个点都缺少若干条边，其中有一个缺少的边数量最少的点，设为r，r缺边数量设为p。p能有多少呢？如果p能上万，那有缺边现象的点就不会超过20个。所以p估计也就是个四五百顶天了，那么最大的一个强联通分量就已经直接预订了这（n-四五百）这么多的点。
对于剩下的点，先不考虑外面，把他们内部的强连通分量分别算出来，然后对于每个强联通分量，如果其中一个点有连向外部的边，那么它属于最大的强联通分量的一部分，否则就是一个独立的真强联通分量。
代码鸽了
SUM and REPLACE
List of Integers