Codeforces Round 962 (Div. 3)

A

贪心思考：

先除4再除2即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
	int n;
	cin>>n;
	cout<<n/4+n%4/2<<'\n';
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

B

枚举时候每次加k即可，这样就满足了。

（楞了好一会，还想转一维度，属于是nt了）

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+10;
char a[N][N];
void solve()
{
int n;
cin>>n;
int k;
cin>>k;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j++)
	{
		cin>>a[i][j];
	}
}
int h=n/k;
for(int i=1;i<=n;i+=k)
{
	for(int j=1;j<=n;j+=k)
	{
		if(a[i][j]=='1')
		{
			cout<<1;
		}
		else
		{
			cout<<0;
		}
	}
	cout<<'\n';
}


}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

C

本题只需要比较l-r的26个字母即可。

用稳定的前缀和即可做到O(1)得到l-r中所有字母的个数了，最后记得/2即可。

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
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+100;
int a[N][30];
int b[N][30];

void solve()
{
	int n;
	cin>>n;
	int q;
	cin>>q;
string s;
string h;
cin>>s>>h;
int x=s.length();
s=" "+s;
h=" "+h;
for(int i=1;i<=x;i++)
{
for(int j=0;j<=25;j++)
{
	if(s[i]=='a'+j)
	{
		a[i][j]=a[i-1][j]+1;
	}
	else
	{
		a[i][j]=a[i-1][j];
	}
	if(h[i]=='a'+j)
	{
		b[i][j]=b[i-1][j]+1;
	}
	else
	{
		b[i][j]=b[i-1][j];
	}
}
}
for(int i=1;i<=q;i++)
{
	int l,r;
	cin>>l>>r;
	int ans=0;
	for(int j=0;j<=25;j++)
	{
		if(a[r][j]-a[l-1][j]!=b[r][j]-b[l-1][j])
		{
			ans+=abs(a[r][j]-a[l-1][j]-b[r][j]+b[l-1][j]);
		}
	}
	cout<<ans/2<<'\n';
}


}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

D

本题考察的就是枚举之技巧。

i从1-n

j怎么优化：观察i*j<=n即可优化到O(nlogn)

最后再看k，k可以直接O(1)计算出来，判断是否大于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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+100;


void solve()
{
ll n,x;
cin>>n>>x;
ll ans=0;
//三个数相加和三个数相乘起来
//枚举以下a,由于a*b<=n,然后枚举b
//之后由于(n-(a*b))/(a+b)就是C,x-(a+b)也是C，只需要取个最小即可。
for(ll i=1;i<=n;i++)
{
	for(ll j=1;j<=n/i;j++)
	{
		ll c1=1ll*(n-i*j)/(i+j);
		ll c2=x-i-j;
		if(c1>0&&c2>0)
		{
			ans+=min(c1,c2);
		}
	}
}
cout<<ans<<'\n';
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

E

小技巧1：前缀和

小技巧2：前缀和中0记作-1，1记作+1，这样会更方便后面的操作

之后就是直接累计答案即可

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+100;
ll sum[N];
const ll mod=1e9+7;
void solve()
{
string s;
cin>>s;
int len=s.length();
s=" "+s;
for(int i=1;i<=len;i++)
{
if(s[i]=='1')
{
	sum[i]=sum[i-1]+1;
}
else
{
	sum[i]=sum[i-1]-1;
}
}
ll ans=0;
map<ll,ll>mp;
mp[0]=1;
for(int i=1;i<=len;i++)
{
	ans=(((mp[sum[i]]%mod)*(len-i+1)%mod)%mod+ans%mod)%mod;
	mp[sum[i]]+=i+1;
}
cout<<ans%mod<<'\n';
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

F

这个要选多少以上的a[i]是具有单调性的，因此可以二分这个选择的阈值。

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
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+100;
ll a[N];
ll b[N];
ll sum[N];
const ll mod=1e9+7;
void solve()
{
ll n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
	cin>>a[i];
}
for(int i=1;i<=n;i++)
{
	cin>>b[i];
}
//感觉弄个堆就结束了
ll l=0;
ll r=1e9;
ll ans=0;
while(l<=r)
{
	ll mid=(l+r)>>1;
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=mid)
		{
			sum+=(a[i]-mid)/b[i]+1;
		}
	}
	if(sum>=k)
	{
		ans=mid;
		l=mid+1;
	}
	else
	{
		r=mid-1;
	}
}
ll sum=0;
for(int i=1;i<=n;i++)
{
	if(a[i]>=ans+1)
	{
		ll x=(a[i]-ans-1)/b[i]+1;
		ll t=a[i];
		ll tm=a[i]-(x-1)*b[i];
		sum+=(a[i]+tm)*x/2;
		k-=x;
	}
}
sum+=k*ans;
cout<<sum<<'\n';
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

G

题目解析

题目描述：

在梦想之地 Penacony，有 n 座房子和 n 条道路。每条道路连接着相邻的两座房子，并且第 n 座房子和第 1 座房子之间也有一条道路形成环形。由于财务危机，只能维护一部分道路，但要求朋友之间必须有可通行的路径。求最少需要维护的道路数量。

输入描述：

  • 第一行是测试用例数 T。
  • 每个测试用例包含：
    • 两个整数 n 和 m，表示房子的数量和朋友关系的数量。
    • 接下来 m 行，每行两个整数 a 和 b，表示房屋 a 和房屋 b 之间存在友谊关系。

输出描述：

  • 对于每个测试用例，输出一个整数，表示最少需要维护的道路数量。

思路解析

题目要求在一个环形图中维护最少的道路以确保给定的朋友关系之间有路径。我们需要找到使得维护的道路数量最少的方法。

步骤：

  1. 构建无向图：将每个测试用例的输入构建成一个环形无向图。
  2. 随机赋权哈希：将每个点赋予随机权值，以便我们可以使用前缀哈希进行区间比较。
  3. 前缀哈希：通过异或操作计算前缀哈希值，帮助确定哪些区间可以被覆盖。
  4. 查找最长可选区间：找到最长的连续区间，这些区间的哈希值相同，表示这些区间可以被覆盖。
  5. 贪心选择：最后选择贪心地不覆盖最长的区间，计算需要维护的最少道路数量。

时间复杂度分析

  • 输入处理：每个测试用例的读取和初始化时间复杂度为 O(n + m)。
  • 随机赋权：每对朋友关系赋权时间复杂度为 O(m)。
  • 前缀哈希计算：时间复杂度为 O(n)。
  • 查找最长区间：使用 map 查找最长区间时间复杂度为 O(n)。

综合分析，最坏情况下总时间复杂度为 O(T * (n + m))，其中 T 是测试用例数，总和不超过 2 * 10^5，可以接受。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int long long
const int N=1e6+100;
ll val[N];
const ll mod=1e9+7;
uniform_int_distribution<int> qwq(1, 400000000000000000);
mt19937_64 mt;
void solve()
{
   		int n, m;
        cin >> n >> m;
        // 初始化 val 数组
        fill(val, val + n + 1, 0);
        // 处理朋友关系，赋予随机权值并计算哈希
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            int t = qwq(mt);  // 生成随机权值
            val[a] ^= t;
            val[b] ^= t;
        }

        // 使用 map 记录前缀哈希值出现次数
        map<int, int> mp;
        int mx = 0;

        // 计算前缀异或哈希值，并找到最长连续区间
        for (int i = 1; i <= n; ++i) {
            val[i] ^= val[i - 1];  // 计算前缀哈希
            mx = max(mx, ++mp[val[i]]);
        }

        // 输出结果，n 减去最长连续区间长度
        cout << n - mx << "\n";
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}