首页 > 其他分享 >ACM日常训练日记——7.25

ACM日常训练日记——7.25

时间：2024-07-25 21:07:59浏览次数：15  
标签：7.25 ll ACM int MAXN long using 日记 dp

  • Atcoder训练
    1. Harlequin
      思维题博弈论，思考每一次怎么转化最优，存在两个答案说明f可以赢，打表发现当所有数字都是偶数时，答案为second，否则为first
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

int main(){
	
	ll n;
	cin>>n;
	ll ans=0;
	vector<ll>v(n+1);
	for(int i=1;i<=n;i++){
		ll b;
		cin>>b;
		if(b%2==0)ans++;
	}
	if(ans==n)cout<<"second";
	else
		cout<<"first";
}
  1. Gathering Children
    思维，模拟打表，最终会聚集在LR两个点上，我们考虑最终要不要交换两个点，打表模拟情况
    最后会发现如果：R+L为偶数，不变，如果R为奇数，那么L++，R不变，如果L为奇数，R++，L不变
#include <bits/stdc++.h>

using namespace std;

using ll=long long;
ll res[100001];

int main(){
	string s;
	cin>>s;
	int	n=s.length();
	vector<ll>v(n+1);
	int le=1;
	for(int i=0;i<n;i++){
		if(s[i]=='R'&&s[i+1]!='R'){
			v[i]+=le,le=1;
		}else if(s[i]=='R'&&s[i+1]=='R')le++;
		else le=1;
	}
	le=1;
	for(int i=n-1;i>=0;i--){
		if(s[i]=='L'&&s[i-1]!='L'){
			v[i]+=le,le=1;
		}else if(s[i]=='L'&&s[i-1]=='L')le++;
		else le=1;
	}
	for(int i=0;i<n;i++)
	{
		if(v[i]!=0)
		{
			if((v[i]+v[i+1])%2==0)
			{
				res[i]=(v[i]+v[i+1])/2;
				res[i+1]=res[i];
			}
			else
			{
				res[i]=floor((v[i]+v[i+1])/2);
				res[i+1]=res[i];
				if(v[i]%2==0)	res[i+1]++;
				else res[i]++;
			}
			i++;
		}
	}
	for(int i=0;i<n;i++)	cout<<res[i]<<" ";
}
  1. Palindrome Hard Problem
    之前没做出来的题，不难但是我做不出来，每次分出来一个数就是一个回文串，我们统计多少个数就是答案，我把每行可能m个看出成都是一个了
#include <bits/stdc++.h>
using namespace std;

using ll =long long;
map<char,ll>mp;
int main(){
	ll n;
	int sum=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		int k=s.length();
		sum+=k;
	}
	cout<<sum;
}
  1. Storybooks
    标准前缀和+二分，没做过可以回去再做一下，这道题注意边界和数据范围就行
#include <bits/stdc++.h>
using namespace std;

using ll =long long;

ll prefix[10011000];
int main(){
	int n,k;
	cin>>n>>k;
	vector<ll>v(n+1);
	vector<ll>d(k+1);
	for(int i=1;i<=n;i++)cin>>v[i];
	
	for(int i=1;i<=k;i++)cin>>d[i];
	
	sort(v.begin()+1,v.end());
	for(int i=1;i<=n;i++)prefix[i]+=v[i]+prefix[i-1];
	for(int i=1;i<=k;i++){
		ll l=0,r=n;
	while(l<=r){
		ll mid=(l+r)/2;
		if(prefix[mid]>d[i]){
			r=mid-1;
		}else
			l=mid+1;
	}
		cout<<r<<' ';
	}
}
  • 动态规划专项训练
    1.P1434 [SHOI2002] 滑雪
    利用记忆化dfs搜素的方法找到最长距离，好题，学会去用记忆化搜素。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = 105;
ll v[MAXN][MAXN];
ll dp[MAXN][MAXN];
int n, m;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

ll dfs(int x, int y) {
    //这里就是记忆化
	if (dp[x][y] != 0) return dp[x][y];
	dp[x][y] = 1;
	for (int i = 0; i < 4; ++i) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && v[nx][ny] < v[x][y]) {
			dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
		}
	}
	return dp[x][y];
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> v[i][j];
		}
	}
	
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			ans = max(ans, dfs(i, j));
		}
	}
	
	cout << ans << endl;
	return 0;
}

2.最长公共子序列
二维dp，状态转移方程a[i]=b[i]时,dp[i][j]=dp[i-1][j-1]+1，否则dp[i][j]=max(dp[i-1][j],dp[i][j-1])时间复杂度为n*n太高
最长公共子序列有专门的问题集最长公共子序列LCS问题
dp代码，注意边界dp[0][0]=0;

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

using ll = long long;
const int MAXN = 5001;
ll a[1000010];
ll b[100010];
ll dp[MAXN][MAXN];
int n, m;

int main(){
	string s;
	string t;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];

	ll ans=1;
	dp[0][0]=0;

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i]==b[j]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
			ans=max(ans,dp[i][j]);
			
		}
	}
	cout<<ans;
}
对于排列的 LCS 问题，有一种特殊的方法可以在线性时间内解决 我们可以利用排列的性质，将问题转化为最长递增子序列（LIS）问题，而 LIS 问题可以在 O(n log n) 时间内解决。 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = 100010;
int a[MAXN];
int b[MAXN];
int pos[MAXN];
int dp[MAXN];
int n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    // 将 a 中的元素位置映射到 b 中
    for(int i = 1; i <= n; i++) {
        pos[b[i]] = i;
    }

    // 将 a 中的元素替换为在 b 中的位置，然后求 LIS
    for(int i = 1; i <= n; i++) {
        a[i] = pos[a[i]];
    }
    // 求 LIS
    int len = 0;
    for(int i = 1; i <= n; i++) {
        int idx = lower_bound(dp, dp + len, a[i]) - dp;
        dp[idx] = a[i];
        if(idx == len) len++;
    }
    cout << len << endl;
    return 0;
}

背包问题
3.NOIP2001 装箱问题
01简化背包的基本过程，怎么去选取，还有优化内存大小的01滚动，就地滚动，转移方程dp[i%2][j]=dp[(i-1)%2][j]||dp[(i-1)%2][j-a[i]]

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

using ll = long long;
const int MAXN = 100010;
int pos[MAXN];
int dp[2][20020];
int a[40];
int n,m;
// 01背包  01滚动
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int v,n;
	cin>>v>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	dp[0][0]=1;
	/*
	  01滚动
	for(int i=1;i<=n;i++){
		for(int j=0;j<=v;j++){
	  //解释：还有空位放的话会放自己的值加上前面选的值加上当前的值，否则只放当前的值
	  //注意j不能从a[i]开始而是j从0开始，原因是小于a[i]的数也要留到下一轮
			if(j>=a[i]){
				dp[i%2][j]=dp[(i-1)%2][j]||dp[(i-1)%2][j-a[i]];
			}else
				dp[i%2][j]=dp[(i-1)%2][j];
		}
	}
	  */
    //就地滚动
	for(int i=1;i<=n;i++){
		for(int j=v;j>=a[i];j--)
		  dp[j]=dp[j]||dp[j-a[i]];
	}
	ll ans=0;
	for(int i=v;i>=0;i--){
		if(dp[i]==1){
			ans=i;
			break;
		}
	}
	cout<<ans;
	
}

2.【模板】01背包
现在目前有两种问法，一种是背包能装的最大价值，另一种是刚好装满的情况下，背包的最大价值
第一张解决方法的转移方程和第二种是一样的dp[j]=max(dp[j].dp[j-a[i]]+w[i])算出来不一定刚刚好容量大价值最大，但是一定在里面；
第二种是初始化为负无穷，最终判断pd[v]有没有初始化，有的话刚刚好满足条件的答案就是pd[v],都用01滚动

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N]; // f[j]表示体积为j的情况下的总价值
int v[N], w[N]; // 物品的体积 价值

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    memset(f, -0x3f, sizeof f);  //一开始都初始化为负无穷  方便记录是否有恰好体积为j的情况出现过  
    f[0] = 0; // 最开始体积为0价值为0
    for(int i = 1; i <= n; i ++) 
        for(int j = m; j >= v[i]; j --) // j>=v[i] 保证了可以选择第i个物品
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]); // 这里其实消去了一维
           // 原式为f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
           // 为了防止计算时所需要的上一层的数值被覆盖所以倒序遍历这样算f[j]时用到的f[j - v[i]]就还是和原来一样
        }
    
    int ans1 = 0, ans2 = 0;
    for(int i = 0; i <= m; i ++) ans1 = max(ans1, f[i]); // 找到最大值
    
    if(f[m] < 0) ans2 = 0; // 如果f[m]<0说明没被初始化过 没有体积恰好为m的情况出现
    else ans2 = f[m];  //否则根据定义可知 f[m]的值就是背包恰好装满的情况下的最大值
    
    cout << ans1 << endl;
    cout << ans2 << endl;
}
  • 牛客萌新联赛(第一场)（复盘）
    1.造数
    逆向思维，怎么把n变成0，能除2，就除，不能就减
#include<bits/stdc++.h>

using namespace std;

using ll =long long;

ll n,m,k,t;
ll v[1000100];
bool is(ll n) 
{
	return n > 0 && (n & -n) == n; 
}
int main(){
	cin>>n;
	if(n==0)cout<<0;
	else if(n==1)cout<<1;
	else if(n==2)cout<<1;
	else if(n==3)cout<<2;
	else if(n==4)cout<<2;
	else{
		ll ans=1;
		
		if(is(n)){
			while(n>2){
				n/=2;
				ans++;
			}
		}else{
			ll ans = 0;
			while (n >= 2) {
				if (n % 2 == 0) {
					n /= 2;
				} else {
					n -= 1;
				}
				ans++;
			}
            cout<<ans;
		}
			
	}
	return 0;
}

2.爱探险的朵拉
很好的记忆化搜素，我们需要认认真真学，这个每个路线判断是否已经走过，或者怎么避免已经走过的路线

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int> v(100010);
vector<int> b(100010);

int ma=0;
int cnt=1;
void bfs(int x,int l){
        //每次标记走过的
		b[x]=cnt;
        //直接找最大
	    ma=max(ma,l);
        //判断是否走过，这里不需要担心，不会走重复，之前走过的已经标记
	if(b[v[x]]!=cnt){
		bfs(v[x],l+1);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=n;i++){
        //这里就是原因
		if(b[i]==0){
          //cnt不同，路线不同
			cnt++;
			bfs(i,1);
		}
	}
	cout<<ma;
}

标签：7.25,ll,ACM,int,MAXN,long,using,日记,dp
From： https://www.cnblogs.com/dontian/p/18322326

相关文章

  • 2024.7.25（Git、gitlab以及分支管理）
    分布式版本控制系统一、Git概述Git是一种分布式版本控制系统,用于跟踪和管理代码的变更。它是由LinusTorvalds创建的,最初被设计用于Linux内核的开发。Git允许开发人员跟踪和管理代码的版本,并且可以在不同的开发人员之间进行协作。Github用的就是Git系统来管理它们的网......
  • 7.25第二周周四学习总结
    算法竞赛（差分）（上午）初始化#include<algorithm>intarr[100];std::fill(arr,arr+100,0);//比memset更高效intarr[100]={};//所有元素都初始化为0栈溢出为局部变量每次运行时都在运行栈中分配，如果数组很大，结果会造成运行栈溢出，自然就运行不了另外，使用全局变......
  • ssl证书90天过期？保姆级教程——使用acme.sh实现证书的自动续期
    前言最近https到期了，想着手动更新一下https证书，结果发现证书现在的有效期只有90天，于是想找到一个自动更新证书的工具，发现了acme.sh，但是网上的文章质量参差不齐，可能需要多篇文章结合来操作，一步步试错。我这里结合了腾讯云的相关文档和一些其他的博文，保证一次性操作成功。下载acme.......
  • （三）复习第三课（07.20- 07.25第二轮）：HTML标签元素练习大全
    <!DOCTYPEhtml><!--练习时间：2024.07.20-2024.07.25--><htmllang="en"><!--添加了en可以让你的网站打开时会提示翻译--><head> <pid="head1"></p><metacharset="utf-8"><!--对于中文网页需要使用此标签声明编码，否则会出现......
  • 订单日记助力“油帮手”成功数字化转型
    感谢官渡区油帮手汽配经营部选择使用订单日记！官渡区油帮手汽配经营部，成立于2023年，位于中国（云南）自由贸易试验区昆明片区官渡区，是一家以从事销售汽车零配件、润滑油、火花塞、防冻液等产品为主的企业。在业务不断壮大的过程中，想使用一种既能提升运营效率又能节省成本的系统......
  • JAVA小白自学日记Day9
     1.序列化序列化版本号：serialVersionUID，是一个类的序列化版本号。如果在反序列化时，类的serialVersionUID与序列化时的版本号不匹配，那么会抛出 InvalidClassException 异常，表示类的版本不兼容，无法进行反序列化。如果流量没有定义，JDK会自动给与一个版本号，当该类发生变化（......
  • 订单日记助力“中山俊丰橡胶制品”提升业务效率
    感谢中山市俊丰橡胶制品有限公司选择使用订单日记！中山市俊丰橡胶制品有限公司，成立于2020年，位于广东省中山市，是一家以从事橡胶和塑料制品业为主的企业。在业务不断壮大的过程中，想使用一种既能提升运营效率又能节省成本的系统管理工具，在市场上多方比较和考察后最终选择了订......
  • 泰凌微8258学习日记-6：LCD屏幕的点亮以及使用
            点亮LCD对我而言算是比较难的操作了，在了解到LCD点亮的步骤以后（开SPI,导入LCD驱动，主函数调用），我开始学习LCD的引脚功能，SPI如何使用，后面拿到中景园给的LCD例程（STM32的），修改LCD驱动（这一步是最难的）。好在有位大哥帮我，也是顺利完成了驱动的修改。......
  • 【日记】果然单身男青年就是牛马吗……（317 字）
    正文昨天睡觉被热醒了……半夜爬起来开空调。这是我头一次睡着的时候开两个小时以上的空调。今天又是搬东西的一天。单身，家住单位，男青年。纯纯牛马的象征。这帮人使唤起我来也没个心理负担，后来我就不干了。累了。她们还说我。光说我有啥用，活儿自己干去啊，反正我是不去了......
  • 泰凌微8258学习日记-5：五路PWM调光
            为了追求更加多样的色彩变化，由RGB三路PWM调光衍生出RGBWY五路PWM调光。与RGB一样，都是要配置相应的PWM，其实非常简单，如果你不需要用到手机APP或者tl-ble-phone-mesh来控制的话，那么你只需要配置好五个PWM，然后照着官方给的SDK代码，照葫芦画瓢地写一个light-adjust-C......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99