2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest

Solved


C、Evolution Game
D、Bus Stop
E、How Many Groups
G、Communication
H、As Rich as Crassus
J、Floating-Point Hazard
K、The Stream of Corning 2
L、Largest Allowed Area

Solution


C、Evolution Game
  • 考虑简单 \(dp\) 。
  • 先把 \(h_{i}\) 从小到大排序,那么答案一定是从小的转移到大的。 \(dp_{i}\) 表示以排序后第 \(i\) 个形态结尾的最大可选数量。
  • 转移方程:当 \(h_{j}\)代表形态满足条件时: \(dp_{i}=max(dp_{i},dp_{j}+1)\)( \(i>j\))。

代码:

struct node{
	int v,id;
	bool operator<(const node &a)const{
		if(v==a.v) return id<a.id;
		return v>a.v;
	}
}e[5050];
int dp[5050];
void run(){
	mem(dp,0);
	int n=rd(),w=rd();
	rep(i,1,n){
		e[i].v=rd();
		e[i].id=i;
	}
	int maxx=0;
	sort(e+1,e+1+n);
	dp[1]=0;
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(abs(e[i].id-e[j].id)<=w&&e[i].v<e[j].v){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		maxx=max(maxx,dp[i]);
	}
	cout<<maxx;
}
signed main()
{	
	int t=1;
	while(t--){
		run();
	} 
	// run();
	return 0;
}
D、Bus Stop
  • 简单签到

代码:

#include<bits/stdc++.h>

using namespace std;
const int maxn=2e6+10;
int h[maxn];
int main()
{
	int T,n;
	cin>>T;
	while(T--){
		cin>>n;
		memset(h,0,sizeof h);
		for(int i=1;i<=n;i++){
			scanf("%d",&h[i]);
		}
		if(n==0){
			printf("0\n");
			continue;
		}
		int ans=0;
		int minn=h[1];
		int pos=-1;
		for(int i=2;i<=n;i++){
			//cout<<i<<" "<<minn<<endl; 
			if(h[i]-pos<=10&&pos!=-1){
				minn=h[i+1]; 
				continue; 
			}
			if(h[i]-minn>=10){
				//cout<<i<<endl;
				pos=minn+10;
				//cout<<pos<<endl;
				//cout<<pos<<endl;
				ans++;
				if(h[i]-pos<=10){
					//cout<<i+1<<" "<<h[i+1]<<endl; 
					minn=h[i+1];
 				}else{
					minn=h[i];
				}
			}
		}
		//cout<<ans<<endl;
		if(minn==h[n])ans++;
		cout<<ans<<endl;
	}
 } 
E、How Many Groups
  • 考虑 \(dp\),先对数组从小到大进行排序。 \(dp[i][j]\) 表示以 \(i\) 为最后一个数经过 \(j\) 次变化得到的最大的答案。
  • \(j\) 这个变化次数可以转化成 当前第 \(i\) 个数和向 \(i\) 转移的数 \(k\) 总共的变化次数,那么这个变化次数的可能性就只有 \([0,1,2]\) 了。
  • 然后就可以通过枚举当前的 \(a_{i}\) 的变化,也就是 \(+1\), \(-1\), 不变。然后从前面转移即可。

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+10;

int dp[300][5];
int a[105];
int main()
{
    int T,n,CASE=0;
    cin>>T;
    while(T--){
        scanf("%d",&n);
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            //dp[a[i]][0]=1;
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            int num=a[i];
            for(int j=2;j>=1;j--){
                int temp=dp[num+1][j],temp2=dp[num+1][j];
                temp=max(temp,dp[num+1][j-1]+1);
                dp[num+1][j]=max(dp[num+1][j],temp);
                temp=temp2;
                temp=max(temp,dp[num][j-1]+1);
                dp[num+1][j]=max(dp[num+1][j],temp);
                temp=temp2;
                temp=max(temp,dp[num-1][j-1]+1);
                dp[num+1][j]=max(dp[num+1][j],temp);
                //cout<<dp[num][j]<<endl;
            }
            for(int j=2;j>=0;j--){
                int temp=dp[num][j],temp2=dp[num][j];
                temp=max(temp,dp[num][j]+1);
                dp[num][j]=max(dp[num][j],temp);
                temp=temp2;
                temp=max(temp,dp[num-1][j]+1);
                dp[num][j]=max(dp[num][j],temp);
                temp=temp2;
                if(num>=2){
                    temp=max(temp,dp[num-2][j]+1);
                    dp[num][j]=max(dp[num][j],temp);
                }
            }
            for(int j=2;j>=1;j--){
                int temp=dp[num-1][j],temp2=dp[num-1][j];
                temp=max(temp,dp[num-1][j-1]+1);
                dp[num-1][j]=max(dp[num-1][j],temp);
                temp=temp2;
                if(num>=2){
                    temp=max(temp,dp[num-2][j-1]+1);
                    dp[num-1][j]=max(dp[num-1][j],temp);
                }
                temp=temp2;
                if(num>=3){
                    temp=max(temp,dp[num-3][j-1]+1);
                    dp[num-1][j]=max(dp[num-1][j],temp);
                }
            }
        }
        int ans=1;
        for(int i=0;i<=250;i++){
            for(int j=0;j<=2;j++){
                ans=max(ans,dp[i][j]);
            }
        }
        printf("Case %d: %d\n",++CASE,ans);
    }
    return 0;
}
G、Communication
  • 刚开始读错题目。
  • 实际上就是求强连通分量的数量, \(tarjan\) 即可。

代码:

#include<bits/stdc++.h>
#define ll long long
#define MOD 998244353
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
int dfn[50005];
int low[50005];
int vis[50005];
int stacks[50005];
int color[50005];
int cnt[50005];
int deep,sum,top;
int n,m;
vector<int>g[50005];
void tarjan(int u)
{
   dfn[u]=++deep;
   low[u]=deep;
   vis[u]=1;
   stacks[++top]=u;
   for(int i=0;i<g[u].size();i++){
       int v=g[u][i];
       if(!dfn[v])
       {
          tarjan(v);
          low[u]=min(low[u],low[v]);
       }else{
           if(vis[v]){
              low[u]=min(low[v],low[u]);
           }
       }
   }
   if(dfn[u]==low[u])
   {
      color[u]=++sum;
      vis[u]=0;
      while(stacks[top]!=u)
      {
          color[stacks[top]]=sum;
          vis[stacks[top--]]=0;
      }
      top--;
   }
}
int main()
{
	int T;
	cin>>T;
	while(T--){
		deep=0;
    top=0;
    sum=0;
    mem(dfn,0);
    mem(vis,0);
    mem(cnt,0);
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)g[i].clear();
    while(m--){
       int from,to;
       scanf("%d %d",&from,&to);
       g[from].push_back(to);
    }
    for(int i=0;i<n;i++){
        if(!dfn[i]){
           tarjan(i);
        }
    }
    int num=0;
    for(int i=0;i<n;i++){
        cnt[color[i]]++;
    }
    cout<<sum<<endl;	
	}
    return 0;
}
H、As Rich as Crassus
  • 好像可以直接暴力。
  • 比赛时用拓展中国剩余定理。

代码:

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;

lt read()
{
    lt f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=100010;
int n;
lt ai[maxn],bi[maxn];

lt mul(lt a,lt b,lt mod)
{
    lt res=0;
    while(b>0)
    {
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

lt exgcd(lt a,lt b,lt &x,lt &y)
{
    if(b==0){x=1;y=0;return a;}
    lt gcd=exgcd(b,a%b,x,y);
    lt tp=x;
    x=y; y=tp-a/b*y;
    return gcd;
}

lt excrt()
{
    lt x,y,k;
    lt M=bi[1],ans=ai[1];//第一个方程的解特判
    for(int i=2;i<=n;i++)
    {
        lt a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b)
        lt gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1; //判断是否无解,然而这题其实不用
        
        x=mul(x,c/gcd,bg);
        ans+=x*M;//更新前k个方程组的答案
        M*=bg;//M为前k个m的lcm
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}

int main()
{   
    int t=read();
    while(t--){
    	n=3;
	    for(int i=1;i<=n;++i)
	    	bi[i]=read();
	    for(int i=1;i<=n;i++)
	    	ai[i]=read();
	    lt xx=excrt();
	    //cout<<"xx=="<<xx<<endl;
	    for(lt i=1;i<=1e7;i++){
	    	if(i*i*i==xx) {
	    		printf("%lld\n",i);
	    		break;
			}
		}
	}
   
    return 0;
}
J、Floating-Point Hazard
  • 考虑公式 \(\sum^{high}_{i=low} (\sqrt[3]{(i+10^{-15})} -\sqrt[3]{i} )\) ,可以想到求导公式 。
  • 设 \(f(x)\) 为原函数, \(f(x)=\sqrt[3]{i}\),设 \(f(x)\) 求导后为 \(g(x)\) ,那么上述公式就是 \(g(x)\times 10^{-15}\),为保持精度,直接把 \(10^{-15}\) 放到要输出的 \(E\) 后面,最后调整精度即可。

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+10;

int main()
{
    int l,r;
    while(1){
        scanf("%d%d",&l,&r);
        if(l+r==0)break;
        double num=0.0;
        for(int i=l;i<=r;i++){
            num+=(1.0/3.0)*pow(1.0*i,-2.0/3.0);
        }
        int x=-15;
        while(num>=10.0){
            x++;
            num=1.0*num/10.0;
        }
        while(num<1.0){
            x--;
            num=1.0*num*10.0;
        }
        printf("%.5fE%04d\n",num,x);
    }
}
K、The Stream of Corning 2
  • 考虑权值线段树。
  • \(l\) 和 \(p\) 总体递增,那么第 \(i\) 次询问的 \(p\)一定大于每个之前的 \(l\) ,那么影响答案的就是 之前所有操作的 \(r\) 的范围。
  • 考虑把每次操作的 \(l,r,p\)离散化,然后就可以从左到右扫描,遇到 \(l\) 就在权值线段树上插入对应的数,遇到 \(r\) 就删除对应的数,遇到询问,此时线段树一定是对应 \(p\) 点它拥有的线段,然后利用权值线段树求全局第 \(k\) 小即可。

代码:

#include<bits/stdc++.h>
#define ll long long
#define lson  rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn=3e5+10;

struct node{
    int opt,pos,val,id;
    bool operator <(const node &b) const {
        if(pos!=b.pos){
            return pos<b.pos;
        }else if(opt==2){
            return true;
        }else if(b.opt==2){
            return false;
        }else{
            return id<b.id;
        }
    }
}p[maxn];
int n;
int T[maxn<<2],lisan[maxn];
void push_now(int k)
{
    T[k]=T[k<<1]+T[(k<<1)|1];
}
void add(int rt,int l,int r,int pos,int val)
{
    if(l==r){
        T[rt]+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) add(lson,l,mid,pos,val);
    if(pos>mid) add(rson,mid+1,r,pos,val);
    push_now(rt);
}
int query(int rt,int l,int r,int k)
{
    if(T[rt]<k) return -1;
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(T[lson]>=k){
        return query(lson,l,mid,k);
    }else{
        return query(rson,mid+1,r,k-T[lson]);
    }
}
int main()
{
    int t,E,CASE=0;
    cin>>t;
    while(t--){
        scanf("%d",&E);
        int tot=0,cnt=0;
        for(int i=1;i<=E;i++){
            T[i]=0;
            int op;
            scanf("%d",&op);
            if(op==1){
                int l,v,r;
                scanf("%d%d%d",&l,&v,&r);
                lisan[++tot]=v;
                p[++cnt]=(node){1,l,v,i};
                p[++cnt]=(node){-1,r,v,i};
            }else{
                int pos,k;
                scanf("%d%d",&pos,&k);
                p[++cnt]=(node){2,pos,k,i};
            }
        }
        sort(lisan+1,lisan+tot+1);
        n=unique(lisan+1,lisan+tot+1)-(lisan+1);
        for(int i=1;i<=cnt;i++){
            if(p[i].opt!=2){
                p[i].val=lower_bound(lisan+1,lisan+n+1,p[i].val)-(lisan);
                //cout<<"yy"<<p[i].val<<endl;
            }
        }
        sort(p+1,p+cnt+1);
        int now=0;
        int ans[maxn];
        for(int i=1;i<=cnt;i++){
            if(p[i].opt!=2){
                add(1,1,n,p[i].val,p[i].opt);
            }else{
                //cout<<"yy"<<i<<endl;
                int temp=query(1,1,n,p[i].val);
                //cout<<"xxx"<<p[i].val<<" "<<temp<<endl;
                if(temp==-1){
                    ans[++now]=-1;
                }else{
                    ans[++now]=lisan[temp];
                }
            }
        }
        printf("Case %d:\n",++CASE);
        for(int i=1;i<=now;i++){
            printf("%d\n",ans[i]);
        }
    }
}
L、Largest Allowed Area
  • 二分答案。
  • 利用二维前缀和去判断是否成立即可。
  • 输入较大,一定要用快读。

代码:

#include<bits/stdc++.h>

using namespace std;
inline int rd(){int x = 0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-f;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return f*x;}
int sum[1005][1005];
int mp[1005][1005];
int n,m;
bool check(int num)
{
	int xx;
	for(int i=1;i<=n-num;i++){
		for(int j=1;j<=m-num;j++){
			if(sum[i+num][j+num]-sum[i-1][j+num]-sum[i+num][j-1]+sum[i-1][j-1]<=1){
				return true;
			}
		}
	}
	return false;
}
int main()
{
	int T;
    scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n;i++)sum[i][0]=0;
		for(int i=0;i<=m;i++)sum[0][i]=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				mp[i][j]=rd();
				sum[i][j]=0;
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
			}
		}
		int l=0,r=min(n,m)-1;
		int ans=0;
		int num=10;
		while(l<=r&&num--){
			int mid=(l+r)/2;
			if(check(mid)){
				l=mid+1;
				if(mid+1>ans)ans=mid+1;
			}else{
				r=mid-1;
			}
		}
		printf("%d\n",ans);
	}
}

2021-03-06 team training

上一篇:ACM模板笔记:最长不下降/上升子序列,最长公共子序列(DP)


下一篇:ACM算法——搜索篇(1)