加载过慢请开启缓存 浏览器默认开启
vector<PII>e[N];
int n,m,c,minn,dist[N];
bool st[N];
void Dijkstra(int u){
minn=1e18;
for(int i=1;i<=n;i++)dist[i]=1e18,st[i]=0;
priority_queue<PII,vector<PII>,greater<PII> >q;
dist[u]=0;
q.push({dist[u],u});
while(q.size()){
auto [dis,ver]=q.top();
q.pop();
if(st[ver])continue;
st[ver]=1;
for(auto [v,w]:e[ver]){
if(v==u)minn=min(minn,dis+w);
if(st[v])continue;
if(dist[v]>dis+w){
dist[v]=dis+w;
q.push({dist[v],v});
}
}
}
}
void solve(){
cin>>n>>m>>c;
int ans=0;
for(int i=1;i<=m;i++){
int u,v,z;cin>>u>>v>>z;
e[u].pb({v,z});
if(z<=c)ans=1;
}
for(int i=1;i<=n;i++){
Dijkstra(i);
if(minn<=c){ans=2;break;}
}
cout<<ans<<"\n";
}
题面：
分析：
对于区间位运算容易想到拆位，对x进行从高位到低位拆位分析：
1.当位为0时如果数组所有元素的第i位一共有奇数个1,那么无论怎么分配，总有一个段内有奇数个1，异或后结果为1，显然导致整体大于x。
2.当i位为0时如果有偶数个1，此时只能就近两两一组去保证异或为0还有组数最多，同时。
3.当i位为1时如果有奇数个1，此时不做任何处理，只能一段一个1.
4.当i位为1时如果有偶数个1，那么两两一组既能保证异或为0，还能保证组数最多，并且此时分组个数可以直接作为答案的一种取max，当然如果每个单独一组不做处理那么数组间异或结果为1，虽然此时不能当作答案，但是之后的数组的分配可能有更多的答案个数，所以也要把不做处理的情况传递下取去。
因为在第4个情况的时候，我们总是不做处理传递下去，并没有真正的处理x当前位相等的情况。所以我们对x进行+1，那么即使传递下去相等情况，那么也可以取答案。
代码：
扩展欧几里得：
对于任意整数 a,b ，求解 ax+by=m
由裴蜀定理可知 ax+by=m 一定有解的充要条件为 gcd(a,b)|m
所以对于解一般的 ax+by=m 不定方程，我们可以先证明ax+by=gcd(a,b),在扩展到一般域
假设一组解为 x1,y1 即ax1+by1=m:
因为gcd(a,b)=gcd(b,a%b) 即 bx2+(a%b)y2=ax1+by1;
其中 a%b=a-b*[a/b] 即 bx2+(a-b*[a/b])y2=ax1+by1
系数对称后可得：x1=y2,y1=x2-[a/b]y2 ;
我们考虑到在gcd(a,b)递归的最终结果为 b|a，则此时ax+b*0=gcd(a,0)=a ,x=1,y=0;
从此时往前递归并借用我们得到的x1,x2,y1,y2 的关系可得最终x1,y1
对于求逆元 ax_= 1(mod m)
即 ax+my =1 与上面同理可得解
爱丽丝和鲍勃正在有向图 上玩游戏。在 中有 个顶点，标记为 。最初， 中没有边。爱丽丝会先从商店直接购买一些边，然后将它们添加到 中。之后，鲍勃需要删除边，直到 中没有边为止。在一轮删除中，鲍勃可以从 中删除一个边子集 ，这样当只保留 中的边时，图就是非循环的。请注意，爱丽丝可以什么也不买，在这种情况下，删除回合数为 。
商店中有 条边。爱丽丝有 美元，因此她要购买的边的总价不应超过 。爱丽丝希望最大化删除回合数，而鲍勃希望最小化删除回合数。爱丽丝和鲍勃都将以最优方式下棋。请编写一个程序来预测删除回合数。
