2019 山东省大学生程序设计竞赛

A. Calandar

纯模拟吧(感觉我做麻烦了(?),

就是如果问的是未来的日期,就用相隔天数取模后加上这天的星期,

如果问的是曾经的,就用这天的星期减去相隔天数的取模后的数,因为是减法,记得加模数

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

using namespace std;

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

    unordered_map<string,int> cal;
    unordered_map<int,string> ca;
    cal["Monday"] = 1;
    cal["Tuesday"] = 2;
    cal["Wednesday"] = 3;
    cal["Thursday"] = 4;
    cal["Friday"] = 5;
    ca[1] = "Monday";
    ca[2] = "Tuesday";
    ca[3] = "Wednesday";
    ca[4] = "Thursday";
    ca[0] = "Friday";

    int T;
    cin >> T;
    while (T--) {
        int y1,y2,m1,m2,d1,d2;
        string s;
        cin >> y1 >> m1 >> d1 >> s >> y2 >> m2 >> d2;
        m1--,m2--;
        int sum = 0;
        if(y1 > y2){
            int s1 = m1 * 30 + d1 + 360 , s2 = m2 * 30 + d2;
            sum = (cal[s] - (s1 - s2) % 5 + 5) % 5 ;
        }else if(y1 < y2){
            int s1 = m1 * 30 + d1 , s2 = m2 * 30 + d2 + 360;
            sum = (cal[s] + (s2 - s1) % 5) % 5 ;
        }else {
            int s1 = m1 * 30 + d1 , s2 = m2 * 30 + d2;
            if(s1 > s2){
                sum = (cal[s] - (s1 - s2) % 5 + 5) % 5 ;
            }else{
                sum = (cal[s] + (s2 - s1) % 5) % 5 ;
            }
        }
        cout << ca[sum] << endl;
    }
    return 0;
}

C. Wandering Robot

先跑一轮算出最后所在的位置,然后算\(k-1\)得出最后一次移动的起点再跑一轮

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

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


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int MaxX,Maxy, EndX,EndY, ans = 0,x = 0,y = 0;
        for(int i = 0;i < n;i ++){
            if(s[i] == 'R') x++;
            else if(s[i] == 'L') x--;
            else if(s[i] == 'U') y++;
            else y--;

            int val = abs(x) + abs(y);
            ans = max(ans, val);

        }
        x *= (k - 1), y *= (k - 1);
        if(k > 1){
            for(int i = 0;i < n;i ++){
                if(s[i] == 'R') x++;
                else if(s[i] == 'L') x--;
                else if(s[i] == 'U') y++;
                else y--;
                int val = abs(x) + abs(y);
                ans = max(ans, val);
            }
        }

        cout << ans << endl;

    }
    return 0;
}

D. Game on a Graph

连通图最少需要 \((n-1)\)条边，因此最多可以操作 \((m-(n-1))\) 次，输的人就是 \((m-(n -1)) \bmod k\)。考虑到读入，复杂度 \(\mathcal{O}(k+m)\)。

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

using namespace std;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while(T--){
		int n,m,k;
		string s;
		cin >> k >> s;
		cin >> n >> m;
		for(int i = 0,l,r;i < m;i ++)
			cin >> l >> r;
		if(s[(m - (n - 1)) % k] == '1') cout << 2 << '\n';
		else cout << '1' << '\n';
	}

	return 0;
}

F. Stones in the Bucket

考虑都往中间靠,如果总数不是\(s\)的倍数,就用操作\(1\)丢掉几个,然后都往中间靠,取多补少

#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--){
		int n,sum = 0;
		cin >> n;
		vector<int> a(n);
		for(auto &i : a){
		 	cin >> i;
		 	sum += i;
		}

		int tag = sum / n, ans = sum % n;
		for(auto i : a)
			ans += max(tag - i, 0ll);
		cout << ans << '\n';
	}

	return 0;
}

H. Tokens on the Segments

如果我们让更多的线段被标记,那同一个点上应该选择右端点最小的段,可以用堆来模拟这个过程

每次我们取了一点后,把后面的段又放进堆里,如此循环(貌似这题数据很水,暴力的也过了

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

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

struct Node{
	int l,r;
	Node(){}
	Node(int l,int r) : l(l),r(r){}
	bool operator < (const Node& s)const{
		if(s.l == l) return r > s.r;
		return l > s.l;
	}
};

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

	
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;

		priority_queue<Node> Q;
		for(int i = 0;i < n;i ++){
			int l,r;
			cin >> l >> r;
			Q.push(Node(l,r));
		}

		int now = 0, ans = 0;
		while(Q.size()){
			auto [l,r] = Q.top();
			Q.pop();

			if(l <= now && l + 1 <= r){
				Q.push(Node(l + 1, r));
				continue;
			}
			if(l > now){
				ans ++;
				now = l;
			}
		}
		cout << ans << '\n';
	}

	return 0;
}

L. Median

思路就是去跑\(dfs\)或\(bfs\)计算出每个数大于多少和小于多少,如果大于的数超过了\(\lfloor\frac{n}{2}\rfloor\)或者小于的数超过了\(\lfloor\frac{n}{2}\rfloor\)都说明这个数不可能为中位数,另外如果在跑\(dfs\)或\(bfs\)的过程中出现了环,就是\(a>b,b>c,c>a\)这种,则无解

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

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


void solve(){
	int n,m;
		cin >> n >> m;
		vector<int> pre(n + 1),nxt(n + 1),g[n + 1];
		for(int i = 0;i < m;i ++){
			int x,y;
			cin >> x >> y;
			g[x].emplace_back(y);
		}	

		vector<int> vis(n + 1);
		auto bfs = [&](int x){
			queue<int> Q;
			Q.push(x), vis[x] = x;

			while(Q.size()){
				auto u = Q.front();
				Q.pop();

				for(auto i : g[u]){
					if(i == x) return false;
					if(vis[i] == x) continue;

					Q.push(i);
					vis[i] = x;
					pre[i]++,nxt[x]++;					
				}
			}
			return true;
		};

		for(int i = 1;i <= n;i ++){
			if(!bfs(i)){
				cout << string(n,'0') << '\n';
				return ;
			}
		}

		for(int i = 1;i <= n;i ++){
			if(pre[i] * 2 <= n && nxt[i] * 2 <= n)
				cout << '1';
			else
				cout << '0';
		}
		cout << '\n';
		return ;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while(T--){
		solve();
	}

	return 0;
}

M. Sekiro

\(n=1\)时就会一直循环了,因此\(n=1\)时退出即可

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

using namespace std;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while(T--){
		int n,m;
		cin >> n >> m;
		for(int i = 1;i <= m;i ++){
			if(n > 1) n = (n + 1) >> 1;
			else break;
		}
		cout << n << '\n';
	}
	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大学生 程序设计 计算机 大学生 程序 组合数学 程序设计 数学 大学生