蓝桥杯真题——洛谷day11 枚举，找规律，数字三角形dp

目录

找规律

P8692 [蓝桥杯 2019 国 C] 数正方形

思路：

代码：

枚举

P8739 [蓝桥杯 2020 国 C] 重复字符串

思路：

代码：

---

找规律

P8692 [蓝桥杯 2019 国 C] 数正方形

思路：

代码：

注意：一定要开long long 

建议使用

typedef long long ll;

格式，使得后面使用ll定义的都是long long

#include<iostream>using namespace std;const long long int mod=7+1e9;
int main()
{int n;cin>>n;long long int  ans=0;for(int i=1;i<n;i++)//遍历边长为i的正方形{ans=(ans+i*(n-i)*(n-i))%mod;}cout<<ans<<endl;return 0;
}

枚举

P8739 [蓝桥杯 2020 国 C] 重复字符串

思路：

题目相当于s由k个子串构成
先将s分割为k个部分，即s.size()/k=n，n为每个部分的长度，对每一个部分的同一个位置进行同时遍历
判断是否相同，对出现次数少的进行修改，改为出现次数多的字母
还要进行特判：判断s是否能修改成k次重复字符串

代码：

#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;int main()
{int k; cin>>k;string s; cin>>s;int cnt=s.size();if(cnt%k!=0)//s是k次重复字符串代表s的长度是k的倍数，若此时余数不为0，就代表s无法转换 {cout<<"-1"<<endl;return 0;}int t=cnt/k;//子串的长度int ans=0; for(int i=0;i<t;i++)//第一次遍历，遍历每一个子串的位置 {map<char,int> mp;//用桶记录每个字母的次数int mx=0;//记录子串中出现次数最多的字母数for(int j=i;j<s.size();j+=t)//遍历每个子串第i个位置 {mp[s[j]]++;mx=max(mx,mp[s[j]]);}ans+=k-mx;//将k个子串减去不需要改变的字母数量即可得到需要改变的字母的数量 } cout<<ans<<endl;return 0;
}