送分向水题，直接模拟即可。
#include<iostream>
#include<cstdio>
#define N 1505
using namespace std;
int n,m,k,a[N],now,ans,hve[N];
int main()
{
cin>>n>>m>>k;
for(int i=;i<=k;i++)cin>>a[i],hve[a[i]]=;
while(now<n)
{
ans++;
now+=m;
if(hve[now])m++;
}
cout<<ans<<endl;
return ;
}
枚举$x,y$，根据$xor$的性质算出z。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 2005
using namespace std;
int n,m,a[N],b[N],c[N],ans;
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
cin>>n>>m;
for(int i=;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
for(int x=;x<=m;x++)
{
for(int y=;y<=m;y++)
{
int z=((abs(a[]-x)^abs(b[]-y)^)),f=;
//a^b=c
//abs(a[1]-x)^abs(b[1]-y)^z=9
int zz=c[]-z;
if(zz>m||zz<=)f=;
for(int i=;i<=n;i++)
{
if((abs(a[i]-x)^abs(b[i]-y)^abs(c[i]-zz))!=)f=;
}
if(!f)ans++;
int ff=,_zz=c[]+z;
if(_zz>m||_zz<=||zz==_zz)ff=;
for(int i=;i<=n;i++)
{
if((abs(a[i]-x)^abs(b[i]-y)^abs(c[i]-_zz))!=)ff=;
}
if(!ff)ans++;
}
}
cout<<ans<<endl;
return ;
}
考试时写了50分做法，枚举每一个边选或不选，然后判断是否是凸多边形，判断一些边能否组成凸多边形很简单，看一下是否出最大值外的权值和是否大于最大值即可。
50分代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
#define N 5005
#define p (long long)(1e9+7)
using namespace std;
int T,n,ans,a[N];
int ksm(int a,int b)
{
int r=;
while(b)
{
if(b&)r*=a,r%=p;
a*=a;a%=p;
b>>=;
}
return r;
}
void dfs(int t,int sum,int maxn,int tot)
{
if(t==n+)
{
if(maxn<sum-maxn)
{
ans+=tot;
ans%=p;
}
return;
}
a[t]=;
dfs(t+,sum,maxn,tot);
a[t]=;
dfs(t+,sum+t,t,tot+);
}
signed main()
{
cin>>T;
while(T--)
{
cin>>n;ans=;
dfs(,,,);
cout<<(ans*ksm((<<n),p-))%p<<endl;
}
}
满分做法是$DP$。
设$f_i$为选出边长和为$i$的不合法方案数
设$w_i$为选出边长和为$i$的不合法权值和
对于$f$的转移，直接背包即可。
对于$w$的转移: 我们考虑加入一条长度$i$的边加入边集,那么如果是从$w[j-i]$转移到 $w[j]$, 那么就会在$w[j-i]$的所有状态的边集中加入一条长度为$i$的边然后考虑的不同的边集个数是$f[j-i]$那么在每一个边集中加入一条边的权值和, 就等价于在原本的权值和的基础上加上等同于边集的个数。
然后从小到大枚举并且累加答案即可。
100分代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 5005
#define int long long
#define p (long long)(1e9+7)
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
int ksm(int a,int b)
{
int r=;
while(b)
{
if(b&)r*=a,r%=p;
a*=a;a%=p;
b>>=;
}
return r;
}
int T,n,f[N],w[N],s[N];
void init(int n)
{
f[]=;
for(int i=;i<=n;i++)
{
s[i]=s[i-];
for(int j=;j<=i;j++)s[i]=(s[i]+f[j]+w[j])%p;
for(int j=n;j>=i;j--)f[j]=(f[j]+f[j-i])%p,w[j]=(w[j]+f[j-i]+w[j-i])%p;
}
}
signed main()
{
T=read();
init(N-);
while(T--)
{
n=read();
int xx=ksm(ksm(,n),p-)%p,xxx=1ll*n*ksm(,n-)%p;
cout<<(xx*(((xxx-s[n])%p)+p)%p)%p<<endl;
}
}
等我看懂题解......