目录

• 1008 Triangle Game
• 1004 Black Magic
• 1003 Counting Stickmen

1008 Triangle Game

题目

​ 一个非退化三角形，三边边长分别为a,b,c。现 Kate 和 Emilico 二人做游戏，每轮需要令三角形的一边长度减去一正整数，使这个三角形退化为线段的一方败。

分析

​ 博弈论题多与异或有很大关系，此题当$\mathrm{（}a-1)\oplus (b-1)\oplus (c-1)\mathrm{\ne }0（a-1)\backslash oplus\; (b-1)\backslash oplus(c-1)\backslash neq0$时Kate必胜，否则必败。

代码

#include<bits/stdc++.h>
using namespace std;
template <typename tn>void read(tn &n){
    tn f=1,t=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) t=t*10+ch-'0',ch=getchar();
    n=f*t;
}
inline void out(int x){
	if(x>9)out(x/10);
	putchar(x%10+'0');
}

int T;
long long a,b,c,d;
int main(){
	read(T);
	while(T--){
		read(a),read(b),read(c);
		a--,b--,c--;
		d=a^b^c;
		if(d) cout<<"Win\n";
		else cout<<"Lose\n"; 
	}
	return 0;
}

1004 Black Magic

题目

​ 有二元组(0,0)，(0,1)，(1,0)，(1,1)各若干个，要将其按照某种顺序排列。相邻的两个二元组如果中间那个是1则会合并为一块，如(0,1)+(1,0) -> (0,0)。要求最少得到几块and最多得到几块。

分析

​ 最少，11并在一起，并且可以额外加上01和10，形如01111110,剩余的01与10配对，形如0110,0110。

​ 最多，01与10分别组合中间可插入一个11,00与11交替放最右边，形如101011010100110011.

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10,M=1e6+5;

int n,m,k;
int a[10];

void solve() {
    int x,y,z,w;
    cin>>x>>y>>z>>w;
    int ans1=0,ans2=0;
    ans1+=x+max(max(y,z),(int)!!w);
    ans2+=y+z+x+min(x+1,w);
    cout<<ans1<<" "<<ans2<<endl;
}

int main(){
    //freopen("data.in","r",stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
	while(T--) {
        solve();
	}
	return 0;
}

1003 Counting Stickmen

题目

​ 给定一棵树，1-2为头,3-4-6 和 3-9-10为一双手，3-5为身体，5-7和5-8是一双腿。问这个树有几个这样的子图。

分析

​ 寻找关键节点，当做身体，枚举对应的头手脚，

​ s0,s1,s2分别头，手，脚的数量

​ 头：$head=s0[x]-3head=s0[x]-3$ (排除手和脚，剩下的做头)

​ 脚: $foot=s0[y]-1\mathrm{}foot=s0[y]-1$ (y为连接脚的身体)

​ 手: $hand=s1[x]-foothand=s1[x]-foot$ (除去做手的部分)

​ 然后利用组合数，进行相乘

​ 其中两只手不能同一条链，$Hand=C_{hand}^2-(s2[x]-C_{deg[y]}^2)Hand=C\_\{hand\}^2-(s2[x]-C\_\{deg[y]\}^\{2\})$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=5e5+10,M=1e6+5;

int n,m,k;
int h[N],ver[N<<1],ne[N<<1],tot=0;
int s0[N],s1[N],s2[N];
int deg[N];

void init() {
    tot=0;
    for(int i=1;i<=n;i++) h[i]=0;
    for(int i=1;i<=n;i++) deg[i]=s0[i]=s1[i]=s2[i]=0;
}

void up(int x,int y) {
    ver[++tot]=y;ne[tot]=h[x];h[x]=tot;
}

inline int add(int a,int b) {return (a+=b)>=mod?a-mod:a;}

inline int sub(int a,int b) {return (a-=b)<0?a+mod:a;}

inline ll calc(int x) {return (ll)x*(x-1)/2%mod;}


void solve() {
    cin>>n;
    init();
    int x,y;
    for(int i=2;i<=n;i++) {
        cin>>x>>y;
        up(x,y); up(y,x);
        ++deg[x]; ++deg[y];
    }
    for(int x=1;x<=n;x++) {
        s0[x]=deg[x];
        for(int j=h[x];j;j=ne[j]) {
            int y=ver[j];
            s1[x]=add(s1[x],deg[y]-1);
            s2[x]=add(s2[x],calc(deg[y]-1));
        }
    }
    int ans=0;
    for(int x=1;x<=n;x++) {
        if(s0[x]>=4) {
            for(int j=h[x];j;j=ne[j]) {
                int y=ver[j];
                if(s0[y]<3) continue;
                int head=sub(s0[x],3);
                int foot=sub(s0[y],1);
                int hand=sub(s1[x],foot);
                ans=add(ans,(ll)head*sub(calc(hand),sub(s2[x],calc(deg[y]-1)))%mod*calc(foot)%mod);
            }
        }
    }
    cout<<ans<<endl;
}

int main(){
    //freopen("data.in","r",stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
	while(T--) {
        solve();
	}
	return 0;
}