天天看點
傳回

2018.12.08【NOIP提高組】模拟B組JZOJ 5123 diyitiJZOJ 100042 保留道路JZOJ 3518 進化序列JZOJ 5223 B後續

遲到的解題報告

  • JZOJ 5123 diyiti
    • 分析
    • 代碼
  • JZOJ 100042 保留道路
    • 題目大意
    • 分析
    • 代碼
  • JZOJ 3518 進化序列
    • 題目大意
    • 分析
    • 代碼
  • JZOJ 5223 B
    • 題目
    • 分析
    • 代碼
  • 後續

JZOJ 5123 diyiti

bzoj 4927 連結

分析

6根木棍，隻能是3+1+1+1或者是2+2+1+1，是以分類讨論。（以下其它情況都排除了之前的情況，也就是容斥，為了行文友善，在此不多寫）

設邊長為 x x x（ i × 2 i\times2 i×2代表 i 和 i i和i i和i）

2+2+1+1的組合方式
x , x , x 2 × 2 , x 2 × 2 ( x 是 偶 數 ) x,x,\frac{x}{2}\times 2,\frac{x}{2}\times 2(x是偶數) x,x,2x​×2,2x​×2(x是偶數)
以下保證 t × 2 &lt; x t\times2&lt;x t×2<x
x , x , x − t 和 t , x − t 和 t x,x,x-t和t,x-t和t x,x,x−t和t,x−t和t
x , x , x − t 1 和 t 1 , x − t 2 和 t 2 （ t 1 ≠ t 2 ） x,x,x-t_1和t_1,x-t_2和t_2（t_1\neq t_2） x,x,x−t1​和t1​,x−t2​和t2​（t1​̸​=t2​）
x , x , x − t 和 t , x 2 × 2 ( x 是 偶 數 ) x,x,x-t和t,\frac{x}{2}\times 2(x是偶數) x,x,x−t和t,2x​×2(x是偶數)
3+1+1+1的組合方式
x , x , x , x 3 × 3 ( x 能 被 3 整 除 ) x,x,x,\frac{x}{3}\times3(x能被3整除) x,x,x,3x​×3(x能被3整除)
x , x , x , x − t 1 × 2 和 t 1 和 t 1 x,x,x,x-t_1\times 2和t_1和t_1 x,x,x,x−t1​×2和t1​和t1​
x , x , x , x − t 1 − t 2 和 t 1 和 t 2 ( x − t 1 − t 2 ≠ t 1 ≠ t 2 ) x,x,x,x-t_1-t_2和t_1和t_2(x-t_1-t_2\neq t_1\neq t_2) x,x,x,x−t1​−t2​和t1​和t2​(x−t1​−t2​̸​=t1​̸​=t2​)

這樣講好像很簡單，實際上實踐會比較容易在細節上出問題，我的細節出錯點詳見代碼

代碼 

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#define rr register
using namespace std;
const int N=10000001;
typedef long long ll; ll ans;
vector<int>t; int cnt[N+10],dcnt[N+10];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
signed main(){
	freopen("yist.in","r",stdin);
	freopen("yist.out","w",stdout);
	for (rr int n=iut(),x;n;--n)
	    if (++cnt[x=iut()]==1) t.push_back(x);
	sort(t.begin(),t.end());
	for (rr int i=0;i<t.size()-1;++i)
	    for (rr int j=i+1;j<t.size();++j)
	        if (t[i]+t[j]<N)
			    dcnt[t[i]+t[j]]+=cnt[t[i]]*cnt[t[j]];//原代碼隻是=
			else break;
	for (rr int i=1;i<t.size();++i){
		if (cnt[t[i]]==1) continue;
		if (cnt[t[i]]>1){
			rr ll x=1ll*cnt[t[i]]*(cnt[t[i]]-1)>>1,sum=0;
			if (!(t[i]&1)&&cnt[t[i]>>1]>3)
			    ans+=x*cnt[t[i]>>1]*(cnt[t[i]>>1]-1)*(cnt[t[i]>>1]-2)*(cnt[t[i]>>1]-3)/3>>3;//原代碼判成奇數
			for (rr int j=0;j<i;++j)
			if ((t[j]<<1)<t[i]){
				if (cnt[t[j]]>1&&cnt[t[i]-t[j]]>1)
				    sum+=1ll*cnt[t[j]]*(cnt[t[j]]-1)*cnt[t[i]-t[j]]*(cnt[t[i]-t[j]]-1)>>2;
			}else break;
			ans+=x*sum; sum=0;
			for (rr int j=0;j<i;++j)
			if ((t[j]<<1)<t[i]){
			    if (cnt[t[i]-t[j]])
			        ans+=x*sum*cnt[t[j]]*cnt[t[i]-t[j]],sum+=cnt[t[j]]*cnt[t[i]-t[j]];
			}else break;
			if (!(t[i]&1)) ans+=x*sum*cnt[t[i]>>1]*(cnt[t[i]>>1]-1)>>1;//原代碼未判斷
		}
		if (cnt[t[i]]==2) continue; 
		if (cnt[t[i]]>2){
			rr ll x=1ll*cnt[t[i]]*(cnt[t[i]]-1)*(cnt[t[i]]-2)/3>>1,sum=0;
			if (t[i]%3==0&&cnt[t[i]/3]>2)
			    ans+=x*cnt[t[i]/3]*(cnt[t[i]/3]-1)*(cnt[t[i]/3]-2)/3>>1;
			for (rr int j=0;j<i;++j){
				sum+=1ll*cnt[t[j]]*dcnt[t[i]-t[j]];
				if ((t[j]<<1)<t[i]&&t[j]*3!=t[i])
				    sum-=1ll*cnt[t[j]]*cnt[t[j]]*cnt[t[i]-(t[j]<<1)];
			}
			ans+=x*sum/3;
			for (rr int j=0;j<i;++j)
			if ((t[j]<<1)<t[i]){
				if (t[j]*3!=t[i]) ans+=x*cnt[t[j]]*(cnt[t[j]]-1)*cnt[t[i]-(t[j]<<1)]>>1;
			}else break;
		}
	}
	return !printf("%lld",ans);
}

JZOJ 100042 保留道路

題目大意

n n n個點 m m m條邊的無向圖中，每條邊都有兩個屬性g和s，如果建某條邊，那麼邊權是 m a x { w G × 所 有 剩 下 道 路 的 屬 性 g } + m a x { w S × 所 有 剩 下 道 路 的 屬 性 s } max\{wG\times所有剩下道路的屬性g\}+max\{wS\times所有剩下道路的屬性s\} max{wG×所有剩下道路的屬性g}+max{wS×所有剩下道路的屬性s}，其中 w G wG wG和 w S wS wS是給定的值。求該圖的最小生成樹

分析

枚舉每一條邊 i i i，固定最大的邊為 g i g_i gi​，對于 s s s跑最小生成樹，不過有一些可以剪枝的地方是之前沒有用上的邊用上不會更優，是以說大大優化了時間複雜度。

代碼 

#include <cstdio>
#include <algorithm>
#include <cstring>
#define rr register
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;
struct node{
	int x,y,g,s,next;
	bool operator <(const node &t)const{
	    if (g!=t.g) return g<t.g;
	        else return s<t.s;
	}
}e[50001]; long long ws,wg,ans=1ll<<62;
int n,m,f[401],t,kr[50001],ls[401];//kr表示候選的編号（升序）
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline signed getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
inline void kruskal(int mg){
	rr bool v[t+1];	rr int cnt=1;
	memset(v,0,sizeof(v));
	for (rr int i=1;i<=n;++i) f[i]=i;
	for (rr int i=1;i<=t;++i){
		rr int tt=kr[i],fa=getf(e[tt].x),fb=getf(e[tt].y);
		if (fa!=fb)
			++cnt,v[i]=1,
			f[min(fa,fb)]=max(fa,fb);
		if (cnt==n){
			rr int tot=0;
			for (rr int j=1;j<=t;++j) if (v[j]) kr[++tot]=kr[j];//沒有最小生成樹那麼肯定會被覆寫掉
			fill(kr+1+tot,kr+1+t,0);
			t=tot; ans=min(ans,wg*mg+ws*e[tt].s);//既然升序答案就是最後一條邊
			break;
		}
	}
}
signed main(){
	n=iut(); m=iut(); wg=iut(); ws=iut();
	for (rr int i=1;i<=m;++i){
		rr int x=iut(),y=iut();
		if (x==y) iut(),iut(),--i,--m;//處理自環
		else e[i]=(node){x,y,iut(),iut(),ls[x]},ls[x]=i;
	}
	sort(e+1,e+1+m);
	for (rr int i=1;i<=m;++i){
		if (wg*e[i].g+ws*e[i].s>=ans) continue;//肯定不會更優
		rr int l=1,r=++t;//二分插入排序
		while (l<r){
			rr int mid=(l+r)>>1;
			if (e[kr[mid]].s>e[i].s) r=mid;
			    else l=mid+1;
		}
		if (l==t) kr[t]=i;
		else{
			for (rr int i=t;i>l;--i) kr[i]=kr[i-1];
			kr[l]=i;
	    }
		kruskal(e[i].g);
	}
	printf("%lld",ans);
	return 0;
}

JZOJ 3518 進化序列

題目大意

有多少區間的按位或值小于 m m m

分析

掃描每一個結尾，然後找到最大的開頭

代碼 

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
int n,m,a[100001],head=1,cnt[33]; long long ans;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
	return ans;
}
signed main(){
	freopen("evolve.in","r",stdin);
	freopen("evolve.out","w",stdout);
	n=iut(); m=iut();
	for (rr int i=1;i<=n;++i) a[i]=iut();
	for (rr int i=1;i<=n;++i){
		rr int sum=0;
		for (rr int j=0;j<32;++j) sum|=(cnt[j]>0)<<j;
		while ((sum|a[i])>=m&&head<=i){
			for (rr int j=0;j<32;++j)
			if (a[head]&(1<<j))
				if (!(--cnt[j])) sum^=1<<j;
			++head;
		}
		if (i>head) ans+=i-head;
		for (rr int j=0;j<32;++j)
		if (a[i]&(1<<j))
		    if (!cnt[j]++) sum|=1<<j;
	}
	printf("%lld",ans);
	return 0;
}

JZOJ 5223 B

題目

給定一個3*3的網格圖，一開始每個格子上都站着一個機器人。每一步機器人可以走到相鄰格子或留在原地，同一個格子上可以有多個機器人。問走n步後，有多少種走法，滿足每個格子上都有機器人。答案對10^9+7取模。

分析

然而這是一道矩陣乘法的題目，機器人隻能跑到相鄰的格子，于是跑完矩陣乘法後枚舉全排列，對于每種全排列用乘法原理求出答案

代碼 

#include <cstdio>
#include <algorithm>
#include <cstring>
#define rr register
using namespace std;
int b[9]; typedef long long ll;
const ll mod=1000000007ll;
ll n,a[9][9],ans;
inline void mulself(ll f[9][9]){
	ll c[9][9];
	memset(c,0,sizeof(c));
	for (rr int i=0;i<9;++i)
	for (rr int j=0;j<9;++j)
	for (rr int k=0;k<9;++k)
	(c[i][j]+=f[i][k]*f[k][j]%mod)%=mod;
	memcpy(f,c,sizeof(c));
}
inline void mul(ll f[9][9],ll x){
	ll c[9]={0,0,0,0,0,0,0,0,0};
	for (rr int i=0;i<9;++i)
	for (rr int j=0;j<9;++j)
	(c[j]+=a[x][i]*f[i][j]%mod)%=mod;
	memcpy(a[x],c,sizeof(c));
}
inline void init(ll x,ll y){
	rr ll f[9][9]={//就是連相鄰的邊
	    {1,1,0,1,0,0,0,0,0},
		{1,1,1,0,1,0,0,0,0},
	    {0,1,1,0,0,1,0,0,0},
		{1,0,0,1,1,0,1,0,0},
		{0,1,0,1,1,1,0,1,0},
		{0,0,1,0,1,1,0,0,1},
		{0,0,0,1,0,0,1,1,0},
		{0,0,0,0,1,0,1,1,1},
		{0,0,0,0,0,1,0,1,1}
	};
	for (;y;mulself(f),y>>=1) if (y&1) mul(f,x);
}
signed main(){
	scanf("%lld",&n);
	for (rr int i=0;i<9;++i)
		a[i][i]=1,init(i,n),b[i]=i;
	do{
		rr ll mull=1;
		for (rr int i=0;i<9;++i) (mull*=a[i][b[i]])%=mod;//乘法原理
		(ans+=mull)%=mod;//加法原理
	}while (next_permutation(b,b+9));//枚舉全排列
	printf("%lld",ans);
	return 0;
}

後續

sto初二除了我以外的所有人

模拟賽 二分、三分 最小生成樹 并查集 容斥定理 矩陣乘法 保留道路 第一題 bzoj 4927 JZOJ 5223 B JZOJ 3518 進化序列
上一篇: 進階資料結構之線段樹與掃描線算法
下一篇: 2021.08.24【NOIP提高A、B組】模拟 YL杯超級籃球賽 c o d e code code

繼續閱讀