Binary Vector
https://ac.nowcoder.com/acm/contest/5671/B
这题主要考察逆元和线代知识,具体思路见下方:
#include<cstdio> const int mod=1e9+7,inv=5e8+4; int ans[20000005],f[20000005]; int main(){ int T,n=20000000; int Pow=1;ans[0]=1; for(int i=1;i<=n;i++){ Pow=1ll*Pow*inv%mod; ans[i]=1ll*ans[i-1]*(1-Pow+mod)%mod; f[i]=ans[i]^f[i-1]; } scanf("%d",&T); while(T--){ scanf("%d",&n); printf("%d\n",f[n]); } }
Combination of Physics and Maths
https://ac.nowcoder.com/acm/contest/5671/C
题意:一个矩阵的底面积定义为最后一行的数的和,重量定义为所有数的和,给一个正整数矩阵,找一个“压强”最大的可非连续子矩阵。
最大压强肯定就是单独的一列最大,枚举每个底面即可。
#include<iostream> using namespace std; int a[300][300],s[300][300]; int main(){ int T,n,m; cin>>T; while(T--){ cin>>n>>m; double ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",a[i]+j); s[i][j]=a[i][j]+s[i-1][j]; ans=max(ans,1.0*s[i][j]/a[i][j]); } printf("%.9f\n",ans); } return 0; }
Easy Construction
https://ac.nowcoder.com/acm/contest/5671/E
思路:很明显当i=n的时候,子序列即为本身,易得(n∗(n+1)/2)%n=k(n∗(n+1)/2)%n=k,所以k可以先判断一下k的值
对于偶数n,序列应该为 {n,1,n-1,2,n-2,…}
对于奇数n,序列应该为 {n,n/2,1,n-1,2,n-2,…}
#include<iostream> using namespace std; int n,k; int main(){ cin>>n>>k; if (n*(n+1)/2%n!=k) cout<<-1; else{ for(int i=1;i<=(n-1)/2;i++) cout<<i<<' '<<n-i<<' '; if(n%2==0) cout<<k<<' '; cout<<n; } return 0; }