周报一（蒟蒻逆袭计划）
  • 板块学术版
  • 楼主Attackpointer
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/11/9 22:08
  • 上次更新2024/11/9 22:10:56
查看原帖
周报一（蒟蒻逆袭计划）
1431915
Attackpointer楼主2024/11/9 22:08

周报一

第一节

多组数据输入

(1) 输入就读取

#include <iostream>
using namespace std;

int main(){
	int a,b;  
  
	//while(scanf("%d%d",&a,&b)!=EOF)  
	while(scanf("%d%d",&a,&b)==2)  
	printf("%d\n",a+b);  
  
	//while(cin>>a>>b) C++写法
	return 0;
}
注意事项：  
//scanf()的返回值是成功读取的变量个数,如果没读取，返回值为-1  
//EOF为预定义常量，等于-1

（2) 输入固定值后结束

while(scanf("%d%d",&a,&b)==2){  
	if(a==0&&b==0) break; //读取两个0就结束  
	printf("%d\n",a+b);  
}

(3) 字符和字符串的输入

//cin>>输入一个字符  
char a,b;  
cin>>a>>b;  
cout<<a<<" "<<b<<endl;

//cin>>接收一个字符数组，遇到“空格”、“Tab”、“回车”就结束  
char c[5];  
cin>>c;  
cout<<c<<endl;

scanf("\n"); 	//cin与cin.getline同时使用时，需要加上  
//cin.getline(接收字符串的变量,接收字符个数,结束字符)  
//接收一个字符数组，可以接收空格并输出  
char m[20];  
cin.getline(m,5); //当第三个参数省略时，系统默认为'\0'd  
cout<<m<<endl;

//接收一个字符串，可以接收空格并输出，需包含“#include<string>”  
string str;  
//当同时使用cin>>,getline()时，需要注意的是，  
//在cin>>输入流完成之后，getline()之前，需要通过的方式将回车符作为输入流cin以清除缓存  
str="\n";  
getline(cin,str);  
cout<<str<<endl;

补充 ==约数个数定理：==

对于一个大于1正整数n可以分解质因数：

n=∏i=1kpiai=p1a1.p2a2...pkakn=\prod_{i=1}^k p_i^{a_i}=p_1^{a_1}.p_2^{a_2}...p_k^{a_k}

则n的正约数的个数就是

f(n)=∏i=1k(ai+1)=(a1+1)(a2+2)...(ak+k)。f(n)=\prod_{i=1}^k (a_i+1)=(a_1+1)(a_2+2)...(a_k+k)。

第二节

数学基础

1、最大公约数和最小公倍数

int gcd(int a,int b){  //欧几里得算法（辗转相除法）
	if(a==0) return b;  
	return gcd(b%a,a);
}
lcm(a,b)=a/gcd(a,b)*b;	//两数之积除以最大公约数

2、取余%的结合律

如果a=b+c，那么amod  d=(b+c)mod  d=bmod  d+cmod  d。(d≠0)如果a=b+c，那么a\mod d=(b+c)\mod d=b\mod d+c\mod d。 (d\ne0)

3、快速幂运算（二分加速）

求a的b次方的后三位数:

//快速幂运算（二分加速）[递归]  
ll power1(ll a,ll n){  
ll ans;  
if(n==0) ans=1; //a的0次方为1  
else{  
ans=power1(a*a,n/2); //递归调用  
ans%=1000;  
if(n%2) ans*=a; //n为奇数，做一次运算，变回偶数  
}  
return ans;  
}

//快速幂运算（二分加速）[循环]  
ll power2(ll a,ll n){  
ll ans=1;  
while(n){  
if(n%2) ans*=a; //奇数情况  
ans%=1000;  
a*=a; //底数平方  
n/=2; //指数减半  
}  
return ans;  
}

==注意事项==： 1.注意爆int(尽量用long long)
2.快速幂运算几乎都伴随模运算

4、二分查找

在有序的数组a[]（单调）中查找元素x:[o(logN)]

int BiSearch(int a[],int n,int x){
	int left=0,right=n-1;
	while(left<=right){				//注意=不能少
	int middle=(left+right)/2;		//整数除法
	if(a[middle]==x)				//找到的情况
		return middle;
	if(x>a[middle])					//如果比中值大
		left=middle+l;
	else							//如果比中值小
		right=middle-1;
	}
return -1;	//说明未找到该数
}

int BiSearch(int a[],int x,int left,int right){
	if(left>right)	//注意不能有=号
		return -1;	//递归出口
	else{
		int mid=(left+right)/2;
		if(a[mid]==x)
			return mid;
		else if(x>a[mid])
			return BiSearch(a,x,mid+l,right);
		else if(x<a[mid])
			return BiSearch(a,x,left,mid-1);
}

5、异或

5.1 符号 异或是一种二进制的位运算，符号以 XOR 或 ^ 表示。 5.2 运算规则 相同为0，不同为1。 由运算规则可知，任何二进制数与零异或，都会等于其本身，即 A ^ 0 = A。 5.3 性质 1）交换律：A ^ B = B ^ A 2）结合律：( A ^ B ) ^ C = A ^ ( B ^ C ) 3）自反性：A ^ B ^ B = A（由结合律可推：A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A） 5.4 应用 1）变量交换

int a=3,b=7;
// 常规方法
int temp=a;  // temp = 3
a=b;         // a = 7
b=temp;      // b = 3
 
// 异或方法
a=a^b;  
//a=3^7
b=a^b;  
//b=(3^7)^7=3^(7^7)=3
a=a^b;  
//a=(3^7)^(3^7^7)=(3^3)^(7^7)^7=7
  1. 排除偶次重复 示例：在一个整数数组中，仅存在一个不重复的数字，其余数字均出现两次（或偶数次），找出不重复数字。
// 常规方法：通过二次循环找出不重复的数字
for(...){
    for(...){
        ...
    }
}
 
// 异或方法：将所有整数异或，出现偶数次的整数会被抵消，最终留下不重复整数。
int ans=0;
for(int i=0;i<sizeof(a)/sizeof(a[0]);i++){
    ans=ans^a[i];
}
return ans;

6、移位运算

定义：在数的二进制形式的基础上进行位移 1、左移运算： 如：26<<2 00011010(26)--01101000(104)【将数整体向左移一位，再在后面补上0，移出去的数舍弃】本质：m<<n=m∗2n本质：m << n = m * 2^n(m可为正数也可为负数) 2、右移运算（有符号）： 正数右移，左侧补0；负数右移，左侧补1。 如：13>>1 00001101(13)--00000110(6)【】

补充：三分查找（数据的凸性） 适用于==凸函数==求极值点(以*==上凸函数==*为例) 但不要求可导，可以是分段函数

double ThirdSearch(double Left,double Right){
		double LeftThird=(Left*2+Right)/3;
		double RightThird=(Left+Right*2)/3;
		if(f(LeftThird)>f(RightThird))	
			return ThirdSearch(LeftThird,Right);
		else 
			return ThirdSearch(Left,RightThird);
		//结束条件：满足一定精度
}

第三节

贪心算法

1、导引：硕鼠的交易

题目描述 胖老鼠准备了M磅的猫粮，准备和看守仓库的猫交易，仓库里有他最喜欢的食物，爪哇豆。 这个仓库有n个房间，第i个房间含有J[i]千克的爪哇豆，交换这些爪哇豆需要F[i]千克的猫食。在交换过程中胖老鼠不必交易房间里的所有爪哇豆，可以部分交换，即如果付给F[i]*a%千克的猫粮，他可能会得到J[i]*a%千克的爪哇豆。 现在胖老鼠把这项作业分配给你：告诉他能得到的最大数量的爪哇豆。 输入格式 每个测试用例以包含两个非负整数M和N的行开始。M表示胖老鼠拥有的猫粮数，N表示房间房间数。后面N行，每个行分别包含两个非负整数J[i]和F[i]所有的整数都不大于1000。 输出格式 对于每个测试用例，在一行中打印一个实数，最多精确到小数点后3位，这是胖老鼠可以获得的爪哇豆的最大数量。

#include <bits/stdc++.h>  
using namespace std;  
  
struct Mouse{  
	int bean; 			//可换取的豆  
	int ml; 			//消耗的猫粮  
	float cost;			//性价比  
};  
  
bool cmp(Mouse a,Mouse b){  
	return a.cost>b.cost;  
}  
  
int main(){  
	int total,num; 		//total猫粮,num房间数  
	float ans; 			//获得的豆  
	while(1){  
		cin>>total>>num;  
		if(total==-1&&num==-1) break;  
		Mouse m[num];  
		for(int i=0;i<num;i++){  
			cin>>m[i].bean>>m[i].ml;  
			m[i].cost=1.0*m[i].bean/m[i].ml;  
		}  
		sort(m,m+num,cmp); 			//按性价比从大到小排序  
		for(int i=0;i<num;i++){  
			if(total>=m[i].ml){ 	//total足够,全部换  
			ans+=m[i].bean;  
			total-=m[i].ml;  
		}  
		else ans+=total*m[i].cost;	//total不足,部分换  
	}  
}  
	printf("%.3f",ans);  
	return 0;  
}

==注意事项==： 在对问题求解时，总是作出在当前看来是最好的选择 也就是说，不从整体上加以考虑，所作出的仅仅是在某 种意义上的局部最优解（是否是全局最优，需要证明)。

2、田忌赛马

int n;  //田忌和国王拥有的赛马数
while(cin>>n&&n!=0){  
	int sum=0; //记录田忌最多能够赢得的金额  
	int a[n],b[n];  

	for(int i=0;i<n;i++) //田忌  
		cin>>a[i];  
	sort(a,a+n);  //从小到大排序
	for(int i=0;i<n;i++) //国王  
		cin>>b[i];  
	sort(b,b+n);  
  
	int count_a=0,count_b=0;  
	while(1){  
		if(a[count_a]>b[count_b]){ 
		//对于未进行比赛且最慢的一匹的赛马，
		//如果田忌的比国王的快，就正常赢一局
			sum+=200;  
			count_a++;  
			count_b++;  
		}  
		else {  
		//对于未进行比赛且最慢的一匹的赛马，
		//如果田忌的比国王的慢，就用这一批和国王最快的马去比
			sum-=200;  
			count_a++;  
		}  
		if(count_a==n) break;  //都比完，就结束
	}  
	cout<<sum;  
}

3、事件序列问题

已知N个事件的发生时刻和结束时刻。一些在时间上没
有重叠的事件，可以构成一个事件序列。事件序列包含的事件数目，称为该事件
序列的长度。请编程找出一个最长的事件序列。

struct Time{  
	int be; 	//发生时刻  
	int en; 	//结束时刻  
};  
  
bool cmp(Time t1,Time t2){  
	return t1.en<t2.en;  //从小到大排序
}  
  
Time t[n];  
for(int i=0;i<n;i++)  
	cin>>t[i].be>>t[i].en;  
  
sort(t,t+n,cmp);		//按结束时刻，结构体从小到大排序  
  
int End=t[0].en; 		//记录事件序列的结束时刻  
int count=1; 			//计数  
for(int i=1;i<n;i++){  
	if(t[i].be>End){  
		count++;  
		End=t[i].en;   	//更新事件序列的结束时刻
	}   
}  
cout<<count;
2024/11/9 22:08