大连大学程序设计竞赛(2023.4)热身赛题解

1154 字
|
23 分钟


题面下载：http://dluacm.cn/wp-content/uploads/2023/04/202304reshen.pdf

A.老人与海

题目大意：一个有向无环图，删除一些边，使得图联通情况下的拓扑序最小。

考虑贪心，依次考虑$ 1-n $每个位置对应的点的编号。

假设我们前$i-1$位置选择的集合为$S$，对于第$i$个位置，我们从小到大考虑所有不在$S$中的点，如果点$k$放在位置$i$有合法的删边方案，那么拓扑序的第$i$位即为$k$。

判断点$k$是否合法：

考虑维护图中所有的合法边相连的点集，如果整张图通过合法边联通，那么点$k$合法。

由于集合$S$中的每个点在拓扑序的位置已经确定，我们用$rnk[i]$表示点$i$的拓扑序，那么有三类不合法边${x>y}$：

（1）$x$和$y$的拓扑序都已经确定，且$rnk[x]>rnk[y]$

（2）$x$的拓扑序未确定，$y$的拓扑序已确定

（3）$y=k$，且$x>y$

将合法边用并查集维护，判断整张图的连通性。

时间复杂度为$O(n^2m)$，实际上加了剪枝后跑不到这个上限。

#include<bits/stdc++.h>
using namespace std ;
const int N = 1005, M = 100005 ;
int n, m ;
int fa[N] ;
vector<pair<int,int>> g ;
int pos[N], rnk[N] ;
bool used[N] ;
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]) ; }
int main()
{
    scanf("%d%d", &n, &m) ;
    for(int i=1;i<=m;++i)
    {
        int x, y ; scanf("%d%d", &x, &y) ;
        g.push_back({x, y}) ;
    }
    // vector<int> ans(n + 1) ;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;j++) if(!used[j])
        {
            for(int k=1;k<=n;k++) fa[k] = k ;
            int cnt = 0 ;
            pos[i] = j ; rnk[j] = i ;
            for(auto [x, y] : g)
            {
                if(!rnk[x] && rnk[y] || rnk[x] && rnk[y] && rnk[x] > rnk[y])
                {
                    continue ;
                }
                else
                {
                    int l = get(x), r = get(y) ;
                    if(l != r) fa[r] = l, cnt ++ ;
                }
            }
            // printf("%d %d %d\n", i, j, cnt) ;
            if(cnt == n - 1) { used[j] = 1 ; break ; }
            else rnk[j] = 0 ;
        }
    }
    for(int i=1;i<=n;++i) printf("%d%c", pos[i], i == n ? '\n' : ' ') ;
    return 0 ;
}

B.百年孤独

因为“化学反应”一定会发生，所以我们只需要判断一个里面有a，另一个里面有u即可。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#include <regex>
#include <list>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
using namespace std;
int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        string s1,s2;
        cin>>s1>>s2;
        if((s1.find('a')!=s1.npos||s1.find('A')!=s1.npos)&&(s2.find('u')!=s2.npos||s2.find('U')!=s2.npos)){
           cout<<"Yes" <<endl;
        }
        else if((s1.find('u')!=s1.npos||s1.find('U')!=s1.npos)&&(s2.find('a')!=s2.npos||s2.find('A')!=s1.npos)){
            cout<<"Yes" <<endl;
        }
        else cout<<"No"<<endl;

    }
    return 0;
}

C.孤星泪



推论：当A与C不连通时，我们无需放置。最多需要放置两个路障。即放在起点或终点的两侧。

我们将四个边进行编号，可以发现，按照12，13，24，34连接两面墙，可以阻止A到达C。

我们可以进行三次dfs。

第一次：判断AC是否连通。

第二次：按照连接的墙壁编号，为连接到不同墙壁的路障染色。

第三次：搜索所有已经染色的墙，如果和他距离为2有其他已经染色的墙，并且可以构成12，13，24，34四种组合的任意之一，则输出1。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#include <regex>
#include <list>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0

#define linf 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
using namespace std;
struct point {
    int x, y;
    point() {};
    point(int _x, int _y) : x(_x), y(_y) {};
    bool operator < (const point a) {
        return a.x < x;
    }
    friend istream& operator >>(istream& in, point& a) {
        in >> a.x >> a.y;
        return in;
    }
    friend ostream& operator <<(ostream& out, point& a) {
        out << a.x << " " << a.y;
        return out;
    }
};
ll power(ll x, ll power, ll mod) {
    x %= mod;
    ll ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
        if (power & 1) (ans *= x) %= mod;
    return ans;
}
struct node {
    ll sec;
    ll x;
    ll y;
    bool operator < (const node& a) const {
        if (sec == a.sec && x == a.x) return y < a.y;
        if (sec == a.sec) return x < a.x;
        return sec < a.sec;
    }
};
string s[5005];
bool vis[5005][5005];
int n;
bool check(int i, int j) {
    if (i < 0 || j < 0 || i >= n || j >= n) return 0;
    if (vis[i][j] == 1) return 0;
    return 1;
}
bool check2(int i, int j) {
    if (i < 0 || j < 0 || i >= n || j >= n) return 0;
    return 1;
}
bool dfs1(int i, int j) {
    //cout << i << " " << j << endl;
    stack<pair<int, int>> p;
    p.push({ i,j });
    while (!p.empty()) {
        pair<int, int> t = p.top();
        p.pop();
        if (s[t.first][t.second] == 'C') return 1;
        if (check(t.first + 1, t.second) && s[t.first + 1][t.second] != 'X') {
            vis[t.first + 1][t.second] = 1;
            p.push({ t.first + 1,t.second });
        }
        if (check(t.first, t.second + 1) && s[t.first][t.second + 1] != 'X') {
            vis[t.first][t.second + 1] = 1;
            p.push({ t.first , t.second + 1 });
        }
        if (check(t.first - 1, t.second) && s[t.first - 1][t.second] != 'X') {
            vis[t.first - 1][t.second] = 1;
            p.push({ t.first - 1, t.second });
        }
        if (check(t.first, t.second - 1) && s[t.first][t.second - 1] != 'X') {
            vis[t.first][t.second - 1] = 1;
            p.push({ t.first , t.second - 1 });
        }
    }
    return 0;

}
pair<int, int> d[] = { {1,0} ,{0,1},{-1,0},{0,-1},{-1,-1},{1,1} ,{1,-1},{-1,1} };
void dfs2(int i, int j, int t) {
    s[i][j] = '0' + t;
    stack<pair<int, int>> p;
    p.push({ i,j });
    while (!p.empty()) {
        pair<int, int> q = p.top();
        s[q.first][q.second] = '0' + t;
        p.pop();
        for (int i = 0; i < 8; i++) {
            if (check(q.first + d[i].first, q.second+d[i].second) && 
                s[q.first + d[i].first][q.second + d[i].second] == 'X') {
                vis[q.first + d[i].first][q.second + d[i].second] = 1;
                p.push({ q.first + d[i].first,q.second + d[i].second });
            }
        }
    }
}
bool dfs3(int i, int j) {
    set<char> st;
    if (check2(i + 1, j)) st.insert(s[i + 1][j]);
    else st.insert('3');
    if (check2(i, j + 1)) st.insert(s[i][j + 1]);
    else st.insert('4');
    if (check2(i - 1, j)) st.insert(s[i - 1][j]);
    else st.insert('1');
    if (check2(i, j - 1)) st.insert(s[i][j - 1]);
    else st.insert('2');
    if (check2(i + 1, j - 1)) st.insert(s[i + 1][j - 1]);
    if (check2(i - 1, j + 1)) st.insert(s[i - 1][j + 1]);
    if (check2(i - 1, j - 1)) st.insert(s[i - 1][j - 1]);
    if (check2(i + 1, j + 1)) st.insert(s[i + 1][j + 1]);
    /*    if(st.size()!=0){
            for(auto i:st){
                cout<<i<<" ";
            }
            cout<<endl;
        }*/
    if (st.count('1') && (st.count('2') || st.count('3'))) return 1;
    if (st.count('2') && st.count('4')) return 1;
    if (st.count('3') && st.count('4')) return 1;
    return 0;
}
int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
     //freopen("D:\\C\\2.txt", "r", stdin);
    //freopen("D:\\C\\2.txt", "w", stdout);
    int T;
    cin >> T;
    while (T--) {

        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> s[i];
        }
        memset(vis, 0, sizeof vis);
        if (dfs1(0, 0) == 0) {
            cout << 0 << endl;
            continue;
        }
        //cout<<1<<endl;
        if (s[0][1] == 'X' || s[1][0] == 'X' || s[n - 2][n - 1] == 'X' || s[n - 1][n - 2] == 'X') {
            cout << 1 << endl;
            continue;
        }
        memset(vis, 0, sizeof vis);
        for (int i = 1; i < n; i++) {
            if (s[0][i] == 'X') dfs2(0, i, 1);
        }
        for (int i = 1; i < n; i++) {
            if (s[i][0] == 'X') dfs2(i, 0, 2);
        }
        for (int i = 1; i < n; i++) {
            if (s[n - 1][i] == 'X') dfs2(n - 1, i, 3);
        }
        for (int i = 1; i < n - 1; i++) {
            if (s[i][n - 1] == 'X') dfs2(i, n - 1, 4);
        }
        bool re = 0;
        //for(int i=0;i<n;i++){
        //    cout<<s[i]<<endl;
       // }
        //cout<<endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == 'O') {
                    re = dfs3(i, j);
                    if (re == 1) break;
                }
            }
            if (re == 1) break;
        }
        if (re) {
            cout << 1 << endl;
        }
        else cout << 2 << endl;

    }
    return 0;
}

D.你的生日

签到题，直接输出即可

E.星星点灯 II

解法1：首先按照开始时间排序，之后一个一个装入优先队列，优先队列按照结束时间排序。如果在装入新时候，有旧的已经到时间，则删除旧的。

解法2：类似扫描线的思想。每个光有开始时间和结束时间，我们依次去遍历，每次操作后取max。

解法3：线段树离散化/动态开点线段树（极度不推荐）

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#include <regex>
#include <list>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
using namespace std;
struct star{
    ll from;
    ll to;
    ll light;
    bool operator< (const star &a) const{
        return a.to < to;
    }
    friend istream &operator >>(istream &in, star &a) {
        in >> a.from >> a.light>>a.to;
        a.to+=a.from-1;
        return in;
    }
};
bool cmp(star a,star b){
    return a.from<b.from;
}
int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<star> ve;
        star s;
        for(int i=0;i<n;i++){
            cin>>s;
            ve.push_back(s);
        }
        sort(ve.begin(),ve.end(),cmp);
        priority_queue<star> win;
        ll re=0;
        win.push(ve[0]);
        re=ve[0].light;
        ll t=ve[0].light;
        for(int i=1;i<n;i++){
            win.push(ve[i]);
            t+=ve[i].light;
            while(ve[i].from>win.top().to) {
                t-=win.top().light;
                win.pop();
            }
            re=max(re,t);
            //cout<<re<<endl;
        }
        cout<<re<<endl;

    }
    return 0;
}

F.大连大学

签到题，按要求输出即可

暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇