首页 > 代码库 > 青岛理工大学第五届ACM交流赛 部分题解
青岛理工大学第五届ACM交流赛 部分题解
A：后缀维护si*pi的最小值，查询的时候二分，判断后缀和当前两个部分就行。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 100100; 6 int n, m; 7 LL s[maxn], p[maxn]; 8 LL suf[maxn]; 9 10 int main() { 11 // freopen("in", "r", stdin); 12 int T; 13 LL q; 14 scanf("%d", &T); 15 while(T--) { 16 scanf("%d%d",&n,&m); 17 memset(suf, 0, sizeof(suf)); 18 for(int i = 0; i < n; i++) scanf("%lld%lld",&s[i],&p[i]); 19 suf[n-1] = s[n-1] * p[n-1]; 20 for(int i = n - 2; i >= 0; i--) suf[i] = min(suf[i+1], s[i]*p[i]); 21 s[n] = 100000000000000LL; suf[n] = 100000000000000LL; 22 while(m--) { 23 scanf("%lld", &q); 24 int pos = lower_bound(s, s+n+1, q) - s; 25 // if(s[pos] == q) printf("%lld\n", q*p[pos]); 26 if(pos == n) printf("%lld\n", q*p[n-1]); 27 else printf("%lld\n", min(suf[pos], q*p[pos-1])); 28 } 29 } 30 return 0; 31 }
B：先离散化找出所有内容的种类，之后尺取卡出最小页数。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1001000; 5 int n, m, rl, rr; 6 int h[maxn], p[maxn]; 7 int vis[maxn]; 8 int cnt, ret; 9 10 int id(int x) { 11 return lower_bound(h, h+m, x) - h; 12 } 13 14 int main() { 15 // freopen("in", "r", stdin); 16 while(~scanf("%d", &n)) { 17 for(int i = 0; i < n; i++) { 18 scanf("%d", &p[i]); 19 h[i] = p[i]; 20 } 21 sort(h, h+n); m = unique(h, h+n) - h; 22 memset(vis, 0, sizeof(vis)); 23 cnt = 0; ret = n; rl = 0, rr = n - 1; 24 int lo = 0, hi = 0; 25 while(lo < n) { 26 while(hi < n && cnt < m) { 27 int idx = id(p[hi++]); 28 if(!vis[idx]) cnt++; 29 vis[idx]++; 30 } 31 if(cnt < m) break; 32 if(ret > hi - lo && cnt == m) { 33 ret = hi - lo; 34 rl = lo, rr = hi - 1; 35 } 36 // printf("%d %d\n", lo, hi); 37 int idx = id(p[lo++]); 38 vis[idx]--; 39 if(vis[idx] == 0) cnt--; 40 if(lo >= n) break; 41 } 42 printf("%d\n", ret); 43 printf("%d %d\n", rl, rr); 44 } 45 return 0; 46 }
C：水题…
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 int n; 6 int a[maxn], b[maxn]; 7 8 int main() { 9 // freopen("in", "r", stdin); 10 int T; 11 scanf("%d", &T); 12 while(T--) { 13 scanf("%d", &n); 14 int x = 0, y = 0; 15 for(int i = 1; i <= n; i++) { 16 scanf("%d%d",&a[i],&b[i]); 17 } 18 sort(a+1, a+n+1); 19 sort(b+1, b+n+1); 20 for(int i = 1; i <= n; i++) { 21 if(a[i] > b[i]) x += 2; 22 else if(a[i] == b[i]) x++, y++; 23 else y += 2; 24 } 25 if(x > y) puts("Winjourn"); 26 else if(x == y) puts("Tie"); 27 else puts("Never_Sorry"); 28 } 29 return 0; 30 }
D：数位DP，dp(l,cnt)统计长度为l到时候1的个数为cnt的整数。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 22; 6 int digit[maxn]; 7 LL dp[maxn][maxn]; 8 LL n; 9 10 LL dfs(int l, int cnt, bool flag) { 11 if(l == 0) return cnt; 12 if(!flag && ~dp[l][cnt]) return dp[l][cnt]; 13 int pos = flag ? digit[l] : 9; 14 LL ret = 0; 15 for(int i = 0; i <= pos; i++) { 16 ret += dfs(l-1, cnt+(i==1), flag&&(pos==i)); 17 } 18 if(!flag) dp[l][cnt] = ret; 19 return ret; 20 } 21 22 LL f(LL x) { 23 int pos = 0; 24 while(x) { 25 digit[++pos] = x % 10; 26 x /= 10; 27 } 28 return dfs(pos, 0, true); 29 } 30 31 int main() { 32 // freopen("in", "r", stdin); 33 int _ = 1; 34 memset(dp, -1, sizeof(dp)); 35 while(~scanf("%lld", &n)) { 36 printf("Case %d:%lld\n", _++, f(n)); 37 } 38 return 0; 39 }
E：模拟，如果循环节正好长度为50的话，就不要打省略号了。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 vector<int> t1, t2; 5 map<int, int> id; 6 int a, b; 7 8 void f(int a, int b) { 9 id.clear(); 10 t1.clear(); t2.clear(); 11 int p = -1; 12 while(1) { 13 t1.push_back(a/b); 14 int x = a % b; 15 if(x == 0) break; 16 if(id.find(x) == id.end()) { 17 id[x] = t2.size(); 18 t2.push_back(x); 19 } 20 else { 21 p = id[x]; 22 break; 23 } 24 a = x * 10; 25 } 26 if(t1.size() == 0) while(1); 27 printf("%d.", t1[0]); 28 bool flag = 0; 29 bool plusflag = 0; 30 int cnt = 0; 31 for(int i = 1; i < t1.size(); i++) { 32 if(cnt >= 50) { 33 plusflag = 1; 34 break; 35 } 36 if(i == p + 1) { 37 printf("("); 38 flag = 1; 39 } 40 printf("%d", t1[i]); 41 if(flag) cnt++; 42 } 43 if(plusflag) printf("..."); 44 if(p >= 0) { 45 if(flag) printf(")\n"); 46 printf("%d\n", t1.size()-p-1); 47 } 48 else { 49 printf("(0)\n"); 50 printf("1\n"); 51 } 52 } 53 54 int main() { 55 // freopen("in", "r", stdin); 56 // freopen("out", "w", stdout); 57 int _ = 1; 58 while(~scanf("%d%d",&a,&b)) { 59 printf("Case %d:\n%d/%d=", _++, a, b); 60 if(a % b == 0) printf("%d.(0)\n1\n", a / b); 61 else f(a, b); 62 } 63 return 0; 64 }
F：好麻烦的计算几何，感觉要先卡出封闭图形，之后找到所有的矩形。然后看看能放的最大圆。
G：对整个数组排序后二分答案，贪心地从左到右选取数字，保证相邻两个数的差不小于二分出来的值，判断是否满足大于等于k个。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 int n, k; 6 int a[maxn], s[maxn]; 7 int ret; 8 9 bool ok(int dis) { 10 int i = 2, p = 1; 11 int cnt = 0; 12 while(i <= n) { 13 if(a[i] - a[p] >= dis) { 14 p = i; i++; 15 cnt++; 16 } 17 else i++; 18 } 19 return cnt + 1 >= k; 20 } 21 22 int main() { 23 // freopen("in", "r", stdin); 24 while(~scanf("%d%d",&n,&k)) { 25 memset(s, 0, sizeof(s)); 26 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 27 sort(a+1, a+n+1); 28 ret = a[n] - a[1]; 29 int lo = 0, hi = a[n]; 30 while(lo <= hi) { 31 int mid = (lo + hi) >> 1; 32 if(ok(mid)) { 33 ret = mid; 34 lo = mid + 1; 35 } 36 else hi = mid - 1; 37 } 38 printf("%d\n", ret); 39 } 40 return 0; 41 }
H：像是需要用启发式搜索将整座附近的点处理出来一个优先值，顺着第一条路走，最后回来。（后来有巨巨说是BFS）
I：枚举a,b字符串子串的起始，扫描对应位，如果不相同则替换至相同，最多k次操作。贪心地将替换操作放到前面，如果不能替换则break更新ret。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <string> 6 #include <map> 7 using namespace std; 8 9 const int maxn = 550; 10 int n, m, k; 11 char a[maxn], b[maxn]; 12 13 int main() { 14 // freopen("in" ,"r", stdin); 15 while(~scanf("%d", &k)) { 16 scanf("%s%s",a,b); 17 n = strlen(a); m = strlen(b); 18 int ret = 0; 19 for(int i = 0; i < n; i++) { 20 for(int j = 0; j < m; j++) { 21 int cnt = 0, tmp = 0; 22 for(int aa = i, bb = j; aa < n && bb < m; aa++, bb++) { 23 if(a[aa] == b[bb]) tmp++; 24 else { 25 if(cnt < k) tmp++, cnt++; 26 else break; 27 } 28 } 29 ret = max(ret, tmp); 30 } 31 } 32 printf("%d\n", ret); 33 } 34 return 0; 35 }
J：f(i,j)表示和为i，用j个数字组成的方案数，转移方程f(i,j)=f(i-p,j-1)，p取1~4，会爆LL所以用double存了f。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 111; 6 const int maxm = 666; 7 int n, m; 8 double f[maxn][maxm]; 9 10 int main() { 11 // freopen("in", "r", stdin); 12 memset(f, 0, sizeof(f)); 13 f[1][1] = 1.0; f[1][2] = 1.0; f[1][3] = 1.0; f[1][4] = 1.0; 14 for(int i = 2; i < maxn; i++) { 15 for(int j = 1; j < maxm; j++) { 16 for(int k = 1; k <= 4; k++) { 17 if(k >= j) continue; 18 f[i][j] += f[i-1][j-k]; 19 } 20 } 21 } 22 while(~scanf("%d%d",&n,&m)) { 23 printf("%.4lf\n", f[n][m]/pow(4,n)); 24 } 25 return 0; 26 }
K：最后的情形无非是两种，一种是wywy..，另一种是ywyw..。整个串长度如果是奇数那么是无法围成要求的项链的；之后判断当前情况和上述哪种情况最近，然后分别找w和y错位的数量，先交换，再修改，min(w,y)+(max(w,y)-min(w,y))=max(w,y)即为答案。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 char s[maxn], t[2][maxn]; 6 int n; 7 8 int main() { 9 // freopen("in", "r", stdin); 10 memset(t, 0, sizeof(t)); 11 for(int i = 0; i < maxn; i++) { 12 if(i % 2 == 0) { 13 t[0][i] = ‘w‘, t[1][i] = ‘y‘; 14 } 15 else { 16 t[0][i] = ‘y‘, t[1][i] = ‘w‘; 17 } 18 } 19 while(~scanf("%d", &n)) { 20 scanf("%s", s); 21 if(n & 1) { 22 puts("What a pity!"); 23 continue; 24 } 25 int a = 0, b = 0; 26 for(int i = 0; i < n; i++) { 27 if(s[i] != t[0][i]) a++; 28 if(s[i] != t[1][i]) b++; 29 } 30 if(a < b) { 31 int w = 0, y = 0; 32 for(int i = 0; i < n; i++) { 33 if(s[i] != t[0][i]) { 34 if(s[i] == ‘w‘) w++; 35 else y++; 36 } 37 } 38 printf("%d\n", max(w, y)); 39 } 40 else { 41 int w = 0, y = 0; 42 for(int i = 0; i < n; i++) { 43 if(s[i] != t[1][i]) { 44 if(s[i] == ‘w‘) w++; 45 else y++; 46 } 47 } 48 printf("%d\n", max(w, y)); 49 } 50 } 51 return 0; 52 }
L：不会…
青岛理工大学第五届ACM交流赛 部分题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。