110

？？？

洛谷有人从红到黑是递增的

今天两个大凶，这波怎么活

你**把,老二*

说实话，我一年半没碰过树这个OI概念了

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=1e5+5;
int n,m,k;
ull P[70],a[maxn],mp;
vector<int>G[maxn];
int tot,dfn[maxn],rnk[maxn],L[maxn],R[maxn],top[maxn],siz[maxn],fa[maxn],dep[maxn],hson[maxn],cnt,lid[maxn],idl[maxn];
void dfs_build(int u,int F){
	siz[u]=1;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==F)continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs_build(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]])hson[u]=v;
	}
}
void dfs(int u,int F){
	dfn[u]=++tot;
	rnk[tot]=u;
	if(hson[u]){
		top[hson[u]]=top[u];
		dfs(hson[u],u);
	}
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==F||v==hson[u])continue;
		top[v]=v;
		dfs(v,u);
	}
}
int opt[maxn];
struct SGT{
	vector<ull>val[2],nval[2];
	vector<int>ls,rs,mid;
}st;
vector<SGT>tr;
int trid;
void pushup(int rt){
	tr[trid].val[0][rt]=(tr[trid].val[0][tr[trid].ls[rt]]&tr[trid].val[1][tr[trid].rs[rt]])
						+(~tr[trid].val[0][tr[trid].ls[rt]]&tr[trid].val[0][tr[trid].rs[rt]]);
	tr[trid].val[1][rt]=(tr[trid].val[1][tr[trid].ls[rt]]&tr[trid].val[1][tr[trid].rs[rt]])
						+(~tr[trid].val[1][tr[trid].ls[rt]]&tr[trid].val[0][tr[trid].rs[rt]]);
	tr[trid].nval[0][rt]=(tr[trid].nval[0][tr[trid].rs[rt]]&tr[trid].nval[1][tr[trid].ls[rt]])
						+(~tr[trid].nval[0][tr[trid].rs[rt]]&tr[trid].nval[0][tr[trid].ls[rt]]);
	tr[trid].nval[1][rt]=(tr[trid].nval[1][tr[trid].rs[rt]]&tr[trid].nval[1][tr[trid].ls[rt]])
						+(~tr[trid].nval[1][tr[trid].rs[rt]]&tr[trid].nval[0][tr[trid].ls[rt]]);
//	for(int i=0;i<k;i++){
//		tr[trid].val[0][rt]+=tr[trid].val[(tr[trid].val[0][tr[trid].ls[rt]]>>i)&1][tr[trid].rs[rt]]&P[i];
//		tr[trid].val[1][rt]+=tr[trid].val[(tr[trid].val[1][tr[trid].ls[rt]]>>i)&1][tr[trid].rs[rt]]&P[i];
//		tr[trid].nval[0][rt]+=tr[trid].nval[(tr[trid].nval[0][tr[trid].rs[rt]]>>i)&1][tr[trid].ls[rt]]&P[i];
//		tr[trid].nval[1][rt]+=tr[trid].nval[(tr[trid].nval[1][tr[trid].rs[rt]]>>i)&1][tr[trid].ls[rt]]&P[i];
//	}
}
int newnode(){
	tr[trid].val[0].push_back(0);
	tr[trid].val[1].push_back(0);
	tr[trid].nval[0].push_back(0);
	tr[trid].nval[1].push_back(0);
	tr[trid].ls.push_back(0);
	tr[trid].rs.push_back(0);
	tr[trid].mid.push_back(0);
	int t=tr[trid].mid.size();
	return t-1;
}
ull calc(ull val,int op,ull xx){
	if(op==1)return (val&xx);
	if(op==2)return (val|xx);
	if(op==3)return (val^xx);
}
void buildcnt(int l,int r,int rt){
//	cout<<l<<' '<<r<<' '<<rt<<'\n';
	if(l==r)return;
	int sum=0;
	for(int i=l;i<=r;i++)sum+=siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]];
	sum/=2;
	int now=0;
	for(int i=l;i<=r;i++){
		if(now+siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]]>=sum){
			tr[trid].mid[rt]=i;
			break;
		}
		now+=siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]];
	}
	if(tr[trid].mid[rt]==r)tr[trid].mid[rt]--;
	int t=newnode();
	tr[trid].ls[rt]=t;
	buildcnt(l,tr[trid].mid[rt],tr[trid].ls[rt]);
	t=newnode();
	tr[trid].rs[rt]=t;
	buildcnt(tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
void build(int l,int r,int rt){
	if(l==r){
//		cout<<l<<' '<<a[rnk[l+dfn[lid[trid]]-1]]<<'\n';
		tr[trid].val[0][rt]=tr[trid].nval[0][rt]=calc(0,opt[rnk[l+dfn[lid[trid]]-1]],a[rnk[l+dfn[lid[trid]]-1]]);
		tr[trid].val[1][rt]=tr[trid].nval[1][rt]=calc(mp,opt[rnk[l+dfn[lid[trid]]-1]],a[rnk[l+dfn[lid[trid]]-1]]);
		return;
	}
	build(l,tr[trid].mid[rt],tr[trid].ls[rt]);
	build(tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
	pushup(rt);
}
void init(int l,int r){
//	cout<<l<<' '<<r<<'\n';
	tr.push_back(st);
	newnode();
	newnode();
	buildcnt(1,r-l+1,1);
	build(1,r-l+1,1);
//	cout<<1111<<'\n';
}
void update(int X,int opc,ull vc,int l,int r,int rt){
	if(l==r){
		tr[trid].val[0][rt]=tr[trid].nval[0][rt]=calc(0,opc,vc);
		tr[trid].val[1][rt]=tr[trid].nval[1][rt]=calc(mp,opc,vc);
		return;
	}
	if(X<=tr[trid].mid[rt])update(X,opc,vc,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else update(X,opc,vc,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
	pushup(rt);
}
struct Val{
	ull val[2];
	void init(){val[0]=val[1]=0;}
};
Val query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		Val res;
		res.val[0]=tr[trid].val[0][rt],res.val[1]=tr[trid].val[1][rt];
		return res;
	}
	if(L<=tr[trid].mid[rt]&&tr[trid].mid[rt]+1<=R){
		Val res;
		Val ls=query(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
		Val rs=query(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
		res.val[0]=(ls.val[0]&rs.val[1])
				 +(~ls.val[0]&rs.val[0]);
		res.val[1]=(ls.val[1]&rs.val[1])
				 +(~ls.val[1]&rs.val[0]);
		return res;
	}else if(L<=tr[trid].mid[rt])return query(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else return query(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
Val queryn(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		Val res;
		res.val[0]=tr[trid].nval[0][rt],res.val[1]=tr[trid].nval[1][rt];
		return res;
	}
	if(L<=tr[trid].mid[rt]&&tr[trid].mid[rt]+1<=R){
		Val res;
		Val rs=queryn(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
		Val ls=queryn(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
		res.val[0]=(ls.val[0]&rs.val[1])
				 +(~ls.val[0]&rs.val[0]);
		res.val[1]=(ls.val[1]&rs.val[1])
				 +(~ls.val[1]&rs.val[0]);
		return res;
	}else if(L<=tr[trid].mid[rt])return queryn(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else return queryn(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
vector<pair<int,int> >lu,lv;
vector<int>ru,rv;
Val getans(int u,int v){
	Val res;
	bool flag=0;
	int tu=u,tv=v;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])rv.push_back(v),lv.push_back({dfn[top[v]],dfn[v]}),v=fa[top[v]];
		else ru.push_back(u),lu.push_back({dfn[top[u]],dfn[u]}),u=fa[top[u]];
	}
	if(dep[u]>dep[v])ru.push_back(u),lu.push_back({dfn[v],dfn[u]});
	else rv.push_back(v),lv.push_back({dfn[u],dfn[v]});
	u=tu,v=tv;
	for(int i=0;i<lu.size();i++){
		trid=idl[top[ru[i]]];
//		cout<<trid<<' '<<lu[i].first-L[trid]+1<<' '<<lu[i].second-L[trid]+1<<'\n';
		Val now=queryn(lu[i].first-L[trid]+1,lu[i].second-L[trid]+1,1,R[trid]-L[trid]+1,1);
		if(!flag){
			res=now;
			flag=1;
		}else{
			res.val[0]=(res.val[0]&now.val[1])
					 +(~res.val[0]&now.val[0]);
			res.val[1]=(res.val[1]&now.val[1])
					 +(~res.val[1]&now.val[0]);
		}
//		put(res);
	}
//	cout<<1111;
	for(int i=rv.size()-1;i>=0;i--){
		trid=idl[top[rv[i]]];
//		cout<<trid<<' '<<lv[i].first<<' '<<lv[i].second<<'\n';
		Val now=query(lv[i].first-L[trid]+1,lv[i].second-L[trid]+1,1,R[trid]-L[trid]+1,1);
		if(!flag){
			res=now;
			flag=1;
		}else{
			res.val[0]=(res.val[0]&now.val[1])
					 +(~res.val[0]&now.val[0]);
			res.val[1]=(res.val[1]&now.val[1])
					 +(~res.val[1]&now.val[0]);
		}
//		put(res);
	}
	ru.clear();
	lu.clear();
	rv.clear();
	lv.clear();
	return res;
}
signed main(){
//	freopen("data.txt","r",stdin);
//	freopen("std.txt","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)cin>>opt[i]>>a[i];
	P[0]=1;
	for(int i=1;i<=63;i++)P[i]=P[i-1]*2;
	for(int i=0;i<k;i++)mp+=P[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dep[1]=1;
	fa[1]=1;
	dfs_build(1,0);
	top[1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++){
		L[i]=n+1;
		if(!idl[top[i]]){
			idl[top[i]]=++cnt;
			lid[cnt]=top[i];
		}
//		cout<<top[i]<<' ';
	}
//	cout<<'\n';
	for(int i=1;i<=n;i++)L[idl[top[i]]]=min(L[idl[top[i]]],dfn[i]),R[idl[top[i]]]=max(R[idl[top[i]]],dfn[i]);
	tr.push_back(st);
	for(int i=1;i<=cnt;i++){
		trid=i;
		init(L[i],R[i]);
//		for(int j=1;j<tr[trid].mid.size();j++){
//			cout<<j<<' '<<tr[trid].ls[j]<<' '<<tr[trid].rs[j]<<' '<<tr[trid].mid[j]<<'\n';
//			for(int K=k-1;K>=0;K--)cout<<tr[trid].val[K][0][j]<<' '<<tr[trid].val[K][1][j]<<'\n';
//			cout<<'\n';
//			for(int K=k-1;K>=0;K--)cout<<tr[trid].nval[K][0][j]<<' '<<tr[trid].nval[K][1][j]<<'\n';
//			cout<<'\n';
//		}
//		cout<<'\n';
	}
	while(m--){
		int OP,x,y;
		ull z;
		cin>>OP>>x>>y>>z;
		if(OP==1){
			Val res=getans(x,y);
//			put(res);
			ull now=0,ans=0;
			for(int i=k-1;i>=0;i--){
				if((res.val[0]>>i)&1)ans+=P[i];
				else{
					if((res.val[1]>>i)&1){
						if(now+P[i]<=z){
							now+=P[i];
							ans+=P[i];
						}
					}
				}
			}
			cout<<ans<<'\n';
		}else{
			trid=idl[top[x]];
			update(dfn[x]-L[trid]+1,y,z,1,R[trid]-L[trid]+1,1);
//			for(int i=1;i<=cnt;i++){
//				trid=i;
//				for(int j=1;j<tr[trid].mid.size();j++){
//					cout<<j<<' '<<tr[trid].ls[j]<<' '<<tr[trid].rs[j]<<' '<<tr[trid].mid[j]<<'\n';
//					for(int K=k-1;K>=0;K--)cout<<tr[trid].val[K][0][j]<<' '<<tr[trid].val[K][1][j]<<'\n';
//					cout<<'\n';
//					for(int K=k-1;K>=0;K--)cout<<tr[trid].nval[K][0][j]<<' '<<tr[trid].nval[K][1][j]<<'\n';
//					cout<<'\n';
//				}
//				cout<<'\n';
//			}
		}
	}
	return 0;
}

@ 我过了

@ 我能抄代码吗

@

@ 请输入文本

• 神了

33DAI还是太细节了，放csp能被他阴死80%（20%记不住998244353）

正常

正常。（笑）

（😍）

因为你的op函数从小到大，所以你的返回值会是最大的公共段，但是如果出现小的公共段，肯定更优（重复的较少），所以找到第一个match的，就break掉。

#include <bits/stdc++.h>
using namespace std;
int n;
string word[25];
int used[25];
int ans=0;
char startch;
int op(string A,string B) 
{
	int la=A.size(),lb =B.size();
	int maxk = 0;
	for (int k=1;k<min(la,lb);k++)
	{
		bool match=true;
		for (int i=0;i<k;i++) 
		{
			if(A[la-k+i]!=B[i]) 
			{
				match=false;
				break;
			}
		}
		if(match){maxk=k; break;}
	}
	return maxk;
}
void dfs(int last,int len)
{
	ans=max(ans,len);
	for(int i=1;i<=n;i++)
	{
		if(used[i]>=2)continue;
		int k=op(word[last],word[i]);
		if(k==0)continue;
		used[i]++;
		dfs(i,len+word[i].size()-k);
		used[i]--;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>word[i];
	}
	cin>>startch;
	for(int i=1;i<=n;i++)
	{
		if(word[i][0]==startch)
		{
			used[i]++;
			dfs(i,word[i].size());
			used[i]--;
		}
	}
	cout<<ans<<endl;
	return 0;
}

@ 谢谢

前面加“```cpp”

@ 你竟然盗我头像!!!

有入把窝的头像盗了喵

@ 啊?!

111111111111111111

1

@

不会就别乱说，真像你那样的话学高精度有什么用？

double的范围是可以到pow(10,308)，但精度只有pow(10,16），后面的位数会丢失

@ 好感谢指正

以后可以直接打$10^5$ 不必那么麻烦pow（10,5）之类的

using namespace std;
struct shi_jian
{
    int money,time;
}arr[100005];
int used[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,head=1;
    cin>>n;
    int xia_biao=1,sum=0;
    while(n--)
    {
        int num,piece,t;
        cin>>num>>piece>>t;
        if(num==0)
        {
            sum+=piece;
            arr[xia_biao].money=piece;
            arr[xia_biao].time=t;
            xia_biao++;
        }
        else
        {
            while(head <= xia_biao && t - arr[head].time > 45) {
                head++;
            }
            int cnt=0;
            for(int i=head;i<=xia_biao;i++)
            {
                if(arr[i].money>=piece&&t-arr[i].time<=45&&used[i]==0)
                {
                    used[i]=1;
                    cnt++;
                    break;
                }
            }
            if(cnt==0)sum+=piece;
        }
    }
    cout<<sum;
}

@ 不要把自己的代码发给我

@ 要说错哪了

@ 你是不是@错人了

@ 是

我大概看了下你的代码

1.核心错误：变量名冲突

  for(int i=1;i<=n;i++) {// 外层 i
      ...
      for(int i=1;i<=cnt;i++) {// 内层 i，冲突！

内层 i 会覆盖外层 i，导致外层循环错乱。

2.其次 优惠票使用策略错误—应该优先使用最早过期的，而不是随便找一个

3.不太重要的小毛病

  yh[i].time=-1 

标记已用,可以，但数组不会清理，越往后越慢

改正代码（45TLE未优化）：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
ll sum;
int way,price,tim;
int cnt;
struct youhui {
    int time;
    int money;
} yh[100005];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>way>>price>>tim;
        if(way==0) {  // 地铁
            cnt++;
            yh[cnt].time=tim;
            yh[cnt].money=price;
            sum+=price;
        } else {  // 公交
            int flag=0;
            // 找最早过期的可用优惠票（FIFO）
            for(int j=1;j<=cnt;j++) {
                if(yh[j].time==-1) continue;
                if(tim-yh[j].time<=45 && yh[j].money>=price) {
                    flag=1;
                    yh[j].time=-1;
                    break;
                }
            }
            if(!flag) sum+=price;
        }
    }
    cout<<sum;
    return 0;
}

但是该代码任会超时 注意到 对于100%的数据， n≤$10^5$,$t_i$≤$10^9$ 1≤$price_i$≤1000

n≤$10^5$ 会TLE

优化： 用队列按时间维护票，每次坐公交： 弹出过期票（时间差>45） 在剩余票中找票价≥公交票价的 如果有，用掉一张（标记或删除）

优化代码： （会RE，没时间了，以后会修改）

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    ll sum = 0;
    // 队列按时间存票，multiset按票价存可用票
    queue<pair<int,int>> q;  // {时间, 票价}
    multiset<int> s;  // 可用票的票价
    
    for (int i = 1; i <= n; i++) {
        int way, price, tim;
        cin >> way >> price >> tim;
        
        if (way == 0) {  // 地铁
            sum += price;
            q.push({tim, price});
            s.insert(price);
        } else {  // 公交
            // 弹出过期票
            while (!q.empty() && tim - q.front().first > 45) {
                s.erase(s.find(q.front().second));
                q.pop();
            }
            // 找票价≥公交票价的票
            auto it = s.lower_bound(price);
            if (it != s.end()) {
                // 用掉这张票
                s.erase(it);
                // 从队列中删除对应票（需要知道是哪个，但队列不方便删中间）
                // 问题：multiset删了，队列里还有，但后面会过期自动弹出
                // 但队列里的票和multiset不同步！
            } else {
                sum += price;
            }
        }
    }
    
    cout << sum;
    return 0;
}

创作不易，不喜勿喷

高德地图头上绿绿的

????

看懂的人已经笑了