ACM日常训练日记——7.25

  • 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;
}

3.旅途的终点
思维+二分,二分答案x一定能走到的国家数,是按顺序走的,然后每次二分检查的时候排序前x个国家数,前面的数我们不用神力,如果满足条件就l=mid+1.
这种按顺序的二分和思维一定要掌握

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

using ll =long long;
vector<ll>v(2e5+8);
ll n,m,k;
bool check(ll x){
	ll hp=m;
	vector<ll>s(n+1);
    s=v;
	sort(s.begin()+1,s.begin()+1+x,greater<ll>());
	for(int i=k+1;i<=x;i++){
		if(hp<=s[i])return false;
		  hp-=s[i];
	}
	return true;
}

int main(){
	cin>>n>>m>>k;
    ll ans=0;
	for(int i=1;i<=n;i++)cin>>v[i];
	ll l=0,r=n;
	while(l<=r){
		ll mid=(l+r)/2;
		if(check(mid)){
			l=mid+1; 
            ans=mid;
		}else
			r=mid-1;
	}
	cout<<ans;
}

热门相关:文娱缔造者   四爷又被福晋套路了   纨绔仙医   战斗就变强   顶级气运,悄悄修炼千年