这一场没打 比赛结束后补了些题 还剩了几个之后会慢慢补上。都是中文题就不写题意了。
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; }