首页 > 其他分享 >2023.11.21做题笔记(对局匹配,砝码称重shui,单词接龙)

2023.11.21做题笔记(对局匹配,砝码称重shui,单词接龙)

时间:2023-11-21 18:22:21浏览次数:37  
标签:ch 21 int 2023.11 ++ length 做题 str include

今天水了一节英语课,翘了一节C++课,就是感觉摆的一批。

 

对局匹配

P8656 [蓝桥杯 2017 国 B] 对局匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


 

 

 对于这道题:

大佬解法1:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, k, a[N], ans, cnt[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }
    if(k == 0)
    {
        for(int i = 0; i <= 100000; i++)
            if(cnt[i])
                ans++;
        cout << ans;
        return 0;
    }
    for(int i = 0; i <= 100000 - k; i++)
    {
        if(cnt[i] < cnt[i + k])
            cnt[i + k] -= cnt[i];
        else   
            cnt[i + k] = 0;
    }
    for(int i = 0; i <= 100000 - k; i++)
        ans += cnt[i];
    cout << ans;
    return 0;
}

好像是用了什么桶之类的东西,不过目前我还没学过,先不管

就是假如k=1, a[2]=3(3个人),a[3]=4(4个人),a[5]=1(1个人)

那么,积分为2和积分为3的人可以匹配,因为匹配是两个人嘛,所以噶掉其中一个,保留另一半,此时a[3]=4-3=1,然后到了后面算a[4]的时候,因为我们每次噶掉的是后面的人,所以保证了前面的都算过而且下一次算后面的人的时候不会有重复或者遗漏(也就是说,我每次算的时候统一让他保留小的,达成一致,这样就不会出问题),有一种1+1=0的感觉。

dp方法:

有一说一这道题的标签是dp,但是我死活想不出来它的状态转移方程(因为我还是一只蒟蒻),所以copy了佬的题解

 下面是代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

inline int read() {
    int x(0),f(0);
    char ch=getchar();
    for(; !isdigit(ch); ch=getchar()) f|=(ch=='-');
    for(;  isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
    return f?-x:x;
}

int n,k,ans;
int a[N],d[N],g[N];
int dp[N][2];
vector<int> v[N];

int main() {
    n=read(), k=read();
    for(int i = 1; i <= n; i++) a[i]=read(),d[a[i]]++;;
    sort(a+1, a+n+1);
    int m = unique(a+1, a+n+1)-a-1;
    if(k == 0) {
        printf("%d\n", m);
        return 0;
    }
    for(int i = 1; i <= m; i++) {
        g[a[i]]++;
        if(g[a[i]] == 1)
            v[a[i] % k].push_back(i);
    }
    // dp
    for(int i = 0; i < k; i++) {
        if(v[i].empty()) continue;
        int siz = v[i].size();
        memset(dp, 0x3f, (siz + 5) * sizeof(dp[0][0]));
        for(int j = 0; j < siz; j++) {
            if(j == 0) dp[0][1] = d[a[v[i][j]]], dp[0][0] = 0;
            else if((a[v[i][j]] - a[v[i][j-1]]) == k) {
                dp[j][0] = max(dp[j-1][1], dp[j-1][0]);
                dp[j][1] = dp[j-1][0] + d[a[v[i][j]]];
            } else {
                dp[j][0] = max(dp[j-1][1], dp[j-1][0]);
                dp[j][1] = max(dp[j-1][1], dp[j-1][0]) + d[a[v[i][j]]];
            }
        }
        ans += max({dp[siz - 1][0], dp[siz - 1][1]});
    }
    printf("%d\n",ans);
}

。。。。。。


砝码称重

 P2347 [NOIP1996 提高组] 砝码称重 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


我fu了,我是sb好吧

 典:背包题,属于能否/判断的背包,能否到达型,下面是题解

#include<iostream>
using namespace std;

const int N=1005;
int m[N],a[7];
int ans=0,maxn=0;

void solution(int a[])
{
    for(int i=1;i<=6;i++)   //第i种砝码
    {
        int l;
        if(i==4)l=5;
        else if(i==5)l=10;
        else if(i==6)l=20;
        else l=i;                   //l是重量
        for(int j=0;j<a[i];j++) //放j个的情况
        {
            for(int k=N-l;k>=0;k--) if(m[k])m[k+l]=1;
        }
    }
    for(int i=0;i<N;i++)if(m[i])ans++;
    ans--;
}

int main()
{
    m[0]=1;
    for(int i=1;i<=6;i++)cin>>a[i];
    solution(a);
    cout<<"Total="<<ans;
    system("pause");
    return 0;
}

核心就是判断重量x是否成立,如果成立,那么重量x+k也成立

这道题数据太水了,以至于我看到有人说六个循环都能过,六个循环就是枚举,我甚至看到有人用二进制优化(bushi)来讽刺这道题的水数据,我写的巨拉,建议跳过不要看

下面是佬的题解:

佬:我们用一个bitset保存每个重量能否被称出即可。

#include <bitset>
#include <cstdio>
int a[10], w[10] = {1, 2, 3, 5, 10, 20};
std::bitset<1010> S;
int main() {
    for(int i = 0; i < 6; i++) scanf("%d", a + i);
    S[0] = 1;
    for(int i = 0; i < 6; i++) for(int j = 0; j < a[i]; j++) S |= S << w[i];
    printf("Total=%d\n", S.count() - 1);
    return 0;
}

。。。。。。


 单词接龙

P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


我不会,无法从我的大脑里面搜索到相关内容,但是我觉得有必要学习

佬:

C++

#include<bits/stdc++.h>
using namespace std;
string str[20];
int use[20], length = 0, n;
int canlink(string str1, string str2) {
    for(int i = 1; i < min(str1.length(), str2.length()); i++) {//重叠长度从1开始,直到最短的字符串长度-1(因为不能包含)
        int flag = 1;
        for(int j = 0; j < i; j++)
            if(str1[str1.length() - i + j] != str2[j]) flag = 0;//逐个检测是否相等
        if(flag) return i;//检测完毕相等则立即return
    }
    return 0;//无重叠部分,返回0
}
void solve(string strnow, int lengthnow) {
    length = max(lengthnow, length);//更新最大长度
    for(int i = 0; i < n; i++) {
        if(use[i] >= 2) continue;//该字符串使用次数需要小于2
        int c = canlink(strnow, str[i]);//获取重叠长度
        if(c > 0) {//有重叠部分就开始dfs
            use[i]++;
            solve(str[i], lengthnow + str[i].length() - c);
            use[i]--;
        }
    }
}
main() {
    cin >> n;
    for(int i = 0; i <= n; i++) use[i] = 0, cin >> str[i];//str[n]为开始字符 
    solve(' '+str[n], 1);//有必要解释一下开始阶段。为了指定第一个字符,而且因为canlink需要重叠部分小于最短长度-1,所以要从前面添加一个无意义充长度的‘ ’。这样就强制了canlink函数比较最后一位。
    cout << length ;
}

好,点到为止。

 

标签:ch,21,int,2023.11,++,length,做题,str,include
From: https://www.cnblogs.com/bosssz/p/17846821.html

相关文章

  • SQL 做题记录
    SQL技能在很多岗位都有涉及,如数据分析师、DBA、研发、大数据工程师....不同的岗位对知识的要求不尽相同,本文关注点目前在于数据分析、取数、查询等日常操作上。大学时期虽然有学习过数据库课程(其中对SQL有所涉及),但工作中使用场景不多,存在一些似是而非的概念,因此通过刷leetcod......
  • ESD保护二极管 RCLAMP0521P-N参数详解
    市场上有选用东沃电子推出的RCLAMP0521P-N低电容ESD静电保护器件应用于天线静电防护。天线广泛出现于便携式电子产品中,众所周知,天线所接受的信号容易受到电磁、静电干扰,因此ESD静电保护器件成为了天线常见的搭配器件。考虑到天线所使用的频段,以及不同频段所能够接受的最小寄生电容......
  • 2023.11.21——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.JavaGUI2.会话跟踪技术明日计划:学习......
  • 11.21每日总结
    今日时间:5h代码行数300学习内容:早上学习大数据的hbase的知识,打开hbase的指令是hbase打开方法,/export/server/hbase/bin/hbaseshell点击list查看表创建表得自己创建,creat‘表名’,‘列1‘,’列2‘,不知怎么必须用创建的,自己的还不行,还得是英文,学习计算机全是英文,当初我们的老祖......
  • 2023-2024-1 20211211 《信息安全系统设计与实现(上)》第13章
    1网络编程简介TCP/IP协议、UDP和TCP协议、服务器-客户机计算、HTTP和Web页面、动态Web页面的PHP和CGI编程2TCP/IP协议IPv432位地址IPv6128位地址TCP/IP协议顶层是使用TCP/IP的应用程序,用于登录到远程主机的ssh,用于交换电子邮件的mail、用于Web页面的http等应用程序需要......
  • 11.21-task2
    启航!c语言与python的区别打印helloworld时:c语言python:与c相比,python显然更加简单,优雅!python注释注释是用来对你写的代码进行解释和说明,能大幅度提升写代码时的逻辑性并让别人容易理解。。。。单行注释用#开头(只能写在一行)多行注释用'''或“”“包裹but这并......
  • 每日总结-23.22.21
    <!doctypehtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1"><metahttp-equiv="X-UA-Compatible......
  • 百度网盘(百度云)SVIP超级会员共享账号每日更新(2023.11.21)
    百度网盘会员账号共享(11.21更新)账号:aro85342密码:zdzv4086账号:3719heuk密码:303ulok账号:13262017701密码:4307uqg账号:5815hewo密码:886pinx账号:4636gpxt密码:1529oux共享账号存在密码被修改的可能,请谨慎使用。小编保持实时更新,希望给大家挖掘到更多有用的信息!如上述共享账......
  • 2023-11-21 托管第三方开发的小程序如何加急发布?==》需要调用微信提供的接口去发布
    接口地址:https://developers.weixin.qq.com/doc/oplatform/openApi/OpenApiDoc/miniprogram-management/code-management/speedupCodeAudit.html 你可以在这里调试:https://developers.weixin.qq.com/apiExplorer?apiName=startPushTicket&plat=thirdparty 注:审核单id为你提......
  • Spring_202311_21_2 2. AOP面向切面编程
    Spring_202311_21_22. AOP面向切面编程AOP:全称是AspectOrientedProgramming即:面向切面编程。简单的说它就是把我们程序重复的代码抽取出来,在需要执行的时候,使用动态代理的技术,在不修改源码的基础上,对我们的已有方法进行增强。即当需要扩展功能时,传统方式采用纵向继承方式......