首页 > 其他分享 >114

114

时间：2022-11-26 17:12:52浏览次数：51  
标签：int top long 114 fep ans define 

barrack
///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
//#define int long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;

const int N = 5e5+5,M = 1e6+5,mod = 1e9+7;
int n,m,ans,top,s[N],ro[N],qp[N];
struct Edge
{
	int u,v;
}e[M];

inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
	while(  ch>='0'&&ch<='9')  {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
	return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}

namespace task1
{	
	inline int find(int x)
	{
		return ro[x]^x?ro[x]=find(ro[x]):x;
	}
	
	inline void merge(int x,int y)
	{
		int rx=find(x),ry=find(y); if(rx==ry) return ;
		ro[rx]=ry;
	}
	
	inline int calc(int x)
	{
		fep(i,1,n) ro[i]=i;
		fep(i,1,m) if(x^i) merge(e[i].u,e[i].v);
		int res=0;
		fep(i,1,top) res|=(find(s[i])!=find(s[1]));
		return res;
	}
	
	inline void solve()
	{
		int res=0; if(!top) return ;
		fep(i,1,m) res+=calc(i);
		addmod(ans,qp[m-res]);
	}
	
	inline void dfs(int u)
	{
		if(u>n) return solve();
		s[++top]=u; dfs(u+1);
		--top; dfs(u+1);
	}
	
	inline void Solve()
	{
		dfs(1); printf("%d",ans);
	}
}

namespace task4
{
	inline void solve()
	{
		int ans=0;
		fep(i,1,n)
		{
			addmod(ans,1ll*(i-1)*qp[m-1]%mod);
			addmod(ans,qp[m]);
		}
		printf("%d",ans);
	}
}

namespace task5
{	
	vector<int> G[N]; int ans=0,f[N][3];
	inline void add(int u,int v)
	{
		G[u].emplace_back(v);
	}
	
	inline void dfs(int u,int fa)
	{
		f[u][0]=1;
		for(auto v:G[u]) if(v^fa)
		{
			dfs(v,u);
			addmod(f[u][2],1ll*Mod(f[u][1]+f[u][2])*Mod(f[v][1]+f[v][2])%mod);
			addmod(f[u][1],1ll*f[u][0]*Mod(f[v][1]+f[v][2])%mod);
		}
		addmod(ans,1ll*Mod(f[u][1]+f[u][2])*qp[m-1]%mod);
		addmod(ans,qp[m]);
		addmod(f[u][1],1);
	}
	
	inline void solve()
	{
		fep(i,1,m) add(e[i].u,e[i].v),add(e[i].v,e[i].u);
		dfs(1,0); printf("%d",ans);
	}
}

signed main()
{
	freopen("barrack.in","r",stdin);
//	freopen("barrack2.in","r",stdin);
	freopen("barrack.out","w",stdout);
	n=read(),m=read(); qp[0]=1;
	fep(i,1,m) qp[i]=2ll*qp[i-1]%mod;
	bool flag=1;
	fep(i,1,m)
	{
		int u=read(),v=read();
		e[i]={u,v}; flag&=(abs(u-v)==1);
	}
	if(n<=16) task1::Solve();
	else if(flag) task4::solve();
	else if(n-1==m) task5::solve();
	else puts("114514");
	return 0;
}

match#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
#define int ull
#define ull unsigned long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;

const int N = 3e5+5;
ull n,mod=(1ll<<60),a[N],b[N];

inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
	while(  ch>='0'&&ch<='9')  {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
	return s*w;
}

namespace task1
{
	ull f[3000+5][3000+5];
	inline void solve()
	{
		fep(r,1,n)
		{
			ull mx1=0,mx2=0;
			feb(l,r,1)
			{
				mx1=max(mx1,a[l]); mx2=max(mx2,b[l]);
				f[l][r]=(f[l+1][r]+mx1*mx2%mod)%mod;
			}
		}
		int Q=read();
		while(Q--)
		{
			int l=read(),r=read(); ull ans=0;
			fep(i,l,r) ans=(ans+f[l][i])%mod;
			printf("%lld\n",(LL)ans);
		}
	}
}

namespace task2
{
	int top=0,s[N],pre1[N],pre2[N];
	inline ull mul(int x,int t)
	{
		ull ans=0;
		while(t)
		{
			if(t&1) ans=(ans+x)%mod;
			x=(x+x)%mod; t>>=1;
		}
		return ans;
	}
	
	inline void solve()
	{
		fep(i,1,n)
		{
			while(top&&a[s[top]]<a[i]) --top;
			pre1[i]=s[top]; s[++top]=i;
		}
		top=0;
		fep(i,1,n)
		{
			while(top&&b[s[top]]<b[i]) --top;
			pre2[i]=s[top]; s[++top]=i;
		}
		int Q=read();
		while(Q--)
		{
			int l=read(),r=read(); ull ans=0;
			feb(i,r,l)
			{
				int p1=i,p2=i;
				while(p1>=l&&p2>=l)
				{
					if(pre1[p1]<pre2[p2])
					{
						int L=max(l-1,pre2[p2]),R=min(p1,p2);
						ans=(ans+mul(mul(R-L,a[p1]),b[p2]))%mod;
						p2=pre2[p2];
					}
					else
					{
						int L=max(l-1,pre1[p1]),R=min(p1,p2);
						ans=(ans+mul(mul(R-L,a[p1]),b[p2]))%mod;
						p1=pre1[p1];
					}
//					cout<<i<<" "<<p1<<" "<<p2<<" "<<ans<<"\n";
				}
			}
			printf("%lld\n",(LL)ans);
		}
	}
}

signed main()
{
	freopen("match.in","r",stdin);
//	freopen("match3.in","r",stdin);
	freopen("match.out","w",stdout);
//	if(system("fc /N /W match.out match3.ans")) puts("wa");
	int _T=read(); n=read();
	fep(i,1,n) a[i]=read();
	fep(i,1,n) b[i]=read();
	if(n<=3000) task1::solve();
	else task2::solve();
	return 0;
}
///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
#define int long long
#define pr pair<int,int> 
#define mpr make_pair
using namespace std;

const int N = 1e3+5,mod = 998244353;
int n,Vc,Vf,m,a[N][N],f[N][N],s[N],b[N][N],c[N][N],sum1[N],sum2[N];

inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
	while(  ch>='0'&&ch<='9')  {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
	return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}

signed main()
{
	freopen("plant.in","r",stdin);
//	freopen("plant3.in","r",stdin);
	freopen("plant.out","w",stdout);
	int _T=read(),Id=read();
	while(_T--)
	{
		n=read(),m=read(),Vc=read(),Vf=read();
		fep(i,1,n) fep(j,1,m) scanf("%1lld",&a[i][j]),b[i][j]=c[i][j]=0;
		fep(i,1,n)
		{
			int top=0;
			fep(j,1,m)
			{
				if(a[i][j]) while(top) b[i][s[top--]]=j;
				else s[++top]=j;
			}
			while(top) b[i][s[top--]]=m+1;
		}
		fep(j,1,m)
		{
			int top=0;
			fep(i,1,n)
			{
				if(a[i][j]) while(top) c[s[top--]][j]=i;
				else s[++top]=i;
			}
			while(top) c[s[top--]][j]=n+1;
		}
		int ans1=0,ans2=0;
		fep(i,1,m) sum1[i]=sum2[i]=0;
		feb(i,n,1)
		{
			fep(j,1,m)//(x1,y0)
			{
				int res1=b[i][j]-j-1;
				if(i+1>n||a[i+1][j]) continue;
//				fep(k,i+2,n)
//				{
//					if(a[k][j]) break;
//					int res2=b[k][j]-j-1;
//					if(res2<=0) continue;
//					int res3=c[k][j]-k-1;
//					addmod(ans1,max(0ll,1ll*res1*res2%mod));
//					addmod(ans2,max(0ll,1ll*res1*res2%mod*res3%mod));
//				}
				if(i+2>n||a[i+2][j]) sum1[j]=sum2[j]=0;
				else
				{
					int res2=b[i+2][j]-j-1,res3=c[i+2][j]-(i+2)-1;
					addmod(sum1[j],max(0ll,res2));
					addmod(sum2[j],max(0ll,1ll*res2*res3%mod));
				}
				addmod(ans1,max(0ll,1ll*res1*sum1[j]));
				addmod(ans2,max(0ll,1ll*res1*sum2[j]));
//				cout<<i<<" "<<j<<" "<<ans1<<" "<<ans2<<"\n";
			}
//			cout<<i<<"\n";
//			fep(j,1,m) cout<<sum1[j]<<" "; puts("");
		}
		printf("%lld %lld\n",1ll*ans1*Vc%mod,1ll*ans2*Vf%mod);
	}
	
	return 0;
}

///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
//#define int long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;

const int N = 300+5,M = 2e6+6;
int n,m,k,a[M],lst[N<<1],c[N<<1]; set<int> s;
struct Node
{
	int opt,x,y;
}ans[M<<1];

inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
	while(  ch>='0'&&ch<='9')  {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
	return s*w;
}

inline void del(int x,int p)
{
//	assert(lst[x]==p);
//	cout<<x<<" "<<p<<"\n";
	lst[x]=0;
	c[p]=0;
	s.insert(p);
}

inline void add(int x,int p)//color stack
{
	lst[x]=p;
	c[p]=x;
	s.erase(p);
}

signed main()
{
	freopen("meow.in","r",stdin);
//	freopen("meow1.in","r",stdin);
	freopen("meow.out","w",stdout);
	int _T=read();
	while(_T--)
	{
		n=read(),m=read(),k=read();
//		cout<<n<<" "<<m<<" "<<k<<"\n";
		fep(i,1,m) a[i]=read();
//		fep(i,1,m) cout<<a[i]<<" "; puts("");
		int cnt=0; s.clear();
		fep(i,1,n-1) s.insert(i),s.insert(i+n);
		fep(i,1,m)
		{
//			cout<<"lst:";
//			fep(j,1,k) cout<<lst[j]<<" "; puts("");
			if(lst[a[i]])
			{
				if(lst[a[i]]>n)//bottom
				{
					ans[++cnt]={1,n,0};
					ans[++cnt]={2,lst[a[i]]-n,n};
					del(a[i],lst[a[i]]);
				}
				else//top
				{
					ans[++cnt]={1,lst[a[i]]};
					del(a[i],lst[a[i]]);
				}
			}
			else
			{
				//c[x]:stack[x]'s color
				//lst[x]:color[x] in stack
				if(!s.empty())
				{
					int it=*s.begin(); // cout<<it<<"\n";
					if(it>n)
					{
						int tmp=c[it-n];// cout<<c[it-n]<<"\n";
						del(tmp,it-n);
						add(tmp,it);
						add(a[i],it-n);
					}
					else add(a[i],it);
					ans[++cnt]={1,it>n?it-n:it,0};
				}
				else
				{
					int tmp=i+1,Lst=cnt+1; ans[++cnt]={1,0,0};
					while(lst[a[tmp]]<n)// in top
					{
						if(lst[a[tmp]])
						{
							ans[++cnt]={1,lst[a[tmp]],0};
							del(a[tmp],lst[a[tmp]]);
						}
						else
						{
							int it=*s.begin(); s.erase(it);
							ans[++cnt]={1,it,0}; lst[a[tmp]]=it;
						}
					}
					int S=lst[a[tmp]];
					ans[Lst].x=S-n;
					ans[++cnt]={1,n};
					ans[++cnt]={2,S-n,n};
					del(a[tmp],S); Lst=c[S-n];
					del(Lst,S-n); add(Lst,S); add(a[i],S-n);
					i=tmp;
				}
			}
		}
		printf("%d\n",cnt);
		fep(i,1,cnt)
		{
			if(ans[i].opt==1) printf("%d %d\n",ans[i].opt,ans[i].x);
			else printf("%d %d %d\n",ans[i].opt,ans[i].x,ans[i].y);
		}
	}
	return 0;
}

标签：int,top,long,114,fep,ans,define
From： https://www.cnblogs.com/lasky/p/16927755.html

相关文章

  • CF1141 Div3 欢乐信心赛
    非常轻松的比赛，连我这样的菜鸡也感到充满力量。A用类似于质因数分解的操作搞一搞即可。B将环复制一遍。C可以发现\(q\)就是差分数组。那么差分数组之和最大的地方......
  • 退役划水 #114515
    好像只会写流水账。所以就不写了。......
  • [题解] CF1149D Abandoning Roads
    难得自己想出来一道3000分的题，虽然说考试的时候打挂了...首先先对较小的边缩点，然后求连通块内的最短路。显然，连通块内其实想怎么走就怎么走，但不能走较大的边。然后不同......
  • 114：设计模式_工厂模式实现
       设计模式是面向对象语言特有的内容，是我们在面临某一类问题时候固定的做法，设计模式有很多种，比较流行的是：GOF（GoupOfFour）23种设计模式。当然，我们没有必要全部学习......
  • 114. Flatten Binary Tree to Linked List
       /例如根节点为1，左2右3classSolution{    TreeNodeprev=null;    publicvoidflatten(TreeNoderoot){//先把最大的数设在root.right，然后剩下......
  • 114. 二叉树展开为链表 -----
    给你二叉树的根结点root，请你将它展开为一个单链表：展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展开后的单链......
  • 场效应管SI7114DN-T1-GE3(11.7A)SM3323NHQAC-TRG(54A)MOSFET NCH 30V
    1、型号：SM3323NHQAC-TRGSM3323NHQAC描述：N沟道30V54A封装：DFN3x3D-82、型号：SI7114DN-T1-GE3SI7114DN描述：MOSFETN-CH30V11.7APPAK1212-8FET类型：N通道技术：MOSFET（金......
  • SP11469 SUBSET - Balanced Cow Subsets Sol
    考虑枚举\(3^n\)种情况，用三进制数表示。对于每一位，\(0\)表示不放，\(1\)表示放入第一个集合，\(2\)表示放入第二个集合。这样显然会TLE。考虑meetinthemiddle。考......
  • MYSQL ERROR 1146 Table doesnt exist 解析
    原创转载请注明出处源码版本5.7.14在MYSQL使用innodb的时候我们有时候会看到如下报错：ERROR1146(42S02):Table'test.test1bak'doesn'texist首先总结下原......
  • 20221114
    存疑的点分类阈值是否和常识一样为0.5/如果改成不是奇偶数判断(例如是否被3整除)阈值是否是0.5BATCH_SIZE:即一次训练所抓取的数据样本数量，更改之后有什么影响，built_......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99