提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- A. Tricky Template
-
- 题意：
- 题解：
- 代码：
- B. Forming Triangles
-
- 题意：
- 题解：
- 代码：
- C. Closest Cities
-
- 题意：
- 题解：
- 代码：
A. Tricky Template
题意：
给出三个由小写字母组成的字符串a，b，c，问是否存在一个模板串t，使得a，b与模板串相匹配，c与模板串不匹配。匹配条件有两个，若t的某个字母为小写，则a与之对应的位置相等，若t的某个字母为大写，则a与之对应的字母不同。每个位置都满足，则a和t相匹配，否则不匹配。
题解：
枚举a，b，c每一位，当
a
i
a_{i}
ai?=
b
i
b_{i}
bi?
=
=
=
c
i
c_{i}
ci?时,此时
t
i
t_{i}
ti?为任何字母时，都满足对a，b，c匹配；当
a
i
a_{i}
ai?=
b
i
b_{i}
bi?
!
=
!=
!=
c
i
c_{i}
ci?时,存在
t
i
t_{i}
ti?
=
=
=
a
i
a_{i}
ai?，满足对
a
i
a_{i}
ai?，
b
i
b_{i}
bi?匹配，与
c
i
c_{i}
ci?不匹配；当
a
i
a_{i}
ai?!=
b
i
b_{i}
bi?
!
=
!=
!=
c
i
c_{i}
ci?时,存在
t
i
t_{i}
ti?，满足对
a
i
a_{i}
ai?，
b
i
b_{i}
bi?匹配，与
c
i
c_{i}
ci?不匹配；当
a
i
a_{i}
ai?=
b
i
b_{i}
bi?，且
c
i
c_{i}
ci?=
a
i
a_{i}
ai?或者
c
i
c_{i}
ci?=
b
i
时
b_{i}时
bi?时，
t
i
t_{i}
ti?只能为大写字母，且与
a
i
a_{i}
ai?,
b
i
b_{i}
bi?,
c
i
c_{i}
ci?都匹配，记录与a，b，c都匹配的元素个数，若个数等于字符长度则不存着这样的模板串，否则存在。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=25;
char a[N],b[N],c[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
scanf("%s",a);
scanf("%s",b);
scanf("%s",c);
int cnt=0;
for(int i=0;i<n;i++)
{
if(a[i]!=b[i]&&(c[i]==a[i]||c[i]==b[i])) cnt++;
if(a[i]==b[i]&&a[i]==c[i]) cnt++;
}
if(cnt==n)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
B. Forming Triangles
题意：
给出一个长度为n的数组m，存在n个小棍，每根小棍的长度为
2
m
i
2^{m_{i}}
2mi?，问由这些木棍可以构成多少个三角形。
题解：
假设组成的三角形最长的边是
2
c
2^{c}
2c，其次是
2
b
2^{b}
2b，
2
a
2^{a}
2a，则满足
c
c
c
>
=
>=
>=
b
b
b
>
=
>=
>=
c
c
c，且
2
a
2^{a}
2a+
2
b
2^{b}
2b>
2
c
2^{c}
2c，只有当
c
c
c
=
=
=
b
b
b时同时满足两个不等式，且
a
a
a只要满足小于等于
c
c
c即可。设数组中存在cnt个数值为t的数字，且存在m个小于t的数字，当cnt>=3时，存在
C
c
n
t
3
C_{cnt}^3
Ccnt3?个三边都为t的三角形，同时存在
C
3
2
C_{3}^2
C32?
?
*
?
m
m
m个两边为
2
t
2^{t}
2t，一边为小于
2
t
2^{t}
2t的三角形，若cnt=2时存在
C
3
2
C_{3}^2
C32?
?
*
?
m
m
m，两边为
2
t
2^{t}
2t,一边小于
2
t
2^{t}
2t的边。
代码：
#include<iostream>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int t;
void solve(){
int n;
int m=0;
int sum=0;
map<int,int> mp;
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
mp[x]++;
}
for(auto mp:mp){
int t=mp.second;
if(t>=3) sum+=t*(t-1)*(t-2)/6+t*(t-1)/2*m;
else if(t==2) sum+=t*(t-1)/2*m;
m+=t;
}
cout<<sum<<endl;
}
signed main(){
cin>>t;
while(t--) solve();
return 0;
}
C. Closest Cities
题意：
在一条线上有n个城市，每个城市的坐标为
a
i
a_{i}
ai?，以下是收费规则，设
a
a
a,
b
b
b,
c
c
c为三个相邻得的城市，若
b
b
b距离
a
a
a最近则路费仅需
1
1
1元,
b
b
b,
c
c
c之间的路费则为
c
?
b
c-b
c?b元，问要想从
l
l
l到
r
r
r最少需要多少钱。
题解：
由题意知，从
l
l
l到
r
r
r最少花费就是从
l
l
l到
l
+
1
l+1
l+1,
l
+
2
l+2
l+2,…
r
r
r;这种路径花费才是最少，若其中两点为
a
a
a,
b
b
b，若
a
a
a距离
b
b
b最近则花费为
1
1
1，否则花费为
b
?
a
b-a
b?a,利用前缀和知识解决。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
int t;
void solve(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
b[1]=0;
b[2]=1;
for(int i=3 ;i<=n;i++){
if(a[i]-a[i-1]<a[i-1]-a[i-2]) b[i]=1;
else b[i]=a[i]-a[i-1];
}
for(int i=1;i<=n;i++) b[i]+=b[i-1];
c[n]=0;
c[n-1]=1;
for(int i=n-2;i>=1;i--){
if(a[i+2]-a[i+1]>a[i+1]-a[i]) c[i]=1;
else c[i]=a[i+1]-a[i];
}
for(int i=n-1;i>=1;i--) c[i]+=c[i+1];
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
if(l<r) cout<<b[r]-b[l]<<endl;
else cout<<c[r]-c[l]<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--) solve();
return 0;
}