| A | HihoCoder 1268 | 九宫 |
思路：
一般类似于数独的题目都是使用回溯解决，这里由于题目数据较小同样可以直接DFS得出结果。这里我用了一个偷懒的方法（next_permutation），直接求出全排列，然后将位置一一对应。
// Asimple #include <bits/stdc++.h> #define debug(a) cout<<#a<<" = "<<a<<endl #define sysp system("pause") using namespace std; typedef long long ll; const int maxn = 200000 + 5; ll T, n, sum, num, m, t, len, ans; int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int res[3][3], Map[3][3], temp[3][3]; bool check() { if( a[0]+a[1]+a[2] == a[3]+a[4]+a[5] && a[3]+a[4]+a[5] == a[6]+a[7]+a[8] && a[6]+a[7]+a[8] == a[0]+a[4]+a[8] && a[0]+a[4]+a[8] == a[2]+a[4]+a[6] && a[2]+a[4]+a[6] == a[0]+a[3]+a[6] && a[0]+a[3]+a[6] == a[1]+a[4]+a[7] && a[1]+a[4]+a[7] == a[2]+a[5]+a[8] ) return true; return false; } void input() { for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { scanf("%d", &Map[i][j]); } } int flag = 0; do{ if( check() ) { bool f = true; for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { temp[i][j] = a[i*3+j]; if( Map[i][j] && Map[i][j] != temp[i][j] ) { f = false; break; } } if( !f ) break; } if( f ) { if( flag == 1 ) { flag = 2; break; } else flag = 1; for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { res[i][j] = temp[i][j]; } } } } if( flag == 2 ) break; }while( next_permutation(a, a+9)); if( flag == 2 ) printf("Too Many "); else { for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { printf("%d", res[i][j]); if( j == 2 ) printf(" "); else printf(" "); } } } //sysp; } int main() { input(); return 0; }
| B | HihoCoder 1269 | 优化延迟 |
思路：
看到题目，第一眼就看到了给出的运行时间10s，果断一发暴力TLE。随后仔细看了下题目，发现当K越大，得出的结果也就越小，这个不是裸二分吗，然后直接上手，wa10+次，最后才发现自己的get_sp竟然是返回int，还以为是自己的二分有问题，改了好几版，-_-||。补充一下，k为什么不能为0呢？虽然为0时相当于没加缓冲。
// Asimple #include <bits/stdc++.h> #define debug(a) cout<<#a<<" = "<<a<<endl #define sysp system("pause") using namespace std; typedef long long ll; const int maxn = 100000 + 5; ll T, n, sum, num, m, t, len, ans; ll a[maxn]; ll get_sp(int cnt) { priority_queue<ll> q; ll sp = 0, c = 1, v; int i = 0; while( !q.empty() || i < n ) { while( q.size()<cnt && i<n ) q.push(a[i++]); v = q.top(); q.pop(); sp += c*v; c ++; if( sp > num ) return num + 1; } return sp; } void input() { scanf("%lld %lld", &n, &num); ll sp = 0; ans = -1; for(int i=0; i<n; i++) scanf("%lld", &a[i]); ll low = 1, high = maxn; while( low <= high ) { ll mid = (low+high)/2; if( get_sp(mid)<=num ) { ans = mid; high = mid-1; } else low = mid+1; } printf("%lld ", ans); //sysp; } int main() { input(); return 0; }
附上自己wa的截图：
| C | HihoCoder 1270 | 建造基地 |
思路：
这道题不由的让我想起了当初做区域赛的网络赛的场景，这完全是道读题目的题，题目看懂了其实还挺简单的。
简单来说就是一个类完全背包的问题，每一层在修建的时候都是在要花最小的代价去满足建筑值。当一层修建完成之后，便是将金属的建筑值更新。
// Asimple #include <bits/stdc++.h> #define debug(a) cout<<#a<<" = "<<a<<endl #define sysp system("pause") using namespace std; typedef long long ll; const int maxn = 10000 + 5; const ll INF = 1<<30; const ll mod = 2000000000000000003; ll T, n, sum, num, m, t, len, ans, k; ll dp[maxn], a[maxn], b[maxn]; void input() { while( cin >> T ) { while( T -- ) { ans = 0; cin >> n >> m >> k >> t; for(int i=1; i<=m; i++) cin >> a[i]; for(int i=1; i<=m; i++) cin >> b[i]; for(int u=1; u<=n; u++) { for(int i = 0; i<maxn; i++) dp[i] = INF; dp[0] = 0; for(int i=1; i<=m; i++) { for(int j=0; j<=k; j++) { if( j + b[i] > k ) dp[k] = min(dp[k], dp[j] + a[i]); else dp[j+b[i]] = min(dp[j+b[i]], dp[j] + a[i]); } } ans += dp[k]; for(int v=1; v<=m; v++) b[v] /= t; } if( ans >= INF ) cout << "No Answer" << endl; else cout << ans << endl; } } //sysp; } int main() { input(); return 0; }
| D | HihoCoder 1271 | 舰队游戏 |
暂无思路。看了题解说是用贪心+状压过，状态压缩是个好东西，可惜我不会。
AC博客1：https://blog.csdn.net/qq_32400847/article/details/51087220
AC博客2：https://blog.csdn.net/tc_to_top/article/details/50825418