SMU Summer 2023 Contest Round 8(2019 陕西省大学生程序设计竞赛)

B - Grid with Arrows(欧拉图)

题意:一个总规模为\(n × m\)的矩阵，矩阵上的每个位置有其下一位置的信息，询问是否存在一种解法从某一点出发，使得整个矩阵的每个位置都被访问到，如果越界或者遇到重复访问位置的解法被认为失败

题解:想要遍历所有的位置,那么只有两种情况

• 由唯一的位置出发,最后能遍历所有位置
• 由任意点位置出发,最后能回到该点

把每个格子看做有向图中的一个节点,那么每个节点至多向别的节点连一条边.如果有入度为 \(0\) 的节点，那么必须从该节点出发并检查（否则不可能经过其它点访问入度为 \(0\) 的节点）；否则整张图可能是一个或多个环，随便挑一个节点出发并检查即可。复杂度 \(\mathcal{O}(nm)\)。

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int,int> PII;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	const int mod = 1e9 + 7;
	int T;
	cin >> T;
	while(T--){

		int n,m;
		cin >> n >> m;
		vector<string> s(n + 1);
		for(int i = 1;i <= n;i ++)	cin >> s[i];
		vector<int> a(1),deg((n + 1) * (m + 1));

		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= m;j ++){
				int step,now = (i - 1) * m + j;//将二维的转换成一维的方便遍历
				int x = i, y = j;
				cin >> step;
				if(s[i][j - 1] == 'u'){
					now -= step * m;
					x -= step;
				}else if(s[i][j - 1] == 'd'){
					now += step * m;
					x += step;
				}else if(s[i][j - 1] == 'l'){
					now -= step;
					y -= step;
				}else {
					now += step;
					y += step;
				}
				if(x < 1 || x > n || y < 1 || y > m)
					now = -1;
				if(now != - 1) deg[now]++;
				a.emplace_back(now);
			}
		}

		vector<bool> vis((n + 1) * (m + 1));
		auto dfs = [&](auto self,int x,int sum) ->bool{
			if(sum == n * m) return 1;
			if(x == -1 || vis[x]) return 0;
			vis[x] = 1;
			return self(self,a[x],sum + 1);
		};

		int num = 0, start = 1;
		for(int i = 1;i <= n * m;i ++){
			if(!deg[i]){
				num ++;
				start = i;
			}
		}

		if(num > 1){
			cout << "No" << endl;
		}else{
			if(dfs(dfs,start,1)) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}

	return 0;
}

C. 0689(前缀和)

首先总共有\(\frac{(n+1)*n}{2}\)个子串,其次,只要它包含了\(0,8,69\)这样的就一定能够变回原来的字符串,所以我们可以再\(+1\),

所以最开始答案为\(\frac{(n+1)*n}{2}+1\)种.

• 如果原字符串存在 \(0\)和 \(8\)，那么只要翻转这个长度为 \(1\) 的区间，仍然还是原字符串。我们要去重,减去\(num_0,num_8\)

• 如果原字符串里都是 \(6\)，那么翻转任何一个区间都会把 \(6\) 变成 \(9\)，不可能得到原字符串。原字符串都是 \(9\) 的情况同理。所以这种要\(-1\)

• 如果原字符串由 \(6\) 和 \(9\) 组成。这样的字符串一定存在子串 \(69\) 或者 \(96\)，翻转这个长度为 \(2\) 的区间，仍然还是原字符串

• 如果一个子串为\(0890\),那么它和翻转\(89\)是一样的,若为两边为\(8\)同理

  所以答案就是左右端点不是\(00,88,69,96\)的区间数量,我们可以用前缀和来解决这个问题

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int,int> PII;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin >> T;
	while(T--){
		string s;
		cin >> s;

		int n = s.size();
		s = " " + s;
		vector<int> a(n + 1),b(n + 1),c(n + 1),d(n + 1);
		for(int i = 1;i <= n;i ++){
			if(s[i] == '0') a[i] = a[i - 1] + 1;
			else a[i] = a[i - 1];

			if(s[i] == '8') b[i] = b[i - 1] + 1;
			else b[i] = b[i - 1];

			if(s[i] == '6') c[i] = c[i - 1] + 1;
			else c[i] = c[i - 1];

			if(s[i] == '9') d[i] = d[i - 1] + 1;
			else d[i] = d[i - 1];
		}

		int ans = (n + 1) * n / 2 + 1;
		if(n == c[n] || n == d[n]) ans --;

		ans -= (a[n] + b[n]);
		for(int i = 1;i <= n;i ++){
			if(s[i] == '0') ans -= a[n] - a[i];
			else if(s[i] == '8') ans -= b[n] - b[i];
			else if(s[i] == '9') ans -= c[n] - c[i];
			else ans -= d[n] - d[i];
 		}
 		cout << ans << endl;
	}

	return 0;
}

E. Turn It Off(二分+枚举)

直接二分+枚举扫一遍,复杂度\(\mathcal{O}(nlogn)\).

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n,k;
        cin >> n >> k;
        string s;
        cin >> s;

        auto check = [&](int x){
            int sum = 0;
            auto str = s;
            for(int i = 0;i < str.size(); i ++){
                if(str[i] == '1'){
                    int cnt = i;
                    while(i < x + cnt && i < str.size())
                        str[i++] = '0';
                    sum ++;
                }
            }
            return sum <= k;
        };


        int l = 0, r = n;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid - 1;
            else l = mid + 1;
        }

        cout << l + 1<< endl;
    }

    return 0;
}

F. K-hour Clock

分类讨论:

• 如果\(x+y = z\),那任何\(k>z\)都可以.
• 如果\(y\le z\),说明不能从\(x\)点到达\(z\)点.
• 如果\(x+y\le z + z\),说明不能过一天后到达\(z\)点.
• 其余情况直接输出\(x+y-z\)就好了,就当作只过了一天,或者还不到一天

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int,int> PII;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	const int mod = 1e9 + 7;
	int T;
	cin >> T;
	while(T--){

		int x,y,z;
		cin >> x >> y >> z;
		int cha = x + y - z;
		if(!cha)
			cout << z + 1 << endl;
		else if(y <= z || x + y <= z + z)
			cout << -1 << endl;
		else cout << cha << endl;		
	}
	
	return 0;
}

L. Digit Product

只要区间不在同一个\(10\)的倍数的区间内,则说明它们一定会经过一个末尾带有\(0\)的数,这时不管乘什么都为\(0\),其余情况正常乘即可

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int,int> PII;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	const int mod = 1e9 + 7;
	int T;
	cin >> T;
	while(T--){

		auto getnum = [&](int x){
			int res = 1;
			while(x){
				res *= x % 10 % mod;
				x /= 10;
			}
			return res % mod;
		};

		int l,r;
		cin >> l >> r;
		if(l / 10 != r / 10){
			cout << 0 << endl;
		}else{
			int ans = 1;
			for(int i = l;i <= r;i ++){
				ans = ans * getnum(i) % mod;			
			}
			cout << ans % mod << endl;
		}
	}
	return 0;
}

本栏目推荐文章
• FIFO设计
• 深入探索JVM：理解Java程序在虚拟机中的存储和管理
• 从C++CLI工程的依赖库引用问题看.Net加载程序集机制
• 微信小程序 wxs的概念
• spring与设计模式之三代理模式
• jQuery自动加载更多程序
• 2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)
• 微信小程序 取列表的for循环的第一个值
• AtCoder Beginner Contest 335 G Discrete Logarithm Problems
• 各种语言版本的“Hello, world”程序汇总

程序设计 Contest 大学生 程序 Summer程序设计contest大学生 程序 contest summer round 2023 contest summer sdut 2023 2023 contest summer round 程序设计 大学生 程序 大学 题解 程序设计 大学生 程序 程序设计 程序 年度 大学生 赛区 程序设计acm-icpc大学生 程序设计 计算机 大学生 程序 组合数学 程序设计 数学 大学生