CSP-J入门组

简介: CSP-J入门组

CSP-J入门组

简单排序:


图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他需要的书,请输出-1。

image.png

#include<stdio.h>#include<stdlib.h>intcmp(constvoid*a, constvoid*b){
return (*(int*)a-*(int*)b);
}
intmod(intx){
inti, sum=1;
for(i=1; i<=x; i++)
    {
sum*=10;
    }
returnsum;
}
intmain()
{
intn, q, len[1002];
scanf("%d%d", &n, &q);
inti, j, num[1002], q1[1002];
for(i=1; i<=n; i++)
scanf("%d", &num[i]);
for(i=1; i<=q; i++)
scanf("%d%d", &len[i], &q1[i]);
qsort(num, n+1, sizeof(int), cmp);
for(i=1; i<=q; i++)
    {
for(j=1; j<=n; j++)
  {
if(num[j]%mod(len[i])==q1[i])
    {
printf("%d\n", num[j]);
break;
    }
elseif(j==n)
printf("-1\n");
  }
    }
return0;
}


字符串


给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零(参见样例2)。

image.png

#include<iostream>usingnamespacestd;
intmain()
{
intn,a,b=0;
cin>>n;
while(n!=0)
    {
a=n%10;
n=n/10;
b=b*10+a;
    }
cout<<b<<endl;
return0;
}


二分:二分法是指对于区间[a,b]上连续不断且f(a)·f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法。


有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值 ≥ 1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。

提示:记方程f(x) = 0,若存在2个数x1和x2,且x1 < x2,f(x1)*f(x2) < 0,则在(x1,x2)之间一定有一个根。

image.png

#include<bits/stdc++.h>usingnamespacestd;
doublea,b,c,d,l,r,mid;
doubles(doubles)
{
returna*pow(s,3)+b*pow(s,2)+c*pow(s,1)+d;
}
intmain()
{
cin>>a>>b>>c>>d;
for(inti=-100;i<=100;i++)
    {
l=i,r=i+1;
if(s(l)==0) cout<<fixed<<setprecision(2)<<l<<" ";
elseif(s(l)*s(r)<0)
        {
while(r-l>=1e-5)
            {
mid=(r+l)/2;
if(s(r)*s(mid)<0) l=mid;
elser=mid;
            }
cout<<fixed<<setprecision(2)<<l<<" ";
        }
    }
return0;
}


高精度:高精度运算,是指参与运算的数(加数,减数,因子……)范围大大超出了标准数据类型(整型,实型)能表示的范围的运算。


给出一个整数 n(n<1030) 和 k 个变换规则(k<=15)。

规则:

一位数可变换成另一个一位数:规则的右部不能为零。

例如:n=234。有规则(k=2):

2-> 5

3-> 6

上面的整数 234 经过变换后可能产生出的整数为(包括原数):

234

534

264

564

共 4 种不同的产生数

问题:

给出一个整数 n 和 k 个规则。

求出:

经过任意次的变换(0次或多次),能产生出多少个不同整数。仅要求输出个数。

image.png

#include<iostream>usingnamespacestd;
strings;
intn,f[10][10],a[100010],c[100010];
voidwork()
{
cin>>s>>n;
for(inti=1;i<=n;i++)
    {
intx,y;
cin>>x>>y;
f[x][y]=1;
    }
for(intk=0;k<=9;k++)
for(inti=0;i<=9;i++)
for(intj=0;j<=9;j++)
if(i!=j&&i!=k&&j!=k&&f[i][k]&&f[k][j]) f[i][j]=1;
for(inti=0;i<=9;i++)
for(intj=0;j<=9;j++)
if(f[i][j]) a[i]++;
intd=1;
c[1]=1;
for(intj=0;j<s.size();j++)
    {
intx=0;
inte=s[j]-'0';
e=a[e]+1;
for(inti=1;i<=d;i++)
        {
c[i]=c[i]*e+x;
x=c[i]/10;
c[i]%=10;
        }
if(x>0) c[++d]=x;
    }
for(inti=d;i>=1;i--)
cout<<c[i];
cout<<"\n";
}
intmain()
{
work();
return0;
}


排列组合数学:

妞妞参加了Nowcoder Girl女生编程挑战赛, 但是很遗憾, 她没能得到她最喜欢的黑天鹅水晶项链。


于是妞妞决定自己来制作一条美丽的项链。一条美丽的项链需要满足以下条件:

1、需要使用n种特定的水晶宝珠

2、第i种水晶宝珠的数量不能少于li颗, 也不能多于ri颗

3、一条美丽的项链由m颗宝珠组成

妞妞意识到满足条件的项链种数可能会很多, 所以希望你来帮助她计算一共有多少种制作美丽的项链的方案。

image.png

#include<cstdio>// #include <algorithm>// using namespace std;#definemax(a, b) ((a) > (b) ? (a) : (b))
#definelllonglongconstintM=1e5+10;
intarr[M];
lldp[25][105];
boolvis[25][105];
structnumber{
intl, r;
}req[25];
llDP(intn, intw) {
if (w<0) return0;
if (n==0&& (w>req[0].r||w<req[0].l)) return0;
if (n==0) return1;
if (vis[n][w]) returndp[n][w];
vis[n][w] =true;
ll&ret=dp[n][w];
for (inti=req[n].l; i<=req[n].r; ++i) {
ret+=DP(n-1, w-i);
    }
returnret;
}
intmain() {
intn, m;
scanf("%d %d\n", &n, &m);
for (inti=0; i<n; ++i) {
intl, r;
scanf("%d %d", &l, &r);
req[i] = {.l=l, .r=r};
    }
printf("%lld", DP(n-1, m));
return0;
}


递归排序:

哈希:散列函数(又称散列算法、哈希函数)能够从某一类数据中提取出一个有限长度的数字指纹作为数据的代表,这个”指纹“被称为散列值(哈希值)。散列函数产生的结果通常会比原数据小,从而实现数据的压缩;同时通过散列函数的计算过程是不可逆的,即无法根据散列值反推出原始数据,所以散列函数被广泛用于需要生成数据摘要或实现数据加密的应用场景中。[1]对于散列函数的选择,通常需要结合散列结果的冲突率、散列函数计算的代价来综合考虑。


基本递推


动态规划


贪心:贪婪算法是一种算法范例,它遵循在每个阶段做出局部最优选择[1] 的启发式求解方法,目的是寻找到一个全局最优解。在许多问题中,贪婪策略通常不会产生最优解,但是贪婪启发式可能会在合理的时间内产生近似全局最优解的局部最优解。


树形结构


枚举和暴力:在数学和计算机科学理论中,一个集的枚举是列出某些有穷序列集的所有成员的程序,或者是一种特定类型对象的计数。

暴力:利用枚举所有的情况,或者其它大量运算又不用技巧的方式,来求解问题的方法。广义的暴力法在解决问题,特别是数学和计算机编程问题方面应用广泛,有着巨大的作用。它的缺点是效率低下,优点是编码复杂度低,几乎不用思考,不容易出错。狭义的暴力法:这是一种简单的串匹配算法,用来判断一个短串t是不是一个长串s的子串。


01背包


区间dp


完全背包


多重背包


目录
相关文章
|
Java API Maven
全网首发:Spring Cloud Gateway设置统一的请求前缀
全网首发:Spring Cloud Gateway设置统一的请求前缀
1379 0
全网首发:Spring Cloud Gateway设置统一的请求前缀
|
7月前
|
安全 Java 数据库
后端进阶之路——浅谈Spring Security用户、角色、权限和访问规则(三)
后端进阶之路——浅谈Spring Security用户、角色、权限和访问规则(三)
|
6月前
|
缓存 安全 Java
【权限管理系统】Spring security(三)---认证过程(原理解析,demo)
【权限管理系统】Spring security(三)---认证过程(原理解析,demo)
|
7月前
|
移动开发 前端开发 数据库
ruoyi-nbcio 基于flowable规则的多重并发网关的任意跳转
ruoyi-nbcio 基于flowable规则的多重并发网关的任意跳转
141 0
|
安全 Java 数据库
深入Spring Security魔幻山谷-获取认证机制核心原理讲解(新版)
在神秘的Web系统世界里,有一座名为Spring Security的山谷,它高耸入云,蔓延千里,鸟飞不过,兽攀不了。这座山谷只有一条逼仄的道路可通。然而,若要通过这条道路前往另一头的世界,就必须先拿到一块名为token的令牌,只有这样,道路上戍守关口的士兵才会放行。
53 0
|
存储 设计模式 缓存
Spring Security 工作原理概览(一)
Spring Security 工作原理概览(一)
|
存储 JSON 安全
Spring Security 工作原理概览(二)
Spring Security 工作原理概览(二)
SpringCloud学习(十七):Gateway网关的自定义全局GlobalFilter
虽然官方为Gateway提供了很多filter,但其实并不使用,我们更多的还是使用自己的配置。 在9527网关模块中新建一个filter包,在里面写一个类来实现自定义filter
233 0
SpringCloud学习(十七):Gateway网关的自定义全局GlobalFilter
|
安全 前端开发 网络协议
Spring Security系列教程18--会话管理之防御固定会话攻击
前言 在前面几个章节中,一一哥 带各位学习了如何实现基于数据库进行认证授权,如何给登录界面添加图形验证码,如何进行自动登录和注销登录,那么Spring Security的功能难道只有这些吗?肯定不是的,它的宝藏还有很多,我们还需要继续往下学习研究。 今天 壹哥 就带各位学习另一个很重要的功能,就是会话管理! 你可能会问:会话管理?干嘛的?有哪些效果? 想一下: 我们的项目上线后,如果黑客对我们的项目进行会话固定攻击怎么办? 如果用户登录后,长时间不进行任何操作,要不要让用户重新登录? 如果你的登录账号,在多台设备上同时登录该怎么实现和处理? ...... 这些问题会话管理都可以替我们解决
320 0
|
XML 缓存 安全
第二十六章 使用 CSP 进行基于标签的开发
第二十六章 使用 CSP 进行基于标签的开发
88 0

热门文章

最新文章