B - A^A
难度: ⭐
题目大意
给出一个数n, 问是否存在一个数m, 使mm = n;
解题思路
因为n的数据范围很大, 到1e18, 经过打表可以发现, 当m=16时就已经大于1e18了, 因为数很多所以用了__int128, 因为double会损失精度;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
signed main(){
cin >> n;
bool f = false;
for (int i = 1; i <= 17; i++) {
__int128 sum = 1;
for (int j = 1; j <= i; j++) {
sum = sum * i;
}
if (sum==n) {
cout << i;
return 0;
}
}
cout << -1;
return 0;
}
C - Number Place
难度: ⭐
题目大意
给定一个9*9的数字表格, 检查它是否满足数独的要求, 即9个3 * 3的小九宫格中都有数字1~9, 每一行和每一列也都是1~9;
解题思路
数据不大, 暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int g[10][10];
PII a[10] = {{1,1},{1,4},{1,7},{4,1},{4,4},{4,7},{7,1},{7,4},{7,7}};
int b[10];
signed main(){
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
cin >> g[i][j];
}
}
bool f = true;
for (int i = 1; i <= 9; i++) {
memset(b, 0, sizeof b);
for (int j = 1; j <= 9; j++) {
b[g[i][j]]++;
}
for (int i = 1; i <= 9; i++) {
if (b[i] == 0) {
f = false;
break;
}
}
}
for (int j = 1; j <= 9; j++) {
memset(b, 0, sizeof b);
for (int i = 1; i <= 9; i++) {
b[g[i][j]]++;
}
for (int i = 1; i <= 9; i++) {
if (b[i] == 0) {
f = false;
break;
}
}
}
for (int k = 0; k < 9; k++) {
memset(b, 0, sizeof b);
int x = a[k].first, y = a[k].second;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
b[g[x + i][y + j]]++;
}
}
for (int i = 1; i <= 9; i++) {
if (b[i]==0) {
f = false;
break;
}
}
}
if (f) cout << "Yes";
else cout << "No";
return 0;
}
D - Good Tuple Problem
难度: ⭐⭐
题目大意
现在有n个人编号为1~n, 给定A1 ~ Am和B1 ~ Bm, 其中Ai和Bi是敌对的; 问最后能否把这n个人分为两个阵营, 每个阵营中没有敌对的人;
解题思路
一道比较明显的染色法判定二分图模板题, 这个就不多说了; 本题还可以用并查集来做;
我们用数组st[i]表示和i为敌对关系的人是谁, 初始情况全设为-1; 这样当我们取出一对Ai和Bi时, 如果find(Ai)和find(Bi)相等说明无法匹配; 否则的话, 如果st[Ai] = -1, 就可以直接让st[Ai]=Bi; 如果st[Ai] != -1, 就说明st[Ai]和Bi是同一阵营的, 我们就可以让p[find(st[Ai])] = find(Bi); 以上过程Bi同理;
神秘代码
// 染色法
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int A[N], B[N];
int st[N];
vector<int> v[N];
bool bfs(int u) {
queue<int> q;
q.push(u);
st[u] = 1;
while (q.size()) {
int t = q.front();
q.pop();
for (int x : v[t]) {
if (!st[x]) {
st[x] = 3 - st[t];
q.push(x);
}
else {
if (st[x] == st[t]) return false;
}
}
}
return true;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> A[i];
for (int i = 1; i <= m; i++) cin >> B[i];
for (int i = 1; i <= m; i++) {
int x = A[i], y = B[i];
v[x].push_back(y);
v[y].push_back(x);
}
bool f=true;
for (int i = 1; i <= n; i++) {
if (!st[i]) {
if (!bfs(i)) {
f = false;
break;
}
}
}
if (f) cout << "Yes";
else cout << "No";
return 0;
}
//并查集
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 4e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int A[N], B[N];
int p[N], st[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= m; i++) cin >> A[i];
for (int i = 1; i <= m; i++) cin >> B[i];
memset(st, -1, sizeof st);
bool f = true;
for (int i = 1; i <= m; i++) {
int x = A[i], y = B[i];
int px = find(x), py = find(y);
if (px == py) {
f = false;
break;
}
if (st[x] == -1) st[x] = y;
else p[find(st[x])] = py;
if (st[y] == -1) st[y] = x;
else p[find(st[y])] =px;
}
if (f) cout << "Yes";
else cout << "No";
return 0;
}
E - Maximize Rating
难度: ⭐⭐⭐
题目大意
给定n个数, 我们从中挑选k个数, 这k个数和相对顺序和在原来n个数中的相对顺序一致, 把这k个数记作Q1到Qk; 请问我们k该设为多少, 并且该如何挑选这k个数可以让题目给出的公式值最大;
解题思路
观察公式, 我们发现如果k固定了, 我们只需要让左边的分子越大越好, 所以从n个数中找出k个使分子最大的数; 这个过程可以用dp来做, dp[i][j]表示在前i个数中挑选k个使分子最大的数所得的分子公式的值, 通过分子的公式可以发现dp[i][k] = dp[i-1][k-1]*0.9 + f[i], 并且对于dp[i][k]我们可以将其初始化为dp[i-1][k]; 这样就得到了转移方程: dp[i][k]=max(dp[i-1][k], dp[i-1][k-1] * 0.9 + f[i]); 最后再对dp[n][k]考虑到底选择k为多少可以得到最大值;
神秘代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 5e3 + 10;
int n, m;
double dp[N][N];
double f[N];
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> f[i];
}
dp[1][1] = f[1];
for(int i = 1; i <= n; i++){
for(int k = 1; k <= i; k++){
dp[i][k]=max(dp[i-1][k], dp[i-1][k-1]*0.9 + f[i]);
}
}
double x = 1;
double maxn=-1e9;
for(int i = 1; i <= n; i++){
dp[n][i] = dp[n][i]/x - 1200/sqrt(i);
maxn=max(maxn, dp[n][i]);
x = x*0.9+1;
}
printf("%.20lf",maxn);
return 0;
}
F - Apples
难度: ⭐⭐⭐⭐
- Beginner AtCoder Contest 327 abcbeginner atcoder contest 327 327 beginner atcoder contest beginner atcoder contest abc atcoder_abc atcoder 327 abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332