做题总结

2021.12.18

贪心____T1279 最小距离字符串

定义两个长度相等的字符串 A, B 的距离 dis(A,B)dis(A,B) 等于：A 和B 有几个位置不同。

给定三个长度为 nn 的小写字母字符串 A,B,C，求一个长度为n的字符串S，满足 dis(S,A)+dis(S,B)+dis(S,C)dis(S,A)+dis(S,B)+dis(S,C) 最小，为了方便，你只需要输出最小的 dis(S,A)+dis(S,B)+dis(S,C)dis(S,A)+dis(S,B)+dis(S,C)。

思路：string中的size()表示字符串中真实有意义的字符的长度，结束符只是用于标记该字符串的结束，并无实际意义，所以不算在长度里面。通过set的特点，去除重复的，以此可以得到不同的字母的个数。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
char a[N];
char b[N];
char c[N];
int main()
{
    cin>>a>>b>>c;
    int l = strlen(a);
    int ans = 0;
    set<int>str;
    for(int i = 0;i<l;i++)
    {
        str.clear();
        str.insert(a[i]);
        str.insert(b[i]);
        str.insert(c[i]);
         if(str.size() == 2){
                ans ++;
            }
        else if(str.size() == 3){
                ans += 2;
            }
    }
    cout<<ans<<endl;
    return 0;
}

CF____T1079 开关灯

假设有 N盏灯（N 为不大于5000 的正整数），从 1到 N 按顺序依次编号，初始时全部处于开启状态；有 M 个人（M 为不大于 N 的正整数）也从 1到 M 依次编号。

第一个人（1 号）将灯全部关闭，第二个人（2 号）将编号为 2 的倍数的灯打开，第三个人（3号）将编号为 3 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和 3 号一样，将凡是自己编号倍数的灯做相反处理。

请问：当第 M 个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用逗号间隔。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+10;
bool a[N];
//0 ——开启 1——关闭 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		for(int j = i;j<=n;j+=i)
		{
			a[j] = a[j] ^ 1;
		}
	}
	cout<<1;
    for(int i = 2; i <= n; i++)
        if(a[i] == 1)			
		cout<<","<<i;
			
	return 0;
 }