C - False Hope
题意
给定一个 $3 \times 3 $ 的矩阵。
以一个随机的顺序先后看这 9 个数,如果说某一行或者某一列或者某一对角线上的三个数看到的先后顺序满足先看到相同的两个数,再看到不同的一个数,则此次观察定义为不高兴的观察。
问你观察不是不高兴的概率
思路
因为随机查看的方式最多只有 9!种,所以直接遍历所有情况判断每种情况是否成立即可
代码
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;
int p[10], t[10];
vector<vector<int>> a = {
{1, 2, 3}, {4, 5, 6}, {7, 8, 9},
{1, 4, 7}, {2, 5, 8}, {3, 6, 9},
{1, 5, 9}, {3, 5, 7}
};
void solve(){
for(int i = 1; i <= 9; ++ i){
cin >> p[i];
t[i] = i;
}
int cnt = 0, tot = 0;
do{
++ tot;
for(auto c : a){
sort(c.begin(), c.end(), [&](int x, int y){
return t[x] < t[y];
});
if(p[c[0]] == p[c[1]] && p[c[1]] != p[c[2]]){
++ cnt; break;
}
}
}while(next_permutation(t + 1, t + 10));
cout << fixed << setprecision(15) << 1.0 * (tot - cnt) / tot << '\n';
return ;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
D - Minimum Width
思路
二分答案
代码
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;
ll n, m, l[maxm], ml;
bool check(ll x){
int cnt = 0;
ll t = 0;
for(int i = 1; i <= n; ++ i){
if(t == 0){
t += l[i];
}else{
if(t + 1 + l[i] > x){
++ cnt;
t = l[i];
}else t += 1 + l[i];
}
}
if(t) ++ cnt;
if(cnt <= m) return true;
else return false;
}
void solve(){
cin >> n >> m;
ll mm = 0;
for(int i = 1; i <= n; ++ i){
cin >> l[i];
ml += l[i];
ml += (i > 1);
mm = max(mm, l[i]);
}
ll x = mm, y = ml, mid;
while(x <= y){
mid = (x + y) >> 1;
if(check(mid)) y = mid - 1;
else x = mid + 1;
}
cout << x << '\n';
return ;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
- 模拟题 Beginner AtCoder Contest 319beginner atcoder contest 319 模拟题beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334