题解 |文远知行杯广东工业大学第十六届程序设计竞赛

有点意思的一场。可惜只会签到。

本题解包含ABCEFHI。

A

经典分块。先预处理a[1]到a[1e4]。对L到R中的某个值，比如k，如果k小于1e4就直接用处理好的答案。k大于1e4单独讨论。注意到i=n/z+1，z>=2时，n%i为部分最大值。如：n=100时，z=2,i=n/z+1=51(此时n%i=49)，z=3,i=n/z+1=34(此时n%i=32)等等。预处理出z=2到z=1e4的i值，逐一检查是否在L到R内即可。复杂度O(sqrt(n)m)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mod 1000000007
#define debug 1
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;

#define for1(i,a,b) for(i=(a);i<=(b);i++)
#define for2(i,a,b) for(i=(a);i>=(b);i--)

ll p[1000005],q[1000005],s[1000005];

int main()
{
	ll t,n,m,i,j,k,l,r;
	
	cin>>n>>t;
	
	for(i=1;i<=1e4;i++)
	{
		p[i]=n%i;
	}
	
	for(i=1;i<=1e4;i++)
	{
		q[i]=n/i+1;
		s[i]=n%q[i];
	}
	
	while(t--)
	{
		ll ans=0;
		scanf("%lld %lld",&l,&r);
		
		ans=max(n%l,n%r);
		for(i=l;i<=min((ll)10000,r);i++) ans=max(ans,p[i]);
		
		for(i=1;i<=min((ll)10000,n);i++)
		{
			if(l<=q[i]&&q[i]<=r)
			ans=max(ans,s[i]);
		}
		
		printf("%lld\n",ans);
	}

	return 0;
}

B

签到。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mod 1000000007
#define debug 1
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;

#define for1(i,a,b) for(i=(a);i<=(b);i++)
#define for2(i,a,b) for(i=(a);i>=(b);i--)

char p[1000005],q[1000005];

int main()
{
	ll t,n,m,i,j,k;
	
	
	scanf("%s",&p);
	p[48]='0';
	
	ll ok=0;
	for(i=0;i<48;i++)
	{
		j=i;
		if(p[j]=='0') continue;
		
		while(p[j]=='1') j++;
		printf("%02lld:%02d - %02lld:%02d\n",
		i/2,i%2?30:0,j/2,j%2?30:0
		);
		
		ok=1;
		
		
		i=j;
	}
	if(!ok) printf("00:00 - 00:00");
	
	
	

	return 0;
}

C

先注意到显然如果对某行i,某行j,某列k，有p[i][k+1]-p[i][k]!=p[j][k+1]-p[j][k]，那么无解。注意这里的减法是模意义下的。

然后，我们先随便找出一个解。这个解写成如下形式：对每行，加上a1,a2,a3...an。对每列，加上b1,b2,b3...bm。

我们可以给a1-an所有数+1，然后给b1-bm所有数-1。注意这里的加减法全部都是模意义下的。显然这样的一步操作不会改变方格的结果。贪心的想一下就能发现，不断的执行这个操作，当a1-an和b1-bm这n+m个数中有一个数为0时，它可能是最优的情况。所以我们遍历一遍每个数，试着计算让它成为0时这n+m个数的和，最终取最小即可。

这题卡了快读。意义不明。

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef int ll;

#define mod 1000000007
#define debug 1
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;

#define for1(i,a,b) for(i=(a);i<=(b);i++)
#define for2(i,a,b) for(i=(a);i>=(b);i--)

ll p[2005][2005],q[1000005];

ll s1[2005],s2[2005],n1=0,n2=0;


long long calc(ll type,ll val,ll k)
{
	if(val==k) val=0;
	long long ret=0;
	int i,now;
	for(i=1;i<=n1;i++)
	{
		if(type==1) now=s1[i]+val+k;
		else now=s1[i]-val+k;
		
		while(now>=k) now-=k;
		ret+=now;
	}
	for(i=1;i<=n2;i++)
	{
		if(type==1) now=s2[i]-val+k;
		else now=s2[i]+val+k;
		
		while(now>=k) now-=k;
		ret+=now;
	}
//	cout<<val<<" "<<ret<<endl;
	return ret;
}

//------------------------------------

inline int read()
{
	int x=0,y=1;char c=getchar();//y代表正负（1.-1），最后乘上x就可以了。
	while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}//如果c是负号就把y赋为-1
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;//乘起来输出
}

//------------------------------------



signed main()
{
//	freopen("in.txt","r",stdin); 
	
	ll t,n,m,i,j,k;
	
	cin>>n>>m>>k;
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			p[i][j]=read();
		}
	}
	
	for(i=1;i<=n;i++)
	{
		ll need=k-p[i][1];
		if(need>=k) need-=k;
		for(j=1;j<=m;j++)
		{
			p[i][j]=p[i][j]+need;
			if(p[i][j]>=k) p[i][j]-=k;
		}
		s1[++n1]=need;
	}
	
	for(j=1;j<=m;j++)
	{
		ll need=k-p[1][j];
		if(need>=k) need-=k;
		for(i=1;i<=n;i++)
		{
			p[i][j]=p[i][j]+need;
			if(p[i][j]>=k) p[i][j]-=k;
		}
		s2[++n2]=need;
	}
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(p[i][j])
			{
				printf("-1");
				return 0;
			}
		}
	}
	
	
	long long ans=1e17;
	
	for(i=1;i<=n;i++) ans=min(ans,calc(1,k-s1[i],k));
	
	for(i=1;i<=m;i++) ans=min(ans,calc(2,k-s2[i],k));
	
	printf("%lld",ans);
	
	return 0;
}
/*
3 3 10
0 0 9 
0 0 9 
9 9 8

3 3 10
8 9 9 
9 0 0 
9 0 0

3 3 10
7 7 9
7 7 9
7 7 9

*/

D

不会。

E

写一个int solve(L,R)函数表示如果只考虑L到R，此时从L层开始最多可以爬多少层。先预处理所有solve(i,n)，其中1<=i<=n，记在q[i]中。对单次询问L,R，我们可以直接起点为L到起点为R-10的答案。因为这些地方的终点肯定不会超过R。然后暴力解决剩下的小部分。

#include<bits/stdc++.h>

using namespace std;

typedef int ll;

#define mod 1000000007
#define debug 1
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;

#define for1(i,a,b) for(i=(a);i<=(b);i++)
#define for2(i,a,b) for(i=(a);i>=(b);i--)

char p[100005];
ll q[100005];


//---------------------------------------------
//---------------------------------------------
//---------------------------------------------

const int maxn=100005;
int h[maxn],a[maxn];
int n,m;
int lowbit(int x)
{
    return x&(-x);
}
void update(int x)
{
    while(x<=n)
    {
        h[x]=a[x];
        for(int i=1;i<lowbit(x);i<<=1)
        h[x]=max(h[x],h[x-i]);
        x+=lowbit(x);
    }
    return ;
}
int findans(int begin,int end)
{
    int ans=0;
    while(end>=begin)
    {
        ans=max(ans,a[end]);
        end--;
        for(;end-lowbit(end)>=begin;end-=lowbit(end))
        ans=max(ans,h[end]);
    }

    return ans;
}

//---------------------------------------------
//---------------------------------------------
//---------------------------------------------


ll solve(ll st,ll ed)
{
	ll ret=0,i,hp=1;
	for(i=st;i<=ed;i++)
	{
		if(p[i]=='0') hp--;
		else hp++;
		if(hp==1) ret=max(ret,i-st+1);
		if(hp<=0) break;
		
		if(i-st>10) break;
	}
	
	return ret;
}

//------------------------------------

inline ll read()
{
	ll x=0,y=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}

//------------------------------------

int main()
{
	ll t,i,j,k;
	
	cin>>n;
	scanf("%s",p+1);
	
	for(i=1;i<=n;i++) q[i]=solve(i,n);
	
	for(i=0;i<=n+2;i++) h[i]=0;
	for(i=1;i<=n;i++) a[i]=q[i],update(i);
	
//	for(i=1;i<=n;i++) printf("%lld ",q[i]);
	
	ll L,R;
	t=read();
	while(t--)
	{
		L=read();R=read();
		
		ll ans=0;
		if(R-11>=L) ans=findans(L,R-11);
		
		for(i=max(L,R-12);i<=R;i++)
		{
			ans=max(ans,solve(i,R));
		}
		
		printf("%d\n",ans);
	}
	
	
	

	return 0;
}
/*
44
10101010101010101010111000111000000111000111

*/

F

想象两个数一左一右，一开始都是1。对每个质数如质数p，它若有k个，则它可以让左侧乘上x次p，其中1<=x<=k。它也可以让右侧乘上x次p，它也可以两边都不乘，但不可以两边都乘（否则这两个数就不互质了）。因此它有2k+1种选择。把总选择数相乘。


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mod 1000000007
#define debug 1
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;

#define for1(i,a,b) for(i=(a);i<=(b);i++)
#define for2(i,a,b) for(i=(a);i>=(b);i--)

ll p[1000005],q[1000005];

int main()
{
	ll t,n,m,i,j,k;
	cin>>t;
	while(t--)
	{
		ll ans=1;
		scanf("%lld",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%lld %lld",&j,&k);
			ans=(ans*(k*2+1))%mod;
		}
		
		printf("%lld\n",ans);
	}
	return 0;
}

G

不会。

H

对一个串，要将它全变0或全变1，最少操作次数是这个串中相邻两位不相等的个数。如000111001，至少要3次。因为它形如000-111-00-1，共有三个地方是相邻两位不相等的。因此我们维护相邻两位不相等的个数。这可以用线段树实现。


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mod 1000000007
#define debug 1
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;

#define for1(i,a,b) for(i=(a);i<=(b);i++)
#define for2(i,a,b) for(i=(a);i>=(b);i--)

//------------------------------------------------------------
//------------------------------------------------------------
//------------------------------------------------------------
#define MAXN 1000005
ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x)
{
    return x<<1;
}
inline ll rs(ll x)
{
    return x<<1|1;
}
inline void push_up(ll p)
{
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;
    if(l==r){ans[p]=a[l];return ;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
} 
inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]=tag[p]+k;
    ans[p]=ans[p]+k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
    ll res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid)res+=query(q_x,q_y,l,mid,ls(p));
    if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));
    return res;
}
//------------------------------------------------------------
//------------------------------------------------------------
//------------------------------------------------------------
 
char p[1000005];
ll now[1000005]={0};

int main()
{
	ll t,i,j,k;
	
	cin>>n>>t;
	
	build(1,1,n);
	
	scanf("%s",p+1);
	for(i=2;i<=n;i++)
	{
		if(p[i]!=p[i-1])
		{
			update(i,i,1,n,1,1);
			now[i]=1;
		}
	}
	
	ll type,L,R;
	while(t--)
	{
		scanf("%lld %lld %lld",&type,&L,&R);
		if(type==2)
		{
			if(L!=1)
			{
				if(now[L]==0)
				{
					update(L,L,1,n,1,1);
				}
				else
				{
					update(L,L,1,n,1,-1);
				}
				now[L]=!now[L];
			}
			R++;
			if(R!=n+1)
			{
				if(now[R]==0)
				{
					update(R,R,1,n,1,1);
				}
				else
				{
					update(R,R,1,n,1,-1);
				}
				now[R]=!now[R];
			}
		}
		else if(type==1)
		{
			printf("%lld\n",query(L+1,R,1,n,1));
		}
	}

	return 0;
}
/*
10 5
0010010010
0010001101
*/

I

对任何i，对位置在i，i+k，i+2k...的物品，我们称他们是一组的。显然不同组的物品不会互相影响，因为勾爪永远不可能同时抓起不在同一组内的物品。对每组单独考虑。问题变成了一个勾爪每次必须抓起相邻的两个物品。可以用dp实现。


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mod 1000000007
#define debug 1
#define deb(x) if(debug) cout<<#x<<"="<<x<< endl;

#define for1(i,a,b) for(i=(a);i<=(b);i++)
#define for2(i,a,b) for(i=(a);i>=(b);i--)

ll p[1000005],q[1000005];
ll dp[1000005][2];

vector<ll> x;

ll solve()
{
	ll ret=0;
	ll n=x.size();
	
	ll i,j;
	for(i=0;i<=n+3;i++) dp[i][0]=0,dp[i][1]=0;
	
	for(i=0;i<n-1;i++)
	{
		dp[i+1][1]=max(dp[i+1][1],dp[i][0]);
		
		dp[i+2][1]=max(dp[i+2][1],dp[i][1]+x[i]+x[i+1]);
		dp[i+1][1]=max(dp[i+1][1],dp[i][1]);
	}
	
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=1;j++)
		{
//			cout<<dp[i][j]<<" ";
			ret=max(ret,dp[i][j]);
		}
	}
	return ret;
}

int main()
{
	ll t,n,m,i,j,k;
	
	cin>>n>>k;
	
	for(i=1;i<=n;i++) scanf("%lld",&p[i]);
	
	
	ll ans=0;
	
	for(i=1;i<=k;i++)
	{
		x.clear();
		for(j=i;j<=n;j+=k)
		{
			x.push_back(p[j]);
		}
		ans+=solve();
	}
	
	cout<<ans;

	return 0;
}