水题
由于整个串是回文串，只要判断前一半和后一半有多少个不同即可
\(N\) 只有15，直接枚举出所有的情况 \(2^N\) 种，对每一种方案判断合法性即可，只要找诚实的人来判断。
点击展开代码
#include<bits/stdc++.h>
using namespace std;
vector<int>x[20],y[20];
int n;
int js(int x){
int ans=0;
while(x){
ans+=(x&1);
x>>=1;
}
return ans;
}
bool check(int X){
int temp[20]={0};
for(int i=1;i<=n;i++){
if((X>>(i-1))&1)temp[i]=1;
else temp[i]=0;
}
for(int i=1;i<=n;i++){
if(temp[i]){
int siz=x[i].size();
for(int j=0;j<siz;j++){
int id=x[i][j];
if((temp[id]^y[i][j])==1)return 0;
}
}
}
return 1;
}
int main()
{
//freopen("H:\\c++1\\in.txt","r",stdin);
//freopen("H:\\c++1\\out.txt","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int m;
scanf("%d",&m);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
x[i].push_back(a);y[i].push_back(b);
}
}
int mx=(1<<n);
int ans=0;
for(int i=0;i<mx;i++){
if(check(i)){
ans=max(ans,js(i));
}
}
printf("%d\n",ans);
return 0;
}给定 \(n\) 个数字，要求求出 \(\sum^{n-1}_{i=1}\sum^{n}_{j=i+1}a_i\ xor\ a_j\)
我们将每一位单独计算贡献，比如讨论第 \(i\) 位，那么把 \(n\)个数字的第 \(i\) 位取出来，\(b_1,b_2,...,b_n\) 那么对于\(b_j\) 如果是 \(0\) ，那么能 \(xor\) 为 \(1\) 的个数为 \([j+1,n]\) 的 \(1\) 的个数。最后把所有计算 \(1\) 的个数相加\(*2^i\) ，那么这就是该位对答案的贡献了。复杂度为 \(O(n*60)\)
点击展开代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+10;
const int mod=1e9+7;
ll a[N],p[N];
ll sum[N];
int n;
int main()
{
//freopen("H:\\c++1\\in.txt","r",stdin);
//freopen("H:\\c++1\\out.txt","w",stdout);
p[0]=1;
for(int i=1;i<=100;i++)p[i]=(p[i-1]*2)%mod;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
ll ans=0;
for(ll i=0;i<=60;i++){
for(int j=1;j<=n;j++){
if((a[j]>>i)&1)sum[j]=sum[j-1]+1;
else sum[j]=sum[j-1];
}
ll cnt=0;
for(int j=1;j<n;j++){
if((a[j]>>i)&1){
cnt+=(n-j-(sum[n]-sum[j]));
}else{
cnt+=(sum[n]-sum[j]);
}
}
cnt%=mod;
ans=(ans+(1ll*cnt*p[i]%mod))%mod;
}
printf("%lld\n",ans);
return 0;
}给一个矩阵，每一个位置有两个数字，现在从左上走到右下，每次将位置的两个数字一个标记红色，一个标记蓝色，问 \(红色数字蓝色数字|\sum{红色数字}-\sum{蓝色数字}|\) 最小是多少
感觉就很像 \(dp\) ，用 \(dp[i][j][k]\) 表示走到 \((i,j)\) ，对于差值为 \(k\) 能否得到，假设当前走到 \((i,j)\) ，两个数字的差值为 \(cha=|a_{ij}-b_{ij}|\) 那么状态转移就是
\(dp[i][j][k\pm cha]=dp[i-1][j][k]\ if(dp[i-1][j][k]=True)\)
\(dp[i][j][k\pm cha]=dp[i][j-1][k]\ if(dp[i][j-1][k]=True)\)
可以用bitset来优化
点击展开代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=100;
const int M=6401;
const int Y=6400;
bitset<M*2> dp[N][N];
int n,m;
int a[N][N],b[N][N];
int main()
{
//freopen("H:\\c++1\\in.txt","r",stdin);
//freopen("H:\\c++1\\out.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
dp[1][0][Y]=1;dp[0][1][Y]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int cha=abs(a[i][j]-b[i][j]);
dp[i][j]|=((dp[i-1][j]<<cha)|(dp[i-1][j]>>cha));
dp[i][j]|=((dp[i][j-1]<<cha)|(dp[i][j-1]>>cha));
}
int ans=inf;
for(int i=0;i<M*2;i++){
if(dp[n][m][i])ans=min(ans,abs(i-Y));
}
printf("%d\n",ans);
return 0;
} 给一个 \(n\) 个数的等差数列，首项为 \(x\) ，公差为 \(d\) ，现在在数列中选择 \(k\) 个数，设计 \(S\) 为 \(k\) 个数的和， \(T\) 为剩下 \(n-k\) 的数的和。为共有多少个 \(S-T\) 的值。
假设所有数字之和为 \(sum\) ，那么 \(S-T=S-(sum-S)=2*S-sum\) ，那么其实就是求 \(S\) 的不同值的个数。假设 \(S=k*x+m*d\) ，其中 \(k\) 就是选择的数的个数， \(m\) 是一个值， \(m\) 应该在 \([0+1+...+k-1,n-k+n-(k+1)+...+n-1]\) 的范围之内。那么对于一个 \(k\) 值， \(S\) 的值就是在一个 \([L,R]\) 中，然后每一个数字间隔 \(d\) ，而且这些值 \(S\%d\) 都是相等的。那么我们就对所有的 \(S\) 用 \(d\) 将它们分成一个剩余系，不同剩余类中的元素是不会相等的，决定其位于哪个剩余类是 \(k*x\%d\) 的值。为了得到每一个剩余类的元素个数，我们将S/d，那么就会得到许多的区间，按照k*x%d分类，对于每一个类将区间排序，合并，计算即可。
感觉比较抽象，具体来说就是，一个模d余0剩余类中的数字为 \(，，，，x，x+d，x+2*d，x+3*d，...\) ，那么一个模d余1剩余类的数字为 \(，，，x+1，x+1+d，x+1+2*d，....\) ，那么我们就对每一个剩余类来求解。
点击展开代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=2e5+10;
struct node{
ll l,r;
bool operator < (const node &x)const{
if(l!=x.l)return l<x.l;
return r<x.r;
}
node(ll a=0,ll b=0){l=a,r=b;}
};
map<ll,vector<node> >s;
ll n,x,d;
ll sum[N];
int main()
{
//freopen("H:\\c++1\\in.txt","r",stdin);
//freopen("H:\\c++1\\out.txt","w",stdout);
for(int i=1;i<N;i++)sum[i]=sum[i-1]+i;
scanf("%lld%lld%lld",&n,&x,&d);
if(x==0&&d==0){
puts("1");return 0;
}
if(x!=0&&d==0){
printf("%lld\n",n+1);return 0;
}
if(d<0)d*=-1,x*=-1;
ll L=0,R=0;
for(ll i=0;i<=n;i++){
ll t=i*x;
L=sum[i-1];
R=sum[n-1]-sum[max(0ll,n-i-1)];
L+=t/d,R+=t/d;
t%=d;
if(t<0)t+=d,L--,R--;
s[t].push_back(node(L,R));
}
ll ans=0;
for(auto it:s){
sort(it.se.begin(),it.se.end());
L=it.se[0].l,R=it.se[0].r;
for(node v:it.se){
if(v.l>R){
ans+=R-L+1;
L=v.l,R=v.r;
}
else{
R=max(v.r,R);
}
}
ans+=R-L+1;
}
printf("%lld\n",ans);
return 0;
}<\details>
原文：https://www.cnblogs.com/C-W-K/p/12013626.html