A题：给你一串只有0和1的字符串，让你通过使一个区间异或后所得的字符串中1的个数最大。
小结：题目以来没想太多，以为是找最长有多少个0，直接交了一发WA，最后看了下数据，暴力秒过。
代码：
#include<iostream>
using namespace std;
int sum[105];
int a[105];
int main()
{
int n;
cin>>n;
sum[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
int max=-1;
int ans1,ans2;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
ans1=sum[j]-sum[i-1];
ans2=j-i+1-ans1;
ans2=ans2+sum[i-1]+sum[n]-sum[j];
if(ans2>max)
max=ans2;
}
}
cout<<max<<endl;
return 0;
}
B题：让你构造一串数，使得后面一个不能别前面的任意一个数整除。
小结：这题以来没想过直接打素数表，数的长度为10^5，而数的范围是10^7，以为10^7中不可能有10^5个素数，后来测试了下，第10^5个素数才1200000左右。
代码：
#include<iostream>
using namespace std;
int a[1500000];
int main()
{
int n;
a[1]=0;
for(int i=2;i<=1500000;i++)
{
if(a[i]==0)
{
for(int j=i+i;j<=1500000;j+=i)
a[j]=1;
}
}
cin>>n;
int count=0;
for(int i=2;i<=10000000;i++)
{
if(a[i]==0)
{
cout<<a[i];
count++;
if(count!=n)
{
cout<<' ';
}
else
{
cout<<endl;
break;
}
}
}
return 0;
}
C题：让你找公式，然后用快速幂取余，还得使用费马小定理求逆元。
费马小定理：(a,p)=1,则a^(p-1)=1modp;
快速幂：
//a^nmodb
long long POW(long long a,long long n,long long b)
{
long long ret=1;
while(n)
{
if(n&1)
{
ret=(ret*a)%b;
}
n/=2;
a=(a*a)&b;
}
return ret;
}
这里还用到了预处理，2^n
代码：
#include<iostream>
#include<cstring>
#include<cmath>
#define N 1000000007
#define ll long long
using namespace std;
char s[100005];
int p[100005];
void init()
{
p[0]=1;
for(int i=1;i<=100005;i++)//2^n
{
p[i]=(p[i-1]*2)%N;
}
}
long long f(long long a,long long n,long long b)
{
long long t=a;
long long ans=1;
while(n)
{
if(n&1)
{
ans=(ans*t)%b;
}
n>>=1;
t=(t*t)%b;
}
return ans;
}
int main()
{
long long k;
cin>>s;
cin>>k;
long long l=strlen(s);
long long ans1=0;
init();
for(int i=0;i<l;i++)
{
if(s[i]=='0'||s[i]=='5')
ans1=(ans1+p[i])%N;
}
long long q=(p[l]-1+N)%N;
q=f(q,N-2,N)%N;//分母
long long tmp=(f(p[l],k,N)-1+N)%N;//分子
tmp=(tmp*q)%N;
cout<<(ans1*tmp)%N<<endl;
return 0;
}
D题：给你一个图，只能在空地上建两种房子，blue，red，而建red的时候必须有blue相邻，并且可以拆房子然后再重建，blue人口容量100，red人口容量200，求怎样才能是的人口容量最大。
小结：直接用dfs()搞，开始把所有的房子都建成blue，回溯的时候在把房子拆了建成red，最开始的房子不拆。
代码：
#include<iostream>
#include<cstdio>
#define maxn 505
using namespace std;
int n,m;
char s[maxn];
int map[maxn][maxn],vis[maxn][maxn];
int count=1;
struct node
{
int x,y;
char a;
}p[1000005];
int xx[]={0,0,1,-1};
int yy[]={-1,1,0,0};
bool inmap(int x,int y)
{
if(1<=x&&x<=n&&1<=y&&y<=m) return true;
else
return false;
}
void dfs(int x,int y)
{
int nx,ny;
for(int i=0;i<4;i++)
{
nx=x+xx[i],ny=y+yy[i];
if(inmap(nx,ny)&&(vis[nx][ny]==0)&&map[nx][ny]==0)
{
p[count].a='B';
p[count].x=nx,p[count].y=ny,count++;
vis[nx][ny]=1;
dfs(nx,ny);
p[count].a='D';
p[count].x=nx,p[count].y=ny,count++;
p[count].a='R';
p[count].x=nx,p[count].y=ny,count++;
}
}
}
int main()
{
int l;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
for(int j=0;j<m;j++)
{
if(s[j]=='.')
map[i][j+1]=0;
else
map[i][j+1]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(vis[i][j]==0&&map[i][j]==0)
{
vis[i][j]=1;
p[count].a='B';
p[count].x=i,p[count].y=j,count++;
dfs(i,j);
}
}
}
printf("%d\n",count-1);
for(int i=1;i<count;i++)
{
printf("%c %d %d\n",p[i].a,p[i].x,p[i].y);
}
return 0;
}
E题：给你一串数，从0开始，每次选某个数，然后向前移动ai长度，这里有些位置不能走，最后问你走到总长度的路有多少条。
小结：很裸的状压dp，不过得用sum数组优化下。
dp[i]=sum{dp[i^(1<<j]};i与j只相差一位，即i能通过i^(1<<j)增加aj转移过来。
代码：
#include<iostream>
#include<cstdio>
#define N 1000000007
#define maxn 1<<25
using namespace std;
int n,k;
int a[25],b[3],dp[maxn],sum[maxn];
int DP()
{
dp[0]=1;//只能从0开始
for(int i=1;i<(1<<n);i++)
{
//求出当前状态所在的位置
sum[i]=0;
int p;
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
p=j;//从小到大找第一个为1的位置
break;
}
}
sum[i]=sum[i^(1<<p)]+a[p];//去掉这个位置的状态一定已经访问过
//判断当前位置是否可以停留
int flag=0;
for(int j=0;j<k;j++)
{
if(sum[i]==b[j])
{
flag=1;
break;
}
}
//不可以的话，直接忽略，当前的路径和为0
if(flag==1) continue;
//动态转移
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
dp[i]+=dp[i-(1<<j)];
if(dp[i]>N)//这里没用%
dp[i]-=N;
}
}
}
return dp[(1<<n)-1];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&k);
for(int i=0;i<k;i++) scanf("%d",&b[i]);
printf("%d\n",DP());
return 0;
}