1872A - Two Vessels
略
1872B - The Corridor or There and Back Again (思维)
题意
有一条无限长的走廊,有一些陷阱,这些陷阱会在你到达之后开始倒计时;你需要走出去然后走回来问你最远能走多远。由于每个陷阱都是独立的,直接取min就行,不需要模拟整个过程。
void slove(){
int n; cin>>n;
int ans=INT32_MAX;
for(int i=0;i<n;i++){
int d,s; cin>>d>>s;
ans=min(ans,d+(s-1)/2);
}
cout<<ans<<endl;
}
1872C - Non-coprime Split (数论+ 构造)
题意
给出l,r;你需要找出a,b满足:
如果[l,r]内存在合数x的话,那么有
x
=
m
∗
n
=
(
1
+
m
−
1
)
∗
n
=
n
+
n
∗
(
m
−
1
)
,
m
>
1
,
n
>
1
x = m*n = (1+m-1)*n = n+n*(m-1) , m>1,n>1
x=m∗n=(1+m−1)∗n=n+n∗(m−1),m>1,n>1
让a=n,b=x-n,刚好可以满足两个要求。
void slove(){
int l,r; cin>>l>>r;
for(int i=max(4,l);i<=r;i++){
for(int j=2;j*j<=i;j++){
if(i%j==0){
printf("%d %d\n",j,i-j);
return;
}
}
}
printf("-1\n");
}
1872D - Plus Minus Permutation (贪心)
题意
给出一个长度为n的序列{1,2,3…}和两个整数x,y;如果数组下标i(从 1开始)和x能整除那么分数要加a[i],如果下标j能和y整除那么分数要减去a[j]。你可以随便排列这个序列,求最大分数。
思路
优先把大的排在和x整除,而且不和y整除的位置;优先把小的排在和y整除,而且不和x整除的位置上,其他的无所谓。最后发现由于题目给的是一个等差序列,其实相当于两个等差数组求和。
ll lcm(ll x,ll y){
return x*y/__gcd(x,y);
}
void slove(){
ll n,x,y; cin>>n>>x>>y;
ll pc=n/x,nc=n/y,cc=n/lcm(x,y);
pc-=cc; nc-=cc;
ll ans=(n+n-pc+1)*pc/2-(1+1+nc-1)*nc/2;
cout<<ans<<endl;
}
1872E - Data Structures Fan (补)
题意:
给出一个长度为n的数组a和一个长度也为n的01串s。然后有两种操作:
当时看了觉得是线段树,但是没想出来怎么做,没想好区间要维护什么信息。如果区间只保存异或和的话好像实现不了区间修改。
思路
区间需要维护两个信息:
修改就swap一下就好了。
using namespace std;
const int N=1e5+10;
int a[N],b[N],mask[N<<2];
pair<int,int> tree[N<<2];
void build(int l,int r,int p){
mask[p]=0;
if(l==r){
if(!b[l]) {tree[p].first=a[l]; tree[p].second=0;}
else {tree[p].first=0; tree[p].second=a[l];}
}else{
int mid=(l+r)>>1;
build(l,mid,p<<1); build(mid+1,r,p<<1|1);
tree[p].first=tree[p<<1].first^tree[p<<1|1].first;
tree[p].second=tree[p<<1].second^tree[p<<1|1].second;
}
}
void push_down(int p,int m){
if(m<=1) return;
mask[p<<1]+=mask[p]; mask[p<<1|1]+=mask[p];
if(mask[p]%2){
swap(tree[p<<1].first,tree[p<<1].second);
swap(tree[p<<1|1].first,tree[p<<1|1].second);
}
mask[p]=0;
}
void update(int cl,int cr,int p,int l,int r){
if(cl>=l&&cr<=r){
mask[p]++;
swap(tree[p].first,tree[p].second);
}else{
push_down(p,cr-cl+1);
int mid=(cl+cr)>>1;
if(mid>=l) update(cl,mid,p<<1,l,r);
if(mid+1<=r) update(mid+1,cr,p<<1|1,l,r);
tree[p].first=tree[p<<1].first^tree[p<<1|1].first;
tree[p].second=tree[p<<1].second^tree[p<<1|1].second;
}
}
pair<int,int> query(int cl,int cr,int p,int l,int r){
if(cl>=l&&cr<=r){
return tree[p];
}else{
push_down(p,cr-cl+1);
pair<int,int> res;
int mid=(cl+cr)>>1;
if(mid>=l){
pair<int,int> lres=query(cl,mid,p<<1,l,r);
res.first^=lres.first; res.second^=lres.second;
}
if(mid+1<=r) {
pair<int,int> rres=query(mid+1,cr,p<<1|1,l,r);
res.first^=rres.first; res.second^=rres.second;
}
tree[p].first=tree[p<<1].first^tree[p<<1|1].first;
tree[p].second=tree[p<<1].second^tree[p<<1|1].second;
return res;
}
}
void slove(){
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
string s; cin>>s;
for(int i=1;i<=n;i++) b[i]=s[i-1]-'0';
build(1,n,1);
int q; cin>>q;
for(int i=0;i<q;i++){
int op; cin>>op;
if(op==1){
int l,r; cin>>l>>r;
update(1,n,1,l,r);
}else{
int v; cin>>v;
pair<int,int> res=query(1,n,1,1,n);
if(v==0){
printf("%d ",res.first);
}else{
printf("%d ",res.second);
}
}
}
printf("\n");
}
int main(){
// freopen("input.txt","r",stdin);
int t; cin>>t;
while(t--){
slove();
}
}
另外,慎用memset,这题如果用memset初始化数据会卡TLE。
看了别人的题解,发现前缀和也可以。因为x^LR区间的异或和正好对应翻转的那个动作。
const int N=1e5+10;
int a[N],b[N],psum[N];
void slove(){
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
string s; cin>>s;
for(int i=1;i<=n;i++) b[i]=s[i-1]-'0';
int sum0=0;
psum[0]=0;
for(int i=1;i<=n;i++) {
psum[i]=psum[i-1]^a[i];
if(!b[i]) sum0^=a[i];
}
int q; cin>>q;
for(int i=0;i<q;i++){
int op; cin>>op;
if(op==1){
int l,r; cin>>l>>r;
sum0^=(psum[r]^psum[l-1]);
}else{
int v; cin>>v;
if(v==0) printf("%d ",sum0);
else printf("%d ",psum[n]^sum0);
}
}
printf("\n");
}
1872F - Selling a Menagerie (补)
题意
一个动物A害怕另一个动物B,我们尽量要让A排在B前面,这样可以获得c[i]的额外奖励;求最佳排列。
思路
如果没有环直接拓扑,但是这题是存在环的。
const int N=1e5+10;
struct edge{
int u,v,w,flag;
};
int d[N],vis[N];
void slove(){
int n; cin>>n;
fill(d,d+n+1,0); fill(vis,vis+n+1,0);
vector<edge> es(n+1);
for(int i=1;i<=n;i++){
int v; cin>>v;
es[i]={i,v,0,0};
d[v]++;
}
for(int i=1;i<=n;i++) cin>>es[i].w;
queue<int> q;
for(int i=1;i<=n;i++){
if(d[i]==0) q.push(i);
}
while(!q.empty()){
int u=q.front(); q.pop();
vis[u]=1;
auto e=es[u];
if(--d[e.v]==0){
q.push(es[u].v);
}
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
vis[i]=2;
int j=es[i].v;
auto de=es[i];
for(;j!=i;){
vis[j]=2;
if(es[j].w<de.w) de=es[j];
j=es[j].v;
}
es[de.u].flag=1;
}
fill(d,d+n+1,0);
for(int i=1;i<=n;i++){
if(!es[i].flag) d[es[i].v]++;
}
for(int i=1;i<=n;i++) if(d[i]==0) q.push(i);
vector<int> ans;
while(!q.empty()){
int u=q.front(); q.pop();
ans.push_back(u);
auto e=es[u];
if(e.flag==0){
if(--d[e.v]==0) q.push(e.v);
}
}
for(int x:ans) printf("%d ",x);
printf("\n");
}
看了别人的题解,后面两步其实可以简化,直接从环的最短边dfs,不用把环破掉再拓扑一次。