依旧三道思维题，
T1：https://www.luogu.org/problem/T92260
失误：重复算了连通块之间的贡献，凉的彻底
考虑熔断一个点后，不可能把一个连通块拆成两个，或将一个环拆为两个（总有一种方法可以将其连回去）
所以对于所有度数>2的点，将其拆成若干个2和至多一个1
最后对于所有度数为1的点，将他们焊接在一起即可
考虑多个连通块：
1.如果一个连通块度数全为2，你需要额外熔断出两个度数为1的点
2.如果一个连通块度数全为偶数且存在度数比2大的点，不需要额外熔断，因为可以在熔断度数>2的点时，特别分出两个度数为1的点
最后答案就是拆点费用+度数=1点数/2
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<climits> #include<map> #include<queue> using namespace std; #define O(x) cout << #x << " " << x << endl; #define B cout << "breakpoint" << endl; #define clr(a) memset(a,0,sizeof(a)); inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int maxn = 1e5 + 5; int d[maxn]; bool vis[maxn]; struct egde { int to,next; }e[maxn << 1]; int fir[maxn],alloc; void adde(int u,int v) { d[u]++,d[v]++; e[++alloc].next = fir[u]; fir[u] = alloc; e[alloc].to = v; swap(u,v); e[++alloc].next = fir[u]; fir[u] = alloc; e[alloc].to = v; } int col[maxn]; bool all[maxn]; bool have[maxn]; void dfs(int u,int c) { if(d[u] != 2) all[c] = 0; if(d[u] % 2) have[c] = 0; col[u] = c; vis[u] = 1; for(int i = fir[u];i;i = e[i].next) { int v = e[i].to; if(vis[v]) continue; dfs(v,c); } } int n,m; int main() { freopen("A.in","r",stdin); freopen("A.out","w",stdout); n = read(),m = read(); for(int i = 1;i <= m;i++) { int u = read(),v = read(); adde(u,v); } int cnt = 0; for(int i = 1;i <= n;i++) if(!col[i] && d[i]) all[++cnt] = 1,have[cnt] = 1,dfs(i,cnt); int tot = 0,ans = 0; for(int i = 1;i <= n;i++) { if(d[i] > 2) tot += (d[i] % 2),ans++; else if(d[i] == 1) tot++; } if(cnt > 1) for(int i = 1;i <= cnt;i++) { if(have[i]) tot += 2; if(all[i]) ans++; } ans += tot / 2; //if(cnt >= 2) ans += cnt; printf("%d",ans); } /* 4 6 1 2 1 4 1 3 3 4 3 2 2 4 */
T2：https://www.luogu.org/problem/T92261
失误：贪心没考虑好，结果错了...
正解是构造，令t=a+b-c，表示需要进位的位数
假设A全填1，讨论t与a的大小关系，再讨论t与b的大小关系
可以证明，当b填满1-a时，向后填更优
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<climits> #include<map> #include<queue> using namespace std; #define O(x) cout << #x << " " << x << endl; #define B cout << "breakpoint" << endl; #define clr(a) memset(a,0,sizeof(a)); inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int maxn = 1e5 + 5; int n,a,b,c; int cnta[maxn],cntb[maxn],cntc[maxn]; void solve() { if(c > a + b) { printf("-1 "); exit(0); } int t = a + b - c; if(a < b) swap(a,b); if(t > a) { if(t >= b) { for(int i = 1;i <= a;i++) cnta[i] = 1; for(int i = a + 1;i <= t;i++) cntb[i] = 1; for(int i = 1;i <= c;i++) cntb[i] = 1; } else { for(int i = 1;i <= b;i++) cntb[i] = 1; for(int i = b - t + 1;i <= c;i++) cnta[i] = 1; } } else { if(t >= b) { for(int i = 1;i <= a;i++) cnta[i] = 1; for(int i = a - t + 1;i <= c;i++) cntb[i] = 1; } else { int x = b - t; for(int i = x + 1;i <= a + x;i++) cnta[i] = 1; for(int i = 1;i <= x;i++) cntb[i] = 1; for(int i = c - t + 1;i <= c;i++) cntb[i] = 1; } } for(int i = 1;i <= n;i++) { cntc[i] += cnta[i] + cntb[i]; cntc[i + 1] = cntc[i] / 2; cntc[i] %= 2; } if(cntc[n + 1]) { printf("-1 "); exit(0); } for(int i = n;i >= 1;i--) printf("%d",cntc[i]); exit(0); } int main() { freopen("B.in","r",stdin); freopen("B.out","w",stdout); n = read(),a = read(),b = read(),c = read(); solve(); /*if(a < b) swap(a,b); if(c > a + b) { printf("-1 "); return 0; } cnta[1] = cntb[1] = 1; int t = a + b - c; int ta = a - 1,tb = b - 1; for(int i = 2;i <= t;i++) { if(!ta && !tb) { printf("-1 "); return 0; } if(i % 2) { if(ta) cnta[i] = 1,ta--; else if(tb) cntb[i] = 1,tb--; } if(i % 2 == 0) { if(tb) cntb[i] = 1,tb--; else if(ta) cnta[i] = 1,ta--; } } for(int i = 1;i <= n;i++) { cntc[i] += cnta[i] + cntb[i]; cntc[i + 1] = cntc[i] / 2; cntc[i] %= 2; } for(int i = 1;i <= n;i++) { if(ta) if(!cntc[i] && !cnta[i]) cntc[i] = 1,ta--; if(tb) if(!cntc[i] && !cntb[i]) cntc[i] = 1,tb--; } if(cntc[n + 1]) { printf("-1 "); return 0; } for(int i = n;i >= 1;i--) printf("%d",cntc[i]); return 0; */ } /* 6 4 1 2 */
T3：咕