cf的几道小题
1、E - Fridge
教训：做题的时候，没有想清楚问题，把问题复杂化了
#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
教训：数据范围比较大，直接暴力会超时，并且推公式比较麻烦，优先考虑打表
思路：当n >= 9时，会达到极限，后面的概率值都是一样的。
#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，那么只需从序列最大的数开始取模，这样最后的结果一定是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
思路：求可变化的数的上界和下界，学会区分上界和下界。
#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){//偶数减x，所以x有最大值,要取上界最小值
maxn = min(maxn, now);
}
else{//奇数 + x，所以x有最小值
minn = max(minn, -now);
}
}
if(minn > maxn) cout <<"0";
else cout << maxn - minn + 1;
return 0;
}
链接：https://www.dianjilingqu.com/616307.html
