Codeforces之旅(2)

薛定谔方程难

发布于 2024-11-20 14:36:41

1760

1、前言

Oh！No！

对于这场比赛来说，我还是没有上青。其实说来惭愧，在比赛开始前我也刷了不少的题目，但是呢，比完结束之后才知道，对于1200分数以下的题目来说，通常都不怎么涉及数据结构和一些难度比较大的题目。但是，这些都是我现在才知道的，如果你也是和我一样是一个灰名的话，你一定要多注意思考简单的方法去实现问题的解决，同时1200以下分数的题目有时候还会多包涵一些简单的模拟，这也是我们小灰明名需要注意的。这场比下来很遗憾吧，对于Div3的C题，我真的哭死

如果这一分钟来的再及时一点~，说不定就能回到1011的max了。

2、题目讲解

1、A、Twice

Twice 这道题目挺简单的，用一个map存储每一个数字出现的次数，然后对每一个都进行除以2的操作，将每一个的结果都相加，最后就能输出最后的结果

2、B、Intercepted Inputs

Intercepted Inputs 对于这道题目的话，我在比赛的时候想到的方法是计算整个数组的大小是多少，然后，如果是偶数个数的话分为一种情况，如果是奇数的话分为另一种情况，这里当时想分为两种情况是因为在后续处理的时候需要对奇数还是偶数个做出判断，这样才能够正确的判断。

#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#include<vector>

const int N = 2e5 + 10;
int a[N], hash1[N];
int n, m;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(hash1, 0, sizeof(hash1));
        int k; cin >> k;
        for (int i = 1; i <= k; i++)
        {
            cin >> a[i];
            hash1[a[i]]++;
        }
        int sum = k - 2;
        sort(a + 1, a + k + 1);
        int n=0, m=1;
        for (int i = 1; i <= k; i++)
        {
            if (hash1[a[i]] != 0)
            {
                if(sum%2==0)
                {
                    if(sum%a[i]==0)
                    {
                        if(hash1[sum/a[i]]!=0)
                        {
                            n=a[i]; 
                            m=sum/a[i];
                        }
                    }
                }
                else
                {
                    if(sum%a[i]==0)
                    {
                        if(hash1[sum/a[i]]!=0)
                        {
                            n=a[i];
                            m=sum/a[i];
                        }
                    }
                }
            }
            else
                continue;
        }
        cout << n << " " << m << endl;
    }
    return 0;
}

但是我觉得我的代码好像是有点冗余了。

所以比赛结束之后，看了网上还有别人的代码，总结下来还有两种方法。一种方法是sort整个的数组，然后进行前后指针的双指针遍历，当符合要求的时候退出双指针循环的条件，此时的双指针一个指向最小的，另一个指向最大的数。因为题目中说了，一定有一个解，所以在双指针寻找位置的时候，我们可以没必要的设置while循环中的 i<=j 的条件。还有一种其实和我的差不多。就是把我这里使用的不规范的hash1改写成了map，来帮助我去减少时间的开销，并且方便寻找。

#include<bits/stdc++.h>
using namespace  std;
typedef long long ll;
void solve() {
    int n;
    cin>>n;
    int sum=n-2;
    unordered_map<int,int> hash;
    vector<int> v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        hash[v[i]]++;
    }
    for(int i=0;i<n;i++)
    {
        int a=sum/v[i];
        if(sum%v[i]==0&&hash[a])
        {
            if(a==v[i])
            {
                if(hash[a]>=2)
                {
                    cout<<a<<" "<<v[i]<<endl;
                    return;
                }
            }
            else
            {
                cout<<a<<" "<<v[i]<<endl;
                return;
            }
 
        }
    }
}
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

3、C、Superultra’s Favorite Permutation

Superultra’s Favorite Permutation 这道题目就是让我得出灰名不应该想那么多的结论，因为这道题目的话我一开始想的方案是去执行递归，但是递归的话一直不能过，一直超时，所以我怀疑自己怀疑了很长时间，是不是递归写错了，其实不然，真真写错的是我的思路，我不应该去直接的暴力，因为对于一个满足题目要求的方案就是讲奇数和奇数组合，偶数和偶数组合，然后确定最小存在奇数和偶数相邻存在的方案。这个方案最小就是奇数为5，偶数为4。所以这样的话，我们只需要判断是否n>=5，如果不是的话，能够直接判断不能组成一个符合条件的方案，但是如果大于5的话，就一定能够符合。

#include <iostream>
#include <vector>
using namespace std;
#include<cstring>
#include<algorithm>

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        if (n < 5)
        {
            cout << -1 << endl;
            continue;
        }
        else
        {
            for (int i = 1; i <= n; i += 2)
            {
                if (i == 5)continue;
                cout << i << " ";
            }
            cout << 5 << " " << 4 << " ";
            for (int i = 2; i <= n; i += 2)
            {
                if (i == 4)continue;
                cout << i << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

哈哈，恍然大明白了，对于一个上多分的机会就那么溜走了，让我知道在这个问题前思维是最重要的，不要被刻板想法给误导了。