题A
题意：有三个地点，家h，超市s1和s2，然后给你三者之间的距离，然后问你从家遍历s1和s2之后又回到家的最短距离是多少？
题解：就四种情况。。。。手动模拟很快出来的。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 7 ll dist[5]; 8 9 int main() { 10 //freopen("case.in", "r", stdin); 11 ll d1, d2, d3; 12 cin >> d1 >> d2 >> d3; 13 dist[0] = d1 + d2 + d3; 14 dist[1] = d1 * 2 + d3 * 2; 15 dist[2] = d2 * 2 + d3 * 2; 16 dist[3] = d1 * 2 + d2 * 2; 17 cout << *min_element(dist, dist + 4) << endl; 18 return 0; 19 } 代码君
题B
题意：一开始有一个序列a1……am，然后取其中的一部分组成长度为n的序列，f1……fn，然后有序列b满足，现在给你序列f和序列b，问你能不能唯一地确定a，如果可以输出possible，并输出a序列，如果有多种答案，输出ambiguous，如果有不符合的情况就输出impossible；
题解：很显然，我们记录得到这个f值的下标，然后如果有多个f值对应同一个下标就记录一下，（代码中标记为-2），然后就遍历b来找这个对应f值的下标是否唯一，如果不唯一，如碰到-2就先记一下，因为可能后面出现不匹配的情况，也就是先遍历整个b序列看看有没有impossible，然后在判断有没有ambiguous，最后都没有才输出。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 1e5 + 100; 6 int vis[maxn], b[maxn], a[maxn]; 7 8 int main() { 9 //freopen("case.in", "r", stdin); 10 int n, m; 11 cin >> n >> m; 12 memset(vis, -1, sizeof vis); 13 for (int i = 1; i <= n; i++) { 14 int t; 15 scanf("%d", &t); 16 if (vis[t] == -1 && vis[t] != -2) vis[t] = i; 17 else vis[t] = -2; 18 } 19 for (int i = 1; i <= m; i++) scanf("%d", b + i); 20 bool ok = true; 21 for (int i = 1; i <= m; i++) { 22 if (vis[b[i]] == -1) { 23 puts("Impossible"); return 0; 24 } 25 if (vis[b[i]] == -2) ok = false; 26 else a[i] = vis[b[i]]; 27 } 28 if (!ok) { puts("Ambiguity"); return 0; } 29 puts("Possible"); 30 for (int i = 1; i <= m; i++) printf("%d ", a[i]); 31 return 0; 32 } 代码君
题C
题意：给你n个数，让你分块，使得块里面的数排完序之后就和这整个序列排完序的效果是一样的，问你最多分成多少块。
题解：假设这个序列已经排好序的话，那么答案就是n啦。这里我们用的是贪心的方法，我开了一个数据类型Node，里面的成员有now，cur，num。我们定义未排序的序列是h，排好序的序列是sh；我们用这个数据类型来表示当前块的开头，now指的是当前块中最大元素的序列h下标，cur指的是这个排好序的序列sh中这个元素出现的最开始的位置，num表示的就是这个元素出现的次数，初始化为1，显然cur+num-1就是这个元素在sh中的真实的位置，然后当循环到当前元素等于这个位置的话就说明已经到达块的末尾，所以只需要将块的个数加一，然后更新结点即可。还有一个要注意的就是，如果下一个元素出现的是一样的，那么不要更新为新的结点，而是num++，这里没注意会WA。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 1e5 + 100; 6 int h[maxn], sh[maxn]; 7 8 struct Node { 9 int now; 10 int cur; 11 int num; 12 }; 13 14 int main() { 15 //freopen("case.in", "r", stdin); 16 int n; 17 cin >> n; 18 for (int i = 0; i < n; i++) { 19 scanf("%d", h + i); 20 sh[i] = h[i]; 21 } 22 sort(sh, sh + n); 23 int ans = 0; 24 Node temp = (Node) {0, lower_bound(sh, sh + n, h[0]) - sh, 1}; 25 for (int i = 0; i < n; i++) { 26 if (i != temp.now) { 27 if (h[i] > h[temp.now]) temp = (Node) {i, lower_bound(sh, sh + n, h[i]) - sh, 1}; 28 else if (h[i] == h[temp.now]) temp.num++; 29 } 30 if (temp.cur + temp.num - 1 == i) { 31 ans++; 32 if (h[i + 1] != h[temp.now]) 33 temp = (Node) {i + 1, lower_bound(sh, sh + n, h[i + 1]) - sh, 1}; 34 } 35 } 36 printf("%d\n", ans); 37 return 0; 38 } 代码君
题D
题意：给你一个x表示方案数，所谓的方案就是指n * m的矩阵中，用1*1,2*2……在这个矩阵能移动的数目。找出这个移动的数目相加为x的所有满足的矩阵。
题解：有两种做法：
先说我想到的一种：n*m的组成方案就是：（k+1）*n*m + sigma（k*k）-sigma（k）*（n+m），这里的sigma是累加，k = min（n，m）-1，这个很容易推导，然后就枚举n，然后二分答案求出满足要求的m。这种做法很麻烦，有两个注意的地方，第一个是要用unsignedlonglong，第二是当满足n*n的情况要单独判断，因为精度关系。。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef unsigned long long ll; 6 const ll inf = 1e18 + 100; 7 vector<pair<ll, ll> > ans; 8 9 ll getSquareSum(ll i) { 10 return 1ULL * i * (i + 1) * (2 * i + 1) / 6; 11 } 12 13 ll get_num(ll x, ll y) { 14 ll k = min(x, y) - 1; 15 return 1ULL * (k + 1) * x * y + getSquareSum(k) - (x + y) * k * (1 + k) / 2; 16 } 17 18 int main() { 19 //freopen("case.in", "r", stdin); 20 ll n; 21 cin >> n; 22 for (ll i = 1; ; i++) { 23 ll temp = getSquareSum(i); 24 if (temp >= n) { 25 if (temp == n) ans.push_back(make_pair(i, i)); 26 break; 27 } 28 ll low = 1, high = n / i, mid; 29 bool ok = false; 30 while (low <= high) { 31 mid = low + (high - low) / 2; 32 ll t = get_num(i, mid); 33 //cout << x << " " << y << " " << t << endl; 34 if (t > n) high = mid - 1; 35 else if (t < n) low = mid + 1; 36 else { 37 ok = true; 38 break; 39 } 40 } 41 if (ok) ans.push_back(make_pair(i, mid)); 42 } 43 int size = ans.size(); 44 for (int i = size - 1; i >= 0; i--) 45 if (ans[i].first != ans[i].second) { 46 ans.push_back(make_pair(ans[i].second, ans[i].first)); 47 } 48 cout << ans.size() << endl; 49 for (int i = 0; i < (int)ans.size(); i++) 50 cout << ans[i].first << " " << ans[i].second << endl; 51 return 0; 52 } 代码君
参照题解，有一种更巧妙的做法：观察式子sigma（n-k）*（m-k），k = min（n，m）,我们先假设这个m=n的话，会算少什么，会算少（m-n）*k，（m-n）是固定值，然后k是可以写成累加的形式的，所以只要判断是否能够整数这个sigma（k*（m-n）），也就是是否能够整除这个sigma（k） = n*（n - 1） / 2，复杂度是O（n）；
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 7 vector<pair<ll, ll> > ans; 8 9 int main() { 10 //freopen("case.in", "r", stdin); 11 ll x; 12 cin >> x; 13 for (ll n = 1; x > 0; n++) { 14 x -= n * n; 15 ll t = n * (n + 1) / 2; 16 if (x % t == 0) { 17 ans.push_back(make_pair(n, x / t + n)); 18 ans.push_back(make_pair(x / t + n, n)); 19 } 20 } 21 sort(ans.begin(), ans.end()); 22 ans.erase(unique(ans.begin(), ans.end()), ans.end()); 23 int size = ans.size(); 24 printf("%d\n", size); 25 for (int i = 0; i < size; i++) 26 cout << ans[i].first << " " << ans[i].second << endl; 27 return 0; 28 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5060777.html
