D题：马的管辖
二进制枚举方案。判断该方案是否全部能被覆盖，将最优方案存下来并进行剪枝。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int vis[15][15];
int ans=0x3f3f3f3f;
int dx[]= {1,1,2,2,-1,-1,-2,-2};
int dy[]= {2,-2,1,-1,2,-2,1,-1};
int dx1[]= {1,1,1,1,-1,-1,-1,-1};
int dy1[]= {1,-1,1,-1,1,-1,1,-1};
int cnt[25];
bool cai(int x,int y)
{
for(int i=0; i<8; i++)
{
int rx=x+dx[i];
int ry=y+dy[i];
int mx=x+dx1[i];
int my=y+dy1[i];
if(rx>=0&&rx<5&&rx<5&&ry>=0&&!vis[mx][my]&&vis[rx][ry])
return true;
}
return false;
}
bool dfs()
{
for(int i=0; i<5; i++)
for(int j=0; j<5; j++)
{
if(!vis[i][j]&&!cai(i,j))
{
return false;
}
}
return true;
}
int main()
{
memset(cnt,0,sizeof(cnt));
int k[10];
memset(k,0,sizeof(k));
int s=0,j;
ans=15;
for(int x0=(1<<5)-1; x0>=0; x0--)
{
k[0]=0;
s=x0;
j=0;
while(j<5)
{
vis[0][j++]=s%2;
k[0]+=s%2;
s>>=1;
}
if(k[0]>ans)
continue;
for(int x1=(1<<5)-1; x1>=0; x1--)
{
k[1]=0;
s=x1;
j=0;
while(j<5)
{
vis[1][j++]=s%2;
k[1]+=s%2;
s>>=1;
}
if(k[0]+k[1]>ans)
continue;
for(int x2=(1<<5)-1; x2>=0; x2--)
{
s=x2;
j=0;
k[2]=0;
while(j<5)
{
vis[2][j++]=s%2;
k[2]+=s%2;
s>>=1;
}
if(k[0]+k[1]+k[2]>ans)
continue;
for(int x3=(1<<5)-1; x3>=0; x3--)
{
s=x3;
j=0;
k[3]=0;
while(j<5)
{
vis[3][j++]=s%2;
k[3]+=s%2;
s>>=1;
}
if(k[0]+k[1]+k[2]+k[3]>ans)
continue;
for(int x4=(1<<5)-1; x4>=0; x4--)
{
s=x4;
k[4]=0;
j=0;
while(j<5)
{
vis[4][j++]=s%2;
k[4]+=(s%2);
s>>=1;
}
if(k[0]+k[1]+k[2]+k[3]+k[4]>ans)
continue;
if(dfs())
{
ans=min(k[0]+k[1]+k[2]+k[3]+k[4],ans),cnt[k[0]+k[1]+k[2]+k[3]+k[4]]++;
}
}
}
}
}
}
printf("%d %d\n",ans,cnt[ans]);
return 0;
}
F题：找质数
这题描述有部分问题，字典序即数字最小的。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int n=5+1e6;
int prime[100005];
bool vis[1000005];
int init()
{
memset(vis,false,sizeof(vis));
int k=0;
prime[1]=true;
for(int i=2; i<=n; i++)
{
if(!vis[i])
{
prime[k++]=i;
for(int j=2; i*j<=n; j++)
vis[i*j]=true;
}
}
return k;
}
int main()
{
int k=init();
int t,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
for(int i=0; i<k; i++)
{
if(!vis[m-prime[i]])
{
printf("%d %d\n",prime[i],m-prime[i]);
break;
}
}
}
return 0;
}
G题：后缀字符串
用字典树做，先将每个字符串倒序加入树中，再挨个遍历寻找个数即可。
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
char b[100005][15];
struct node
{
int cnt;
int next[28];
void init()
{
cnt=0;
memset(next,-1,sizeof(next));
}
}a[1000005];
int tol=1;
void add(char l[],int n)
{
int p=0;
// printf("%s\n",l);
for(int i=n-1;i>=0;i--)
{
int c=l[i]-'a';
if(a[p].next[c]==-1)
{
a[tol].init();
a[p].next[c]=tol++;
}
p=a[p].next[c];
a[p].cnt++;
}
}
int query(char l[],int n)
{
int p=0;
for(int i=n-1;i>=0;i--)
{
int c=l[i]-'a';
if(a[p].next[c]==-1)
return 0;
p=a[p].next[c];
}
return a[p].cnt;
}
int main()
{
a[0].init();
int n,t;
int i,j;
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%s",b[i]);
add(b[i],strlen(b[i]));
}
for(i=0;i<n;i++)
{
printf("%d\n",query(b[i],strlen(b[i])));
}
return 0;
H题：轻重搭配
固定匹配人数n，二分寻找答案(注意区间是左闭右开)。
固定人数的话，最小的n个数肯定是要和最大的n个数匹配，如果有一个不匹配证明该匹配人数不符合。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[500005],n;
bool check(int x)
{
int pos1,pos2,k=0;
pos2=n-1;
pos1=x-1;
while(pos1>=0)
{
if(2*a[pos1]>a[pos2])
return false;
k++;
pos1--;
pos2--;
}
return true;
}
int main()
{
int i,l,r,mid;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
l=0,r=n/2+1;
while(l+1<r)
{
mid=(l+r)>>1;
if(check(mid))
l=mid;
else
r=mid;
}
printf("%d\n",l+n-2*l);
}
}
J题：蒜厂年会
因为可取的情况只有两种,第一种是取al,al+1,al+2,…..ar-1,ar。第二种是a1,a2…al, ar,ar+1…..an(l≤r)。
对于第一种我们求最大连续子段和即可。
对于第二种，我们要使两侧最大,即使中间最小即可，所以求出总和-最小连续和即可。
比较两种方式哪种值更大。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
int main()
{
ll maxi;
ll mini;
ll sum;
ll n,i,t,s,s2=0;
while(scanf("%lld",&n)!=EOF)
{
maxi=0;
mini=0;
sum=0;
s=0;
s2=0;
for(i=0; i<n; i++)
{
scanf("%lld",&t);
sum+=t;
s+=t;
s2+=t;
if(s>0)
s=0;
if(s2<0)
s2=0;
mini=max(mini,s2);
maxi=min(maxi,s);
}
printf("%lld\n",max(sum-maxi,mini));
}
}
