20241123课程记录|陈/张|数字三角形

admin

各位家长、同学，你们好，20241123学习内容如下： 【课堂内容】 1.辅助同学完成课上练习； 2.讨论数字三角形问题中的动态规划、深搜解法； 3.讨论数字三角形问题中路径的复现方法。 【学情分析】 本次课程主讲动态规划算法，从数字三角形问题出发，指导同学们完成了正反向的动态规划解法，并讨论深搜的处理方法，引导同学积极思考，学会从不同角度分析与解决问题。同学们课上表现良好，对常规算法掌握熟练，望课后常常复习，勤于思考，积极完成作业。 【课后作业】 完成作业网中20241122作业。 【参课学生】 陈鸿宇，张传瑞

ice_pick

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h> 
using namespace std;
int main()
{
        int n,sum=1;
        cin>>n;
        for(int i=1;i<=n;i++)
        sum=sum*2+1;
        cout<<sum;
        return 0;
}

ice_pick

ice_pick 发表于 2024-11-29 10:59
[mw_shl_code=cpp,true]#include
using namespace std;
int main()

P1309 [NOIP2011 普及组] 瑞士轮

admin

[C] 纯文本查看 复制代码

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

int N,R,Q,n;
struct player{
	int no;
	int score;
	int power;
}p[200001],win[100001],lost[100001];

bool cmp(player a,player b)
{
	if(a.score!=b.score)	
		return a.score>b.score;
	else 
		return a.no<b.no;
}

void way1()//方法1 sort 
{
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=R;i++){
		for(int j=1;j<=N;j++){
			if(p[2*j].power>p[2*j-1].power)
				p[2*j].score++;			
			else		
				p[2*j-1].score++;		
		}
		sort(p+1,p+n+1,cmp); 
	}
}

void way2()//方法2 归并 
{
	sort(p+1,p+n+1,cmp);
	int w=1,l=1,t=1;
	
	for(int i=1;i<=R;i++){
		for(int j=1;j<=N;j++){
			if(p[2*j].power>p[2*j-1].power){
				p[2*j].score++;
				win[j]=p[2*j];
				lost[j]=p[2*j-1];	
			}			
			else{
				p[2*j-1].score++;
				win[j]=p[2*j-1];
				lost[j]=p[2*j];	
			}						
		}
		
		w=1;
		l=1;
		t=1;
		 
		while(w<=N && l<=N)
		{
			if(cmp(win[w],lost[l]))
				p[t++]=win[w++];
			else
				p[t++]=lost[l++];		
		}
		
		while(w<=N) p[t++]=win[w++];
		while(l<=N) p[t++]=lost[l++];
	}
}

int main()
{
	cin>>N>>R>>Q;
	n=2*N;
	for(int i=1;i<=n;i++){
		cin>>p[i].score;
		p[i].no=i;
	}		
	for(int i=1;i<=n;i++)
		cin>>p[i].power;
	
		
	
	//way1();
	way2();
	cout<<p[Q].no;
	return 0;
}