2026.6.1

稳定的符文序列

a=input()
n=len(a)
i=0
j=0
ans=0
s=set()
while(i<n and j<n):
    if(a[j] not in s):
        s.add(a[j])
        j+=1
        ans=max(ans,j-i)
    else:
        s.remove(a[i])
        i+=1
print(ans)

工程师的齿轮

排序并双指针会破坏原来的顺序，使用哈希表扫两遍。

from collections import defaultdict
n,t=map(int,input().split())
s=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
    if(s[i] in d):
        continue
    else:
        d[s[i]]=i+1
ans=(n,n)
for i in range(n):
    if(t-s[i] in d and ans>(d[t-s[i]],i+1) and ((i+1)!=d[t-s[i]])):
        ans=(d[t-s[i]],i+1)
print(ans[0],ans[1])

狭路相逢

n=int(input())
a=list(map(int,input().split()))
s=[]
for i in range(n):
    if(a[i]>0):
        s.append(a[i])
    else:
        while(s and s[-1]>0 and a[i]<0):
            if(-a[i]>=s[-1]):
                a[i]+=s[-1]
                s.pop()
            else:
                s[-1]+=a[i]
                a[i]=0
        if(a[i]<0):
            s.append(a[i])
print(len(s))
print(*s)

量子芯片研发

from collections import deque
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
g=[[]for _ in range(n+1)]
in_deg=[0]*(n+1)
for i in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
    in_deg[v]+=1
q=deque()
ve=[0]*(n+1)
cnt=0
for i in range(1,n+1):
    if(in_deg[i]==0):
        q.append(i)
        cnt+=1
while(q):
    idx=q.popleft()
    for i in g[idx]:
        ve[i]=max(ve[i],ve[idx]+a[idx])
        in_deg[i]-=1
        if(in_deg[i]==0):
            q.append(i)
            cnt+=1
if(cnt!=n):
    print(-1)
else:
    ans=0
    for i in range(1,n+1):
        ans=max(ans,ve[i]+a[i])
    print(ans)

动态图连通性

n,q=map(int,input().split())
fa=[i for i in range(n+1)]
siz=[1 for i in range(n+1)]
cnt=[0 for i in range(n+1)]
from collections import defaultdict
ans=0
def find(x):
    if(x==fa[x]):
        return x
    fa[x]=find(fa[x])
    return fa[x]
def merge(x,y):
    global ans
    fx=find(x)
    fy=find(y)
    if(fx==fy):
        return ans
    if(siz[fx]>siz[fy]):
        fx,fy=fy,fx
    ans-=(cnt[fx]+cnt[fy])
    fa[fx]=fy
    siz[fy]+=siz[fx]
    cnt[fx]=0
    tmp=siz[fy]
    cnt[fy]=tmp*(tmp-1)//2
    ans+=cnt[fy]
    return ans
for i in range(q):
    u,v=map(int,input().split())
    print(merge(u,v))

0-W 最小生成树

bfs求所有连通块并标记，然后对连通块跑MST.

from collections import deque
n,m=map(int,input().split())
g=[[]for _ in range(n+1)]
edges=[]
for i in range(m):
    u,v,w=map(int,input().split())
    g[u].append(v)
    g[v].append(u)
    edges.append((w,u,v))
par=[0]*(n+1)
q=deque()
un_vis=[i for i in range(1,n+1)]
marked=[0]*(n+1)
cnt=0
while(un_vis):
    cnt+=1
    start=un_vis.pop()
    q.append(start)
    par[start]=cnt
    while(q):
        idx=q.popleft()
        for i in g[idx]:
            marked[i]=1
        nxt=[]
        for i in un_vis:
            if(marked[i]==0):
                q.append(i)
                par[i]=cnt
            else:
                nxt.append(i)
        un_vis=nxt
        for i in g[idx]:
            marked[i]=0
fa=[i for i in range(cnt+1)]
def find(x):
    if(x==fa[x]):
        return x
    fa[x]=find(fa[x])
    return fa[x]
def merge(x,y):
    fx=find(x)
    fy=find(y)
    if(fx==fy):
        return
    fa[fx]=fy
new_edges=[]
for w,u,v in edges:
    if(par[u]!=par[v]):
        new_edges.append((w,par[u],par[v]))
new_edges=sorted(new_edges,key=lambda x:x[0])
ans=0
tot=cnt-1
qwq=0
for w,u,v in new_edges:
    if(qwq==tot):
        break
    if(find(u)!=find(v)):
        merge(u,v)
        ans+=w
        qwq+=1
print(ans)

Excel表列序号

a=input()
n=len(a)
ans=0
for i in range(n):
    ans*=26
    ans+=ord(a[i])-ord('A')+1
print(ans)

清北学术走廊规划

n,m=map(int,input().split())
edges=[]
for i in range(m):
    u,v,w=map(int,input().split())
    edges.append((w,u,v))
fa=[i for i in range(n+1)]
def find(x):
    if(fa[x]==x):
        return fa[x]
    fa[x]=find(fa[x])
    return fa[x]
def merge(x,y):
    fx=find(x)
    fy=find(y)
    if(fx==fy):
        return
    fa[fx]=fy
cnt=0
ans=0
edges.sort(key=lambda x:x[0])
for w,u,v in edges:
    if(find(u)==find(v)):
        continue
    ans+=w
    cnt+=1
    merge(u,v)
if(cnt<n-1):
    print("orz")
else:
    print(ans)

简化路径

a=input().split("/")
s=[]
n=len(a)
for i in a:
    if(i==""):
        continue
    elif(i=="."):
        continue
    elif(i==".."):
        if(s):
            s.pop()
        else:
            continue
    else:
        s.append(i)
print("/",end="")
print("/".join(s))

沉没孤岛

n,m=map(int,input().split())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))
vis=[[0 for _ in range(m)]for _ in range(n)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
def dfs(flag,x,y):
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if(0<=xx<n and 0<=yy<m):
            if(vis[xx][yy]==0 and a[xx][yy]==1):
                vis[xx][yy]=1
                a[xx][yy]=flag
                dfs(flag,xx,yy)
                
for i in range(n):
    if(a[i][0]==1 and vis[i][0]==0):
        vis[i][0]=1
        dfs(1,i,0)
    if(a[i][m-1]==1 and vis[i][m-1]==0):
        vis[i][m-1]=1
        dfs(1,i,m-1)
for i in range(m):
    if(a[0][i]==1 and vis[0][i]==0):
        vis[0][i]=1
        dfs(1,0,i)
    if(a[n-1][i]==1 and vis[n-1][i]==0):
        vis[n-1][i]=1
        dfs(1,n-1,i)
for i in range(1,n-1):
    for j in range(1,m-1):
        if(a[i][j]==1 and vis[i][j]==0):
            a[i][j]=0
            vis[i][j]=1
            dfs(0,i,j)
for i in range(n):
    print(*a[i])

神经网络

在拓扑序上面更新神经状态。神经不激活也要置零然后继续往下走，否则会干扰到判环的逻辑。

from collections import deque
import sys
n,p=map(int,input().split())
a=[0]
b=[0]
for i in range(n):
    u,v=map(int,input().split())
    a.append(u)
    b.append(v)
g=[[]for _ in range(n+1)]
in_deg=[0]*(n+1)
out_deg=[0]*(n+1)
for i in range(p):
    u,v,w=map(int,input().split())
    g[u].append((v,w))
    in_deg[v]+=1
    out_deg[u]+=1
    if(v==u):
        print("NULL")
        sys.exit(0)
q=deque()
cnt=0
for i in range(1,n+1):
    if(in_deg[i]==0):
        q.append(i)
        cnt+=1
while(q):
    idx=q.popleft()
    if(a[idx]<=0):
        a[idx]=0
    for i,w in g[idx]:
        a[i]+=w*a[idx]
        in_deg[i]-=1
        if(in_deg[i]==0):
            cnt+=1
            a[i]-=b[i]
            q.append(i)
flag=0
if(cnt<n):
    print("NULL")
else:
    for i in range(1,n+1):
        if(out_deg[i]==0 and a[i]>0):
            flag=1
            print(i,a[i])
    if(flag==0):
        print("NULL")

没有上司的宴会

import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=[0]
for i in range(n):
    r=int(input())
    a.append(r)
up=[[]for _ in range(n+1)]
down=[[]for _ in range(n+1)]
in_deg=[0]*(n+1)
for i in range(n-1):
    l,k=map(int,input().split())
    up[l].append(k)
    down[k].append(l)
    in_deg[l]+=1
dp1=[0]*(n+1)#i号节点参加，最大值
dp2=[0]*(n+1)#i号节点不参加，最大值
root=0
for i in range(1,n+1):
    if(in_deg[i]==0):
        root=i
        break
def dfs(x):
    dp1[x]=a[x]
    for i in down[x]:
        dfs(i)
        dp1[x]+=dp2[i]
        dp2[x]+=max(dp1[i],dp2[i])
dfs(root)
print(max(dp1[root],dp2[root]))

Okabe and Boxes

重排之后清空，如果要取出的时候栈为空则说明可以随便取。否则重排一次。

n=int(input())
s=[]
cnt=0
res=1
for i in range(2*n):
    a=input()
    if(a[0]=='a'):
        op,num=a.split()
        s.append(int(num))
    else:
        if(s and s[-1]==res):
            s.pop()
            res+=1
        elif(len(s)==0):
            res+=1
            continue
        else:
            cnt+=1
            s.clear()
            res+=1
print(cnt)

分糖果

from collections import deque
n,m=map(int,input().split())
t=list(map(int,input().split()))
a=deque()
for i in range(n):
    a.append((t[i],i+1))
while(len(a)>1):
    num,idx=a.popleft()
    if(num>m):
        qaq=(num-m,idx)
        a.append(qaq)
print(a[0][1])

受限条件下可到达节点的数目

n=int(input())
g=[[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u].append(v)
    g[v].append(u)
a=set(list(map(int,input().split())))
vis=[0]*n
def dfs(x):
    for i in g[x]:
        if(vis[i]==0 and i not in a):
            vis[i]=1
            dfs(i)
vis[0]=1
dfs(0)
print(sum(vis))

堆路径

n=int(input())
a=[0]+list(map(int,input().split()))
s=[]
is_max=1
is_min=1
def dfs(x,path):
    global is_max,is_min
    if(2*x>n):
        s.append(path)
        return
    if(2*x+1<=n):
        if(a[2*x+1]>a[x]):
            is_max=0
        if(a[2*x+1]<a[x]):
            is_min=0
        dfs(2*x+1,path+[a[2*x+1]])
    if(2*x<=n):
        if(a[2*x]>a[x]):
            is_max=0
        if(a[2*x]<a[x]):
            is_min=0
        dfs(2*x,path+[a[2*x]])
dfs(1,[a[1]])
for i in range(len(s)):
    print(*s[i])
if(is_max):
    print("Max Heap")
elif(is_min):
    print("Min Heap")
else:
    print("Not Heap")

谣言

n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
g=[[]for _ in range(n+1)]
vis=[0]*(n+1)
minm=[0]
for i in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
    g[v].append(u)
def dfs(x,tag):
    for i in g[x]:
        if(vis[i]==0):
            vis[i]=tag
            minm[tag]=min(minm[tag],a[i])
            dfs(i,tag)
cnt=1
for i in range(1,n+1):
    if(vis[i]==0):
        vis[i]=cnt
        minm.append(a[i])
        dfs(i,cnt)
        cnt+=1
ans=sum(minm)
print(ans)

判断等价关系是否成立

不等关系不能传递，因此相等的合并，再把不等的全部跑一遍判断。

n=int(input())
fa=[i for i in range(30)]
def find(x):
    if(fa[x]==x):
        return x
    fa[x]=find(fa[x])
    return fa[x]
def merge(x,y):
    fx=find(x)
    fy=find(y)
    if(fx==fy):
        return
    fa[fx]=fy
flag=1
query=[]
for i in range(n):
    s=input()
    query.append(s)
    a=ord(s[0])-ord('a')
    b=ord(s[-1])-ord('a')
    if(s[1]=='='):
        merge(a,b)
for i in range(n):
    s=query[i]
    a=ord(s[0])-ord('a')
    b=ord(s[-1])-ord('a')
    if(s[1]=='!'):
        if(find(a)==find(b)):
            flag=0
if(flag):
    print("True")
else:
    print("False")

2026.6.3 数算期末机考

遗憾离场

缺失的第一个正数

从一开始搜索，注意整个数组都为负的情况，因此结束点取范围最大值即可。

n=int(input())
a=list(map(int,input().split()))
s=set(a)
for i in range(1,2**31):
    if(i not in s):
        print(i)
        break

猫猫水群聊

按倒序排序然后判断当前值是否比序号大即可。

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
for i in range(n):
    if(a[i]>=i+1):
        ans=i+1
    else:
        break
print(ans)

匹配队友

将每一组队友的编号存下来，最后判断是否成队。

from collections import defaultdict
n=int(input())
a=list(input().split())
ans=[0]*n
res=[[0 for _ in range(3)]for _ in range(n+1)]
idx0=1
idx1=1
idx2=1
teams=defaultdict(list)
for i in range(n):
    s=a[i]
    if(s=='D'):
        if(res[idx0][0]>=3):
            idx0+=1
        res[idx0][0]+=1
        ans[i]=idx0
        teams[idx0].append(i)
    elif(s=='T'):
        if(res[idx1][1]>=1):
            idx1+=1
        res[idx1][1]+=1
        ans[i]=idx1
        teams[idx1].append(i)
    elif(s=='H'):
        if(res[idx2][2]>=1):
            idx2+=1
        res[idx2][2]+=1
        ans[i]=idx2
        teams[idx2].append(i)
t=max(ans)
for i in range(t,-1,-1):
    if(len(teams[i])<5):
        for j in teams[i]:
            ans[j]=0
    else:
        break
print(*ans)

森林局部排序遍历

离散化，找根，然后按照题目要求dfs.

from collections import defaultdict
n=int(input())
g=defaultdict(list)
idx=defaultdict(int)#self->idx
tran=[]#idx->self
cnt=0
for i in range(n):
    temp=list(map(int,input().split()))
    head=temp[0]
    g[head]=temp[1:]
    idx[head]=cnt
    cnt+=1
    tran.append(head)
in_deg=[0]*n#idx
for i in g.keys():
    for j in g[i]:
        in_deg[idx[j]]+=1
par=[]#self
for i in range(n):
    if(in_deg[i]==0):
        par.append(tran[i])
par.sort()
# vis=[0]*n
def dfs(x,fa):
    if(len(g[x])==0):
        print(x)
        return
    elif(x==fa):
        print(x)
        return
    else:
        qaq=[x]
        for i in g[x]:
            qaq.append(i)
        qaq.sort()
        for i in qaq:
            dfs(i,x)
for i in par:
    dfs(i,-10086)

Ask for Likes

对每个询问进行约数分解。然后依次搜索每个数换成某个比它大的因数之后能不能达到目标。 剪枝：1.由于$2^{30}>{10}^9$,因此如果大于1的数的个数多于30个，那么肯定不能达到目标。因此实际进入dfs的候选数不超过30个。 2.后缀积数组，如果剩余的数小于当前后缀积，那么乘起来肯定大了，可以剪掉。 3.使用lru_cache进行记忆化搜索。

import sys
from math import sqrt
from bisect import bisect_left
from functools import lru_cache
n,q=map(int,input().split())
c=list(map(int,input().split()))
cnt=0
for i in range(n):
    if(c[i]==0):
        c[i]=1
    if(c[i]>1):
        cnt+=1
c.sort(reverse=True)
if(cnt>30):
    for i in range(q):
        x=int(input())
        print("No")
    sys.exit(0)
suf=[1]*(n+1)
for i in range(n-1,-1,-1):
    suf[i]=suf[i+1]*c[i]
for i in range(q):
    x=int(input())
    div=[]
    for j in range(1,int(sqrt(x))+1):
        if(x%j==0):
            div.append(j)
            if(j*j!=x):
                div.append(x//j)
    div.sort()
    @lru_cache(None)    
    def dfs(i,rem):
        global cnt
        if(i==cnt):
            return (rem==1 or n-cnt>0)
        if(suf[i]>rem):
            return False
        for d in div:
            if(d>rem):
                break
            if(d>=c[i] and rem%d==0):
                if(dfs(i+1,rem//d)):
                    return True
        return False
    dfs.cache_clear()
    if(dfs(0,x)):
        print("Yes")
    else:
        print("No")

猫猫逛公园

使用Tarjan进行SCC缩点，然后遍历所有边，建立DAG并将属于同一SCC的边归类。然后对每个SCC中的边作数学处理，得到SCC内部的最大愉悦值。再在拓扑序上dp，注意起点给定，因此除了起点之外的点的dp值设为-1，dp的更新基于前一点已被更新，即大于零。

import sys
from math import sqrt,ceil
from collections import deque
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[]for _ in range(n+1)]
for i in range(m):
    x,y,w=map(int,input().split())
    g[x].append((y,w))
start=int(input())
dfn=[0]*(n+1)
low=[0]*(n+1)
time=0
s=[]
scc=[]
in_s=[0]*(n+1)
idx=[0]*(n+1)
def tarjan(k):
    global time
    time+=1
    low[k]=dfn[k]=time
    s.append(k)
    in_s[k]=1
    for i,qaq in g[k]:
        if(dfn[i]==0):
            tarjan(i)
            low[k]=min(low[k],low[i])
        elif(in_s[i]):
            low[k]=min(low[k],dfn[i])
    if(low[k]==dfn[k]):
        tmp=[]
        while(True):
            x=s.pop()
            tmp.append(x)
            idx[x]=len(scc)
            in_s[x]=0
            if(x==k):
                break
        scc.append(tmp)
for i in range(1,n+1):
    if(dfn[i]==0):
        tarjan(i)
lens=len(scc)
in_deg=[0]*lens
vis=set()
dag=[[]for _ in range(lens)]
sums=[[] for _ in range(lens)]
for i in range(1,n+1):
    for j,qaq in g[i]:
        if(idx[i]!=idx[j]):
            in_deg[idx[j]]+=1
            dag[idx[i]].append((idx[j],qaq))
        else:
            sums[idx[i]].append(qaq)
res=[]
for i in range(lens):
    cnt=0
    for j in sums[i]:
        k=ceil((sqrt(8*j+1)-1)/2)
        val=k*j-(k-1)*k*(k+1)//6
        cnt+=val
    res.append(cnt)
q=deque()
dp=[-1]*lens
sidx=idx[start]
dp[sidx]=res[sidx]
for i in range(lens):
    if(in_deg[i]==0):
        q.append(i)
while(q):
    node=q.popleft()
    for i,val in dag[node]:
        if(dp[node]!=-1):
            dp[i]=max(dp[i],dp[node]+res[i]+val)
        in_deg[i]-=1
        if(in_deg[i]==0):
            q.append(i)
print(int(max(dp)))

2026.6.25

最小支配集

贪心。每次找能够支配当前未支配点的最大值，然后更新未支配点。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[200005];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    int ans=0;
    int idx=0;
    while(idx<n){
        int goal=a[idx]+k;
        while(idx+1<n and a[idx+1]<=goal){
            idx+=1;
        }
        ans+=1;
        int right=a[idx]+k;
        while(idx<n and a[idx]<=right){
            idx+=1;
        }
    }
    printf("%d",ans);
    return 0;
}

树上距离旅行商

最小周游距离和为所有边权*2，因此直接输出s开头的dfs序。

#include<bits/stdc++.h>
using namespace std;
int n,s;
vector<vector<pair<int,int>>> a;
vector<int> res;
void dfs(int node,int parent){
    res.push_back(node);
    for(const auto&[v,w]:a[node]){
        if(v!=parent){
            dfs(v,node);
        }
    }
}
int main(){
    scanf("%d%d",&n,&s);
    a.resize(n);
    for(int i=0;i<n-1;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    dfs(s,s);
    for(int i=0;i<n;i++){
        printf("%d ",res[i]);
    }
}

Correlation Clustering

并查集。

#include<bits/stdc++.h>
using namespace std;
int n;
int fa[300005];
vector<pair<int,int>> a;
int find(int x){
    if(fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
    fa[fx]=fy;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=0;i<n;i++){
        int u,v;
        char x;
        scanf("%d %d %c",&u,&v,&x);
        if(x=='+'){
            merge(u,v);
        }
        else if(x=='-'){     
            a.push_back({u,v});   
        }
    }
    int ans=0;
    unordered_map<int,vector<int>> res;
    for(int i=1;i<=n;i++){
        res[find(i)].push_back(i);
    }
    for(const auto&[u,v]:a){
        if(find(u)==find(v)) ans++;
    }
    int k=res.size();
    printf("%d %d\n",ans,k);
    for(int i=1;i<=n;i++){
        int m=res[i].size();
        if(m>0){
            printf("%d ",m);
            sort(res[i].begin(),res[i].end());
            for(int j=0;j<m;j++){
                printf("%d ",res[i][j]);
            }
        }
    }
}

2026.6.26 程设实验班期末机考

遗憾离场*2

欧氏距离平方和查询

#include<bits/stdc++.h>
using namespace std;
int n,m,d;
long long a[500005][25];
long long sum1=0;
long long sum2[25];
int main(){
    scanf("%d %d %d",&n,&m,&d);
    memset(sum2,0,sizeof(sum2));
    for(int i=0;i<n;i++){
        for(int j=0;j<d;j++){
            scanf("%lld",&a[i][j]);
            sum1+=a[i][j]*a[i][j];
            sum2[j]+=a[i][j];
        }
    }  
    for(int i=0;i<m;i++){
        long long q[25];
        long long ans=0;
        for(int j=0;j<d;j++){
            scanf("%lld",&q[j]);
            ans+=q[j]*q[j];
        }
        ans*=n;
        ans+=sum1;
        for(int j=0;j<d;j++){
            ans-=2*sum2[j]*q[j];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

坐标轴上的曼哈顿匹配

STL炸了遂使用py.

from collections import defaultdict
a=defaultdict(list)
n,d=map(int,input().split())
for i in range(n):
    ls=list(map(int,input().split()))
    idx=0
    for j in range(d):
        if(ls[j]!=0):
            idx=j+1
            a[idx].append((ls[j],i+1))
            break
    if(idx==0):
        a[idx].append((0,i+1))
left=[]
res=[0]*(n+1)
if(len(a[0])>0):
    for i in range(len(a[0])):
        left.append(a[0][i])
for i in range(1,d+1):
    if(len(a[i])==0):
        continue
    m=len(a[i])
    a[i].sort()
    if(m%2==0):
        for j in range(0,m,2):
            v1,l1=a[i][j]
            v2,l2=a[i][j+1]
            res[l1]=l2
            res[l2]=l1
    else:
        cnt1=0
        cnt2=0
        for j in range(0,m):
            v1,l1=a[i][j]
            if(v1<0):
                cnt1+=1
            elif(v1>0):
                cnt2+=1
        if(cnt1%2==1):
            flag=cnt1-1
        elif(cnt2%2==1):
            flag=cnt1
        for j in range(0,flag,2):
            v1,l1=a[i][j]
            v2,l2=a[i][j+1]
            res[l1]=l2
            res[l2]=l1
        for j in range(flag+1,m,2):
            v1,l1=a[i][j]
            v2,l2=a[i][j+1]
            res[l1]=l2
            res[l2]=l1               
        left.append(a[i][flag])
for i in range(0,len(left),2):
    v1,l1=left[i]
    v2,l2=left[i+1]
    res[l1]=l2
    res[l2]=l1
print(" ".join(map(str,res[1:n+1])))

合力平衡

蒙特卡洛

#include<bits/stdc++.h>
using namespace std;
int n;
int a[300005][5];
int res[300005];
int main(){
    scanf("%d",&n);
    mt19937 rng(time(0));
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int ans[300005];
    __int128 tot=-1;
    for(int t=1;t<100;t++){
        for(int i=0;i<n;i++){
            res[i]=rng()%2;
            if(res[i]==0) res[i]=-1;
        }
        __int128 sum=0;
        for(int j=0;j<2;j++){
            __int128 sum1=0;
            for(int i=0;i<n;i++){
                sum1+=a[i][j]*res[i];
            }
            sum+=sum1*sum1;
        }
        if(tot==-1){
            tot=sum;
            for(int qaq=0;qaq<n;qaq++) ans[qaq]=res[qaq];
        }
        else{
            if(sum<tot){
                tot=sum;
                for(int qaq=0;qaq<n;qaq++) ans[qaq]=res[qaq];
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}