这一场没打 比赛结束后补了些题 还剩了几个之后会慢慢补上。都是中文题就不写题意了。
A:
B:思路:前缀和取模。标记下每次取模后该值(不为0)所在的位置,如果之后还出现取模后的值,则说明这一段内是可以被k除尽,比较一下取最大值。再处理取模后为0的情况即可。
while(t--)
{
ll n,k; cin >> n >> k;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
memset(vis,-1,sizeof(vis));
ll ans=-1;
for(ll i=1;i<=n;i++)
{
ll tmp=sum[i]%k;
if(tmp==0) ans=max(ans,i);
if(vis[tmp]==-1) vis[tmp]=i;
else ans=max(ans,i-vis[tmp]);
}
cout << ans << endl;
} C:由样例可以得,一段非降序的序列(cnt个数)可以分为(cnt+1)*cnt/2个子数组。直接遍历一遍,如果出现当前这个数小于它前面一个数,套前面公式累加再重新将cnt置1,如果没出现就一直cnt++,当循环结束再加上即可。 int main()
{
ios::sync_with_stdio;
cin.tie(0); cout.tie(0);
int n; cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
ll cnt=1;ll ans=0;
for(int i=2;i<=n;i++)
{
if(a[i]>=a[i-1]) cnt++;
else
{
ans+=(cnt+1)*cnt/2;
cnt=1;
}
}
ans+=(cnt+1)*cnt/2;
cout << ans << endl;
return 0;
} D:巴士博弈。每次至少取1,最多取k,由题意得取到倒数第二个的人必胜,所以直接将总数减一再直接套巴士博弈模板。
int main()
{
ios::sync_with_stdio;
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--)
{
int n,k; cin >> n >> k;
n--;
if(n%(k+1))
{
cout << "yo xi no forever!" << endl;
}
else cout << "ma la se mi no.1!" << endl;
}
return 0;
} E:威佐夫博弈。将乌龟牌上方和下方看成两堆,每次至少选一个,最后谁取到乌龟牌输,即谁先去玩那两堆谁赢。直接套威佐夫模板。
补充威佐夫结论:有两堆石子,数量为a,b.设a中的石子数量少于b中的。当a == (b - a) *(1+√5)/2此时先手必输。
该题还多了一张乌龟牌且取乌龟牌者输,即当a == (b - a) *(1+√5)/2后手必赢。
while(t--)
{
int n,x; cin >> n >> x;
int t1=x-1,t2=n-x;
if(t1>t2) swap(t1,t2);
int tmp=abs(t2-t1)*((1 + sqrt(5))/2);
if(tmp!=t1) cout << "yo xi no forever!" << endl;
else cout << "ma la se mi no.1!" << endl;
} F:
G:
H:结论题。总共三种情况,m==0,答案为n+2。m==1,答案为2*n。m==2,答案为2^n。
推导:m=0,如题。
m=1的情况如下:A(n,1)=A(A(n−1,1),0)。A(0,1)=1,所以 A(1,1)=A(1,0)=2,那么A(2,1)=A(A(1,1),0)=2+2=4,依此类推可根据数学归纳法可得:A(n,1)=2n
m=2的情况如下:A(n,2)=A(A(n−1,2),1)=2A(n−1,2),又因为A(0,2)=1,所以A(n,2)=2^n
int main()
{
ios::sync_with_stdio;
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--)
{
int n,m; cin >> n >> m;
if(m==0) cout << (n+2)%MOD << endl;
if(m==1) cout << (2*n)%MOD << endl;
if(m==2) cout << qmod(2,n)%MOD << endl;
}
return 0;
} I:等比公式。注意输出不是yes no。
while(t--)
{
int n; cin >> n;
int flag=0;
for(int i=2;i<=15;i++)
{
ll tmp=pow(2,i)-1;
if(n%tmp==0)
{
cout <<"YE5" << endl;
flag=1;
break;
}
}
if(!flag)cout << "N0" << endl;
} J: K:
L:经典二分了,不熟悉的可以再去做做青蛙跳。二分站台之间的距离,由题意得最小得距离我们设为l=0,最大为r=1e12。当然你根据题目输入的具体数值来初始化也是可以,然后check函数里面判断一下,若两站台的间距取当前mid,我们可添加多少新站台,小于等于k说明此时mid值太大更新r,否则更新l。两个相邻的车站之间最多还能建立(t-1+d)/d-1个车站。
bool check(ll d)
{
ll cnt=0;
for(int i=1;i<n;i++) {
ll t=a[i+1]-a[i];//相邻站台之间的距离
cnt+=(t-1+d)/d-1;//两站台之间在当前站台距离为d(mid)下可新添加的站台数
}
if(cnt<=k) return 1;
return 0;
}
int main()
{
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+1+n);
ll l=0,r=1e12;
ll ans=1e12+10;
while(l<r)
{
ll mid=(l+r)/2;
if(check(mid))
{
r=mid;
}
else l=mid+1;//,ans=min(ans,l);
}
cout << l << endl;
return 0;
}

京公网安备 11010502036488号