A. Two Friends
一共只有两种情况：
- 存在 \(A\) 的最好朋友是 \(B\) 且 \(B\) 的最好朋友是 \(A\) 的情况：此时只需邀请这两个人即可。
- 不存在上述情况：设某个人 \(A\) 的最好朋友是 \(B\)，\(B\) 的最好朋友是 \(C\),这时邀请 \(A,B,C\) 三个人就可使 \(A,B\) 到场。
根据上述两种情况分别输出 \(2\) 和 \(3\) 即可。
#include<cstdio>
using namespace std;
const int N=55;
int n,p[N];
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
bool flag=false;
for(int i=1;i<=n;i++)
if(i==p[p[i]]) {flag=true; break;}
printf("%d\n",flag?2:3);
}
return 0;
}
B. Shifts and Sorting
贪心，每次循环移动一截连续的 \(1\) 串，串的长度 \(+1\) 就是这次操作的代价。
这样不断右移 \(1\)，最后可使 \(1\) 全部集中在右部。
代码中忽略了开头连续的 \(0\)，把一列连续的 \(1\) 和一列连续的 \(0\) 分为一组（例如 11100 这种为一组），这个串所耗的代价就是 \((0\) 的数量 \()\) \(\times\) \((\) 当前总共 \(1\) 的数量 \(+1)\)，每次计算前都把这一组 \(1\) 的数量累加到总共 \(1\) 的数量里去。
赛时没开 long long 还 WA 了一发。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n; char s[N];
int cnt[N][3],idx;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
{
if(s[i]=='0' && !idx) continue;
if(s[i]!=s[i-1] && s[i]=='1') idx++;
cnt[idx][s[i]-'0']++;
}
long long ans=0,len=0;
for(int i=1;i<=idx;i++)
{
len+=cnt[i][1];
ans+=1ll*cnt[i][0]*(len+1);
}
printf("%lld\n",ans);
for(int i=1;i<=idx;i++)
cnt[i][0]=cnt[i][1]=0;
idx=0;
}
return 0;
}