寒假刷题第11天

PTA甲级

1067 Sort with Swap(0, i)

将0作为哨兵，每次和这个元素进行交换，如果0号位不是0，则证明有没有排好序，将每一个元素和0号交换，排完之后，如果还是没有在合适的位置，将该位置与0交换即可。

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        int x;
        cin >> x;
        a[x] = i;
    }
    int res = 0;
    for(int i = 1;i < n;i ++)
    {
        if(i != a[i]) // 没有在正确的位置
        {
            while(a[0] != 0) // 0的位置有其他的元素占用
            {
                swap(a[0] , a[a[0]]); // 交换到适合的位置
                res ++;
            }
            if(i != a[i]) // 还是没有在正确的位置
            {
                swap(a[0] , a[i]); // 将该位置与0交换
                res ++;
            }
        }
    }
    cout << res << endl;
    return 0;
}

1068 Find More Coins

dp或者dfs

dfs（29分）

#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
int n , m;
int a[N];
vector<int>path;
bool st[N];

inline void dfs(int u , int sum , vector<int>&p)
{
    if(sum == m)
    {
        path = p;
        return ;
    }
    if(u > n || sum > m || a[u] > m || path.size()) return ;
    // 选择u
    p.push_back(a[u]);
    dfs(u + 1 , sum + a[u] , p);
    // 恢复现场
    p.pop_back();
    
    // 不选择u
    dfs(u + 1 , sum , p);
}

int main()
{
    scanf("%d %d" ,&n ,&m);
    for(int i = 1;i <= n;i ++)
        scanf("%d" ,&a[i]);
    sort(a + 1 , a + n + 1);
    vector<int>p;
    dfs(1 , 0 , p);
    if(!path.size()) puts("No Solution");
    else 
    {
        for(int i = 0;i < path.size();i ++) 
        {
            if(i) printf(" ");
            printf("%lld" , path[i]);
        }
    }
    return 0;
}

1071 Speech Patterns

from collections import Counter
s = input()
s = s.lower()
for i in range(200):
    ch = chr(i)
    if ord('0') <= i <= ord('9') or ord('a') <= i <= ord('z'):
        continue
    if ord(' ') == i:
        continue
    s = s.replace(ch , ' ')
s = s.split()
res = list(dict(Counter(s)).items())
res = sorted(res , key = lambda x : (not x[0] , x[1]))[-1]
print(res[0] , res[1])