题解 |文远知行杯广东工业大学第十六届程序设计竞赛
有点意思的一场。可惜只会签到。
本题解包含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;
}
J
不会。
会的构造和贪心乱杀，不会的还是到死都做不出来，咋办啊。烂完了。
百度公司氛围 312人发布
投递百度等公司10个岗位 >
