发布时间:2024-02-16 16:30
ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客:面向阿尼亚学习
算法学习笔记系列持续更新中~
填空题都可以做,大多都是模拟题,考一些常见的基本知识。
编程题前几个都可以做
后几个编程题数据大的可以暴力拿数据小的部分分
做题一定要自信,相信自己可以做出了
其实国赛题也没有多难,大不了拿部分分嘛。
A,B,C,D为填空题
bps指的是bit per second(比特每秒)。
B的英文全称为Byte(字节)。
换算关系:1 Byte = 8 bits。
带宽除以8等于每秒网速
故:200Mbps = 200/8 = 25 MB/s。
#include
using namespace std;
int main()
{
cout<<200/8<<endl;
return 0;
}
答案:25
根据题意写个check函数判断模拟即可
#include
using namespace std;
bool check(int n)
{
int x=n;
while(x)
{
int y=x%10;
x=x/10;
if(y==0||y==1||y==4||y==6||y==8||y==9)
return false;
}
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
return false;
}
return true;
}
int main()
{
int ans=0;
for(int i=1;i<=20210605;i++)
{
if(check(i))
ans++;
}
cout<<ans<<endl;
return 0;
}
答案:1903
蓝桥杯爱考的日期问题
注意闰年的判断即可
四年一润,百年不润,四百年再润
闰年366天
#include
using namespace std;
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int x)
{
if(x==1||x==4||x==9||x==16||x==25||x==36||x==49||x==64)
return true;
return false;
}
int calc(int n)
{
int s=0;
while(n)
{
s+=n%10;
n=n/10;
}
return s;
}
int main()
{
int y=2001,m=1,d=1;
int ans=0;
while(y<=2021)
{
if(check(calc(y)+calc(m)+calc(d)))
ans++;
d++;
int x=a[m];
if(m==2&&(y%4==0&&(y%100!=0||y%400==0)))//判断是否为闰年
++x;//闰年二月日期加一
if(d>x)
d=1,m++;
if(m>12)
m=1,y++;
}
cout<<ans<<endl;
}
答案:977
DP问题
状态转移方程见题面
记得开longlong
#include
using namespace std;
long long f[2022];
int main()
{
memset(f,127,sizeof(f));
f[0]=0;
for(int i=1;i<=2021;i++)
{
for(int j=0;j<i;j++)
{
f[i]=min(f[i],1+2*f[j]+3*f[i-1-j]+j*j*(i-1-j));
}
}
cout<<f[2021]<<endl;
}
答案:2653631372
以下为编程题
大小写问题,
没手也行
#include
#include
using namespace std;
int main() {
string s;
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] <= 'z' && s[i] >= 'a') s[i] = s[i] - 'a' + 'A';
}
cout << s;
return 0;
}
也可以用c++库函数cctype
具体可见常用库函数整理
#include
#include
using namespace std;
int main()
{
string s;
cin>>s;
for(int i=0;i<s.length();i++)
{
if(islower(s[i]))
s[i]=toupper(s[i]);
}
cout<<s<<endl;
return 0;
}
分块前缀和+二分
#include
using namespace std;
typedef long long LL;
const int N = 1500000;
LL a[N], s[N];
int get(LL x) { // 二分
int l = 1, r = N;
while (l < r) {
int mid = (l + r) >> 1;
if (x <= a[mid]) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
for (int i = 1; i < N; i++) {
a[i] = i + a[i - 1];
s[i] = a[i] + s[i - 1];
}
int T;
cin>>T;
LL l, r;
while (T--) {
cin>>l>>r;
int pl = get(l);
int pr = get(r);
LL t = s[pr - 1] - s[pl - 1] + a[r - a[pr - 1]] - a[l - 1 - a[pl - 1]];
cout<<t<<endl;
}
return 0;
}
肯定有循环节
遇到这种规律题,直接找规律就行,熟练了就属于送分题,除非仍然需要优化
模拟就好
#include
using namespace std;
int n,a[10001],b[10001];
long long t;
char str[10011];
int main()
{
cin>>n>>t>>str;
//找循环节
int c=1;
while(c<n)
c=c*2;//周期结束
t%=c;
for(int i=1;i<=n;i++)
if(str[i-1]=='0')
a[i]=0;
else
a[i]=1;
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
b[j]=a[j-1]^a[j];
memcpy(a,b,sizeof(a));
}
for(int i=1;i<=n;i++)
if(a[i])
cout<<"1";
else
cout<<"0";
}
}
利用排列组合的方法进行求取,例如对于十进制数字22对应二进制数字10110,可以分别求取位于区间(10110,10100]、(10100,10000]、(10000,00000]这每个区间内满足要求的数字个数,再相加即可。
#include
using namespace std;
int m,a[71];
long long n,c[71][71];
int main()
{
c[0][0]=1;//求组合数
for(int i=1;i<=70;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)
{
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
}
cin>>n>>m;
++n;
int l=0;
for(;n;n/=2)
a[++l]=n%2;
for(int i=1,j=l;i<j;i++,j--)
swap(a[i],a[j]);
int tot=0;
long long ans=0;
for(int i=1;i<=l;i++)
if(a[i]==1)
ans+=c[l-i][m-tot],++tot;
cout<<ans<<endl;
return 0;
}
线段树
待补~
数位DP
暴力骗分(20%)
#include
using namespace std;
typedef long long LL;
bool check(int i,int j,int k) {
int a[3];
a[0]=i;
a[1]=j;
a[2]=k;
sort(a,a+3);
return a[0]+a[1]>a[2];
}
int main() {
int t,n;
cin>>t;
while(t--) {
cin>>n;
int ans=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
int k;
k=i^j;
if(k>=1&&k<=n&&check(i,j,k))
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
莫言真理无穷尽,寸进自有寸进欢