T1
判断是否存在一棵树，满足它有 \(a\) 个一度点和 \(b\) 个三度点，如果存在请给出一个节点数不超过 \(1000\) 的构造，否则输出 。
考场看了一个小时发现
和
第一种可以构造等量的一度电和三度电，第二种可以在不勾造三度电的情况下构造一度电，根据阳历六 ans 看出
可惜
没加 return 0; 挂成50了
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void WritE(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) WritE(x/10);
putchar(x%10+48);
}
void write(int x){
WritE(x);
puts("");
}
void Write(int x){
WritE(x);
putchar(' ');
}
}
using namespace Testify;
int a,b;
const int N=2005;
int deg[N];
inline void Print(){
write(a+b+1);
for(register int i=1;i<=b;i++){
Write(i+1),write(i);
}
int cnt=b+1;
Write(1),write(++cnt);
for(register int i=1;i<=b;i++){
Write(i),write(++cnt);
}
int op=cnt;
for(register int i=1;i<=(a+b+1)-op;i++){
Write(b+1),write(++cnt);
}
}
signed main(void){
// freopen("ex_a6.in","r",stdin);
// freopen("irises.out","w",stdout);
a=read(),b=read();
if(!a&&!b){
return !puts("1");
}
if(!b){
if(a==1){
puts("0");
return 0;
}
if(a==2){
puts("2");
puts("1 2");
return 0;
}
if(a==3){
return !puts("0");
}
write(a+1);
puts("1 2");
for(register int i=3;i<=a+1;i++){
Write(2),write(i);
}
return 0;
}
for(register int i=1;i<=b;i++){
deg[i]++,deg[i+1]++;
// add(i,i+1),add(i+1,i);
}
int cnt=b+1;
deg[1]++,deg[++cnt]++;
// add(1,++cnt);
for(register int i=1;i<=b;i++){
deg[i]++;
deg[++cnt]++;
// add(i,++cnt);
}
int op=cnt;
for(register int i=1;i<=(a+b+1)-op;i++){
deg[b+1]++;
deg[++cnt]++;
// add(b+1,++cnt);
}
cnt=0;
op=0;
int numA=0,numB=0;
for(register int i=1;i<=a+b+1;i++){
// cerr<<deg[i]<<endl;
if(deg[i]==1){
numA++;
}
else if(deg[i]==3){
numB++;
}
}
if(numA==a&&numB==b){
Print();
}
else{
puts("0");
}
return 0;
}
T2
\(\max_{i=1}^{t}{iw_i}\)
二分答案，将边权假设为 1，\(check\) 为以 1 为起点跑 Dijstra 跑的过程中判断一下 \(Val*step\le \text{二分答案}\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void WritE(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) WritE(x/10);
putchar(x%10+48);
}
void write(int x){
WritE(x);
puts("");
}
void Write(int x){
WritE(x);
putchar(' ');
}
}
using namespace Testify;
const int N=3e5+5;
int n,m;
int head[N],nxt[N<<1],to[N<<1],tot,val[N<<1];
inline void add(int x,int y,int v){
to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
val[tot]=v;
}
bool vis[N];
int dis[N];
typedef pair<int,int> P;
int ans=1e18,mAx=-1;
inline bool check(int VAL){
priority_queue<P,vector<P>,greater<P>> q;
for(register int i=1;i<=n;i++){
dis[i]=-1,vis[i]=false;
}
q.push({0,1});
dis[1]=0;
while(q.size()){
int op=q.top().second;
q.pop();
if(vis[op]) continue;
vis[op]=true;
for(register int i=head[op];i;i=nxt[i]){
int y=to[i];
if(vis[y]) continue;
if((dis[op]+1)*val[i]>VAL){continue;}
if(dis[y]==-1||dis[y]>dis[op]){
dis[y]=dis[op]+1;
q.push({dis[y],y});
}
}
}
return dis[n]!=-1;
}
signed main(void){
freopen("zinnia.in","r",stdin);
freopen("zinnia.out","w",stdout);
n=read(),m=read();
for(register int i=1;i<=m;i++){
register int asd=read(),jkl=read(),v=read();
add(asd,jkl,v);
mAx=max(mAx,v);
}
int l=0,r=mAx*n,ans=l;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
write(ans);
// cerr<<(double)clock()/CLOCKS_PER_SEC;
return 0;
}
/*
4 4
1 2 100
1 3 3
3 2 7
2 4 3
14
*/
T3 紫丁香
现在你需要删掉若干条边，最大化度数为奇数的点的个数。
使用 \(kurscal\) 重构树，记录 \(val\) 和 \(siz\)，手摸一下发现图上的边一定会选，在倒序的最小生成树即字典序最大生成树上选择是否删边，因为你可以自由选择一个边是否被删，比如把fa边去掉即可改变其奇偶性。
每次加边的时候用可撤销并查集去掉当前边，如果一个点的 \(siz+val\) 为奇数说明这个边要选，最终可构造出答案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void WritE(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) WritE(x/10);
putchar(x%10+48);
}
void write(int x){
WritE(x);
puts("");
}
void Write(int x){
WritE(x);
putchar(' ');
}
}
using namespace Testify;
const int N=1e6+5;
int x[N],y[N];
int fa[N];
int val[N],siz[N];
inline int find(int x){
return x==fa[x]?x:find(fa[x]);
}
inline void update(int x){
while(fa[x]!=x){
val[x]++;
x=fa[x];
}
val[x]++;
}
int xx[N],yy[N];
int ans[N];
int n,m;
signed main(void){
freopen("lilac.in","r",stdin);
freopen("lilac.out","w",stdout);
n=read(),m=read();
for(register int i=1;i<=m;i++){
x[i]=read()+1,y[i]=read()+1;
}
for(register int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
val[i]=0;
}
for(register int i=m;i>=1;i--){
xx[i]=find(x[i]),yy[i]=find(y[i]);
if(xx[i]==yy[i]){
ans[i]=1;
}
else{
if(siz[xx[i]]>siz[yy[i]]){
swap(xx[i],yy[i]);
}
siz[yy[i]]+=siz[xx[i]];
fa[xx[i]]=yy[i];
}
}
for(register int i=1;i<=m;i++){
if(ans[i]){
update(x[i]),update(y[i]);
}
else{
siz[yy[i]]-=siz[xx[i]];
val[yy[i]]-=val[xx[i]];
fa[xx[i]]=xx[i];
int vx=siz[xx[i]]+val[xx[i]];
int vy=siz[yy[i]]+val[yy[i]];
if(vx&1||vy&1){
ans[i]=1;
update(x[i]),update(y[i]);
}
}
}
for(register int i=1;i<=m;i++){
WritE(ans[i]);
}
return 0;
}