首页 > 其他分享 >杂题 Solution 速通 #1

杂题 Solution 速通 #1

时间:2024-08-13 21:39:50浏览次数:12  
标签:return 速通 int Solution read while && buc 杂题

[ICPC2021 Nanjing R] Ancient Magic Circle in Teyvat

设 \(f_x\) 表示钦定至少有 \(x\) 条边的四元子图个数,由容斥我们有一条边都没有的子图个数是 \(f_0-f_1+f_2-f_3+f_4-f_5+f_6\),而所有边都有的个数就是 \(f_6\)。作差之后只需要求 \(f_0,f_1,f_2,f_3,f_4,f_5\)。

子图计数只要不是数 \(K_4\),其它所有的四元图都是好做的,把你会的三元环、四元环、\(K_4\) 少一条边的计数方法全用上就可以了。

#include <cstdio>
#include <vector>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=100003,M=200003;
typedef long long ll;
typedef __int128 lll;
int n,m;lll res;
void write(lll x){if(x>9) write(x/10);putchar((x%10)^48);}
lll C4(int x){return (lll)x*(x-1)*(x-2)*(x-3)/24;}
lll C3(int x){return (lll)x*(x-1)*(x-2)/6;}
lll C2(int x){return (lll)x*(x-1)>>1;}
int eu[M],ev[M],d[N];
vector<int> adj[N],vec[N],ec[N];
int vis[N],ps[N];
inline bool cmp(int x,int y){
	if(d[x]!=d[y]) return d[x]>d[y];
	return x<y;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;++i){
		eu[i]=read();ev[i]=read();
		adj[eu[i]].emplace_back(ev[i]);
		adj[ev[i]].emplace_back(eu[i]);
	}
	for(int i=1;i<=n;++i) d[i]=adj[i].size();
	for(int i=1;i<=m;++i)
		if(cmp(eu[i],ev[i])) vec[eu[i]].emplace_back(ev[i]);
		else vec[ev[i]].emplace_back(eu[i]);
	for(int i=1;i<=n;++i) ec[i].resize(vec[i].size());
	res=C4(n)-m*C2(n-2);
	lll tmp=0;
	for(int i=1;i<=m;++i){
		tmp+=(lll)(d[eu[i]]+d[ev[i]]-2)*(n-4);
		res-=(lll)(d[eu[i]]-1)*(d[ev[i]]-1);
	}
	res+=C2(m)+(tmp>>1);
	for(int x=1;x<=n;++x){
		res-=C3(d[x]);
		int id=0;
		for(int y:vec[x]) vis[y]=x,ps[y]=id++;
		id=0;
		for(int y:vec[x]){
			int nid=0;
			for(int z:vec[y]){
				if(vis[z]==x){
					res+=d[x]+d[y]+d[z]-n;
					res-=ec[x][id]++;
					res-=ec[x][ps[z]]++;
					res-=ec[y][nid]++;
				}
				++nid;
			}
			++id;
		}
	}
	for(int x=1;x<=n;++x){
		for(int y:vec[x])
			for(int z:adj[y]) vis[z]=0;
		for(int y:vec[x])
			for(int z:adj[y]) if(cmp(x,z)) res+=vis[z]++;
	}
	if(res<0) res=-res;
	write(res);putchar('\n');
	return 0;
}

[GDCPC2023] Classic Problem

套路题,离散化之后 Boruvka 一下就行了。

我为啥这玩意需要写拍才能调出来啊?

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
typedef long long ll;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=100003,M=400013;
const int INF=0x3f3f3f3f;
int n,m;ll res;
int eu[N],ev[N],ew[N];
int buc[M],rk;
vector<pii> vec[M];
vector<int> arr[M];
int f[M],dir[M],mn[M];
int rt(int x){
	if(f[x]==x) return x;
	return f[x]=rt(f[x]);
}
int dis(int x,int y){
	if(x>y) swap(x,y);
	return buc[y-1]+1-buc[x];
}
int pre[M],suf[M],cur[M];
void solve(){
	n=read();m=read();rk=0;res=0;
	for(int i=1;i<=m;++i){
		buc[++rk]=eu[i]=read();if(eu[i]>1) buc[++rk]=eu[i]-1;
		buc[++rk]=ev[i]=read();if(ev[i]>1) buc[++rk]=ev[i]-1;
		ew[i]=read();
	}
	buc[++rk]=n;
	sort(buc+1,buc+rk+1);rk=unique(buc+1,buc+rk+1)-buc-1;
	n=rk;
	for(int i=1;i<=n;++i) vec[i].clear(),f[i]=i,res+=buc[i]-buc[i-1]-1;
	for(int i=1;i<=m;++i){
		eu[i]=lower_bound(buc+1,buc+n+1,eu[i])-buc;
		ev[i]=lower_bound(buc+1,buc+n+1,ev[i])-buc;
		vec[eu[i]].emplace_back(ev[i],ew[i]);
		vec[ev[i]].emplace_back(eu[i],ew[i]);
	}
	int cnt=n-1;
	while(cnt){
		for(int i=1;i<=n;++i) arr[rt(i)].emplace_back(i),cur[i]=-1;
		for(int i=1;i<=n;++i){
			dir[i]=-1;mn[i]=INF;
			if(f[i]==i){
				int sz=arr[i].size();
				for(int t=0;t<sz;++t){
					int x=arr[i][t];
					if(t&&arr[i][t-1]==x-1) pre[x]=pre[x-1];
					else pre[x]=x-1;
				}
				for(int t=sz-1;~t;--t){
					int x=arr[i][t];
					if(t+1<sz&&arr[i][t+1]==x+1) suf[x]=suf[x+1];
					else suf[x]=x+1;
				}
				for(int x:arr[i]){
					for(auto [y,w]:vec[x]){
						if(rt(y)!=i&&w<mn[i]) dir[i]=y,mn[i]=w;
						cur[y]=x;
					}
					int t;
					t=x-1;
					while(t){
						if(cur[t]==x){--t;continue;}
						if(rt(t)==i){t=pre[t];continue;}
						if(dis(x,t)<mn[i]) mn[i]=dis(x,t),dir[i]=t;
						break;
					}
					t=x+1;
					while(t<=n){
						if(cur[t]==x){++t;continue;}
						if(rt(t)==i){t=suf[t];continue;}
						if(dis(x,t)<mn[i]) mn[i]=dis(x,t),dir[i]=t;
						break;
					}
				}
			}
		}
		for(int i=1;i<=n;++i){
			arr[i].clear();
			if((~dir[i])&&rt(i)!=rt(dir[i])) f[rt(i)]=rt(dir[i]),res+=mn[i],--cnt;
		}
	}
	printf("%lld\n",res);
}
int main(){
	int tc=read();
	while(tc--) solve();
	return 0;
}

[JOISC2017] Sparklers

很喜欢的一道牛题啊!但是时间问题我们还是速通 Solution。

考虑策略是两个人一但碰面了就不会分开,这样两个人碰面相当于合并成一个人,燃烧时间 \(+T\)。

二分速度 \(v\)。就变成了两个队列,每次可以花费距离的代价买下一个队头,然后赚 \(2Tv\) 的距离,问能否删空队列。

考虑经典的合并策略贪心,如果一个亏的策略下一个策略是赚的策略,那么显然在中间插入另一个队列的策略不优。所以合并这些策略后会形成前面都是赚后面都是亏的两个策略队列。

接下来一步很神。考虑赚的两段前缀一定先取完,而且能取则取。亏的两段后缀呢?考虑倒着做,最终花费代价恒定,所以说最终状态确定,这样倒推的时候也是能取则取。只需要判断一下正着倒着能否取完就行了。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
int n,k,t;
const int N=100003;
typedef long long ll;
int a[N];
struct node{
	ll x,d;
	friend node operator+(const node u,const node v){
		return (node){max(u.x,v.x-u.d),u.d+v.d};
	}
}s1[N],s2[N];
int n1,n2;
bool check(int w){
	ll sum=(ll)n*w-(a[n]-a[1]);
	if(sum<0) return 0;
	n1=0;
	for(int i=k;i>1;--i){
		int d=a[i]-a[i-1];
		node cur({d,w-d});
		while(cur.d>=0&&n1&&s1[n1].d<0) cur=s1[n1--]+cur;
		s1[++n1]=cur;
	}
	n2=0;
	for(int i=k;i<n;++i){
		int d=a[i+1]-a[i];
		node cur({d,w-d});
		while(cur.d>=0&&n2&&s2[n2].d<0) cur=s2[n2--]+cur;
		s2[++n2]=cur;
	}
	bool fl=1;
	while(fl){
		fl=0;
		while(n1&&s1[n1].d<0&&sum-s1[n1].d>=s1[n1].x) sum-=s1[n1--].d,fl=1;
		while(n2&&s2[n2].d<0&&sum-s2[n2].d>=s2[n2].x) sum-=s2[n2--].d,fl=1;
	}
	int p1=1,p2=1;
	fl=1;sum=w;
	while(fl){
		fl=0;
		while(p1<=n1&&s1[p1].d>=0&&sum>=s1[p1].x) sum+=s1[p1++].d,fl=1;
		while(p2<=n2&&s2[p2].d>=0&&sum>=s2[p2].x) sum+=s2[p2++].d,fl=1;
	}
	return p1>n1&&p2>n2;
}
int main(){
	n=read();k=read();t=read();
	for(int i=1;i<=n;++i) a[i]=read();
	int l=0,r=ceil(0.5e9/t);
	while(l<r){
		int mid=(l+r)>>1;
		if(check(2*mid*t)) r=mid;
		else l=mid+1;
	}
	printf("%d\n",r);
	return 0;
}

[ICPC2021 Macao R] the Matching System

什么鬼畜打表题。看看题目给的啥限制?完了这看起来完全规划不了啊!

进行一个表的打,发现取到最大值的它就是很有规律:

**********0*
011111111111
000000******
000000000000

原理都很好懂,比如说最大匹配的串一定那堆通配符匹配长度都是 0,所以耗费能量极多。

下面这个能量好算,在平方级别;上面这个能量通过一大堆插板法反复计算+竖行和公式得到 \({2n-1\choose n+1}+{2n-3\choose n-2}\),做完了。

#include <cstdio>
using namespace std;
const int P=1000000007;
const int N=10003;
typedef long long ll;
int qp(int a,int b=P-2){
	int res=1;
	while(b){
		if(b&1) res=(ll)res*a%P;
		a=(ll)a*a%P;b>>=1;
	}
	return res;
}
int fac[N],fiv[N],n;
int main(){
	scanf("%d",&n);
	if(n==1) puts("0\n0\n1");
	else if(n==2) puts("*0\n00\n3");
	else{
		fac[0]=1;
		for(int i=1;i<=2*n;++i) fac[i]=(ll)fac[i-1]*i%P;
		fiv[2*n]=qp(fac[2*n]);
		for(int i=2*n;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
		int cur=((ll)fac[2*n-1]*fiv[n+1]+(ll)fac[2*n-3]*fiv[n-1])%P*fiv[n-2]%P;
		for(int i=1;i<=n;++i) if(i==n-1) putchar('0');else putchar('*');
		putchar('\n');
		for(int i=1;i<=n;++i) if(i==1) putchar('0');else putchar('1');
		putchar('\n');
		printf("%d\n",cur);
	}
	int t=((n+1)>>1);
	int res=(t+3)*t;
	if(n&1) res-=t+1;
	for(int i=1;i<=n;++i) if(i<=t) putchar('*');else putchar('0');
	putchar('\n');
	for(int i=1;i<=n;++i) putchar('0');
	putchar('\n');
	printf("%d\n",res);
	return 0;
}

标签:return,速通,int,Solution,read,while,&&,buc,杂题
From: https://www.cnblogs.com/yyyyxh/p/18351460/problemset1

相关文章

  • Solution - Atcoder ABC155F Perils in Parallel
    首先可以按\(a_i\)排序,对于区间\([l_i,r_i]\)可以通过二分确定实际影响到的\(b_i\)的区间。考虑到区间\(i\in[l,r]\)的\(b_i\)都取反影响到的元素过多,考虑去减少影响到的元素。于是可以想到令\(c_i=b_i\oplusb_{i-1}\),那么对于区间\([l,r]\)操作实际影响......
  • 文化课速通目录
    桑百天够吗(24.8.11~25.6.6)化学\(\text{step1}\)高中化学基础:必修\(1.1/1.2\)\(\text{step2}\)元素化学基础:必修\(1.5\)微观结构和物质的多样性选修\(2.1\)\(\text{step3}\)具体元素:必修\(1.3\)海水中的重要元素必修\(1.4\)硫与环境保护必修\(2.7......
  • 网络流部分题目及杂题选做
    网络流网络流初探A.【例题1】求最大流P3376模板。B.卖猪问题SP4063&&P4638Solution[trick]:网络流有时间顺序要求的考虑分层图,优化建图的思路很妙。D.危桥通行P3163Solution正常按照题意建边,危桥建边权为\(1\)的双向边,普通的桥建边权为\(inf\)的双向边,源点向......
  • 《开源大模型食用指南》发布,7个小时,一杯奶茶速通大模型!
    前言《开源大模型食用指南》是一个围绕开源大模型、针对国内初学者、基于AutoDL平台的中国宝宝专属大模型教程,针对各类开源大模型提供包括环境配置、本地部署、高效微调等技能在内的全流程指导,简化开源大模型的部署、使用和应用流程,**让更多的普通学生、研究者更好地使......
  • 杂题 Solution 速通 #1
    [ICPC2021NanjingR]AncientMagicCircleinTeyvat设\(f_x\)表示钦定至少有\(x\)条边的四元子图个数,由容斥我们有一条边都没有的子图个数是\(f_0-f_1+f_2-f_3+f_4-f_5+f_6\),而所有边都有的个数就是\(f_6\)。作差之后只需要求\(f_0,f_1,f_2,f_3,f_4,f_5\)。子图计数只......
  • 什么是大模型?一文速通了解什么才是真正的大模型
    在这个充满变革的时代里,人工智能领域的几个关键词——ChatGPT、OpenAI、大模型、提示词工程以及“幻觉”频繁出现在我们的视野中,它们如同一股不可忽视的力量,冲击并重塑着我们的认知。这些术语不仅代表了技术的前沿动态,也引发了社会各界的广泛讨论与关注。什么是大模型当......
  • 杂题瞎写
    来点乱搞题。灯塔首先,这是一个DP。观察到\(\sqrt{|i-j|}\)的取值范围是\(O(\sqrtn)\)的。所以枚举每个取值,转移就是区间\(\max\)。随便写写\(O(n\sqrtn)\)。当然,这复杂度太高了,看着不舒服。我们考虑删除一些无用的状态。考虑若目前的最大值为\(val\),由于\(......
  • 【题解】Solution Set - NOIP2024集训Day2 线段树
    【题解】SolutionSet-NOIP2024集训Day2线段树https://www.becoder.com.cn/contest/5431「CF1149C」TreeGenerator™结论:对于括号序列的一个子段,删去所有的匹配括号之后,剩下的不匹配的括号,按顺序构成树上的一条路径。Why?从括号序列的构造出发。每次(相当于开始遍历......
  • 「杂题乱刷2」CF1486C1 & CF1486C2
    题目链接CF1486C1CF1486C2解题思路提供一个比较显然的思路。我们发现我们可以先求出整体的最小值,然后设整体最小值所在的位置为\(id\),则我们可以通过\(1\)次询问\([1,id]\)来求出最大值的位置是在\([1,id)\)还是在\((id,n]\)。然后我们就有了整体最大值在一个前缀或......
  • 一文速通Redis常见问题,带你深入了解Redis数据结构、分布式锁、持久化策略等经典问题。
    本文参考资料:黑马Redis讲义本文参考资料:JavaGuide,guide哥的八股内容个人思考的Redis实践,面试问题的总结,反思目录Redis五大数据结构String1.String数据结构(SDS)2.String应用场景3.Hash与String存储对象的区别SetListHashSortedSetRedis三种特殊数据结构BitMap(位图)......