链接
分析
根据题意模拟就行,合理运用STL可以简化代码。
实现
#include
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
void solve() {string a, b;cin >> a >> b;int n = a.size(), m = b.size();if (n != m) {cout << -1 << '\n';return;}string ans;for (int i = 0; i < n; i++) {ans += to_string((a[i] - '0') * (b[i] - '0'));//to_stirng函数可以使得int转换为string类型}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}
分析
这题看似唬人,其实不难,因为这里只说了取一道菜所以只需暴力取最优的即可。
实现
#include
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
void solve() {int n, a, b;cin >> n >> a >> b;int ans = inf;while (n--) {int k, x, y;cin >> k >> x >> y;while (k--) {int c;cin >> c;if (c >= a && c >= x) {c = max(0, c - b - y);} else if (c >= a) {c = max(0, c - b);} else if (c >= x) {c = max(0, c - y);}ans = min(ans, c);}}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}
分析
这里n的范围是5000,我们可以直接枚举两端,对26个字母统计前缀字符数,即可,时间复杂度O(n^2*26),注意可能卡map,这里用数组。
实现
#include
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 5005;
char s[N];
int cnt[26][N];
void solve() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {for (int j = 0; j < 26; j++) {cnt[j][i] = 0;}}scanf("%s", s + 1);for (int i = 1; i <= n; i++) {char ch = s[i];for (int j = 0; j < 26; j++) {if (ch - 'a' == j) cnt[j][i] = cnt[j][i - 1] + 1;else cnt[j][i] = cnt[j][i - 1];//继承前缀}}
// for (int i = 0; i < 26; i++) {
// for (int j = 1; j <= n; j++) {
// cout << cnt[i][j] << ' ';
// }
// cout << '\n';
// }double ans = 0;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {int sum = 0;for (int k = 0; k < 26; k++) {int c = cnt[k][j] - cnt[k][i - 1];sum += c * (c - 1) / 2;//统计相同的对数}ans = max(ans, 1.0 * sum / (j - i + 1));}}printf("%.6lf\n", ans);
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}
分析
首先300的数目步数最多300,总共有8种更新方法,求最小操作次数,但是这里组数有点多,考虑用记忆化搜索,总时间复杂度为O(n^2).
实现
#include
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 5005;
int go[6] = {1, -1, 10, -10, 100, -100};
int dp[305];
bool vis[305];
void bfs(int tar) {for (int i = 10; i <= 300; i++) vis[i] = 0;vis[10] = 1;queue q;q.push({10, 0});while (!q.empty()) {int x = q.front().first, s = q.front().second;if (x == tar) {//找到目标值就弹出,先进先出,所以步数是最小的dp[tar] = s;return;}q.pop();for (int i = 0; i < 8; i++) {int nx;if (i < 6) nx = x + go[i];else if (i == 6) nx = 10;else nx = 300;if (nx < 10 || nx > 300 || vis[nx]) continue;vis[nx] = 1;int ns = s + 1;q.push({nx, ns});}}
}
void solve() {int a, b, c, d;
// cin >> a;
// bfs(a);
// cout << dp[a] << '\n';cin >> a >> b >> c >> d;if (dp[a] == -1) bfs(a);if (dp[b] == -1) bfs(b);if (dp[c] == -1) bfs(c);if (dp[d] == -1) bfs(d);cout << dp[a] + dp[b] + dp[c] + dp[d] << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;for (int i = 11; i <= 305; i++) dp[i] = -1;//0也算,所以初始化-1while (T--) {solve();}
}
分析
为了更加充分地利用空间,我们需要紧凑地使用格子,所以把棋盘分成奇数格和偶数格使用,预处理平方数,可以得到所有奇数格的数目和偶数格的数目,如果平方数是偶数则两者一样多否则奇数多1个,我们查询的两个数较大的那一个放在奇数格上,利用二分,但是,此时另一个数可能不行,因为如果说这个数是对应的平方数是奇数,而两者又是一样大的话,是无法放入的,例如:n=3,b[3]=5,c[3] = 4, x = y = 5,必须往右挪一格(可能前面有需要几格的,但是不多)到y符合,在向右挪的时候由于单调性,x始终符合。注意爆int。
实现
#include
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 1e5 + 5;
int go[6] = {1, -1, 10, -10, 100, -100};
ll a[N], b[N], c[N];
void solve() {ll x, y;cin >> x >> y;if (x < y) swap(x, y);int n = 1e5;int p = lower_bound(b + 1, b + 1 + n, x) - b;
// cout << b[p] << '\n';while (c[p] < y) p++;//稍微挪一格左右cout << p << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;int m = 1e5;for (int i = 1; i <= m; i++) a[i] = 1ll * i * i;//这里爆intfor (int i = 1; i <= m; i++) {b[i] = (a[i] + 1) / 2;c[i] = a[i] - b[i];}
// cout << b[70000] << '\n';
// for (int i = 1; i <= 5; i++) cout << c[i] << '\n';while (T--) {solve();}
}