第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组蓝桥杯

第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组小结提示：代码为比赛时本人提交的代码，不代表是正解！！！
试题 A: 九进制转十进制暴力

1478

试题 B: 顺子日期 【第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组】012居然不算QAQ！！！！！！！
反正也是暴力，根据队友的答案应该是

4

试题 C: 刷题统计假设需要用x周+y天，我们可以快速求出需要用多少周，再慢慢减求出多出几天就行

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll N = 1e5+9; int main(){ ll a,b,n; scanf("%lld %lld %lld",&a,&b,&n); ll num = n/(5*a+2*b); n = n - num*(5*a+2*b); num = num*7; for(int i = 1; i <= 7; i++){ if(n <= 0) break; if(i <= 5){ n -= a; num++; }else{ n -= b; num++; } } printf("%lld",num); return 0; }

试题 D: 修剪灌木第i个灌木如何长最高呢，那就是爱丽丝从当前灌木往左剪回来i，和往右剪回来i，看看哪个高。

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll N = 1e5+9; int n; int a[N]; int maxx[N]; int main(){ scanf("%d",&n); for(int i = 1; i <= n; i++){ maxx[i] = max(2*(i-1),2*(n-i)); } for(int i = 1; i <= n; i++){ printf("%d\n",maxx[i]); } return 0; }

试题 E: X 进制减法因为a是大于b的，所以想要让a-b尽可能小，就要让每一位的进制尽可能小。
pa[i]代表的是第i+1位数1转化为十进制的大小

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll N = 1e6+9; const ll mod = 1e9+7; ll pow_mod(ll a,ll b){ ll ans = 1; ll base = a; while(b){ if(b&1) ans = (ans * base) % mod; base = (base * base) % mod; b >>= 1; } return ans; } ll n; ll a[N]; ll b[N]; ll na,nb; ll pa[N]; int main(){ scanf("%lld",&n); scanf("%lld",&na); for(ll i = 1; i <= na; i++){ scanf("%lld",&a[i]); } reverse(a+1,a+1+na); scanf("%lld",&nb); for(ll i = 1; i <= nb; i++){ scanf("%lld",&b[i]); } reverse(b+1,b+1+nb); ll p = max(na,nb); ll ans = 0; pa[0] = 1; for(ll i = 1; i <= p; i++){ ll maxx = max(a[i],b[i]); ll x = max(2ll,maxx + 1); pa[i] = (pa[i-1]*x)%mod; ans = (ans + a[i]*pa[i-1] - b[i]*pa[i-1] + mod) % mod; } printf("%lld",ans); return 0; }

试题 F: 统计子矩阵比赛时算错复杂度，用二维前缀和暴力算的。70分

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll N = 5e2+9; ll a[N][N]; ll pre[N][N]; ll work(int x1,int y1,int x2,int y2){ return pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]; } int main(){ ll ans = 0; ll n,m,k; scanf("%lld %lld %lld",&n,&m,&k); for(ll i = 1; i <= n; i++){ for(ll j = 1; j <= m; j++){ scanf("%lld",&a[i][j]); pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ for(int p = i; p <= n; p++){ for(int l = j; l <= m; l++){ ll x = work(i,j,p,l); if(x <= k) ans++; } } } } printf("%lld",ans); return 0; }

试题 G: 积木画不会！！！！！！！
试题 H: 扫雷根据雷和雷的关系建一张有向图，注意因为r最大是10，所以最多只用在平面上找20*20个点，用map存图，比赛时没算复杂度感觉能过，现在算了一下，50000 * 20 * 20 * log(50000)有点极限，希望测评机够快。

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll N = 1e6+9; struct node{ ll x,y,r; }e[N]; vector g[N]; map ,int> mp; ll dis(ll x1,ll y1,ll x2,ll y2){ return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2); } int vis[N]; void dfs(int now){ if(vis[now]) return ; vis[now] = 1; for(int i = 0; i < g[now].size(); i++){ int to = g[now][i]; if(!vis[to]) dfs(to); } } int main(){ ll n,m,r; scanf("%lld %lld %lld",&n,&m,&r); for(ll i = 1; i <= n; i++){ scanf("%lld %lld %lld",&e[i].x,&e[i].y,&e[i].r); mp[make_pair(e[i].x,e[i].y)] = i; } for(int k = 1; k <= n; k++){ for(int i = -e[k].r; i <= e[k].r; i++){ for(int j = -e[k].r; j <= e[k].r; j++){ ll xx = e[k].x+i,yy = e[k].y+j; if(dis(e[k].x,e[k].y,xx,yy) <= e[k].r*e[k].r){ if(mp[make_pair(xx,yy)]){ g[k].push_back(mp[make_pair(xx,yy)]); } } } } } for(ll k = 1; k <= m; k++){ for(int i = -e[k].r; i <= e[k].r; i++){ for(int j = -e[k].r; j <= e[k].r; j++){ ll xx = e[k].x+i,yy = e[k].y+j; if(dis(e[k].x,e[k].y,xx,yy) <= e[k].r*e[k].r){ if(mp[make_pair(xx,yy)]){ int now = mp[make_pair(xx,yy)]; if(!vis[now]) dfs(now); } } } } } ll ans = 0; for(int i = 1; i <= n; i++){ if(vis[i]) ans++; } printf("%lld",ans); return 0; }

试题 I: 李白打酒加强版三维dp，定义d[i] [j] [k]表示前i个去处，去了j家店，还剩余k斗酒有多少种情况。
因为最后一定要遇到花，所以d[n+m] [n] [0]一定只能由d[n+m-1] [n] [1]转移而来，所以输出d[n+m-1] [n] [1]即可

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll N = 2e2+9; const ll mod = 1000000007; ll d[N][N][N]; ll n,m; int main(){ d[0][0][2] = 1; scanf("%lld %lld",&n,&m); ll ans = 0; for(int i = 1; i <= n+m; i++){ for(int j = 0; j <= n; j++){ for(int k = 0; k <= m; k++){ if(i != n+m){ if(d[i-1][j][k]){ if(k > 0){ d[i][j][k-1] = (d[i][j][k-1] + d[i-1][j][k])%mod; } if(k*2 <= m){ d[i][j+1][k*2] = (d[i][j+1][k*2] + d[i-1][j][k])%mod; } } }} } } printf("%lld",d[n+m-1][n][1]); return 0; }

试题 J: 砍竹子写完i没时间看了QAQ