• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# [四校联考]Easy Problems

3小时前 2次浏览

## 简单计数

Description

Input

Output

Sample Input

``````3 8
``````

Sample Output

``````18
``````

HINT
(1;leq;n;leq;50,1;leq;m;leq;2500)
Solution

(f[i][j][k]=f[i-1][j-1][k-i])
(;;;;;;;;;;;;;;+f[i-1][j-2][k-itimes2]times[(i-1)-(j-2)])
(;;;;;;;;;;;;;;+f[i-1][j-1][k-i]times[(i-1)-(j-1)])
(;;;;;;;;;;;;;;+f[i-1][j-1][k-i]times[(i-1)-(j-1)])
(;;;;;;;;;;;;;;+f[i-1][j][k])

``````#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 55
#define M 1901
#define K 998244353ll
using namespace std;
typedef long long ll;
int n,m,mx;
ll f[N][N][M],mul=1ll,ans;
inline ll sqr(int k){
return (ll)(k*k);
}
inline void Aireen(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
mul=mul*(ll)(i)%K;
f[0][0][0]=1;
for(int i=1;i<=n;++i)
for(int j=0;j<=i;++j)
for(int k=0;k<M;++k){
if(j&&k>=i) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-i])%K;
if(j>=2&&k>=(i<<1)) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k-(i<<1)]*sqr(i-j+1)%K)%K;
if(j&&k>=i) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-i]*(ll)(i-j)%K)%K;
if(j&&k>=i) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-i]*(ll)(i-j)%K)%K;
f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%K;
}
for(int i=m;i<M;++i){
ans=(ans+f[n][n][i]*mul)%K;
}
printf("%lldn",ans);
}
int main(){
freopen("easycount.in","r",stdin);
freopen("easycount.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
``````

## 简单几何

Description

Input

Output

Sample Input

``````5 5
7612781 7923905
390883 6554981
8816160 3805981
4131888 3855473
4491640 5239819
998553 2850237
5957016 3387077
8511547 701391
8935990 677435
3706758 5650977
``````

Sample Output

``````18
``````

HINT
(n,m;leq;400)
Solution

``````#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 405
#define eps 1e-13
using namespace std;
typedef long long ll;
const double pi=acos(-1);
struct point{
int x,y;
}a[N],b[N];
struct cnt{
int s;double w;
}p[N+N];
int n,m,sum;ll ans;
inline bool cmp(cnt x,cnt y){
return x.w<y.w;
}
inline point dec(point x,point y){
return (point){x.x-y.x,x.y-y.y};
}
inline int mul(point x,point y){
ll k=(ll)(x.x)*(ll)(y.y)-(ll)(y.x)*(ll)(x.y);
if(!k) return 0;
if(k<0ll) return -1;
return 1;
}
inline void Aireen(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=m;++i)
scanf("%d%d",&b[i].x,&b[i].y);
for(int i=1;i<n;++i)
for(int j=i+1;j<=n;++j){
sum=0;
for(int k=1;k<=m;++k)
if(mul(dec(b[k],a[i]),dec(a[j],a[i]))>0) ++sum;
ans+=(ll)(sum*(m-sum));
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
p[j].w=atan2(b[j].y-a[i].y,b[j].x-a[i].x);
if(p[j].w>0.0) p[j].w-=pi;
else p[j].w+=pi;
}
sort(p+1,p+1+m,cmp);
for(int j=1;j<=m;++j){
p[j].s=0;
for(int k=1;k<j;++k)
if(p[j].w-p[k].w<pi) ++p[j].s;
else{
--p[j].s;ans-=(ll)(n-1);
}
for(int k=j+1;k<=m;++k)
if(p[k].w-p[j].w<pi) --p[j].s;
else ++p[j].s;
}
for(int j=1;j<i;++j){
p[j+m].s=N;p[j+m].w=atan2(a[j].y-a[i].y,a[j].x-a[i].x);
}
for(int j=i+1;j<=n;++j){
p[j+m-1].s=N;p[j+m-1].w=atan2(a[j].y-a[i].y,a[j].x-a[i].x);
}
sort(p+1,p+m+n,cmp);sum=0;
for(int j=1;j<n+m;++j){
if(p[j].s==N) ++sum;
else ans-=(ll)(sum*p[j].s);
}
}
printf("%lldn",ans);
}
int main(){
freopen("easygeom.in","r",stdin);
freopen("easygeom.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
``````

## 简单01串

Description

1. (01)串某一位取反；
2. (01)串前(k;times;m)位取反（(k)为整数且(0<k;times;m;leq;n)

Input

Output

Sample Input

``````12 3
010011001101
``````

Sample Output

``````3
``````

HINT
(n;leq;300,m;leq;55)
Solution

(1.mleqsqrt{n},)枚举循环节的(01)串,(DP)出每一段所需最少改变次数,(f[i][0/1])表前第(i)段是否取反所需最少步数,不足(m)的那一段直接判断.
(k)表示不娶反所需改变次数,
(f[i][0]=min(f[i-1][0],f[i-1][1])+k,)
(f[i][1]=min(f[i-1][0]+min(2,(i-1)m),f[i-1][1])+m-k).
(2.m>sqrt{n})枚举每一段是否取反,贪心判断(mod;m)相同的位变成相同所需最少改变次数.

``````#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 305
using namespace std;
typedef long long ll;
int f[N][2],g[N],a[N],b[N],n,m,sum,ans,cnt;
bool flag;char ch[N];
inline void dfs2(int u,int s,int f){
if(u<0){
int cnt=0;
for(int i=0,k,l=n-n%m;i<m;++i){
k=0;flag=false;
for(int j=i;j<n;j+=m){
if(j>=l) flag=true;
if(a[j]^g[j/m]) ++k;
}
if(flag) cnt+=min(n/m+1-k,k);
else cnt+=min(n/m-k,k);
}
ans=min(ans,cnt+s);
return;
}
g[u/m]=f;
dfs2(u-m,s,f);
g[u/m]=f^1;
dfs2(u-m,s+1,f^1);
}
inline void dfs1(int u){
if(u==m){
int cnt=0;
memset(g,0,sizeof(g));
for(int l=0,j;l<n;l+=m){
j=l/m;
for(int i=l;i<l+m&&i<n;++i)
if(a[i]!=b[i%m]) ++g[j];
if(n-l<m){
cnt=min(n%m-g[j],g[j]);
}
else if(!l){
f[l][0]=g[j];f[l][1]=m-g[j]+1;
}
else{
f[j][0]=min(f[j-1][0],f[j-1][1])+g[j];
f[j][1]=min(f[j-1][0]+min(2,l),f[j-1][1])+m-g[j];
}
}
ans=min(ans,min(f[(n-n%m-1)/m][0],f[(n-n%m-1)/m][1])+cnt);
return;
}
b[u]=0;dfs1(u+1);
b[u]=1;dfs1(u+1);
}
inline void Aireen(){
scanf("%d%d",&n,&m);
scanf("%s",ch);
for(int i=0;i<n;++i){
a[i]=ch[i]-'0';
if(a[i]) ++ans;
}
ans=min(ans,n-ans);
if(m<=17) dfs1(0);
else dfs2(n-n%m,0,0);
printf("%dn",ans);
}
int main(){
freopen("easy01.in","r",stdin);
freopen("easy01.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
``````

2017-01-26 19:18:31