上海市计算机学会竞赛平台三星级挑战

上海市计算机学会竞赛平台 | 2022 三星级挑战

• • • 最大回撤
    • 最后一击
    • 平衡点
    • 栈的判断
    • 排队安排
    • 逆波兰式
    • 股票市场
    • 城市的中心
    • 伙伴
    • 两数之和
    • 阶乘求和(Python(因为懒))
    • 连乘问题
    • 随机性验证
    • 文本编辑器
    • 浏览器
    • 牛奶供应（一）
    • 牛奶供应（三）
    • 反子序列

---

此文章仅供学习交流，不得抄袭刷分！！！
本文会不间断更新，更新速度取决与博主的做题速度…

最大回撤

#include 
using namespace std;

int main()
{
    int n, min = -100001, large = -100001, a;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a;
        min = max(min, large - a);
        large = max(large, a);
    }
    cout << min;
    return 0;
}

最后一击

#include 
using namespace std;

long long n, a, b, x = 1, y = 1, cont = 0, sum = 0;
bool q = false, g = false, d = false;
int main()
{
	cin.tie(0);
	cin >> n >> a >> b;
	while(sum < n)
	{
		if (a * y > b * x)
			sum++, x++, q = true, g = false, d = false;
		else if (a * y == b * x)
			sum += 4, x++, y++, q = false, g = false, d = true;
		else
			sum++, y++, q = false, g = true, d = false;
	}
	if (q == true)	
		cout << "A";
	else if (g == true)	
		cout << "B";
	else if (d == true)	
		cout << "C";

	return 0;
}

平衡点

#include 
#include 
#include 
#include 
using namespace std;

int n;
long long a[100005];
long long pre[100005], suf[100005];
long long ans, L, R;
int main()
{
	std::ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i]; //前缀和
		ans += a[i] * (i - 1); //初始为最大
	}
	for(int i = n; i >= 1; i--)
		suf[i] = suf[i + 1] + a[i]; //后缀和
	R = ans;
	for(int i = 1; i <= n; i++)
	{
		L += pre[i];
		R -= suf[i + 1];
		ans = min(ans, abs(L - R));
	}
	cout << ans;
	return 0;
}

栈的判断

#include 
#include 
#include 
using namespace std;

int n, x;
stack<int>stak;
int main() {
	std::ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		if(stak.empty() && x <= tmp) {
			while(x < tmp) 
				stak.push(x++);
			x++;
			}
		else if(stak.top() == tmp)
			stak.pop();
		else if(stak.top() < tmp) {
			while(x < tmp) 
				stak.push(x++);
			x++;
			}
		else if(stak.top() > tmp) {
			cout << "Invalid" << endl;
			return 0;
			}
		}
	cout << "Valid" << endl;
	return 0;
	}

排队安排

#include 
#include 
using namespace std;

int n, a[1000000], c;
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	
	sort(a, a + n);
	for (int i = 0; i < n; ++i)
		if (c <= a[i])
			++c;

	cout << c << endl;
	return 0;
}

逆波兰式

#include
using namespace std;
stack<int> st;
string line;
int main() {
    getline(cin,line);
    for(int i=0; i<line.size(); i++) {
        char tem=line[i];
        if(tem==' ') continue;
        if(tem<='9' and tem>='0') {
            st.push(tem-'0');
            continue;
        }
        int now=0;
        int b= st.top();
        st.pop();
        int a=st.top();
        st.pop();
        if(tem=='+') st.push((a+b)%10);
        if(tem=='-') st.push((a-b)%10);
        if(tem=='*') st.push(a*b%10);
    }
    int ans=st.top();
    ans=ans%10;
    if (ans<0) ans=10+ans;
    cout<<ans;
    return 0;
}

股票市场

#include 
using namespace std;
long long n, m, stock = 0, a[100001];
bool flag = false;
int main() {
	cin.tie(0);
	cin >> n >> m;
	cin >> a[0];
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i];

	for (int i = 1; i <= n; ++i) {
		if (a[i - 1] < a[i] && !flag) {
			/* 比手中小，可以买股票 */
			stock = m / a[i - 1];
			m -= (m / a[i - 1]) * a[i - 1];
			flag = true;	// falg:如果一直涨的话，没必要一直买
		} else if (a[i - 1] > a[i] && flag) {
			/* 小了，卖股票 */
			m += stock * a[i - 1];
			stock = 0;
			flag = false;
		}
	}
	if (flag)
		m += stock * a[n];
	cout << m << endl;
	return 0;
}

城市的中心

#include 
#include 
using namespace std;

int n, ans = 0;
struct dis {
	int x, y;
} s[100000];
bool xcmp(dis a, dis b) {
	return a.x < b.x;
}
bool ycmp(dis a, dis b) {
	return a.y < b.y;
}

int main() {
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n ; ++i)
		cin >> s[i].x >> s[i].y;

	sort(s, s + n, xcmp);
	int advx = s[n / 2].x;
	sort(s, s + n, ycmp);
	int advy = s[n / 2].y;

	for (int i = 0; i < n ; ++i) {
		ans += abs(s[i].x - advx);
		ans += abs(s[i].y - advy);
	}

	cout << ans << endl;
	return 0;
}

伙伴

#include
using namespace std;
int n, m, ds, a[1000001], l[1000001], r[1000001];
int main() {
	cin.tie(0);
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		a[i] = i;
		l[i] = i - 1;
		r[i] = i + 1;
	}

	for (int i = 1; i <= m; i++) {
		cin >> ds;

		if (l[ds] == 0)
			cout << "* " << r[ds] << endl;
		else if (r[ds] == n + 1)
			cout << l[ds] << " *" << endl;
		else 
			cout << l[ds] << " " << r[ds] << endl;

		l[r[ds]] = l[ds];
		r[l[ds]] = r[ds];
	}

	return 0;
}

两数之和

#include 
#include 
using namespace std;

long long  n, t, a[1000001];
int search(int x) {
	int left = 1, right = n, mid;

	while (left <= right) {
		mid = (right + left) >> 1;

		if (a[mid] < x)
			left = mid + 1;
		else if (a[mid] > x)
			right = mid - 1;
		else
			return a[mid];
	}

	return -1;	// Not found
}

int main() {
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n; ++i)
		cin >> a[i];

	cin >> t;

	for (int i = 0; i < n; ++i)
		if (search(t - a[i]) != -1 && search(t - a[i]) != a[i]) {
			cout << "Yes";
			return 0;
		}

	cout << "No";
	return 0;
}

阶乘求和(Python(因为懒))

#!/usr/bin/python3
s = 0
t = 1
n = int(input())
for i in range(1, n + 1):
    t *= i
    s += t
print(s)

连乘问题

#include 
using namespace std;
long long n, a[100001], f[100001], g[100001];
int main() {
	cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) 
		cin >> a[i];
    f[0] = 1;
    for (int i = 1; i <= n; ++i) 
    	f[i] = f[i-1] * a[i] % 10000;
    g[n+1] = 1;
    for (int i = n; i >= 1; --i) 
    	g[i] = g[i+1] * a[i] % 10000;
    for (int i = 1; i <= n; ++i)
        cout << f[i-1] * g[i+1] % 10000 << endl;
    return 0;
}

随机性验证

#include 
using namespace std;

string s;
bool ran = true;
int main() {
	cin.tie(0);
	cin >> s;
	int len = s.length();
	for(int i = 0; i < len - 2 ; ++i)
		if(s[i + 1] == s[i] || s[i + 2] == s[i])
			ran = false;

	if(ran)
		cout << "Random string";
	else
		cout << "Not a random string";
	return 0;
}

文本编辑器

#include
#include
using namespace std;

char ch, c;
long long n, i;
list<char> l;
list<char>::iterator iter = l.begin();
int main() {
	cin >> n;
	for(i = 1; i <= n ; ++i) {
		cin >> ch;
		if(ch == 'i')
			cin >> c;
		if(ch == 'i') {
			l.insert(iter, c);
		} else if(ch == 'd') {
			if(!l.empty() && iter != l.end()) {
				iter = l.erase(iter);
			}
		} else if(ch == 'f') {
			if(iter != l.end()) {
				++iter;
			}
		} else if(ch == 'b') {
			if(iter != l.begin()) {
				--iter;
			}
		}
	}
	for(iter = l.begin(); iter != l.end(); ++iter) {
		cout << *iter;
	}
	return 0;
}

浏览器

#include 
using namespace std;
int n, limit, pos;
char op;
string w[50001];
int main() {
	cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> op;
        if (op == 'v') {
            limit = ++pos;
            cin >> w[pos];
        }

        if (op == 'b') {
            if (pos <= 1) {
                cout << "?" << endl;
                continue;
            }
            --pos;
        }
        
        if (op == 'f') {
            if (pos >= limit) {
                cout << "?" << endl;
                continue;
            }
            ++pos;
        }
        cout << w[pos] << endl;
    }
    return 0;
}

牛奶供应（一）

#include
using namespace std;
int n, m, need, ans = 0, t = 1, a[1000001];
int main()
{
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> need;

		for (int j = max(i - m, t); j <= i; j++)
			if (!need)
				break;
			else if (a[j] >= need) {
				a[j] -= need, ans += need, t = j;
				break;
			} else
				ans += a[j], need -= a[j], a[j] = 0;
	}

	cout << ans;
	return 0;
}

牛奶供应（三）

#include 
using namespace std;
long long ans = 0;
int n, s, minn = 100001;
int main() {
  	cin.tie(0);
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        int c, a;
        cin >> c >> a;
        minn = min(c, minn);
        ans += minn * a;
        minn += s;
    }
    cout << ans << endl;
    return 0;
}

反子序列

#include 
#include 
using namespace std;
int n, k, F[100001], ans, cnt;
int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		if (!F[x])
			F[x] = 1, ++cnt;
		if (cnt == k) {
			cnt = 0, ++ans;
			memset(F, 0, sizeof(F));
		}
	}
	cout << ++ans << endl;
	return 0;
}