国产AⅤ无码一区二区三区_青青在线香蕉精品视频在线_2021年国产精品专区丝袜_久久青草费线频观看地址_亚洲A综合一区二区三区

世界熱推薦：AtCoder Beginner Contest 284（A~F）

2023-02-24 15:17:18來(lái)源：騰訊云

A - Sequence of Strings

Original Link

題目大意：

輸入 N個(gè)字符串，倒序輸出。

思想：


(資料圖)

簽到題。

代碼：

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)#define re register#define fi first#define se second#define endl "\n"typedef long long LL;typedef pair PII;typedef pair PLL;const int N = 1e6 + 3;const int INF = 0x3f3f3f3f, mod = 1e9 + 7;const double eps = 1e-6, PI = acos(-1);string s[N];void solve(){    int n; cin >> n;    for(int i = 0; i < n; i ++) cin >> s[i];    for(int i = n - 1; i >= 0; i --) cout << s[i] << endl;}int main(){    IOS;    int _ = 1;    // cin >> _;    while(_ --){        solve();    }    return 0;}

B - Multi Test Cases

Original Link

題目大意：

統(tǒng)計(jì)一組數(shù)中的奇數(shù)個(gè)數(shù)。

思想：

簽到題。

代碼：

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)#define re register#define fi first#define se second#define endl "\n"typedef long long LL;typedef pair PII;typedef pair PLL;const int N = 1e6 + 3;const int INF = 0x3f3f3f3f, mod = 1e9 + 7;const double eps = 1e-6, PI = acos(-1);void solve(){    int n; cin >> n;    int cnt = 0;    for(int i = 0; i < n; i ++){        int x; cin >> x;        if(x % 2 != 0) cnt ++;    }    cout << cnt << endl;}int main(){    IOS;    int _ = 1;    cin >> _;    while(_ --){        solve();    }    return 0;}

C - Count Connected Components

Original Link

題目大意：

給定一個(gè)無(wú)向圖。求連通塊數(shù)量。

思想：

并查集。

代碼：

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)#define re register#define fi first#define se second#define endl "\n"typedef long long LL;typedef pair PII;typedef pair PLL;// const int N = 1e6 + 3;const int INF = 0x3f3f3f3f, mod = 1e9 + 7;const double eps = 1e-6, PI = acos(-1);const int N = 500;int g[N]; int n, m;int cnt = 0;int find(int u){    if(g[u] != u) g[u] = find(g[u]);    return g[u];}void solve(){    cin >> n >> m;    for(int i = 1; i <= n; i ++) g[i] = i;  //初始化    for(int i = 1; i <= m; i ++){        int a, b; cin >> a >> b;        g[find(a)] = find(b);    }    for(int i = 1; i <= n; i ++){        if(g[i] == i) cnt ++;    }    cout << cnt << endl;}int main(){    IOS;    int _ = 1;    // cin >> _;    while(_ --){        solve();    }    return 0;}

D - Happy New Year 2023

Original Link

題目大意：

給定一個(gè)整數(shù) N。保證 N=p^2q，其中 p,q 均為質(zhì)數(shù)且 p\ne q。求滿足條件的 p,q。

思想：

算術(shù)基本定理：任何一個(gè)大于1的自然數(shù) N，如果 N 不為質(zhì)數(shù)，那么 N 可以唯一分解成有限個(gè)質(zhì)數(shù)的乘積 N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k}，且最多只有一個(gè)大于 \sqrt{n} 的質(zhì)因子。

法一：

可以選擇線性篩預(yù)處理素?cái)?shù)表，然后從小到大枚舉不超過(guò) \sqrt[3]{N} 的素?cái)?shù)判斷即可。

法二：

從 i=2 開始枚舉因子，當(dāng)枚舉到 N % i == 0 時(shí)，i 必為 N 的一個(gè)因子。則 i 不是 N 的質(zhì)因子 q 就是平方因子 q。當(dāng) (N / i) % i == 0 時(shí)，說(shuō)明 i 為平方因子 q，否則為質(zhì)因子 p。

代碼：

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)#define re register#define fi first#define se second#define endl "\n"typedef long long LL;typedef pair PII;typedef pair PLL;const int N = 1e6 + 3;const int INF = 0x3f3f3f3f, mod = 1e9 + 7;const double eps = 1e-6, PI = acos(-1);void solve(){    LL x; cin >> x;    for(LL i = 2; i < x ; i ++){        if(x % i == 0){            if((x / i) % i == 0) cout << i << " " << x / (i * i) << endl;            else cout << (LL)sqrtl(x / i) << " " << i << endl;            return ;        }    }}int main(){    IOS;    int _ = 1;    cin >> _;    while(_ --){        solve();    }    return 0;}

E - Count Simple Paths

Original Link

題目大意：

給定一個(gè) N 個(gè)頂點(diǎn)，M 條邊的無(wú)向圖。求從點(diǎn) 1 開始，簡(jiǎn)單路徑（沒(méi)有重復(fù)頂點(diǎn)的路徑）的數(shù)量 K。答案取 min(K, 1\times 10^6)。

思想：

圖的深度優(yōu)先遍歷。遇到可走的路徑，數(shù)量增加 1。超過(guò) 10^6 退出，

代碼：

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)#define re register#define fi first#define se second#define endl "\n"typedef long long LL;typedef pair PII;typedef pair PLL;const int N = 2e5 + 3;const int INF = 0x3f3f3f3f, mod = 1e9 + 7;const double eps = 1e-6, PI = acos(-1);vector g[N];bool vis[N];LL cnt = 0;void dfs(int u){    if(cnt > 1e6) return ;    vis[u] = 1;    cnt ++;    for(int i = 0; i < g[u].size(); i ++){        if(vis[g[u][i]]) continue;        vis[g[u][i]] = 1;        dfs(g[u][i]);        vis[g[u][i]] = 0;    }}void solve(){    int n, m; cin >> n >> m;    for(int i = 0; i < m; i ++){        int a, b; cin >> a >> b;        g[a].push_back(b);        g[b].push_back(a);    }    dfs(1);    cout << min(cnt, (LL)1000000) << endl;}int main(){    IOS;    int _ = 1;    // cin >> _;    while(_ --){        solve();    }    return 0;}

F - ABCBAC

Original Link

題目大意：

已知一個(gè)長(zhǎng)度為 N 的字符串 S 和一個(gè)整數(shù) i(0\le i \le N)。定義運(yùn)算 f_i(S) 鏈接的字符串如下： S 的前 i 個(gè)字符。 S 的翻轉(zhuǎn)。 S 的最后 (N-i) 個(gè)字符。 若 S = "abc", i = 2，則 現(xiàn)給出某個(gè)字符串 S 的長(zhǎng)度 N 和經(jīng)過(guò) f_i(S) 的結(jié)果。求原始字符串 S 和 i 的值。

思想：

字符串哈希。枚舉 i，判斷 1 \sim i 和 i + N + 1 \sim 2\times N 拼接成的字符串與 i + 1 \sim N + i 翻轉(zhuǎn)后的字符串是否相同即可。

代碼：

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)#define re register#define fi first#define se second#define endl "\n"typedef long long LL;typedef unsigned long long ULL;typedef pair PII;typedef pair PLL;// const int N = 1e6 + 3;// const int INF = 0x3f3f3f3f, mod = 1e9 + 7;const double eps = 1e-6, PI = acos(-1);const ULL N = 2e6 + 9;const int hash_cnt = 2; //哈希次數(shù)int n;string s;ULL Prime[] = {1998585857ul,23333333333ul};ULL base[] = {131, 146527, 19260817, 91815541}; // 字符集大小，進(jìn)制數(shù)ULL mod[] = {1000000007, 29123,998244353,1000000009,4294967291ull}; // 模數(shù)ULL h1[N][hash_cnt], h2[N][hash_cnt], p[N][hash_cnt];//初始化哈希void initHash(ULL n, ULL cnt){    p[0][cnt] = 1;    for(int i = 1; i <= n; ++ i) p[i][cnt] = p[i - 1][cnt] * base[cnt] % mod[cnt];    for(int i = 1; i <= n; ++ i) h1[i][cnt] = (h1[i - 1][cnt] * base[cnt] % mod[cnt] + s[i]) % mod[cnt]; // 正序hash    for(int i = n; i >= 1; -- i) h2[i][cnt] = (h2[i + 1][cnt] * base[cnt] % mod[cnt] + s[i]) % mod[cnt]; // 逆序hash}//正序HASHULL getHash1(ULL id, ULL l, ULL r){    return (h1[r][id] - h1[l - 1][id] * p[r - l + 1][id] % mod[id] + mod[id]) % mod[id];}//逆序HASHULL getHash2(ULL id, ULL l, ULL r){    return (h2[l][id] - h2[r + 1][id] * p[r - l + 1][id] % mod[id] + mod[id]) % mod[id];}//判斷區(qū)間正逆序是否相等，如果區(qū)間正逆序哈希值一樣，則回文；bool isRe(ULL id, ULL l,ULL r){    return getHash1(id, l, r) == getHash2(id, l, r);}void solve(){    cin >> n >> s;    s = " " + s;    initHash(2 * n, 0);    for(int i = 0; i <= n; i ++ ){        ULL sum1 = ((getHash1(0, 1, i) * p[n - i][0] % mod[0] + getHash1(0, n + i + 1, 2 * n)) % mod[0]);        ULL sum2 = getHash2(0, i + 1, n + i);        if(sum1 == sum2){            string st = s.substr(i + 1, n);            reverse(st.begin(), st.end());            cout << st << endl;            cout << i << endl;            return;        }    }    cout << -1 << endl;}int main(){    IOS;    int _ = 1;    // cin >> _;    while(_ --){        solve();    }    return 0;}

關(guān)鍵詞： 編程算法

[ 相關(guān)文章 ]

[ 相關(guān)新聞 ]