AtcoderSoundHound Inc.Contest解题报告

A

C++ Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
if(a+b==15)puts("+");
else if(a*b==15)puts("*");
else puts("x");
return 0;
}

B

C++ Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn=100000;
char str[maxn];
int main(){
int w;
scanf("%s",str);
scanf("%d",&w);
if(w==1){printf("%s",str);return 0;}
for(int i=0;i<strlen(str);i++){
if(i%w==0){
putchar(str[i]);
}
}
return 0;
}

C

这题画风突变啊喂

这题我比较SB打表没找出规律还是yjw学长点醒了我 $yjw$学长 $orz$

这题其实是个概率题,长度为$m$,则最多有$m-1$对数字,显然每一对之间是互相不影响的,于是我们先来研究一对数字的情况:

首先每个数字都有n个数字与之配对,总计$n × n$种情况,再考虑对答案做贡献的,假设那一对数字是$x,y (y>x)$,则能做贡献的情况有$n-d$种.当然我们这只是$x<y$的情况,所以共$2×(n-d)$种。当然$d==0$时,就无关大小,只有$(n-d)$种,这需要特判.

然后交上去还是$WA$了,发现强制类型转换写在括号外导致会爆$int$,比较坑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#define ri register int
using namespace std;
template <class T>void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int n,m,d;
int main(){
read(n),read(m),read(d);
if(d==0)printf("%.10Lf\n",(long double)(m-1)/n);
else if(n<=d)printf("0.0000000\n");
else printf("%.10Lf\n",(long double)(1.00*2*(n-d)*(m-1))/n/n);
return 0;
}

D

这题解法很有意思,比较考验智商

求两个最短路,一个是$s$到$x (x \in [1,n])$的用$yen$衡量的最短路$dis_1(s,x)$,一个是从$t$到$x (x \in [1,n])$的最短路$dis_2(t,x)$,用$snuuk$衡量的最短路

然后我们想,最后$n-1$年出发的时候只用$n$这个点可以交换货币,所以$val[n-1]=dis_1(s,n)+dis_2(t,n)$

再向下想,在$n-2$年出发时,要么继续到$n$这个点交换货币,要么到$n-1$这个点交换货币,以此类推得到

$val[p]=min(val[p+1],dis_1(s,p)+dis_2(t,p)) p \in [0,n-1]$

最后初始钱数$-val$值就是对应答案

E

我太菜不知道怎么做,等待咕咕咕的题解吧