首页 > 其他分享 >week 14

week 14

时间：2023-10-16 18:15:30浏览次数：47  
标签：week 14 int cin ans using include dp

Week 14

目录

Div2 每日一题

202 路径计数（dp)

  • dp，熟悉的dp入门！！

    #include<bits/stdc++.h>
using namespace std;
const int N=1e9+7;
long long mp[110][110],dp[110][110];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>mp[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(mp[1][i]==0)
		break;
		dp[1][i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(mp[i][1]==0)
		break;
		dp[i][1]=1;
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=n;j++)
		{
			if(mp[i][j]!=0)
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%N;
		}
	}
	
	cout<<dp[n][n]<<endl;
	return 0;
 }

203 最大和上升子序列（线性dp）

  • 跟最长上升子序列差不多，注意初始化和状态转移方程改改就行
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[1005],dp[1005]; //dp[i]表示以a[i]结尾的最大和上升子序列的和 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i]=a[i];
	}
	
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(a[i]>a[j])
			dp[i]=max(dp[i],dp[j]+a[i]);
		}
		ans=max(ans,dp[i]);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

204 加一（dp)(回)

  • 因为最后要%mod，所以只需要考虑后10位。然后我们在后10位里找规律，得状态转移方程

    #include<bits/stdc++.h>

#define ll long long
using namespace std;

const int mod = 1e9 + 7;

int dp[13][200004];

void solve(){
    for(int i = 0; i <= 9; i++){
		for(int j = 0; j <= 10; j++) {
			if(i + j < 10) dp[i][j] = 1;
			else dp[i][j] = 2;
		}
	}

    for(int i = 0; i <= 9; i++){
		for(int k = 10; k <= 200000; k++){
			dp[i][k] = dp[i][k - 9] + dp[i][k - 10];
			dp[i][k] %= mod;
		}
	}
    
    int t; cin >> t;
    while(t--){
		int n,m;
		cin >> n >> m;
		int x = n;
		ll ans = 0;
		while(x){
			ans += dp[x % 10][m];
			ans %= mod;
			x /= 10;
		}
		cout << ans << '\n';
	}
}

int main(){
    solve();
    return 0;
}

205 跳跳

  • 这个数据量可以直接暴力！
  • 魔法阵取差值的最简式（比例不变，两边值最小
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>PII; 
const int MOD = 1e9 + 7;
const int N = 200010;
ll f[N+50][10];

int gcd(int x, int y)
{
	while (y ^= x ^= y ^= x %= y);
	return x;
}
int main()
{
	ll n, x, y;
	vector<PII>v;
	cin >> n;
	map<PII, int>mymap;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y;
		v.push_back({ x,y });
	}
	ll res = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (j == i)continue;
			int x = v[j].first - v[i].first;
			int y = v[j].second - v[i].second;
			if (x == 0 || y == 0)
			{
				x = x != 0 ? x / abs(x) : x;
				y = y != 0 ? y / abs(y) : y;
			}
			else
			{
				int num = abs(gcd(x, y));
				x /= num;
				y /= num;
			}
			if (mymap[{x, y}] == 0)
			{
				mymap[{x, y}] = 1;
				res++;
			}
		}
	}
	cout << res << endl;
	return 0;
}

206 异或和或

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s1, s2;
        cin >> s1 >> s2;
        int n = s1.length(), m = s2.length();
        if (n != m)
        {
            cout << "NO" << endl;
            continue;
        }
        int s1_zero = 0, s1_one = 0, s2_zero = 0, s2_one = 0;
        for (int i = 0; i < n; i++)
        {
            if (s1[i] == '0')s1_zero++;
            else s1_one++;

            if (s2[i] == '0')s2_zero++;
            else s2_one++;
        }
        if (s2_one == 0 && s1_one != 0)cout << "NO" << endl;
        else if (s2_one != 0 && s1_one == 0)cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}

207 01序列（前缀和）（map哈希表）

  • 用前缀和存前面出现了几个1

    刚开始用暴力写法没过

     for(int i=1;i<=len;i++)
	 {
	 	if(a[i]==k)
	 	ans++;
	 	for(int j=1;j<=i;j++)
	 	{
	 		if(a[i]-a[j]==k)
	 		ans++;
		 }
	 }

  • 前缀和，然后用map存相同前缀和的数量

    正常情况下，res+=前缀和为i的数量*前缀和为i-k的数量

    当k==0时，特判，子串数量为连续ans个0的子串

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long k,len,res;
long long a[N];
string s;
map<long long,long long> mp;
int main()
{
	cin>>k;
	cin>>s;
	len=s.length();
	mp[0]=1;
	if(k==0)
	{
		s+='1';
		len++;
		long long ans=0;
		for(int i=0;i<len;i++)
		{
			if(s[i]=='0')
			ans++;
			else
			{
				res+=ans*(ans+1)/2;
				ans=0;
			}
		}
	}
	else
	{
		for(int i=1;i<=len;i++)
		{
			a[i]=a[i-1]+(int)(s[i-1]-'0');
			mp[a[i]]++;
		}
		long long ans=0;
		while(mp[ans+k]!=0)
		{
			res+=mp[ans]*mp[ans+k];
			ans++;
		}
	}
	cout<<res<<endl;
	return 0;
}

301 出栈序列判断

  • 注意！！！！非空判断只能放在前面！！！要先判断非空，不然如果s已经空了还取s.top()就会有问题！！！
  • 注意！！！！'\n'比endl快！！！！这题如果用endl就会超时！！！'\n'不会！！！！！！
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int n;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	stack<int>s;
	int flag=0;
	for(int i=1;i<=n;i++)
	{
		s.push(i);
		cout<<"push "<<i<<'\n';

		while(!s.empty()&&s.top()==a[flag])
		{
			cout<<"pop"<<'\n';
			s.pop();
			flag++;
		}

	}
	while(!s.empty())
	{
		cout<<"pop"<<'\n';
		s.pop();
	}
	return 0;
}

302 序列维护

  • 直接用vector
#include<bits/stdc++.h>
using namespace std;
vector<int>v;
int main()
{
	int m;
	cin>>m;
	while(m--)
	{
		string s;
		cin>>s;
		if(s=="insert")
		{
			int x,y;
			cin>>x>>y;
			v.insert(v.begin()+x,y);
		}
		else if(s=="delete")
		{
			int x;
			cin>>x;
			v.erase(v.begin()+x-1);
		}
		else if(s=="query")
		{
			int x;
			cin>>x;
			cout<<v[x-1]<<endl;
		}
	
	}
	return 0;
}

303 网格判断

  • 基础题捏，注意细节不要着急
#include<bits/stdc++.h>
using namespace std;
int pd1,pd2,pd3;
char a[26][26];
bool flag=true;
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>a[i][j];
			if(pd2==3||pd3==3)
			flag=false;
			if(flag)
			{
				if(a[i][j]=='W')
				{
					pd1++;
					pd2++;
					pd3=0;
				}
				else
				{
					pd2=0;
					pd3++;
				}
			}
			
		}
		if(pd1!=n/2)
		flag=false;
		pd1=0;
		pd2=0;
		pd3=0;
	}
	if(flag)
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(pd2==3||pd3==3)
			flag=false;
			if(flag)
			{
				if(a[j][i]=='W')
				{
					pd1++;
					pd2++;
					pd3=0;
				}
				else
				{
					pd2=0;
					pd3++;
				}
			}
		}
		if(pd1!=n/2)
		flag=false;	
		pd1=0;
		pd2=0;
		pd3=0;
	}
	cout<<flag<<endl;
	return 0;
}

304 整齐的数组

  • __gcd()函数
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		long long ans=0;
		set<long long>a;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			long long x;
			cin>>x;
			a.insert(x);
		}
		bool f=0,f2=0;
		long long pre;
		for(auto it:a)
		{
			if(!f){
				pre=it;
				f=1;
			}
			else if(!f2)
			{
				ans=it-pre;
				f2=1;
			}
			else{
				ans=__gcd(it-pre,ans);
			}
		}
		if(ans)
		cout<<ans<<'\n';
		else
		cout<<"-1"<<'\n';
	}
	return 0;
 }

洛谷dp题

P1020 [NOIP1999 普及组] 导弹拦截

  • 最长不升（降）子序列

  • 狄尔沃斯定理（Dilworth）：对于任意有限偏序集，其中最长链的数目必定等于其最小反链划分中反链的数目。

    在本题中，第二问即求最长上升子序列的长度

  • 时间复杂度为O(n2)的算法

    #include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[1005],dp[1005]; //dp[i]表示以a[i]结尾的最大和上升子序列的和
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i]=a[i];
	}
	
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(a[i]>a[j])
			dp[i]=max(dp[i],dp[j]+a[i]);
		}
		ans=max(ans,dp[i]);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

  • 二分优化(+贪心思想)：low[i]表示的是子序列长度为i的情况下，该序列最后一个数的最小值(该值越小后面能接的数就越多)

    eg. 1 4 7 2 5 9
low[1]=1;
low[2]=2;//此时序列为1 2
low[3]=5;
....

    所以只需要遍历一次a[n]数组，二分法找出low[n]中第一个大于a[i]的数，并把它换成a[i]；

    如果都比a[i]小，最长子序列长度就能+1，然后把a[i]接在后面

    注意：low[n]的结果并不是最长子序列的排列

    #include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int a[N],low[N];
int n,js=1;
int binary_search(int x)
{
	int l=1,r=js;
	while(l<=r)
	{
		int mid=l+(r-l)/2;
		if(x<low[mid]) r=mid-1;
		else l=mid+1;
	}
	return l;
}
int main()
{
	while(cin>>a[++n])
	{
		if(cin.get()=='\n')
		break;
	}
	low[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		if(a[i]>low[js])
		low[++js]=a[i];
		else
		{
			int k=binary_search(a[i]);
			low[k]=a[i];
		}
	}
	cout<<js<<endl;
	return 0;
}

P1439 【模板】最长公共子序列(线性dp)（二分）

  • 线性dp，时间复杂度为O(n2)，二维数组开不了1e5

    #include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,maxn;
int a[N],b[N],dp[N][N];//dp[i][j]表示以a[i]结尾和以b[j]结尾的最长公共子序列长度 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>b[i];
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(b[j]==a[i])
			dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);
			else 
			dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		maxn=max(maxn,dp[i][j]);
	}
	cout<<maxn<<endl;
	return 0;
}

  • 二分法，时间复杂度nlogn

    • 注意读题：每行都是1~n的排列，也就是说第一排有的数第二排都有
    • 思路：把a[N]从1~n升序赋值，记录每个数字变成了哪个值，再将b[N]的值变成对应的，这样就将该题变成了在b[N]中查找最长升序子序列的问题！
    • 开longlong
    #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],belong[N],low[N],ans=1;
int binary_search(int x)
{
	int l=1,r=ans;
	while(l<=r)
	{
		int mid=l+(r-l)/2;
		if(x<low[mid]) r=mid-1;
		else l=mid+1; 
	}
	return l;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		belong[a[i]]=i;
	}
	
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		b[i]=belong[b[i]];
	}
	
	low[ans]=b[1];
	for(int i=2;i<=n;i++)
	{
		if(b[i]>low[ans])
		low[++ans]=b[i];
		else
		low[binary_search(b[i])]=b[i];
	}
	
	cout<<ans<<endl;
	
	return 0;
}

P2758 编辑距离

  • 思路：dp[i][j]表示a的前i个需要通过几次操作得到b的前j个

    dp[i][j]=dp[i-1][j]+1;           //删除
dp[i][j]=dp[i][j-1]+1;           //插入(注意)
dp[i][j]=dp[i-1][j-1]+1;         //修改
dp[i][j]=dp[i-1][j-1];           //不变

    AC代码

    #include<bits/stdc++.h>
using namespace std;
const int N=2010;
string a,b;
int len1,len2;
int dp[N][N];//dp[i][j]表示a的前i个需要通过几次操作得到b的前j个 
int main()
{
	cin>>a>>b;
	len1=a.length();
	len2=b.length();
	
//初始化 因为状态转移方程中有i-1,j-1，如果数组从0开始存会出现段错误 
	for(int i=len1;i>=1;i--) a[i]=a[i-1];
	for(int i=len2;i>=1;i--) b[i]=b[i-1]; 
	
//边界 
	for(int i=0;i<=len1;i++) dp[i][0]=i; 
	for(int i=0;i<=len2;i++) dp[0][i]=i;
	
	for(int i=1;i<=len1;i++)
	{
		for(int j=1;j<=len2;j++)
		{
			int x=1;
			if(a[i]==b[j]) x=0;
			dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+x);
		}
	}
	
	cout<<dp[len1][len2]<<endl;
	return 0;
 }

第十三届蓝桥杯

D 选数异或(dp)

  • 求存在性问题可以考虑用dp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x;
int dp[N];//dp[i]表示以i为右端点的最大左端点位置 
map<int,int>mp;
int main()
{
	cin.tie(0);
	cout.tie(0);//加速用
	cin>>n>>m>>x;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		dp[i]=max(mp[a^x],dp[i-1]);
		mp[a]=i; 
	}
	
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		if(dp[r]>=l) cout<<"yes"<<'\n';
		else cout<<"no"<<'\n';
	}
	return 0;
}

标签：week,14,int,cin,ans,using,include,dp
From： https://www.cnblogs.com/xiaoyangii/p/17768015.html

相关文章

  • Week 12
    Week12P1776宝物筛选思路：多重背包问题，用二进制优化注意：看清题目输入的顺序#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intw[N],v[N],s[N],dp[N];intmain(){ intW,n; cin>>n>>W; intnum=1; for(inti=1;i<=n;i++) { intx,y,z; ......
  • Week 6
    Week6贪心算法P1199[NOIP2010普及组]三国游戏知识点：贪心、博弈题思路：计算机的选择是贪心的，所以玩家和计算机都不可能选到默契值最大的武将组合。小涵赢的情况：在第二次选将时可以拿到第一次选中的武将的次大默契值组合。#include<bits/stdc++.h>usingnamespaces......
  • week 3
    Week3线性表P3613【深基15.例2】寄包柜分析：此题直接用数组得1e9个格子，内存要爆知识点map容器：find()返回数据所在位置的迭代器insert()插入pair迭代器：iterator，用于遍历容器元素（类似指针），输出*迭代器打印元素的值主要思路：vector容器嵌套map容器柜子数i......
  • week16
    Week16目录Week16div2代码源每日一题501RSA503A-B数对504数位计算505新国王游戏506完美数507Lusir的游戏601BFS练习1（广度优先）60201序列2603整除光棍604碰撞刷题P4913二叉树深度div2代码源每日一题501RSA质数正常判断即可A*B大于1的整数的平方的整数倍......
  • week7
    Week7动态规划P1048[NOIP2005普及组]采药思路：跟背包问题的思路差不多，for循环遍历所有情况，把选该草药和不选该草药的价值情况比较大小，选大的。#include<bits/stdc++.h>usingnamespacestd;constintN=1005;intw[N],v[N];//草药的时间和价值intres[N][N];//前i......
  • week5
    Week5P8604[蓝桥杯2013国C]危险系数知识点：图的vector存储和+dfs思路：用一个数组来记录每个节点被访问的次数，如果起点和终点之间有点的访问次数和终点的访问次数一样，那么它就是关键点。#include<bits/stdc++.h>usingnamespacestd;constintN=10005;intm,n,u,v,to......
  • 文心一言 VS 讯飞星火 VS chatgpt （114）-- 算法导论10.2 7题
    七、用go语言，给出一个O(n)时间的非递归过程，实现对一个含n个元素的单链表的逆转。要求除存储链表本身所需的空间外，该过程只能使用固定大小的存储空间。文心一言：在Go语言中，你可以使用迭代方法来反转一个单链表。这种方法只需要O(1)的额外空间。首先，我们需要定义链表的数据结构：t......
  • 文心一言 VS 讯飞星火 VS chatgpt （114）-- 算法导论10.2 7题
    七、用go语言，给出一个O(n)时间的非递归过程，实现对一个含n个元素的单链表的逆转。要求除存储链表本身所需的空间外，该过程只能使用固定大小的存储空间。文心一言：在Go语言中，你可以使用迭代方法来反转一个单链表。这种方法只需要O(1)的额外空间。首先，我们需要定义链表的数据结构：type......
  • 「解题报告」2023-10-14 模拟赛
    1．计数(count.cpp/c/pas)时间限制：1s内存限制：256MB【问题描述】给出\(m\)个数\(a_1,a_2,…,a_m\)求1~n中有多少数不是\(a_1,a_2,…,a_m\)的倍数。【输入】输入文件名为count.in。第一行，包含两个整数：\(n,m\)第二行，包含\(m\)个数，表示\(a_1,a_2,…,a_m\)【输出】......
  • 2023-2024-1 20231413 《计算机基础与程序设计》第四周学习总结
    班级：2023-2024-1-计算机基础与程序设计作业要求：2023-2024-1《计算机基础与程序设计》教学进程目标：自学教材：计算机科学概论第4、5章并完成云班课测试《C语言程序设计》第3章并完成云班课测试教材学习内容总结：了解了门和电路、计算部件的基础知识教材学习中的问题和解决过程：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99