第一次尝试打\(AtCoder\)，考前紧张刺激地对着\(google\)学日语，不过真正到了开考了还是英语读起来比较靠谱。
\(Beginner\)的比赛还是比较水的，我涨了\(400pts\)，似乎是\(Beginner\)能涨到的最高分了？不太清楚。
\(ABC113 A – Discount Fare\)
打卡题，没什么可说的。
\(ABC113 B – Palace\)
大力模拟即可。
\(ABC113 C – ID\)
排序。善用STL可以高效得分。
\(ABC113 D – Number of Amidakuji\)
一道有一定难度的DP题。
\(f_{i,j}\)表示，走到\(f_{i,j}\)并用完横杠的方案数。
然后我们可以发现，这种方案数是可以直接计算出来的——具体来说要乘上一个斐波那契数。这是因为放置东西的时候不能同行。
可以类比爬楼梯问题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 A - Discount Fare
*/
long long x,y;
void init(){
scanf("%lld%lld",&x,&y);
printf("%lld",x+(y>>1));
}
int main(){
init();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 B - Palace
*/
int n,loc[100005];
double t,a,h[100005];
inline double cmp(int a,int b){
return h[a]<h[b];
}
void init(){
scanf("%d",&n);
scanf("%lf%lf",&t,&a);
for(int i=1;i<=n;++i){
scanf("%lf",&h[i]);
h[i]=t-h[i]*0.006;
h[i]-=a;
h[i]=(h[i]<0)?(-h[i]):h[i];
loc[i]=i;
}
sort(loc+1,loc+1+n,cmp);
printf("%d",loc[1]);
}
int main(){
init();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 C - ID
*/
int n,m;
struct data{
int a;
int b;
int id;
}tl[100005];
vector<data> nl[100005];
inline bool cmp(const data &a,const data &b){
return a.b<b.b;
}
inline bool cmp2(const data &a,const data &b){
return a.id<b.id;
}
void init(){
scanf("%d%d",&n,&m);
int x,y;
data nw;
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
nw.b=y;
nw.id=i;
nw.a=x;
nl[x].push_back(nw);
}
for(int i=1;i<=n;++i){
sort(nl[i].begin(),nl[i].end(),cmp);
}
int tp=0;
for(int i=1;i<=n;++i){
for(int j=0;j<nl[i].size();++j){
nl[i][j].b=j+1;
tl[++tp]=nl[i][j];
}
}
sort(tl+1,tl+1+m,cmp2);
for(int i=1;i<=m;++i){
printf("%.6d%.6d\n",tl[i].a,tl[i].b);
}
}
int main(){
init();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
#define MOD 1000000007
/*
ABC113 D - Number of Amidakuji
*/
//w 棍子，k 列数。
long long h,w,k;
long long ans=0;
long long f[105][10];
long long fib[1005];
//Y取X的情况。
void init(){
scanf("%lld%lld%lld",&h,&w,&k);
memset(f,0,sizeof(f));
fib[1]=fib[2]=1;
for(int i=3;i<=1000;++i){
fib[i]=(fib[i-1]+fib[i-2])%MOD;
}
f[0][1]=1;
for(int i=1;i<=h;++i){
for(int j=1;j<=w;++j){
if(j>1){
f[i][j]=(f[i][j]+(f[i-1][j-1]*fib[w-j+1]*fib[j-1])%MOD)%MOD;
}
if(j<w){
f[i][j]=(f[i][j]+(f[i-1][j+1]*fib[w-j]*fib[j])%MOD)%MOD;
}
f[i][j]=(f[i][j]+(f[i-1][j]*fib[j]*fib[w-j+1])%MOD)%MOD;
}
}
printf("%lld",f[h][k]);
}
int main(){
init();
return 0;
}
