1.统计星号

考点:简单模拟

class Solution {
public:
    int countAsterisks(string s) {
        int cl=0,ca=0,cb=0;
        //ca记录'*'的总出现次数，cb记录'*'在| |直接出现的次数
        for(auto c:s)
        {
            if(c=='|'){
                cl++;
                cl%=2;
            }
            if(c=='*')ca++;
            if(cl==1&&c=='*')cb++;
        }
        return ca-cb;  //返回没有在| |出现'*'的次数 
    }
};

2.统计无向图中无法互相到达点对数

考点:并查集求连通块(维护连通块点的数目)+计数问题

class Solution {
public:
       int f[100010];
        int cnt[100010];
    int find(int x)
    {
        return x==f[x]?x:f[x]=find(f[x]);
    }
    long long countPairs(int n, vector<vector<int>>& edges) {
        for(int i=0;i<n;i++)f[i]=i,cnt[i]=1;
        for(int i=0;i<edges.size();i++){
            int a=edges[i][0],b=edges[i][1];
            int fa=find(a),fb=find(b);
            if(fa!=fb)
            {
                f[fa]=fb;
                cnt[fb]+=cnt[fa];
            }
        }
        vector<int>ans;
        long long sum=0;
        for(int i=0;i<n;i++)
        {
            if(f[i]==i)
            {
                ans.push_back(cnt[i]);
                sum+=cnt[i];
            }
        }
        long long res=0;
        long long sz=0;
        //计数:乘法原理,每一个连通块都可以选除了它之外的其它连通块(注意是组合)
        for(int i=0;i<ans.size();i++)
        {
            res+=ans[i]*(sum-ans[i]-sz);
            sz+=ans[i];
        }
        return res;

    }
};

3.操作后的最大异或和

考点:思维

class Solution {
public:
    int maximumXOR(vector<int>& nums) {
        //我们可以按位考虑，如果在这一位上所有数都是0，那么这一位我们无论怎么操作都只能是0，反之，如果这一位
        //有至少一个1，我们都可以构造一种操作方案使得这一位是1，所有我们发现结果就是所有数|起来
        int res=0;
        for(auto c:nums)res|=c;
        return res;
    }
};

4.不同骰子序列的数目

考点:序列类dp

class Solution {
public:
    const int mod=1e9+7;
    //题目中第二个条件等价于序列中任意三个数字都不能一样，这里说明前面和后面的数之间会相互影响
    //所以启示我们要记录当前这一位的数是什么，以及上一位数是什么
    int dp[10010][7][7]; //考虑长度为n，最后一个数是i，倒数第二个数是j的所有方案
    int gcd(int a,int b)
    {
        return b?gcd(b,a%b):a;
    }
    int distinctSequences(int n) {
        if(n==1)return 6;
        for(int i=1;i<=6;i++){
            for(int j=1;j<=6;j++){
                if(gcd(i,j)==1&&i!=j)dp[2][i][j]=1;
            }
        }
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<=6;j++) //n
            { 
                for(int k=1;k<=6;k++) //n-1
                {
                    for(int z=1;z<=6;z++)
                    {
                        if(gcd(j,k)==1&&gcd(k,z)==1&&j!=k&&k!=z&&j!=z)
                        {
                            dp[i][j][k]=(dp[i][j][k]+dp[i-1][k][z])%mod;
                        }
                    }
                }
            }
        }
        int res=0;
        for(int i=1;i<=6;i++){
            for(int j=1;j<=6;j++){
                if(gcd(i,j)==1&&i!=j)res=(res+dp[n][i][j])%mod;
            }
        }
        return res;
    }
};