AtCoder Beginner Contest 353

A

题意：检查是否有比第一个数大的数

#include<bits/stdc++.h>using namespace std;int main()
{int n;cin>>n;int a;cin>>a;int f=0;for(int i=2;i<=n;i++){int k;cin>>k;if(k>a){cout<<i<<endl;f=1;break;}}if(f==0){cout<<"-1"<<endl;}return 0;} 

B

题意：有n组人，还有一个k大小的座舱，题目保证每组人都小于k，计算要做多少个座舱

模拟，依次让每组人往里边坐，如果发现一组人不能完全坐满，则答案加1，换一个空的座舱

#include<bits/stdc++.h>using namespace std;
int n;
int a[110];
int main()
{int k;int res=0;cin>>n>>k;for(int i=0;i<n;i++) cin>>a[i];int i=0;int x=k;while(i<n){x-=a[i];i++;while(x>=a[i]&&i<n){x-=a[i];i++;}res++;x=k;}cout<<res<<endl;return 0;} 

C

思路：可以推出每个元素都会被加n-1次，那么可以把他们每个元素都乘以n-1，

因为当两个数相加大于1e8时，会取余数，就是相当于减去了一个1e8，所以还要计算减去1e8的个数

先排序，然后二分找每个数和其他数相加大于等于1e8的个数

如果找到的数，是在当前数的位置的前边，那么x=i+1（当前的位置+1），这样做是为了避免重复减去1e8

如果一个目标数被查找到的位置，是当前位置的前边，那么之前在更新被查找到的位置的数时，已经减去了一个1e8了，所以此时不能再减去1e8，同理，被查找到的位置 是当前位置，那么也要加1，这两个数不能相加

#include<bits/stdc++.h>using namespace std;
const int N = 3e5 + 10,mod=1e8;
#define int long long
int n;
int a[N];
int find(int x)
{int l=0,r=n+1;while(l<r){int mid=l+r>>1;if(a[mid]>=x) r=mid;else l=mid+1;}return r;}
signed  main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int res=0;sort(a+1,a+n+1);int cnt=0;for(int i=1;i<=n;i++){res+=(n-1)*a[i];int x=find(mod-a[i]);if(x<=i)//避免重复减去mod x=i+1;if(x>n) continue;res=res-(n-x+1)*mod;}cout<<res<<endl;return 0;} 

D

模拟

以第i个数为中心点

res加上(i-1)*a[i]

i后边的数，依次加上10^(数的位数），此处可以做个优化，先记录每个数的位数，存进map中，

在更新第i个数时，只需遍历1到10(因为位数是1到10)

#include<bits/stdc++.h>using namespace std;
const int N = 2e5 + 10,mod=998244353;
#define int long long
int n;
int a[N];
int q[15]={0,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000};
map<int,int> mp;
int ck(int x)
{int cnt=0;while(x){cnt++;x/=10;}return cnt;
}
signed  main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++)mp[ck(a[i])]++;int res=0;for(int i=1;i<=n;i++){res=(res+(i-1)*a[i]%mod)%mod;mp[ck(a[i])]--;for(int j=1;j<=10;j++){res=(res+(a[i]*mp[j]%mod)*(q[j]%mod)%mod)%mod;}}cout<<res<<endl;return 0;} 

E

依次计算最长公共前缀子串，记录每个子串出现的次数，每个字串贡献的价值为，cnt[i]*(cnt[i]-1)/2

3

ab ab ab

可以看出a字串出现了3次，ab字串出现了3次，总贡献值6

当时在想计算ab字串时，会不会重复？因为前边已经计算过a字串了

ab ab ac

此时就可以看出，必须得一个一个前缀字串考虑，因为第一个a字串，可以和第二个，第三个匹配，第二个和第三个匹配，产生3的贡献值，但ab字串只能和第二个匹配产生2的贡献值，因为题目要的是每次匹配的最长公共前缀字串的长度

突然想到，是不是也可以看为，ab字串的长度是2，a的字串在前边已经计算过了，而ab字串只是计算以b结尾的ab字串的数量可以产生的贡献值

再举一个例子 a ab abc abcd

字典树可以快速存储和查询字符串

#include<bits/stdc++.h>using namespace std;
const int N = 3e5 + 10,mod=998244353;
#define int long longint n;
int a[N];
map<string,int> mp;
int son[N][26],cnt[N],idx;
void insert(string s)
{int p=0;//p代表的是p表示第几个结点for(int i=0;i<s.size();i++){int x=s[i]-'a';if(!son[p][x]) son[p][x]=++idx;cnt[p]++;//每经历过一个字串就标记一下p=son[p][x];//将p指向他的子节点}cnt[p]++;
}
signed  main()
{string str;cin>>n;for(int i=1;i<=n;i++) {cin>>str;insert(str);}int res=0;for(int i=1;i<=idx;i++){res+=(cnt[i]*(cnt[i]-1)/2);}cout<<res<<endl;return 0;}