rank 31,垫底了，T1 0pts，T2 18pts，T3 0pts，T4 50pts
状态有点不好，策略有问题，T4是可以切的，但是不知道为什么弃了。T1不会线性基寄。T3 奇怪结论题，T2 结论题。
在猜结论上还是不行。
T1 欧几里得的噩梦
用到了线性基线性无关的性质，将两个数连边，把环去掉，并查集判断即可。
统计答案用快速幂和线性基可以异或出的数的个数的性质即可。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCALFILE *InFile = infile("in.in"),*OutFile = outfile("out.out");// FILE *ErrFile=errfile("err.err");
#elseFILE *Infile = infile("Euclid.in"),*OutFile = outfile("Euclid.out");//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10;
int fa[N],n,m,siz[N];
inline int get_fa(int x){while(x != fa[x]) x = fa[x] = fa[fa[x]];return x;}
vector<int> p;
inline int power(int a,int b,int mod){int res = 1;for(;b;b>>=1,a = 1ll*a*a%mod) if(b&1) res = 1ll*res*a%mod;return res;
}
inline void solve(){cin>>n>>m;rep(i,1,m+1,1) fa[i] = i,siz[i] = 1;rep(i,1,n,1){int op;cin>>op;if(op == 1){int x,y = m+1;cin>>x;int fx = get_fa(x),fy = get_fa(y);if(fx == fy) continue;fa[fx] = fy;siz[fy] += siz[fx];p.emplace_back(i);}else{int x,y;cin>>x>>y;int fx = get_fa(x),fy = get_fa(y);if(fx == fy) continue;fa[fx] = fy;siz[fy] += siz[fx];p.emplace_back(i);}}int ans = 1;rep(i,1,m+1,1) if(get_fa(i) == i) ans = 1ll*ans*power(2,siz[i]-1,1e9+7)%(int)(1e9+7);cout<<ans<<' '<<p.size()<<'\n';for(auto i:p) cout<<i<<' ';
}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);cout.tie(nullptr)->sync_with_stdio(false);solve();
}
T2 清扫
[AGC010C] Cleaning
先特判掉点数为2的情况，然后以一个至少连接了两个节点的点为根。
考虑一个点处的石子被去掉有两种方式
- 被它的子树消去
- 被它的子树和另一个地方的消去
比如\(5\)处的石子，可能是被\(2,6\)消走了一部分，也可能是被\(2,1\)消走了一部分。
那么每个节点需要上传的就是它还需要几个点来与其相连，记为\(f\)。
对于叶子节点，\(f_x=a_x\)
对于非叶子节点，先令其的\(f_x = \sum\limits_{y\in son_x}f_y\)，另记\(mx = \max\limits_{y\in son_x} f_y\)
然后分讨，如果\(mx\)占了一半以上，那么记\(p = f_x-mx\)
反之，那么\(p = \frac{f_x}{2}\)
如果所有的点都向别的子树连还不够将\(x\)处的节点消去或者将所有的点都向该子树连还是不能删去\(x\)，直接无解。
最后\(f_x = 2\times a_x - f_x\)
为什么是这个?假设连向外面子树的个数为\(out\)，连向自身的为\(in\)，有\(in+out = a_x\)，又有\(2\times in+out = f_x\)
联立就有\(out = 2\times a_x - f_x\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCALFILE *InFile = infile("in.in"),*OutFile = outfile("out.out");// FILE *ErrFile=errfile("err.err");
#elseFILE *Infile = stdin,*OutFile = stdout;//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
#define eb emplace_back
int n,a[N];
vector<int> edge[N];
inline void add(int u,int v){edge[u].eb(v);}
int fa[N];
ll f[N];
bool flag = false;
void dfs(int x){if(edge[x].size() == 1) return f[x] = a[x],void();ll p,mx = 0;for(int y:edge[x]){if(y == fa[x]) continue;fa[y] = x;dfs(y);f[x] += f[y];mx = max(mx,f[y]); }if(mx > f[x] - mx) p = f[x] - mx;else p = f[x]/2;if(f[x] < a[x] || f[x] - a[x] > p) cout<<"NO\n",exit(0);f[x] = 2ll*a[x] - f[x];
}
inline void solve(){cin>>n;rep(i,1,n,1)cin>>a[i];if(n == 2){if(a[1] != a[2]) cout<<"NO\n";else cout<<"YES\n";return;}rep(i,2,n,1){int u,v;cin>>u>>v;add(u,v),add(v,u);}rep(i,1,n,1) if(edge[i].size() > 1)dfs(i),cout<<(f[i]?"NO\n":"YES\n"),assert(!f[i]&&!flag),exit(0);
}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);cout.tie(nullptr)->sync_with_stdio(false);solve();
}
T3 购物
结论题。
考虑先将\(a\)升序排列，记\(sum_i = \sum_{j=1}^i a_i\)。
枚举\(i\)，如果没有加上第\(i\)个数，那么最大的值为\(sum_{i-1}\)，若加上第\(i\)个数，那么中间就会多出\(sum_{i-1}\sim \left\lfloor\frac{a_i}{2}\right\rfloor\)的空缺，直接加上即可。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCALFILE *InFile = infile("in.in"),*OutFile = outfile("out.out");// FILE *ErrFile=errfile("err.err");
#elseFILE *Infile = infile("buy.in"),*OutFile = outfile("buy.out");//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
int n,a[N];
inline void solve(){cin>>n; rep(i,1,n,1) cin>>a[i];sort(a+1,a+1+n);ll s = 0,m = 0;rep(i,1,n,1){if((a[i]+1)/2 > s) m -= (a[i]+1)/2-s-1;s += a[i];}cout<<m+s<<'\n';
}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);cout.tie(nullptr)->sync_with_stdio(false);solve();
}
T4 ants
原题permu，回滚莫队，用链表模拟的并查集。
考虑将每段的最右段的点的左指针指向该段最左端，最左端的点的右指针指向该段最右段。
然后四种情况分讨即可，删除操作记录一下，逆序处理即可。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCALFILE *InFile = infile("in.in"),*OutFile = outfile("out.out");// FILE *ErrFile=errfile("err.err");
#elseFILE *Infile = infile("ants.in"),*OutFile = outfile("ants.out");//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
int n,m,L[N],R[N],pos[N],len,a[N],out[N];
struct node{int id,l,r;}q[N];
struct Change{int op,val,lef,rgh;};
int pre[N],suf[N],rpre[N],rsuf[N];
bitset<N> vis;
inline void Add(int x,int &res){vis[x] = true;if(vis[x-1] && vis[x+1]){suf[pre[x-1]] = suf[x+1];pre[suf[x+1]] = pre[x-1];res = max(suf[x+1] - pre[x-1] + 1,res);}if(vis[x-1] && !vis[x+1]){pre[x] = pre[x-1],suf[pre[x-1]] = x;res = max(x - pre[x - 1] + 1,res);}if(!vis[x-1] && vis[x+1]){suf[x] = suf[x+1],pre[suf[x+1]] = x;res = max(suf[x+1] - x + 1,res);}if(!vis[x-1] && !vis[x+1]) pre[x] = suf[x] = x;
}
inline void solve(){cin>>n>>m;rep(i,1,n,1) cin>>a[i];rep(i,1,m,1) cin>>q[i].l>>q[i].r,q[i].id = i;len = sqrt(n);rep(i,1,len,1) L[i] = R[i-1]+1,R[i] = i*len;if(R[len] < n) len++,L[len] = R[len-1] + 1,R[len] = n;rep(i,1,len,1) rep(j,L[i],R[i],1) pos[j] = i;sort(q+1,q+1+m,[](node x,node y){return pos[x.l]==pos[y.l]?x.r<y.r:x.l<y.l;});int l,r,res = 0,i = 1;rep(now,1,len,1){rep(i,1,n,1) pre[i] = suf[i] = vis[i] = 0;r = R[now],res = 0;int ql = q[i].l,qr = q[i].r,id = q[i].id;while(pos[ql] == now){if(qr - ql < len){bitset<N> vis;rep(i,ql,qr,1) vis[a[i]] = true;int lastpos = 0,res = 0,ans = 0;while(vis._Find_next(lastpos) != vis.size()){int pos = vis._Find_next(lastpos);if(!lastpos) res = 1;else if(lastpos && pos - lastpos == 1) res++;else if(lastpos && pos - lastpos > 1) res = 1;lastpos = pos;ans = max(ans,res);}out[id] = ans;i++;ql = q[i].l,qr = q[i].r,id = q[i].id;continue;}l = R[now] + 1;while(r < qr) Add(a[++r],res);int rres = res;vector<Change> que;while(l > ql){l--;int x = a[l];vis[x] = true;Change p;p.val = x;if(vis[x-1] && vis[x+1]){suf[pre[x-1]] = suf[x+1];pre[suf[x+1]] = pre[x-1];p.op = 1;p.lef = pre[x-1],p.rgh = suf[x+1];res = max(suf[x+1] - pre[x-1] + 1,res);}if(vis[x-1] && !vis[x+1]){pre[x] = pre[x-1],suf[pre[x-1]] = x;p.op = 2;p.lef = x,p.rgh = pre[x-1];res = max(x - pre[x - 1] + 1,res);}if(!vis[x-1] && vis[x+1]){suf[x] = suf[x+1],pre[suf[x+1]] = x;p.op = 3;p.lef = x,p.rgh = suf[x+1];res = max(suf[x+1] - x + 1,res);}if(!vis[x-1] && !vis[x+1]){pre[x] = suf[x] = x;p.op = 4; res = max(res,1);}que.push_back(p);}out[id] = res;res = rres;l = R[now] + 1;while(que.size()){auto p = que.back();que.pop_back(); vis[p.val] = false;if(p.op == 1) suf[p.lef] = p.val - 1,pre[p.rgh] = p.val + 1;if(p.op == 2) suf[p.rgh] = p.val - 1;if(p.op == 3) pre[p.rgh] = p.val + 1;if(p.op == 4) suf[p.val] = pre[p.val] = 0;}i++;ql = q[i].l,qr = q[i].r,id = q[i].id;}}rep(i,1,m,1) cout<<out[i]<<'\n';
}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);cout.tie(nullptr)->sync_with_stdio(false);solve();
}
