首页 > 其他分享 >2023-2-训练赛5 题解

2023-2-训练赛5 题解

时间：2023-01-09 23:57:00浏览次数：44  
标签：std 10 int 题解 namespace 训练赛 2023 using include

Buctoj 训练赛5 题解(C++)

A、统计单词数

该题目考查对string字符串的灵活运用
初步观察题目，可将解题步骤分为大致四个模块

  1. 输入两行字符串
  2. 由于题目要求不区分大小写，故将其全部转化为大写或小写（代码中为小写）
  3. 用空格将第二行句子分为单词与第一行单词进行比对（string字符串检测是否相等即可）
  4. 记录第一个配对成功的首字母位置和配对成功次数并输出
#include <bits/stdc++.h>
using namespace std;

int pos=-1, ans=-1, tpos=0; //pos记录单词首字母出现的位置，ans记录配对成功次数，tpos记录总单词数
//由于没找到结果时要求输出-1，建议将初始值设置为-1
string a, s, tmp; 


int main()
{
    //模块一
    getline(cin, a);
    getline(cin, s); //getline() 用于读取整行字符串

    //模块二
    int lena=a.size(), lens=s.size();
    for(int i=0; i<lena; i++) //注意string字符串从0开始
        if(a[i]>='A' && a[i]<='Z') a[i]+=32;
    for(int i=0; i<lens; i++)
        if(s[i]>='A' && s[i]<='Z') s[i]+=32;

    //模块三
    for(int i=0; i<lens; i++)
    {
        if(s[i]!=' ') tmp+=s[i];
        else if(tmp==a)
        {
            if(pos==-1) pos=i-tmp.size();
            if(ans==-1) ans=0;
            ans++, tpos++;
            tmp.clear(); //可以清空临时字符串
        }
        else
            tmp.clear(), tpos++;
    }
    
    //模块四
    if(ans!=-1) cout<<ans<<" "<<pos;
    else cout<<-1;

    return 0;
}

B、单词替换

本题与上题类似，但本题主要考察多个字符串的存储
string a[] 可以保存多个字符串，注意不要与已经string a后的a[]混淆
初始化为a[]，a[]的每个元素表示一个字符串
初始化为a, a[]的每个元素表示字符串中的一个字符
所以string这里真的很烦

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

string s, a, b;
char tmp=' ';
string t[101];
int k, wor;

int main()
{
    //在读取第一行的时候利用string数组直接将词与词分开存储
    while(tmp==' ')
    {
        k++;
        cin>>t[k];
        tmp=getchar();
    }

    //后面就是比对了
    cin>>a>>b;
    for(int i=1; i<=k; i++)
        if(a==t[i]) t[i]=b;
    for(int i=1; i<=k; i++)
    {
        if(i==1) cout<<t[i]; //这里为了防止输出末尾出现空格可能影响评判结果
        else cout<<" "<<t[i];
    }
    return 0;
}

C、确定进制

此题我的思路很怪，仅供参考
看到此题，首先想到的是，我应该把所有的数转换为10进制再计算，于是我写了这样一个转换函数

int change(int x, int y) //x为进制数，y为待转换数
{
    int tmp[8], k=0;
    long long ans=0;
    while(y>0)
    {
        k++;
        tmp[k]=y%10;
        y/=10;
    }
    for(int i=0; i<k; i++)
        ans+=tmp[i+1]*pow(x, i);
    return ans;
}

把每位拆开，再按照很简单的x进制向10进制转换的小公式转换，这样就成功把一个x进制的数转换为了10进制的数
那么怎么保证该数在某进制下合法呢
我们就要找到p、q、r中最大的一位数
如样例
6 9 42
中，9就是最大的一位数，那它就不可能被9+1=10进制以下的进制表示
由于题目中给的全部都是整数，即全部可以用十进制表示，我们正好就用上文提到的转换函数找到了最大的一位数，暂且将其表示为maxx
用maxx+1来代表将来搜索时的左边界，那右边界呢？当然是p，q，r里面最大的数，设为maxt，因为进制数如果大于maxt，再大多少也是一样的结果
for(int i=maxx+1; i<=maxt; i++)
我们就得到了如上搜索范围，循环里面就像下面这样写就可以了

  pc=change(i, p), qc=change(i, q), rc=change(i, r);
  if(pc*qc==rc) {cout<<i; exit(0);}

但是一旦遇到特别大的数，change()里的pow()是扛不住的，我们就要提早判断循环结束条件
也就是说一旦进制数大于10，p*q还是小于r，那无论多大的进制数都无法使他们相等了
所以加一条
if(pc*qc<rc && i>=10) {cout<<0; exit(0);}
最终代码如下：

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

int p, q, r, maxx, maxt;
int pc, qc, rc; //转换为10进制之后的p,q,r

int change(int x, int y)
{
    int tmp[8], k=0;
    int ans=0;
    while(y>0)
    {
        k++;
        tmp[k]=y%10;
        y/=10;
        maxx=max(maxx, tmp[k]);
    }
    for(int i=0; i<k; i++)
        ans+=tmp[i+1]*pow(x, i);
    return ans;
}

int main()
{
    cin>>p>>q>>r;
    pc=change(10, p), qc=change(10, q), rc=change(10, r);
    maxt=max(p, q), maxt=max(maxt, r), maxt=min(100000, maxt);
    for(int i=maxx+1; i<=maxt; i++)
    {
        pc=change(i, p), qc=change(i, q), rc=change(i, r);
        if(pc*qc==rc) {cout<<i; exit(0);}
        if(pc*qc<rc && i>=10) {cout<<0; exit(0);}
    }
    cout<<0;
    return 0;
}

D、Vigenere密码

此题是一个简单题，单看代码就能看懂
第一次提交莫名其妙 段错误
又交了一次就正常了，不知道咋回事

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

string k, s;
char ans;
int kk; //密钥k的位数

int main()
{
    cin>>k>>s;
    int lens=s.length(), lenk=k.length();

    //密文的每一位经过密钥计算后直接输出
    for(int i=0; i<lens; i++)
    {
        kk=i%lenk; //使得kk可以循环起来

        //关于大小写的调试
        if(k[kk]>='A' && k[kk]<='Z') ans=s[i]-(k[kk]-'A');
        if(k[kk]>='a' && k[kk]<='z') ans=s[i]-(k[kk]-'a');

        if(ans<'A') ans='Z'-('A'-ans)+1;
        if(s[i]>='a' && s[i]<='z' && ans<'a') ans='z'-('a'-ans)+1;
        cout<<ans;
    }
    return 0;
}

E、【蓝桥杯2021初赛】货物摆放

此题为输出结果题，所以直接暴力

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

typedef long long ll;
const ll n = 2021041820210418;
vector<ll> v;  //懒得去除了直接动态数组

int main()
{
	for(ll i=1; i*i<n; i++)
    {
		if(n%i==0) 
        {
		    v.push_back(i);
		    if(n/i!=i) v.push_back(n/i);
		}
	}
 
	int ans=0; 
	for(int i=0; i<v.size(); i++)
		for(int j=0; j<v.size(); j++)
			for(int k=0; k<v.size(); k++)
				if(v[i]*v[j]*v[k]==n) ans++; //三个循环非常暴力
	cout<<ans;
}

当然提交的时候别忘了把代码改成

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

int main()
{
    cout<<2430;
    return 0;
}

F、【蓝桥杯2021初赛】砝码称重

这是一个基础的背包问题，用动态规划（dp）很简单
我们可以很简单的得到天平的四个状态

如果j=w[i]，说明可以正好一个砝码
如果dp[i-1][j]=1,说明砝码不变
如果dp[i-1][j+w[i]]=1,说明可以加一个砝码
如果dp[i-1][abs(j-w[i])]=1,说明可以减一个砝码（abs()为绝对值）

由此写出代码：

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

int n, ans, sum, w[101];
int dp[101][100001];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        sum+=w[i];
    }
    for(int i=1;i<=n;i++)
    {
		for(int j=sum;j;j--)
        {
            if(j==w[i])dp[i][j]=1;
            else if(dp[i-1][j])dp[i][j]=1;
			else if(dp[i-1][j+w[i]])dp[i][j]=1;
            else if(dp[i-1][abs(j-w[i])])dp[i][j]=1;
        }
	}  
    for(int i=1; i<=sum; i++)
        if(dp[n][i]) ans++;
    cout<<ans;
    return 0;
}

G、最小值-2019

要求区间[l,r]间(i*j)%2019的最小值
很简单
首先，如果l和r的跨度大于2019，那么最小值必定是0
其次，如果再l，r分别对2019取余之后，l是大于r的，说明他们跨越了一个2019的倍数，最小值也必定是0
最后，如果都不是，再暴力求解，就不会超时
代码如下：

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

typedef long long ll; //这范围不开long long风险巨大
ll l, r;
const int mod=2019;

int main()
{
    cin>>l>>r;
    if(r-l>=mod) {cout<<0; exit(0);}
    l%=mod; r%=mod;
    if(l>r) {cout<<0; exit(0);}

    int tmp=mod;
    for(int i=l; i<=r; i++)
        for(int j=i+1; j<=r; j++)
            if(tmp > (i*j)%mod)
                tmp = (i*j)%mod;
    cout<<tmp;
    return 0;
}

H、等于没有比

这道题可以说是入门级别的题，建议当作A题

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

int n, d;

int main()
{
    cin>>n>>d;
    int sum=2*d+1;
    if(n%sum==0) cout<<n/sum;
    else cout<<n/sum+1;
    return 0;
}

I、补题抄题解

这道题我用了快读，否则O(nlogn)的复杂度都会炸
快读之后一下就从2000ms降到40ms，可以说是效果显著
一定记得把快读的模板背了，说不定会用到什么时候

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

int n;
struct node{
    int juan, pos;
}a[200005];
int s[200005]; //由于上面那个结构体数组被我按卷的程度排序了，顺序变了没法输出，所以新建一个数组来存相对应a数组那个人的希望值

//快读（只读正数）
int read()
{
    int f=1,k=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar(); 

    while(c>='0'&&c<='9')
    {
	k=k*10+c-'0';
	c=getchar(); 
    }
    return f*k;
}

inline bool cmp(node x, node y){
    return x.juan>y.juan;
}

int main()
{
    n=read();
    for(int i=1; i<=n; i++)
    {
        a[i].juan=read();
        a[i].pos=i;
    }
    
    sort(a+1, a+n+1, cmp);
    for(int i=1; i<=n; i++)
    {
        if(a[i].juan!=a[1].juan) s[a[i].pos]=a[1].juan;
        else for(int j=2; j<=n; j++)
            if(a[j].juan<=a[i].juan) {s[a[i].pos]=a[j].juan; break;}
    }  
    for(int i=1; i<=n; i++)
        printf("%d\n", s[i]);
    return 0;
}

J、毛遂自荐2

to_string()函数的妙用

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

int n, ans;

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        if(to_string(i).length()%2 == 1) ans++;
    cout<<ans;
    return 0;
}

K、山or水库?

本题本质上为数学问题
很简单的列方程就好
我们设第i座山的雨量为a[i]
设第i个水库的雨量为k[i]
于是可以得到以下方程
k[1]=(a[1]+a[2])/2
k[2]=(a[2]+a[3])/2
k[3]=(a[3]+a[4])/2
...
k[n]=(a[n]+a[1])/2

由此可知

2*(k[1]+k[3]+...+k[n])=2*a[1]+a[2]+a[3]+...+a[n-1]+a[n]
2*(k[2]+k[4]+...+k[n-1])=a[2]+a[3]+...+a[n-1]+a[n]
令k[奇数]的和=kj，k[偶数]的和=ko
上面的式子减去下面的式子，就得到
2*(kj-ko)=2*a[1]
即
a[1]=kj-ko
所以我们就可以求出
a[n]=2*k[n]-a[1]
最后依次将所有数推出即可

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

long long n, k[100005], a[100005];
long long kj, ko;

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>k[i];
        if(i%2==0) ko+=k[i];
        if(i%2==1) kj+=k[i];
    }
    a[1]=kj-ko;
    a[n]=2*k[n]-a[1];
    for(int i=n-1; i>1; i--)
        a[i]=2*k[i]-a[i+1];
    for(int i=1; i<=n; i++)
        cout<<a[i]<<" ";
    return 0;
}

L&M 由于本蒟蒻图论不好，这两道题可以参照一下其他大佬的 （哭

标签：std,10,int,题解,namespace,训练赛,2023,using,include
From： https://www.cnblogs.com/GImagine/p/buctoj-2.html

相关文章

  • Namomo Winter Camp D3 Div2 简易题解
    题目提交链接ProblemK.KotlinIsland首先不用考虑描边（那样和不画这条边是一样的）。那么剩下的就是在长度和宽度内枚举了。显然可以知道长宽最多画\((n-1)/2\)和......
  • note_2023年1月9日22点46分
    D:\code_gitee\python_socket\agvServer.tsimport{createServer}from"net";constserver=createServer();server.listen(19204,"localhost");server.on("conn......
  • 十二省联考 2019 题解
    Day1B字符串问题朴素的想法是，建一张\(n_a+n_b\)个点的有向图\(G\)。对于一个支配关系\((x,y)\)，从\(x\)向\(y+n_a\)连边。此外，枚举\(1\lei\len_b\)，对于每个......
  • 1.9寒假集训-进阶训练赛（五）A-M题解
    前五题网上都有不写了需要注意的是第四题是给定密钥和密文要把它加密算是一个逆过程看了半天都没读懂样例 第六题应该也有但是我写一下因为学校oj这边空间给的是1......
  • 2023年的油价走势,Forexclub认为与这息息相关,你认为对吗?
    2023年初，Forexclub认为有几个因素决定今年油价的中短期走势。供求关系、全球货币政策、经济增长大幅放缓的预期和可能的衰退，以及中国疫情的战胜，都会对原油价格产生影响。今......
  • HDU-3949 XOR 题解报告
    题目地址题意：从一个序列中取任意个元素进行异或，求能异或出的所有数字中的第k小。分析：性质：一个线性基异或上另一个不同的线性基，并作为自己的新值，这并不改变整个线性......
  • 光速上手k8s(2023)(containerd)(未完待续)
    又过了好久没写了，主要是近来状况也无聊一、了解概念（参考）概念Kubernetes是一个可移植、可扩展的开源平台，用于管理容器化的工作负载和服务，可促进声明式配置和自动化。Ku......
  • C++ATM取存款机模拟程序[2023-01-09]
    C++ATM取存款机模拟程序[2023-01-09]ATM取存款机模拟程序要求：设计一个程序，当输入给定的卡号和密码(初始卡号和密码为123456)时，系统能登录ATM取款机系统，用户可以按照以下......
  • 2023.1.9周报
    本周总结：《算法竞赛》5.3、5.4，《算法竞赛进阶指南》0x56、0x5C、靠队友录屏白嫖了namomocamp的内容。大方向：动态规划小专题：数位DP、状压DP题目完成情况：div2、abc各......
  • 【CF802O】April Fools' Problem (hard) 题解 （线段树模拟费用流）
    线段树模拟费用流。LG传送门。SolutionPart1根据题面，显然想到此题是费用流。建图方式亦是显然：\(S\rightarrowi\)，流量为\(1\)，费用为\(a_i\)；\(i\rightarrowT_0\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99