2024-05-20周赛总结笔记

T1 LG1063 [NOIP2006 提高组] 能量项链 NOIP提高2006

题目传送门：洛谷P1063

考点：动态规划，DP ，递归 ，枚举 ，区间DP

难点：如何计算项链

易错点：若分成很多个项链，容易TLE

模版。

状态：AC

By Minecraft-Sep。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h> 
#define sep int
using namespace std;
sep dp[1001][1001],s[10000001],n,maxa=-1e9;//dp[i][j]表示区间[i,j]的最大能量
sep main(){
	cin>>n;
	for(sep i=1;i<=n;i++){
		cin>>s[i];
		s[n+i]=s[i];//复制一遍数组 
	}
	memset(dp,0,sizeof(dp));//初始化 
	for(sep i=n*2-1;i>=1;i--){
		for(sep j=i+1;j<=n*2-1;j++){
			for(sep k=i;k<=j-1&&j-i<n;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+s[i]*s[k+1]*s[j+1]);//环形区间DP模板 
			maxa=max(maxa,dp[i][j]);//边走边找最大值 
		}
	}
	cout<<maxa;
	return 0;
}

T2 LG1328[NOIP2014 提高组] 生活大爆炸版石头剪刀布 NOIP提高2014

题目传送门：洛谷P328

考点：模拟

难点：无

易错点：表格的存取和调用，复制数组

用char数组存储每一个手势的输与赢，每次调用，分数加减。

状态：AC

By Minecraft-Sep。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h> 
using namespace std;
int num,a1,a2,a[100001],b[100001],tes,as,bs;
char sep[6][6]={
{'p','s','y','y','s'},
{'y','p','s','y','s'},
{'s','y','p','s','y'},
{'s','s','y','p','y'},
{'y','y','s','s','p'}
};
int main(){
	cin>>num>>a1>>a2;
	for(int i=1;i<=a1;i++){
		cin>>a[i];
	}
	for(int i=1;i<=a2;i++){
		cin>>b[i];
	}
	tes=a[1];
	for(int i=a1+1;i<=201;i++){
		tes=a[i-a1+1];
		if(i%a1+1) a[i]=a[1];
		a[i]=a[i-a1];
	}
	tes=b[1];
	for(int i=a2+1;i<=201;i++){
		tes=b[i-a2+1];
		if(i%a2+1) b[i]=b[1];
		b[i]=b[i-a2];
	}	
	for(int i=1;i<=num;i++){
			if(sep[a[i]][b[i]]=='p'){
				as+=0;
				bs+=0;
			}
			if(sep[a[i]][b[i]]=='y'){
				as+=1;
				bs+=0;
			}	
			if(sep[a[i]][b[i]]=='s'){
				as+=0;
				bs+=1;
			}	
				
	}
	cout<<as<<" "<<bs;
}

T3 P8550 冬之花 洛谷原创，洛谷月赛

题目传送门：洛谷P8850

考点：数学

难点：如何计算

易错点：倍数关系，abs

模拟201次操作。

状态：WA

原因：不知道如何进行10^100次操作

By liuxiwen。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int k,t[10],n,x;
int main(){
    cin>>k;
    while(k--){
    	string ans="No";
    	cin>>n>>x;
    	for(int i=1;i<=n;i++){
    		cin>>t[i];
		}
		for(int i=1;i<=n;i++){
    		if(t[i]>0&&x>0||t[i]<0&&x<0){
    			ans="Yes";
    			break;
			}
			if(abs(x)%abs(t[i])!=0){
				ans="Yes";
				break; 
			}
		}
		cout<<ans<<endl;
	} 
    return 0;
}

By Minecraft-Sep。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int zu,n,x,a[100000],flag;
int main(char **argc)
{
	cin>>zu;
	while(zu--)
	{
		cin>>n>>x;
		flag=0;//初始化 
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			if(((a[i]>0&&x>0)/*当前的数大于0且x也大于零*/||(a[i]<0&&x<0)/*当前的数小于0且x也小于零*/)||abs(x)%(int)abs(a[i])/*所有的数的绝对值都是整形*/) flag=1;//标记 
		}
		if(flag) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return false;
}

T4 LG1006 [NOIP2008 提高组] 传纸条 NOIP提高2008

题目传送门：洛谷P1006

考点：动态规划，DP ，费用流

难点：状态转移方程

易错点：容易混淆成DFS的题目

DFS和BFS

状态：WA

原因：用错方式。

By Minecraft-Sep。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
long long  dp[110][100][100],f[1001][1001],m,n;
int main(){
	cin>>m>>n;
	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++){
			cin>>f[i][j];
		}
				
	dp[3][1][2]=f[1][2]+f[2][1];
	dp[3][2][1]=f[2][1]+f[1][2];
	
	for(int i=3;i<=m+n;i++)
		for(int j=1;j<i;j++)
			for(int k=1;k<i;k++){
				if(j!=k){
					if(j-k==1)
						dp[i][j][k]=max(max(dp[i-1][j-1][k-1],dp[i-1][j][k-1]),dp[i-1][j][k])+f[i-j][j]+f[i-k][k];
					else if(k-j==1)
						dp[i][j][k]=max(dp[i-1][j-1][k-1],max(dp[i-1][j][k],dp[i-1][j-1][k]))+f[i-j][j]+f[i-k][k];
					else
						dp[i][j][k]=max(max(dp[i-1][j-1][k-1],dp[i-1][j][k-1]),max(dp[i-1][j][k],dp[i-1][j-1][k]))+f[i-j][j]+f[i-k][k];
				}
			}
			cout<<max(dp[m+n-1][n-1][n],dp[m+n-1][n][n-1]);
	
	return 0;
}

总结

下次继续努力！

版权所有©Minecraft-Sep。