20230307
A
根据题面信息可知图为奇环树，考虑将环上的点和树上的点分开处理，预处理出来环上的点。
如果先去想如何处理树上的点，可以想到一种\(dp\)方法，设\(f_{i,0/1}\)表示当前点为\(i\),对于\(i\)向父亲连的边，值为\(w/1\)的一段在\(i\)上是否可行，对于每一个点开一个\(map\),用来存该点上所有值。
这一做法是正确的，但过于麻烦。
如果先考虑环，容易发现环上的边的方向全部相同，也就是说环上的点至少会有一个\(1\)和一个\(w_i\),那么连接他与他儿子的边的“\(1\)”一段应当在他的儿子上，这样其子树中所有边的方向都是确定的，那么我们枚剧环的方向，用\(map\)来存每一个点上的所有值，不冲突就输出所有边的方向，冲突就换另一种方向，仍冲突则无解，复杂度为\(O(nlogn)\)。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
struct edge{
int v,w,id;
};
vector<edge> e[N];
int n;
int dfn[N],tim;
int loop[N],tot,on[N],pa[N];
edge pre[N],nxt[N],pl[N];
void get(int u){
dfn[u]=++tim;
for(auto i:e[u]){
int v=i.v;
if(v==pa[u]) continue;
if(dfn[v]){
if(dfn[v]<dfn[u]) continue;
loop[++tot]=v;
pre[tot]=i;
pre[tot].v=u;
on[v]=1;
while(v!=u){
loop[++tot]=pa[v];
pre[tot]=pl[v];
v=pa[v];
on[v]=1;
}
}
else pa[v]=u,pl[v]=i,get(v);
}
}
int ans[N];
map<int,int> mp[N];
bool boom;
void dfs(int u,int fa){
for(auto i:e[u]){
int v=i.v,w=i.w,id=i.id;
if(on[v]||v==fa) continue;
ans[id]=v;
if(mp[u].find(w)!=mp[u].end()){
boom=1;
return;
}
mp[u][w]=1;
dfs(v,u);
}
}
int main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
scanf("%d",&n);
int u,v,w;
// bool _=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&u,&v,&w);
// if(i==1&&n==2000&&u==1577) _=1;
e[u].push_back({v,w,i});
e[v].push_back({u,w,i});
}
get(1);
for(int i=1;i<=tot;i++)
nxt[i]=pre[i+1];
nxt[tot]=pre[1];
// if(_)
// printf("%d\n",tot);
// for(int i=1;i<=tot;i++) printf("%d ",loop[i]);
// printf("\n");
// for(int i=1;i<=tot;i++) printf("%d %d %d\n",pre[i].v,pre[i].w,pre[i].id);
loop[0]=loop[tot],loop[tot+1]=loop[1];
for(int i=1;i<=tot;i++){
mp[loop[i]].clear();
ans[pre[i].id]=loop[i-1];
mp[loop[i]][pre[i].w]=1;
dfs(loop[i],0);
if(boom) break;
}
if(!boom){
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
// printf("?\n");
for(int i=1;i<=n;i++) mp[i].clear();
boom=0;
for(int i=1;i<=tot;i++){
mp[loop[i]].clear();
ans[nxt[i].id]=loop[i+1];
mp[loop[i]][nxt[i].w]=1;
dfs(loop[i],0);
if(boom) break;
}
if(!boom){
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
printf("impossible\n");
}
B
\(30pts:\)直接维护两个存钱罐和所有的值，但\(multiset\)维护会\(TLE\)
\(100pts:\)每次插入点的时候更新贡献，记录每个\(x\)的最小\(y\),在线段树上二分；删除操作用线段树分治，可以旋转坐标系\((x,y)\)->\((x-y,y)/(y-x,x)\),在叶子节点上开\(multiset\),复杂度为\((nlogn)\).
code:
#include<bits/stdc++.h>
using namespace std;
const int N=2.5e5+5;
const int inf=0x3f3f3f3f;
int n,m=2.5e5;
int f[N<<4],g[N<<4][2],h[N<<4][2];
multiset<int> s[N<<2][2];
void pushup(int rt){
f[rt]=min(f[rt<<1],f[rt<<1|1]);
for(int i=0;i<2;i++){
g[rt][i]=min(g[rt<<1][i],g[rt<<1|1][i]);
h[rt][i]=min(h[rt<<1][i],h[rt<<1|1][i]);
f[rt]=min(f[rt],g[rt<<1][i]+h[rt<<1|1][i^1]);
}
}
void update(int rt,int l,int r,int k,int x,int y,int op){
if(l==r){
if(op==1) s[x+m][k].insert(y);
else s[x+m][k].erase(s[x+m][k].find(y));
if(s[x+m][k].empty()) g[rt][k]=h[rt][k]=inf;
else {
g[rt][k]=*s[x+m][k].begin();
h[rt][k]=g[rt][k]+x;
}
if(h[rt][0]<inf&&h[rt][1]<inf) f[rt]=h[rt][0]+g[rt][1];
else f[rt]=inf;
return;
}
int mid=l+r>>1;
if(x<=mid) update(rt<<1,l,mid,k,x,y,op);
else update(rt<<1|1,mid+1,r,k,x,y,op);
pushup(rt);
}
int main(){
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
scanf("%d",&n);
memset(f,0x3f,sizeof f);
memset(g,0x3f,sizeof g);
memset(h,0x3f,sizeof h);
int op,k,x,y;
while(n--){
scanf("%d%d%d%d",&op,&k,&x,&y);
k&=1;
if(k) update(1,-m,m,k,x-y,y,op);
else update(1,-m,m,k,y-x,x,op);
printf("%d\n",f[1]<inf?f[1]:-1);
}
return 0;
}
C
code:
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int T;
int n,id,t,cnt,tot,a[N],pos[N],ans[N];
int vis[N];
vector<int> vec[N];
void dfs1(int u){
if(!vis[u]){
vis[u]=1;
dfs1(u>>1);
a[++tot]=u;
}
u|=(1<<t-1);
if(!vis[u]){
vis[u]=1;
dfs1(u>>1);
a[++tot]=u;
}
}
void dfs2(int u){
//printf("u:%d\n",u);
vec[id].push_back(u);
if(!vis[u]){
vis[u]=1;
dfs2(u>>1);
}
u|=(1<<t);
if(!vis[u]){
vis[u]=1;
dfs2(u>>1);
}
}
void solve(){
memset(pos,0,sizeof pos);
scanf("%d",&n);
t=1;
while((1<<t)<=n-t+1) ++t;
--t;
if(t<2){
if(n==1) printf("0\n");
if(n==2) printf("10\n");
if(n==3) printf("101\n");
if(n==4) printf("0010\n");
return;
}
n-=(1<<t)+t-1;
tot=0;
memset(vis,0,sizeof vis);
dfs1(0);
reverse(a+1,a+tot+1);
//printf("%d\n",tot);
//for(int i=1;i<=tot;i++) printf("%d ",a[i]);
//printf("\n");
//printf("%d\n",n);
if(!n) cnt=tot,memcpy(ans,a,sizeof a);
else {
memset(vis,0,sizeof vis);
for(int i=1;i<=tot;i++)
vis[(a[i%tot+1]<<1)|(a[i]&1)]=1;
//printf("???%d\n",vis[0]);
cnt=id=0;
for(int i=1;i<=tot;i++){
vec[++id].clear();
dfs2(a[i]);
vec[id].pop_back();
//printf("%d\n",vec[id].size());
if(vec[id].empty()){
--id;
continue;
}
if(vec[id].size()>=n){
for(int j=i%tot+1;j!=i;j=j%tot+1){
if(pos[j])
for(int k:vec[pos[j]])
ans[++cnt]=k;
ans[++cnt]=a[j];
}
vec[id].push_back(a[i]);
for(int j=0;j<=n;j++) ans[++cnt]=vec[id][j];
break;
}
n-=vec[id].size(),pos[i]=id;
}
}
//printf("%d %d\n",t,cnt);
for(int i=1;i<cnt;i++)
printf("%c",(ans[i]&1)+'0');
for(int i=0;i<t;i++)
printf("%c",((ans[cnt]>>i)&1)+'0');
printf("\n");
return;
}
int main(){
freopen("tao.in","r",stdin);
freopen("tao.out","w",stdout);
scanf("%d",&T);
while(T--) solve();
return 0;
}