总体发挥还算正常
A - Jiro
呵呵呵，有人像我这么做的吗？
点击查看代码
#include<cstdio>
using namespace std;
int main()
{
char ab,ac,bc;
scanf("%c %c %c",&ab,&ac,&bc);
if(ab=='<'&&ac=='<'&&bc=='<') printf("B\n");
if(ab=='<'&&ac=='<'&&bc=='>') printf("C\n");
if(ab=='<'&&ac=='>'&&bc=='<') printf("O\n");
if(ab=='<'&&ac=='>'&&bc=='>') printf("A\n");
if(ab=='>'&&ac=='<'&&bc=='<') printf("A\n");
if(ab=='>'&&ac=='<'&&bc=='>') printf("O\n");
if(ab=='>'&&ac=='>'&&bc=='<') printf("C\n");
if(ab=='>'&&ac=='>'&&bc=='>') printf("B\n");
return 0;
}
B - Taro
太君！太郎
点击查看代码
#include<cstdio>
using namespace std;
const int N=105;
int n,m;
bool fam[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int num; char sex[5];
scanf("%d%s",&num,sex);
if(sex[0]=='M' && !fam[num])
{
fam[num]=true;
printf("Yes\n");
}
else printf("No\n");
}
return 0;
}
C - Make Isomorphic
暴力枚举所有对应关系即可（即枚举 \(G\) 中的点和 \(H\) 中点的对应关系）。
时间复杂度 \(O(N! \times N^2)\)。
运用各类 C++ 自带函数可以有效缩短代码长度
#include<cstdio>
#include<numeric>
#include<algorithm>
using namespace std;
const int N=10;
int n,c[N][N],ans=0x3f3f3f3f;
struct Graph{
int m;
bool a[N][N];
void read()
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y; scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=true;
}
return;
}
}g,h;
int order[N];
int main()
{
scanf("%d",&n);
g.read(),h.read();
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
scanf("%d",&c[i][j]);
c[j][i]=c[i][j];
}
iota(order+1,order+n+1,1);
do
{
int tmp=0;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
if(g.a[order[i]][order[j]]!=h.a[i][j])
tmp+=c[i][j];
ans=min(ans,tmp);
next_permutation(order+1,order+n+1);
}while(!is_sorted(order+1,order+n+1));
printf("%d\n",ans);
return 0;
}
D - 1D Country
很板，就是离散化（其实我也不知道我写的是不是离散化）
将位置和人数组合起来共同排序后记录前缀和。
询问区间 \([l,r]\) 的时候，使用 lower_bound、upper_bound（有效缩短代码长度并避免手打二分写挂）函数找到第一个大于等于 \(l\) 的位置和最后一个小于等于 \(r\) 的位置（就是找查询的左右边界卡在那些村庄之间），然后直接输出区间和即可。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,q,pos[N];
long long sum[N];
pair<int,int> village[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&village[i].first);
for(int i=1;i<=n;i++) scanf("%d",&village[i].second);
sort(village+1,village+n+1);
for(int i=1;i<=n;i++)
{
pos[i]=village[i].first;
sum[i]=sum[i-1]+village[i].second;
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int l,r; scanf("%d%d",&l,&r);
l=lower_bound(pos+1,pos+n+1,l)-pos;
r=upper_bound(pos+1,pos+n+1,r)-pos-1;
printf("%lld\n",sum[r]-sum[l-1]);
}
return 0;
}
E - I Hate Sigma Problems
动态规划题，总感觉在哪里见到过。
为了方便起见，这里用 \(F\) 表示题目中的 \(f\) 函数。
设 \(f_i\) 表示以 \(a_i\) 结尾的区间的 \(F\) 值之和，即：
\[f_i = \sum_{j=1}^{i} F(j,i) \]设 \(pos_k\) 表示 \(k\) 最后一次出现的位置，那么只有在区间左端点在 \([pos_{a_i}+1,i]\) 内时，\(a_i\) 才算一种新数，这一段中的每个左端点都可以额外有 \(1\) 的贡献，可以加到答案里面；反之，若左端点在 \([1,pos_{a_i}]\) 内，\(a_i\) 都不能算一种新数，不能额外算到答案里，这一部分的答案就是 \(f_{i-1}\)。
综上所述，共有 \(i-pos_{a_i}\) 个区间在多了 \(a_i\) 以后能每个多出 \(1\) 的贡献，其余所有区间在多出 \(a_i\) 以后贡献毫无变化。所以当前总贡献就等于上一个的贡献加上 \(i-pos_{a_i}\)，即：
\[f_i = f_{i-1} +(i - pos_{a_i}) \]最后的答案就是所有 \(f_i\) 的和。
看看我超短的代码
#include<cstdio>
using namespace std;
const int N=2e5+5;
int n,a[N],pos[N];
long long f[N],ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=f[i-1]+i-pos[a[i]];
ans+=f[i],pos[a[i]]=i;
}
printf("%lld\n",ans);
return 0;
}