CSP-S第二轮tips

WPY

发布于：2019年10月1日

C++学习

一些极其重要的提丶高丶组算法。

二分

const int N=100000+1000;
int n,p,d[N],l=1,r=99999999;
inline bool pand(int x){
	int sans=0;
	for(int i=1; i<=n; i++) sans+=d[i]/x;
	return sans>=p;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>p;
	for(int i=1; i<=n; i++){
		double a; cin>>a;
		d[i]=int(a*100); //化成整数做
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(pand(mid)) l=mid+1;
		else r=mid-1;
	}
	return cout<<fixed<<setprecision(2)<<double(r/100.0)<<endl,0; //还原
}

快速幂

P1226

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll b,q,k,ans=1;
inline ll kasm(){
	while(q>0){
		if(q & 1 ==1) ans=ans*b%k; //不要忘记%
		b=b*b%k;
		q >>= 1;
	}
	return ans;
}
int main()
{
	cin>>b>>q>>k;
	return cout<<b<<"^"<<q<<" mod "<<k<<"="<<kasm()%k<<endl,0;
}

搜索

深搜

###P2919

int n,m,a[1000][1000]={0},b[1000][1000]={0},ans=0,flag,maxx;
int dx[]={0,-1,-1,-1,0,0,1,1,1},dy[]={0,-1,0,1,-1,1,-1,0,1}; //方向数组
void dfs(int x,int y)
{
    for(int i=1; i<=8; i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>0 && xx<=n && yy>0 && yy<=m)
        {
            if(a[x][y]==maxx && a[xx][yy]>maxx) {flag=0; continue;}
            if(!b[xx][yy] && a[xx][yy]<=a[x][y])
            {
                b[xx][yy]=1;
                dfs(xx,yy);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int k=1; k<=m; k++)
            cin>>a[i][k];
    for(int i=1; i<=n; i++)
        for(int k=1; k<=m; k++)
        {
            if(a[i][k] && !b[i][k])
            {
                flag=1; maxx=a[i][k];
                dfs(i,k);
                ans+=flag;
            }
        }
    cout<<ans<<endl;
    return 0;
}

###P1506

const int N=500+1000;
int n,m,mp[N][N],ans=0;
int dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1};
void dfs(int x,int y){
	mp[x][y]=1;
	for(int i=1; i<=4; i++){
		int x0=x+dx[i],y0=y+dy[i];
		if(x0>0 && x<=n && y0>0 && y0<=m && !mp[x0][y0]) //判断边界和障碍物
      	dfs(x0,y0);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int k=1; k<=m; k++){
			char a; cin>>a;
			if(a=='*') mp[i][k]=1;
		}
	for(int i=1; i<=n; i++){ //边缘1
		if(!mp[i][1]) dfs(i,1);
		if(!mp[i][m]) dfs(i,m);
	}
	for(int i=1; i<=m; i++){ //边缘2
		if(!mp[1][i]) dfs(1,i);
		if(!mp[n][i]) dfs(n,i);
	}
	for(int i=1; i<=n; i++) //统计未被淹没的地方
		for(int k=1; k<=m; k++)
			if(!mp[i][k]) ans++;
	return cout<<ans<<endl,0;
}

种子染色

P1451

int m,n,a[200][200],ans=0;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
void print()
{
    for(int i=0; i<m; i++)
    {
        for(int k=0; k<n; k++)
            cout<<a[i][k];
        cout<<endl;
    }
    cout<<ans<<endl;
}
void dfs(int x,int y)
{
    if(x>m || x<0 || y>n || y<0) return;
    a[x][y]=0;
    for(int i=0; i<4; i++)
    {
        int x2=x+dx[i],y2=y+dy[i];
        if(a[x2][y2]) dfs(x2,y2);
    }
}
int main()
{
    cin>>m>>n;
    for(int i=0; i<m; i++)
        for(int k=0; k<n; k++)
        {
            char c; cin>>c;
            a[i][k]=c-'0';
        }
    for(int i=0; i<m; i++)
        for(int k=0; k<n; k++)
            if(a[i][k]) ans++,dfs(i,k);
    cout<<ans<<endl;
    return 0;
}

记忆化搜索

P1434

const int N=100+500;
int n,m,mp[N][N],f[N][N],ans=-99;
int dx[]={0,1,-1,0,0},dy[]={0,0,0,-1,1};
inline int dfs(int x,int y){
	if(f[x][y]) return f[x][y];
	int sans=1;
	for(int i=1; i<=4; i++){
		int tx=x+dx[i],ty=y+dy[i];
		if(tx>0 && tx<=n && ty>0 && ty<=m && mp[x][y]>mp[tx][ty])
			sans=max(sans,dfs(tx,ty)+1);
	}
	f[x][y]=sans; //记忆化
	return sans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int k=1; k<=m; k++)
			cin>>mp[i][k];
	for(int i=1; i<=n; i++)
		for(int k=1; k<=m; k++){
			f[i][k]=dfs(i,k);
			ans=max(ans,f[i][k]);
		}
	return cout<<ans<<endl,0;
}

动归

最长不降子序列

P1481

strstr(s1,s2)判断s2是否s1的子串，没有找到返回NULL，找到则返回子串第一个字符的地址

const int N=2000+100;
int n,f[N],ans=-999;
char s[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>s[i]; f[i]=1; //初始化
		for(int k=i-1; k>=1; k--)
			if(strstr(s[i],s[k])==s[i]) f[i]=max(f[k]+1,f[i]); //DP
		ans=max(ans,f[i]); //更新
	}
	return cout<<ans<<endl,0;
}

最长上升子序列(LIS)

例子：

有6个数，分别是： 1 7 6 2 3 4求最长上升子序列。

最长上升子序列的元素不一定相邻

最长上升子序列一定是原序列的子集

所以这个例子中的LIS就是：1 2 3 4，共4个
$$
n^2
$$

void print(int x){
    if(!x) return;
    print(from[x]);
    cout<<a[x]<<endl; //迭代输出
}
int main()
{
	cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++){
        dp[i]=1; from[i]=0; //from:前驱记录
        for(int k=1; k<i; k++)
            if(a[k]<d[i] && dp[i]<dp[k]+1) dp[i]=dp[k]+1,from[i]=k;
    }
    int ans=dp[1],p=1;
    for(int i=1; i<=n ;i++) if(ans<dp[i]) ans=dp[i],p=i;
    cout<<ans<<endl;
    print(p);
}

最长公共子序列(LCS)

P1439

使用dp[i][j]表示第一个串的前i位，第二个串的前j位的LCS长度

则状态转移方程为：

1: 如果有新的公共元素(A1[i]==A2[j])
$$
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
$$
2: 如果无法更新公共元素
$$
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
$$

朴实做法 (n^2)

cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a1[i];
for(int i=1; i<=m; i++) cin>>a2[i];
for(int i=1; i<=n; i++)
    for(int k=1; k<=m; k++){
        dp[i][k]=max(dp[i-1][k],dp[i][k-1]);
        if(a1[i]==a2[k]) dp[i][k]=max(dp[i][k],dp[i-1][k-1]+1);
    }
return cout<<dp[n][m]<<endl,0;

~~实则爆零~~

AC

以第一个串为标准，用第二个串来匹配第一个串，看能匹配多少

把第一个串离散化后的数组是满足上升，反过来，满足上升的也就是满足原串的排列顺序的

求一个最长不下降序列

lower_bound(begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。

通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#define INF 0x7fffffff
const int N=100000+1000;
int a[N],b[N],ma[N],ans=0,f[N],p[N],n;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		ma[a[i]]=i;
	}
	for(int i=1; i<=n; i++) cin>>b[i];
	for(int i=1; i<=n; i++){
		if(ma[b[i]]>p[ans]){
			p[++ans]=ma[b[i]];
			f[i]=ans; continue;
		}
		int k=lower_bound(p+1,p+ans+1,ma[b[i]])-p;
		p[k]=ma[b[i]];
		f[i]=k;
	}
	return cout<<ans<<endl,0;
}

01背包

P1417

平常做01背包的题时，由于i的价值永远是不变的，所以i讨论的顺序对结果不影响

但是这道题中，如果你先讨论了1号点，再讨论第二点，第二点的价值会减小，反之一号点会减小，这两个哪个更优是不确定的，所以如果你先讨论1号点就会错

由此，需要按优先度对所有点进行排序

const int N=100000+1000;
#define ll long long
struct data{
	ll a,b,c;
}d[N];
ll T,n,f[N],ans=0;
inline bool cmp(data x,data y){return x.c*y.b<y.c*x.b;}
int main()
{
	ios::sync_with_stdio(false);
	cin>>T>>n;
	for(ll i=1; i<=n; i++) cin>>d[i].a;
	for(ll i=1; i<=n; i++) cin>>d[i].b;
	for(ll i=1; i<=n; i++) cin>>d[i].c;
	sort(d+1,d+n+1,cmp);
	for(ll i=1; i<=n; i++)
		for(ll k=T; k-d[i].c>=0; k--)
			f[k]=max(f[k],f[k-d[i].c]+d[i].a-k*d[i].b);
	for(ll i=1; i<=T; i++) ans=max(ans,f[i]);
	return cout<<ans<<endl,0;
}

P1510

用01背包求出当精卫剩下的体力为x时，她最多能填多少海。这样，她第一次能填完海时剩下的体力就是所需的最小体力。

最后添加一个搜索就完成了。

int v,n,c,ans;
int f[100000];
int main()
{
    ios::sync_with_stdio(false);
    cin>>v>>n>>c;
    for(int i=1; i<=n; i++){
        int a,b; cin>>a>>b;
        for(int k=c; k>=b; k--)
            f[k]=max(f[k],f[k-b]+a); //填或不填
    }
    int p=0;
    for(int i=1; i<=c; i++)
        if(f[i]>=v) {p=1; ans=i; break;}
    if(p) cout<<c-ans<<endl;
    else cout<<"Impossible"<<endl;
    return 0;
}

P1855

const int N=1000;
int n,ma,ta,m[N],t[N],f[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>ma>>ta;
    for(int i=1; i<=n; i++){
        cin>>m[i]>>t[i];
        for(int k=ma; k>=m[i]; k--)
            for(int j=ta; j>=t[i]; j--)
                f[k][j]=max(f[k][j],f[k-m[i]][j-t[i]]+1); //实现与否
    }
    return cout<<f[ma][ta]<<endl,0;
}

完全背包

P1616

int n,m;
int v[100001],t[100001],f[100001]; 
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>t[i]>>v[i];
    for(int i=1; i<=m; i++)
        for(int k=t[i]; k<=n; k++)
            f[k]=max(f[k],f[k-t[i]]+v[i]);
    cout<<f[n]<<endl;
    return 0;
}

CSP-S problem plan

1.二分 (洛谷 1577)

2.快速幂（洛谷 1226）

3.搜索
1>.深搜（洛谷2919）
2>.广搜（洛谷1506）
3>.种子染色（洛谷1451）
3>.记忆化搜索（洛谷1434）

4.动规
1>.最长不降子序列：1481
2>.最长公共子序列：1439
3>.01背包：1417 1510 1855
4>.完全背包：1616
5>.多重背包：1776
6>.区间动规：3146

5.图论
1>.最短路
dij （堆优化）1629
floyed 1364
SPFA 1529
最短路计数 1144

2>.最小生成树
prim：1194
克鲁斯卡尔：1195

3> targen强连通分量 1656