思维训练2

偏执的太偏执、 2024-02-21 09:59 8阅读 0赞

### 题目描述1 ###

[Problem - A - Codeforces][]

![e71625cd70d04988bc3ca5f1b6952b95.png][]

### 题目分析 ###

通过题目发现a\[1\] = d\[1\]，

a\[i\] = d\[i\] + a\[i - 1\]

由于所有的数都为正数，所以只要出现a\[i - 1\] - d\[i\] >= 0这种情况a\[i\]就可以取为绝对值，也就是说a\[i\]会有一正一负两种情况，当然，如果在这个a\[i - 1\] - d\[i\] >= 0条件我们要保证d\[i\]是不为0的不然正负都是只有一种情况

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10;
    int d[N], a[N];
    void solve()
    {
    	int n;
    	memset(d, 0, sizeof d);
    	memset(a, 0, sizeof a);
    	cin >> n;
    	for(int i = 1; i <= n; i ++)cin >> d[i];
    	a[1] = d[1];
    	for(int i = 2; i <= n; i ++)
    	{
    		a[i] = d[i] + a[i - 1];
    		if(d[i] && a[i - 1] - d[i] >= 0)
    		{
    			cout << - 1 << '\n';
    			return;
    		}
    	}
    	for(int i = 1; i <= n; i ++)cout << a[i] << ' ';
    	cout << '\n';
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int t;
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

### 题目描述2 ###

[Problem - B - Codeforces][]

![c486134cce6d40098f3040d5f69598cb.png][]

### 题目分析 ###

我们最终的目的是为了升序排序，且其操作为反转操作，故我们从数组两边使用双指针，遇到01需要进行反转的就停下做出一次记录（此处使用vector)即可,注意输出时从小到大即可，所以需要排序

#include<bits/stdc++.h>
    using  namespace std;
    const int N = 2e5 + 10;
    void solve()
    {
    	char a[N];
    	int n, flag = 0;
    	cin >> n;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> a[i];
    	}
    	for(int i = 2; i <= n; i ++)
    	{
    		if(a[i - 1] > a[i])flag = 1;
    	}
    	if(!flag)
    	{
    		cout << 0 << '\n';
    	}
    	else
    	{
    		vector<int> v;
    		int l = 1, r = n;
    		while(l < r)
    		{
    			while(l < r && a[l] == '0')l ++;
    			while(l < r && a[r] == '1')r --;
    			if(l < r)
    			{
    				v.push_back(l);
    				v.push_back(r);
    				l ++;
    				r --;
    			}
    		}
    		sort(v.begin(), v.end());
    		cout << 1 << '\n' << v.size() << ' ';
    		for(auto i : v)
    		{
    			cout << i << ' ';
    		}
    		cout << '\n';
    	}
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int t;
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

### 题目描述3 ###

[Problem - C - Codeforces][]

![3d670b9b94894616b2f12b1881cabb89.png][]

### 题目分析 ###

将10拆解成2和5，因为只有2 \* 5可以拆解成10，如果少2就乘2或者少5就乘5，如果还可以继续就乘10，由于此时末尾都为0，故还可以乘到小于m的倍数

![82c27d8c26464f19a1f7fa334816d6f8.jpeg][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    void solve()
    {
    	ll n, m;
    	cin >> n >> m;
    	ll k = 1;
    	ll t = n;
    	ll c2 = 0, c5 = 0;
    	while(t % 2 == 0)t /= 2, c2 ++;
    	while(t % 5 == 0)t /= 5, c5 ++;
    	while(c2 < c5 && k * 2 <= m)k *= 2, c2 ++;
    	while(c5 < c2 && k * 5 <= m)k *= 5, c5 ++;
    	while(k * 10 <= m)k *= 10;
    	cout << n * k * (m / k) << '\n';
    }
    int main()
    {
    	int t;
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

### 题目描述4 ###

[Problem - D - Codeforces][]

![fc026ca5195e482ca84bd7a58fbc78cb.png][]

### 题目分析 ###

对于此题主要是数的配对，我们将数都存入map将数组排序，从大到小来看每一个数，如果其数/x在map中还存在说明这两个数字可以配对，将这个数字以及可以和这个数配对的数字删除，如果说没有可以/x的数说明不能配对此时就需要添加数字用ans记录添加的个数

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 2e5 + 10;
    void solve()
    {
    	int ans = 0;
    	int n, x;
    	map<int, int> mp;
    	int a[N];
    	cin >> n >> x;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> a[i];
    		mp[a[i]] ++;
    	}
    	sort(a + 1, a + 1 + n);
    	for(int i = n; i >= 1; i --)
    	{
    		if(mp[a[i]])
    		{
    			if(a[i] % x == 0)
    			{
    				if(mp[a[i] / x] == 0)
    				{
    					ans ++;
    					mp[a[i]] --;
    				}
    				else
    				{
    					mp[a[i]] --;
    					mp[a[i] / x] --;
    				}
    			}
    			else
    			{
    				mp[a[i]] --;
    				ans ++;
    			}
    		}
    	}
    	cout << ans << '\n';
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int t;
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

### 题目描述5 ###

[Problem - E - Codeforces][]

![2f411c90f2eb480fbf46174b2a82b0ed.png][]

### 题目分析 ###

我们可以将每一列存在vector中进行计算，使用下方的区间模型将答案加入ans

![7db3156e642b4b1599dbacf5f8b24b9d.jpeg][]

![1d8a1bcf2464437893ee3e7a9f3d85c5.jpeg][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    vector<vector<ll>> v;
    void solve()
    {
    	int n, m, x;
    	ll ans = 0;
    	cin >> n >> m;
    	v.clear();
    	v.resize(m + 1);
    	for(int i = 1; i <= n; i ++)
    	{
    		for(int j = 1; j <= m; j ++)
    		{
    			cin >> x;
    			v[j].push_back(x);
    		}
    	}
    	for(int i = 1; i <= m; i ++)
    	{
    		sort(v[i].begin(), v[i].end());
    		for(int j = 1; j < n; j ++)
    		{
    			ans += 1ll * (v[i][j] - v[i][j - 1]) * j * (n - j);
    		}
    	}
    	cout << ans << '\n';
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int t;
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	} 
    	return 0;
    }

[Problem - A - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/478562/problem/A
[e71625cd70d04988bc3ca5f1b6952b95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/e637aa8fd9b4418a8be4e31d6db70201.png
[Problem - B - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/478562/problem/B
[c486134cce6d40098f3040d5f69598cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/29e45cb987c44c4494927da8148310d4.png
[Problem - C - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/478562/problem/C
[3d670b9b94894616b2f12b1881cabb89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/f672bc218ea546e99983b097ad2e8be9.png
[82c27d8c26464f19a1f7fa334816d6f8.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/ef3c3ba9f48c44eb840ff4710a917203.png
[Problem - D - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/478562/problem/D
[fc026ca5195e482ca84bd7a58fbc78cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/e1320acd67ef44dfb24d29a2bf2ccfcb.png
[Problem - E - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/478562/problem/E
[2f411c90f2eb480fbf46174b2a82b0ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/97f9c24670ba4cffb0cff9972fa9a038.png
[7db3156e642b4b1599dbacf5f8b24b9d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/47b7f5638f5e4143b8203e7b6c89e483.png
[1d8a1bcf2464437893ee3e7a9f3d85c5.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/1366d215d023464ca385e7ec0e91fdb8.png