考NOI过程回顾

今天考了下NOI，入门组和提高组都报了，说一下感想：

首先，时间肯定够，入门组+提高组一共7个半小时，中间还听了会课。

入门组

入门组第一题是送分的，不多说。

接下来两道题：

第一道题，看似是gcd，实际啥也不是，就是个乘法题，记得开long long

第二道题，个人用了”DFS”，没太明白，有人能帮我改改吗

提高组

第一道题叫丹钓战，其实就是单调栈（谐音梗），本人用的贪心，可能速度不够，渴望大家多提建议。

第二道题，讨论问题，当时没弄对，后来调的差不多了，供参考

第三道题，说白了就是数学题，求和+函数，送分题

不多说了，上代码：

入门组第一题

#include <iostream>
using namespace std;
int cnt[100001], ans[100001];
#pragma warning(disable:4996)
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	freopen("kingdom.in", "r", stdin);
	freopen("kingdom.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	int tmp;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tmp;
			cnt[j] += tmp;
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> ans[i];
	}
	int counted = 0;
	for (int i = 0; i < n; i++) {
		if ((cnt[i] > (m - cnt[i]) && ans[i]) || (((m - cnt[i])>cnt[i]) && !ans[i])) {
			counted++;
		}
	}
	cout << counted;
	return 0;
}

第二题：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#pragma warning(disable:4996)
typedef long long ll;
int main() {
	freopen("math.in", "r", stdin);
	freopen("math.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll T;
	cin >> T;
	while (T--) {
		ll x, y = -1, z;
		cin >> x >> z;
		vector<ll> v;
		for (int i = 1; i <= sqrt(x); i++) {
			if (x % i == 0) {
				v.push_back(i);
				v.push_back(x / i);
			}
		}
		stable_sort(v.begin(), v.end(), greater<int>());
		for (ll i : v) {
			ll g = (x * i * i);
			if (z % g == 0) {
				y = i*z/g;
				if (count(v.begin(), v.end(), y)) {
					y = -1; continue;
				}
				break;
			}
		}
		cout << y << endl;
	}
	return 0;
}

第三题

#include <iostream>
using namespace std;
#pragma warning(disable:4996)
void DFS(int step, string nowstring, string likestring, size_t n, int&cnt, int pos) {
	if (step >= n) {
		if (nowstring == likestring) cnt++; 
		return;
	}
	for (int i = pos; i < nowstring.size(); i++) {
		if (nowstring[i] == '-') {
			nowstring.erase(i, 1);
			pos = i;
			break;
		}
	}
	string nst2;
	string nst1 = nst2 = nowstring;
	nst1.erase(0, 1);
	int l = 1;
	if (pos > nst2.size())l = 2;
	nst2.erase(pos - l, 1);
	DFS(step + 1, nst1, likestring, n, cnt, pos-1);
	DFS(step + 1, nst2, likestring, n, cnt, pos-1);
	return;
}
int main() {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		int len, cnt = 0;
		string str1, str2;
		cin >> len >> len;
		cin >> str1 >> str2;
		DFS(0, str1, str2, (str1.size() - str2.size()) / 2, cnt, 1);
		cout << cnt << endl;
	}
	return 0;
}

提高组第一题

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#pragma warning(disable:4996)
struct eryuan {
	int a, b;
};
int main() {
	vector<int> a;
	vector<int> b;
	freopen("stack.in", "r", stdin);
	freopen("stack.out", "w", stdout);
	int n, q;
	cin >> n >> q;
	int tmp, tmp1;
	a.push_back(0);
	b.push_back(0);
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		a.push_back(tmp);
	}
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		b.push_back(tmp);
	}
	for (int i = 0; i < q; i++) {
		cin >> tmp >> tmp1;
		int cnt = 0;
		stack<eryuan> f;
		for (int i = tmp; i <= tmp1; i++) {
			eryuan l{};
			l.a = a[i];
			l.b = b[i];
			if (f.size()==0) {
				f.push(l);
				cnt++;
			}
			else {
				while (f.size()>0) {
					if (f.top().b <= b[i] || f.top().a == a[i]) f.pop();
					else {f.push(l);break;}
				}
				if (f.size() == 0) {
					f.push(l); cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

第二题

#include <iostream>
#include <vector>
using namespace std;
vector<int> li[100010];
int n;
#pragma warning(disable:4996)
inline bool gongtong(vector<int> a, vector<int> b) {
    for (int i = 1; i < a.size(); i++) {
        for (int j = 1; j < b.size(); j++) {
            if (a[i] == b[j])return true;
        }
    }
    return false;
}
inline bool taolun(vector<int> a, vector<int> b) {
    int cnt[100001]{};
    int bcnt[100001]{};
    for (int i = 1; i < a.size(); i++) {
        cnt[a[i]] = 1;
    }
    for (int j = 1; j < b.size(); j++) {
        cnt[b[j]] = 1;
    }

    for (int i = 1; i <= n; i++) {
        if (cnt[i] != 1 && bcnt[i] != 1) {
            return false; 
        }
        else {
            continue;
        }
    }

    return true;
}
inline bool disc(vector<int> a, vector<int> b) {
    if (gongtong(a, b) && taolun(a, b))return true;
    return false;
}
int main() {
    freopen("discuss.in", "r", stdin);
    freopen("discuss.out", "w", stdout);
    int T, tmp;
    cin >> T;
    li->push_back(0);
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> tmp;
            li[i].push_back(0);
            for (int j = 1; j <= tmp; j++) {
                int tmp2;
                cin >> tmp2;
                li[i].push_back(tmp2);
            }
        }
        bool flag = false;
        for (int i = 1; i <= n - 1; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (disc(li[i], li[j])) { cout << "YES" << endl << i << " " << j << endl; flag = true; break; }
            }
            if (flag)break;
        }
        if (!flag)cout << "NO" << endl;
    }
}

第三题

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int p[1000010];
int n, m;
vector<vector<int>> a;
inline int64_t f(int i, int j) {
	for (int k = 1; k <= m; k++) {
		p[k] = a[k][i] + a[k][j];
	}
	return static_cast<int64_t>(*min_element(p+1, p + m + 1)) + *max_element(p+1, p + m+1);
}
#pragma warning(disable:4996)
int main() {
	freopen("sort.in", "r", stdin);
	freopen("sort.out", "w", stdout);
	int64_t ans=0;
	cin >> m >> n;
	vector<int> v;
	v.push_back(0);
	a.push_back(v);
	for (int i = 0; i < m; i++) {
		vector<int> tmp;
		tmp.push_back(0);
		for (int j = 0; j < n; j++) {
			int temp;
			cin >> temp;
			tmp.push_back(temp);
		}
		a.push_back(tmp);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ans += f(i, j);
		}
	}
	cout << ans;
}