首页 > 其他分享 >10.23解题报告

10.23解题报告

时间:2022-10-24 23:11:08浏览次数:71  
标签:10 10.23 报告 int long 解题 freopen dp define

T1

用时:\(20\) min

要求统计数组 \(a\) 中有序三元组 \((x,y,z)\) 的个数,满足 \(\gcd(a_x,a_y)=a_z\),直接枚举 \(x\),\(y\),将 \(x\) 后面的加入一个 map 中,统计答案即可。

#include<bits/stdc++.h>
#define ll long long
//#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
//#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
map<int,int> mp;
int a[3010];
signed main(){
//	freopen("1.in","r",stdin);
//	freopen("mobius.in","r",stdin);
//	freopen("mobius.out","w",stdout);
	int n=read();
	for(register int i=1;i<=n;i++) a[i]=read();
	ll sum=0;
	for(register int i=1;i<=n;i++){
		mp.clear();
		for(register int j=i+1;j<=n;j++) mp[a[j]]++;
		for(register int j=i+1;j<=n;j++){
			mp[a[j]]--;
			sum+=(mp[__gcd(a[i],a[j])]);
		}
	}
	cout<<sum;
	return 0;
}
/*

5
6 4 9 2 3

*/

T2

用时:\(20\) min

一个比较板的二分套 dp,当 \(k\) 能够满足时,\(k+1\) 一定也能够满足,所以具有单调性,考虑二分,check时一个dp统计最长合法子序列长度是否 \(\ge m\) 即可。

#include<bits/stdc++.h>
#define ll long long
//#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*
显然若k满足,k+1一定满足,考虑二分这个k
dp[i]表示以i结尾,符合条件的最长长度
dp[i]=max(dp[j])+1 1<=j<i |a[j]-a[i]|<=k
期望100pts 
*/
int n,m,a[1010],dp[1010];
bool check(int k){
	int ret=1;
	for(int i=1;i<=n;i++){
		dp[i]=1;
		for(int j=1;j<i;j++)
			if(abs(a[j]-a[i])<=k)
				dp[i]=max(dp[i],dp[j]+1);
		ret=max(ret,dp[i]);
	}
	return ret>=m;
}
signed main(){
//	freopen("cauchy.in","r",stdin);
//	freopen("cauchy.out","w",stdout);
	int l=1,r=2e9,ans=0;
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}

T3

用时:\(1.5\) h

发现由于题目的限制,必须要在一棵子树全部处理完成之后再去处理别的子树,所以这可以 dp。

这题用的时间比较久,在考场上想到一点思路,当时也考虑到了应该贪心的按 dp 值或者是剩余石子数来排序,但是没想打其实是按照 \(dp-w\) 来排序,然后 dp,由于细节太多,打了一个暴力就跑路了。

但实际上真正理解之后写起来并不难写。

标签:10,10.23,报告,int,long,解题,freopen,dp,define
From: https://www.cnblogs.com/wapmhac/p/16823401.html

相关文章

  • 10.24解题报告
    T1用时:约\(100\)min这个题用的时间最多,主要原因还是想多了,应该注意多观察一下题目性质:题目要求求出这个式子的正整数解个数:\(\frac{a}{x}+\frac{b}{c}=\frac{d}{y}\)......
  • cv学习总结(10.16-10.23) KNN
    本周从周一开始学习cs231n的相关内容,看完了231n的课程介绍,背景介绍,图像分类的KNN和SVM算法,完成了作业中assignment1的KNN部分的代码(附件),思考总结了KNN的实现原理:即将原......
  • 上周热点回顾(10.17-10.23)
    热点随笔:· 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 (葡萄城技术团队)· 提高工作效率的神器:基于前端表格实现ChromeExcel扩展插件 (葡萄城技术团队)......
  • 10.23回顾
    本周内容回顾异常捕获生成器相关内容概述模块简介常用内置模块本周测评作业解析异常捕获1.异常捕获的语法异常捕获一般是使用Trytry:待检测的子代码excep......
  • [2022.10.23]String的不可变性
    final关键字代表最终、不可改变的常见四种用法:1.可以用来修饰一个类(不能有任何子类)2.可以用来修饰一个方法(最终方法,不能被覆盖重写)3.还可以用来修饰一个局部变量(对......
  • 2022.10.23每日一题
    任务分配题目描述你有\(n\)个任务,其中第\(i\)个任务,在\(s_i\)开始,\(e_i\)时刻结束,如果做这个任务,你能获得\(w_i\)的收益。但是你在一个时刻只能做一个任务,问选......
  • 【闲话】2022.10.23
    今天没有考试于是赫了些DP题每日一(?)图密码是咱最喜欢的番二度提示:我们一日日……记得第一个字母大写怎么登不上SPOJ啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊今......
  • 闲话 22.10.23
    闲话打”细节”,然后输入了“xj”,第一候选字是“星界”aaaa我想听情绪的歌了aaaa奇怪的戒断反应增加了smtwy:我手机里有一万多张二次元图我:您是在什么精神状态下做出这......
  • Python实验报告(第7周)
    实验7:面向对象程序设计一、实验目的和要求1、了解面向对象的基本概念(对象、类、构造方法);2、学会类的定义和使用;3、掌握属性的创建和修改;4、掌握继承的基本语法。 ......
  • 10.23学习总结
    10.23学习总结目录10.23学习总结一、常见内置函数二、可迭代对象三、迭代器对象四、生成器对象五、for循环的本质六、异常捕获七、异常捕获语法八、迭代取值与索引取值的......