cf的幾道小題
1、E - Fridge
教訓(xùn)：做題的時(shí)候，沒有想清楚問題，把問題復(fù)雜化了
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;
string st;
int cnt[N], minn = N, pos;
struct node
{
? ?int num;
? ?int sum;
? ?bool operator<(const node &p) const
? ?{
? ? ? ?if (sum < p.sum)
? ? ? ? ? ?return true;
? ? ? ?else if (sum == p.sum && num < p.num)
? ? ? ? ? ?return true;
? ? ? ?return false;
? ?}
} a[N];
signed main()
{
? ?cin >> st;
? ?for (int i = 0; i < st.size(); i++)
? ?{
? ? ? ?int x = st[i] - '0';
? ? ? ?cnt[x]++;
? ?}
? ?for (int i = 1; i <= 9; i++)
? ?{
? ? ? ?if (cnt[i] == 0)
? ? ? ?{
? ? ? ? ? ?cout << i;
? ? ? ? ? ?return 0;
? ? ? ?}
? ?}
? ?for (int i = 0; i < 10; i++)
? ?{
? ? ? ?a[i].num = i;
? ? ? ?a[i].sum = cnt[i];
? ?}
? ?if (!a[0].sum)
? ?{
? ? ? ?cout << 10;
? ? ? ?return 0;
? ?}
? ?sort(a + 1, a + 10);
? ?if (a[0].sum < a[1].sum)
? ?{
? ? ? ?cout << 1;
? ? ? ?for (int i = 1; i <= a[0].sum + 1; i++)
? ? ? ?{
? ? ? ? ? ?cout << 0;
? ? ? ?}
? ?}
? ?else
? ?{
? ? ? ?for (int i = 1; i <= a[1].sum + 1; i++)
? ? ? ?{
? ? ? ? ? ?cout << a[1].num;
? ? ? ?}
? ?}
? ?return 0;
}
2、J - Secret Santa
教訓(xùn)：數(shù)據(jù)范圍比較大，直接暴力會(huì)超時(shí)，并且推公式比較麻煩，優(yōu)先考慮打表
思路：當(dāng)n >= 9時(shí)，會(huì)達(dá)到極限，后面的概率值都是一樣的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N ?= 1010;
int a[N], num = 1, n;
double cnt[N];
signed main(){
? ?cin >> n;
? ?for(int i = 1; i <= 10; i++) a[i] = i;
? ?int ans = 0;
? ?for(int i = 1; i <= 10; i++){
? ? ? ?ans = 0;
? ? ? ?num = num * i;
? ? ? ?do{
? ? ? ? ? ?for(int j = 1; j <= i; j++){
? ? ? ? ? ? ? ?if(a[j] == j){
? ? ? ? ? ? ? ? ? ?ans ++;
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ?}while(next_permutation(a + 1, a + 1 + i));
? ? ? ?cnt[i] = ?1.0 * ans / num;
? ?}
? ?if(n >= 10) cout <<fixed << setprecision(8) << cnt[10];
? ?else cout <<fixed << setprecision(8) << cnt[n];
}
3、CF1656C Make Equal With Mod
思路：如果想讓所有的序列變成0，那么只需從序列最大的數(shù)開始取模，這樣最后的結(jié)果一定是0
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], t;
signed main(){
? ?cin >> t;
? ?while(t --){
? ? ? ?cin >> n;
? ? ? ?set<int> s;
? ? ? ?for(int i = 1; i <= n; i++){
? ? ? ? ? ?cin >> a[i];
? ? ? ? ? ?s.insert(a[i]);
? ? ? ?}
? ? ? ?bool flag1 = false, flag2 = false;
? ? ? ?for(set<int>::iterator it = s.begin(); it != s.end(); it ++){
? ? ? ? ? ?if(*it == 0) flag1 = true;
? ? ? ? ? ?if(*it == 1) flag2 = true;
? ? ? ?}
? ? ? ?if(flag1 && flag2){
? ? ? ? ? ?cout <<"NO" << endl;
? ? ? ?}
? ? ? ?else{
? ? ? ? ? ?sort(a + 1,a + 1 + n);
? ? ? ? ? ?bool flag = true;
? ? ? ? ? ?for(int i =1 ; i < n; i++){
? ? ? ? ? ? ? ?if(a[i + 1] - a[i] == 1 && a[1] == 1) {
? ? ? ? ? ? ? ? ? ?flag = false; break;
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ? ? ?if(!flag) cout << "NO" << endl;
? ? ? ? ? ?else cout <<"YES" << endl;
? ? ? ?}
? ?}
? ?return 0;
}
4、D - Down the Pyramid
思路：求可變化的數(shù)的上界和下界，學(xué)會(huì)區(qū)分上界和下界。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], now, minn = 0, maxn = 0x3f3f3f3f;
signed main(){
? ?cin >> n;
? ?for(int i = 1; i <= n; i++){
? ? ? ?cin >> a[i];
? ?}
? ?for(int i = 1; i <= n; i++){
? ? ? ?now = a[i] - now;
? ? ? ?if(i % 2 == 1){//偶數(shù)減x，所以x有最大值,要取上界最小值
? ? ? ? ? ?maxn = min(maxn, now);
? ? ? ?}
? ? ? ?else{//奇數(shù) + x，所以x有最小值
? ? ? ? ? ?minn = max(minn, -now);
? ? ? ?}
? ?}
? ?if(minn > maxn) cout <<"0";
? ?else cout << maxn - minn + 1;
? ?return 0;
}
鏈接：https://www.dianjilingqu.com/616307.html
