codeforces/Atcoder思维题总结_codeforcesdiv2难度和atcoder abc比

Codeforces Round #713 (Div. 3)D. Corrupted Array

题意：
给一个b数组，去掉b数组中的两个元素构成数组a，满足a数组中元素的和等于去掉两个元素中的一个，问是否存在这样的数组。

思路：
如果存在这样的数组，去掉的两个元素一定有一个是数组中的最大值或者次大值。
这样分情况：
1.对b排序，取出最大值，以它为a数组的和，遍历b，如果最大值-其中一个元素等于数组的和，那去掉的元素就为这个和最大值
2.如果上述情况不满足，可能是a数组的和为b数组的次大值，去掉的元素只能为b中的最大值，只要判断是否sum等于二倍的a数组的和就行
3.如果前面都不满足，那么就不存在这样的数组。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
ll b[maxn];

void solve()
{
	int n;
	ll sum = 0;
	cin>>n;
	for(int i=1;i<=n+2;i++)
	{
		cin>>b[i];
		sum += b[i];
	}
	sort(b+1,b+1+n+2);
	sum -= b[n+2];
	ll mx = b[n+2];
	int pos = 1;
	bool flag = false;
	for(int i=1;i<=n+1;i++)
	{
		if(sum-b[i]==mx)
		{
			flag = true;
			pos = i;
			break;
		}
	}
	if(flag==false)
	{
		if(sum==2*b[n+1])
		{
			for(int i=1;i<=n;i++)
			{
				cout<<b[i]<<" ";
			}	
		}
		else  cout<<-1<<'\n';
		return ;
	}
	for(int i=1;i<=n+1;i++)
	{
		if(pos==i) continue;
		cout<<b[i]<<" ";
	}
	cout<<"\n";
}
int main()
{
	int _;
	cin>>_;
	while(_--)
	{
		solve();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Codeforces Round #719 (Div. 3)

题意：
给定一个数组，让你找满足 $a_i-a_j=i-j(i\ne j)$的对数

思路：
把所有$a_i-i$的值存起来，记录次数，结果就为所有值出现次数$C_k^2=\frac{n(n-1)}{2}$的和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5+5;
ll a[N];
void solve()
{
	map<ll,ll>mp;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		mp[a[i]-i]++;
	}
	ll ans = 0;
	for(auto i : mp)
		ans += i.second*(i.second-1)/2;
	cout<<ans<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int _;
	cin>>_;
	while(_--) solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

或者直接累加次数，因为1+2+3+…+n-1+n的前n-1项和为$\frac{n(n-1)}{2}$

#include <bits/stdc++.h> 
using namespace std;
int main() 
{	
    int t;	
    cin>>t;	
    while(t--) 
    {	
        int n;
        map<int, int> mp;
        cin>>n;
        long long ans=0;
        for(int i=1; i<=n; i++) 
        {	
            int x;
            cin>>x;
            ans+=mp[x-i]++;
        }	
        cout<<ans<<endl;
    }	
    return 0;
}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

AtCoder Beginner Contest 200 C

求一个数组中满足 $a_i-a_j(\mathrm{m}\mathrm{o}\mathrm{d}200)=0$的对数

和上一题思路一样

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
const ll inf = 0x3f3f3f3f3f3f3f;
ll a[N];

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	int n;
	cin>>n;
	map<ll,ll>mp;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		mp[a[i]%200]++;
	}
	ll ans =0;
	for(auto i : mp)
	{
		ans += i.second*(i.second-1)/2;
	}
	cout<<ans<<'\n';
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

AtCoder Beginner Contest 200 D - Happy Birthday! 2

题意：给定一个序列，找两个不同的子序列使这两个子序列的和模上200相等，输出这两个子序列的长度和在原序列中的下标。

思路：鸽巢原理：当200+个子序列存在时，一定存在两个相同的子序列的和模200相等，长度为8时，子序列的个数为256个一定存在至少两个，所以只需枚举前8个元素就可以得出答案。
二进制枚举
枚举$0\backsim 2^{cnt}-1$的数即可，cnt代表十进制表示成二进制的位数，然后对每个二进制位进行判断，存储，如果存在序列和模200一样，就输出。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<vector<int> >bk(200,vector<int>(0));
    int n;cin>>n;
    vector<int>v(n);
    for(auto &x:v) cin>>x;
    int mn = min(n,8);
    for(int i=1;i<(1<<mn);i++)
    {
        vector<int>vi;
        int t = 0;
        for(int j=0;j<mn;j++)
        {
            if(i & (1<<j))
            {
                vi.push_back(j+1);
                t += v[j];t%=200;
            }
        }
        if(bk[t].size()!=0)
        {
            cout<<"YES\n";
            cout<<bk[t].size()<<" ";
            for(auto x:bk[t]) cout<<x<<" ";
            cout<<"\n";
            cout<<vi.size()<<" ";
            for(auto x : vi) cout<<x<<" ";
            cout<<"\n";
            return 0;
        }
        else bk[t] = vi;
    }
    cout<<"NO\n";
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

Educational Codeforces Round 102 (Rated for Div. 2) B

题意：
给定两个字符串，问是否存在最小公倍字符串。存在则输出最小公倍字符串，否则输出-1
最小公倍字符串：两个字符串的任意倍数的长度叠加之后相同，即$s_1\ast k_1=s_2\ast k_2(k_1,k_2\in Z)$

思路：
两个字符串若干倍如果能够组成一个相同的字符串，那么可以构造$\frac{len2}{gcd（len1，len2）}$倍的$s_1$和$\frac{len1}{gcd（len1，len2）}$倍的$s_2$，看两者是否相等

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 25;
string dis(string a,int k)
{
    string s="";
    while(k--)s+=a;
    return s;
}
void solve()
{
    string a,b;
    cin>>a>>b;
    int len1 = a.size(),len2 = b.size();
    int g = __gcd(len1,len2);
    if(dis(a,len2/g)==dis(b,len1/g)) cout<<dis(a,len2/g)<<"\n";
    else cout<<-1<<"\n";

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Codeforces Round #693 (Div. 3) C(dp,递推)

思路：
可以考虑从后往前递推
dp[i] 代表从 i 位置开始能够获得的分数
递推方程：$dp[i]=dp[i+a[i]]+a[i]（i+a[i]<n）$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 25;

void solve()
{
    int n;cin>>n;
    vector<int >a(n);
    for(auto &x:a)cin>>x;
    vector<ll>dp(n);
    for(int i=n-1;i>=0;i--)
    {
        dp[i] = a[i];
        if(i+a[i]<n)dp[i]+=dp[i+a[i]];
    }
    cout<<*max_element(dp.begin(),dp.end())<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Codeforces Round #701 (Div. 2) A

题意：
给两个数a和b，有两种操作
第一种：让a/b(下取整)代替a
第二种：让b加一
求让a变成0的最小操作次数

需要找到最小的分界值，b每次加一，都判断一下最终的次数，求不同b值的最终次数的最小值。
b最多加到10，如果b本身大于10，就直接除求次数
mn记录最终次数最小值，cnt代表a/b的次数，bb代表b加一的次数

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;

void solve()
{
	int a,b,cnt,bb=0,ans=0;
	int mn = inf;
	cin>>a>>b;
	if(b>=10) 
	{
		while(a)
		{
			ans++;
			a/=b;
		}
		cout<<ans<<'\n';
		return ;
	}
	if(b==1) ++b,++bb;
	for(int i=1;i<10&&b<=10;i++)
	{
		cnt = 0;
		int t = a;
		while(t)
		{
			t/=b;
			cnt++;
		}
		ans = cnt+bb;
		if(ans<mn) mn = ans;
		bb++;
		b++;
	}
	cout<<mn<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
 } 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

Codeforces Round #703 (Div. 2)B(求中位数)

题意：
给定n个点的坐标，求到达所有点的权值和相等且最小的点有多少个，点可以和给定的点重合。每个点到其他点的权值为$|x_1-x_2|+|y_1-y_2|$,就是求权值和相同的点的个数

思路：
求曼哈顿距离的最小值，当坐标的y值改变后，并不影响x值的改变，所以这个二维问题可以转化为两个一维问题的求解。
其实就是求中位数
从x轴来看，如果点的个数为奇数个，那么到达所有点的x的权值和相同的点只有中间的一个数
如果为偶数的话，就是 中间的两个数之间的距离差+1 的个数
最后把x轴和y轴的情况相乘就行了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+5;
ll x[N],y[N];
ll ans;
void solve()
{
	ans = 0;
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
	sort(x+1,x+1+n);
	sort(y+1,y+1+n);
	if(n&1) ans = 1;
	else ans = (x[n/2+1]-x[n/2]+1)*(y[n/2+1]-y[n/2]+1);
	cout<<ans<<'\n';
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _;cin>>_;
	while(_--)
	{
		solve();
	}
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29