AtCoder Beginner Contest 353

很有趣的一场题，值得写一下题解：

A

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int x;
    cin>>x;
    for(int i=1;i<=n-1;i++)
    {
        int y;
        cin>>y;
        if(y>x)
        {
            cout<<i+1;
            return 0;
        }
    }
    cout<<-1;
}

B

很简单的分组，大于变0就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int a[N];
int main()
{
int n,m;
cin>>n>>m;
int ans=0;
int sum=0;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    if(sum+a[i]>m)
    {
        sum=a[i];
        ans++;
        if(i==n)
        {
            ans++;
        }
    }
    else
    {
        sum+=a[i];
                if(i==n)
        {
            ans++;
        }
    }
}

cout<<ans;
}

C

本题重要是范围不然还不好做

只需要找到每个数第一个加他大于1e8的数字的位置，然后就可以开始求前缀和了

因为在这之前的数字都是满足题意得相加，不用取模，因此并入答案

后面部分大于1e8就-1e8然后正常并入即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int long long
const int N=1e6+100;
ll a[N];
ll sum[N];
const int mod=100000000;
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
}
ll ans=0;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
    sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n-1;i++)
{
int x=lower_bound(a+i+1,a+n+1,100000000-a[i])-a;
//cout<<x<<'\n';
if(x==n+1)
{
ans+=(n-i)*a[i]+sum[n]-sum[i];
}
else
{
ans+=(x-n-1)*100000000+sum[n]-sum[x-1]+(n-x+1)*a[i];
ans+=(x-i-1)*a[i]+sum[x-1]-sum[i];
}

}
cout<<ans<<'\n';

}

D

本题也是前缀和加上一个*10操作，和获取位数即可

感觉<c啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int p=998244353;
int len(int num){
	int ans=0;
	while(num){
		ans++;
		num/=10;
	}
	return ans;
}
int qmi(int a,int b,int p){
	int res=1;
	while(b){
		if(b&1==1){
			res=(res*a)%p;
		}
		a=(a*a)%p;
		b>>=1;
	}
	return res;
}
signed main(){
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int ans=0;
	int sum=a[0];
	for(int i=1;i<n;i++)
    {
		ans=(ans+a[i]*i%p)%p;
		ans=(ans+sum*qmi(10,len(a[i]),p))%p;
		sum=(sum+a[i])%p;
	}
	cout<<ans<<'\n';
}

E

双哈希！

非常帅气的双哈希写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull n,ans,len,hs,Hs;
string s;
map<pair<ull,ull>,ull> mp;
int main(){
	cin >> n;
	for(ull i=1;i<=n;i++){
		cin >> s;
		len=s.length(),hs=Hs=1;
		for(ull j=0;j<len;j++)
        {
			hs=(hs*131+s[j]-'a'),Hs=(Hs*1331+s[j]-'a');
			ans+=mp[{hs,Hs}];
			mp[{hs,Hs}]++;
		}
	}
	cout << ans;
	return 0;
}

队友吐槽->

image-20240511220911868