Codeforces Round 895 (Div. 3)
title: Codeforces Round 895 (Div. 3)
categories:
- ICPC
tags:
- null
abbrlink: 5848dec6
date: 2024-12-16 00:00:00
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;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！