月度归档： 2018年11月

第一次尝试打\(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;
}