1 月 30 日算法练习-思维和贪心

文章目录

重复字符串
翻硬币
乘积最大

重复字符串

请添加图片描述
思路：判断是否能整除，如果不能整除直接退出，能整除每次从每组对应位置中找出出现最多的字母将其他值修改为它，所有修改次数即为答案。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int k;
char s[N];
int cnt[30];

int main( ){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
 
    scanf("%d\n%s",&k,s+1);

    if(strlen(s+1)%k){
        cout<<-1<<'\n';
        return 0;
    }
    
    int ans=0,n = strlen(s+1)/k;
    
    for(int i = 1;i<=n;i++){
        int ma = 0;
        
        for(int j = 0;j<=25;j++)cnt[j] =0;
        
        for(int j=1;j<=k;j++){
            char x = s[i + (j-1)*n];
            cnt[ x - 'a' ]++;
            ma = max(ma,cnt[x-'a']);
        }
        ans += k -ma;
    }
    
    cout<<ans<<'\n';
    return 0;
}

翻硬币

小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

**********
o****o****

输出样例1：

思路：从前往后枚举硬币，计数过程中翻转后一枚硬币。

#include<iostream>
#include<string>
using namespace std;
string s,d;
int main( ){
    cin>>s>>d;
    int cnt = 0,len=s.length();
    for(int i = 0;i<len;i++){
        if(s[i]!=d[i]){
            cnt++;
            if(s[i+1]=='*')s[i+1]='o';
            else s[i+1]='*';
        }
    }
    cout<<cnt<<'\n';
    return 0;
}

做法二：考验思维，硬币一共有两种情况，第 i 个不同，第 i+1 可能相同也可能不同。当第 i 个不同时，第 i+1 个相同翻的时候后面会变成不同，所以要一直往后翻直到找到不同，期间就是一组翻硬币次数。由于题目没有要我们输出不能成功翻硬币的输出，所以硬币一定能翻成功，即不同个数一定是偶数。

#include<iostream>
#include<vector>
using namespace std;
signed main( ){
    string s,d;
    int cnt = 0;
    cin>>s>>d;
    vector<int>vec;
    
    for(int i=0;i<s.size();i++)if(s[i]!=d[i])vec.push_back(i);
    
    for(int i=0;i<vec.size();i+=2)cnt+=vec[i+1]-vec[i];
    
    cout<<cnt<<'\n';
    return 0;
}

乘积最大

给定N个整数A1, A2, … AN。请你从中选出K个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。
注意，如果X<0，我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
即：0-((0-x) % 1000000009)
【输入格式】
第一行包含两个整数N和K。
以下N行每行一个整数Ai。
对于40%的数据，1 <= K <= N <= 100
对于60%的数据，1 <= K <= 1000
对于100%的数据，1 <= K <= N <= 100000 -100000 <= Ai <= 100000
【输出格式】
一个整数，表示答案。
【输入样例】
5 3
-100000
-10000
2
100000
10000
【输出样例】
999100009
再例如：
【输入样例】
5 3
-100000
-100000
-2
-100000
-100000
【输出样例】
-999999829
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

思路：思维题，把所有情况都考虑到。如果用动态规划只能过一半。
在这里插入图片描述

#include<iostream>
using namespace std;
int n,k;
const int N = 1e5+10,mod = 1e9+9;
long long  res = 1;
int cnt1,cnt2;
int a[N];

int main( ){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>=0)cnt1++;
        else cnt2++;
    }
    sort(a+1,a+1+n);
    if(k==n){
        for(int i = 1;i<=n;i++) res *= a[i],res%=mod;
        cout<<res<<'\n';
    }else if(!cnt2){
        for(int i=n;i>=n-k+1;i--)res *= a[i],res%=mod;
        cout<<res<<'\n';
    }else if(!cnt1){
        if(k&1)for(int i=n;i>=n-k+1;i--)res = res*a[i]%mod;
        else for(int i=1;i<=k;i++)res = res*a[i]%mod;
        cout<<res<<'\n';
    }else{
        int p = 1;
        while(k>cnt1){
            res *= (a[p]*a[p+1])%mod,res %= mod;
            p+=2,k-=2;
        }
        
        int p1 = p,p2 = n;
        while(k>1){
            if(a[p1]*a[p1+1] >= a[p2]*a[p2-1]){
                res *= (a[p1]*a[p1+1])%mod,res %= mod;
                p1+=2;
            }else{
                res *= (a[p2]*a[p2+1])%mod,res %= mod;
                p2-=2;
            }
            k-=2;
        }
        if(k)res = res*a[p2]%mod;
        cout<<res<<'\n';
    }
    
    return 0;
}