首页 > 其他分享 >2024.08.25字节

2024.08.25字节

时间:2024-09-10 16:40:12浏览次数:12  
标签:25 字节 nums int 2024.08 vector cnt2 cnt1 糖果

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

相关文章

  • 2024.08.31美团
    1.小美的姓名统计小美写单词喜欢横着写,她记录了若干个人的名字,但是不小心加进去了一些无关的单词。一个名字单词以大写字母开头,请你帮助她统计共有多少个人的名字。简单输入处理intmain(){stringcur;intres=0;while(cin>>cur){if(cur[0]>='A'......
  • 250M高速采样数字化仪、2路同步AD数据采集卡——PCIe8912M/8914M/8916M
    品牌:阿尔泰科技型号:PCIe8912M/8914M/8916M概述:PCIe8912M/8914M/8916M数据采集卡,该板卡提供250MS/s12/14/16位2通道同步采样数字化仪,专为输入信号高达100M的高频和高动态范围的信号而设计。与Labview无缝连接,提供图形化API函数。模拟输入范围可以通过软件编程设置为±1V......
  • 【闲话】09.09.25
    0909闲话头图:K7有了,那K8联军的事就要提上日程了今日推歌:《余裕欲feat.nagi&カゼヒキ》稲葉曇もったいないフレーバー这么好的味道真是可惜了啊わかりたかったけど虽然我想要去了解とっておきのデザートは但珍藏的甜点已然无用ダメになってから捨(す)てようかな......
  • linux删除0字节文件
    实现方式:find-typef-size0-execrm-rf{}\;[root@logstash~]#find-typef-size0-execls-l{}\;-rw-r--r--1rootroot0Jul1914:39./a.txt-rw-r--r--1rootroot0Jul1914:39./b.txt-rw-r--r--1rootroot0Jul1914:39./c.txt-rw-r--r--1......
  • 2563. 统计公平数对的数目
    题目链接2563.统计公平数对的数目思路排序+二分(upper_bound-lower_bound)题解链接两种方法:二分查找/三指针(Python/Java/C++/Go)关键点排序并不影响答案(数对数量未变化)时间复杂度\(O(n\logn)\)空间复杂度\(O(1)\)代码实现:classSolution:d......
  • 2529. 正整数和负整数的最大计数
    题目链接2529.正整数和负整数的最大计数思路二分法题解链接标准库调用关键点0的处理时间复杂度\(O(\logn)\)空间复杂度\(O(1)\)代码实现:classSolution:defmaximumCount(self,nums:List[int])->int:deflower_bound(val):......
  • 代码随想录训练营第25天|set去重
    491.非递减子序列classSolution{public:vector<vector<int>>result;vector<int>path;voiddfs(vector<int>&nums,intstartIdx){if(startIdx==nums.size()){return;}unordered_set&......
  • 【Java毕设最新选题推荐2025】基于springboot的酒店管理系统
    摘 要21世纪的今天,随着社会的不断发展与进步,人们对于信息科学化的认识,已由低层次向高层次发展,由原来的感性认识向理性认识提高,管理工作的重要性已逐渐被人们所认识,科学化的管理,使信息存储达到准确、快速、完善,并能提高工作管理效率,促进其发展。论文主要是对酒店管理系统......
  • P5025
    高效高效,坚持高效,耶(•̀ω•́)y首先,我们考虑引爆每个炸弹,它能引爆的区间是多少(即:它能对答案做出什么贡献)易得炸一个=炸这个区间为什么?你只要引爆了一个大炸弹(例如沙皇)它就会把它的左边和右边一起抬走所以考虑线性维护每个炸弹向左/向右能炸到哪里代码十分精华:#inclu......
  • 2024.08.28得物(超简单)
    1.拨动数字已知小红每次可以把一个数字向下拨动,即9变成8,8变成7...1变成0,0变成9。她想知道从第一个状态变成第二个状态需要最少拨动多少次?简单打卡intmain(){stringa,b;cin>>a>>b;intres=0;for(inti=0;i<a.size();i++){intnum1=a[i]-......