呜呜呜，第一次打完完整的 ABC。才打了 2000 多名，太菜了。（
A - Jiro
十分简单，分讨即可。
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
char a,b,c;
int main(){
cin>>a>>b>>c;
if(a=='>'){
if(b=='>'){
if(c=='>')cout<<"B"<<endl;
if(c=='<')cout<<"C"<<endl;
}
if(b=='<'){
if(c=='>')cout<<"A"<<endl;
if(c=='<')cout<<"A"<<endl;
}
}
if(a=='<'){
if(b=='>'){
if(c=='>')cout<<"A"<<endl;
if(c=='<')cout<<"A"<<endl;
}
if(b=='<'){
if(c=='>')cout<<"C"<<endl;
if(c=='<')cout<<"B"<<endl;
}
}
return 0;
}
时间复杂度 \(O(1)\)。
B - Taro
用一个数组记录每个家庭是否生过一个男孩。
如果是女的直接输出 no，否则查看数组是否标记，然后做判断。
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N=105;
int n,m,mk[N];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
char f;int x;
cin>>x>>f;
if(f=='F')cout<<"No"<<endl;
else{
if(mk[x])cout<<"No"<<endl;
else cout<<"Yes"<<endl,mk[x]=1;
}
}
return 0;
}
时间复杂度 \(O(n)\)。
C - Make Isomorphic
终于不再入门。不过依然十分简单。
“同构”的关系比较难处理，不过我们可以这样理解同构：
给每个 \(G\) 上的点 \(i\) 确定一个 \(H\) 上的点 \(p_i\)，如果 \(G,H\) 同构，则说明 \(\forall (i,j),G_{i,j}=1,H_{p_i,p_j}=1\)。
排列 \(p\) 是不确定的，不过 \(n\le 8\)，可以暴力枚举全排列，然后取所有全排列的方案的最小花费。
计算方案的花费非常简单，先将原图使用邻接矩阵存储下来，枚举邻接矩阵上的每个位置，如果存在没某个位置 \((i,j)\) 使得 \(G_{i,j}\ne H_{i,j}\)，则花费增加 \(A_{i,j}\)。
全排列可以用 STL 中的 next_permutation 函数来实现。
点击查看代码
#include <iostream>
#include <algorithm>
using namespace std;
int p[10],n,w[10][10],h[10][10],m,ans=1e9+10,a[10][10];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
p[i]=i;
}
cin>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
w[u][v]=w[v][u]=1;
}
cin>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
h[u][v]=h[v][u]=1;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
while(1){
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(w[i][j]!=h[p[i]][p[j]])res+=a[p[i]][p[j]];
}
}
ans=min(ans,res);
if(!next_permutation(p+1,p+1+n))break;
}
cout<<ans<<endl;
return 0;
}
时间复杂度 \(O(n!·n^2)\)
D - 1D Country
感觉比上一题还简单，不过有一点细节。
静态查询区间和，显然可以用前缀和。
下标过大，可以离散化，然后二分查找，因为题目限制，实现起来非常简单。
注意二分的边界问题，如果不存在一个村庄位置小于当前查询的 \(l\)，或不存在一个村庄位置大于当前查询的 \(r\)。答案都是 \(0\)。
否则二分查找第一个大于等于 \(l\) 的村庄离散化后的值，即为查询的左边界；二分查找第一个大于 \(r\) 的村庄离散化后的值，其减一即为查询的有区间。可以用 STL 中的 lower_bound 和 upper_bound 实现。
点击查看代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+10;
typedef long long ll;
ll n,q,x[N],s[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",x+i);
}
for(int i=1;i<=n;i++){
scanf("%lld",s+i);
s[i]+=s[i-1];
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
ll l,r;
scanf("%lld %lld",&l,&r);
if(l>x[n]||r<x[1])printf("0\n");
else{
l=(lower_bound(x+1,x+1+n,l)-x)-1;
r=(upper_bound(x+1,x+1+n,r)-x)-1;
printf("%lld\n",s[r]-s[l]);
}
}
return 0;
}
时间复杂度 \(O(q\log n)\)。
E - I Hate Sigma Problems
终于上难度哩！
由于长的像序列分治，所以我决定使用序列分治。
假设当前分治区间为 \([l,r]\)，令 \(mid=\dfrac{l+r}{2}\)。我们考虑如果快速计算所有 \(l\le i\le mid<j\le r\) 的 \(f(i,j)\) 之和。
我们考虑枚举 \(j\)，假设 \(s=\sum_{i=l}^{mid}f(i,j-1)\)。我们考虑 \(a_j\) 的加入对 \(s\) 的影响。
如果存在 \(k\in[mid+1,j-1],a_k=a_j\)，则 \(a_j\) 的加入无任何影响，即 \(\sum_{i=l}^{mid}f(i,j)=\sum_{i=l}^{mid}f(i,j-1)\)
如果不存在 \(k\) 满足上述条件，那么对于那些 \(i\in [l,mid]\) 且不存在 \(k\in [i,mid]\) 使得 \(a_k=a_j\) 的区间 \(f(i,j)\) 均等于 \(f(i,j-1)+1\)。我们直接在 \(s\) 上修改。
暴力枚举 \(i\) 显然是低效的，我们预处理出 \(lst_x\) 表示 \(x\) 在 \([l,mid]\) 中最后一次出现的位置，显然所有 \(i\in [lst_{a_{j}}+1,mid]\) 均满足要求。
最后记得清空。
点击查看代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int n,a[N],lst[N],mk[N];
ll ans;
void solve(int l,int r){
if(l==r){ans++;return;}
int mid=(l+r)>>1;
ll res=0,sum=0;
solve(l,mid);
solve(mid+1,r);
for(int i=mid;i>=l;i--){
if(!lst[a[i]])lst[a[i]]=i,res++;
sum+=res;
}
for(int i=mid+1;i<=r;i++){
if(!mk[a[i]]){
if(lst[a[i]])sum+=mid-lst[a[i]];
else sum+=mid-l+1;
mk[a[i]]=1;
}
ans+=sum;
}
for(int i=l;i<=mid;i++)lst[a[i]]=0;
for(int i=mid+1;i<=r;i++)mk[a[i]]=0;
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
solve(1,n);
printf("%lld\n",ans);
return 0;
}
时间复杂度 \(O(n\log n)\)。
好像有点复杂了
F - Takahashi in Narrow Road
赛时理解错题意了，本来以为是安排最优方案，没想到是模拟。
好像用线段树做一下就可以了，可惜没时间了
G - Lexicographically Smallest Permutation
赛时好像有点思路？大概是并查集+贪心。
可是时间太短了。
The End
这么说给我四个小时我可以 AK ABC?!?这一定是时间太短的问题
标签：10,cout,int,ll,mid,include,ABC371 From： https://www.cnblogs.com/zuoqingyuan/p/18414815菜就多练，输不起就别玩。
--《古希腊哲学》