Codeforces Round 895 (Div. 3)

A题简单的模拟计算，注意上取整的实现。

B题计算每个房间对应的每个最迟时间点，在这些时间点最取最小值，保证能安全通过所有房间。

D题拿到手就可以发现是贪心，但发现两部分会有冲突，也就是重复计算的部分。故提前找到两个数的lcm然后不计算lcm的倍数，为其他参与计算的数安排剩余数种的最大值和最小值，最后需要推导一一下等差数列求和

C题是构造题，需要给出一种构造使得两个非互质数相加在目标区间，我的思路有些单一化，确定了以2为gcd来进行构造，导致需要考虑细分的情况很多，写的也很琐碎，还用到了线性筛，以及深刻体会到了能用数组就不用map，被卡死了，难受（。

大致说一下我的思路：

• 首先要找到4这个分界点，因为4能被分解2和2，这是可以给出的最小非质对了。
• 对于大于4的左边界L，我们看右边界R是不是和L重合，若不重合，则区间内一定能找到大于4的偶数sum，将其分解成4，和sum-4,他们起码有gcd是2。
• 如果重合，则这个数是偶数和刚刚一样处理即可。
• 若是奇数，我们看它是不是质数，根据数论我们可以找到如果是质数的话一定是无解的。
• 如果不是质数，则我们找到它的最小质因子f,分解成f和sum-f。
  以上是我的思路，为了保证时间效率，我提前用线性筛预处理范围内所有的质数和非质数的最小质因子，结果发现好像每次都处理也能来及，而且似乎时间还快了，我的是$O(n)$,每次现场处里$O(T*\sqrt{n})$。

// Problem: C. Non-coprime Split
// Contest: Codeforces - Codeforces Round 895 (Div. 3)
// URL: https://codeforces.com/contest/1872/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 1e7;
const int M = 1e7+ 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;


bool st[N];
int mp[N];
void pre(){
	for(int i=2;i<=N;i++){
		if(st[i])continue;
		else{
			for(int j=2*i;j<=N;j+=i){
				st[j]=true;
				mp[j]=i;
			}
		}
	}
}
// void ans(){
	// for (int i = 2; i <= N; i ++ )
    // {
        // if (!st[i]) primes[cnt ++ ] = i;
        // for (int j = 0; primes[j] <= N / i; j ++ )
        // {
            // st[primes[j] * i] = true;
          // mp[primes[j] * i]= primes[j];
            // if (i % primes[j] == 0) {
//             	
            // break;
            // }
//            
        // }
    // }
// }
void solve(){
	int l,r;
	cin>>l>>r;
	if(r<=3){cout<<-1<<endl;return;}
	if(l<=4&&r>=4){cout<<2<<" "<<2<<endl;return ;}
	if(l!=r){
		if(l%2==0){cout<<4<<' '<<l-4<<endl;return ;}
		else {
			cout<<4<<' '<<l-3<<endl;return ;
		}
	}
	else {
		if(l%2==0){cout<<4<<' '<<l-4<<endl;return ;}
		else {
			if(st[l]==false){
				cout<<-1<<endl;return;
			}
			else {
				int f=mp[l];
				cout<<f<<" "<<l-f<<endl;
				return ;
			}
		}
	}
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   cin>>t;
pre();
    while (t--) {
    
solve();
    }
    return 0;
}

这样思考时间花费太多，如果直接暴力枚举区间内的数，并且在线分解也是可以的。
给出jls的代码,就是对于区间内的每个数，直接枚举它能的最小质因子，然后直接拆分，其实也就是我最后对奇合数的处理思路，只不过我没想到可以统一处理，还是思维局限了，从小点出发，没能将大点拆解后再统一回来。

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int l, r;
    std::cin >> l >> r;
    
    for (int i = std::max(4, l); i <= r; i++) {
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                std::cout << j << " " << i - j << "\n";
                return;
            }
        }
    }
    std::cout << -1 << "\n";
}

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

E题标题是数据结构，果然实际上不用线段树就可以做，主要用到了异或的性质和前缀和动态维护。

还是分析一下本题的特点，边改边查，具体是在线的区间修改和整体查询，我们提前预处理出异或前缀和，以及0的对应异或值s0，1的对应异或值s1.
每次修改我们得到改变的数值sum[r]^sum[l-1],s0异或上这个值,相当于在区间内把变成1的值给再异或一次消去,变成0的值添加进来,所以总体来看就是异或这个值,这就是总体观.所以我们动态维护s0,s1.

// Problem: E. Data Structures Fan
// Contest: Codeforces - Codeforces Round 895 (Div. 3)
// URL: https://codeforces.com/contest/1872/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int sum[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	string s;
	cin>>s;
int s0=0,s1=0;
	for(int i=1;i<=s.length();i++){
		sum[i]=sum[i-1]^a[i];
		if(s[i-1]=='0'){
			s0^=a[i];
			
		}
		else {
			s1^=a[i];

		}
	}
	int q;
	cin>>q;
	while(q--){
		int num;
		cin>>num;
		if(num==1){
			int l,r;
			cin>>l>>r;
			int tmp=sum[r]^sum[l-1];
			s1^=tmp;s0^=tmp;
		}
		else {
			int x;
			cin>>x;
			if(x==0)cout<<s0<<" ";
			else cout<<s1<<" ";
		}
	}
	cout<<endl;
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   cin>>t;

    while (t--) {
solve();
    }
    return 0;
}

F题是图论,对于目前套模板都困难的我,对于这题有些想法,但确实想不到怎么做,确实需要积累实现方式,因为你只有知道有哪些实现方式,才能去想这题怎么做.(个人观点’

F题动物间的害怕关系会形成一张有向图,我们规定一个点的前驱是这个点的食物,一个点的后继是这个点所害怕的动物,为了拿到最多的钱,我们这样的规定方式有利于找到卖出顺序,如果不会形成环,那自然用拓扑排序思想找到入度为0的点即可
那如果局部形成环呢,我们考虑先把环外点卖出,因为这不会相互影响其他动物的价格.
但终究我们需要找到一个破环点,也就意味着这个点的前驱将失去它最害怕的动物,最终只能卖低价,所以我们只需要找到环中价格最小的动物即可找到答案.
但本题可能会形成多个局部环,我们需要重复多次上述破环操作.
实现过程参考了jls的,建议时常复习一下

// Problem: F. Selling a Menagerie
// Contest: Codeforces - Codeforces Round 895 (Div. 3)
// URL: https://codeforces.com/contest/1872/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;



void solve(){
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]--;
	}
	vector<int>c(n);
	for(int i=0;i<n;i++){
		cin>>c[i];
	}
	vector<int>deg(n);
	for(int i=0;i<n;i++){
		deg[a[i]]++;
	}
	vector<int>ans;
	vector<bool>vis(n);
	auto dfs=[&](auto self,int x)->void{
		ans.push_back(x);
		vis[x]=true;
		if(--deg[a[x]]==0){
			self(self,a[x]);
		}
	};
	for(int i=0;i<n;i++){
		if(deg[i]==0&&!vis[i]){
			dfs(dfs,i);
		}
	}
	for(int i=0;i<n;i++){
		if(vis[i])continue;
		vector<int>b,ca;
		for(int j=i;!vis[j];j=a[j]){
			vis[j]=true;
			b.push_back(j);
			ca.push_back(c[j]);
		}
		int p=min_element(ca.begin(),ca.end())-ca.begin();
		for(int j=0;j<b.size();j++){
			ans.push_back(b[(j+1+p)%b.size()]);
		}
	}
	for(int i=0;i<n;i++)cout<<ans[i]+1<<" ";
	cout<<endl;
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   cin>>t;

    while (t--) {
solve();
    }
    return 0;
}

G题是典型的一类题,对于某个性质,符合这个性质的怎么处理,不符合的怎么处理,像这样划分以后有可能就可以使用暴力了.

在本题中最关键的就是1元素,因为如果修改区间内如果含1,1的贡献会从1变为0,也就是1没有贡献.所以最佳区间的左边界l是第一个非1的位置,右边界l是最后一个非1的位置.所以最终答案的位置一定是非1元素的位置,如果直接暴力枚举,总共枚举次数是n^2次,每一次计算值可以用前缀和优化成o(1),但这依然会超时.其实我们能发现当非1的数量多到可以让我们忽略损失的1的数量所带来的贡献时,我们可以直接选择
最佳区间的左边界l是第一个非1的位置,右边界l是最后一个非1的位置
那怎么样算足够多时,忽略的1的数量最多是2e5,

上面这个方程是得出为什么 **性质设置为乘积大于4e5,**方程中x表示数组中1的数量,不等式是假设当前全部乘起来的值大于全部加起来的值得到的.

那如果不满足这个性质呢?

我们考虑
我们考虑数组中都是最小的非1数也就是2的数量,总共也才18个,不然就会满足上面的性质.
此时我们再暴力枚举,数据范围才20不到,$O(n^2)$的复杂度可以接受.

// Problem: G. Replace With Product
// Contest: Codeforces - Codeforces Round 895 (Div. 3)
// URL: https://codeforces.com/contest/1872/problem/G
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
    # define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 2e5 + 10;

const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int s[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		}
	int l=1;int r=n;
	while(l<=n&&a[l]==1)l++;
	while(r>=1&&a[r]==1)r--;
	if(l==n+1){
		cout<<1<<" "<<1<<endl;
		return ;
	}
	int res=1;
	bool flag=false;
	for(int  i=1;i<=n;i++){
		if(a[i]!=1){
			if(res*a[i]>=4e5){
				flag=true;
				break;
			}
			res*=a[i];
		}
	}
	if(flag){
		cout<<l<<" "<<r<<endl;
		return ;
	}
	//cerr<<l<<" "<<r<<endl;
	vector<int>b;
	b.push_back(0);
	for(int i=1;i<=n;i++){
		if(a[i]!=1)b.push_back(i);
	}
	
	int st=1,ed=1;
	int mx=s[n];
	int m=b.size()-1;
	for(int i=1;i<=m;i++){
		int res=1;
		int posl=b[i];
		for(int j=i;j<=m;j++){
			int posr=b[j];
			res*=a[posr];
			int tmp=s[n]-(s[posr]-s[posl-1])+res;
			if(mx<tmp){
				mx=tmp;
				st=posl;
				ed=posr;
			}
			//cerr<<mx<<endl;
		}
	}
	cout<<st<<" "<<ed<<endl;
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   cin>>t;

    while (t--) {
solve();
    }
    return 0;
}