• 2022杭电多校联赛第七场 题解

    比赛传送门
    作者： fn

    目录

    签到题

    1004题 Black Magic / 黑魔法

    题目大意
    给出 n n n 个方块，每个方块的左/右都可能是黑或白。将这些方块排成一列，如果两个相邻方块相连接的面都是黑色，那么这两个方块会连在一起。
    求连通块的最大/最小数量。

    考察内容
    贪心，模拟

    分析
    计算连通块的最大数量时，要尽可能少粘合；计算最小数量时，要尽可能多粘合。
    把每个方块一个个放进去，放的时候贪心一下即可。

    #include
#define ll long long
#define int long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=4e5+10;
ll a[N]; // 记录第i格右边是否是黑色 
ll e,l,r,b;
 
signed main(){ // 贪心 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){ // 
		cin>>e>>l>>r>>b;
		ll sum=e+l+r+b;
		
		// 计算max1，尽可能少粘合 
		ll max1=sum; // 先取得总数 
		ll e2=e,l2=l,r2=r,b2=b;
		for(int i=0;i<=sum;i++){
			a[i]=0; // 初始化 
		}

		for(int i=1;i<=sum;i++){
			if(a[i-1]==1){ // 前一个的右边是黑的
				if(e2>0){ // 两边白色 
					e2--;
				}
				else if(r2>0){
					a[i]=1; // 右边黑 
					r2--;
				}
				else{ // 必须黏在一起了 
					if(l2>0){
						max1--; // 少1块 
						l2--;
					}
					else if(b2>0){ // 两边黑
						max1--; // 少1块 
						a[i]=1; // 右边黑 
						b2--; 
					}
				}
			}
			else{ // 前一个的右边是白的
				if(l2>0){ // 左边黑 
					l2--;
				}
				else if(b2>0){ // 两边黑
					a[i]=1; 
					b2--; 
				}
				else if(e2>0){
					e2--;
				}
				else if(r2>0){
					a[i]=1; // 右边黑 
					r2--;
				} 
			} 
		}
		
		
		// 计算min1,尽可能多粘合 
		ll min1=sum;
		e2=e,l2=l,r2=r,b2=b;
		for(int i=0;i<=sum;i++){
			a[i]=0; // 初始化 
		} 
		for(int i=1;i<=sum;i++){ // 
			if(a[i-1]==1){ // 前一个的右边是黑的
				if(b2>0){ // 两边黑
					min1--; 
					a[i]=1;
					b2--; 
				}
				else if(l2>0){
					min1--;
					l2--;
				}	
				else if(r2>0){
					a[i]=1; // 右边黑 
					r2--;
				} 
				else if(e2>0){
					e2--;
				}
			}
			else{ // 前一个的右边是白的
				if(r2>0){
					a[i]=1; // 右边黑 
					r2--;
				} 
				else if(e2>0){
					e2--;
				}
				else if(b2>0){ // 两边黑
					a[i]=1;
					b2--; 
				}
				else if(l2>0){
					l2--;
				}
			} 
		}
		cout<<min1<<' '<<max1<<endl;
	}
	return 0;
}
/*
1
0 2 2 0

1
100000 100000 100000 100000 

*/ 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118

    1008题 Triangle Game / 三角形游戏

    题目大意
    一个非退化三角形，三边边长分别为 。二人做游戏，每轮令三角形的一边长度减去一正整数，使这个三角形退化的一方负。
    双方均采用最优策略，问先手必胜还是后手必胜。

    考察内容
    NIM博弈，结论

    分析
    -1NIM，和昨天的K题类似。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
int a[4];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>a[1]>>a[2]>>a[3];
		
		ll sum=(a[1]-1)^(a[2]-1)^(a[3]-1);
		
		if(sum!=0) cout<<"Win"<<endl;
		else cout<<"Lose"<<endl; 
	}
	return 0;
}
/*
100 100 1

*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    基本题

    1003题 Counting Stickmen / 数火柴人

    题目大意
    给一棵无根树，数树上 “火柴人” 的数量。如图是一个火柴人。
    火柴人

    考察内容
    dfs，组合数，模拟

    分析
    跑一遍dfs，度 ≥ 4 ≥4 ≥4 的时候把这个结点当作身体，统计一下答案。
    详见代码和注释。细节还是比较多的。

    #pragma GCC optimize(3) // O3 
#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
#define int long long
using namespace std;
ll read(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
const int N=5e5+5;
const ll mod=998244353;
ll n,ans; 
vector<ll> g[N]; // 记录一棵树 

ll num[N]; // 单纯的手（相邻，度==2的点的数量） 
vector<ll> v[N]; // 下身（相邻，度>=3的点的度）
bool vis[N];
ll C2[N]; // 返回C(x,2)%mod

void dfs(int x){
	int len=g[x].size(); // x的度 
	if(len>=4){ // 度>=4，x可能可以作为身体 
		num[x]=0; // 记录单纯的手的数量  
		ll sumv=0; // v的和 
		
		for(auto a1:g[x]){ // 枚举相邻的边 
			int len0=g[a1].size();
			if(len0==2){
				num[x]++; // 单纯的手
			}
			else if(len0>=3){ // 可以作为下身 
				v[x].push_back(len0-1); // 记录下身的度-1(腿的个数) 
				sumv+=len0-1; // 记录 
			}
		}
		
		ll sum=C2[num[x]]; // 选择手的种类数。先在单纯的手里面选2个 
		
		sum+=num[x]*sumv%mod; // 一个单纯的手,一个下身当手 
		sum%=mod;
		
		ll t2=0;
		int lenvx=v[x].size();
		for(int i=0;i<lenvx;i++){ // 遍历每一个下身的度 
			t2+=v[x][i]*(sumv-v[x][i]+mod)%mod; // 一个下身当第一只手+其他下身当第二只手 
			t2%=mod;
		}
		t2*=499122177; t2%=mod; // 除以2去掉重复情况 
		
		sum+=t2; 
		
		// 统计答案 
		for(int i=0;i<lenvx;i++){ // 遍历选择每一个下身的情况 
			ll t1 = (sumv-v[x][i] + num[x] +mod)%mod *v[x][i]%mod; // 选这个下身时少掉的情况 
			
			ans += (sum-t1+mod)%mod *C2[v[x][i]]%mod *(len-3)%mod; // 手种类数*脚种类数*头种类数 
			ans %= mod;
		}
	}
	
	for(auto a1:g[x]){
		if(vis[a1]==0){ // 没去过 
			vis[a1]=1; // 标记已经去过了 
			dfs(a1); // 往下遍历 
		}
	}
}

signed main(){ // AC 
	C2[0]=0;
	ll h=5e5+1;
	for(ll i=1;i<=h;i++){
		C2[i]=i*(i-1)%mod*499122177%mod; // 预处理C2 
	}
	
	int t; read(t);
	while(t--){
		read(n);
		for(int i=0;i<=n;i++){ // 初始化 
			g[i].clear();
			v[i].clear();
			num[i]=0;
			vis[i]=0; 
		}
		
		ll u,v; 
		for(int i=1;i<=n-1;i++){
			read(u); read(v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		
		ans=0;
		
		vis[1]=1; // 标记起点（勿忘） 
		dfs(1); // 统计答案 
		cout<<(ans+mod)%mod<<endl;
	}
	return 0;
}
/*
1
10
1 3
2 3
3 4
3 5
3 6
5 7
5 8
6 9
6 10

正确输出： 
0

1
11
1 2
2 3
3 4
2 5
5 6
2 7
7 8
7 9
2 10
10 11

6

*/ 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137

    进阶题

    1006题 Sumire / 苏米尔

    题目大意
    计算 ∑ i = l r f k ( i , B , d ) \sum_{i=l}^r f^k(i,B,d) ∑i=lr​fk(i,B,d) 。

    其中 f ( i , B , d ) f(i,B,d) f(i,B,d) 表示数位 d d d 在 B B B 进制的 x x x 出现的次数。在这个问题中，令 0 0 = 0 0^0=0 00=0 。

    ( 0 ≤ k ≤ 1 0 9 , 2 ≤ B ≤ 1 0 9 , 0 ≤ d < B , 1 ≤ l ≤ r ≤ 1 0 18 ) (0\le k\le 10^9 , 2\le B\le 10^9 , 0\le d< B , 1\le l\le r\le 10^{18}) (0≤k≤109,2≤B≤109,0≤d<B,1≤l≤r≤1018)

    考察内容
    数位dp，记忆化搜索

    分析
    1006题解

    #include
using namespace std;
#define fi first
#define se second
#define MS0(x) memset((x),0,sizeof((x)))
typedef long long ll;
typedef unsigned long long ull;

template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(ll &x) { scanf("%lld", &x); }
void _R(ull &x) { scanf("%llu", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }

const int MOD=1e9+7;
const int MAXN=5e5+10,MAXM=1e7+10;

template <int _P>
struct Modint
{
    static constexpr int P=_P;
private :
    int v;
public :
    Modint() : v(0){}
    Modint(ll _v){v=_v%P;if(v<0)v+=P;}
    explicit operator int() const {return v;}
    explicit operator long long() const {return v;}
    explicit operator bool() const {return v>0;}
    bool operator == (const Modint &o) const {return v==o.v;}
    bool operator != (const Modint &o) const {return v!=o.v;}
    Modint operator - () const {return Modint(v?P-v:0);}
    Modint operator + () const {return *this;}
    Modint & operator ++ (){v++;if(v==P)v=0;return *this;}
    Modint & operator -- (){if(v==0)v=P;v--;return *this;}
    Modint operator ++ (int){Modint r=*this;++*this;return r;}
    Modint operator -- (int){Modint r=*this;--*this;return r;}
    Modint & operator += (const Modint &o){v+=o.v;if(v>=P)v-=P;return *this;}
    Modint operator + (const Modint & o)const{return Modint(*this)+=o;}
    Modint & operator -= (const Modint & o){v-=o.v;if(v<0)v+=P;return *this;}
    Modint operator - (const Modint &o)const {return Modint(*this)-=o;}
    Modint & operator *=(const Modint & o){v=(int)(((ll)v)*o.v%P);return *this;}
    Modint operator * (const Modint & o)const {return Modint(*this)*=o;}
    Modint & operator /= (const Modint & o){return (*this)*=o.Inv();}
    Modint operator / (const Modint & o)const{return Modint(*this)/=o;}
    friend Modint operator + (const Modint &x,const ll &o) {return x+(Modint)o;}
    friend Modint operator + (const ll &o,const Modint &x) {return x+(Modint)o;}
    friend Modint operator - (const Modint &x,const ll &o) {return x-(Modint)o;}
    friend Modint operator - (const ll &o,const Modint &x) {return (Modint)o-x;}
    friend Modint operator * (const Modint &x,const ll &o) {return x*(Modint)o;}
    friend Modint operator * (const ll &o,const Modint &x) {return x*(Modint)o;}
    friend Modint operator / (const Modint &x,const ll &o) {Modint c=o;return x*c.Inv();}
    friend Modint operator / (const ll &o,const Modint &x) {Modint c=o;return c*x.Inv();}
    Modint operator ^ (ll o)const{Modint r=1,t=v;while(o){if(o&1)r*=t;t*=t;o>>=1;}return r;}
    Modint operator ~ (){return (*this)^(P-2);}
    Modint Inv() const{return (*this)^(P-2);}
};

using mi=Modint<MOD>;


template<int P>
void _W(Modint<P> x){printf("%d",(int)x);}

template<int P>
void _R(Modint<P> &x){ll t;scanf("%lld",&t);x=t;}


mi dp[75][75][2][2],vis[75][75][2][2];;
ll t;
int s[75],k,b,d,n,m,c;

mi dfs(int dep,int tot,int lim,bool zero){
    if(dep==m+1&&tot==0)return 1;
    if(dep==m+1)return 0;
    if(tot<0)return 0;
    if(vis[dep][tot][lim][zero])return dp[dep][tot][lim][zero];
    vis[dep][tot][lim][zero]=1;
    int up=lim?s[dep]:b-1;
    int ct=0,i=0;
    int c=(i==d);
    if(zero&&(d==0))c=0;
    dp[dep][tot][lim][zero]+=dfs(dep+1,tot-c,lim&&(s[dep]==i),zero);
    ct++;
    if(i!=d&&d<=up){
        ct++;
        i=d;
        int c=(i==d);
        if(zero&&(d==0))c=0;
        dp[dep][tot][lim][zero]+=dfs(dep+1,tot-c,lim&&(s[dep]==i),0);
    }
    if(i!=up){
        ct++;
        i=up;
        dp[dep][tot][lim][zero]+=dfs(dep+1,tot,lim&&(s[dep]==i),zero&&(i==0));
    }
    dp[dep][tot][lim][zero]+=dfs(dep+1,tot,0,0)*max(0,up-ct+1);
    return dp[dep][tot][lim][zero];
}

mi calc(bool f){
    MS0(dp); MS0(vis);
    R(t);
    m=0;
    t-=f;
    while(t){
        s[++m]=t%b;
        t/=b;
    }
    reverse(s+1,s+m+1);
    mi ans=0;
    for(int i=1;i<=m;i++){
        mi t=i;
        ans+=dfs(1,i,1,1)*(t^k);
    }
    return ans;
}

void solve(){
    R(k,b,d);
    mi ans=calc(1);
    ans=calc(0)-ans;
    W(ans);
}

int main(){
    srand(time(0));
    int T=1;
    scanf("%d",&T);
    for(int kase=1;kase<=T;kase++){
        solve();
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140

    1002题 Independent Feedback Vertex Set / 独立反馈顶点集

    题目大意

    森林：一个没有环的无向图。
    独立集：图中的一组顶点，其中任意两个顶点之间没有边相连。

    给定一个无向图 G = （ V ， E ） G=（V，E） G=（V，E） ，其中V是顶点集，E是边集。V中的每个顶点都有一个点权。现在她想把V分成两个互补的子集 V I V_ I VI​ 和 V F V_F VF​ 。
    使得 V I V_ I VI​ 并且生成子图 G [ V F ] G[V_F] G[VF​] 是一片森林。生成子图 G [ V F ] G[V_F] G[VF​] 是顶点集为 V F V_F VF​ 的图。
    其边集由E中具有 V F V_ F VF​ 中两个端点的所有边组成。
    ​
    此外，她希望 V I V_I VI​ 中顶点的权重之和最大。
    ​
    解决这个问题的一个特例。通过以下步骤构建特殊图。最初，图由三个顶点 1 , 2 , 3 1,2,3 1,2,3 和三条无向边 （ 1 , 2 ）、（ 2 , 3 ）、（ 3 , 1 ） （1,2）、（2,3）、（3,1） （1,2）、（2,3）、（3,1） 组成。当我们将顶点 x x x 添加到图中时，我们选择已经存在于图中的边 （ y , z ） （y,z） （y,z） ，并连接 （ x , y ） （x,y） （x,y） 和 （ x , z ） （x,z） （x,z） 。继续这样做，直到图中有 n n n 个顶点。

    考察内容
    图论，枚举

    分析
    答案必须包含每个三元环中的恰好一个点，因为一个点都不选则会破坏森林约束，选至少两个则会破坏独立集约束。
    同时对于一对有至少两个公共点的三元环，确定了答案包含其中一个的某个点之后另一个也随之确定了。
    因此答案只可能有三种，分别对应图中唯一的三染色方案（去重后）中的每一种颜色的点。
    枚举第一个选的是1或者2还是3，最终答案取顶点的权重之和最大的那个。

    #include 
using namespace std;

int main(void) {
    typedef pair<int, int> pii;
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        vector<int> w(n);
        vector<int> c(n, 0);
        c[0] = 0;
        c[1] = 1;
        c[2] = 2;
        for (int i = 0; i < n; ++i)
            scanf("%d", &w[i]);

        for (int i = 3; i < n; ++i) {
            int j, k;
            scanf("%d %d", &j, &k);
            j--; k--;
            c[i] = (3 - c[j] - c[k]) % 3;
        }

        long long ans[3] = { 0, 0, 0 };
        for (int i = 0; i < n; ++i)
            ans[c[i]] += w[i];

        cout << max({ ans[0], ans[1], ans[2] }) << endl;
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
  • 相关阅读:
    nginx、apache流量日志分析
    UE4 源码阅读：从引擎启动到Receive Begin Play
    拉链法和开放寻址法 c++实现
    20220726汇承科技的蓝牙模块HC-05的AT命令测试
    Elasticsearch：什么是向量和向量存储数据库，我们为什么关心？
    Java | 选择排序算法实现
    Git基本操作（2）
    CCL2022自然语言处理国际前沿动态综述——开放域对话生成前沿综述
    [硬件基础]-快速了解I2C串行通信协议
    【算法面试题汇总】LeetBook列表的算法面试题汇总---动态规划题目及答案
  • 原文地址：https://blog.csdn.net/weixin_51937688/article/details/126251936