比赛传送门
作者： fn

签到题

1004题 Black Magic / 黑魔法

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

考察内容
贪心，模拟

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

#include<bits/stdc++.h>
#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 */ 

1008题 Triangle Game / 三角形游戏

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

考察内容
NIM博弈，结论

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

#include<bits/stdc++.h>
#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 */

基本题

1003题 Counting Stickmen / 数火柴人

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

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

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

#pragma GCC optimize(3) // O3 
#include<bits/stdc++.h>
#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 */ 

进阶题

1006题 Sumire / 苏米尔

题目大意
计算 ${\sum }_{i=l}^r{f}^k(i,B,d)$ 。

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

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

分析

#include<bits/stdc++.h>
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;
}

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

题目大意

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

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

考察内容
图论，枚举

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

#include <bits/stdc++.h>
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;
}