牛客周赛104A-E

A题:求不动点的数量. 输入数据后直接计数即可

#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int , int>
#define tiii tuple<int,int,int>
#define sort(a) sort(a.begin(),a.end())
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;




void solve() {
	int cnt = 0;
	vector<int>a(4);
	for (int i = 1; i <= 4; i++) {
		cin >> a[i];
		if (a[i] == i)
			cnt++;
	}
	cout << cnt << endl;
}


int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
		solve();
	return 0;
}

B题:构造一个长度为n的数组,使其有k个不动点. 注意到当n-k=1时无解,易证当n-1个数都是不动点,最后一个必然是不动点.于是萌新便有了清晰的思路:从1-k输出,然后从n-k+1输出便能得到所求序列,写下代码后自信提交得到wa...举了例子后发现n=3,k=0时代码会输出3,2,1.有一个不动点不满足题意,于是发现当n-k%2=时,中间的数会是不动点使得不动点的数量+1从而wa.因此我们只需要在此情况上特判即可.

#define int long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int , int>
#define tiii tuple<int,int,int>
#define sort(a) sort(a.begin(),a.end())
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;




void solve() {
	int n, k;
	cin >> n >> k;
	if (n - k == 1) {
		cout << "-1\n";
		return;
	}
	vector<int>ans;
	for (int i = 1; i <= k; i++)
		ans.pb(i);
	for (int i = n; i > k; i--)
		ans.pb(i);
	//n=3,k=0,3 1 2
	if (  (n - k) % 2 == 1) {
		int mid = (n - k) / 2 ;
		swap(ans[k + mid], ans[k + mid + 1]);
	}
	for (auto a : ans)
		cout << a << ' ';
}


signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
		solve();
	return 0;
}

C题:给定2*n长度的数组,问操作后不动点的最大数量.满足不动点的首要条件:元素≤n.因此我们可以记录≤n的元素出现次数,该元素的贡献=min(2,元素出现次数).(感觉真比B题简单吧..萌新勿喷)

#define int long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int , int>
#define tiii tuple<int,int,int>
#define sort(a) sort(a.begin(),a.end())
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;




void solve() {
	int n;
	cin >> n;
	vector<int>a(2 * n + 1, 0);
	vector<bool>b(2 * n + 1, false);
	map<int, int>mp;
	for (int i = 1; i <= 2 * n; i++) {
		cin >> a[i];
		mp[a[i]]++;
	}
	int cnt = 0;
	for (int i = 1; i <= 2 * n; i++) {
		if (a[i] <= n && b[a[i]] == false) {
			cnt += min(mp[a[i]], 2ll);
			b[a[i]] = true;
		}
	}
	cout << cnt << endl;
}


signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
		solve();
	return 0;
}

D题:最大化矩阵的不动点数量.矩阵不动点:aij=min(i,j).不难发现,第一行第一列所求为1,第二行第二列所求为2(不包括被第一行第一列标记的部分)...依次类推.于是我们可以标记原本就是不动点的位置并记录个数,这些位置在操作中不能动.操作有+2(两个不是不动点的交换之后变为了所在区域的所求点),+1(不存在+2的情况,但是存在该区域的所求点),不变(前两种都没有)的情况,这些样例都很好的展现.然后写代码发现+2的情况不知道怎么写比较好,卡了挺久(嵌套用的太少了).我们遍历这个非不动点的位置时,标记当前的数和所求数,在后面的遍历中发现所求数和当前的数就可以互换+2.详见代码

#define int long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int , int>
#define tiii tuple<int,int,int>
#define sort(a) sort(a.begin(),a.end())
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;




void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>>a(n + 1, vector<int>(m + 1, 0));
	vector<vector<bool>>b(n + 1, vector<bool>(m + 1, false));
	map<int, int>mp1;
	map<pii, int>mp2;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == min(i, j)) {
				cnt++;
				b[i][j] = true;
			} else {
				mp2[ {a[i][j], min(i, j)}]++;
				mp1[a[i][j]]++;
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!b[i][j]) {
				if (mp2[ {min(i, j), a[i][j]}]) {
					cout << cnt + 2 << endl;
					return;
				} else if (mp1[min(i, j)])
					res = 1;
			}
		}
	}
	cout << cnt + res << endl;
}


signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
		solve();
	return 0;
}

E题:补题,当时有了确切的思路但没能想到用下标来处理贡献(感觉是经验问题吧,还是写题太少了呜呜呜).求所有子数组的不动点数量,这些子数组能从小到大排序(看到这有经验的人已经想到会和下标有关,正如排序能用二分).我们举样例:3 6 4 2 1 5.要使3有贡献,那么必须出现1,2,因此子数组长度最小为5(1的下标比2的大自然把2也囊括了,维护最大下标的原因),那么以3为起点,往后取就能有两次符合条件的子数组(6-5+1),而3的下标为1(如果是4,必须要取3,不能因为4的下标是3就能往前取,因为4前面必须有3,维护最小下标的原因),显然不能往前取了,因此3的总贡献=1*(6-5+1).再看1,1不需要前面有元素,因此只要遍历到它都能有贡献,1的下标为5,因此往后取有2次,往前取有5次,因此1的总贡献=5*(6-5+1).不难发现,要计算3的贡献需要涉及到1,于是遍历1-n,维护当前元素的最小最大下标即可算出每个元素的总贡献.

#define int long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int , int>
#define tiii tuple<int,int,int>
#define sort(a) sort(a.begin(),a.end())
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;




void solve() {
	int n;
	cin >> n;
	vector<int>a(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	map<int, int>mp;
	for (int i = 1; i <= n; i++) {
		mp[a[i]] = i;
	}
	int ans = 0;
	int mn = 3e5 + 1, mx = -1;
	for (int i = 1; i <= n; i++) {
		mn = min(mn, mp[i]);
		mx = max(mx, mp[i]);
		ans += mn * (n - mx + 1);
	}
	cout << ans << endl;
}


signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
		solve();
	return 0;
}