首页 > 其他分享 >济南 Day 6 数学

济南 Day 6 数学

时间:2023-07-29 19:11:05浏览次数:45  
标签:简要 洛谷 原题 int 代码 Day 数学 链接 济南

Solution

T1 回文数

原题链接

4093: 回文数

简要思路

  • 进位情况
    当所有数位都为 \(9\) 的时候才会进位,此时输出形如 1000001 的形式
  • 不进位情况
  1. 如果 \(n\) 的前一半翻过来比后一半更大就直接把 \(n\) 的前一半翻过来贴在 \(n\) 的后面。
  2. 否则就把 \(n\) 的前一半 \(+1\) 翻过来贴在 \(n\) 的后面。

注意处理好 \(n\) 的位数为 奇数/偶数 的情况

完整代码

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

char s[201],ans[201];
int i;

signed main(){
	cin>>s;
	int len=strlen(s)-1;
	
	while(s[i++]=='9')
		if(i==len+1){
			s[0]='1';
			len++;
			for(;i>0;i--)
				s[i]='0';
		}	
	
	for(i=0;i<=len-i;i++)
		ans[i]=ans[len-i]=ans[i];
	
	if(strcmp(ans,s)<=0){
		while(ans[--i]=='9');ans[i]=ans[len-i]=++ans[i];
		for(i++;i<=len-i;i++)
			ans[i]=ans[len-i]='0';
	}
	
	cout<<ans<<endl;
	return 0;
}

T2 求和

原题链接

4094: 求和

简要思路

枚举所有 “好数”,最后去重即可。

注意当考虑数位中含有 23512457898 的情况时,注意分讨:数位前面有几个多加的数,后面又有几个。

完整代码

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

ll power10[15], n, ans = 0;//power10[i] 代表 10^i
const ll QQ = 2351257898;
vector<ll> vec;
int main() {
	
	power10[0] = 1;
	for (int i = 1; i < 15; i++) {//预处理
		power10[i] = power10[i - 1] * 10;
	}
	
	cin >> n;
	for (int i = 1; i <= n / QQ; i++) {//先把倍数的情况加入 vector 中
		vec.push_back(QQ * i);
	}
	
	//考虑当数位中有 2351257898 时的情况
	for (int pos = 1; pos <= 5; pos++) {//第一层代表枚举数位前面有几个多加的数,后面有几个多加的数
		for (int rest = 0; rest <= 9999; rest++) {//第二层枚举代表多加的数是啥
			ll tmp = QQ * power10[pos - 1] + rest % power10[pos - 1] + rest / power10[pos - 1] * power10[pos + 9];//计算
			if (tmp <= n)
				vec.push_back(tmp);//如果合法才计入答案
		}
	}
	sort(vec.begin(), vec.end());//排序
	vec.erase(unique(vec.begin(), vec.end()), vec.end());//去重
	for (auto x: vec) {//枚举 vector 中的每一个数
		ans += x;
	}
	
	
	cout << ans << endl;
	
	return 0;
}

T3 计算

原题链接

4095: 计算

简要思路

前缀和 + 桶 + 差分。

完整代码

#include <bits/stdc++.h>
#define maxn 100010
#define ll long long
using namespace std;

int a[maxn], cnt[maxn], n, l, r;
ll ans[maxn], tag[maxn];
int main() {
	cin >> n >> l >> r;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		ans[0] += l / a[i];
	}
	
	for (int i = 1; i <= n; i++) {
		if (a[i] < maxn)
			cnt[a[i]]++;
	}
	for (int i = 1; i < maxn; i++) {
		/* pos = the minimum multiple of i that is greater than l */
		int pos = (l / i + 1) * i;
		while (pos <= r) {
			tag[pos - l] += cnt[i];
			pos += i;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] < maxn)
			continue;
		
		/* pos = the minimum multiple of a[i] that is greater than l */
		int pos = (l / a[i] + 1) * a[i];
		while (pos <= r) {
			tag[pos - l]++;
			pos += a[i];
		}
	}
	
	for (int i = 1; i <= r - l; i++) {
		ans[i] = ans[i - 1] + tag[i];
	}
	
	for (int i = 0; i <= r - l; i++) {
		cout << ans[i] << "\n "[i < r - l];
	}
	return 0;
}

T4 保 KDA

原题链接

4096: 保 KDA

简要思路

01 分数规划 + 背包

完整代码

咕咕。

讲课笔记

洛谷 P3908

原题链接

P3908 数列之异或

相关知识

位运算

位运算符号:&,|,^

  • &
    1&1=1 1&0=0 0&0=0 0&1=0

  • |
    1|1=1 1|0=1 0|1=1 0|0=0

  • ^
    二进制的不进位加法。
    1^1=0 1^0=1 0^1=1 0^0=0
    两个相同的数字异或答案为 \(0\):\(a^a=0\)

简要思路

一个偶数异或下一个奇数的答案为 \(1\):\((2k) ^ (2k+1) = 1\)

  1. 当 \(n\) 是奇数时
    如果 \((n-1)/2\) 为奇数,答案为 \(0\)。
    偶数答案则为 \(1\)。
  2. 当 \(n\)

image

完整代码

洛谷 P4942

原题链接

题面

相关知识

如果一个数的数位之和为 \(3\) 的倍数,那么这个数就是 \(3\) 的倍数。
如果一个数的个数位上为 \(0\) 或 \(5\),那么这个数就是 \(5\) 的倍数。
如果一个数的千位及其以前的数位组成的数减去后三位数,得到的答案的绝对值为 \(7\) 或 \(11\) 或 \(13\) 的倍数,那么这个数就是 \(7\) 或 \(11\) 或 \(13\) 的倍数。

简要思路

完整代码

洛谷 P6267

原题链接

题面

相关知识

分解质因数

简要思路

完整代码

洛谷 P1029

原题链接

题面

相关知识

最大公约数和最小公倍数

  • 辗转相除
  • 指数(分解质因子),min-max

简要思路

完整代码

洛谷 P1072

原题链接

题面

相关知识

简要思路

  • 模拟

  • PPT

完整代码

  • 模拟做法

  • (PPT) 做法

洛谷 P3197

原题链接

题面

相关知识

组合数

  • 例题 1
    共有 \(n\) 个相同的小球,放置于 \(m\) 个不同个盒子中,保证每个盒子都非空的方案数。

\(C^{m-1}_{n-1}\)

  • 例题 2
    如果不要求非空,一开始就将每个盒子的初始值为 \(1\),最后减去 \(m\) 个小球就为 \(C^{m-1}_{n+m-1}\)。

上述为 插板法。

  • 例题 3
    不同小球,不同盒子,可以为空。

每个小球都可以放置在任何盒子里,答案为 \(m^n\)。

简要思路

完整代码

进阶

一号房间和 \(n\) 号房间连接,成为了环。

洛谷 P3414

原题链接

题面

标签:简要,洛谷,原题,int,代码,Day,数学,链接,济南
From: https://www.cnblogs.com/CheZiHe929/p/17590308.html

相关文章

  • Day06-26 内部类
    内部类内部类就是在一个类的内部在定义一个类,比如,A类中定义一个B类,那么B类相对A类来说就称为内部类,而A类相对B类来说就是外部类了。1、成员内部类2、静态内部类3、局部内部类4、匿名内部类importcom.oop.demo10.Outer;​publicclassApplication{  publi......
  • 组合数学
    入门:先介绍三个简单的技术插板法:直接插板:看下面的问题:eg1:\(x+y+z=20\),其中\(x,y,z\)为正整数,求有多少组解。我们考虑有\(20\)个球排成一排。我们插入两个板子把这\(20\)个球分成\(3\)个部分,其中第一部分的球的个数是\(x\)的大小,第二部分是\(y\),第三部分是\(z\)。这两个板......
  • day3c++学习
    1内存分区模型C++程序在执行时,将内存大方向划分为4个区域代码区:存放函数体的二进制代码,由操作系统进行管理的全局区:存放全局变量和静态变量以及常量栈区:由编译器自动分配释放,存放函数的参数值,局部变量等堆区:由程序员分配和释放,若程序员不释放,程序结束时由操作系统回收......
  • Qt-day01
    //不用手动进行回收?://条件一:在QT中建立了内存回收机制从QBject派生的类,//条件二:指定父类,父类对象析构的时候,先析构子类对象 #include"mywidget.h"#include<QApplication>intmain(intargc,char*argv[]){//QApplication应用程序类每个程......
  • 7.29 day6数学
    如果没问题就是300T1线性筛里,每个数都会被他最小的质因数筛到,令\(f(x)=[x\%p==0]\quadp\indangerous\)这显然是个完全积性函数,线性筛即可时间复杂度:\(O(n)\)T2考虑这棵树实质上是一个以1为根,边权为大于父亲边权的质数,节点值则为到根路径上边权累乘那么我们要求x,y之间......
  • SCU预备役Day 1
    2023-07-2822:13:56 基本算法二分与三分使用范围:答案具有单调性时。原理:判断远比求解简单定义域:为整数域的时候,若区间长度为N,则需要进行log2N次运算为实域的时候,判断R-L精度是否达到要求,需要R-L>=eps(但因为实数运算带来的精度问题,若eps太小会导致是循环,往往指定二分次数......
  • Day2
    数组专题:leetcode:977暴力解法也是最开始就可以想到的方法:defsortedSquares(self,nums):""":typenums:List[int]:rtype:List[int]"""foriinrange(len(nums)):nums[i]*=nums[i]......
  • day16
    一.白哥的鸽子1.得到一张jpg,binwalk显示格式有问题,010打开,在末尾发现类似flag的数据2.是栅栏密码,字数为3时,得到flag二.split_all1.得到一张无法显示的png,删去png的头,补上gif文件头2.现象出来的图像很窄,与之前的一个题很像,扔进Stegsolve中,看不到,查看framebrowser,发现有770......
  • [代码随想录]Day03-链表part01
    题目:203.移除链表元素思路:做链表首先最好有个虚拟头指针,这样做删除添加操作的时候可以统一操作否则还得特判。那删除元素的过程,从虚拟头指针开始要做以下几步:如果当前p的next不为空,那么就可以进行判断如果p的next的值是val(↑p的next不为空↑),那么就把p的next修改为p的下......
  • 济南 Day 5 图论
    SolutionT1emoairx的二叉树原题链接4114:emoairx的二叉树简要思路一道简单的递归签到题,每次找到较大的数进行除以\(2\),每次递归把步数加一,直到两个点走到同一个点上。完整代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intm;intans(intx......