qsmy_41

阅读量

218

+关注发消息

离线：21小时前

qsmy_41
1天前

                #include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n, m, p[N], num[N];
int a, b;

int find(int a) {
    if (p[a]!=a) p[a]=find(p[a]);
    return p[a];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for (int i=1; i<=n; i++) num[i]=1, p[i]=i;
    while (m--) {
        string s;
        cin>>s;
        if (s=="C") {
            cin>>a>>b;
            if (find(a)==find(b)) continue;
            num[find(b)]+=num[find(a)];
            p[find(a)]=find(b);
        } else if (s=="Q1") {
            cin>>a>>b;
            cout<<(find(a)==find(b)?"Yes":"No")<<'\n';
        } else {
            cin>>a;
            cout<<num[find(a)]<<'\n';
        }
    }
    return 0;
}

            

活动打卡代码 AcWing 836. 合并集合

qsmy_41
1天前

                #include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n, m, p[N];
char c;
int a, b;

int find(int x) {
    if (p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for (int i=1; i<=n; i++) p[i]=i;
    while (m--) {
        cin>>c>>a>>b;
        if (c=='M') p[find(a)]=find(b);
        else {
            if (find(a)==find(b)) cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
    return 0;
}

            

活动打卡代码 AcWing 143. 最大异或对

qsmy_41
1天前

                #include <bits/stdc++.h>
using namespace std;
const int N=31e5+10;
int n, son[N][2], idx;

void insert(int x) {
    int p=0;
    for (int i=30; i>=0; i--) {
        int u=x>>i&1;
        if (!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
}

int query(int x) {
    int p=0, res=0;
    for (int i=30; i>=0; i--) {
        int u=x>>i&1;
        if (son[p][!u]) {
            res=res*2+!u;
            p=son[p][!u];
        } else {
            res=res*2+u;
            p=son[p][u];
        }
    }
    return res;
}

int main() {
    cin>>n;
    int res=0;
    for (int i=0; i<n; i++) {
        int m;
        cin>>m;
        insert(m);
        res=max(res, query(m)^m);
    }
    cout<<res;
}

            

活动打卡代码 AcWing 835. Trie字符串统计

qsmy_41
1天前

                #include <bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n, cnt[N], son[N][26], idx;

void insert(string s) {
    int p=0;
    for (auto c:s) {
        if (!son[p][c-'a']) son[p][c-'a']=++idx;
        p=son[p][c-'a'];
    }
    cnt[p]++;
}

int query(string s) {
    int p=0;
    for (auto c:s) {
        if (!son[p][c-'a']) return false;
        p=son[p][c-'a'];
    }
    return cnt[p];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    while (n--) {
        char c;
        cin>>c;
        string s;
        cin>>s;
        if (c=='I') insert(s);
        else cout<<query(s)<<'\n';
    }
    return 0;
}

            

活动打卡代码 AcWing 680. 剪绳子

qsmy_41
2天前

                #include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n, m, a[N];

bool check(double x) {
    int total=0;
    for (int i=0; i<n; i++) total+=a[i]/x;
    return total<m;
}

int main() {
    cin>>n>>m;
    for (int i=0; i<n; i++) cin>>a[i];
    double l=0, r=1e9;
    while (r-l>1e-5) {
        double mid=(l+r)/2;
        if (check(mid)) r=mid;
        else l=mid;
    }
    printf("%.2f", l);
}

            

题解 AcWing 124. 数的进制转换（队列）

qsmy_41
2天前

题目描述

编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。

这里有62个不同数位{0-9,A-Z,a-z}。

输入格式

第一行输入一个整数，代表接下来的行数。

接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。

输入进制和输出进制都在2到62的范围之内。

（在十进制下）A = 10，B = 11，…，Z = 35，a = 36，b = 37，…，z = 61 (0-9仍然表示0-9)。

输出格式

对于每一组进制转换，程序的输出都由三行构成。

第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。

第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。

第三行为空白行。

同一行内数字用空格隔开。

输入样例

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

输出样例

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

使用队列而非vector版

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int numq[N], resq[N];
int hh, tt;

int main() {
    int T;
    cin>>T;
    while (T--) {
        int a, b;
        string a_string, b_string;
        cin>>a>>b>>a_string;

        hh=0, tt=-1;
        for (auto c:a_string) {
            if (c>='0' && c<='9') numq[++tt]=c-'0';
            else if (c>='A' && c<='Z') numq[++tt]=c-'A'+10;
            else numq[++tt]=c-'a'+36;
        }

        int hh2=0, tt2=-1;
        while (hh<=tt) {
            int r=0;
            for (int i=hh; i<=tt; i++) {
                numq[i]+=r*a;
                r=numq[i]%b;
                numq[i]/=b;
            }
            resq[++tt2]=r;
            while (hh<=tt && numq[hh]==0) hh++;
        }

        reverse(resq+hh2, resq+tt2+1);
        for (int i=hh2; i<=tt2; i++) {
            if (resq[i]<10) b_string+=(char) resq[i]+'0';
            else if (resq[i]<36) b_string+=(char) resq[i]-10+'A';
            else b_string+=(char) resq[i]-36+'a';
        }
        cout<<a<<' '<<a_string<<'\n'<<b<<' '<<b_string<<'\n'<<'\n';
    }
    return 0;
}

活动打卡代码 AcWing 1346. 回文平方

qsmy_41
3天前

原来的冗长的实现。。。

#include <bits/stdc++.h>
using namespace std;
const int N=300;
unordered_map<int, char> M={
    {0,'0'},
    {1,'1'},
    {2,'2'},
    {3,'3'},
    {4,'4'},
    {5,'5'},
    {6,'6'},
    {7,'7'},
    {8,'8'},
    {9,'9'},
    {10,'A'},
    {11,'B'},
    {12,'C'},
    {13,'D'},
    {14,'E'},
    {15,'F'},
    {16,'G'},
    {17,'H'},
    {18,'I'},
    {19,'J'}
};

bool check_palin(vector<char> s) {
    for (int i=0, j=s.size()-1; i<j; i++, j--) {
        if (s[i]!=s[j]) return false;
    }
    return true;
}

vector<char> convert(int n, int b) {
    vector<char> s;
    while (n) {
        s.push_back(M[n%b]);
        n/=b;
    }
    reverse(s.begin(), s.end());
    return s;
}

void pr(vector<char> &s) {
    for (int i=0; i<s.size(); i++) cout<<s[i];
}

int main() {
    int b;
    cin>>b;
    for (int i=1; i<=N; i++) {
        int n=i*i;
        auto s=convert(n, b);
        if (check_palin(s)) {
            auto s1=convert(i, b);
            pr(s1);
            cout<<' ';
            pr(s);
            cout<<'\n';
        }
    }
    return 0;
}

精简！

#include <bits/stdc++.h>
using namespace std;
int n;

char get(int n) {
    if (n<10) return n+'0';
    return n-10+'A';
}

string base(int n, int i) {
    string s;
    while (i) {
        s+=get(i%n);
        i/=n;
    }
    reverse(s.begin(), s.end());
    return s;
}

bool check(string s) {
    for (int i=0, j=s.size()-1; i<j; i++, j--) {
        if (s[i]!=s[j]) return false;
    }
    return true;
}

int main() {
    cin>>n;
    for (int i=1; i<=300; i++) {
        auto s=base(n, i*i);
        if (check(s)) cout<<base(n, i)<<' '<<s<<'\n';
    }
    return 0;
}

再转换回去！

#include <bits/stdc++.h>
using namespace std;
int n;

char get(int n) {
    if (n<10) return n+'0';
    return n-10+'A';
}

string base(int n, int i) {
    string s;
    while (i) {
        s+=get(i%n);
        i/=n;
    }
    reverse(s.begin(), s.end());
    return s;
}

bool check(string s) {
    for (int i=0, j=s.size()-1; i<j; i++, j--) {
        if (s[i]!=s[j]) return false;
    }
    return true;
}

int uget(char c) {
    if (c-'0'<10) return c-'0';
    return c-'A'+10;
}

int revert(string s) {
    int res=0;
    for (int i=0; i<s.size(); i++) {
        res=res*10+uget(s[i]);
    }
    return res;
}

int main() {
    cin>>n;
    for (int i=1; i<=300; i++) {
        auto s=base(n, i*i);
        cout<<i<<' '<<revert(s)<<endl;
        // if (check(s)) cout<<base(n, i)<<' '<<s<<'\n';
    }
    return 0;
}

活动打卡代码 AcWing 1113. 红与黑

qsmy_41
3天前

bfs

#include <bits/stdc++.h>
using namespace std;
const int N=25;
int w, h, tt, hh;
char g[N][N];
pair<int,int> q[N*N];
int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

int bfs(int x, int y) {
    hh=0, tt=0, q[0]={x, y};
    int res=0;
    g[y][x]='#';
    while (hh<=tt) {
        res++;
        auto cur=q[hh++];
        for (int i=0; i<4; i++) {
            int a=cur.first+dx[i], b=cur.second+dy[i];
            if (a>=0 && a<w && b>=0 && b<h && g[b][a]=='.') {
                g[b][a]='#';
                q[++tt]={a, b};
            }
        }
    }
    return res;
}

int main() {
    while (cin>>w>>h, w||h) {
        int x, y;
        for (int i=0; i<h; i++) for (int j=0; j<w; j++) {
            cin>>g[i][j];
            if (g[i][j]=='@') x=j, y=i;
        }
        cout<<bfs(x, y)<<endl;
    }
    return 0;
}

dfs

#include <bits/stdc++.h>
using namespace std;
const int N=25;
int w, h;
char g[N][N];
int dx[]={1, 0, -1, 0}, dy[]={0, -1, 0, 1};

int dfs(int x, int y) {
    int res=1;
    g[y][x]='#';
    for (int i=0; i<4; i++) {
        int a=x+dx[i], b=y+dy[i];
        if (a>=0 && a<w && b>=0 && b<h && g[b][a]=='.') res+=dfs(a, b);
    }
    return res;
}

int main() {
    while (cin>>w>>h, w||h) {
        int x, y;
        for (int i=0; i<h; i++) for (int j=0; j<w; j++) {
            cin>>g[i][j];
            if (g[i][j]=='@') x=j, y=i;
        }
        cout<<dfs(x, y)<<'\n';
    }
    return 0;
}

题解 AcWing 1000. 动物园

qsmy_41
4天前

题目:1000.动物园

近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。

为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

某天，园长给动物们讲解KMP算法。

园长：“对于一个字符串$S$，它的长度为$L$。我们可以在$O(L)$的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？”

熊猫：“对于字符串$S$的前$i$个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作next[i]。”

园长：“非常好！那你能举个例子吗？”

熊猫：“例$S$为abcababc，则next[5]=2。因为$S$的前5个字符为abcab，ab既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出next[1]=next[2]=next[3]=0，next[4]=next[6]=1，next[7]=2，next[8]=3。”

园长表扬了认真预习的熊猫同学。

随后，他详细讲解了如何在$O(L)$的时间内求出next数组。

下课前，园长提出了一个问题：“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串$S$的前$i$个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。例如$S$为aaaaa，则num[4]=2。这是因为S的前4个字符为aaaa，其中a和aa都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，num[1]=0,num[2]=num[3]=1,num[5]=2。”

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。

听了这句话，睡了一节课的企鹅立刻就醒过来了！

但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。

你能否帮助企鹅写一个程序求出num数组呢？

特别地，为了避免大量的输出，你不需要输出num[i]分别是多少，你只需要输出
$$\Pi_{i=1}^L (\texttt{num[i]}+1)$$
对1,000,000,007取模的结果即可。

输入格式

第1行仅包含一个正整数$n$ ，表示测试数据的组数。

随后$n$行，每行描述一组测试数据。每组测试数据仅含有一个字符串S，S的定义详见题目描述。

数据保证$S$中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。

输出格式

包含$n$行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。

对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对1,000,000,007取模的结果。

输出文件中不应包含多余的空行。

输入样例：

3
aaaaa
ab
abcababc

输出样例：

36
1
32

算法

这题利用KMP得出$O(n)$的解法。

首先，不考虑前缀和后缀不重叠的情况，先考虑$S$的每一个子字符串$S[1\sim i]$所能形成的相同前后缀的数量$cnt[i]$，这个表达式是

$$cnt[i]=cnt[ne[i]]+1.$$

我们来看一个例子来说明。比如aasdaa。很容易可以理解，cnt[2]=2。注意，字符串本身就是一个相同长度的前缀和后缀，所以是2。我们再来看cnt[6]。本身通过kmp能够得到ne[6]=3，所以肯定起码一种前后缀。另外，对于aa这个前/后缀本身，我们可以把它拆开来，再形成一组前后缀，那么又多了一个，所以cnt[6]=4。同理，对于aaaasdaaaa，那么cnt[10]=5。

其次，这时候再考虑前后缀不重叠的情况。和cnt不同的地方在于，对于cnt来说只要一层ne[i]的嵌套，但是在找num[i]的时候，我们需要多次嵌套ne[i]来找到一个值使得前后缀不重复。所以我们再另用一个指针k来首先找前后缀的尺寸，然后如果有重叠的话，再利用ne数组对前后缀的长度缩短，最后找到合适的前后缀长度，及其对应的cnt值。

这个算法精髓的地方在于，在找num的值的时候，也是利用了类似kmp的方式，即用ne往回走，由此把时间复杂度控制在了$O(n)$，$n$为字符串的长度。

参考文献

博客文章

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+10, mod=1e9+7;
ll n, ne[N], cnt[N];
char s[N];

int main() {
    cin>>n;
    while (n--) {
        fill(cnt, cnt+N, 0);
        fill(ne, ne+N, 0);
        cin>>s+1;
        ll res=1;
        cnt[1]=1;
        for (int i=2, j=0, k=0; s[i]; i++) {
            while (j && s[i]!=s[j+1]) j=ne[j];
            if (s[i]==s[j+1]) j++;
            ne[i]=j;

            cnt[i]=cnt[j]+1;
            while (k && s[i]!=s[k+1]) k=ne[k];
            if (s[i]==s[k+1]) k++;
            while (k<<1>i) k=ne[k]; 
            res=res*(cnt[k]+1)%mod;
        }
        cout<<res<<'\n';
    }
}

活动打卡代码 AcWing 831. KMP字符串

qsmy_41
4天前

                #include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;
int n, m, ne[N];
char p[N], s[N];

int main() {
    cin>>n>>p+1>>m>>s+1;
    for (int i=2, j=0; i<=n; i++) {
        while (j && p[i]!=p[j+1]) j=ne[j];
        if (p[i]==p[j+1]) j++;
        ne[i]=j;
    }
    for (int i=1, j=0; i<=m; i++) {
        while (j && p[j+1]!=s[i]) j=ne[j];
        if (s[i]==p[j+1]) j++;
        if (n==j) {
            j=ne[j];
            cout<<i-n<<' ';
        }
    }
    return 0;
}

            

0 评论

0 评论

0 评论

0 评论

0 评论

题目描述

输入格式

输出格式

输入样例

输出样例

0 评论

0 评论

0 评论

题目:1000.动物园

输入格式

输出格式

输入样例：

输出样例：

算法

参考文献

C++ 代码

0 评论

0 评论