8.2学习记录

今天做题太不顺了，四道题都是自己不会的。
D. Color with Occurrences
题意：给定一个母串和若干子串，要求通过子串拼接母串，注意，如果子串发生重叠则忽略重叠影响。
即：母串为ababc，子串为aba和abc，拼接时第二个a字母重叠了，仍然视为合法拼接情况。

思路：也就是我们要找n个子区间覆盖一个大区间，思路就是最小区间覆盖，作为d3的D题码量略大

tag：贪心的最小区间覆盖问题是个经典，积累下板子。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2+100;
char t[N];
string s[N];
int n,q,len;
struct node
{
    
    int l,r,id;
};
bool cmp(const node &a,const node &b)
{
    
    if(a.l==b.l)
        return a.r>b.r;
    return a.l<b.l;
}
vector<node>seg;
vector<node>ans;
bool check(int st,string str)
{
    
    if(str.length()+st-1>strlen(t+1))
        return false;
    for(int i=0,j=st;i<(int)str.length();i++,j++)
    {
    
        if(str[i]!=t[j])
            return false;
    }
    return true;
}
int main()
{
    
    for(cin>>q;q;q--)
    {
    
        seg.clear();
        ans.clear();
        cin>>(t+1);
        cin>>n;
        len=strlen(t+1);
        for(int i=1;i<=n;i++)
        {
    
            cin>>s[i];
            for(int j=1;j<=len;j++)
            {
    
                if(check(j,s[i]))
                {
    
                    seg.push_back({
    j,j+(int)s[i].length()-1,i});
                }
            }
        }
        sort(seg.begin(),seg.end(),cmp);
       /* for(auto a:seg) { cout<<a.l<<" "<<a.r<<" "<<a.id<<endl; }*/
        int st=1,ed=len;
        bool falg=false;
        for(int i=0;i<seg.size();i++)
        {
    
            int j=i,temp=0,r=-1e9;
            while(j<seg.size()&&seg[j].l<=st)
            {
    
                 if(seg[j].r>r)
                 {
    
                     r=seg[j].r;
                     temp=j;
                 }
                 j++;
            }
            if(r<st)
                break;
            st=r+1;
            i=j-1;
            ans.push_back(seg[temp]);
            if(r>=ed)
            {
    
                falg=true;
                break;
            }
        }
        if(falg)
        {
    
            cout<<ans.size()<<endl;
            for(auto temp:ans)
            {
    
                cout<<temp.id<<" "<<temp.l<<endl;
            }
        }
        else
        {
    
            cout<<-1<<endl;
        }
    }
    return 0;
}

D. Gargari and Permutations

题意：给定n个排列求他们的LCS。

思路：这题其实数据量不大啊，可以nnk暴力去做，但是我代码调不出来啊qwq烦。
有一种一维的dp很好写
思路就是：由于这是个排列，所以所有数字都是独一无二不重复的，我们可以考虑，如果对于第一个数组中数组x出现在数字y的前方，而且对于之后的所有数组里，数字x都出现在y的前方，我们就认为xy是一个合法情况。lcs的长度增加1

DP记录路径的WA代码qwq

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+100;
int dp[N][N];
string str_dp[N][N];
int main()
{
    
    int n,k,maxx=-1;
    cin>>n>>k;
    string a;
    string s="0",s1="0";
    for(int i=1;i<=n;i++)
    {
    
        cin>>a;
        s+=a;
    }
    for(int i=2;i<=k;i++)
    {
    
        for(int j=1;j<=n;j++)
        {
    
            cin>>a;
            s1+=a;
        }
        for(int j=1;j<=n;j++)
        {
    
            for(int k=1;k<=n;k++)
            {
    
                if(s[j]==s1[k])
                {
    
                    dp[j][k]=dp[j-1][k-1]+1;
                    str_dp[j][k]=str_dp[j-1][k-1]+s[j];
                }
                else
                {
    
                    if(dp[j-1][k]>=dp[j][k-1])
                    {
    
                        dp[j][k]=dp[j-1][k];
                        str_dp[j][k]=str_dp[j-1][k];
                    }
                    else
                    {
    
                        dp[j][k]=dp[j][k-1];
                        str_dp[j][k]=str_dp[j][k-1];
                    }
                }
            }
        }
        maxx=max(maxx,dp[n][n]);
        s="0"+str_dp[n][n];
        s1="0";
        for(int j=0;j<=n;j++)
        {
    
            for(int k=0;k<=n;k++)
            {
    
                str_dp[j][k]="";
                dp[j][k]=0;
            }
        }
    }
    cout<<maxx<<endl;
    return 0;
}

一维DP的枚举代码。好巧妙（bx）

#include<bits/stdc++.h>
using namespace std;
int a[6][2005];
int b[6][2005];
int dp[2005];
int n,k;
int check(int x,int y)
{
    
	for(int i=2;i<=k;i++)
	{
    
		if(b[i][x]>b[i][y]) 
            return 0;
	}
	return 1;
}
int main()
{
    

	cin>>n>>k;
	for(int i=1;i<=k;i++)
    {
    
	  for(int j=1;j<=n;j++)
      {
    
	  	 cin>>a[i][j];
	  	 b[i][a[i][j]]=j;//i这个数列中a[i][j]这个数的位置
	  }
    }
	for(int i=1;i<=n;i++)
    {
    
        dp[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
    
      for(int j=i+1;j<=n;j++)
      {
    
      	  if(check(a[1][i],a[1][j]))
          {
    
              dp[j]=max(dp[i]+1,dp[j]);
          }
	  }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
    
        ans=max(ans,dp[i]);
    }
	  cout<<ans<<endl;
}

A. Orac and LCM
DIFF：1600

n个数的数组，我们任意两个数做lcm后求产生的所有lcm的gcd。

第一种做法：暴力
发现n是2e5，t飞了。
第二种做法：推公式。
根据lcm(a，b)=a*b/gcd(a,b)
推出题目要求的实际是
gcd{A[i]*B[j]/gcd｛a[1],a[n]｝|i<j}

#include<bits/stdc++.h>
#define int long long 

using namespace std;

const int N=1e5+5;
int n,a[N],b[N],ans;

signed main()
{
    
    cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>=1;i++)
		b[i]=__gcd(b[i+1],a[i]);
	for(int i=1;i<=n;i++)
		ans=__gcd(ans,a[i]*b[i+1]);
	cout<<ans/b[1]<<endl;
	return 0;
} 

第三种做法：筛素数因子。

用到了如下性质：
1.一个数可以由分解成一些素数的幂次方相乘得到
2.两个数的LCM就是两个数分解的素数因子后，相同的素数因子区最大幂次之后再相乘。
比如10=25，24=2223，那么lcm（10，24）=2 * 2 * 2 * 3 * 5；

3.两个数的gcd就是相同素数的最小次幂

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 300010;

int f[MAXN];
int g[MAXN];

int tot,n;
int pri[MAXN];
int chk[MAXN];
int Min[MAXN];

inline void Sieve(int n)
{
    
	for(int i = 2; i <= n; i++)
    {
    
		if(!chk[i])
            pri[++tot] = i, Min[i] = i;
		for(int j = 1; j <= tot; j++)
        {
    
			if(i * pri[j] > n)
			 break;
			chk[i * pri[j]] = 1;
			Min[i * pri[j]] = pri[j];
			if(i % pri[j] == 0)
			break;
		}
	}
}

vector<int>d[MAXN];
int main()
{
    
	Sieve(200000);
	cin>>n;
	for(int i=1,x;i<=n;i++)
    {
    
		cin>>x;
		while(x>1)
		{
    
			int p=Min[x];
			int ct=0;
			while(x%p==0)
			{
    
			    x/=p;
			    ++ct;
			}
			d[p].push_back(ct);
		}
	}
	int res=1;
	for(int i=1;i<=200000;i++)
    {
    
		if((int)d[i].size()>=n-1)
		{
    
			sort(d[i].begin(),d[i].end());
			int pw=d[i][0];
			if((int)d[i].size()==n)
            {
    
                pw=d[i][1];
            }
			while(pw--)
            {
    
                res*=i;
            }
		}
	}
	cout<<res<<endl;
	return 0;
}