文章目錄

• • A B-Suffix Array
  • B Infinite Tree
  • C Domino
  • D Quadratic Form
  • E Counting Spanning Trees
  • F Infinite String Comparision
  • • 題意：
    • 題解：
    • 代碼：
  • G BaXianGuoHai, GeXianShenTong
  • H Minimum-cost Flow
  • I 1 or 2
  • J Easy Integration
  • • 題意
    • 題解
    • 代碼

2020牛客暑期多校訓(xùn)練營（第一場）

A B-Suffix Array

B Infinite Tree

C Domino

D Quadratic Form

E Counting Spanning Trees

F Infinite String Comparision

題意：

兩個字符串A和B，對AAAA…和BBBB…(字符串A和B無限重復(fù)）進(jìn)行比較，輸出 > = <

題解：

方法一：
字符串a(chǎn)和b從第一位開始比較，當(dāng)比到其中最后一位時再跳轉(zhuǎn)到第一位繼續(xù)。那什么時候算等于呢，我一開始想的是a和b的最小公倍數(shù)，這樣會超時，我們其實只需比較較長字符串的兩倍即可。因為如果兩個字符串不相等，那么在較長字符串的兩倍范圍內(nèi)必將可以必出大小關(guān)系
方法二：
很簡單，比較a+b和b+a的大小關(guān)系，直接輸出
如果a和b相等，那么a+b肯定==b+a,否則兩者肯定能必出大小

代碼：

方法一：

#include <iostream> #include <math.h> #include <stdlib.h> #include <cstring> #include <stdio.h> #include <queue> #include <algorithm> #include <vector> #include <map> #include <set> #include <string>#define MAX 1000010using namespace std;typedef long long ll;char a[MAX]; char b[MAX];int main(){while(~scanf("%s %s",a,b)){int la=strlen(a);int lb=strlen(b);ll l=max(la,lb)*2;int ia=0,ib=0;int flag=0;for(ll i=0;i<l;i++){if(a[ia]>b[ib]){printf(">\n");flag=1;break;}else if(a[ia]<b[ib]){printf("<\n");flag=-1;break;}else {ia++;ib++;if(ia==la)ia=0;if(ib==lb)ib=0;}}if(flag==0){printf("=\n");}}return 0; }

方法二：

#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector>using namespace std;using Int = long long;template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }char S[100010]; char T[100010];int main() {for (; ~scanf("%s%s", S, T); ) {const string s = S;const string t = T;const string st = s + t;const string ts = t + s;puts((st < ts) ? "<" : (st > ts) ? ">" : "=");}return 0; }

G BaXianGuoHai, GeXianShenTong

H Minimum-cost Flow

I 1 or 2

J Easy Integration

題意

對于一個n，求出的值，結(jié)果可以寫成p/q的形式，最后輸出 (p?q ^?1 )mod998244353 的值

題解

沃利斯公式

直接有公式，帶入計算就行

代碼

#include<bits/stdc++.h> using namespace std;const int manx=2e6+5; const int N=1e3+5; const int mod=998244353;ll dp[manx],n; ll poww(ll a, ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; } ll inv(ll x){return poww(x,mod-2); } int main() {dp[1]=1;for(int i=2;i<=2000005;i++) dp[i]=dp[i-1]*i%mod;while(cin>>n){ll ans=dp[n]*dp[n]%mod*inv(dp[2*n+1])%mod;cout<<ans<<endl;}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的2020牛客暑期多校训练营（第一场）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。