赛时rank 47,T1 20,T2 0,T3 30,T4 45
赛时最后想到了T1的正解，可惜没有打出来。
整场比赛都在死磕T1的神秘构造，导致本来可以AC的T2没有写，开题的策略不行，太容易死磕了。
T1 黎明与萤火
贪心构造。
先给一组数据
Input:
5
0 1 2 3 4
Output:
YES
2
4
1
3
5
通过这组数据可以发现，从叶子节点点往上找可以删去的删去是符合条件的。
考虑证明为什么。
根据题意，当\(n\)为偶数时，答案一定为NO,因为我们一次只能删掉偶数条边，所以最后一定有一条边余下。
那么就考虑到，对于每一颗子树，只有当它的大小为奇数时，才可以删去。
假设有一个节点\(x\)
如果它的所有子树都为奇数，那么只有它有奇数颗子树时，这颗子树才合法。
所以\(x\)的度数为\(奇数+1=偶数\)符合题意。
所以就从深度大的往深度小的搜索即可
点此查看代码
#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)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *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 = 2e5 + 10;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){
edge[++cnt] = {v,head[u]};
head[u] = cnt;
}
int n,d[N],fa[N];
stack<int> s;
vector<int> ans;
bitset<N> vis;
void dfs1(int x,int f){
fa[x] = f;s.push(x);
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(y == f) continue;
dfs1(y,x);
}
}
void dfs2(int x){
vis[x] = true;
ans.emplace_back(x);
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;d[y]--;
if(y == fa[x] || vis[y]) continue;
if(d[y] % 2 == 0) dfs2(y);
}
}
inline void solve(){
cin>>n;
for(int i = 1,fa;i <= n; ++i){
cin>>fa;
if(!fa) continue;
add(i,fa);add(fa,i);
d[i]++,d[fa]++;
}
dfs1(1,0);
while(s.size()){
int x = s.top();s.pop();
if(d[x] % 2 == 0) dfs2(x);
}
if(ans.size() == n){
cout<<"YES\n";
for(auto i : ans) cout<<i<<'\n';
}
else cout<<"NO\n";
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T2 Darling Dance
简单题。
建出以1为根的最短路树，bfs保留即可。
点此查看代码
#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)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *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 = 3e5 + 10;
int n,m,k;
struct EDGE{int to,next,w;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v,int w){
edge[++cnt] = {v,head[u],w};
head[u] = cnt;
}
int u[N],v[N],w[N],fa1[N],fa2[N];
#define pii pair<int,int>
#define mk make_pair
bitset<N> vis;
ll dist[N];
inline void dijkstra(int s){
vis.reset();
memset(dist,0x3f,sizeof dist);
priority_queue<pii,vector<pii>,greater<pii> > q;
dist[s] = 0;
q.push(mk(0,s));
while(q.size()){
int x = q.top().second;q.pop();
if(vis[x]) continue;
vis[x] = true;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(dist[y] > dist[x] + edge[i].w){
dist[y] = dist[x] + edge[i].w;
fa1[y] = x;
fa2[y] = i;
q.push(mk(dist[y],y));
}
}
}
}
vector<int> son[N];
inline void solve(){
cin>>n>>m>>k;
for(int i = 1,u,v,w;i <= m; ++i){
cin>>u>>v>>w;
add(u,v,w),add(v,u,w);
}
dijkstra(1);
for(int i = 2;i <= n; ++i)
son[fa1[i]].emplace_back(i);
vector<int> ans;
queue<int> q;
q.push(1);
while(q.size() && ans.size() <= k){
int x = q.front();q.pop();
for(auto y : son[x]){
if(ans.size() == k)break;
ans.push_back((int)(ceil(fa2[y]/2.0)));
q.push(y);
}
}
cout<<ans.size()<<'\n';
for(auto i : ans) cout<<i<<' ';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T3 Non-breath oblige
将线段树维护值转化为维护时间戳。
将询问离线，既然询问是查询\([l,r]\)中所有询问的值的和，那么这个答案显然可以转化成\([1,r]\)的答案\(-[1,l)\)的答案，树状数组维护即可
卡卡常就过了。
线段树变成珂朵莉树也可以。
点此查看代码
#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)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define getchar getchar_unlocked
#define putchar putchar_unlocked
template<class T>
inline void read(T &x){
x = 0;
char s = getchar();
for(;s < '0' || '9' < s;s = getchar());
for(;'0' <= s && s <= '9';s = getchar())
x = (x<<1) + (x<<3) + (s^48);
}
template<class T>
void write1(T x){
if(x > 9) write1(x/10);
putchar(x%10 + '0');
}
template<class T>
inline void write(T x){
if(x < 0) x = -x,putchar('-');
write1(x);
}
const int N = 1e6 + 10;
int n,m,q;
struct node{
int op,l,r,x;
}a[N];
class Segment_Tree{
private:
struct segment_tree{
int l,r,val,lazy;
#define l(k) tree[k].l
#define r(k) tree[k].r
#define val(k) tree[k].val
#define lazy(k) tree[k].lazy
}tree[N<<2];
inline void pushdown(int k){
if(lazy(k)){
val(k<<1) = val(k<<1|1) = lazy(k);
lazy(k<<1) = lazy(k<<1|1) = lazy(k);
lazy(k) = 0;
}
}
public:
void build(int k,int l,int r){
l(k) = l,r(k) = r;val(k) = lazy(k) = 0;
if(l == r) return val(k) = 0,void();
int mid = (l + r) >> 1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int val){
if(l <= l(k) && r(k) <= r) return val(k) = lazy(k) = val,void();
pushdown(k);
int mid = (l(k) + r(k)) >> 1;
if(l <= mid) update(k<<1,l,r,val);
if(r > mid) update(k<<1|1,l,r,val);
}
int query(int k,int pos){
if(l(k) == r(k)) return val(k);
pushdown(k);
int mid = (l(k) + r(k)) >> 1;
if(pos <= mid) return query(k<<1,pos);
else return query(k<<1|1,pos);
}
}T;
vector<pair<int,int> > que[N];
class BIT{
private:
ll tree[N];
#define lowbit(x) (x&(-x))
public:
int mx;
inline void update(int pos,int val){
if(!pos) return;
for(int i = pos;i <= mx;i += lowbit(i))
tree[i] += val;
}
inline ll query(int pos){
ll res = 0;
for(int i = pos; i;i -= lowbit(i))
res += tree[i];
return res;
}
}Tr;
ll ans[N];
inline void solve(){
read(n),read(m),read(q);
T.build(1,1,n);
Tr.mx = m;
int tot = 0;
for(int i = 1;i <= m; ++i){
read(a[i].op);
if(a[i].op == 2){
tot++;
read(a[i].l),read(a[i].r),read(a[i].x);
T.update(1,a[i].l,a[i].r,i);
}
if(a[i].op == 1){
read(a[i].l),read(a[i].r);
int res1 = T.query(1,a[i].l);
int res2 = T.query(1,a[i].r);
T.update(1,a[i].l,a[i].l,res2);
T.update(1,a[i].r,a[i].r,res1);
}
if(a[i].op == 3) read(a[i].x),a[i].r = T.query(1,a[i].x);
}
for(int i = 1,l,r;i <= q; ++i){
read(l),read(r);
que[r].emplace_back(make_pair(l-1,i));
}
for(int i = 1;i <= m; ++i){
if(a[i].op == 3) Tr.update(a[i].r,a[a[i].r].x);
for(auto j : que[i])
ans[j.second] = Tr.query(i) - Tr.query(j.first);
}
for(int i = 1;i <= q; ++i) write(ans[i]),putchar('\n');
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T4 妄想感伤代偿联盟
正解好像很唐，不会。
挂一下。
打了一个记忆化加上一个数据点分治。
比某些人的正解快
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using ll = long long;
const int N = 6e5 + 10;
const ll base = 2333,mod = 1e9 + 3579;
string s[N];
int n,m,len[N];
vector<ll > H[N];
vector<ll > h[N];
ll pw[N];
unordered_map<int,int> mp[N];
int Ans[5000][5000],to[N];
inline void solve(){
pw[0] = 1;
for(int i = 1;i < N;++i) pw[i] = pw[i - 1] * base % mod;
cin>>n>>m;
for(int i = 1;i <= n; ++i){
cin>>s[i];
len[i] = s[i].length();
}
vector<int> big;big.clear();
for(int i = 1;i <= n; ++i){
H[i].push_back(0);
for(int j=0;j<len[i];j++){
H[i].push_back((H[i].back()*base%mod+s[i][j]-'a'+1)%mod);
}
h[i].push_back(0);
for(int j=len[i]-1,k=0;j>=0;j--,k++){
h[i].push_back((h[i].back()+(s[i][j]-'a'+1)*pw[k]%mod)%mod);
}
if(len[i] > 1000) big.emplace_back(i),to[i] = big.size()-1;
// for(auto j:H[i]) cout<<j<<' ';
// cout<<'\n';
// for(auto j:h[i]) cout<<j<<' ';
// cout<<"\n\n";
}
int x,y;
int siz = big.size();
for(int i = 0;i < siz; ++i){
for(int j = 0;j < siz; ++j){
if(i == j) continue;
int x = big[i],y = big[j];
int l = 0,r = min(len[x],len[y]),ans = 0;
for(int mid = r;mid >= l; --mid){
if(h[x][mid] == H[y][mid]){
ans = mid;break;
}
}
Ans[i][j] = ans;
}
}
while(m--){
cin>>x>>y;
if(x > n || y > n){cout<<"0\n";continue;}
if(x == y){cout<<len[x]<<'\n';continue;}
int l = 0,r = min(len[x],len[y]),ans = 0;
if(r > 1000){
cout<<Ans[to[x]][to[y]]<<'\n';
continue;
}
if(mp[x].find(y) != mp[x].end()){
cout<<mp[x][y]<<'\n';
continue;
}
if(min(len[x],len[y])<=1000){
for(int i=min(len[x],len[y]);i>=0;i--){
if(h[x][i]==H[y][i]){
ans = i;
break;
}
}
}
cout<<(mp[x][y] = ans)<<'\n';
}
}
signed main(){
#ifdef LOCAL
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}