桂林电子科技大学第三届ACM程序设计竞赛

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 5.5k 阅读时长 ≈ 5 分钟

比赛链接

A,串串

不会写

B，重复

查重，直接set就完事了,然后求长度就ok了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;

int main()
{
    ll n,m;
    cin>>n>>m;
    string str[n];
    for(ll i=0;i<n;i++){
        cin>>str[i];
    }
    set<string>map(str,str+n);
    cout<<map.size()<<endl;
    return 0;
}

C，二元

思路： 暂无

二元： 暂无

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;
const int maxn=1e5+50;
int n,k;
struct T{
    int a,b;
}p[maxn<<2];
priority_queue<int,vector<int>,greater<int>>q;
bool cmp(const T &a,const T &b)
{
    return a.a>b.a;
}

int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>p[i].a>>p[i].b;
    sort(p,p+n,cmp);
    for(int i=0;i<k;i++) q.push(p[i].b);
    int ans=q.top()+p[k-1].a;
    for(int i=k;i<n;i++){
        q.pop();
        q.push(p[i].b);
        ans=max(ans,p[i].a+q.top());
    }
    cout<<ans<<endl;
    return 0;
}

D，查找

树，

不会

E，区间

直接模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;
const int maxn=1000+10;
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[maxn];
        int l=1,min=1;;
        int cnt=0,max=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        for(int i=1;i<n;i++){
            if(a[i-1]<=a[i]){
                cnt++;
                if(cnt>max){
                    l=min;
                    max=cnt;
                }
            }
            else {
                min=i+1;
                cnt=0;
            }
        }
        printf("%d %d\n",l,l+max);
    }
    return 0;
}

F，点对

有相图，连通性

定义一个大数组，M [a] [b] == 1 && M[b] [a]==1 成立时， ans++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;
const int maxn=310;
int n,m;
int M[maxn][maxn];

int main()
{
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++){
        cin>>u>>v;
        M[u][v]=1;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(M[i][k]==1&&M[k][j]==1)
                    M[i][j]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(M[i][j] && M[j][i]) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

G，路径

没写

H，分离

模拟就完事了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define ll long long
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--){
        string str;
        vector<char>m;
        cin>>str;
        m.push_back(str[0]);
        for(int i=1;i<str.size();i++){
            if(i%2==0) m.push_back(str[i]);
        }
        for(int i=0;i<m.size();i++){
            cout<<m[i];
        }
        cout<<endl;
    }
    return 0;
}

I，选择

还没写

J，相聚

连通性问题，只要找到1，就dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;
const int maxn=50+10;
char str[maxn][maxn];
int n,m;
int dir[][2]={{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y)
{
    str[x][y]='0';//注意
    if(x<0||x>n||y<0||y>m) return;//结束条件
    else {
        for(int i=0;i<4;i++){
            int dx=x+dir[i][0];
            int dy=y+dir[i][1];
            if(str[dx][dy]=='1')
                dfs(dx,dy);
        }
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        int ans=0;
        memset(str, '0',sizeof(str));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>str[i][j];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(str[i][j]=='1'){
                    dfs(i,j);
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}