Gym102174 (The 14-th BIT Campus Programming Contest)

落日映苍穹つ 2021-09-19 17:00 255阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>Sloved</th> 
   <th align="center">A</th> 
   <th align="center">B</th> 
   <th align="center">C</th> 
   <th align="center">D</th> 
   <th align="center">E</th> 
   <th align="center">F</th> 
   <th align="center">G</th> 
   <th align="center">H</th> 
   <th align="center">I</th> 
   <th align="center">J</th> 
   <th align="center">K</th> 
   <th align="center">L</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>7/12</td> 
   <td align="center">O</td> 
   <td align="center">.</td> 
   <td align="center">O</td> 
   <td align="center">.</td> 
   <td align="center">O</td> 
   <td align="center">O</td> 
   <td align="center">.</td> 
   <td align="center">O</td> 
   <td align="center">.</td> 
   <td align="center">O</td> 
   <td align="center">O</td> 
   <td align="center">.</td> 
  </tr> 
 </tbody> 
</table>

*  O for passing during the contest
 *  Ø for passing after the contest
 *  ! for attempted but failed
 *  · for having not attempted yet

## A.两只脑斧(firevolt,0:05,+1) ##

签到题，读题找规律即可

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 100005
    #define ll long long
    int t,n,m,k;
    string b;
    int main(){ 
        cin>>n;
        for(int i=1;i<=n;i++){ 
            cin>>b;
            if(b[0]=='0'){ 
                cout<<'X';
            }
            else if(b[0]=='1'||b[0]=='3'||b[0]=='5'){ 
                cout<<'E';
            }
            else
                cout<<'I';
        }
    }

## C 赛尔逵传说(firevolt,0:57,+3) ##

由于吃果实获得好攻击力和自身攻击力一样，所以吃一个果实相当于多攻击一次，即少被攻击一次，所以将果实全部用在攻击力高的怪物上即为最优解  
**爆int**

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 100005
    #define ll long long
    ll t,n,m,k;
    struct ac{ 
        ll x,y;
    }f[maxn];
    bool cmp(ac a,ac b){ 
        return a.y>b.y||(a.y==b.y&&a.x<b.x);
    }
    int main(){ 
        cin>>n>>k>>m;
        for(ll i=1;i<=n;i++){ 
            cin>>f[i].x>>f[i].y;
        }
        sort(f+1,f+1+n,cmp);
        ll z=0;
        for(ll i=1;i<=n;i++){ 
            ll zz=f[i].x/k;
            if(f[i].x%k==0)
                zz--;
            if(m>0&&zz>=1){ 
                if(m>=zz){ 
                    m-=zz;
                    continue;
                }
                else{ 
                    zz-=m;
                    m=0;
                }
            }
            z=z+zz*f[i].y;
        }
        cout<<z<<endl;
    }

## E 只有一端开口的瓶子(indiewar,01:57,+1) ##

考虑最多的情况只需要2个栈，这时形成了一个3个桩的汉诺塔，考虑特判只需要1的情况，比较好的做法是直接用一个栈模拟，如果成功那就只需要一个栈（废话）

#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 T,n;
    int a[maxn];
    int b[maxn];
    
    int main(int argc, char const *argv[])
    { 
        cin >> T;
        while(T--)
        { 
            cin >> n;
            rep(i,0,n)
            { 
                cin >> a[i];
            }
            stack<int> st;
            int t = 1;
            rep(i,0,n)
            { 
                st.push(a[i]);
                while(!st.empty() && st.top() == t)
                { 
                    t++;
                    st.pop();
                }
            }
            if(st.empty())
            { 
                cout << 1 << endl;
            }
            else
            { 
                cout << 2 << endl;
            }
        }
        return 0;
    }

## F风王之瞳(huhaowen,0:57,+1) ##

![O(n)][O_n]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 7;
    const int inf = 0x3f3f3f3f;
    const double pi = acos(-1.0);
    const double eps = 1e-6;
    ll n,m,t;
    int main()
    { 
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        scanf("%lld",&t);
        while(t--){ 
            scanf("%lld%lld",&n,&m);
            if(n > m) swap(n,m);
            ll ans = 0;
            for(int i = 1;i <= n;++i){ 
                ans += (n + 1 - i) * (m + 1 - i) * i;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

## H目标是成为数论大师(huhaowen,01:59,+9) ##

暴力枚举-1e5+7到1e5+7（其实5000应该就够了）判断定义域内满足的解  
之前只考虑了定义域，这个题目显然还有值域的约束

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 7;
    const int inf = 0x3f3f3f3f;
    const double pi = acos(-1.0);
    const double eps = 1e-6;
    ll n,m,t,a,b;
    ll s[N];
    int main()
    { 
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        scanf("%lld",&t);
        while(t--){ 
            ll cnt = 0;
            scanf("%lld%lld",&a,&b);
            for(int i = -N;i < N;++i){ 
                if(i < b) ;
                else if(a * i == (i - b) * (i - b)) s[cnt++] = i;
            }
            printf("%lld\n",cnt);
            for(int i = 0;i < cnt;++i) printf("%lld%c",s[i],i == cnt - 1 ? '\n' : ' ');
        }
        return 0;
    }

## J金色传说(indiewar,02:30,+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=998244353;
    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 = 5e5 + 1000;
    
    ll a[maxn],b[maxn];
    int n;
    int main(int argc, char const *argv[])
    { 
    	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	rep(i,1,maxn-100)
    	{ 
    		ll tem = powmod(10,i);
    		a[i] = (tem-1) * tem / 2 % mod;
    	}
    	b[1] = 10;
    	b[2] = 100;
    	rep(i,3,maxn-100)
    	{ 
    		b[i] = b[i-1] * 10  % mod + b[i-2] * 20 % mod;
    		b[i] %= mod;
    	}
    	int t;
    	cin >> t;
    	while(t--)
    	{ 
    		cin >> n;
    		ll ans = a[n];
    		rep(i,1,n-1)//1 -> n-2
    		{ 
    			ans += (a[i] * 2 * b[n-i-1] % mod)%mod;
    			ans %= mod;
    		}
    		cout << ans << endl;
    	}
    	return 0;
    }

## K多项式求导(indiewar,0:21,+1) ##

模拟求导过程即可，比较好写的方法是从前往后更新

#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=998244353 ;
    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 = 110;
    
    
    ll n,k;
    ll a[maxn];
    
    int main(int argc, char const *argv[])
    { 
    	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	cin >> n >> k;
    
    	per(i,0,n+1)
    	{ 
    		cin >> a[i];
    		//a[i] = a[i] % mod * i % mod;
    	}
    	rep(i,0,k)
    	{ 
    		rep(j,0,n+1)
    		a[j] = a[j+1] % mod * (j+1) % mod;
    	}
    	cout << 0;
    	per(i,0,n)
    	cout << " " << a[i];
    	cout << endl;
    	return 0;
    }

[O_n]: /images/20210907/cdff60abd2d94ba3b129ff273f9df617.png