1. 周期字符串
小红有一个长度为n的字符串s,由0、1和 * 组成,可以把*替换成0或者1,
小红想知道替换后的字符串的最短周期是多少,如果一个字符串每一个位置的字母都与后k位的字母相同,那么k即为该字符串的一个周期。
形式化的说,如果存在一个正整数k使得对于所有的 i属于[1,n - k] 都有 s[i]= s[i+k] ,那么称k是字符串s的周期。
简单枚举
int main() {
string s;
cin>>s;
int n = s.size();
for(int k=1;k<n;k++){
string cur = s;
bool flag = true;
for(int i=0;i<n-k;i++){
if(cur[i]=='*') continue;
if(cur[i]!=cur[i+k]){
if(cur[i+k]=='*')
cur[i+k] = cur[i];
else{
flag = false;
break;
}
}
}
if(flag){
cout<<k<<endl;
break;
}
}
return 0;
}
2. 经过原点的点对
二维平面上有几 个整点 a[1],a[2],·..,a[n],其中第个点的坐标为(i,a[i])。
小苯想知道有多少个点对“,j满足第i个点和第j个点的连线所在的直线恰好经过原点,请你帮他算一算吧。
哈希计数
int main() {
int n;
cin>>n;
vector<int> nums(n+1);
int res = 0;
unordered_map<double,int> mp;
for(int i=1;i<=n;i++){
cin>>nums[i];
double k = (double)nums[i]/i;
if(mp.count(k)) res+=mp[k];
mp[k]++;
}
cout<<res<<endl;
return 0;
}
3. 糖果最小值
小苯面前有n 堆糖果,其中第i堆糖果里有a[i]个糖果,小苯现在希望从中选择恰好两堆糖果带走,
选择后他会施法将自己的糖果数量乘上k,剩下的所有糖果都是格格的,他希望他和格格的糖果数量尽可能接近,
假设小苯拿走的糖果数量为x,格格拿走的数量为 y,即他希望:|k*x- y|的值尽可能小 请你帮他求出这个最小值吧。
红黑树维护最接近的值
int main() {
int n,k;
cin>>n>>k;
vector<int> nums(n);
for(int i=0;i<n;i++)
cin>>nums[i];
int sum = accumulate(nums.begin(),nums.end(),0);
//target*k = sum-target
double target = (double)sum/(k+1);
int res = INT_MAX;
//维护一个数据结构,寻找离指定值最接近的数,这里使用红黑树
set<double> st;
for(int i=0;i<n;i++){
double first = target-nums[i];
auto it = st.lower_bound(first);
if(it!=st.end()){
int x = (int)(*it + nums[i]);
res = min(res,abs(k*x-(sum-x)));
}
if(it==st.begin()){
st.insert((double)nums[i]);
continue;
}
auto pre = prev(it);
if(pre!=st.end()){
int x = (int)(*pre + nums[i]);
res = min(res,abs(k*x-(sum-x)));
}
st.insert((double)nums[i]);
}
cout<<res<<endl;
return 0;
}
4. 最小生成树
小红有一张联通无向图,她希望找到这张图的一棵生成树,使得1号点和n 号点的度数之差尽可能大。
请你帮助她找到这样一棵生成树 对于一张图,选择其中n-1条边,使得所有顶点联通,
这些边一定会组成一棵树,即为这张图的一棵生成树。可以证明,图中存在至少一棵生成树。
kruskal算法生成树,这里优先拓展节点1或者节点n
int main() {
int n,m;
cin>>n>>m;
vector<int> cnt1(n+1);//每个点的度1
vector<int> cnt2(n+1);//每个点的度2
vector<vector<int>> nums(m+1,vector<int>(4));
for(int i=1;i<=m;i++){//遍历所有边
int from,to;
cin>>from>>to;
nums[i] = {0,i,from,to};
if(from==1||to==1) nums[i][0]--;
if(from==n||to==n) nums[i][0]++;
}
vector<int> res1;//让节点1更多的结果
vector<int> res2;//让节点n更多的结果
sort(nums.begin(),nums.end());
for(int i=0;i<=m;i++){//优先拓展节点1
if(nums[i][1]==0) continue;//多加了个空边的去掉
if(cnt1[nums[i][2]]>0&&cnt1[nums[i][3]]>0) continue;
cnt1[nums[i][2]]++;
cnt1[nums[i][3]]++;
res1.push_back(nums[i][1]);
}
for(int i=m;i>=0;i--){//优先拓展节点n
if(nums[i][1]==0) continue;//多加了个空边的去掉
if(cnt2[nums[i][2]]>0&&cnt2[nums[i][3]]>0) continue;
cnt2[nums[i][2]]++;
cnt2[nums[i][3]]++;
res2.push_back(nums[i][1]);
}
if(abs(cnt2[n]-cnt2[1])>abs(cnt1[1]-cnt1[n]))
swap(res1,res2);
for(int i=0;i<res1.size();i++){
if(i!=0) cout<<" ";
cout<<res1[i];
}
return 0;
}
标签:25,字节,nums,int,2024.08,vector,cnt2,cnt1,糖果
From: https://www.cnblogs.com/929code/p/18406653