AtCoder Beginner Contest 113-蒲公英云

AtCoder Beginner Contest 113

亦凉 2021-09-16 21:58 380阅读 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;
}