本文主要是介绍AtCoder Beginner Contest 353,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
AtCoder Beginner Contest 353题解
A - Buildings (atcoder.jp)
读题模拟即可
代码:
void solve()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int m=a[1];for(int i=2;i<=n;i++){if(a[i]>m){cout<<i<<endl;return;}}cout<<-1<<endl;
}
B - AtCoder Amusement Park
阅读理解题,如果当前位置不够一个团队那就开走,然后模拟即可
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];int cnt=0,res=0;for(int i=1;i<=n;){if(cnt+a[i]<=m){cnt+=a[i++];}else{// cout<<i<<' '<<cnt<<endl;res++;cnt=0;}}res++;cout<<res<<endl;
}
C - Sigma Problem (atcoder.jp)
数学题,先不考虑 m o d 1 0 8 mod10^{8} mod108 我们先观察这个 ∑ i = 1 N − 1 ∑ j = i + 1 N f ( A i , A j ) \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j) i=1∑N−1j=i+1∑Nf(Ai,Aj).发现任意的一个元素都会加 n − 1 n-1 n−1次也就是说 ∑ i = 1 N − 1 ∑ j = i + 1 N f ( A i , A j ) = ∑ i = 1 n ( n − 1 ) ∗ A i \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)=\sum_{i=1}^{n}(n-1)*A_i i=1∑N−1j=i+1∑Nf(Ai,Aj)=i=1∑n(n−1)∗Ai然后再看 m o d mod mod操作因为是任意的两个数相加再取 m o d mod mod其中任意一个元素都小于 1 0 8 10^{8} 108两个相加就小于 2 ∗ 1 0 8 2*10^{8} 2∗108所以可以只要超过了 1 0 8 10^{8} 108取 m o d mod mod相当于减去了一个 1 0 8 10^{8} 108,所以这时候我们只要看任意两个数相加有多少个大于 1 0 8 10^{8} 108即可,这时候只需要排个序,然后用双指针维护只要找到满足两个元素相加小于 1 0 8 10^{8} 108的最大区间即可。就能保证时间复杂度在 O ( n ) O(n) O(n)
void solve()
{cin>>n;int s=0;map<int,int>mp;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++){s=s+(a[i]*(n-1));} int j=n;int cnt=0;for(int i=1;i<=n;i++){while(a[i]+a[j]>=p)j--;cnt+=min(n-j,n-i);}cout<<s-cnt*p<<endl;
}
D - Another Sigma Problem (atcoder.jp)
思维题,我们先观察一下 A = ( A 1 , … , A N ) A = (A_1, \ldots, A_N) A=(A1,…,AN) ,先假设数组是$ A_1=3,A_2=14,A_3=123,A_4=1700,A_5=100000,A_6=60,A_7=546,A_8=7954$
∑ i = 1 N − 1 ∑ j = i + 1 N f ( A i , A j ) \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j) i=1∑N−1j=i+1∑Nf(Ai,Aj).
假设此时 A j = A 3 A_j=A_3 Aj=A3 那么 f ( A 1 , A 3 ) = A 1 ∗ 1000 + A 3 f ( A 2 , A 3 ) = A 2 ∗ 1000 + A 3 f(A_1,A_3)=A_1*1000+A_3 \space f(A_2,A_3)=A_2*1000+A_3 f(A1,A3)=A1∗1000+A3 f(A2,A3)=A2∗1000+A3
假设此时 A i = A 3 A_i=A_3 Ai=A3那么 f ( A 3 , A 4 ) = A 3 ∗ 10000 + A 4 f ( A 3 , A 5 ) = A 3 ∗ 10000 + A 5 f(A_3,A_4)=A_3*10000+A_4 \space f(A_3,A_5)=A_3*10000+A_5 f(A3,A4)=A3∗10000+A4 f(A3,A5)=A3∗10000+A5
从中我们观察出 A i A_i Ai每次要乘以 1 0 l e n ( a j ) 10^{len(a_j)} 10len(aj)然后将得出的结论进行简化推理
假设 i < j < k i<j<k i<j<k
∑ i = 1 j − 1 ∑ j = i + 1 n f ( A i , A j ) = ∑ i = 1 j − 1 ∑ j = 1 n − 1 A i ∗ 1 0 l e n ( A j ) + A j = ( j − 1 ) ∗ A j + 1 0 l e n ( A j ) ∗ ∑ i = 1 j − 1 A i \displaystyle \sum_{i=1}^{j-1}\sum_{j=i+1}^n f(A_i,A_j)=\sum_{i=1}^{j-1} \sum_{j=1}^{n-1}A_i*10^{len(A_j)}+A_j=(j-1)*A_j+10^{len(A_j)}* \sum_{i=1}^{j-1}A_{i} i=1∑j−1j=i+1∑nf(Ai,Aj)=i=1∑j−1j=1∑n−1Ai∗10len(Aj)+Aj=(j−1)∗Aj+10len(Aj)∗i=1∑j−1Ai①
∑ j = 1 n − 1 ∑ k = j + 1 n f ( A j , A k ) = ∑ j = 1 n − 1 ∑ k = j + 1 n A j ∗ l e n ( A k ) + A k = A j ∗ ( ∑ k = j n l e n ( A k ) ) + ∑ k = j n A k \sum_{j=1}^{n-1}\sum_{k=j+1}^n f(A_j,A_k)=\sum_{j=1}^{n-1}\sum_{k=j+1}^nA_j*len(A_k)+A_k=A_j*(\sum_{k=j}^n len(A_{k}))+\sum_{k=j}^n A_{k} ∑j=1n−1∑k=j+1nf(Aj,Ak)=∑j=1n−1∑k=j+1nAj∗len(Ak)+Ak=Aj∗(∑k=jnlen(Ak))+∑k=jnAk②
①+②就是答案
换句话说只要做一下对 A i A_i Ai做一下前缀和和后缀和,在对 1 0 l e n ( A j ) 10^{len(A_j)} 10len(Aj)做后缀和即可
int n,m;
int a[N];
int v[N],r[N],l[N],sv[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++)v[i]=1;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)l[i]=(l[i-1]+a[i])%p;for(int i=n;i>=1;i--)r[i]=(r[i+1]+a[i])%p;for(int i=1;i<=n;i++){string s=to_string(a[i]);int len=s.size(); int tv=pow(10,len);v[i]=tv%p;}for(int i=n;i>=1;i--)sv[i]=(sv[i+1]+v[i])%p; int res=0;for(int i=1;i<=n;i++){// res=(res+v[i]*l[i-1]+a[i]*(n-1))%p;res=(res+a[i]*sv[i+1]+r[i+1])%p;}cout<<res<<endl;
}
E - Yet Another Sigma Problem (atcoder.jp)
用一下字典树然后记录一下每个前缀有多少个字符串 c n t ∗ ( c n t − 1 ) / 2 cnt*(cnt-1)/2 cnt∗(cnt−1)/2加起来即可
int n;
int son[N][26],cnt[N],idx=0;
void insert(string s)
{int p=0;for(int i=0;i<s.size();i++){int u=s[i]-'a';if(!son[p][u])son[p][u]=++idx;cnt[p]++;p=son[p][u];}cnt[p]++;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){string s;cin>>s;insert(s);}int res=0;for(int i=1;i<=idx;i++){res+=(cnt[i]*(cnt[i]-1)/2);}cout<<res<<endl;
}
这篇关于AtCoder Beginner Contest 353的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!