ABC147

早上花2个多小时全过了，来写篇总集

ABC147A Blackjack

题解：

3行签到题，模拟即可

代码：

略

ABC147B Palindrome-philia

题解：

正着反着同时扫，不同就ans++

代码：

略

ABC147C HonestOrUnkind2

题解：

n很小，所以可以直接$2^n$枚举哪些是好的，一个简便的做法就是通过枚举$1~2^n-1$这些数，第i位为1则表示第i个人是好的，再对每种情况依次去检查每句“好人”说的话，如果与自己的枚举相矛盾则不合法，否则合法就统计1的个数（即好人的个数），取最大的输出

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=17;
int n,ans,a[N],x[N][N],y[N][N];

bool check(int s){
    for(int i=0;i<n;i++) if(s>>i&1)
        for(int j=1;j<=a[i];j++) if((s>>x[i][j]&1)!=y[i][j])
            return 0;
    return 1;
}

int count(int x){
    int ans=0;
    while(x){
        if(x&1) ans++;
        x>>=1;
    }
    return ans;
}

signed main(){
    read(n);
    for(int i=0;i<n;i++){
        read(a[i]);
        for(int j=1;j<=a[i];j++)
            read(x[i][j]),read(y[i][j]),x[i][j]--;
    }
    int lim=1<<n;
    for(int s=0;s<lim;s++) if(check(s)) ans=max(ans,count(s));
    write(ans);
}

ABC147D Xor Sum 4

题解：

注意到异或，这说明所有的异或值都是各自独立的，我们就可以用每一位上1的个数乘每一位上0的个数得到答案中该位上的数

十分巧妙的是，虽然这是二进制，但并不用考虑高精（我就打了高精），因为改为的单位值乘上该位的数值，自动就会帮你进位到较高位，依次类推

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int mod=1e9+7;
int ans,cnt[70],n;

signed main(){
    read(n);
    for(int i=1,x;i<=n;i++){
        read(x);
        for(int j=0;j<60;j++) if(x>>j&1ll) cnt[j]++; //cnt[i]表示第i位上1的个数
    }
    for(int i=0;i<60;i++) (ans+=cnt[i]*(n-cnt[i])%mod*((1ll<<i)%mod)%mod)%=mod;
    write(ans);
}

ABC147E Balanced Path

题解：

递推题，详见这里

代码：

同上

ABC147F Sum Difference

题解：

递推题，详见这里

代码：

同上