B 博弈

虽然不难但是很有教育意义。很大一类博弈问题的思路都是：某一个量每轮都可以变化某一固定值，当这个量达到某一阈值时游戏结束。那么不管怎么操作，游戏的胜负在开始时都已经注定了，唯一的影响就是先后手，只要判断下奇偶就行了。

对这题来说，每轮都变化的固定值是每轮数字个数都会减一，阈值是结束时数字一定是奇偶交替排列，奇偶数量相等，也就是总数一定是偶数。那么就很简单了，开始时数字个数如果是奇数，先手必胜，反之先手必败。

不过考场上并没有做出来，因为没看到数字是在一个环上的，所以说一定要认真读题……

GH 枚举

只有三个元素，完全可以把他们所有的大小关系全枚举出来，然后看是否存在一种满足题目给出的约束。

然而重点还是读题，Z等于1表示确定x严格小于y，等于0表示不确定x是否严格小于y，并不是确定x严格大于y！！！！x可能小于y，也可能等于y！！！

当时看题干太长就以为前面的都是废话，结果这个k=0/1的定义实际上只在前面特长的那段资料里提过一次，后面没有再给出形式化题意。

using namespace std;
const int N=1e3+10;
int x[N],y[N],z[N];
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        bool flag=0;
        for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>z[i];
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++){
                for(int k=1;k<=3;k++){//枚举大小关系
                    int a[4];
                    a[1]=i;
                    a[2]=j;
                    a[3]=k;
//                     cout<<i<<' '<<j<<' '<<k<<' ';
                    bool flag2=1;
                    for(int p=1;p<=n;p++){//检验约束是否满足
                        if(z[p]==0){
                            if(a[x[p]]<a[y[p]]){
                                flag2=0;
                            }
                        }
                        else{
                            if(a[x[p]]>=a[y[p]]){
                               flag2=0;
                            };
                        }
                    }
//                     cout<<flag2<<'\n';
                    if(flag2)flag=1;
                }
            }
                
        if(flag)cout<<"Yes\n";//存在一组满足就可以
        else cout<<"No\n";
    }
}

J 期望，容斥

很多时候其实没想的那么难，关键是找到一些重要的性质。比如期望是可以线性叠加的，因此问总人数的期望，其实就是每个人成为心动嘉宾的期望的和，只需要单独计算每个人成为心动嘉宾的概率然后加起来。

一个人成为心动嘉宾，条件是所有他有好感的嘉宾中，至少有一个人选了他。用容斥来算就是所有他有好感的嘉宾都不选他的概率的反面。

using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
#define ll long long
ll qpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
ll inv(ll x){
    return qpow(x,mod-2);
}
vector<int>a[N],b[N];
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        b[v].push_back(u);
    }
    ll ans1=0;
    for(int i=1;i<=n;i++){
        ll t=1;
        for(int j:a[i]){//枚举所有有好感的嘉宾
            t=t*(1-inv(b[j].size())+mod)%mod;//这个人不选他的概率
        }
        ans1=(ans1+1-t+mod)%mod;//所有人都不选他的反面就是至少一个人选他
    }
    ll ans2=0;
    for(int i=1;i<=m;i++){
        ll t=1;
        for(int j:b[i]){
            t=t*(1-inv(a[j].size())+mod)%mod;
        }
        ans2=(ans2+1-t+mod)%mod;
    }
    cout<<"modint\n";
    cout<<ans1<<' '<<ans2;
}

k构造

这个思路确实不敢想，直接构造，最后能构造出来就是有，造不出来就是没有。

using namespace std;
const int N=1e6+10;
queue<int>qr,qb;
int ls[N],rs[N];
int tot,a,b,T;
bool build(queue<int>& in,queue<int>& out,int& cnt){
    if(cnt>=2&&!out.empty()){//还有至少两个叶节点的名额，并且还有可以父节点
        int x=out.front();
        out.pop();//取一个父节点出来
        ls[x]=++tot;//造两个叶节点，入队
        in.push(tot);
        rs[x]=++tot;
        in.push(tot);
        cnt-=2;//叶节点名额减二
        return 1;//构造成功
    }
    return 0;//反之构造失败
}
int main(){
    cin>>T;
    while(T--){
        cin>>a>>b;
        for(int i=1;i<=a+b;i++)ls[i]=rs[i]=-1;
        while(qr.size())qr.pop();
        while(qb.size())qb.pop();
        qb.push(1);//开始有一个黑色的根节点
        a--;//黑色名额减一
        tot=1;
        while(build(qb,qr,a)||build(qr,qb,b));//构造到不能构造
        if(!a&&!b){//如果两个颜色名额都刚好用完，构造成功
            cout<<"Yes\n";
            for(int i=1;i<=tot;i++)cout<<ls[i]<<' '<<rs[i]<<'\n';
        }
        else{//反之构造失败
            cout<<"No\n";
        }
    }
}

LM map统计数对，数论

统计数对，经典问题，首先应该考虑的思路就是单向遍历，每读一个元素就检测map里有多少可以和当前元素构成合法数对的元素，最后再把这个数也加入map

以上是一般性的思路，本题的特殊性在于要统计的是有多少数对，拼起来是36的倍数。这里又有两种思路，特殊一点的是36是4和9的倍数，我们可以从4和9倍数的特征入手，4的特征是最后两位是4的倍数，9的特征的是所有数位之和是9的倍数。一般性的思路是，假设这里的36是一个更一般的数字m，开map统计膜m的余数分别为0-m-1的元素的个数，然后没读一个元素，就遍历0-m-1，看哪些余数的元素可以和当前元素拼成膜m余0的数。

对于最后一步，假设当前读取的元素放在低位，map里取出的元素放在高位，那么实际上就是要判断(j*10^len(i)+i)%36是否为0。根据模运算的规则，可以转化为(j*(10^len(i)%36)+i)%36，j和i都不大，唯一的问题是这个10^len(i)%36，注意到她只和长度有关，和具体是什么数无关，可以预处理。当然这里还有一个特殊的性质，就是10大于等于2次幂膜36都为28，因此其实10^len(i)%36只有两种可能，10是10，100及以上是28

using namespace std;
#define ll long long
vector<ll>a;
int main(){
    ll ans=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        ll t;
        cin>>t;
        a.push_back(t);
    }
    auto cal=[&](){
        ll cnt[40]={0};
        for(auto i:a){//i作为右边的数
            for(int j=0;j<36;j++){//枚举所有左边的数
                if((j*(i<10LL?10LL:28LL)+i)%36==0){//判断拼起来是否是36倍数
                    ans+=cnt[j];//是的话加上贡献
                }
            }
            cnt[i%36]++;//当前i也加入map
        }
    };
    cal();
    reverse(a.begin(),a.end());//前面是被枚举的数只能在右边，漏了一些情况
    cal();//数组反过来，再算一遍
    cout<<ans;      
}