软盟2练习答案
1.签到题I
这题排个序输出第k个下标就好,注意输入如果从0开始就是输出k-1
c++:
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int arr[N];
int n, k;
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n);
cout << arr[k-1] << endl;
return 0;
}
2.A题
这题算法涉及到了快速幂,灵活运用快速幂即可
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; int qmi(int a, int b, int p) { int res = 1 % p; while (b) { if (b & 1) res = res * (LL)a % p; a = a * (LL)a % p; b >>= 1; } return res; } int main() { int n, m, k, x; scanf("%d%d%d%d", &n, &m, &k, &x); printf("%d\n", (x + qmi(10, k, n) * (LL)m) % n); return 0; }
3.B题
本来想考区间和或差分的,没发现这题要求边修改边查询,就得用树状数组或者线段树做,这边推荐用树状数组的知识点做更简单
#include <iostream> using namespace std; typedef long long LL; // 树状数组中最重要的操作,修改和查询 const int N = 1000010; int a[N]; LL tr[N]; int n , q; int lowbit(int x) { return x & (-x); } void add(int u , int x) { for (int i = u ; i <= n ; i += lowbit(i)) tr[i] += x; } LL sum(int x) { LL res = 0; for (int i = x ; i ; i -= lowbit(i)) res += tr[i]; return res; } int main() { scanf("%d%d", &n, &q); for (int i = 1 ; i <= n ; i ++) scanf("%d", &a[i]); for (int i = 1 ; i <= n ; i ++) add(i , a[i]); // 建立树状数组 for (int i = 1 ; i <= q ; i ++) { int c; scanf("%d", &c); if (c == 1) { int u , x; scanf("%d%d", &u, &x); add(u , x); } else { int l , r; scanf("%d%d", &l, &r); printf("%lld\n", sum(r) - sum(l - 1)); } } return 0; }
第四题:小红的扫雷游戏
这题很考验思维,相当于怎么用用代码编写我们平时玩的扫雷游戏的推断思想,非常灵活这里提供用dfs的做法
#include<iostream> #include<algorithm> using namespace std; const int N=5; char g[N][N]; int cnt[N][N]; int d; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]={-1,0,1,1,-1,-1,0,1}; void dfs(int x,int y) { if(y==4) { y=0;x++; } if(x==4) { for(int i=0;i<4;i++) for(int j=0;j<4;j++) { if(g[i][j]>='0'&&g[i][j]<='9') { int k=g[i][j]-'0'; int t=0; for(int u=0;u<8;u++) { int nx=i+dx[u];int ny=j+dy[u]; if(nx<0||nx>=8||ny<0||ny>=8)continue; if(g[nx][ny]=='X')t++; } if(t!=k)return; } } d++; for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(g[i][j]=='X')cnt[i][j]++; return; } if(g[x][y]>='0'&&g[x][y]<='9')dfs(x,y+1); else { g[x][y]='X'; dfs(x,y+1); g[x][y]='.'; dfs(x,y+1); } } int main() { for(int i=0;i<4;i++) for(int j=0;j<4;j++) cin>>g[i][j]; dfs(0,0); for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { if(g[i][j]>='0'&&g[i][j]<='9')cout<<g[i][j]; else if(cnt[i][j]==d)cout<<'X'; else if(cnt[i][j]==0)cout<<'O'; else cout<<'.'; } cout<<endl; } return 0; }
python做法
import sys input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) lii = lambda: list(map(int, input().split())) dir8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)] grid = [] for _ in range(4): grid.append(list(input())) res = [[0] * 4 for _ in range(4)] calc = 0 def check(): for r, row in enumerate(grid): for c, ch in enumerate(row): if ch.isdigit(): cnt = 0 for dr, dc in dir8: r2, c2 = r+dr, c+dc if 0 <= r2 < 4 and 0 <= c2 < 4 and grid[r2][c2] == 'X': cnt += 1 if cnt != int(ch): return False return True def dfs(i, j): global calc if i == 4: if check(): calc += 1 for r in range(4): for c in range(4): res[r][c] += grid[r][c] == 'X' return if j == 4: return dfs(i+1, 0) if grid[i][j].isdigit(): return dfs(i, j+1) grid[i][j] = 'X' dfs(i, j+1) grid[i][j] = '.' dfs(i, j+1) dfs(0, 0) ans = [['.'] * 4 for _ in range(4)] for r in range(4): for c in range(4): if grid[r][c].isdigit(): ans[r][c] = grid[r][c] else: if res[r][c] == 0: ans[r][c] = 'O' elif res[r][c] == calc: ans[r][c] = 'X' for row in ans: print(''.join(row))
5.石子合并
经典的一个区间dp的石子合并问题
c++代码
#include <iostream> #include <algorithm> using namespace std; const int N = 315; int s[N]; int dp[N][N], n; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1]; for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; dp[i][j] = 1e8; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]); } } } printf("%d\n", dp[1][n]); return 0; }
python做法
n = int(input()) f = [[0]*(n+2) for _ in range(n+2)] a = [0] + list(map(int,input().split())) s = [0]*(n+2) for i in range(1,n+1): s[i] = s[i-1]+a[i] for le in range(2,n+1): i = 1 while i+le-1<=n: l,r=i,i+le-1 f[l][r] = 1000000000 for k in range(l,r): f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]) i += 1 print(f[1][n])