AtCoder Beginner Contest 113

亦凉 2021-09-16 21:58 217阅读 0赞

## [A - Discount Fare][] ##

z = x + y / 2 z = x + y / 2 z=x\+y/2

include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
     
    int x,y,z;
    int main()
    { 
    	while(scanf("%d%d",&x,&y)!=EOF)
    	{ 
    		z = y / 2 + x;
    		cout<<z<<endl;
    	}
    }

## [B - Palace][] ##

比较**差值的绝对值的大小**

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
     
    int n,T,a;
    struct node 
     { 
     	ll tt;
     	int id;
     }t[2110];
     
     bool cmp(node a,node b)
     { 
     	return a.tt <= b.tt;
     }
    int x;
    int main()
    { 
    	while(scanf("%d",&n)!=EOF)
    	{ 
    		cin>>T>>a;
    		a *= 1000;
    		rep(i,0,n)
    		{ 
    			cin>>x;
    			t[i].tt = 1000 * T - x * 6;
    			t[i].tt = abs(a - t[i].tt);  
    			t[i].id = i+1;
    		}
    		sort(t,t+n,cmp);
    		cout<<t[0].id<<endl;
    	}
    }

## [C - ID][] ##

先整个进行时间的排序，再遍历一遍

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    const int maxn = 1e5+1000;
     
     
    int n,m,a;
    struct node 
     { 
     	ll tt;
     	int pp;
     	int id;
     } t[maxn];
     
     bool cmp(node a,node b)
     { 
     	return a.tt <= b.tt;
     }
    ll p,y;
     
    int s[maxn];
    int pre[maxn];
    int  en[maxn];
    int main()
    { 
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{ 
    		memset(s,0,sizeof s);
    		rep(i,0,m)
    		{ 
    			cin>>p>>y;
    			t[i].tt = y; 
    			t[i].pp = p;
    			t[i].id = i;
    		}
    		sort(t,t+m,cmp);
    		rep(i,0,m)
    		{ 
    			pre[t[i].id] = t[i].pp;
    			en[t[i].id] = ++s[t[i].pp]; 
    		}
    		rep(i,0,m)
    		{ 
    			printf("%06d%06d\n",pre[i],en[i]);
    		}
     
    	}
    }

## [D - Number of Amidakuji][] ##

注意题目中K代表的意义，K是指从左边开始沿着边走最后到达的第几根，**注意可以往回走**（可以看第四个样例第一个介绍）

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
     
    int h,w,k;
    ll dp[1000][110];
    int s[] = { 1,1,2,3,5,8,13,21};
     
    int main(int argc, char const *argv[])
    { 
    	cin>>h>>w>>k;
    	if(w == 1)
    		{ 
    			printf("1\n");
    			return 0;
    		}
    	dp[0][0] = 1;
    	rep(i,0,h)
    		rep(j,0,w)
    		{ 
    			dp[i][j] %= mod;
    			if(j == 0)
    			{ 
    				dp[i+1][j+1] += dp[i][j] * s[max(0,w - j - 2)];
    				dp[i+1][j] += dp[i][j] * s[w - j - 1];
    			}
    			else if(j != 0)
    			{ 
    				dp[i+1][j+1] += dp[i][j] * s[j] * s[max(0,w - j - 2)];
    				dp[i+1][j] += dp[i][j] * s[j] * s[w - j - 1];
    				dp[i+1][j-1] += dp[i][j] * s[max(0,j-1)] * s[w-j-1];
    			}
    		}		
    	cout<<dp[h][k-1]%mod<<endl;	
    	return 0;
    }

[A - Discount Fare]: https://abc113.contest.atcoder.jp/tasks/abc113_a
[B - Palace]: https://abc113.contest.atcoder.jp/tasks/abc113_b
[C - ID]: https://abc113.contest.atcoder.jp/tasks/abc113_c
[D - Number of Amidakuji]: https://abc113.contest.atcoder.jp/tasks/abc113_d