Codeforces Round 895 (Div. 3)
A. Two Vessels
思路：
我们可以发现当在 a 拿 c 到 b 其实可以让他们差值减少 2c，所以对a和b的差值除以2c向上取整即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define x first
#define y second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t;
vector<int>del;
int a[200010],b[200010];
int prime[N];
bool st[N];
map<int,int>mp;
void solve(){int a,b,c;cin>>a>>b>>c;int x=abs(a-b);int y=x/(2*c);if(x%(2*c))y++;cout<<y<<endl;
}
signed main(){cin>>t;while(t--)solve();
}
B. The Corridor or There and Back Again
思路：
我们可以发现我们当前能到达最远是 d+（s-1）/ 2，然后就是找这些里面最小的值即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define x first
#define y second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t;
vector<int>del;
int a[200010],b[200010];
int prime[N];
bool st[N];
map<int,int>mp;
void solve(){int n;cin>>n;int a,b;int ans=10000000000;rep(i,0,n-1){cin>>a>>b;ans=min(ans,a+(b-1)/2);}cout<<ans<<'\n';
}
signed main(){cin>>t;while(t--)solve();
}
C. Non-coprime Split
思路：
这里我们分三种情况：
① 如果a ！= b，我们就能找一个偶数，输出2和偶数-2
② 如果a== b，如果a和b不是质素那么就直接找出他的最小的约数即可
③ 如果a ==b，如果a和b是质素那么就输出-1
还有些细节注意下就行
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define x first
#define y second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t;
vector<int>del;
int a[200010],b[200010];
int prime[N];
bool st[N];
map<int,int>mp;
bool isPrime(int n)
{if (n <= 3)//当n不大于3时只有1不是素数return n > 1;if (n % 6 != 1 && n % 6 != 5)//只有6i+1和6i+5可能是素数return false;for (int i = 5; i <= sqrt(n); i += 6){if (n % i == 0 || n % (i + 2) == 0)return false;}return true;
}
void solve(){int a,b;cin>>a>>b;if(a==b&&a<=2){cout<<-1<<endl;return ;}if(a==1&&b==3||a==1&&b==2){cout<<-1<<endl;return ;}if(a==b&&!isPrime(a)){rep(i,2,sqrt(a)){if(a%i==0){cout<<i<<" "<<a-i<<endl;return ;}}return ;}else if(a==b&&isPrime(a)){cout<<-1<<endl;return ;}else{if(b-1==2){cout<<-1<<endl;return ;}if(b%2==0){cout<<2<<" "<<b-2<<endl;}else cout<<2<<" "<<b-2-1<<endl;}
}
signed main(){cin>>t;while(t--)solve();
}
D. Plus Minus Permutation
思路：
我们可以发现如果某个数能被x和y同时整除的话对答案没有贡献，所以，我们只需要找到在x中的数不在y中的个数num1，在y中的数不在x中的数num2，然后根据前n项和公式sum1-sum2即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){int t;cin>>t;while(t--){int n,x,y;cin>>n>>x>>y;int d=__gcd(x,y);d=x/d*y;int c=n/d;x=n/x-c;y=n/y-c;cout<<x*(n-x+1+n)/2-(1+y)*y/2<<'\n';}
}
E. Data Structures Fan
思路1：线段树
没补
思路2：异或性质
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
void solve()
{int n; cin >> n;vector<int> a(n + 10),sum(n+10);for (int i = 1; i <= n; i++) cin >> a[i],sum[i]=sum[i-1]^a[i];string op; cin >> op;int sum1 = 0, sum2 = 0;for (int i = 0; i < n; i++){if (op[i] == '0') sum2 ^= a[i + 1];else sum1 ^= a[i + 1];}//cout<<"sum== "<<sum1<<" "<<sum2<<endl;int q; cin >> q;while (q--){int cnt;cin >> cnt;if (cnt == 2){int x; cin >> x;if (x == 0) cout << sum2 << ' ';else cout << sum1 <<' ';}else{int l, r; cin >> l >> r;sum1 ^= sum[r] ^ sum[l - 1];sum2 ^= sum[r] ^ sum[l - 1];}}cout<<endl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t; cin >> t;while (t--)solve();
}
F. Selling a Menagerie
思路：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int a[N], c[N];
int d[N], minn = 1e9 + 10, id = -1;
bool st[N];
void dfs(int u)
{if (st[u]) return;st[u] = true;int j = a[u];if (minn > c[j]) minn = c[j], id = j;dfs(j);
}
void solve()
{queue<int> q;vector<int> ans;int n; cin >> n;for (int i = 0; i <= n; i++) st[i] = false, d[i] = 0;for (int i = 1; i <= n; i++) cin >> a[i], d[a[i]]++;for (int i = 1; i <= n; i++) cin >> c[i];for (int i = 1; i <= n; i++)if (!d[i])q.push(i);while (q.size()){int t = q.front();ans.push_back(t);st[t] = true;q.pop();if (--d[a[t]] == 0) q.push(a[t]);}for (int i = 1; i <= n; i++)if (!st[i]){minn = c[i];id = i;dfs(i);//找最小的贡献int x = a[id];do{ans.push_back(x);x = a[x];} while (x != a[id]);}for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';cout << endl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t; cin >> t;while (t--)solve();
}
G. Replace With Product
思路：
#include <bits/stdc++.h>
using namespace std;
#define int long long
// const int N = 1e5 + 10;const int N = 2e5 + 10, M = 4e5 + 10;int n, a[N], b[N], idx;void solve()
{cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];int l = 1, r = n;while (a[l] == 1 && l < r)l++;while (a[r] == 1 && l < r)r--;int res = 1;for (int i = l; i <= r; ++i){res *= a[i];if (res > 1e9){cout << l << " " << r << "\n";return;}}idx = 0;int sum = 0;for (int i = 1; i <= n; ++i){if (a[i] > 1)b[++idx] = i;sum += a[i];}int ans = sum, ansl = 1, ansr = 1;for (int i = 1; i <= idx; ++i){res = 1;l = b[i];int s = 0;for (int j = i; j <= idx; ++j){res *= a[b[j]];r = b[j];s += a[b[j]];int val = sum - s - (r - l + 1 - (j - i + 1)) + res;if (val > ans){ans = val;ansl = l, ansr = r;}}}cout << ansl << " " << ansr << "\n";
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t; cin >> t;while (t--)solve();
}
